基于流量的IP OVER WDM 网络多跳疏导节能路由算法设计

邢移单

(同济大学 浙江学院，浙江 嘉兴 314051)



基于流量的IP OVER WDM 网络多跳疏导节能路由算法设计

邢移单

(同济大学 浙江学院，浙江 嘉兴 314051)

摘要：降低网络能耗和提高能量利用率的需求，使绿色IP over WDM网络成为光网络领域的研究热点。针对流量业务，以降低网络能耗和保证网络性能为优化目标，建立了分层集成辅助图模型，根据多跳疏导机制设计了IP over WDM 网络光层节点优化配置下的节能多跳疏导(Optical Multiple Jump Grooming，OMJG)路由算法，进行了仿真，并与最短路径优先算法(Dijkstra)进行了比较。结果表明：在网络总能耗和业务请求阻塞率方面，设计的OMJG算法均优于传统的Dijkstra算法。

关键词：IP over WDM网络；网络能耗；流量疏导；多跳路由；分层集成辅助图

0引言

随着互联网用户的增长和多媒体业务的普及，通信网络规模不断扩大，网络能耗快速增长。IP over WDM网络是通信网络的重要组成部分，具有覆盖范围广、传输距离长、业务接口丰富、传输容量大、组网方式及业务调度能力灵活等优点，已成为下一代网络的支撑技术之一，研究IP over WDM网络的能耗优化问题，可以为通信网络带来更大的节能空间，对构建绿色通信网络体系具有重要意义。

光通信网络单个波长信道的通信速率可达Gb/s级别，而实际应用中大多数业务的通信速率低于一个波长的最高传输速率，如果为单个业务提供一个专用波长或者端到端的独立波长信道，资源利用率低且不经济，因此有必要进行流量疏导。流量疏导能按物理链路、每个网络节点的光收发器数目、每根光纤的波长数目以及波长容量，为多个低速率的业务连接进行路由，优化网络性能。Yetginer等[1]从能耗的角度出发研究流量疏导问题，并建立整数线性规划模型，将最小化光路数量和最小化电层路由次数结合起来，加上一定的约束条件，计算取得最小能耗的解。为了评估核心网的能耗，Heddeghem等[2]以泛欧教育网为例，采取链路-链路疏导和端-端疏导机制，利用时分复用方式在电域进行数据包交换，采用光旁路机制，在光域疏导本地上、下路业务，结果表明端-端疏导机制节能优势更显著。Tucker等[3]深入研究了基于流量的IP over WDM骨干网中的节能，采用混合整数线性规划(MILP)模型，基于光旁路和流量疏导设计了启发式算法，通过MILP模型得到最小网络能耗。宋璨、袁梦、王汝言等[4-6]针对该现状提出一种基于区域扩展的流量疏导算法，通过分层图模型寻找最佳路径，仿真结果表明在网络能耗和阻塞率方面的性能优于传统算法，不足之处没有讨论光收发器、光放大器的功耗。贾晓蕾等[7]研究了无源光网络的流量疏导问题。在目前的研究中，基于流量疏导机制的能耗优化方案大多是基于不同的疏导策略设计相应的启发式算法和数学优化方法，节能效果较优，但仍存在如何确保网络性能的问题。

本文基于流量疏导机制，设计IP over WDM网络的能耗优化路由问题。首先从节点级角度，建立网络分层集成辅助图模型，然后从网络级出发，引入多跳流量疏导机制，设计节能路由算法，并通过仿真，根据多个评价指标，分析和评估模型与算法对网络能耗和性能的影响。

1问题描述和模型定义

1.1问题描述

流量疏导是如何在给定网络物理拓扑、业务需求矩阵、节点资源及带宽资源等限制条件下，为不同带宽粒度的业务建立光路，形成最优的虚拟拓扑进行业务疏导。性能优化目标是：网络的总能耗最小(即在给定网络拓扑和业务需求矩阵的情况下，疏导所有业务消耗的节点设备的能耗之和最小)和平均请求阻塞率最小(被阻塞的业务个数与业务请求总数的比值最小)。流量疏导问题分为三个子问题：① 虚拟拓扑：根据连接请求将源节点所在的路由器通过OXC与目的节点对应的IP路由器互联，在物理拓扑的基础上建立新的逻辑拓扑；② 流量路由：在虚拟拓扑上为低速业务连接请求选路，使得该路由路径的能耗最小；③ 波长分配：当路由路径确定时，为在该路径上的每条链路上分配波长。

1.2分层集成辅助图模型

流量疏导一般用网络物理拓扑和虚拟拓扑的辅助图模型进行分析，本文设计综合网络物理拓扑和虚拟拓扑的分层集成辅助图模型。作为实例，图1为6节点双向单光纤的IP over WDM网络，包含λ1、λ2两个波长信道，信道容量设为单位1，有两个建立连接业务请求，假定已计算得到其最短路径，如表1所示，表中的表达式Es(s,d,t)表示源节点s到目的节点d的归一化流量为t，Ni表示网络节点。

表1　业务请求

根据波长信道个数分为多层，每层代表一个波长平面，实线连接波长通道建立初始辅助图(见图1(a))；虚线链接源节点和目的节点并标注流量请求虚链路用虚线在波长平面中表示出来(见图1(b))，将物理拓扑和虚拟拓扑的信息整合在一起形成分层集成辅助图。

图1　分层集成辅助

2基于流量的多跳疏导路由算法设计

2.1算法描述

辅助图中每条边都具备可用容量和边权代价两个基本属性，传统的最短路径算法Dijkstra中，边权代价定义为相邻两个节点之间的物理距离；基于流量的多跳疏导路由算法为了使疏导每个建立连接请求所需的能耗最小，需要将边权进行相应的转换，对图1中的波长链路、虚链路的边权代价重新定义为

波长链路的代价函数为：

(1)

虚链路的代价函数为：

(2)

式中，tmn表示节点对(m,n)之间的业务负载，T为总负载。

如果一条路由路径包括g条波长链路和h条虚链路，波长链路和虚链路构成的混合路径的代价函数为：

(3)

当路由路径确定以后，可以根据路径形式，选取对应的代价函数来计算每条路径的功耗：

(4)

在完成所有业务请求之后，可以由每条路径的功耗以及使用的线卡总数，计算网络总功耗为：

Ptotal=∑P

(5)

在选路过程中，优先利用已建虚链路而非新建光路来承载当前的业务请求时，能够充分利用光路的带宽资源，并且路由路径的总代价最小，网络的总能耗最少。

2.2算法实现

基于流量的多跳疏导路由算法的描述，提出光层节点优化配置下的多跳疏导(Optical Multiple Jump Grooming Algorithm，OMJG)算法，具体的处理和实现过程为：

步骤1：根据输入的网络拓扑、波长平面数W、波长信道容量B等信息，采用图1的方法建立辅助图，并根据式(1)计算所有波长链路的边权值。

步骤2：对所有的业务连接请求按照业务负载的大小降序排列，如果负载相同，按先进先出(First In First Out，FIFO)原则确定实际的路由处理队列Seq。

步骤3：判断队列Seq是否为空，若不为空，则从队列Seq中取出当前第一个业务请求Es(s，d，tsd)进行路由，排除辅助图中波长可用带宽小于tsd的链路，跳转至步骤4；若为空，则直接跳转至步骤8。

步骤4：在W层辅助图上分别运行Dijkstra算法，找出每个波长平面的最短路径。如果不存在一条这样的路径，则阻塞该业务连接请求，并跳转至步骤3；否则跳转至步骤5。

步骤5：如果存在一条或多条最短路径，它是s至d的一条直达虚链路，那么选取链路权重最小的路径作为最终的路由路径，若路径权重相同，则选取波长平面序号最小的路径，从虚链路中扣除业务负载tsd，并按式(1)更新虚链路的权重，路径功耗P满足式(4)，返回步骤3继续处理下一个业务。

步骤6：如果存在一条或多条最短路径，它全部由波长链路组成，那么选取链路权重最小的路径作为最终的路由路径，如果路径权重相同，选取波长平面序号最小的路径，删除波长链路，建立s至d的一条直达虚链路，从虚链路中扣除业务负载tsd，并按式(1)更新虚链路的权重，路径功耗P满足式(4)，更新Ptotal，返回步骤3继续处理下一个业务。

步骤7：如果存在其他形式的最短路径，则阻塞该业务请求，并跳转至步骤3，继续处理下一个业务。

步骤8：完成所有业务连接请求，式(5)将每条路径的功耗P累加得到网络的总功耗Ptotal。

2.3算法实现举例

改进图1中建立的辅助图为图2，其边长上的数字表示节点的间距，对于采用新能源方式供电的节点做特殊标记，如图2中节点2是特殊节点。然后初始化辅助图，按功耗参数和式(1)修改相应的波长链路的权重，如图3所示。光层节点优化配置下的路由算法采用多跳疏导，由于特殊光节点的存在，导致部分波长链路的权重减小，在路由过程中，会优先选择这些能耗较小的路径。具体的处理过程如下：

图2　优化配置物理拓扑

图3　优化配置辅助

按照文献[8]的参数数据，初始化辅助图，如图1所示，根据式(1)计算每条波长链路的权重。

3仿真及数值分析

3.1仿真参数

(1)仿真数据：连接请求带宽主要有四种：{B1，B2，B3，B4}，将其大小分别记作{1，3，6，10}(Gbps)，业务在网络中的生成概率情况为①以小负载业务居多：B1:B2:B3:B4=3:3:3:1 ；②业务生成概率相同：B1:B2：B3：B4=1:1:1:1 ；③以大负载业务居多：B1:B2:B3:B4=1:2:2:3。

图4　OMJG算法的过程示例

(2)网络拓扑：选取两种类型的网络拓扑①小型网络(见图5)：含6个节点，8条链路；②NSFNET网络(见图6)，包括14个节点，21条链路。图中每条光纤链路都是双向传输，边上的数值代表节点间的物理距离，单位是km，光纤链路中的波长数目为W，波长信道容量为10 Gb/s，每个节点都具备业务疏导能力，但没有波长转换功能。

(3)业务模型：所有业务请求均匀分布在网络中的各个节点。

图5　小型网络

图6　NSFNET网络

3.2不同算法的性能比较

为对比算法性能，分别仿真了本文设计的算法OMJG和最短路径优先算法(Dijkstra)。

(1)网络总能耗：针对图5的小型网络，波长平面数W=8；对于图6的NSFNET网络，波长平面数W=16，当业务总数相同，不同带宽下的业务数量比分别满足仿真数据中的①、②、③时，比较OMJG算法和Dijkstra算法的网络总能耗(见图7、图8)。 由图7、图8看出，不同带宽和业务量下采用光层节点优化配置下的多跳疏导OMJG算法优于Dijkstra算法的能耗，尤其在网络规模和业务负载较大时，Dijkstra算法与OMJG算法的能耗差距增大。

(2)平均业务请求阻塞率：不同带宽下的业务数量比分别满足仿真数据中的①、②、③，当波长平面数变化时，小型网络和NFSNET网络中，OMJG和Dijkstra路由算法的业务请求阻塞率，如图9、图10所示。

① 波长平面个数的影响：由以图9、图10可知，当业务负载不变时，平均请求阻塞率随波长平面的增加而大大降低；与Dijkstra算法相比，OMJG算法的阻塞率较低，特别是在大规模网络NSFNET中，OMJG算法能够疏导的业务请求数明显优于Dijkstra算法。

② 业务负载的影响：当波长平面数相同时，平均请求阻塞率随业务负载的增多而逐渐升高，OMJG算法算法也优于传统的Dijkstra算法。

图7　不同B1:B2:B3:B4下小型网络的总能耗

图8　不同B1:B2:B3:B4下NSFNE网络的总能耗

图9　不同W下小型网络的阻塞率

图10　不同W下NSFNET网络的阻塞率

4结语

针对以能耗优化为目标的流量疏导问题，设计了适合IP over WDM网络的分层集成辅助图，便于同时表示波长链路和虚链路的可用容量及权重信息。在分层集成辅助图的基础上，设计节能的OMJG算法，进行了仿真。仿真结果表明，与传统的Dijkstra算法相比， OMJG算法不仅网络总能耗得到了降低，而且平均业务请求阻塞率也得到了降低，OMJG算法在网络节能和降低业务请求阻塞率方面有着良好性能。

参考文献：

[1]Yetginer E, Rouskas G. Power Efficient Traffic Grooming in Optical WDM Networks[C]. IEEE Global Telecommunications Conference 2009, 2009,1-6.

[2]Heddeghem W, Groote M, Vereecken W. Energy-Efficiency in Telecommunications Networks: Link-by-Link Versus End-to-End Grooming[C]. 2010 14thConference on Optical Network Design and Modelling, 2010, 9-15.

[3]Tucker R S. Green Optical Communications-part II: Energy Limitations in Networks, IEEE Journal of Selected Topics in Quantum Electronics[J]. 2011, Vol. 17(2): 261-274.

[4]宋璨, 侯韶华.WDM网络中基于分层图模型的ICBR路由算法[J].通信技术,2012,45(02):84-89.

SONG Can, HOU Shao-hua. A Layered Graph Model-based ICBR Algorithm in WDM Network[J]. Communications Technology, 2012, 45(02): 84-89.

[5]袁梦，张民，王力. 一种新的动态流量疏导算法[J]. 光通信研究，2012，38(02)：11-13.

YUAN Meng, ZHANG Min, WANG Li. A Novel Topology Integration-based Dynamic Traffic Grooming Algorithm. Study on Optical Communication, 2012,38(02)：11-13.

[6]王汝言，徐印，吴大鹏等. 基于区域扩展的绿色业务量疏导算法[J].重庆邮电大学学报:自然科学版，2012，24(02)：133-137.

WANG Ru-yan，XU Yin，WU Da-peng，et al. Green Traffic Grooming in Zone-based Scalable Optical Networks. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2012，24(02)：133-137.

[7]贾晓蕾, 沈建华.支持流量疏导弹性光网络的共享保护策略[J]. 光通信研究,2015,189(03):24-26.

JIA Xiao-lei, SHEN Jian-hua. Shared Protection Strategyprotecion Grooming-Supporting Elastic Optical Networks.Study on Optical Communication, 2015, 189(3)：24-26.

[8]Idzikowski F. Power Consumption of Network Elements in IP over WDM Networks[EB/OL]. www.tkn.tu-berlin.de/publications/papers/powerNumbers_final.pdf.

邢移单(1988—)，女，硕士，助教，主要研究方向为宽带通信网络与技术。

Energy-Saving Routing Algorithm for Multiple Jump Grooming in

IP over WDM Network based on Traffic

XING Yi-dan

(Zhejiang College,Tongji Univ., Jiaxing Zhejiang 314051, China)

Abstract：The demand for decrease of network energy consumption and improvement of energy efficiency makes the green IP over WDM network a research hotspot in the area of optical communication network. For the purpose to reduce the network energy consumption and ensure the network performance for the traffic load, the hierarchical integrated auxiliary graph model is established, and the saving energy multiple jump grooming (OMJG)routing algorithm for the optical layer node optimization configuration of IP over WDM network designed and simulated, Simulation and comparison with the shortest path first algorithm (Dijkstra) inidcate that the OMJG algorithm is clearly superior to the traditional Dijkstra algorithm in total energy consumption and service request blocking probability of the netwok.

Key words：IP over WDM network, network energy consumption, trafic grooming, multiple jump, hierarchical integrated auxiliary graph

作者简介：

中图分类号：TN915

文献标志码：A

文章编号：1002-0802(2015)12-1389-06

收稿日期：2015-07-16；修回日期：2015-11-09Received date:2015-07-16；Revised date：2015-11-09

doi:10.3969/j.issn.1002-0802.2015.12.014