vnm test学习

师兄给了一个虚网映射的仿真(cpp),和之前的embed-detail的C语言仿真工具很像,经过一周左右的学习,挖掘出了其中虚网映射部分的内容,在此整理,以作日后学习。鉴于之前embed-detail的学习总结很繁琐,这里的总结只做精要的介绍。

数据结构

这一部分在Utility.h中完成,是对映射种种数据容器的整理。

节点:

编号,CPU,带宽和,优先度

最短路:

跳数,带宽,路径列表,下一跳

映射结果(单节点):

物理节点对象,虚拟节点编号,所属根节点,到根节点跳数,Node_list中序号,Node_list总数

(类)物理拓扑:

节点总数,边总数,资源,节点资源,边资源;

节点群(一维向量),边群(二维向量),最短路群(二维结构向量);

方法:

  • 初始化,
  • 节点排序算法,
  • Floyd算法,
  • 找到节点序号对应的下标,
  • 计算网络资源

(类)虚拟拓扑(继承物理拓扑):

//同物理拓扑

允许最大跳数,分割率,拓扑类型,起始时间,映射时间,存活时间,消耗,节点消耗,链路消耗,收入,收入支出比,是否匹配成功,是否起请求截止,是否delay过,是否失败

满足约束条件的节点群(二维向量),结果群(结果向量),最短路群(二维链表向量)

方法:

  • 读入拓扑,
  • 初始化,
  • 计算最短路径和,
  • 查找结点是否已经映射,
  • 匹配节点(包含匹配边),
  • 匹配边,
  • 匹配过程(包含匹配节点),
  • 分配或释放资源(匹配过程中完成),
  • 打印结果,
  • 计算收入支出,
  • 计算收入,
  • 释放虚网的所有资源

核心方法分析

这一部分在Utility.cpp中完成,是对映射种种方法的实现。

(物理网络)

1. 初始化:开辟最短路群空间,计算链路CPU/带宽和/PR值

2. 计算资源:节点,链路资源相加。

(虚拟网络)

1. 读入文件:读入节点数,链路数,开始时间,存活时间等。

2. 初始化:填充Node_list

3. 查找结点是否已被映射:for 循环遍历暴力查找

4. 匹配节点:读入物理网络和参照物理网络,当前结点所属根节点,已映射节点数。

(1)打印

(2)从可行最短跳(虚拟网络中的跳数)到最大允许跳开始循环

(2.1)从可行节点(Node_list)中查找满足CPU要求的节点

(2.2)查找匹配边(Match_Edge),若有打印信息并返回

(3)打印失败信息返回

5. 匹配链路:读入物理网络预期参照,当前结点编号和下标,已映射节点数。

(1)循环寻找所有与该节点关联的节点

(1.1)若有关联,清空并循环更新最短路向量

(1.2)循环检测带宽是否满足要求

(2)循环还原减少的带宽资源

(3)返回成功标记

6. 匹配:读入物理拓扑,完成一个虚网的匹配

(1)建立物理拓扑最短路矩阵

(2)初始化最短路群,root, chosen_num(已选中节点数)

(3)初始化根节点result类实例,若无备选节点,返回 0

(4)循环寻找可行的根节点直到遍历完成

(4.1)以当前父节点为基础开始匹配子节点,循环

(4.1.1)循环寻找父节点的关联的子节点

(4.1.1.1)若某节点无匹配物理节点,循环释放资源,返回 0

(4.1.1.2)若找到,更新result群向量,调用匹配节点,找到对应物理节点序号

(4.1.1.2.1)若成功返回,继续更新result,最短路矩阵,更新底层资源

(4.1.1.2.2)若不成功,回退chosen_num,释放资源,更新root,最短路

(4.1.2)若未回退到根节点,不用调整根节点,继续从下个父节点开始匹配,直到匹配完成

(4.2)若匹配未完成,释放根节点和其余资源

(5)若匹配成功计算收入支出返回回退次数,否则释放资源,返回 0;

7. 资源管理:通过标记值区分占用或是释放,循环更新节点和链路资源

8. 打印,计算收入支出

9. 释放虚网资源:循环释放,返回释放资源值

主程序

这一部分在VNM.cpp中完成,是时间窗模型下虚网映射的实现。步骤如下:

1. 初始化临时变量,

2. 从文件中读入底层物理网络,虚网请求

3. 打印初始信息,计算物理资源

4. 循环到所有请求都被处理完成或是有finish标记

4.1 循环计算该窗口内待映射请求数

4.2 循环这些请求

4.2.1 挑出未延迟且未成功的

4.2.1.1 初始化虚网,打印信息

4.2.1.2 开始匹配,计算时间

4.2.1.3 计算收入,更改标记为映射完成或延迟

4.2.1.4 计算当前物理资源,写入到文件

4.2.2 挑出匹配成功且到期的请求

4.2.2.1 更新它们的R/S和完成数目

4.2.2.2 释放它们的资源

4.2.3 挑出delay过久的请求,置为失败,更新资源和计数器

4.3 计算该时间窗内的支出,收入等数据,更新finish和计数器

4.4 打印该时间窗测试数据到文件

4.5 更新时间窗时间

5. 关闭文件,打印当前时间