报文路由器维护

Vol.
15,No.
32004JournalofSoftware软件学报1000-9825/2004/15(03)0414区分服务中分层视频组播报文测量和转发算法张明杰+,朱培栋,卢锡城(国防科学技术大学计算机学院,湖南长沙410073)APacketMeteringandForwardingAlgorithmtoSupportLayeredVideoMulticastinDifferentiatedServicesNetworksZHANGMing-Jie+,ZHUPei-Dong,LUXi-Cheng(SchoolofComputer,NationalUniversityofDefenseTechnology,Changsha410073,China)+Correspondingauthor:E-mail:skyws_hn@yahoo.
com,http://www.
nudt.
edu.
cnReceived2002-12-25;Accepted2003-06-04ZhangMJ,ZhuPD,LuXC.
Apacketmeteringandforwardingalgorithmtosupportlayeredvideomulticastindifferentiatedservicesnetworks.
JournalofSoftware,2004,15(3):414~420.
http://www.
jos.
org.
cn/1000-9825/15/414.
htmAbstract:Differentiatedservices(DiffServ)isascalablearchitectureforsupportingqualityofservices(QoS),andvideomulticastistheapplicationwhichneedsnetworktosupportQoSguarantee.
Toaccommodatetoheterogeneousnetworkandhost,itisagoodideatotransmitvideoinafewlayers.
ThepaperproposesLVMM(layeredvideomulticastmeter)andLVMF(layeredvideomulticastforwarder)algorithmsfordistributionofthelayeredvideomulticastinDiffServnetworks.
Themethodneedsonlyonemulticastaddressanditsvalidityisverifiedusingns-2simulator.
Keywords:qualityofservices;differentiatedservices;layeredvideomulticast;heterogeneousness;assuredforwarding摘要:区分服务是一种可扩展的服务质量支撑框架,视频组播是对服务质量有较高要求的应用.
为了满足端系统的异构性要求,对视频进行分层传输是比较好的方法.
研究了使用区服务中的确保服务进行分层视频组播传输的方法,提出了LVMM(layeredvideomulticastmeter)测量算法和LVMF(layeredvideomulticastforwarder)转发算法.
该方法只需要一个组播地址,其有效性通过ns-2模拟器进行了验证.
关键词:服务质量;区分服务;分层视频组播;异构性;确保转发中图法分类号:TP393文献标识码:A随着路由器技术和光传输技术的发展,Internet上的应用种类越来越多,这些应用具有各种各样的服务质量要求.
但是,当前的best-effort网络模型对应用不提供任何服务质量保证,端系统通过估计网络拥塞程度来调整SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.
90204005(国家自然科学基金)作者简介:张明杰(1974-),男,天津人,博士生,主要研究领域为网络服务质量,拥塞控制;朱培栋(1971-),男,博士,副教授,主要研究领域为网络路由,组播技术,高性能路由器;卢锡城(1946-),男,教授,博士生导师,中国工程院院士,主要研究领域为先进网络技术,高性能计算,并行与分布处理.
张明杰等:区分服务中分层视频组播报文测量和转发算法415发送速率.
视频组播对带宽有较高要求,典型的视频组播包括远程会议、视频点播、远程教学等.
由于best-effort网络的特点以及端系统处理能力和网络本身的异构性,使得以单一速率进行视频组播发布不能满足所有用户的要求[1].
为了解决这个问题,研究人员提出使用分层编码[1,2]进行视频组播发布:每一层是对前面层次的强化,不同层在不同的组播组中传输.
接收方根据当前网络资源的可用情况加入/退出组播组.
用户接收的层越多,视频解码的质量就越高.
虽然分层视频组播较好地解决了接收成员之间的异构性,但是由于best-effort网络不提供任何服务质量保证机制,因此,在其中进行视频组播传输必然存在接收质量不稳定、控制比较复杂、组播树变动比较频繁等问题,不适合对服务质量有较高要求的应用.
在网络中如何提供服务质量一直是研究的热点.
为了解决IntServ/RSVP模型可扩展性差的问题,近几年研究人员提出了DiffServ模型[3],该模型把服务质量要求分成几大类,应用可以使用某一类服务传输数据.
DiffServ网络由边缘路由器和核心路由器组成,边缘路由器根据用户要求对其流量进行测量,然后根据测量的结果为报文打上不同的标记;核心路由器根据报文标记执行简单的缓冲管理和调度转发.
由于DiffServ具有非常好的可扩展性,因此受到了广泛关注.
虽然DiffServ网络能够提供比较好的服务质量保证,但是在DiffServ网络中进行视频组播传输同样存在异构性问题,异构性产生的原因包括:(1)组成员需求的异构性:不同的组成员希望付出不同的费用来获得不同的接收质量;(2)端系统处理能力和网络带宽资源的异构性.
基于以上两点,在DiffServ中进行视频组播传输同样需要对视频源进行分层编码,以满足接收者的异构性要求.
DiffServ和组播相结合存在报文如何测量、标记的问题.
DiffServ中已有的标记算法TSWTCM[4]只适合标记单播报文,不适合异构组播报文标记.
因为在单播应用中,接收方只有一个,接收方的要求是确定的,这样就可以在报文的DSCP(DiffServcodepoint)中标记报文所属的服务类别及报文的丢弃优先级.
但是在组播应用中,由于接收者有多个且可以动态变化,同一个组播报文对一个接收者来说对应A服务,但是对另一个接收者来说对应B服务,因此边缘路由器无法使用已有的标记算法为组播报文打标记.
为了解决上述问题,本文提出了LVMM(layeredvideomulticastmeter)算法和LVMFLVMF(layeredvideomulticastforwarder)算法.
两个算法不仅较好地解决了异构组播在DiffServ网络中的传输问题,而且该方法只需要一个组播地址,既节约了存储开销,也避免了组播树的频繁变化问题.
本文第1节介绍DiffServ网络中进行分层视频组播传输的网络模型.
第2节阐述LVMM和LVMF算法.
第3节通过实验验证所提算法的有效性.
第4节介绍相关工作及比较.
第5节总结全文.
1网络模型Receiver3CorerouterReceiver1Receiver2VideoserverEdgerouterFig.
1Networkmodel图1网络模型DiffServ网络中进行分层视频组播传输的网络模型如图1所示.
在DiffServ网络中,外部可观察的路由器对每一类报文的转发行为称为PHB(per-hop-behavior).
IETF区分服务工作组定义了两类PHB:加速转发(expeditedforwarding,简称EF)PHB[5]和确保转发(assuredforwarding,简称AF)PHB[6].
AFPHB分为4类,每一类具有3个丢弃优先级.
使用AFPHB进行数据传输的用户首先向网络预约一定的带宽,边缘路由器根据416JournalofSoftware软件学报2004,15(3)用户当前的流量以及用户所预约的带宽给报文打上green,yellow,red三色,当核心网络发生拥塞时,报文的丢弃概率pgreen≤pyellow≤pred.
图1中的视频组播源具有如下特点:分层视频编码流用()LrrrL,.
.
.
,,,21表示,其中L为编码器的编码层数,为第i层的平均编码速率,设=.
这些层通过一个组播组发送,而不像best-effort中使用单独的组播地址传输每一层.
irmaxR∑=Liir1在DiffServ体系结构中进行视频组播传输,需要如下技术支持:QoS组播路由、资源预约以及报文标记和转发.
组播QoS路由是一个研究热点,已有的组播QoS路由算法见文献[7,8],本文不讨论DiffServ中的QoS路由问题,而是研究在QoS路由找到一条满足用户要求的组播树之后,如何进行资源预约和报文标记转发.
下面具体分析为什么TSWTCM算法不适合异构组播报文标记.
在图1中,如果接收者1预约的层数为2层,接收者2预约的层数为3层,那么,第3层的报文对于接收者1而言是高丢弃优先级报文(在预约范围之外),而对接收者2而言却是低丢弃优先级报文(在预约范围之内).
因此,与视频服务器相连的边缘路由器无法为报文打上丢弃优先级标记.
2算法本文的方法由3部分组成:组成员预约过程、边缘路由器测量过程以及核心路由器转发过程.
2.
1预约过程在DiffServ网络中,带宽资源必须在预约成功之后才能使用.
由于组播接收者的动态变化和资源要求的异构性,使得基于发送方发起的资源预留不适合组播传输.
如果使用传统的RSVP进行资源预留会带来NRS(neglectedreservationsubtree)问题[9],本文的资源预留过程对文献[9]的方法进行了简单扩充.
当每个接收者在加入组播组时,根据具体情况决定自己要使用的服务种类和需要接收的层数l及l层所对应的接收速率R=,然后向资源管理器提出资源预留请求.
在资源请求被认可之前,接收者只能使用LBE(limitedbesteffort,是比best-effort级别更低的服务)PHB接收数据;当接收者的资源请求得到资源管理器认可之后,接收者向分枝路由器传送λ=∑=liir1maxRR信息,λ为预约的接收比例.
分枝路由器接收到该预约消息后,把λ与对应分枝接口记录在组播路由表项之中,然后把当前输出接口中最大的max{λ}和max{R}沿组播树向上游路由器传送.
组播路由表项mEntry的结构如下所示:)),,,(),.
.
.
,,,,(),,,,(,,(22221111nnnnRSLOLRSLOLRSLOLGSλλλ.
其中组的源地址为,组地址为G,标示一个输出接口,为对应接口使用的服务级别,为对应接口上预约的带宽最大值,SiiOLiSLiRλ为对应接口上预约的带宽比例最大值.
DiffServ具有"核心简单"的特点,因此在DiffServ体系结构中核心路由器不维护资源预留信息;然而从路由器的角度看,组播与单播最大的区别在于组播是面向流的,核心路由器必须维护组播树信息,即使在best-effort网络中也是如此,那么在组播路由表项中加入上述信息之后,本质上没有增加系统的复杂性.
从下面的LVMF算法中可以看到,路由表项中维护预约比例信息使得报文的重标记过程很简单.
2.
2边缘流量测量算法LVMMLVMM算法的思想如下:组播源首先通知边缘路由器()LrrrL,.
.
.
,,,21信息,边缘路由器把该信息记录在策略表中.
同时边缘路由器维护一个测量的速率数组(][iavgr≤0iL≤),记录了由所有小于等于i层的报文组成的报文流的平均速率,其中=0.
组播源在发送报文时,把该报文属于的层信息写在IP报文头的TOS(DiffServ中称为DSCP)域中.
当有组播报文到达时,边缘路由器首先取出层信息,然后更新数组.
][iavgr]0[avgr][iavgrLVMM算法.
接收到一个组播报文Setp1:张明杰等:区分服务中分层视频组播报文测量和转发算法417读取报文对应的层数layer;for(i=layer;i≤L;i++){计算平均速率ravg[i];}Step2:在[max]1[Rrlayeravg,max][Rrlayeravg]取一个均匀分布的随机数rand;把rand记录在报文的DSCP域中计算采用时间滑动窗口算法][iavgr[10].
由于每个接收者所要求的服务类型和带宽比例信息已经记录在组播路由表项之中,这时DSCP失去了标记报文服务类型的作用,因此可以把rand记录在DSCP域中.
2.
3核心路由器转发算法LVMFLVMF算法.
对于每一个分枝接口:If(rand≤λi)报文送入SLi的green队列;elseif(rand≤iSLRSumRC)报文送入SLi的yellow队列;else报文送入SLi的red队列;其中,CSL为链路分配给对应服务类的带宽,SumR为对应服务被预约的带宽总量.
rand记录在报文的DSCP域中,Ri,λi记录在路由表项中,SumRSLC也是预计算好的.
算法中报文进入yellow队列的比例与一个组播组在该输出链路上预约的带宽成正比,从而保证了对剩余带宽的公平共享.
2.
4算法性能分析对于LVMM算法,复杂性主要来自于for循环的次数.
为了分析方便,设第i层在单位时间内到达的报文数为ni,则单位时间内for循环的次数为(1)∑=+=LiimniLN1)1(由于分层视频编码的模式各不相同,下面具体分析指数递增分层编码模式下LVMM算法的复杂性.
指数递增分层编码模式[1,2]具有如下特征:ni=(112niLi≤≤1)(2)把式(2)带入式(1)∑=+=LiimniLN1112)1(=242(++1111)2)1(.
.
.
83422().
.
.
1nLnLLL++++++=2(111]12)2[()12nLnLLL+=12(nL(3)1)2L+考虑一个单播应用流,如果在单位时间内到达的报文数为,那么,TSWTCM需要计算次平均速率,而且有∑=Liin1∑=Liin1===(4)uN∑=Liin1∑=Liiin1121)12(nL418JournalofSoftware软件学报2004,15(3)比较式(3)和式(4)2)12()22(111路由器维护路由信息,核心路由器只进行报文复制和转发,并且针对该框架提出了组成员加入/退出算法.
DSMCast方法让报文携带组播树和服务级别信息,类似于源路由,该方法的缺点是,当组播树很大时(如密集模式),或者报文比较小时,每个报文携带的额外信息相对太多造成了有效带宽的利用率低.
文献[9,12]的工作只是针对接收者预约的服务级别不同,对于接收方预约带宽异构的情况没有考虑或没有给出解决方法,而预约带宽不同是很实际的问题.
本文具体分析了具有带宽异构性要求的应用实例——分层视频组播如何在DiffServ网络中进行高效传输问题.
由于用户预约的带宽不一样,因此必须解决报文测量和转发问题.
本文借鉴了文献[9]的思想并且对其进行了扩充,在组播路由表项中不仅记录了用户预约的服务级别,而且记录了接收者预约的带宽信息,从而满足了用户的带宽异构性要求.
420JournalofSoftware软件学报2004,15(3)5结语本文提出了在DiffServ网络中进行分层视频组播传输的机制.
该机制主要由LVMM和LVMF两个算法组成.
该方法简单、易于实现,较好地解决了DiffServ网络中进行分层视频组播的异构性问题.
而且与best-effort中使用的方法比较,本文的方法还有一个特点,就是只使用了一个组播地址.
这样既节省了路由表存储空间,又避免了组成员加入/退出组播组带来的处理开销.
最后指出一点,本文的方法同样适用于非分层的组播应用,对于非分层的组播应用而言,相当于L=1的情况,此时接收者向网络预约某种服务并且指出其预约的接收比例lλ=1.
References:[1]McCanneS,JacobsonV.
Receiver-Drivenlayeredmulticast.
In:Proc.
oftheACMSIGCOMM'96.
NewYork:ACMPress,1996.
117~130.
[2]GopalakrishnanR,GriffioenJ,HjálmtssonG,SreenanCJ,WenS.
Asimplelossdifferentiationapproachforlayeredmulticast.
In:SidiM,ed.
Proc.
oftheIEEEINFOCOM.
TelAviv:IEEECommunicationsSociety,2000.
461~469.
[3]BlakeS,BlackD,CarlsonM,DaviesE,WangZ,WeissW.
Anarchitecturefordifferentiatedservices.
RFC2475,InternetEngineeringTaskForce,1998.
[4]FangW,SeddighN,NandyB.
Atimeslidingwindowthreecolourmarker(TSWTCM).
RFC2859,InternetEngineeringTaskForce,2000.
[5]JacobsonV,NicholsK,PoduriK.
AnexpeditedforwardingPHB.
RFC2598,InternetEngineeringTaskForce,1999.
[6]HeinanenJ,BakerF,WeissW,WroclawskiJ.
AssuredforwardingPHBgroup.
RFC2597,InternetEngineeringTaskForce,1999.
[7]FaloutsosM,BanerjeaA,PankajR.
QoSMIC:QualityofservicesensitivemulticastInternetprotocol.
In:Proc.
oftheACMSIGCOMM'98.
NewYork:ACMPress,1998.
144~153.
[8]ChenS,NahrstedtK,ShavittY.
AQoS-Awaremulticastroutingprotocol.
In:SidiM,ed.
Proc.
oftheIEEEINFOCOM.
TelAviv:IEEECommunicationsSociety,2000.
1594~1603.
[9]BlessR,WehrleK.
IPmulticastindifferentiatedservicesnetworks.
InternetDraft,InternetEngineeringTaskForce,2000.
[10]ClarkD,FangW.
Explicitallocationofbesteffortpacketdeliveryservice.
IEEE/ACMTrans.
onNetworking,1998,6(4):362~373.
[11]Ns-2Networksimulator.
http://www.
isi.
edu/nsnam/ns[12]StriegelA,ManimaranG.
AscalableapproachtodiffServmulticasting.
In:NeuvoY,ed.
Proc.
oftheIEEEInt'lConf.
onCommunications(ICC).
Helsinki:IEEECommunicationsSociety,2001.
2327~2331.