WDM网络中的一种基于BFP_Tree方法的负载平衡路由机制

光通信研究

STUDYONOPTICALCOMMUNICATIONS

2009.12(Sum.No.156)

通信系统与网络技术

WDM网络中的一种基于BFP󰀁Tree方法的

负载平衡路由机制

徐玲艳,王汝言,吴大鹏

(重庆邮电大学重庆高校光纤通信技术重点实验室,重庆󰀁400065)

摘要:文章提出一种基于数据包频率模式󰀁树结构(BFP󰀁Tree)方法的负载平衡路由机制,该机制首先统计所有路径节点的使用频度;然后选取使用频度最高的节点路径,按照网络中各链路使用波长数的统计方差最小的原则,对业务请求进行路由选择。仿真结果表明:该方法在阻塞概率和传输延迟性能方面都优于BFP󰀁Tree路由机制。关键词:全光网络;负载平衡;路由机制;路径

中图分类号:TN915󰀁󰀁󰀁文献标识码:A󰀁󰀁󰀁文章编号:1005󰀁8788(2009)06󰀁0001󰀁03

ABFP󰀁Tree󰀁basedload󰀁balancingroutingmechanisminWDMnetworks

XuLingyan,WangRuyan,WuDapeng

(KeyLaboratoryofOpticalFiberCommunicationofChongqingCollege,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)

Abstract:Aload󰀁balancingroutingmechanismbasedonBFP󰀁Treeapproachisproposedinthispaper,whichfirstcountsuptheusefrequencyofallthenodes,thenchoosesthemostoftenusedpathandperformsroutingselectionforthetrafficrequestac󰀁cordingtotheprinciplethatthestatisticalvarianceofthenumberoftheusedwavelengthsforeachlinkinthenetworkistheminimum.SimulationresultsshowthatthismechanismissuperiortotheBFP󰀁Treeroutingmechanisminbothblockingproba󰀁bilityandtransmissiondelay.

Keywords:all󰀁opticalnetwork;loadbalance;routingmechanisms;path

󰀁󰀁随着宽带视频、多媒体等业务的日益发展,尤其是Internet业务的持续快速增长,对骨干网的带宽提出了越来越高的要求。波分复用(WDM)技术以传输容量大、对高层协议和技术适应性强和易于扩展等优点得到了广泛的应用。目前采用路由选择和波长分配的WDM光传送网被公认为是下一代高速广域骨干网最具有竞争力的技术[1]。对于WDM网络来说,提高网络整体性能的主要途径是降低网络阻塞率和缩短传输延迟。文献[2]在最短路由[3]选择机制的基础上提出了一种负载平衡的路由机制,该路由机制大大降低了网络的阻塞率,但在传输延迟性能方面却未得到改善。数据包频率模式󰀁树结构(BFP󰀁Tree)算法[4]是根据节点使用频率来选路,优先选节点使用频率最高的,假如两节点使用频率相等,就选取子节点使用频率高的路径。该算法大大改善了传输延迟性能,但由于未考虑网络负载情况,有可能使得某些链路特别󰀂繁忙 ,承载了较多的业务,而其他链路又比较󰀂空闲 ,大量的波长信道闲置,因而资源不能得到合理的利用,导致网络阻塞

率较高。本文提出一种新的基于BFP󰀁Tree方法的负载平衡路由机制,对其进行了数学建模和算法描述,并通过仿真分析验证了该算法的优越性。

1󰀁基于负载平衡思想的路由机制

BFP󰀁Tree算法是根据节点使用频率来进行选路,但这样会使得阻塞率较高。针对这一缺点本文提出一种优化算法,通过一个优化过程,使得全网链路业务负载(波长使用数)更加均衡,从而有效地降低网络阻塞率。基于负载平衡思想的路由机制假定一个给定的网络可描述为G(M,L,W),其中,M代表节点集,L代表链路集,W代表网络使用的波长集。算法的流程是先为业务节点寻找路由,然后在路由经过的链路上分配波长,最后建立光路。1.1󰀁数学建模

定义i、j为网络中的相邻节点;s、d分别为源节点和目的节点;Rsd:若从源节点s到目的节点d的路径通过链路(i,j),则Rsd为1,否则为0;Rsd:若从源节点s到目的节点d且使用波长󰀁的路径通过链路

ij

ij,󰀁

ij

收稿日期:2009󰀁08󰀁17

基金项目:国家自然科学基金资助项目(60972069);重庆市科委自然科学基金资助项目(CSTC2008BB2414);重庆市教委自然科学基金资助项目(KJ080513);重庆邮电大学自然科学基金资助项目(A2007󰀁46)

作者简介:徐玲艳(1985󰀁),女,江西南昌人,硕士研究生,主要研究方向为光交换网络技术。

1光通信研究

,󰀁

(i,j),则Rijsd为1,否则为0;󰀁sd:若路径(s,d)使用

2009年󰀁第6期󰀁总第156期

所以有F∀

ij&rt

波长󰀁,则󰀁sd为1,否则为0;󰀁ij:若链路(i,j)中波长已被使用,则󰀁ij为1,否则为0;|L|为网络中的链路数;|W|为每条链路所包含的波长数;N为一条链路中的光纤数。

目

ij

n

ij&rt

!

|󰀂ij-󰀂rt|

2

。定义Fmax=

!

|󰀂ij-󰀂rt|,目标简化为Minimize{Fmax}。算法的具体步骤如下:

(1)用BFP󰀁Tree方法进行初始化选路。先计

1.2󰀁算法步骤

标

󰀁

sd

函数-

Minimize:1|L|

n

ij

󰀁

sd

F

ij,n,󰀁sd

=

2

!!!!R

约束条件为

ij,n,󰀁sd

!!!!R

1󰀁󰀁j=s1󰀁󰀁j=d󰀁,0󰀁󰀁其他

;

算所有路径节点的使用频度,确定节点使用频度阈值以上的节点,列出树形结构图,并标出每个节点的使用频率。

(2)选取使用频率最高的节点;假如节点使用频率次数相等,就考虑子节点的使用频率次数,选取子节点使用频率高的节点形成链路Ri。以此原则查找出所有路径,并按跳数由少及多置入链路集合L(N),即L(N)={L1,L2,∃,Ln}。

(3)定义B(i) L(N),且B(i)={L1,L2,∃,Li}(1∀i∀n),用负载平衡算法对B(i)中的路径计算F值。取i值为路径数(即链路集合B中包含L(N)中前i条最短路径),为了方便描述记为bal󰀁ance。

(4)选择这balance条路径中F值最小的路径并发送数据。如果数据发送失败,则选取balance条路径中F值次小的路径发送。

(5)为了不增加核心节点的处理负担,不增大数据端到端的延迟,故不必对每一个数据都采用一次平衡算法来达到波长使用均衡的目的,而只需每隔时间T执行一次。设ti为系统上次路由更新时刻;t为系统当前时间,如果t=ti+T,则返回第(1)步;否则,新业务请求按原路径发送。T的取值可以视网络负载情况而定,当负载及网络拓扑相对稳定时,T可以稍大;相反,当负载变化较快或网络拓扑变化时,T可以稍小。

!R

i

ij,nsd

-

!R

k

jk,nsd

=

(1)(2)(3)(4)(5)(6)

!

nsd

ij,nR!sd∀|L|-1,ijij,nsd

!R

n

∀|W|,

ij,nsdsj,nsdid,nsd

!!R

sd

∀|W|#|N|,∀|W|#|N|,∀|W|#|N|。

!!R

n

jd

!!R

n

is

其中,式(1)限定了各节点的波长使用情况,也体现了波长连续性的约束;式(2)限定了一次路由请求所经过的链路数最多为|L|-1;式(3)限定了在一条光纤中最多可用|W|个波长;式(4)限定了一个请求通过中间节点时可选波长数最多为|W|#|N|,体现了各节点全波长变换;式(5)限定了入口节点处理波长数最多为|W|#|N|;式(6)限定了出口节点处理波长数最多为|W|#|N|。

由于上述模型是一个NP󰀁C[5]问题,所以解决优化计算的问题十分重要。关于一般NP问题解决办法可参照文献[6~9]。为了便于对问题的处理,下面提出一种对模型的简化方案。

定义:󰀂ij和󰀂rt分别为链路(i,j)和(r,t)的已分配波长数,其值分别等于!󰀁ij和!󰀁rt。

󰀁

󰀁

2󰀁仿真分析

仿真条件如下:(1)拓扑使用NSFnet即美国国家科学基金会网络(如图1所示);(2)每个核心节点外接一个边缘路由器,每条链路都是一对双向光纤,

每根光纤传输8个波长;(3)全网所有节点对间的业务强度都相同,即支持的业务为均匀业务;(4)光路建立请求按参数为󰀁的泊松过程独立地到达网络各节点;(5)光路建立后业务的持续时间服从均值为1/ =1(时间单位)的负指数分布,故全网总负载为󰀁/ ;(6)假设每个核心节点完全没有波长变换能

目标为Minimize{F},

F=

!

ij

󰀂ij-

1|L|

!󰀂

i,j

2

ij

,(7)

式中,󰀂ij∀|L|,记|L|为n,󰀂ij为xi(i=1,2,∃,n),1!󰀂ij=x󰀂,则

|L|ij

F%=

i=1

!(x

n

i

-x󰀂)2=1n

i&j

!(x

i

-xj)2,

2

式中,n为常数,舍去,因而上式可简化为

F%=2!

i&j

(xi-xj)2∀

!

i&j

|xi-xj|,

力;(7)一旦一个光路建立请求被拒绝,则立即丢弃,看作网络阻塞一次。

徐玲艳等:󰀁WDM网络中的一种基于BFP󰀁Tree方法的负载平衡路由机制

塞率降低为BFP󰀁Tree路由方案的29.2%,平均可以使阻塞率较BFP󰀁Tree路由方案减少23.7%。

图1󰀁NSFnet拓扑

图1中,假定请求是从源节点1到目的节点14,为了降低复杂性,路径的节点数限制在6以内。根据预计算的路径,计算每个节点出现的频度,假设频度阈值为35%,则节点2、3、6、8、10、11和12符合要求,节点4、5、7、9和13被隐藏;然后,根据被隐藏后的路径进行选路,选路按照选路标准根据频率高低而定,选节点使用频率最高的,若使用频率相等,则考虑子节点的使用频率;这样就能按使用频率原则选择出一条最合适的路径

[10~11]

图3󰀁有负载平衡与无负载平衡时

阻塞率与负载的关系

3󰀁结束语

本文针对BFP󰀁Tree方法路由机制网络阻塞率较高和传输延迟较大等问题,提出了基于BFP󰀁Tree方法的负载平衡路由机制,利用负载平衡的思想来改善网络阻塞率和传输延迟。这种路由方案使网络中各链路波长使用数的统计方差最小化,从而提高了网络资源利用率。仿真结果表明:该方法在阻塞率和传输延迟性能方面都优于BFP󰀁Tree路由机制。对实现平衡的网络中的生存性问题的研究将是下一步的工作。

参考文献:

[1]󰀁GREENPE.Opticalnetworkingupdate[J].IEEEJ

SelAreasinCommun,1996,14(5):764󰀁779.

[2]󰀁赵成仕.光突发交换网络中一种基于负载平衡的路由

机制[J].电子学报,2006,34(11):2085󰀁2089.[3]󰀁GURUT.Dynamiccongestion󰀁basedloadbalance󰀁

droutinginopticalburst󰀁switchednetworks[A].Pro󰀁ceedingsofIEEEGlobecom2003[C].SanFrancisco,CA:IEEE,2003.2694󰀁2698.

[4]󰀁HwangI󰀁Shyan,ChiuChaochang,ShyuZen󰀁Der.A

frequent󰀁patternapproachforopticalnetworksroutingplanning[J].PhotonNetwCommun,2008,(7):218󰀁225.

[5]󰀁CHLAMTACI.Lightpathcommunications:anap󰀁

proachtohighbandwidthopticalWANs[J].IEEETransComm,1992,40(7):1171󰀁1182.

[6]󰀁ZALESKYA.Evaluationoflimitedwavelengthcon󰀁

versionanddeflectioninopticalburstswitchednet󰀁works[A].ProceedingsofICC2004[C].Paris:2004IEEEInternationalConference,2004.1543󰀁1547.

(下转第51页)󰀁󰀁

。

图2所示为不同balance情况下的阻塞率与负

载的关系,目的是从按跳数排列的前balance中选出一条波长使用最均衡的路由。balance太小时,很难实现波长使用数均衡,而balance太大时,在实现网络波长使用数最均衡的前提下,会使所选路由所走的路径相对较长,这样反而会在负载较小时造成网络阻塞,导致性能下降。由图2可知,balance=3时网络性能最佳,所以以下的仿真都是基于balance=3的条件展开的。

图2󰀁不同balance情况下阻塞率与负载的关系

图3给出了有负载平衡和无负载平衡时阻塞率与负载的关系图。仿真结果是以图1所示的网络拓扑且每个节点的爱尔兰负载为30~70为条件得出的网络阻塞率(只要网络中任何一条链路发生阻塞就认为网络发生阻塞)。从图中可以看出,在低负载情况下(30~40Erl),均衡后的路由方案可以使阻

3徐󰀁来等:󰀁光纤通信用可调谐色散补偿器的研究进展

sionCompensator[A].ECOC2008[C].Brussels,Belgium:NexusMediaLimited,2008.17h00󰀁17h30Mo.4.C.3.

[11]SenoKazunori,SuzukiKenya,WatanabeKei,etal.

Channel󰀁by󰀁channeltunableopticaldispersioncompen󰀁satorconsistingofarrayed󰀁waveguidegratingandliq󰀁uidcrystalonsilicon[A].OFC/NFOEC2008[C].SanDiego,California,USA:OSA,2008.OWP4.

(上接第3页)󰀁󰀁

[7]󰀁ZALESKYA.Routingandwavelengthassignmento󰀁

vermulti󰀁fiberopticalnetworkswithnowavelengthconversion[A].ONDM2003[C].Budapest,Hungary:SpringerNetherlands,2003.333󰀁346.

[8]󰀁BANERJEED.Apracticalapproa󰀁chforroutingand

wavelengthassignmentinlargewavelength󰀁routedopti󰀁calnetworks[J].IEEEJSelectAreasCommun,1996,4(5):903󰀁908.

[9]󰀁HYYTIAE.Linearprogramformul󰀁ationforrouting

probleminOBSnetworks[A].ISCC2004[C].Alex󰀁

andria,Egypt:IEEE,2004.252󰀁257.

[10]AgrawalR,ImielinskiT,SwamiA.Miningassociation

rulesbetweensetsofitemsinlargedatabases[A].ProceedingsoftheACM󰀁SIGMODInternationalCon󰀁ference1993[C].Washington,USA:InternationalConferenceonManagementofData,1993.207󰀁216.[11]BorgeltC,KruseR.Inductionofass󰀁ociationrules:

aprioriimplementation[A].15thConferenceonCom󰀁putationalStatistics2002[C].Heidelberg,Germany:PhysicaVerlag,2002.395󰀁400.

(上接第16页)

端口处将产生一个种子波长。一旦自种子光建立起来了,RSOA就能通过传送到OLT的上行数据进行直接调制,同样的RSOA能作为种子光用在所有

的ONU中,因此传输波长由AWG的光谱特性所决定。

参考文献:

[1]󰀁ZhangBo,LinChinlon,LiHuo,etal.Asimplehigh󰀁

speedWDMPONutilizingacentralizedsupercontinu󰀁umbroadbandlightsourceforcolorlessONUs[A].OpticalFiberCommunicationConference,2006andthe2006NationalFiberOpticsEngineersConference[C].California:IEEE,2006.3.

[2]󰀁HannS,KimTae󰀁Young,ParkChang󰀁Soo.Direct󰀁

modulatedupstreamsignaltransmissionusingaself󰀁injectionlockedF󰀁PLDforWDM󰀁PON[A].OpticalCommunication,2005.ECOC2005.31stEuropeanCon󰀁ference[C].Scotland:IEEPhotonicsProfessionalNet󰀁work,2005.451󰀁452.

[3]󰀁HealeyP,TownsendP,FordC,etal.Spectralslicing

WDM󰀁PONusingwavelength󰀁seededreflectiveSOAs[J].IEEElectLett,2001,37:1181󰀁1182.

[4]󰀁KoponenJJ,SoderlundMJ.AduplexWDMpassive

opticalnetworkwith1:16powersplitusingreflectiveSOAremoduatoratONU[A].Proc.ofOFC∋2004[C].California,CA:IEEE,2004.99.

4󰀁结束语

随着用户对带宽需求的不断增长,WDM󰀁PON将成为新一代光接入网的最佳选择,为了降低ONU的成本,出现了无色ONU。无色ONU的发射波长是不确定的,其由在远端节点的AWG的滤波属性、ONU的注入光或种子光的波长所决定。鉴于早前一些方案的调制速度低,本文提出了基于注入锁定的FP󰀁LD和种子波长RSOA的选择方案。注入锁定的FP󰀁LD或者种子波长RSOA的发射波长由种子光决定,其由位于中心局的宽带光源通过窄带分割而成。本文介绍的3种无色ONU的方案都有各自的特点,均可降低WDM󰀁PON系统的初期建设投资和长期运营成本,无色ONU将是构建WDM󰀁PON的一种理想方案。

51