虚网映射仿真包 embed.c 代码分析

发表于 更新于 分类于 Disqus： 本文字数： 4k 阅读时长 ≈ 7 分钟

此次论文仿真中，需要对虚网映射的过程进行改进。在原先只考量CPU和带宽的基础上为链路增加VLAN属性，并在映射过程中分配VLAN、检测VLAN是否用尽。经过三天的阅读，这里把仿真包里embed.c这个主要文件的各函数分析在下面，方便日后修改。

数据结构

数据结构存储在embed.h中。

  • struct_link 描述物理链路，有from、to、带宽三个属性
  • request 虚网请求，有split, node, links, CPU[], bw等多个属性。
  • substrate_network 底层物理网络，有nodes, struct_link links等属性
  • s2v_node 被映射了虚网的物理节点的状态
  • s2v_link 被映射了虚网的物理链路的状态
  • path 逻辑链路映射成的多段物理链路
  • req2sub 描述虚网映射的实时映射关系
  • shortest_path 最短路径，通过Floyd算出（用于链路映射）
  • bneck 瓶颈节点

相关函数

节点映射

find_proper_node

目标：在当前底层物理网络中寻找rest_cou最适合（rest_cpu和request CPU最近，且大于它）当前虚节点的节点。

find_MinNeighborResource_node

目标：在当前底层物理网络中寻找rest_cpu满足要求，且自资源最不丰富的物理节点

衡量标准：节点rest_cpu * sum(rest_bw)

find_MaxNeighborResource_node

目标：在当前底层物理网络中寻找除了exclude节点外的rest_cpu满足要求的，且自资源最丰富的物理

节点

衡量标准：同上

find_available_node

目标：在当前底层物理网络中，从一随机起点出发，寻找第一个rest_cpu满足要求的物理节点

map_node_greedy

目标：在当前物理网络中，为特定index的虚网映射进行节点映射，哟西按占用资源最丰富的节点，成功则更新物理网络的状态（s2v_node, s2v_link），失败则对已映射的节点进行拆除。

map_node_star

目标：在当前物理网络中，为第一个请求节点分配资源最丰富的节点，其余逻辑节点随机分配，成功则更新物理网络的状态（s2v_node, s2v_link），失败则对已映射的节点进行拆除。

链路映射

由于链路映射算法大多很复杂，这里将算法流程也一并列在下方。

unsplittable_flow

目标：为不可分割流进行链路映射

算法流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
0  初始化变量，位置分配内存空间
1  死循环
1.1  找到请求中状态满足要求（完成了节点映射）且收益最大的请求，直到状态全部更新
1.1.1    存储id,改变其标志位
1.2  判断该请求状态，与是否可分割
1.2.1    找到该请求的所有逻辑链路
1.2.1.1      找到它们的起始、终结物理节点
1.2.1.2      判断它们是否已找到之间的最短路，否则继续寻找
1.2.1.2.1        Floyd矩阵找下一跳
1.2.1.2.2        下一跳若不可达，break
1.2.1.2.3        寻找有没有实体链路对应Floyd的下一跳
1.2.1.2.4        如果没有，或者有但是rest_bw不够，break
1.2.1.2.5        吧路过链路的可用带宽减少，将当前链路存入到路径数组中
1.2.1.3      如果上一步失败，给sub1(底层物理网络)划分内存空间，在sub1里删除上步出现问题的链路
1.2.1.4      在sub1里算出Floyd矩阵，并存储在临时变量里
1.2.1.4.1        一个类似于1.2.1.2的循环
1.2.1.4.1.1          若还不行，break到1.2.1.4.2；若可以减少可用带宽，存入到路径
1.2.1.4.2        返回错误物理链路、虚拟链路、虚网请求id
1.2.1.5      存储当前算出的路径，与逻辑链路一一对应
2  将状态标志位全部清零
3  死循环
3.1    找到请求中状态满足要求（完成了节点映射）且收益最大的请求，直到状态全部更新
3.1.1      存储id, 改变标志位
3.2    判断该请求状态，与是否可分割
3.2.1      更新时间与链路状态值
3.2.2      为请求内的spath赋值(len, bw)
3.2.2.1        为spath内的各段物理链路赋值
3.2.2.2        更新物理网络链路状态
4  释放临时变量空间
5  返回-1(虚网请求成功标志)

multicommodity_flow

目标：打印基本信息

算法流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1  打开测试文件
2  指定范围内检测有误状态符合条件的请求，
3  若没有，则返回-2并关闭文件
4  打印出满足要求的链路总数
5  打印基本信息到文件
6  打印ARC COSTS到文件
7  打印ARC CAPACITIES到文件
8  打印NODE INJECTIONS到文件
9  打印ARC MUTUAL到文件
10 打印NETWORK TOPOLOGY到文件
11 打印LOWER AND UPPER BOUNDS到文件
12 打印SIDE CONSTRAINTS到文件
13 关闭文件对象
14 运行lintest文件
15 返回 0

检测

check_flow

目标：检查映射情况

算法流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1  打开test文件，初始化变量
2  查找STATUS字段，停在此处
3  若不可执行，且阶段 0，则关闭文件，返回 -3
4  若不可执行，且阶段 1，则继续
4.1    查找VARIABLE字段
4.2    在每条链路上查找已使用过的情况，为s2v_link赋值
4.3    查找SIDE CONSTRAINTS字段
4.3.1      找到过载最严重的链路
4.3.2      找到该链路占用最多贷款的租户ID，及其占用带宽，并确定请求ID和虚拟链路ID
5  其余情况，查找OPTIMAL字段，若找到，则继续
5.1    查找VARAIABLE字段
5.2    在每条链路上查找已使用过的情况，为s2v_link赋值
5.3    为v2s赋值
6  关闭文件，释放内存
7 打印租户ID或-1（成功标志）

资源分配

同样，算法复杂，将具体流程列在下面

allocate

目标：整合节点、链路映射完成虚网映射的核心部分

算法流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1  为变量s2v_node,s2v_link,v2s划分空间，赋初值
2  为节点数组req_count清零
3  将请求按收入大小排序，找出最大收入者，为它进行节点映射，知道请求的节点映射全部完成
4  若全部未完成节点映射，返回-1
5  初始化链路映射相关变量
6  找到瓶颈节点，并进行链路映射（尝试）
7  若映射成功或链路可分割，用新方法找到瓶颈节点
8  循环：
8.1    如果上一步尝试成功，为s2v_node, s2v_link赋值，跳出循环
8.2    否则，计算这一批次的cost之和
8.3    找出剩余资源最少的节点ID，及其剩余资源
8.4    随机从上面移除一个虚拟节点
8.5    找到这个节点以外资源最丰富的节点，成功则映射到这个新节点；否则映射请求失败
8.6    检查有误未完成链路请求的虚网请求，无则跳出循环
8.7    若时间正忙而无法映射，try=门限+1，找到未完成的请求ID
8.8    cost清零，try+1，打印try次数
8.9    若try > 尝试门限，释放资源，更改状态，还原try
8.10   否则，找到瓶颈链路上的任一节点外的资源最丰富的节点
8.10.1     若找到，则映射；否则这个请求失败
8.11   检查链路映射是否完成，为s2v_node, s2v_link, v2s赋值
9  检查当前瓶颈节点，尝试链路映射
10 为s2v_node, s2v_link等赋值，用cost防止重复操作
11 检查新映射是否cost更低，是则更新
12 #允许迁移则继续向下
13 计算原始cost，释放原始映射资源，进行新的映射
14 新的映射成功则计算新cost，否则返回 0
15 新的cost是否更小，是则迁移，否则不做操作
16 还原s2v_node, ltmp
17 用unsplittable映射计算一次cost，若新的cost更小，则迁移；否则不作操作
18 更新s2v_node, s2v_link v2s
19 返回 0

辅助

calculate_cost

目标：返回指定范围内的虚网请求cost之和。cost算法同上

筛选标准：完成链路映射

exist_req

目标：查找是否存在完成了节点映射，未完成链路映射的请求。存在，则返回0，否则返回-1。

主函数 main

算法流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
1  为v2s, s2v_node, s2v_link, sub, req 赋初值
2  打开底层网络文件
3  为sub赋node(sub.s2v_nod(req_count,rest_cpu,cpu),sub.link(from,to,s2v_l,rest_bw))
4  关闭文件
5  循环打各req的文件
5.1   为req的revenue/nodes,links,split,time,duration,topo)赋值
5.2   循环为req的cpu,link.from,link.to,link.bw赋值
5.3   计算出revenue
6  关闭文件
7  为临时变量s2v_node/ltmp2/v2stmp2/spath分配内存空间
8  计算得到spath值
9  初始化临时变量
10 循环：
10.1   循环检测所有完成链路映射的请求，为done_count+1
10.2   更新done,rev,cost,map状态，若映射完成则释放资源
10.3   计算当前req.rev/cost/count
10.4   写入当前数据到文件
11 为当前所有请求进行映射
12 依次次检测所有请求状态，更新未请求成功的状态与错误计数器
13 打开stat文件
14 为成功的虚网请求释放资源
15 计算当前req,dev/cost/count
16 写入当前数据到stat文件/trace文件
17 关闭文件
18 返回 0