新闻中心

EEPW首页 > 测试测量 > 设计应用 > 一种改进的光突发交换数据信道调度算法

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

——
作者:时间:2007-12-27来源:收藏

  1 引言

  在()网络中,控制分组(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

  在网络中,由于偏置时间的存在,核心节点处的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算法而言偏置时间也有所延长。



评论


相关推荐

技术专区

关闭