基于K算法的绿色IP over WDM网络设计方法

田立伟,孙 宇,张 旭

(1.广东科技学院 计算机系，广东 东莞，23083；2.广东省电信规划设计院有限公司，广东 东莞523120)

基于K算法的绿色IP over WDM网络设计方法

田立伟1,孙 宇2,张 旭1

(1.广东科技学院 计算机系，广东 东莞，23083；2.广东省电信规划设计院有限公司，广东 东莞523120)

通过构建整数线性规划（I LP）来计算网络的能耗，求解I LP的解需要的计算机内存空间大，但内存不足仍然是需要考虑的问题之一。针对这一问题，提出了一种基于K算法来设计绿色I P over W D M网络的方法，该方法是基于传统的虚拓扑网络业务疏导方法，首先利用K算法求解网络中节点与节点之间的K条可能路径，然后通过构建整数线性规划（I LP）来求解网络资源的分布。分析网络能耗的模型，利用数学表达式来描述基于K算法下3种I P over W D M网络的能耗。

I P over W D M网络；I LP；K算法；网络能耗

0 引言

目前对于光交换网络的研究，很大一部分是对疏导问题的研究，这些研究主要集中在如何最小化网络的代价，或者为了满足业务负载的需要如何使网络的收益最大。文献[1～7]中提出了一些解决方法，但这些方法均是将IP层和WDM层结合起来考虑，通过求解ILP来计算网络的能耗，由于受计算内存大小的限制，这些方法不适应大规模网络的计算。针对于内存的限制，本文将IP层和WDM层分开讨论，从能耗方面着手，提出一种利用K算法来设计绿色IP over WDM网络的方法。此方法首先利用K算法求解网络中节点与节点之间的K条可能路径，然后再来优化网络能耗。考虑到光层的能耗比较小，忽略其能耗，假设网络中的能耗等于所有路径中器件的能耗之和，即网络中的能耗就可以用光路总数与电交换总数的函数来表示。因此，新方法的优化问题就可以用整数线性规划来表示，它充分结合了文献[3]和文献[4]的业务疏导方法。

1 IP over WDM网络中的能耗模型

图1是IP over WDM网络的结构图，从中可以看出，每个网络节点都包含IP核心路由器和光交叉连接器两部分。将低速路由器汇聚来的IP数据接入IP核心路由器，然后通过光旁路的方式来负载路由数据。光层提供IP层路由的通信容量，节点之间通过物理光纤相连，信号在光纤中向着相反方向传输，每根光纤中包含W条波长。与每根光纤相连的是复用器和解复用器，它们利用WDM技术将多个承载载波信号的光波复用到同一个光纤中去传输。在源端，利用多路波分复用器将信号汇聚起来；在目的端，利用解复用器将信号分解给不同的终端。为了增加接收端的灵敏度，需要在发送端增加一个前置放大器来放大信号的功率，为了简化模型，该部分在图1中省略。核心路由器与光交叉连接器之间的转换器可以实现不同的波长数据之间的转换。为了拓展光信号的传播距离，在每根光纤链路中部署EDFA放大器。

图1 IP over WDM的结构图

网络中业务的传输方法主要有两种，即多跳路由和单跳路由。在单跳路由中，所有光路携带的业务必须通过IP路由器转发；在多跳路由中，全部的负载信息不需要经过IP路由器的传输，而直接在光区域中传输，这样做的目的就是为了节省更多的能量，但是它要求光节点对光路的旁路比较敏感。光的旁路在核心路由器之间直接建立光路，而这个光路映射到IP层，我们就把它称为一个虚链路。显然多跳路由能够充分利用网络资源，因此新方案主要考虑多跳路由情况。

在IP over WDM光网络中，网络中的能量主要在IP层和光层中消耗。路由器进行电信号的交换及转换器对信号进行转换都会导致能量消耗，这就是IP层能量消耗的主要原因，它们分别用PI、PT来表示。据文献[8]可知，核心由器的数目等于所有光路承载的业务量与源节点到目的节点之间的总业务量之差，转换器数量与光路数量呈线性关系，在以上两种层次的能量消耗中IP层的能量消耗起主导作用，因此要最小化网络能耗就应首先考虑最小化路由器和转换器的能耗。光交叉连接器中进行信号交换也会导致能量损耗，这就是光层能量消耗的主因。从文献[9]中可知，光层的能量消耗远小于IP层所能量消耗，故在实验设计时将IP over WDM网络拓扑简化，即光层的能量消耗不作考虑，主要考虑IP的能量消耗。同时，作如下假设：①连接到接入网中本地路由器端口的能耗将不考虑，因为在这些端口中添加和删除的业务量与任何业务疏导方法无关；②由于EDFA总是被部署在网络中，在网络中它的能耗是一个常数；③在给定的负载下，在源节点和目的节点进行疏导所消耗的能量是一个常数，它与采用的疏导方法没有任何关系。

基于以上几点可知，求解最消耗网络能耗问题的目标归结为构建IP层的可能虚拓扑以及在虚拓扑上合理地路由业务请求。

2 K算法求解原理

CPLEX虽然提供了灵活方便的优化程序，例如采用分支切割算法来求解线性规划问题，但它仍需要大量的内容空间。所以，求解规模大的LP，首先要解决内存不足的问题。针对内存不足现象，CPLEX通过对可行解进行松弛来调解，但是这样调解后将影响到计算的性能。因此，我们提出了一种基于K条路径来设计骨干网络，使网络能耗达到最低的方法。此方法先根据网络中节点与节点的距离，利用K算法求解网络中节点与节点之间的K条可能最短距离路径[10]，最后再来优化网络能耗。

首先，通过初始化函数来初始网络中的节点数、边数及其每条边上的权值（距离）等数据，然后利用Dijkstra算法求解出所有点之间的距离，其中网络中所有节点之间的最小的那条作为第一条最短路径。将其路径信息保存在数组P(N1,L1)中，参考前面求出的最短路径信息继续求下一条最短路径，不断求出节点到所有节点的K-1条最短路径，利用递归算法即可求出第K条路径。求解第K条路径的过程如下：遍历前K-1条路径中的所有点，每个被遍历的点都需要断开一次；重新计算路径，如果求得的新路径已经存在，则将断点复原；如果求得路径与前面K-1条路径中的任何路径的前i个点重合，则将其边值设为无穷大，继续求新的路径；如果总是重合，不再断开节点，恢复边的情况，同时需要检测路径上是否有环路；如果没有环路，表明找到一条新的路径，保存在P(N1,L1)中；如果不存在新的路径，循环截止。

通过上述算法，即可求出网络中节点与节点之间可能存在的K条路径，并可通过ILP表达式来表示其路径信息。

3 基于K算法的ILP表达式

假设在IP over WDM网络中，WDM层的结构可以用图G=(N,L)来表示，PI为每发送Gb/s的数据在IP层路由器中产生能耗，Pt为每个光交叉连接器产生的能耗，N为网络拓扑中节点的集合，L为物理层中点与点之间的链路集合，假设物理链路通过光纤相连，光纤中的信息向着相反方向传输，每一根光纤都由W条波长信道组成。每条信道的容量用C来表示，m和n表示光纤链路的端点。i和j表示光路的两个端点。s和d表示在IP层中的低速负载量。相同的约束调节下，有3种表达式可以解决业务疏导问题。

①最小化核心路由器端口(minL)的方法：即通过减少核心路由器端口的数量来降低网络的能耗。由于每个光路都终止于核心路由器端口，路由器的个数是网络中建立光路的两倍，因此最小化网络端口数可以通过光路数来获取，相应的表达式如式(1)所示：

其中Vij表示在IP层建立的从i节点到j节点的光路数目。

②最小化电交换数（minT）的方法：文献[4]考虑通过电交换数作为目标函数，在网络中任何光路所承载的业务量要么终止于目的节点，要么终止于中间节点，由中间节点复用到一个新的光路中去。因此，计算网络中电交换的总数等于所有光路承载的业务量数减去源目节点之间的总业务量数。目标表达式如式(2)所示：

其中：λsd为从源端节点s到目的端节点d之间的业务总量；为节点s到节点d的业务量中经过链路(i,j)的业务量。

③最小化网络能耗(minP)的方法：综合上述2种方法，最小化网络能耗的模型表达式如式(3)所示，其能耗包括电交换的能耗与光交换的能耗。

4 COST239网络的仿真结果

假设IP层路由器Gb/s的能量消耗为14.5W，每个波长转换器的能量消耗为34.5W，使用的仿真工具是ILP优化器 “ILOG CPLEX”，采用的计算机为2× 2.00GHz的处理器，计算机存储数据的容量为16G，具体的仿真结果在以下详细描述。

图2为COST239网络(超大容量光传输网络)的拓扑图，在该网络中，节点与节点之间的链路通过光纤相连，光纤中的信息可向着相反方向传输。每个光纤链路中有W个 40Gb/s的波长。为了使仿真结果明显，将W设置为8。

图2 COST239网络的拓扑图

在表1中，采用类似于文献[7]的业务矩阵，在IP核心骨干网中，基本的业务带宽假设为1Gb/s，总的业务数量为T（即1Tb/s）。其它业务数目分别为1T、2T、3T、4T、5T、6T、7T。具体的仿真结果在以下详细描述。

表1 COST239业务矩阵

考虑到用CPLEX求解ILP问题会受到计算机内存容量的限制，首先根据图2求解K调路径的算法，离线求出节点与节点之间的12条可能路径。保存到文件中，然后在已知12条路径的基础上，通过目标函数(1～3)所示可以求出minL、minP和minT下网络的资源使用情况。

图3 不同业务疏导量下的网络能量消耗

图3为不同业务量下网络消耗的变化，由此可以看出minL和minP网络随着网络中业务量的不断增加，网络的能耗也不断增加。而对于minT网络，当业务请求量从1T变化到2T时网络的能耗增加比较少，但是业务请求量从2T到3T时迅速增加到最大值。这是因为随着业务量的增加，网络的资源变得不太充足，网络将不惜牺牲一切代价来使电交换数达到最小值，此时没有考虑到其它光路数对网络能耗的影响，导致网络能耗瞬间增大。之后，随着网络负载的不断增加，网络的能耗维持一个平衡状态，当业务量等于5T时网络的能耗急剧减少。能耗之所以会急剧减少，是因为此时网络的资源变得越来越紧张，为了满足网络中业务的需要，此时必须考虑通过电交换来给业务选择合适的路径。由于电交换数目的增加，使得网络中能量消耗减少。与minT、minL相比可知，在相同网络负载下，minP的网络能耗最小,这是因为minP网络能够充分考虑到网络中电交换与光路数对网络能耗的影响，是将上述2种方法综合运用，从而使网络能量消耗达到最低。

图4所示为不同业务请求下网络中所建立的光路数，从图中可知，minT网络的光路数的变化与图3中minT网络的能耗变化趋势相同，由此可以很明确地解释minT网络的能耗变化情况：当业务量从1T变化到2T时，三者网络所建立的光路数相差比较少，而minT建立最多。通过对比发现，随着业务量的逐渐增加，minT对应的光路数比minL和minP有较大的增加，直到业务量在6T时，三者才基本平衡。正如我们所料，minL网络在业务量增加的过程中，使用的光路始终最小，而minP网络的光路数始终处于两者之间。从总的趋势来看，随着业务量的增加，建立的光路数也增加，其原因是为了路由更多的业务请求，必须要建立更多的光路来满足业务需求。

图4 不同业务量下所建立的光路数

图5 不同业务量下进行电交换的数目数

图5所示为不同业务请求数下电交换数的变化，当业务请求从1T变化到5T时，由于网络在建立源端与目的端的链路首先选择建立直接的光路数，导致电路数为0；当业务请求从5T变化到7T时，电交换数在快速增加。由此可以很好地解释，在图3和图4中为什么当T从5T变化到6T时网络所建立的光路数和能耗急剧减少，这是因为此时网络中的负载不能够通过建立直接光路来路由业务请求，为满足负载需求，必须通过间接光路来路由，从而使网络中的能耗急剧减少。当业务量等于5T时，minP网络由于电交换数的增加，所建立光路的数目减少，网络的能耗也相应地减少。而在业务请求的不断增加过程中，minT网络的电交换数始终最少，minL网络的电交换数始终最多。

综合图3～图5可知，minP网络可以充分均衡网络中电交换与转换器的能量，由此来选择是否建立更多的直接链路，从而使网络的能耗始终达到最低。minP网络为了使电交换数达到最小值，建立更多的光路数，从而使网络的能耗变化比较剧烈；minL网络所建立的光路是三种网络中最少的，但是由于电交换的数目的不断增加，使网络消耗的能量不断的增加。

5 结束语

IP over WDM网络的能耗问题可以归结为求解ILP，然而它却受到存储容量的限制，为了减少ILP问题的复杂度，本文提出了一种基于K算法的绿色IP over WDM网络的设计方法。本算法将物理层光路的路由与IP层的业务路由分开来求，首先求出物理层中可能的K条光路路径，然后在IP层中通过建立ILP表达式来路由业务请求，最后通过是否使用K条路径来将二者相关联。考虑到能耗网络是一种有效的节省网络能耗的方法，我们对比了在K算法下，不同网络的能耗变化。仿真结果显示，基于K算法的绿色IP over WDM网络能够选择路由业务请求的合理路径，从而使网络的能耗达到最低。

[1]ZHU K,MUKHERJEE B.Traffic grooming in an optical WDM mesh network[J].Selected Areas in Communications,IEEE Journal on,2002,20 (1):122-133.

[2]CHEN B,BOSE S K,ZHONG W D,et al.A new lightpath establishing method for dynamic traffic grooming under the overlay model[J].Photonic Network Communications,2009,17(1):11-20.

[3]陈彬,鲍东晖,苏恭超,等.基于路径的整数线性规划方法在阻塞IP over WDM网络中能耗优化的应用 [J].电子与信息学报,2015,37(3): 715-720.

[4]DUTTA R,ROUSKAS G N.On optimal traffic grooming in WDM rings[J].Selected Areas in Communications IEEE Journal on,2001,20(1): 110-121.

[5]王汝言,马礼冬,张超,等.IP over WDM网络中能耗自感知的混合疏导专有保护算法[J].光电子·激光，2014,25(9):1701-1708.

[6]SHEN G,TUCKER R S.Energy-minimized design for IP over WDM networks[J].Optical Communications and Networking,IEEE/OSA Journal of,2009,1(1):176-186.

[7]MUSUMECI F,TORNATORE M,PATTAVINA A.A power consumption analysis for IP-over-WDM core network architectures[J].Journal of Optical Communications and Networking,2012,4(2):108-117.

[8]XIN C.Blocking Analysis of Dynamic Traffic Grooming in Mesh WDM Optical Networks[J].IEEE/ACM Transactions on Networking,2007,15(3): 721-733.

[9]CHEN B,JIANG Z,TENG R K F,et al.An Energy Efficiency Optimization Method in Bandwidth Constrained IP over WDM Networks[C]. International Conference on Information,Tainan China:2013:1-4.

[10]白轶多,胡鹏,夏兰芳,等.关于k次短路径问题的分析与求解[J].武汉大学学报（信息科学版）,2009(4):492-494.

Design method of green IP over WDM network based onKalgorithm

TIAN Li-wei1,SUN Yu2,ZHANG Xu1
（1.Department of Computer,Guangdong University of Science and Technology, Dongguan Guangdong 523083,China;2.Guangdong Planning and Designing Institute of Telecommunications Co Ltd,Dongguan Guangdong 523120,China)

By constructing integer linear programming(ILP),the energy consumption of the network is calculated,and the memory space of the ILP is required.However,insufficient memory is still one of practical issues.With the consideration of such problem,this paper presented a method to design green IP over WDM networks withKalgorithm,which is based on the traditional method of virtual topology network traffic grooming.Firstly,figured out the possibleKpaths between node and node in network withKalgorithm,and then to solve the distribution of network resources by building an integer linear programming(ILP).The paper mainly analyzed the model of energy consumption：utilizing mathematical expressions to describe three models of IP over WDM network energy consumption based onKalgorithm.

IP over WDM network,ILP,Kalgorithm,network energy consumption

TP393.2

A

1002-5561（2016）02-0012-04

10.13921/j.cnki.issn1002-5561.2016.02.004

2015-11-17。

广东省教育厅重大科研平台项目（2014KTSCX210）资助。

田立伟(1981-)，男，硕士，高级工程师，主要从事通信网络、无线传感网络方面的研究。