Page 313 - 《软件学报》2020年第9期

2934 Journal of Software 软件学报 Vol.31, No.9, September 2020

输出: Sol BL ij .
1: 初始化 Sol BL ij ←∅ ;
v
2: 对 demand (v∈{1,2,…,n}),按从大到小降序排列,记为 A ij demand : demand ij max 1 ,demand ij max 2 ,...,demand ij max n ,将
ij
当前已开启的物理链路,按可用容量从小到大升序排列,记为 A ij active :l ij active 1 ,l ij active 2 ,...,l ij active n a ,将当前未开启的物理
链路,按容量从小到大升序排列,记为 A ij sleeping :l ij sleeping 1 ,l ij sleeping 2 ,...,l ij sleeping n s ;
3: FOR demand ij max v (v=1;v≤n;v++) DO
4: IF 已开启的物理链路 l ij active n a 尚且不能容纳当前流量需求 demand ij max v THEN
5: 从 A ij sleeping 中顺序查找能容纳 demand ij max v 的第 1 个物理链路,记为 l ij sleeping v s ,将该物理链路从 A ij sleeping
中剔除,将 demand ij max v 分配至该物理链路,并依据其剩余可用容量将其加入到 A ij active 中的相应位置:
← Sol ∪ Sol {l sleeping v s ← demand max v } ;
BL ij BL ij ij ij
6: ELSE
7: 从 A ij active 中顺序查找能容纳 demand ij max v 的第一个物理链路,记为 l ij active v a ,将该流量需求分配至该物
理链路,更新该物理链路的可用容量及其在整个排序中的位置, Sol ← ∪ Sol {l active v a ← demand max v } ;
BL ij BL ij ij ij
8: END IF
9: END FOR
10: RETURN Sol BL ij .

4 仿真实现与机制评估
为了更好地评价本文提出的 SRCF-G 机制(在全局视图下,采用 SRCF 算法,沿着具有最小剩余容量的路径
路由所有流量需求;而在局部视图下的边内部使用 G-BFD 算法进行流量分配),我们采用如下 5 种机制在功耗和
性能方面进行对比.
• SPT 机制:在全局视图下,以功耗作为边权重,采用 SPT(shortest path tree)算法 [33] 路由所有流量需求;而
流量在局部视图下边内部的分配是随机的(只要流量能够被物理链路容纳即可);
• SPT-G 机制:在全局视图下,以功耗作为边权重,采用 SPT 算法路由所有流量需求;而在局部视图下的边
内部使用 G-BFD 算法进行流量分配;
• SOPF 机制:采用 SOPF 算法 [24] 路由所有流量需求,由于此算法是基于捆绑链路模型提出的,故无需进一
步改造,可将其直接进行比较;
• MSPF 机制:采用 MSPF-NF2(multiple paths by shortest path first-node first version 2)算法 [34] 路由所有流
量需求.同样,由于该算法也是基于捆绑链路模型提出的,可以将其直接进行比较;
• SRCF 机制:在全局视图下,采用 SRCF 算法,沿着具有最小剩余容量的路径路由所有流量需求;而流量
在局部视图下边内部的分配是随机的(只要流量能够被物理链路容纳即可).
4.1 仿真环境
以上所有方案均在如下仿真环境下进行仿真实现.
• 硬件配置:CPU:Intel Quad-Core i5-4590@3.30GHz,RAM:4GB (DDR3,1600MHz);
• 操作系统:Windows 7 professional 64bits;
• 开发平台:Microsoft Visual Studio 2010;
• 开发语言:C++.