一种改进的光突发交换数据信道调度算法

　　1 引言

　　在光突发交换(OBS)网络中，控制分组(BHPBurst Head Packet)和数据分组(BDP-Burst DataPacket)在时间和空间上是分离的。由于采用了单向资源预留方式，BHP先于BDP在特定的WDM信道巾传送，核心节点根据BHP中的信息为相应的BDP建立全光通路。BDP经过一段延迟后，在不需要确认的情况下直接在预先设置的全光通道中透明传输[1，2]。在这种情况下，核心节点如何根据BHP中的信息及当前节点信道占用情况为后续到达的BDP合理配置相应的交换矩阵，即数据信道调度算法，就成为人们研究的一个热点。一个好的数据信道调度算法应尽量做到：(1)算法简单，计算量小;(2)信道利用率高，丢包率低：(3)不增加额外的网络资源开销及网络设备的复杂程度。传统的调度算法如LAUC，LAUC_VF等[3, 4]，都是仅针对当前BHP来调度分配信道的,这样就可能造成对当前的BHP来说,该次调度为最合适的调度。但对后续到达的其它BHP该次调度为不合理的涮度,从而造成数据信道使用不合理现象的出现[5]。考虑图1(为方便仅以两个数据信道为例)所示的情况，图中每一个方框代表一个BDP，方框中数字代表与BDP相应的BHP的到达顺序，也就是BDP被调度的顺序，BDP5为新到达的BHP对应的BDP。采用LAUC或LAUC_VF等传统调度算法,BDP5将由于无可用信道而被丢弃。

　　采用重新调度算法[2]或成组调度算法[6,7,8]可以较好的解决这个问题。下面我们将先简单介绍一下这两种调度算法,然后在分析不合理调度产生原因的基础上，提出一种新的改进算法。

　　2 两类基于LAUC的信道调度算法

　　2.1重新调度算法

　　重新调度算法的主要思想是一个已经调度的BDP可以被重新调度到另一个可用波长上,以容纳新的突发请求。一旦重调度成功,需要发送一个"NOTIFY"消息,通知下一个节点突发数据包改变后的波长,以便其修改该包的入口信道设置[2]。在调度与重调度的每一步，仍然应用LAUC的"最迟可用信道"思想。在文献[2]中提到了一种ABR(Active Burst Re-scheduling)算法,该算法在每个BDP的请求(即与该BDP对应得BHP)到达时,按LAUC方式安排信道,一旦调度成功(安排了某个信道Di).就检查其他信道的最后一个突发包是否可以"移动"到信道Di,当存在多个可能性时,找出其中最新的一个进行重调度。对图1所示情况来说，当BDP4被调度安排到信道D2后，已调度的DBP3符合ABR算法的条件，被重新调度到信道D2，而DBP5将可以被调度到D1，从而降低了丢包率。图2说明了这一重调度过程。

　　ABR算法的优点是提高了数据信道利用率(与LAUC相比)，降低了丢包率：其缺点是由于"朝令夕改",追发的NOTIFY消息增加了控制信道的负担,同时也对核心节点的处理能力提出了更高的要求。文献[2]指出，ABR的计算量近似为LAUC的两倍，但小于LAUC-VF。

　　2.2 成组调度算法

　　文献[6，7，8]分别提出了几种调度算法，虽然其具体实现过程各异,但都存在一个共同之处,即核心节点每次调度都是以一组BHP为单位进行的,在本文中统称之为成组调度算法。文献[8]提出了一种最小间隙组调度(SGGS)算法,该算法的基本思想是核心节点对每个到达的BHP,先不分配信道,而是按其对应的BDP到达时间顺序将其插入一个队列，当队列中的BHP数目达到事先规定的一组控制包应包含的控制包数目N时，再按队列中BHP的排列顺序以LAUC(最小间隙)方式调度安排。这样就保证了BHP在数据信道调度时按突发数据包DBP到达的先后次序被调度,达到合理使用数据信道的目的。

　　SGGS算法不需要额外的控制信息,信道利用率在LAUC算法的基础上有了进一步的提高。增加一组控制包中包含的BHP数目N可以进一步提高其信道利用率,但付出的代价是整个系统偏置时间foffsettime)的普遍增加.因此Ⅳ不能取得很大。其它成组调度算法也存在同样的问题,即在提高信道利用率的同时付出了系统偏置时间延长的代价。

　　3 一种改进的调度算法

　　3.1 不合理调度产生原因分析

　　考虑图3所示的情况。t'、t"分别为突发数据包BDP3和BDP4的到达时刻,l1为BDP4的持续时间,L为所有BDP的最大持续时间,d为BDP3与各数据信道Di的最迟可用时刻(即未调度时间)之间的间隔。由于d1

　　在OBS网络中,由于偏置时间的存在,核心节点处的BHP到达顺序与BDP到达顺序不一致.就会产生上述不合理调度现象。实际上，在"最迟可用信道"思想下,只要一个BDP的到达时刻与某个信道的最迟可用时刻ti之间的间隔di>L,那么一旦后续调度的突发数据包完全在这个间隔内到达,就会产生不合理调度。若一个BHP对应的BDP符合上述条件(即di>L)，我们就称该BHP存在"隐患"。图3中的BDP3对应的BHP就存在"隐患",因为它与信道D2的最迟可用时刻之间的问隔d2>L。当一个存在"隐患"的BHP到达核心节点时,一次不合理的调度就很有可能会发生(究竟能否发生还要视其后到达的BHP所携带的信息而定)。

　　3.2 改进调度算法的提出

　　针对上述情况,我们提出了一种基于LAUC算法的改进调度算法。该算法的核心思想是主动去发现存在不合理"隐患"的BHP.并试图通过等待分析其后的一个BHP所携带的BDP到达情况来出合理的决定。当一个BHP到达后,程序首先判断其是否存在"隐患",若不存在"隐患"，则按LAUC方式调度该BHP,返回程序头部继续分析下一个BHP;若存在"隐患"，则该BHP的调度要视下一个BHP所携带的BDP到达情况而定：要么两个BDP能构成一种更为合理的信道占用情况(形如图2中的BDP3和BDP4),将两个BDP分配到同一信道,视为一次成功的调度,返回程序头部,继续分析处理后续到达的BHP：要么两个BDP不能构成更为合理的信道占用情况,则首先调度先到的BHP，然后分析后到的BHP是否存在"隐患",再重复上述过程。在该算法中,具体分配某个BDP时,按照LAUC的最迟可用信道思想进行。

　　为防止等待时间过长,可设定一个最大等待时间Tmax，当Tmax内无BHP到达时，结束等待,调度当前BHP。由于只须等待一个BHP,该算法的偏置时间延长量与所有成组调度算法相比是最小的。

　　3.3 程序流程图及变量说明

　　图4给出了该算法的程序流程图。相关变量说明如下：

　　M：核心节点到下一个相邻节点的数据信道数目：

　　t'、t"：存放BDF到达时刻的两个变量：

　　l1、l2：存放BDP持续时间的两个变量;

　　ti：各信道的最迟可用时刻，i=1～M;

　　di：BDP到各信道最迟可用时刻的间隔，i=1～M;

　　min1、min2：存放最小间隔的两个变量;

　　c1、c2：存放最小间隔对应的信道编号的两个变量;

　　L：所有BDP的最大持续时间：

　　Lmax：事先设定的等待时间。

　　4 结论

　　在数据信道调度算法中,提高信道利用率和降低计算复杂度是一对不可调和的矛盾。本文提出的改进算法由于采取了主动寻找存在"隐患"BHP的策略,其信道利用率高于LAUC算法及SGGS算法(N=2时),同时能解决一些特定的问题(例如图1所示情况)，降低了丢包率。作为代价,新算法由于增加了在大于零的di中轮询di是否大于L的过程，在最坏的情况下计算量将比LAUC算法多M次(仅就算法的时间复杂度来说，两者都是O(M)，相对LAUC算法而言偏置时间也有所延长。