时隙可变长分组缓存调度算法

杜晓萍，陈名松，王 宁

(桂林电子科技大学光通信研究所，广西 桂林 541004)

为了适应DWDM技术所带来的更高核心节点交换性能需求，全光交换技术应运而生，它不需要进行光电转换，数据交换在光域中完成，除了能提供很高的带宽外，还可以提供高速的数据速率、透明的数据格式和灵活的配置，它也能消除电域所带来的瓶颈[1-2]。然而光分组交换网络存在着分组冲突的问题，在同一时间、同一波长的两个或两个以上的分组需要到达同一个输出端口时，必然会造成分组冲突。在电域中，分组交换中出现的分组冲突可以由随机访问存储器(RAM)解决。但在光域中，光RAM还不成熟，不能应用在光分组交换中。因此，为了解决光分组交换的分组冲突问题，以下几种方法被提出:波长转换、空间上的偏移路由和时间上的光纤缓存。基于光纤延迟线(FDL)的光缓存即为时间上的缓存，目前被广泛地应用于解决分组冲突。但是FDL只能提供固定数量的时延，缓存性能是否能通过使用传统的排队模型准确地获得，还需要考虑符合缓存结构的排队调度算法。分组交换的排队调度算法对分组交换结构的吞吐量、平均时延和分组丢失率等性能指标有着较大的影响[3]，交换调度的设计是整个OPS系统的关键，是对OPS网络性能影响最大的一个环节。缓存调度算法主要功能是根据光分组的信息和节点的状态信息进行资源的调度，从而提供对交换矩阵、FDL的配置，为光分组建立全光的透明通路。目前，支持异步可变长分组的光分组交换的调度算法有很多[4-11]，在文献[8-11]中，主要应用了大量的可变长波长转换器，但可变长波长转换目前仍然难以实现，并且价格也很昂贵。在这些文献中，都没有考虑到利用光线延迟线所带来的固有缺陷，即将当前的缓存资源延缓到下一时刻，占用下一时刻的缓存资源，从而使下一时刻有更加严重的分组丢失率。因此，本文的算法不依靠波长转换器，针对FDLS缓存结构这一不足，提出了一种改进的算法——时隙可变长分组缓存调度算法SVPB(slotted variable-lengthpacket-capable buffer)。

1 输出缓存结构

所提出的算法是依据N×N的通用输出缓存结构设计的，该结构由N个1×N的交换矩阵和N×1的缓存结构，以及一个处理光分组信号的调度控制器组成，该结构能处理异步可变长光分组的交换[12]，如图1所示。

图1 参考的输出缓存型交换结构

当光分组从输入端输入，光分组的分组头信息(目的地址、分组长度等)被提取到调度控制器中进行处理，调度器调度光分组到达目的输出端口输出或缓存器进行缓存。调度控制器处理信息需要一定的时间，所以在输入端增加了提供固定时延的光纤延迟线，延迟的时间等于分组头处理的时间。B×1的缓存器采用B根光纤延迟线组成，每根延迟线的长度为单位长度D(也称为延迟粒度)的整数倍(分别为0，D，2D，…，(B-1)D)，则该缓存器提供0～(B-1)D的离散延迟时间。

2 时隙可变长分组缓存调度算法SVPB

假设上述介绍的结构的输入端口N为4，输入波长为1，延迟深度B为5(D0～D4)。分组到达的情况如图2所示。

图2 分组的到达情况

调度控制器有一个内部调度时钟，周期为T，调度器以周期T为一个时隙来处理到达的分组。在每个时隙里，调度器通过提取到达分组的信息，得到在该时隙中到来的分组数目、各个分组的到达时间和长度，从而根据先到先服务的排队原则确定每个到达分组的处理顺序和延迟时间。

图2的时隙 T0中，有5个光分组(L0，L1，L2，L3和L4)到达(图中白色的分组)，到达的时刻与该时隙的开始时刻时间间隔分别为t0，t1，t2，t3和t4，由于t4＜t2＜t0＜t3＜t1，根据先到先服务的排队原则，调度器安排分组进入FDL的顺序为L4→L2→L0→L3→L1，因此，L4将进入D0延迟线，L2将进入D2，L0将进入D4，如图3所示。

在图3中，各光分组在FDL缓存器中延迟的时间依据分组延迟时间公式得到

图3 分组在FDL的顺序和位置

式中:「x⏋表示取大于等于x的最小正整数;tf表示缓存器所存储的所有分组都离开缓存器，缓存器变为空闲的时刻。当第i个光分组完全离开缓存器时，tf=ti+li+Δi－1D，它将为下一个到达的分组的时延做参考;ti表示第i个分组到达的时刻;则tf－ti等于第i个分组为避免发生冲突所需要的延迟时间。

在FDL缓存器中，进行缓存的连续的两个分组间会产生空隙Vi=ΔiD－tf+ti，空隙的大小不仅与FDL的粒度有关，还与分组的大小和分组到达的时间间隔有关。空隙的产生会导致额外的负荷，在异步操作中，这种空隙是最主要的损失之一。然而，如果所产生的空隙被后面到来的具有合适长度的光分组利用，就可以大大提高FDL缓存器的利用率，降低光分组丢失率，因此，考虑算法时应该把空隙填充考虑进去。由于D4是最大的一根延迟线，剩下的两个分组因为没有可用的延迟线，采用了空隙填充算法，把没有进入延迟线的分组填充到可利用的空隙中，如图中的L3分组。由于L1没有可用的FDL和空隙，所以只能被丢弃。在处理完该时隙到来的所有分组后，开始调度下一个时隙到来的分组。

因此，提出的SVPB算法的步骤如下:

1)在第i个时隙[0，T]内，分组从输入端口n进入交换节点;

2)调度器查看各个输入端口，记录到达分组的情况，用 L(Ti，lj，tj)表示，Ti表示分组在第 i个时隙到达，li为分组的长度，ti为分组到达时距时隙的开始时刻的时间间隔;

3)根据先到先服务的原则，确定分组进入缓存器的顺序;

5)记录随后到达分组的时间间隔ti与第1个到达分组时间间隔tfirst的差值(ti–tfirst)，作为空隙的信息;

6)参看FDL使用情况，如果Δi≤B，表明有可用的FDL，把分组传输到时延最小的可用的FDL上，然后转到步骤2);

7)如果Δi＞B，表明没有可用的FDL，然后比较到达分组的长度li与差值(ti–tfirst)的大小;

8)如果li＜ti–tfirst，分组插入该空隙中，然后转到步骤2);

9)如果li≥ti–tfirst，表明没有可以利用的空隙，分组丢弃，然后转到步骤2);

10)第i个时隙的时间结束，进入下一个时隙(i+1)，重复步骤2)～9)。

3 仿真分析

假设光分组以Poisson过程到达，光分组的长度分布遵从均值为1.0的负指数分布，FDL的粒度和时钟周期也为0.8，输入光纤为6，波长数为1，FDL缓存器的数量为10。下面对SVPB算法的性能进行仿真实验，并与已有的对光分组进行连续处理的空隙填充算法做比较，如图4所示。

图4 SVBP算法与已有空隙填充的分组丢失率

从仿真结果可以看出，在相同条件下，当业务负载较小时，已有的空隙填充调度算法和SVBP算法性能差不多，但当业务负载增大到0.6以上时，SVBP算法与已有的算法相比，能够获得更小的分组丢失率(PLR)。在较大的业务负载情况下(ρ=0.9)，已有调度算法由于无法立即处理发生冲突的分组，将不得不丢弃后面到来的分组，从而导致分组丢失率急剧提高，PLR几乎接近于1。而SVBP算法由于上一时刻的分组处理并不影响现在的分组处理，PLR将趋于平稳。

4 小结

由于FDL缓存器解决竞争冲突的思想是将当前无法解决的情况延缓到下一时刻去解决，从而增加了下一时刻缓存器的负担，即增加了下一时刻缓存器的输入负载，导致下一时刻更加严重的竞争冲突。为了解决FDL缓存器的不足，提出了时隙可变长分组缓存调度算法SVPB，该算法以一个时隙为分组处理单元，在时隙中及时处理这段时间到来的全部分组，解决了FDL缓存器的不足，这种有效性在网络负载较大的时候更加明显。

[1]ZHENGHAO Z，YUANYUAN Y.Prioritized schduling in WDM packet switching networks with limited range wavelength conversion[C]//Proc.IEEE Global Telecommunications Conference.[S.l.]:IEEE Press，2004:1823-1827.

[2]“下一代通信技术和计算机技术对广播电视发展的影响”项目组.下一代网络的发展趋势与业务融合(续一)[J].电视技术，2007，31(8):4-6.

[3]ERAMO V，LISTANTI M，DONATO M D.Performance evaluation of a bufferless optical packet switch with limited-range wavelength converters[J].IEEE Photonics Technology Letters，2004，16(2):644-646.

[4]CALLEGATI F.Optical buffers for variable length packets[J].IEEE Communicatioms Letters，2000，4(9):292-294.

[5]KITAYAMA K I，MURATA M.WDM fiber delay line buffer control for optical packet switching[C]//Proc.Optical Networking and Communications.Imrich Chlamtac:SPIE，2000:247-256.

[6]ALMEIDA R C，PELEGRINI J U，WALDMAN H.Delay-line buffer modeling for asynchronous optical networks[C]//Proc.Optical Networking and Communications.[S.l.]:SPIE，2003:381-391.

[7]HARAI H，MURATA M.Optical fiber-delay-line buffer management in output-buffered photonic packet switch to support service differentation[J].IEEE Journal on Selected Areas in Communications，2006，24(8):108-116.

[8]MURATA M，KITAYAMA K.Ultrafast photonic label switch for asynchronous packets of variable length[C]//Proc.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies.[S.l.]:IEEE Press，2002:371 –380.

[9]CALLEGATI F，CORAZZA G，RAFFAELLI C.Exploitation of DWDM for optical packet switching with quality of service guarantees[J].IEEE J.Selected Areas in Communications，2002，20(1):190-201.

[10]WADA N，HARAI H，HARAI H.Photonic packet routing based on multiwavelength label switching using fiber Bragg gratings[C]//Proc.Optical Transmission Systems and Equipment for WDM Networking.[S.l.]:SPIE，2002:185-198.

[11]ROGIEST W，BRUNEEL H.Exact optimization method for an FDL buffer with variable packet length[J].IEEE Photonics Technology Letters，2010，22(4):242-244.

[12]WADA N，HARAI H.Optical code based photonic packet switch prototype-10 to 40Gbit/s，ultra-high speed，scalable packet switching[C]//Proc.7th IFIP Working Conference on Optical Network Design and Modelling.[S.l.]:IEEE Press，2003:1119-1132.