OBS考虑优先级的突发包碎片可控合并重传算法

陈荷荷

(温州职业技术学院电子电气工程系，温州325000)

引 言

伴随着密集波分复用(dense wavelength division multiplexing，DWDM)技术的发展［1-2］，单根光纤的传播速度已经达到了Tbit/s级，光纤通信已然成为未来全光网络通信技术的主要载体。而光交换技术作为全光网络通信技术的一个关键技术，越来越受到国内外很多研究机构和学者的高度重视，已经成为现代光网络研究的一个重要领域［3］。目前较主流的光交换技术主要有以下3种方案:光电路交换(optical circuit switching，OCS)、光分组交换(optical packet switching，OPS)和光突发交换(optical burst switching，OBS)［4］。OCS 技术是一种面向连接的交换方式，其交换粒度大，带宽利用率不高，并不是现在主流的光交换技术。OPS技术实一种不面向连接的交换方式，在进行数据传输前不需要建立路由、分配资源，相比OCS，OPS技术具有很高的资源利用率和较强的适应突发数据的能力，但是它对光器件的要求非常高，多个分组的精确同步的技术难点实现比较困难。

QIAO等人提出了一种全新的光交换技术OBS，作为OCS到OPS的过渡技术，OBS技术结合了两者的优点，交换粒度适中、难度适中、灵活性强、网络带宽资源利用率高，被誉为是未来光网络中最有前途的光交换技术［4］。当网络中的数据到达边缘节点时，节点将数据按照一定的汇聚算法组装成一个突发数据包(burst data packet，BDP)，并为此数据包产生一个突发控制分组(burst control packet，BCP)，OBS通过预先发送BCP，来为数据包单向预留资源，从而使突发数据包能够透明地通过各个核心节点，提高了网络传送的效率［5］。从OBS的传输原理可见，这种资源预留机制是单向的，当网络有多个边缘节点同时向某核心节点的同一端口、同一波长发送数据时，就有可能造成多个资源竞争同一条链路资源，从而造成了数据的冲突［6］。如何降低丢包率、提高网络的性能，成为了目前光交换网络的研究热点。

作者在第一部分将详细介绍目前国内外对于如何降低突发包的丢包率问题的研究现状和存在的不足，进而提出新算法;在第二部分将对新算法模型进行详细的叙述并分析;在第三部分对新算法进行仿真验证，进而提出新算法在改善网络性能方面优于其它算法的证据;在第四部分对新算法进行总结。

1 算法背景

在OBS网络中，当网络资源发生竞争时，传统解决冲突的方法主要有光缓存法［7］、波长转换法［8］和偏射路由法［9］，这些方法在一定程度上能改善网络丢包率，但是各自仍有着无法弥补的缺点。另有学者提出，可将冲突的突发包丢弃，这种方法实现比较简单，但是它比较容易带来较大的丢包率。基于以上考虑，有研究者提出光组合突发交换技术(optical composite burst switching，OCBS)［10］，此算法考虑将突发包分段丢弃的策略，将冲突的数据包进行头尾分割，丢弃部分，这种方法能够降低网络的丢包率。但是研究发现，网络的负载有时候并不是平稳的，在某一时刻它负载非常重，这个时候采用突发包的分段丢弃策略，丢弃了大量的竞争包，但是在下一时刻，网络负载可能就比较轻，这样就浪费了网络资源，并且分段丢弃策略通常没有考虑到突发包的优先级，这样对于很多实际的基于服务质量(quality of service，QoS)的业务来讲是不利的［11］。又有学者在此基础上提出了一种基于优先级的先分割后缓存冲突解决算法(priority-based burst segmentation-optical buffer contention resolution，PBSCR)［12］，此算法考虑了突发包的优先级，将分割突发包进行光缓存处理，从而保证了高优先级突发包的低丢包率。但是这种算法引入了光缓存处理，使突发包碎片一直游离在网络路径中，极容易造成网络路径的阻塞，使信道的利用率下降。还有学者提出了突发包丢弃并重传策略(burst abandon and retransmission，BAR)，对于产生竞争的突发包采用丢弃之后，在中心节点会往突发包汇聚的边缘节点处发送一个确认字符信号，告知边缘节点该突发包已经被丢弃，与此同时边缘节点重新发送一个该突发包的副本，这种策略在一定程度上可以降低丢包率，但是此算法没有考虑业务的优先级等级，并且每次都采用重传整个突发包的方案，当网络负载比较大时，这种重传方案反而会增大冲突产生的概率，从而增大数据在核心节点的阻塞率，并且在一个支持QoS的OBS网络，并不需要重传所有的被丢弃的突发包［13］，这种算法使得网络传送数据的效率低下。在此基础上，作者提出了一种新型的考虑优先级的突发包碎片可控合并重调度算法(burst-segment recombination and controllable retransmission algorithm based on priority，BSRCR)。

2BSRCR算法介绍

2．1 BSRCR算法模型

BSRCR算法的模型如图1所示，当突发包在核心节点发生冲突时，根据突发包的优先级采用分段丢弃的策略，当分片结束后，目的核心节点会发送一个反馈信息给边缘汇聚节点。假设在某一时刻Ti，链路中有散落的n个突发包碎片，这些突发包碎片有自己的重传概率，分别为 αi1，αi2，…，αin。规定优先级较高的碎片的重传概率较高，这里假设αi1＞αi2＞…＞αin，即1号碎片的优先级最高，2号碎片次之，n号碎片优先级最低。当网络业务较为繁忙时，由于重传的碎片数目繁多，就有可能会造成网络通信的阻塞，所以在边缘节点处，设计一个突发包碎片重组装机制，此机制采用混合优先级的方式，在组装时，将优先级高的碎片尽量往中间靠，优先级低的碎片依次往两边放，这样能很好地保证高优先级业务的顺利通过，并且也尽可能地保证低优先级的通过。

Fig.1 Principle diagram of BSRCR

2．2 BSRCR算法模型分析

由于基于突发包粒度的整包重传方案已经不适用于分段重传的描述方法，在描述突发数据丢失率时，采用字节丢失率(byte-loss probability，BLP)代替包丢失率作为衡量网络的性能指标。算法的流程图按照图2所示。

Fig.2 Flow diagram of BSRCR

算法详细描述如下。

(1)信息反馈阶段:在时刻Ti，边缘节点向核心节点发送数据包时，因为发生资源竞争，采用突发包分片的策略，优先级较高的突发包顺利传送到核心节点处，优先级较低或者竞争无法处理的突发包碎片因此被丢弃，这些突发包的碎片为1号，2号，…，n号突发包，优先级按照数字的变大而降低。同时，核心节点向边缘节点发送一个反馈信息，要求边缘节点以一定的重传概率重传这些被丢弃的突发包碎片，重传概率分别为 αi1，αi2，…，αin，重传概率的设定根据网络的业务拥挤程度和突发包的优先级综合决定，通常优先级较高的，重传概率较大。

(2)突发包碎片重组阶段:当边缘节点收到反馈信息，得到的需要重传的突发包碎片过多时，边缘节点就开始进行突发包碎片的重组。为了方便描述，假设每次突发包碎片重组的个数最多3个，优先级编号为1，2，3，其中，1号为最高优先级，2号为次高优先级，3号为最低优先级，重传概率满足αi0＞αi1＞αi2。为了保证高优先级业务的顺利重传，在混合重组时，将优先级高的突发包碎片放在中间，优先级低得碎片放在两边，即如图3所示的组包方式，那么在时刻Ti+1重组包成功的概率为:

Fig.3 Contention occurred when the recombinant burst retransmit

(3)可控重传阶段:假设重组包成功的突发包以概率1进行发送，那么重组包在时刻Ti+1由边缘节点以概率重新发送，重发的情况如图3所示分情况讨论。当出现图3a所示时，两个重组突发数据包(data burst，DB)DB1和DB2发生冲突，那么将DB1的尾部发生分片，并根据它的重传概率进行重传。当发生如图3b中的情况，DB2的尾部发生分片，并重传。

用r来表示网络中源节点和目的节点之间的一条最优路径，用ηr，i表示路径r上Ti时刻较高优先级的突发包碎片的离开率，θr，i表示路径 r上 i时刻的突发包阻塞率。那么根据流量守恒定律，时刻i上，源节点中需要重新组包重传的突发包碎片增长率等于目的节点突发包的成功离开率，则有:

即:

则突发包在路径r上i时刻的离开率为:

λr，0表示路径r上突发包在源节点的到达率，那么，路径r上，从0时刻到i时刻这一段时间的突发包总到达率 λr，i可以表示为:

用Lr，ij(t)表示在i时刻、路径r上的第j个突发包碎片的分布长度，那么:

同时，i时刻、路径r上的组合突发包总碎片长度为:

用Gr，i(t)表示在 i时刻、路径r上的组合突发包的总分布长度，那么:

即:

3 仿真说明

系统的仿真环境OBS-NS搭建在开源的NS-2平台上，NS版本为2.28，采用的操作系统是开源的linux操作系统。仿真的网络拓扑采用美国国家科学基金会网络，它包含14个节点，21条双向传输链路。选用的路径r包含1个入口边缘节点、1个出口边缘节点、3个核心节点。为了简化仿真过程，作者在系统中做如下约定:每条光链路包含16个数据信道和1条控制信道，每个数据信道的传输速率为10Gbit/s，边缘节点数据流按照Poisson过程随机到达，网络负载采用归一化处理，汇聚算法采用固定长度汇聚算法，网络互联协议(internet protocol，IP)包的平均长度为1250byte，突发数据包到达平均间隔是0.0001s，假设信道之间转发延时是0.0001s，仿真开始时间是0s，结束时间是2s，假设突发包碎片重传的次数为3，即i≤3，每次重组合的最大包数为3，即j≤3。对于重传概率，假设一个突发包的重传概率是随着重传次数的增加而减少，令 αij=0．8α(i-1)j(其中i=2，3;j=1，2，3)。

图4～图7中给出了算法的仿真结果，图中对横坐标的业务负载量和纵坐标的比特丢失率、网络阻塞率均做归一化处理。

Fig.4 Byte loss probability of BSRCR with different retransmit probability when traffic load changes

Fig.5 Byte loss probability of BSRCR，OCBS and BAR when traffic load changes

Fig.6 Path blocking probability of BSRCR with different retransmit probability when traffic load changes

Fig.7 Path blocking probability of BSRCR，OCBS and BAR when traffic load changes

图4 中给出了BSRCR算法在路径r上，针对不同的重传概率，突发数据业务的字节丢失率情况。仿真了4 组数据，分别是当 α1j=0．3，α1j=0．5，α1j=0．7和 α1j=0．9时的数据情况，同时满足 αij=0．8α(i-1)j(其中，i=2，3;j=1，2，3)。可以观察到，这4组数据都反映了随着网络中业务量的增大，突发包的字节丢失率也在增大。同时，在相同的数据业务量情况下，当业务的重传概率越大，那么该突发数据包的比特丢失率也较低。从中可以得出结论，对于网络中优先级比较高地业务，当发生不可避免的冲突时，若适当地增加它的重传概率，可以大大降低其丢字节率，这样可以保证高优先级业务的顺利通过。

图5中给出了随着网络中业务量的增加，BSRCR算法、OCBS算法、BAR算法的比特丢失率比较，这里BSRCR的业务重传概率选取α1j=0．5，从图5中可以观察到，在开始网络业务量较小时，BRCR算法的突发包比特丢失率最小，而BSRCR和OCBS的丢比特率比较接近，但是随着网络业务的逐渐增大，BRCR算法的比特丢失率呈现比较大的上升率，而OCBS算法次之，BSRCR的丢比特率对于业务的增加呈现了较好的适应性，增加的趋势较为缓慢。这是因为BSRCR采用了新型的可控合并重调度算法，当网络业务较为繁忙时，它会综合考虑此时网络业务的负载情况和突发包的优先程度，需要选择合适的重传概率，并将网络中过多的突发包碎片进行合适的重组包算法，这样也减少了重发时的路径阻塞情况，提高了重发的成功概率。

图6反映的是BSRCR针对不同的重传概率，突发数据业务在路径r上的阻塞率。从图6中可知，在相同的业务量情况下，越高的重传概率带来了相对较大的网络阻塞率，并且，随着网络中业务量的增加，路径的阻塞率会逐渐增加，但是当业务量增加到一定程度，由于BSRCR采用了突发碎片重组装办法，网络路径的阻塞率反而会呈现一定的下降趋势，这对于高重传概率带来的高阻塞率有非常好的调节作用。

图7中给出了不同业务量情况下，BSRCR算法、OCBS算法、BAR算法的网络阻塞率比较，这里BSRCR的业务重传概率选取α1j=0．5，从图7中可以发现，随着网络负载的增加，BAR由于采取了突发包重传策略，会更加加重网络的阻塞率，而OCBS算法对于发生竞争的突发包采取直接丢弃的措施，故对于网络的阻塞率的影响较为平缓，而采用的BSRCR算法对于业务的阻塞率介于BRCR算法和OCBS算法中间。

4 结论

提出了一种考虑优先级的可控合并重调度算法BSRCR。当OBS网络中突发包因为竞争网络资源而发生冲突时，该算法采用基于优先级的突发包分片办法，同时，目的节点向边缘节点发送一个反馈信息，使得边缘节点以一定的概率重传该突发包分片。该重传概率根据网络的复杂情况和突发包分片的优先级动态决定，并针对由于重发的突发包碎片过多、而使得网络路径阻塞率过大的问题，采用突发包碎片进行一定优先等级排列的碎片重组，这样减少了网络中突发包碎片的数量，大大降低了网络的路径堵塞率，并保证了高优先级业务的顺利传送。在仿真部分中，给出了BSRCR算法在路径r上，针对不同的重传概率，突发数据业务的字节丢失率情况和业务阻塞情况，仿真结果对设定重传概率、突发碎片重组包方案、及业务优先级等方面提供了一定的参考意义。同时，还给出了不同业务量情况下，BSRCR算法、OCBS算法、BAR算法的比特丢失情况和网络业务阻塞情况比较，仿真结果证实，对于业务负载比较大的情况，BSRCR算法在比特丢失率方面较之OCBS算法和BAR算法，有很好的表现。在不同业务情况下，在网络阻塞率的改善方面，BSRCR算法介于BRCR算法和OCBS算法之间，但是其对业务比特丢失率方面的改善，这点阻塞率方面的牺牲是值得的。

［1］ BERGMAN L A，YEH C，MOROOKIAN J.Advances in multichannel multi Gbytes/s bit-parallel WDM single fiber link［J］.IEEE Transactions on Advanced Packaging，2001，24(4):456-462.

［2］ ZHAO T F，WANG W K，LIU L.A preferential shared path protection algorithm for WDM optical network［J］.Laser Technology，2012，36(3):408-412(in Chinese).

［3］ WANG B Y，GUAN A H，ZHANG Y，et al.A preemption window mechanism based on priority in E-OBS networks［J］.Laser Technology，2011，35(4):531-534(in Chinese).

［4］ QIAO Ch M，YOO M.Optical burst switching-a new paradigm for an optical internet［J］.Journal of High Speed Networks，Special Issue on Optical Networks，1999，8(1):69-84.

［5］ WANG B Y，GUAN A Y，ZHANG Y，et al.A deflection routing algorithm based on priority and load-balancing in optical burst switching networks［J］.Laser Technology，2011，35(3):343-347(in Chinese).

［6］ QIAO C.Labeled optical burst switching for IP-over-WDM integra-tion［J］.IEEE Communication Magazine，2000，38(9):104-114.

［7］ HOU R.Performance analysis of an improved burst outputted scheme in a limited buffer equipped OBS core node［J］.Optik-International Jouranl for Light and Electron Optics，2012，123(5):400-403.

［8］ YAO M，WEN A，LIU Z.Blocking probability of asynchronous optical burst/packet switches with limited range wavelength conversion［J］.IEEE Photonics Technology Letters，2006，18(12):1302-1304.

［9］ BALIGA J，WONG E W M，ZUKERMAN M.Analysis of bufferless OBS/OPS networks with multiple deflections［J］.IEEE Communication Letters，2009，13(12):974-976.

［10］ DETTI A，ERAMO V，LISTANTI M.Performance evaluation of a new technique for IP support in a WDM optical network:optical composite burst switching(OCBS)［J］.IEEE Journal of Lightwave Technology，2002，20(2):154-165.

［11］ HOU R，SUN J Q，DING P F.Study on a priority based contention resolution for optical burst switching networks［J］.Journal of Electronics＆ Information Technology，2006，28(4):747-752(in Chinese).

［12］ GUAN A H，WANG B Y，FU H L.A burst segmentation-optical buffer contention resolution mechanism based on priority in OBS networks［J］.Journal of Optoelectronics·Laser，2012，23(2):273-279(in Chinese).

［13］ LOU X，NING F，GAO Z H.ACK retransmission scheme on TCP over OBS networks［J］.Optical Communication Technique，2008，10(4):21-24(in Chinese).