多约束多播业务量疏导机制*

李　泰，王兴伟，李福亮，黄　敏

东北大学 信息科学与工程学院，沈阳 110819

多约束多播业务量疏导机制*

李泰+，王兴伟，李福亮，黄敏

东北大学 信息科学与工程学院，沈阳 110819

为了使WDM（wavelength division multiplexing）光网络中的波长资源利用率达到最大化，提出了一种多约束多播业务量疏导机制。该机制在考虑光收发器数约束、波长转换能力约束以及分光量约束等多约束的前提下，结合多约束光树建立算法，可以有效地完成WDM光网络中多播业务量疏导的任务。对美国国家自然科学基金网NSFnet和欧洲教育科研网GEANT的拓扑进行了仿真实现。性能分析表明，该疏导机制不仅能够有效完成多播业务量疏导工作，而且与多跳疏导机制相比，具有较低的阻塞率。

光网络；多播路由；多约束；光树；业务量疏导

1　引言

随着互联网技术的飞速进步，互联网业务与人们的生活结合得越来越紧密，如何提升网络性能已经成为目前人们最关心的问题[1]。WDM（wavelength division multiplexing）光网络可以提供巨大的网络带宽，单波长容量可以达到几十甚至几百G，单根光纤可以容纳上千个波长。为增加网络的吞吐量，业务量疏导技术已经成为WDM光网络必备的基本功能[2]。另外，随着视频会议、网络电视以及网络游戏等多播应用规模的不断扩大，多播业务量疏导问题已然成为当前的研究热点之一[3]。

在WDM光网络中，业务量疏导可以分为动态[4-6]和静态[7-8]两类。前者表示业务连接请求在疏导前没有预先给定的情形，而后者表示业务连接请求在疏导前已经预先给定的情形。文献[9]提出了一种基于光树的静态多播业务量疏导算法，实现了网络开销的优化，提高了波长资源的利用率；文献[10]提出了一种静态业务量疏导问题的整数线性规划模型，可以通过改变模型中的参数来实现不同的优化目标；文献[11]研究了WDM网状网中的多对多多播疏导问题；文献[12]研究了基于单跳和多跳的动态多播疏导算法；文献[13]提出了一种基于跨层优化的联合路由疏导算法，可以在多粒度网络中实现较高能效；文献[14]提出了一种新的多粒度疏导算法，通过改变模型中的不同因子，可以提高WDM光网络的业务疏导效率。

然而，当前WDM光网络中的大多数多播疏导算法只针对单约束的情况，而没有考虑收发器数量、波长转换能力以及分光量等多约束的情况。在考虑收发器数量、波长转换能力和分光量等多约束的前提下，本文基于波长分层的思想[15]，设计了多约束多播光树建立算法（multi-constrained multicast light-tree establishing，MMLE）和多约束多播业务量疏导算法（multi-constrained multicast traffic grooming，MMT-G）。其中MMLE算法用于在MMTG算法中建立新光树。MMTG算法与MMLE算法相结合，可以很好地完成WDM光网络中业务量疏导的任务。

2　问题描述

已知的网络物理拓扑表示为Gp(V,L,W)，网络中的节点集、物理链路集和每条物理链路中的波长集分别表示为V、L、W。已知的多播路由请求表示为r(vs,D,br)，源节点表示为vs，目的节点集合表示为D，业务请求带宽表示为br，其中vs,D∈V。

通过MMLE算法，为业务请求建立一个满足光收发器数、波长转换能力以及分光量的多约束光树集合，之后通过MMTG算法，用建立的光树对业务请求进行疏导。

2.1约束描述

2.1.1光收发器数约束

在对网络中的业务进行疏导的过程中，当通过现有的逻辑链路无法找到到达目的节点的路由时，就需要建立新的光路。因为光路起于源节点的光发送器，止于目的节点的光接收器，所以新建一条光路，源节点和目的节点的光发送器和光接收器数量需要分别减1。逻辑链路必须记录当前可用的光发送器和光接收器的数量。若源节点的光发送器数量不足，或目的节点的光接收器数量不足，便无法建立光路。

2.1.2波长转换能力约束

对于vi∈V的所有节点，r表示其波长转换范围，增加从节点到节点的虚链路，将这种虚链路称为波长转换链路，其中。

2.1.3波长节点分光量约束

波长节点分光量表示一个波长节点当前已经使用的分光次数。举例来说，如果一个光树上的波长节点作为目的节点，它的分光量应为其子节点数加1，因为目的节点需要对业务数据流进行一次备份；而当一个波长节点为非目的节点时，这个波长节点的分光量即为其子节点的个数。

当一个波长节点的分光量尚未达到该节点最大的分光能力，且该波长节点的上一跳不是波长转换链路时，本文将这种节点定义为MC（multicast capable）波长节点。如图1所示，图中方形节点表示非目的节点，圆形节点表示目的节点，箭头表示业务数据流在多播树上的传输路径。假设图中节点均具有波长转换能力，v1节点最大分光能力为4次。初始波长为λ2的光信号首先到达v1，并在v1处进行3次分光，之后分别到达v2、v3、v4，光信号到达v2和v4后进行波长转换，由λ2转换为λ1。在这种情形下，的最大分光能力为4次，目前已经进行了3次分光，仍小于其最大分光能力，因此是MC波长节点。而图中不是MC波长节点，因为它的上一跳为波长转换链路。

Fig.1　MC wavelength node图1　MC波长节点

2.2链路代价

本文为波长转换链路、逻辑链路、接纳链路和波长链路的代价设置了不同的权值，分别表示为αwcl、αll、αal、αwll。不同的权值可以区分不同代价的优先级，上述顺序按权值的数量级降序排列，波长转换链路代价的权值最高，路由时便会倾向于选择波长转换链路较少的路径。选择其他链路的情况以此类推，这样就可以较好地实现负载均衡。

2.2.1波长转换链路

波长转换链路对网络负载几乎不产生影响，因为它仅仅在波长转换时产生一定时延。波长转换链路的代价可表示为：

2.2.2逻辑链路

WDM层的每一条光路都对应一条逻辑链路，二者的带宽相同。本文中光路即逻辑链路。在实际情况下，业务的个数无法准确反映逻辑链路的负载情况，因为不同业务所请求的带宽是不同的。可以用当前不可用带宽（工作占用或保护占用）与光路总带宽之比来表示逻辑链路的负载。这个比值越高，代表链路负载越重，这时需要为该链路设置相对高的代价，使得选路时尽量回避该链路；相反地，比值较低时，应为该链路设置较小的代价。

逻辑链路的总带宽、工作带宽、保护带宽分别表示为bt、bw、bp，用户请求带宽表示为br，则该逻辑链路的代价为：

2.2.3接纳链路

接纳链路与节点当前剩余的光收发器数量有关。剩余的光收发器越少，接纳链路的代价越高。对于同一个节点，光发送器和光接收器的使用情况显然是不相关的。

节点的总发送器、总接收器、可用发送器和可用接收器的数量分别表示为tt、rt、ta、ra，则该节点作为源节点时的接纳链路代价如下：

该节点作为目的节点时的接纳链路代价如下：

2.2.4波长链路

波长链路的代价与该波长链路所在的物理链路的使用情况有关。可以用当前不可用波长数量（工作占用或保护占用）与物理链路总波长数之比来表示物理链路的负载。本文为波长链路定义4种状态：用于保护，用于构建光路，用于构建光树，空闲。

若波长链路的资源已被完全占用，则其代价为∞；否则工作波长的数量表示为ww，保护波长的数量表示为wp。波长链路代价如下：

3　多约束多播光树建立算法

在考虑光收发器数量、波长转换能力以及分光量等多约束的前提下进行多播业务量疏导之前，必须先建立满足以上约束的光树集合。将这样的光树集合表示为F，当前正在创建的光树表示为T，其上的MC波长节点表示为Vmc，目前尚未处理的目的节点表示为D*，与D*中的节点相对应的逻辑节点表示为D′。算法描述如下：

4　多约束多播业务量疏导算法

本算法同时利用网络中的光路和光树对业务进行疏导。对于网络中现有的光树与到来的业务请求，二者的目的节点集可能存在交集。当交集元素个数达到一定数量时，便用该光树进行疏导；当光树的源节点与业务请求的源节点不同时，可以让业务流从源节点先通过已有光路到达某一光树的源节点，再用该光树进行疏导。

4.1疏导可用率

光树中可疏导的目的节点数ngrooming即为光树的目的节点集Vst与到来的业务请求的目的节点集D的交集：

疏导可用率rgrooming即为光树中可疏导的目的节点数ngrooming与光树中所有目的节点数||Vst之比：

4.2子树

在一次业务量疏导过程中，业务流可能由若干光树负责疏导，每棵光树负责疏导业务请求的一部分目的节点，且每棵光树所负责的目的节点集互不相交。若业务请求的源节点与现有光树都不相同，则在当前网络中查找从业务请求源节点到现有光树源节点的逻辑链路。若找到这样的逻辑链路，则让业务流先通过该逻辑链路到达光树，再用该光树进行疏导；若网络中不存在这样的逻辑链路，则新建一棵满足该业务请求的光树。由于业务请求由若干光树所承载，本文将承载业务请求的某一棵光树称为子树。

本文将子树的带宽定义为3种状态，分别为空闲、工作和保护。在一棵光树中，只有源节点可以作为业务请求的接入点，其他节点或为目的节点，或只能作为中间节点。如果光树的rgrooming比较低，可能会出现光树中只有少部分链路承担了业务量疏导的情况，而由于该光树已使用，导致其空闲链路并不能用于疏导其他业务，从而导致该光树的带宽利用率偏低。

如图2所示。假设业务请求的目的节点集为{v4,v5,v6,v7,v8}，网络中某光树的目的节点集为{v3,v4, v5}，{v4,v5}为目的节点交集，表示v4和v5可以利用该光树进行业务量疏导，rgrooming=66.7%。假设一条链路的带宽为br，该次疏导过程中链路v2→v3空闲，而v2只能作为中间节点，不能接受其他业务量疏导任务，因此该光树会有br的带宽浪费。为避免这种带宽浪费，最理想的情况是只有当某光树的rgrooming= 100%时才使用该光树进行疏导。但是，这样会导致网络中现有光树被用于新业务疏导的概率偏低，大部分业务量疏导都是通过新建光树完成的，使得波长链路资源消耗迅速，最终导致业务阻塞。因此，为rgrooming设置一个阈值是必要的。

Fig.2　Usage of light-tree bandwidth resources图2　光树带宽资源的使用

本文将rgrooming的阈值表示为Qgrooming，只有当光树的 rgrooming≥Qgrooming时，才使用该光树进行业务量疏导。为Qgrooming设置一个合理的值，可以在资源利用率和业务阻塞率之间寻求一个平衡点。

子树的总带宽、工作带宽、保护带宽分别表示为bt、bw、bp，业务请求带宽表示为br，则该子树的代价为：

4.3算法描述

当前网络中的光树集表示为Ta，业务量疏导使用的光树集表示为T，为业务量疏导创建的光树集表示为Tnew；当前网络中的逻辑链路集表示为La，业务量疏导使用的逻辑链路集表示为L，为业务量疏导创建的逻辑链路集表示为Lnew；尚未疏导的目的节点集表示为D*。算法描述如下：

5　性能分析

本文基于美国国家自然科学基金网NSFnet对该多播业务量疏导机制进行拓扑仿真实现。假设多播请求服从Poisson分布，业务流持续时间服从指数分布，并假设网络中所有节点的分光能力相同。αwcl、αll、αal、αwll取值分别为1、100、10 000、1 000 000，促使选路时优先选择使用波长链路最少的路径，其次选择接纳链路数较少的路径，即使用光收发器数较少的路径，以减少新建光路的数量。仿真参数如表1所示。

图3和图4表示MMTG算法和多跳疏导算法在自变量为业务强度，因变量为阻塞率的设定下的对比情况。仿真实验中，阈值Qgrooming设为0.01，光发送器和接收器的数量均设为16。实验结果表明，阻塞率会随着业务强度的增加而升高。在多跳疏导算法中，业务请求的目的节点集与光树目的节点集完全相同时才使用该光树进行业务量疏导，大部分疏导任务都是通过新建光树的方式完成的，使得网络中现有光树的复用率很低，导致光树的资源利用率较为低下。因此多跳疏导算法的阻塞率要高于MMTG算法。

Fig.3　Variation of blocking rate with traffic intensity on NSFnet图3　NSFnet拓扑上阻塞率随业务强度变化

Fig.4　Variation of blocking rate with traffic intensity on GEANT图4　GEANT拓扑上阻塞率随业务强度变化

图5和图6表示MMTG算法在自变量为疏导可用率，因变量为阻塞率的设定下的情况。仿真实验中，光发送器和光接收器的数量均设为16，业务强度设置为500。实验结果表明，随着阈值Qgrooming的增加，阻塞率先减小到一个最低点，而后缓慢增大，在Qgrooming>0.8后迅速增大。若阈值Qgrooming设置得当，MMTG算法可以提供较低的阻塞率，并在资源利用率和业务阻塞率之间达到很好的平衡；若阈值Qgrooming设置过高，则大部分业务量疏导是通过新建光树的方式完成的，导致网络带宽资源大量消耗，进而使得阻塞率迅速升高。

Fig.5　Variation of blocking rate with grooming usable rate on NSFnet图5　NSFnet拓扑上阻塞率随疏导可用率变化

Fig.6　Variation of blocking rate with grooming usable rate on GEANT图6　GEANT拓扑上阻塞率随疏导可用率变化

图7和图8表示MMTG算法和多跳疏导算法在自变量为光收发器数，因变量为阻塞率的设定下的对比情况。阈值Qgrooming设为0.01，业务强度设置为500。实验结果表明，MMTG算法和多跳疏导算法的阻塞率均随光收发器数量增加而降低，MMTG算法阻塞率一直低于多跳疏导算法，多跳疏导阻塞率下降明显。由于多跳疏导算法中，大部分疏导任务都是通过新建光树的方式完成的，导致光发送器和接收器的大量消耗。MMTG算法阻塞率在光收发器数大于8时趋于稳定，因为算法对网络中已有光树的复用率较高，很少新建光树，所以对光发送器和接收器数量要求不高，这时波长资源为算法的主要约束。

Fig.7　Variation of blocking rate with optical transmitters and receivers on NSFnet图7　NSFnet拓扑上阻塞率随光收发器数变化

Fig.8　Variation of blocking rate with optical transmitters and receivers on GEANT图8　GEANT拓扑上阻塞率随光收发器数变化

综上所述，MMTG算法相比于多跳疏导算法，在不同情况下均具有较低的阻塞率，能够较好地完成多播业务量疏导的工作。

[1]Wang Xingwei,Sun Jiajia,Li Hongxing,et al.A reverse auction based allocation mechanism in the cloud computing environment[J].Applied Mathematics&Information Sciences, 2013,7(1):75-84.

[2]Ajaykumar S,Ghosh S K.Traffic grooming in optical WDM mesh networks[C]//Proceedings of the 2008 IEEE Region 10 and the 3rd International Conference on Industrial and Information Systems,Kharagpur,India,Dec 8-10,2008.Piscataway,USA:IEEE,2008:1-6.

[3]Lin Rongping,Zhong Wende,Bose S K,et al.Leaking strategy for multicast traffic grooming in WDM mesh networks [J].Journal of Lightwave Technology,2012,30(23):3709-3719.

[4]Farahmand F,Zhang Qiong,Jue J P.Dynamic traffic grooming in optical burst-switched networks[J].Journal of Lightwave Technology,2005,23(10):3167-3177.

[5]Srinivasan R,SomaniAK.Dynamic routing in WDM grooming networks[J].Photonic Network Communications,2003,5 (2):123-135.

[6]Thiagarajan S,Somani A K.Traffic grooming for survivable WDM mesh networks[J].Optical Networks Magazine, 2002,3(3):88-98.

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

[8]Zhu Hongyue,Zang Hui,Zhu Keyao,et al.A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks[J].IEEE/ACM Transactions on Networking, 2003,11(2):285-299.

[9]Lin Rongping,Zhong Wende,Bose S K,et al.Design of WDM networks with multicast traffic grooming[J].Journal of Lightwave Technology,2011,29(16):2337-2349.

[10]Jaekel A,Bari A,Chen Ying,et al.New techniques for efficient traffic grooming in WDM mesh networks[C]//Proceedings of the 16th International Conference on Computer Communications and Networks,Honolulu,USA,Aug 13-16,2007.Piscataway,USA:IEEE,2007:303-308.

[11]Saleh M A,Kamal A E.Design and provisioning of WDM networks with many-to-many traffic grooming[J].IEEE/ ACM Transactions on Networking,2010,18(6):1869-1882.

[12]Khalil A,Hadjiantonis A,Assi C M,et al.Dynamic provisioning of low-speed unicast/multicast traffic demands in meshbased WDM optical networks[J].Journal of Lightwave Technology,2006,24(2):681-693.

[13]Wang Xingwei,Cheng Hui,Li Keqin,et al.A cross-layer optimization based integrated routing and grooming algorithm for green multi-granularity transport networks[J].Journal of Parallel and Distributed Computing,2013,73(6):807-822.

[14]Wang Xingwei,Hou Weigang,Guo Lei,et al.A new multigranularity grooming algorithm based on traffic partition in IP over WDM networks[J].Computer Networks,2011,55 (3):807-821.

[15]Chen C,Banerjee S.A new model for optimal routing and wavelength assignment in wavelength division multiplexed optical networks[C]//Proceedings of the 15th Annual Joint Conference of the IEEE Computer and Communications Societies,Networking the Next Generation,San Francisco, USA,Mar 24-28,1996.Piscataway,USA:IEEE,1996:164-171.

LI Tai was born in 1991.He is an M.S.candidate at Department of Computer Application Technology,Northeastern University.His research interest is Internet routing.

李泰（1991—），男，辽宁大连人，东北大学计算机应用技术系硕士研究生，主要研究领域为互联网路由。

WANG Xingwei was born in 1968.He received the Ph.D.degree from Northeastern University in 1998.Now he is a professor and Ph.D.supervisor at Northeastern University,and the member of CCF.His research interests include cloud computing and future Internet,etc.

王兴伟（1968—），男，辽宁沈阳人，1998年于东北大学获得博士学位，现为东北大学教授、博士生导师，CCF会员，主要研究领域为云计算，未来互联网等。

LI Fuliang was born in 1986.He received the Ph.D.degree from Tsinghua University in 2015.Now he is a lecturer at Northeastern University.His research interests include next generation Internet and network security,etc.

李福亮（1986—），男，辽宁葫芦岛人，2015年于清华大学获得博士学位，现为东北大学讲师，主要研究领域为下一代互联网，网络安全等。

HUANG Min was born in 1968.She received the Ph.D.degree in control theory from Northeastern University in 1999.Now she is a professor and Ph.D.supervisor at Northeastern University.Her research interests include modeling and optimization for logistics and supply chain system,etc.

黄敏（1968—），女，辽宁沈阳人，1999年于东北大学获得博士学位，现为东北大学教授、博士生导师，主要研究领域为物流与供应链管理，智能算法设计与优化等。

Multi-Constrained Multicast Traffic Grooming Mechanism*

LI Tai+,WANG Xingwei,LI Fuliang,HUANG Min
College of Information Science and Engineering,Northeastern University,Shenyang 110819,China

E-mail:nfsfan@126.com

In order to fully utilize the wavelength resources of the WDM(wavelength division multiplexing)optical networks,this paper proposes a multi-constrained multicast traffic grooming mechanism.According to a multi-constrained multicast light-tree establishing algorithm,this mechanism provides an effective solution to multicast traffic grooming in WDM optical networks under multi-constraints,including the number of optical transceivers,wavelength conversion capability and wavelength splitting capability.This paper evaluates the proposed traffic grooming mechanism based on the topology of the National Science Foundation Network of USA(NSFnet)and Pan-European Research and Education Network(GEANT).The simulation results show that the proposed mechanism can not only accomplish multicast traffic grooming effectively,but also gain a lower blocking proportion compared with the multihop traffic grooming mechanism.

optical networks;multicast routing;multi-constrained;light-tree;traffic grooming

2015-08,Accepted 2015-10.

10.3778/j.issn.1673-9418.1509096

A

TP393

*The National Natural Science Foundation of China under Grant Nos.61572123,61502092(国家自然科学基金);the National Science Foundation for Distinguished Young Scholars of China under Grant Nos.61225012,71325002(国家杰出青年科学基金);the Specialized Research Fund of the Doctoral Program of Higher Education of China for the Priority Development Areas under Grant No.20120042130003(高等学校博士学科点专项科研基金优先发展领域资助课题).

CNKI网络优先出版:2015-10-29,http://www.cnki.net/kcms/detail/11.5602.TP.20151029.1705.004.html

LI Tai,WANG Xingwei,LI Fuliang,et al.Multi-constrained multicast traffic grooming mechanism.Journal of Frontiers of Computer Science and Technology,2016,10(10)：1398-1406.