OBS基于回退和信道分级的冲突解决算法

李敏涛，陈荷荷，章晓春

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

引 言

随着波分复用技术的发展，光网络传输能力也大幅度地得到了提升，但是光网络中节点的路由交换能力却没有得到同步提高，这已成为当前光网络传输的瓶颈。目前比较主流的光交换技术主要有光电路交换(optical circuit switching，OCS)、光分组交换(optical package switching，OPS)和光突发交换(optical burst switching，OBS)。OCS技术比较成熟，但是交换的粒度比较大，带宽利用率不高，而OPS对于光器件的要求又非常高，实现的成本和技术难点比较大。

OBS技术结合了OCS和OPS的优点，规避了其技术难点，是近年来光交换技术研究的热点［1］，有望成为下一代光网络的核心交换技术。当网络数据到达边缘节点时，会根据一定的突发包汇聚算法使网络数据组成突发数据包(burst data packet，BDP)，每一个BDP都会产生一个相应的突发控制分组(burst control packet，BCP)，BCP包含 BDP传输交换所必须的控制信息。网络节点预先发送BCP，为BDP进行单向资源预留，使得BDP能够按照预留的资源路径进行数据的发送。有了这种资源预留机制，BDP在数据通道中传输时，就可以采用全光交换和传输，从而省略了光/电/光转换，达到了一个较好的传输效果。但是这种资源预留机制是单向的，很容易造成多个突发包竞争同一条链路资源的情况，冲突的产生必然会导致网络丢包率的上升，从而使得网络的性能下降。如何降低因突发包竞争资源而造成的网络性能的降低成为目前光突发交换研究的热点。

1 突发包竞争解决机制研究

目前解决突发包冲突问题，无外乎有降低突发冲突的概率和降低丢包率两种方法［2］。主流的方法主要有:光缓存、波长转换、偏射路由和突发包分段丢弃技术等［3-4］。这些方法都能从给一定角度上缓和网络的丢包率，但是各自仍有缺点，在网络负担比较重的情况下，甚至可能会带来更多的冲突问题，从而增加了丢包率并且带来了比较严重的延时［5］。

利用信道分级来解决突发包竞争问题［6］，此方法人为地将信道分为Ⅰ级信道和Ⅱ级信道，当突发包到达核心节点时，优先选择用Ⅰ级信道来传输，若Ⅰ级信道忙碌，再选择Ⅱ级信道传输，如果Ⅱ级信道忙碌，则延时做转发，如果有空余的Ⅱ级信道，则发送，否则丢弃，此方法能够较好地进行业务优先级的区分，Ⅰ级信道保证系统较低的延时性，Ⅱ级信道保证较低的丢包率［7］。

回退信道竞争解决机制(back-off channel contention resolution，BCCR)，主要思想是将链路中波分复用(wavelength division multiplexing，WDM)的多条信道中抽取少量作为回退信道，当发生竞争时，将突发包通过回退信道发送到上游节点，根据网络负担情况，重新进行路由转发［8］。这种方法能够有效地降低丢包率，但是其固定地占用了一部分网络的信道作为回退资源，没有考虑当回退信道发生竞争业务发生竞争时的处理方法，在网络业务繁重时，反而会带来更多的丢包率，并且这种方法并没有很好地考虑到数据包的优先级问题，不能很好地保证网络的服务质量(quality of service，QoS)［9］。

2 新算法

2.1 算法的提出

针对以上的情况，作者提出了一种考虑业务优先级的基于信道分级的带回退业务的冲突解决算法。该算法主要包括:(1)人为地将信道分为3类信道，Ⅰ级信道主要用来传输优先级较高的业务，而Ⅱ级优先级信道用来传输低优先级业务和部分高优先级竞争突发包转发，回退信道(back-off channel，BC)主要用来进行竞争突发包的回退转发，在不同的网络负载情况下，此3类信道能进行自适应的比例配比变化;(2)对于发生竞争的突发包，作者采用分段切割，尽量转发的思想，根据优先级的比较来进行综合考虑。这种算法的核心思想是最大限度地保障高优先级的业务的传输特性，此外，尽量保证低优先级业务的丢包率。

2.2 算法描述

作者定义信道类型有3类:Ⅰ级信道、Ⅱ级信道和回退信道，信道总数不变。为了方便描述，将业务类型简单得分为高优先级业务和低优先级业务两类［10］。t时刻开始标志信道分级，从该时刻开始，Ⅰ级信道只能传送高优先级业务，Ⅱ级信道可以传送高优先级和低优先级业务。

IDC(input data channel)为输入数据信道，ODC(output data channel)为输出数据信道，CBDH(content burst data with high priority)为高优先级竞争数据包，OBDH(original burst data with high priority)为高优先级原数据包，CBDL(content burst data with low priority)为低优先级竞争数据包，OBDL(original burst data with low priority)为低优先级竞争数据包，BC为回退信道，Mh表示高优先级业务的最大回退次数，用i来表示高优先级业务回退次数的统计，Ml表示低优先级业务的最大回退次数，用j来表示低优先级回退次数的统计。NⅠ为Ⅰ级信道的数目，NⅡ为Ⅱ级信道的条数，NBC为回退信道的条数，N为总的信道链路条数。

(1)高优先级数据包CBDH和高优先级数据包OBDH1发生冲突。

CBDH被分段，CBDH'沿着原先预设的路线(即ODC1)继续发送，CBDL″进行路由偏射到附近空闲的Ⅰ级信道ODC2上进行发送，如图1a所示。若偏射路由找不到空闲的Ⅰ级信道，则偏射到回退信道，经过一个回退机制，回退到前段节点，接着再转发到下一个节点的IDC，此时相当于延时了两倍的传输节点之间的传输时延，这时重新进行选择Ⅰ级信道进行数据的转发，如图1b所示。如果依然和各ODC上的数据发生冲突，则进入回退模式，同时计数器i++，当回退次数超过了极限，即i≥Mh时此时说明高优先业务过于繁忙，则在第Mh+1次将CBDH″偏射到临近的Ⅱ级信道，并将此信道标为Ⅰ级信道，NⅠ++，NⅡ--(注意:NⅡ≥1)，如图1c所示，如果找不到，则丢弃此突发包。

(2)低优先级数据包CBDL和高优先级数据包OBDH发生冲突。

说明此时竞争发生在Ⅱ级信道，此时将CBDL进行分段，CBDL'沿着原先预设的信道(即ODC1)发送，被分段的CBDL″被偏射到附件空闲的ODC2上进行发送，见图2a，若没有合适的Ⅱ级信道转发，则发射到回退信道，若回退信道忙碌，则直接丢弃此包，若回退信道空闲，则进入回退机制，经过突发包两倍的传输时延，重新回到IDC进行下一次的转发，见图2b;如果回退的次数j超过了Ml，说明网络低优先级业务的负担很繁重，则在第Ml+1此进行Ⅰ级信道寻找，如果找到一条合适的信道，则将此信道标为Ⅱ级信道，NⅡ++，NⅠ--，见图2c，如果找不到，则丢弃此突发包。

(3)两个低优先级的突发数据包CBDL和OBDL发生冲突。

说明此时竞争发生在Ⅱ级信道，将CBDL分段成CBDL'和CBDL″，CBDL'随着原先预设的信道资源和OBDL发送，而CBDL″则偏射路由，去寻找空闲的Ⅱ级信道，转发此数据，如果没有空闲的Ⅱ级信道，为了不让低优先级的业务过多的占用网络资源，选择直接丢弃。

Fig.1 Two high priority when burst conflict

Fig.2 Low priority burst and high priority burst

3 仿真说明

3.1 仿真场景

为了分析高低优先级两类突发包的丢包率情况，假定两类数据以泊松分布到达核心节点［9］，高优先级业务的到达率为λh，低优先级的到达率为λl，总的到达率为λ。高低优先级业务的到达时间设为τh和τl，服从指数分布。系统中链路总的条数为N，Ⅰ级信道条数为NⅠ，Ⅱ级信道条数为NⅡ，备用信道的数目用NBC来表示，那么，Ⅰ级信道可以用排队模型M/D/NⅠ/NⅠ表示，Ⅱ级信道用M/D/NⅡ/NⅡ表示(其中，M和D表示常数，排队模型M/D/NⅡ/NⅡ表示突发数据以泊松分布到达，系统服务时间为常数 D，有 NⅡ个服务对象，容量为 NⅡ的模型)，则有:

概率密度为:

那么容易得出:

系统的仿真环境OBS-NS搭建在开源的NS-2平台上，NS版本为2.28，采用的操作系统是开源UNIX操作系统。为了简化仿真过程，作者在系统中做如下约定:每条光链路包含65个波长信道，其中56个为数据信道，分为Ⅰ级信道和Ⅱ级信道，初始设置Ⅱ级信道个数为28条，Ⅱ级信号个数为28条，8个作为回退信道，1个为控制信道，波长信道传输速率为10Gbit/s，边缘节点数据流按照Poisson过程随机到达，两种优先级的网络负载采用归一化处理，设高优先的业务负载和低优先级的业务负载为L(0≤L≤1)，汇聚算法采用固定长度汇聚算法，IP包得平均长度为1250byte，突发数据包到达平均间隔是0.0001s，假设信道之间转发延时是0.0001s，仿真开始时间是0s，结束时间是2s。

3.2 结果分析

仿真结果如图3所示。

图3a表示的是在网络负载优先级不同的配比L下，高优先级业务和低优先级业务的丢包率情况，从图中可以看出来，当网络里高优先级业务占主要部分时，随着仿真时间的推移，高优先级业务的丢包率呈现快速下降的趋势;而低优先级业务的丢包率则一直保持较低的水平。这是由于新算法采用了动态调配不同等级信道的数目，当高优先级业务冲突较为严重时，表明网络中高优先级业务的负担比较重，随着时间的推移，新算法自适应得增加Ⅰ级信道的数目，并且由于回退机制的引入，大大降低了丢包率。

图3b表示的是当仿真结束时，不同网络负载的各业务丢包率比较，比较的是新算法的高优先业务丢包率、低优先级业务丢包率和回退信道竞争解决机制(back-off channel contention resolution，BCCR)算法。从图中可以看到，新算法在保证高优先级业务的低丢包率的情况下，对低优先级业务也有非常大的改善，尽管在某些时候可能会不如传统的BCCR算法，但是符合优先保证高优先级业务的原则。

图3c反映了仿真到达2s时，不同网络负载的各业务延时比较，从图中可以看出，不管是高优先级业务还是低优先级业务，随着相应网络比重的增加，延时都会增加，综合考虑到网络的丢包率，认为为此牺牲的延时是有价值的。

Fig.3 a—packet loss probability of high priority and low priority serviceswith different load b—packet loss probability of high priority，low priority and BCCR services c—time delay of high priority and low priority services

4 结论

提出了一种新型的考虑业务优先级的基于信道分级的带回退业务的冲突解决算法，该算法采用信道分级，将信道分为Ⅰ和Ⅱ两个级别，用来区别对待高低优先级两类业务，并且能根据实时网络业务的动态配比自适应地调整两类信道的数目;算法还划分出一部分的回退信道作为保护机制，当突发包发生竞争时，根据竞争业务的优先级进行突发包分段处理，被分段的突发包可以经过优先级比较，进入回退信道，在保护高优先级业务的稳定地低丢包率的同时，也能大幅度降低低优先级的丢包率和网络业务的延时。仿真结果证实，相比较BCCR算法，这种新型的冲突解决算法确实能够良好地保证高优先级的低丢包率，并且对低优先级的业务的丢包率也能大幅度降低。这些结果对于OBS网络的优化和设计都是有一定的参考作用的。

［1］CHEN Y，QIAO C，YU Y.Optical burst switching:a new area in optical networking research［J］.IEEE Network，2004，18(3):16-23.

［2］JIY F，WANG H X.Optical burst switching networks［M］.Beijing:Beijing University of Posts and Telecommunications Press，2005:38-45(in Chinese).

［3］VU H L，ZUKERMAN M.Blocking probability for priority classes in optical burst switching networks［J］.IEEE Communications Letters，2002，6(5):214-216.

［4］HOU R，SUN JQ，DING PF.Study of fair burst segmentation or droppingmethod in optical burst switched multi-hop network［J］.Journal of Electronics＆ Information Technology，2006，28(11):2144-2147(in Chinese).

［5］BIF J，ZHANGM，YE PD.A novel prioritized scheme for contention resolution in optical burst switched networks［J］.Acta Photonica Siniea，2005，34(6):900-904(in Chinese).

［6］XIANG B B，ZHU J，ZHANG J.Research on channel grading contention in OBS networks［J］.Optical Communication Technique，2011，15(4):20-22(in Chinese).

［7］BARAKAT N，DARCM TE，GANTIS.Back-off channel contention resolution in optical networks［C］//Optical Fiber Communication/National Fiber Optic Engineers Conference.New York，USA:IEEE，2008:759-762.

［8］LEE SK，SRIRAM K，KIM H K，etal.Contention-based limited deflection routing protocol in optical burst-switched networks［J］.IEEE Journal of Selected Areas in Communication，2005，23(8):1596-1611.

［9］HOU R，SUN JQ，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).

［10］WANG B Y，GUAN A H，ZHANG Y.A preemption window mechanism based on priority in E-OBSnetworks［J］.Laser Technology，2011，35(4):531-538(in Chinese).