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

张金宏 等:面向主干网的网络级绿色节能机制 2933

20: ELSE IF 与{Route 1 ,Route 2 ,…,Route i−1 }边重叠最多的路径只有 1 条 THEN
21: 选取该路径,记为 Route i ,ROUTE←ROUTE∪{Route i };
22: ELSE
23: 从与{Route 1 ,Route 2 ,…,Route i−1 }边重叠最多的几条路径中随机选取 1 条,记为:
Route i ,ROUTE←ROUTE∪{Route i };
24: END IF
25: END IF
26: ELSE
27: 记该路径为 Route i ,ROUTE←ROUTE∪{Route i };
28: END IF
29: END IF
30: 在网络图 G −1−2−…−(i−1) 中,Route i 沿途各边中减去相应的容量(即 demand i 大小),记由此更新后的网络
图为 G −1−2−…−i ;
31: END FOR
32: RETURN ROUTE.
3.3 G-BFD算法
在第 3.2 节中,我们使用 SRCF 算法得到所有流量需求的路由路线.由于我们的链路模型考虑的是捆绑链路,
为了保证网络绿色节能,将面临对于流经每条捆绑链路的流量,如何使捆绑链路中开启的物理链路数目最少这
样一个装箱问题,其形式化表述如下:
n
1
设当前网络中有 n 个流量需求 demand demand ij 2 ,...,demand 流经捆绑链路 BL ij (由 n ij 条物理链路组成),它
,
ij
ij
n
1
1
N
,
们的大小分别为 size size ij 2 ,...,size .使用当前可用容量分别为 ac ac 2 ij ,...,ac 的 N 条物理链路来容纳这 n 个流量
,
ij
ij
ij
ij
需求,每条物理链路容纳的流量需求总和不能超过该物理链路的可用容量.目标是寻求满足以上条件,使得所使
用物理链路的数目 N 最小的分配解决方案 Sol BL ij .
我们可以将上述问题规划如下:
ij n
N x x u (6)
ij
min ( ) = ∑ ij
u = 1
n
ij v × ∑ size uv ≤ ij u × y x u ij ,∀ ac u ∈ {1,2,..., }n ij (7)
ij
v = 1
ij n
∑ y uv =∀ ∈v {1,2,..., }n (8)
1,
ij
u = 1
x u ∈ {0,1},∀ u ∈ {1,2,..., }n (9)
ij ij
y ∈ ij uv {0,1}, v∀ ∈ {1,2,..., }n (10)
u
uv
uv
u
u
其中, x 和 y 均是状态标识符: x 取值为 1 或 0,分别表示物理链路 l 上是否承载了流量需求; y 取值为 1 或
ij ij ij ij ij
u
v
0,分别表示流量需求 demand 是否被分配至物理链路 l 承载.
ij ij
由于装箱问题是一个经典的 NP 难问题,该问题不存在在多项式时间内求得精确解的算法.因此,我们设计
了一种启发式算法——绿色降序最佳适应(green-best fit deceasing,简称 G-BFD)算法对其进行求解.
v
对流经每个捆绑链路 BL ij (i,j∈{1,2,…,|V|},i≠j)的 n 个流量需求 demand (v∈{1,2,…,n}),使用 G-BFD 算法获
ij
取流量分配解决方案 Sol BL ij ,其伪代码如算法 2 所示.
算法 2. G-BFD 算法.
ij n
n
1
1
n
1
输入: BL demand demand ij 2 ,...,demand size size ij 2 ,...,size ac ac 2 ij ,...,ac ;
,
,
,
,
,
,
ij
ij
ij
ij
ij
ij
ij