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

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

ITU-T Y.1540 [31] 和 ITU-T Y.1541 [32] ,将网络应用划分为 K 种类型:type 1 ,type 2 ,…,type K .对于每种类型的应用,关注
4 个 QoS 参数:带宽、延迟、延迟抖动和出错率.对于第 k 类应用,需要网络提供的带宽、延迟、延迟抖动和出
错率分别为 bw ≥ bw min ,dl ≤ dl max , jt ≤ jt max 和 er ≤ er max ,其中,1≤k≤K.
classk classk classk classk classk classk classk classk
参考我们之前的研究工作 [21] ,本文将路由途经的每个节点处的 QoS 合并到与其相连的后向链路中,将链路
l 的带宽、延迟、延迟抖动和出错率分别表示为 bw l ,dl l ,jt l 和 er l ,则路径 P 的 QoS 可以通过公式(4)得到:
bw = P min{bw l ∈ l | P },dl = P dl l , jt = ∑ P jt l ,er = ∑ P 1− ∏ (1 er− l ) (4)
∈
∈
∈
lP lP lP
本文提出的路由算法针对每个流量需求计算路径,判断路径 QoS 是否落入对应应用类型所必须满足的
QoS 区间,以此确定求得的路由是否有效.
3.2 SRCF路由算法
本文设计了一种单路径节能路由算法——基于最小剩余容量优先(smallest remaining capacity first,简称
SRCF)的功率感知路由算法,该算法将初始全网络图和流量需求矩阵作为算法的输入,以边的剩余容量配置网
络图的边权重,每次路由新的流量需求时,都选取和先前所使用路由路线的边重叠最多的路径,这样,随着路由
流量需求的不断进行,流量被不断汇聚到一个尽可能小的网络子集,通过关闭剩余的那些未被使用的网元来实
现全网节能,伪代码如算法 1 所示.流量需求矩阵由网络中所有节点对间的流量需求值组成,描述如公式(5)所示,
其中,demand ii =0(i∈{1,2,…,|V|}):
⎡ demand demand 1| | ⎤
11
V
DEMAND = ⎢ ⎢ ⎥ ⎥ (5)
⎢ ⎥
⎣ demand ||1V demand ||||V V ⎦
算法 1. SRCF 算法.
输入:DEMAND,初始网络图 G 0 ;
输出:ROUTE or NULL.
1: 初始化 ROUTE←∅;
2: 对流量需求矩阵中不为零的元素 demand ij (i,j∈{1,2,…,|V|},i≠j),按从大到小进行排序,得到:
demand 1 ,demand 2 ,…,demand |V|(|V|−1) ;
3: FOR i←1:|V|(|V|−1 DO
i −
4: 删除网络图 G −1−2−…−(i−1) 中剩余容量小于 demand i 的边,由此得到子图 G − 1 2 ... ( 1)i−− − − ;
i −
5: 在 G −− − − 上使用 Dijkstra 算法(以边的剩余容量为权重)为 demand i 计算路由路径;
1 2 ... ( 1)i−
6: IF 路径不存在 THEN
7: 对 demand i 的路由失败,RETURN NULL;
8: ELSE
9: 对路径进行 QoS 检验,剔除不合格的路径;
10: END IF
11: IF 满足 QoS 的路径不存在 THEN
12: 对 demand i 的路由失败,RETURN NULL;
13: ELSE IF 存在多条路径 THEN
14: IF i==1 THEN
15: IF 跳数最少的路径只有 1 条 THEN
16: 选取该路径,记为 Route i ,ROUTE←ROUTE∪{Route i };
17: ELSE
18: 从跳数最少的几条路径中随机选取 1 条,记为 Route i ,ROUTE←ROUTE∪{Route i };
19: END IF