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

此次论文仿真中,需要对虚网映射的过程进行改进。在原先只考量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