一种IP网络中的节能权重设计方法

摘要

本发明公开了一种IP网络中的节能权重设计方法，通过结合链路层和网络层来设计节能链路权重，从而决定网络中业务分布来关闭部分闲置线卡和链路，以达到最小化能耗的目的，优化了节能效果，其次，考虑了IP网络中的实际能耗组成，在不修改网络协议条件下适用于任意规模的IP网络，最大限度实现了节能，同时保证网络的联通性和服务质量。

权利要求

1.一种IP网络中的节能权重设计方法，其特征在于，包括以下步骤：

(1)、输入给定的网络拓扑信息和业务量矩阵，并等量初始化网络的链路权重；所述的拓扑信息包括节点编号、链路编号、线卡编号、链路容量、链路和节点对应关系、链路和线卡对应关系；所述的业务量矩阵包括所有源、目节点对SD间的业务流量；

(2)、判断网络拓扑中所有链路是否能够正常通信，如果有链路未被判断则进入步骤(3)，如果判断完所有链路则进入步骤(7)；

(3)、计算各链路的利用率，选出最优链路Lbest：

根据当前链路权重，通过Dijkstra算法计算出当前网络拓扑T中每对源、目节对SD间的最短路径，每对SD的业务路由采用最短路径路由且流经最短路径的所有链路，由此计算出每条链路上总的业务负载和链路利用率UL，当一对SD间有多条最短路径时，采用ECMP算法进行分流，将业务平均分配在所有最短路径上；

根据当前各链路利用率UL，找出当前最低链路利用率Umin，得到链路利用率范围上限βUmin其中，增益因子 将所有利用率在[Umin,βUmin]]间且未被判定过的链路作为候选链路集S,S＝{L|UL∈[Umin,βUmin]}]}，根据当前网络中链路对应的线卡上开启的端口数，从S中找出对应线卡上开启端口数最少的一条链路作为最优链路Lbest，最后关闭Lbest和其反向链路，得到新网络拓扑T1，然后重新计算新网络拓扑T1中各SD间最短路径和链路利用率，如果对应线卡上开启端口数最少的链路有多条，则选择其中链路利用率最低的一条作为最优链路Lbest；

(4)、如果新网络拓扑T1不联通，即存在一对SD之间无法通信，则重新开启Lbest和其反向链路，并不修改当前网络拓扑T，跳至步骤(2)；如果新网络拓扑T1联通则跳至步骤(5)；

(5)、计算新网络拓扑T1中链路的最大利用率 当 时，则新网络拓扑T1中没有链路超载，将新网络拓扑T1作为当前网络拓扑T，并记录下当前被关闭的Lbest和其反向链路ID，跳至步骤(2)；当 时，则网络拓扑中存在超载，即会发生拥塞需要均衡流量，则继续步骤(6)；

(6)、调用基于邻域搜索算法的流量均衡算法修改开启链路权重，引导SD间的业务走向，为开启的链路重新分配业务负载，进行流量均衡；如果流量均衡成功则将新网络拓扑T1作为当前网络拓扑T，并记录下当前被关闭的Lbest和其反向链路ID，并跳至步骤(2)；如果流量均衡失败则重新开启当前Lbest和其反向链路，并不修改当前网络拓扑T，跳至步骤(2)；

(7)、关闭闲置线卡；将已关闭链路对应的线卡上端口关闭，统计此时线卡上开启端口的数目，如果线卡上开启端口数目为0，则线卡被闲置并关闭，并记录此线卡ID；如果线卡上开启端口数目不为0，则继续保持该线卡开启；

(8)、输出最终各链路权重、被关闭线卡与链路ID。

2.根据权利要求1所述的IP网络中的节能权重设计方法，其特征在于，所述的链路之间关系以及链路和线卡对应关系为：一个路由节点上有多块线卡，一块线卡上有多个端口，每个端口对应一条链路，每条链路两端对应有线卡和路由节点。

3.根据权利要求1所述的IP网络中的节能权重设计方法，其特征在于，所述的步骤(2)中对网络拓扑的每条链路仅判断一次。

说明书

一种IP网络中的节能权重设计方法

技术领域

[0001] 本发明属于网络通信技术领域，更为具体地讲，涉及一种IP网络中的节能权重的设计方法。

背景技术

[0002] 在IP网络中，由于潜在的经济利益和预期的环境的影响，减少不必要的能源消耗成为了一个网络研究中的关注重点，这些能耗问题通常被称为“绿色网络”问题。近几年涌现出许多绿色网络技术，它们从各种层面上为网络节省能耗，其中，在链路层上，由于链路能耗几乎与其负载无关，因此可以通过关闭链路节能；在网络层上，能耗感知路由就是在为网络制定路由策略时考虑能量消耗，主要研究在互联网自治系统内部如何使用最少的网络资源提供路由转发服务，以实现全网能耗最小化目标，一般遵循资源整合的原则，即将流量聚合到一部分的设备中，关闭或休眠空闲的设备从而节省能量，并且在进行流量整合时考虑到网络的可用性和服务质量，如限制链路的最大利用率等。

[0003] 在现有技术中，Chabarek等建立了节能问题的MINP模型，通过结合考虑链路权重和链路利用率来整合网络中业务分布，从而关闭闲置链路达到最小化网络能耗，MINP模型优化目标是最小化链路的能耗，约束条件是每条链路上流量负载不超过链路容量，其中链路权重决定业务分布。但MINP模型只能求解小规模网络，并且优化目标只包括链路能耗，而实际链路能耗只占网络能耗极小部分。

[0004] Mingui Zhang等结合了链路层和网络层建立节能模型MIP，MIP模型比MINP模型更具有实际意义，它考虑到网络中能耗的组成主要包括路由器和链路能耗，路由能耗最多，但是关闭路由涉及到协议修改比较复杂，路由大部分能耗来自线卡，因此决定通过重新分布网络中业务来关闭部分闲置线卡和链路来节省能耗。MIP模型优化目标是最小化链路和线卡的能耗，约束条件是每条链路上流量负载不超过链路容量，其中业务分布是基于多商品流模型。然而MIP模型路由基于多商品流模型，需要集中控制器指定业务路由而不是路由器按照链路权重决定路由，这需要改变网络环境因此不适合传统IP网络，同时MIP模型也只能求解小规模网络。

[0005] Po-Kai Tseng等提出了一种基于遗传算法的启发式算法CA，它将MINP模型分解成两个子问题：子问题1是通过遗传算法找出一些解，每个解对应一套链路开关状态，每个解对应的新网络都至少是联通的；子问题2是已知新网络中链路开启情况，通过采用模拟退火算法迭代调整权重，通过业务重分布使得最终网络中没有链路超载，最后不断迭代寻找最优解，即找到一套链路开关状态使网络中开启链路数最少并且没有链路超载。但CA算法也只考虑了链路能耗，而实际链路能耗只占网络能耗极小部分，其次，CA算法在设计上的目标是关闭更多有向边，而实际中需要关闭物理链路才能实现节能，因此需要加入物理链路的约束才更有实际意义。

发明内容

[0006] 本发明的目的在于克服现有技术的不足，提供一种IP网络中的节能权重设计方法，通过结合链路层和网络层来设计链路权重，从而决定网络中业务分布来关闭部分闲置线卡和链路，最大限度实现了节能，同时保证网络的联通性和服务质量。

[0007] 为实现上述发明目的，本发明一种IP网络中的节能权重设计方法，其特征在于，包括以下步骤：

[0008] （1）、输入给定的网络拓扑信息和业务量矩阵，并等量初始化网络的链路权重；所述的拓扑信息包括节点编号、链路编号、线卡编号、链路容量、链路和节点对应关系、链路和线卡对应关系；所述的业务量矩阵包括所有源、目节点对SD间的业务流量；

[0009] （2）、判断是否完成对所有链路的判定，如果有链路未被判定则进入步骤（3），如果判定完所有链路则进入步骤（7）；

[0010] （3）、计算各链路的利用率，选出最优链路Lbest：

[0011] 根据当前链路权重，通过Dijkstra算法计算出当前网络拓扑T中每对源、目节对SD间的最短路径，每对SD的业务路由采用最短路径路由且流经最短路径的所有链路，由此计算出每条链路上总的业务负载和链路利用率UL，当一对SD间有多条最短路径时，采用ECMP（Equal Cost Multipath Routing）算法进行分流，将业务平均分配在所有最短路径上；

[0012] 根据当前各链路利用率UL，找出当前最低链路利用率Umin，得到链路利用率范围上限βUmin其中，增益因子 将所有利用率在[Umin,βUmin]]间且未被判定过的链路作为候选链路集S,S＝{L|UL∈[Umin,βUmin]}]}，根据当前网络中链路对应的线卡上开启的端口数，从S中找出对应线卡上开启端口数最少的一条链路作为最优链路Lbest，最后关闭Lbest和其反向链路，得到新网络拓扑T1，然后重新计算新网络拓扑T1中各SD间最短路径和链路利用率，如果对应线卡上开启端口数最少的链路有多条，则选择其中链路利用率最低的一条作为最优链路Lbest；

[0013] （4）、如果新网络拓扑T1不联通，即存在一对SD之间无法通信，则重新开启Lbest和其反向链路，并不修改当前网络拓扑T，跳至步骤（2）；如果新网络拓扑T1联通则跳至步骤（5）；

[0014] （5）、计算新网络拓扑T1中链路的最大利用率 当 时，则新网络拓扑T1中没有链路超载，将新网络拓扑T1作为当前网络拓扑T，并记录下当前被关闭的Lbest和其反向链路ID，跳至步骤（2）；当 时，则网络拓扑中存在超载，即会发生拥塞需要均衡流量，则继续步骤（6）；

[0015] （6）、调用基于邻域搜索算法的流量均衡算法修改开启链路权重，引导SD间的业务走向，为开启的链路重新分配业务负载，进行流量均衡；如果流量均衡成功则将新网络拓扑T1作为当前网络拓扑T，并记录下当前被关闭的Lbest和其反向链路ID，并跳至步骤（2）；如果流量均衡失败则重新开启当前Lbest和其反向链路，并不修改当前网络拓扑T，跳至步骤（2）；

[0016] （7）、关闭闲置线卡；将已关闭链路对应的线卡上端口关闭，统计此时线卡上开启端口的数目，如果线卡上开启端口数目为0，则线卡被闲置并关闭，并记录此线卡ID；如果线卡上开启端口数目不为0，则继续保持该线卡开启；

[0017] （8）、输出最终各链路权重、被关闭线卡与链路ID。

[0018] 其中，所述的链路之间关系以及链路和线卡对应关系为：一个路由节点上有多块线卡，一块线卡上有多个端口，每个端口对应一条链路，每条链路两端对应有线卡和路由节点；所述的步骤（2）中对网络拓扑的每条链路仅判断一次。

[0019] 本发明的发明目的是这样实现的：

[0020] 本发明IP网络中的节能权重设计方法，通过结合链路层和网络层来设节能计链路权重，从而决定网络中业务分布来关闭部分闲置线卡和链路，以达到最小化能耗的目的，优化了节能效果，其次，考虑了IP网络中的实际能耗组成，在不修改网络协议条件下适用于任意规模的IP网络，最大限度实现了节能，同时保证网络的联通性和服务质量。

[0021] 同时，本发明IP网络中的节能权重设计方法还具有以下有益效果：

[0022] （1）、大量节能。本发明结合考虑了链路层和网络层，通过网络中业务分布来关闭闲置线卡和链路来实现节能。一般算法不考虑设备间的能耗差异仅根据链路的利用率来决定设备关闭顺序，然而本发明首先确定设备关闭优先级保证优先关闭耗能多的线卡，其次才是链路，以达到最小化能耗的目的，优化了节能效果；

[0023] （2）高实用性。一般算法在设计链路层节能时，节能目标是关闭尽可能多的有向边，然而关闭物理链路才能实现节能，因此实际节能效果较差。本发明加入了物理链路的约束，在权重调整时会对物理链路对应的两条有向边进行相同操作，保证它们的状态和权重相同，最终实现物理链路的节能。

[0024] （3）高适用性。本发明可以对任意规模拓扑进行节能，不需要修改网络中协议，适合传统IP网络。

附图说明

[0025] 图1是本发明IP网络中的节能权重设计方法的流程图；

[0026] 表1是网络拓扑信息表；

[0027] 表2是业务量矩阵表；

[0028] 表3是网络拓扑中各有向边的当前利用率表；

[0029] 表4是各线卡上当前开启端口数表；

[0030] 表5本发明最终输出的链路权重表。

具体实施方式

[0031] 下面结合附图对本发明的具体实施方式进行描述，以便本领域的技术人员更好地理解本发明。需要特别提醒注意的是，在以下的描述中，当已知功能和设计的详细描述也许会淡化本发明的主要内容时，这些描述在这里将被忽略。

[0032] 实施例

[0033] 图1是本发明IP网络中的节能权重设计方法的流程图。

[0034] 在本实施例中，如图1所示，一种IP网络中的节能权重设计方法，包括以下步骤：

[0035] S101、输入给定的网络拓扑信息和业务量矩阵，并等量初始化网络的链路权重；所述的拓扑信息包括节点编号、链路编号、线卡编号、链路容量、链路和节点对应关系、链路和线卡对应关系；所述的业务量矩阵包括所有源、目节点对SD间的业务流量；本实施例中，给定5个节点、10条物理链路和16块线卡，其对应关系如表1所示；并将链路权重初始化为30，则由重力模型生成的业务矩阵如表2所示；

[0036]物理链路ID 源节点 目的节点 链路容量 源线卡 目的线卡
0 0 1 10000 0 4
1 0 2 10000 1 6
2 0 4 10000 2 13
3 4 0 10000 13 2
4 1 2 10000 3 5
5 2 1 10000 5 3
6 2 3 10000 8 9
7 2 4 10000 7 12
8 3 4 10000 10 11
9 4 1 10000 14 15

[0037] 表1

[0038] 编号为N的物理链路对应编号为2N和2N+1的有向链路，则本实施例中，编号为0的物理链路对应编号为0和1的有向链路，编号为1的物理链路对应编号为2和3的有向链路，以此类推；

[0039]业务ID 源节点 目的节点 业务大小
0 0 0 0
1 0 1 3000
2 0 2 3750
3 0 3 1500
4 0 4 3750
5 1 0 3000
6 1 1 0
7 1 2 3750
8 1 3 1500
9 1 4 3750
10 2 0 4000
11 2 1 4000
12 2 2 0
13 2 3 2000
14 2 4 5000
15 3 0 1333
16 3 1 1333
17 3 2 1667
18 3 3 0
19 3 4 1667
20 4 0 4000
21 4 1 4000
22 4 2 5000
23 4 3 2000
24 4 4 0

[0040] 表2

[0041] S102、判断是否完成对所有链路的判定，每条链路仅判定一次，如果有链路未被判定则进入步骤S103，如果判定完所有链路则进入步骤S107；

[0042] S103、计算各链路的利用率，选出最优链路Lbest：

[0043] 根据当前链路权重，通过Dijkstra算法计算出当前网络拓扑T中每对源、目节对SD间的最短路径，每对SD的业务路由采用最短路径路由且流经最短路径的所有链路，由此计算出每条链路上总的业务负载和链路利用率，当一对SD间有多条最短路径时，采用ECMP（Equal Cost Multipath Routing）算法进行分流，将业务平均分配在所有最短路径上；

[0044] 根据当前各链路利用率UL，找出当前最低链路利用率Umin，得到链路利用率范围上限βUmin其中，增益因子 将所有利用率在[Umin,βUmin]]间且未被关闭过的链路作为候选链路集S,S＝{L|UL∈[Umin,βUmin]}]}，根据当前网络中链路对应的线卡上开启的端口数，从S中找出对应线卡上开启端口数最少的一条链路作为最优链路Lbest，最后关闭Lbest和其反向链路，得到新网络拓扑T1，然后重新计算新网络拓扑T1中各SD间最短路径和链路利用率，如果对应线卡上开启端口数最少的链路有多条，则选择其中链路利用率最低的一条作为最优链路Lbest；

[0045] 从步骤S103开始进行第一轮链路判定，在本实施例中，当前最低链路利用率Umin=0.23，上限βUmin=0.69，候选链路集S={0,1,..,19}，各有向边的利用率如表3所示；根据表1输入的线卡和链路的对应关系，得到对应线卡上开启端口数如表4所示；

[0046]有向边ID 边利用率
0 0.30
1 0.30
2 0.43
3 0.47
4 0.24
5 0.23
6 0.23
7 0.24
8 0.24
9 0.23
10 0.23
11 0.24
12 0.35
13 0.30
14 0.50
15 0.50
16 0.30
17 0.35
18 0.47
19 0.43

[0047] 表3

[0048]线卡ID 开启端口数
0 1
1 1
2 2
3 2
4 1
5 2
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 2
14 1
15 1

[0049] 表4

[0050] 在本实施例中，在S中寻找对应开启端口数最少的线卡的链路，发现编号为0的链路对应线卡上开启端口为1，且链路利用率为0.3是所有对应开启端口数最少的线卡的链路中利用率最小的一条，因此Lbest=0，其反向边编号为1，关闭有向边0和1，然后重新计算拓扑中各SD间最短路和链路利用率。

[0051] S104、如果新网络拓扑T1不联通，即存在一对SD之间无法通信，则重新开启Lbest和其反向链路，并不修改当前网络拓扑T，跳至步骤S102；如果新网络拓扑T1联通则跳至步骤S105；

[0052] S105、计算新网络拓扑T1中链路的最大利用率 当 时，则新网络拓扑T1中没有链路超载，将新网络拓扑T1作为当前网络拓扑T，并记录下当前被关闭的Lbest和其反向链路ID，跳至步骤S102；当 时，则网络拓扑中存在超载，即会发生拥塞需要均衡流量，则继续步骤S106；本实施例中，链路的最大利用率 确定关闭有向边0和1，再跳至步骤S102；

[0053] S106、调用流量均衡算法修改开启链路权重，引导SD间的业务走向，为开启的链路重新分配业务负载，进行流量均衡；如果流量均衡成功则将新网络拓扑T1作为当前网络拓扑T，并记录下当前被关闭的Lbest和其反向链路ID，并跳至步骤S102；如果流量均衡失败则重新开启当前Lbest和其反向链路，并不修改当前网络拓扑T，跳至步骤S102；

[0054] 至此，第1轮判定链路完毕，关闭有向边ID为0和1，物理链路ID为0，一共进行了10轮链路判定，之后每轮如此操作不再详述，其中第1,2,6,8轮进行到步骤S105关边成功；第3,5,6,7,10轮进行到步骤S106调用流量均衡算法后网络最大链路利用率分别为1.1,
1.225,1.025,1.233,1.233，网络中存在链路超载，因此流量均衡失败，关边失败；第4轮进行到步骤S104网络不联通关边失败；

[0055] S107、关闭闲置线卡；将已关闭链路对应的线卡上端口关闭，统计此时线卡上开启端口的数目，如果线卡上开启端口数目为0，则线卡被闲置并关闭，并记录此线卡ID；如果线卡上开启端口数目不为0，则继续保持该线卡开启；

[0056] S108KL、输出最终各链路权重、被关闭线卡与链路ID。本实施例中，最终输出各链路的权重如表5所示；

[0057]物理链路ID 链路权重
0 INF
1 30
2 INF
3 30
4 INF
5 30
6 INF
7 30
8 30
9 30

[0058] 表5

[0059] 本实施例中，结合表1和表5可知，被关闭的线卡ID：0,4,8,9，被关闭的物理链路ID:0,2,4,6。

[0060] 尽管上面对本发明说明性的具体实施方式进行了描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易见的，一切利用本发明构思的发明创造均在保护之列。