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. 关闭文件，打印当前时间