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 不合理调度产生原因分析

　　t'、t"分别为突发数据包bdp3和bdp4的到达时刻,l1为bdp4的持续时间,l为所有bdp的最大持续时间,d为bdp3与各数据信道di的最迟可用时刻(即未调度时间)之间的间隔。由于d1<d2，按照最小间隙原则，bdp3被调度到信道d1。当下一个bhp对应的突发数据包bdp4完全在间隔d2内到达时,bdp4将被调度到信道d2。这时我们发现bdp3与bdp4的间隔更小一些(t'-t"-l2<min),若能将bdp3也调度安排到信道d2,位于bdp4之后,信道使用会更为合理。因此现在看来,前次对bdp3所做的调度就是一次不合理的调度。

　　在obs网络中,由于偏置时间的存在,核心节点处的bhp到达顺序与bdp到达顺序不一致．就会产生上述不合理调度现象。实际上，在"最迟可用信道"思想下,只要一个bdp的到达时刻与某个信道的最迟可用时刻ti之间的间隔di>l,那么一旦后续调度的突发数据包完全在这个间隔内到达,就会产生不合理调度。若一个bhp对应的bdp符合上述条件(即di>l)，我们就称该bhp存在"隐患"。图3中的bdp3对应的bhp就存在"隐患",因为它与信