ATM缓冲排队优化-反法西斯战争时期的中国与世界研究

7．3．1　ATM缓冲排队

ATM信元交换是将信元从一个VP/VC交换到另一个VP/VC上。ATM信元在传输交换时，各路信元载到链路上的方式是统计复用的，各虚连接的信元会竞争交换介质等资源。一般地，信元竞争主要有两种情况：出线竞争和内部竞争。出线竞争是指两个或两个以上的信元同时交换到同一个输出端口，内部竞争是指两个或两个以上的信元同时争用交换网络的内部链路。内部竞争有的网络可以消除，如CLOS网络、BANYAN网络等，而出线竞争只能设置排队缓冲来解决。为了解决出线竞争，减少信元丢失，必须对各信元进行排队，在时间上将它们分开。排队方式有五种，分别是内部排队、输入排队、输出排队、输入输出排队及环回排队。图7．13（a）、（b）、（c）、（d）所示为除了内部排队以外的四种排队方式。

图7．13　ATM信元常用排队方式

1．输入缓冲排队

输入排队是在交换网络的每个输入端口（入线）上设置缓冲器，如图7．13（a）所示。每个缓冲器一般采用先进先出（First－in First－out，FIFO）的排队规则。多输入线上的信元，若同时要交换到相同的出线上，即可出现出线竞争，此时，竞争成功的信元通过交换网络传送到相应的出线，竞争失败的信元暂时留在输入缓冲器中，等待下一轮信元的传送。

输入排队对存储器速率要求低，实现简单，但是如果队列头的信元不能通过交换网络时，其后所有的信元会被延迟，使输出效率很低。为了解决输出效率低的问题，对FIFO排队规则进行改进，改进的方法有很多种，窗口方法是一种常用的方法，如图7．14（a）所示。由图可见，窗口方法在每个输入缓冲器设定一个宽度为W的窗口，即在一个时隙内每个输入队列可以有W个信元参与出线竞争。一个时隙可划分为两个时间片，即竞争仲裁时间与信元传送时间，其中竞争仲裁时间又可进一步划分为W个子区间，如图7．14（b）所示。在第一个子区间，所有输入队列的排头信元进行出线竞争，若有占用的出线则在第二个子区间进行第二次出线竞争，以此类推，直到所有的窗口已经用尽或出线均被占用。

(www.xing528.com)

图7．14　采用窗口方法的输入排队及时隙结构

2．输出缓冲排队

输出缓冲是在交换网络的每个输出端口（出线）上设置缓冲器，如图7．13（b）所示。所有来自不同输入端口的信元同时送到交换网络进行交换，当出现出线竞争时，由输出端口进行信元的缓冲。输出排队中若有X个信元发往同一目的地址，则将有X－1个信元滞留在输出队列中等待传送，如果队列溢出，就会发生信元丢失现象。为了尽量减少信元丢失，要求缓存处理速度和存储器的存取速度要高。

3．输入输出缓冲排队

输入缓冲对处理速度和存储器的存取速度没有过高的要求；输出缓冲对处理速度和存储器的存取速度有较高的要求。输入输出缓冲综合了输入缓冲与输出缓冲的优点，如图7．13（c）所示。假设输出缓冲器在一个信元时隙内最多能接收X个信元，而在某一时隙内超过X个信元就要交换到同一个端口，那么这些超过的信元将会被存储在输入缓冲器中，而不像输出缓冲方式那样把它们丢弃。

4．环回缓冲排队

环回缓冲除了包括输入端口与输出端口外，还包括被称为环回端口的一些特殊端口以及环回缓冲器，如图7．13（d）所示。环回排队方式让那些在竞争中失败的信元通过环回端口存储在环回缓冲器中，在下一时隙与新来的信元重新进行竞争。但环回的信元会引起信元失序的问题，为了解决这个问题，信元在进入交换网络时要赋予一个优级标识。当竞争失败的信元进入环回时，其优先级标识数值会自动加l，这就保证了环回缓冲中的信元有较高的优先级，在下一轮的竞争中优先放行。环回缓存器具有较高的吞吐率、较低的信元丢失率，但时延大，且交换结构复杂。