第3章-ATM交换机构控制机理

1第3章ATM交换控制机理2为使ATM交换结构能完成正常的信元交换和其它一些必要的功能，以及能达到一定的服务性能指标的要求，ATM交换结构必须具备相应的控制机理。本节将介绍ATM交换结构的控制机理，包括缓冲策略、竞争消除、反压控制、选路方式、多播实现和队列管理。34.1缓冲策略1缓冲策略的分类缓冲策略(bufferingstrategies)或称为排队策略(queueingstrategies)，是ATM交换结构设计中的重要内容，对ATM交换结构的性能指标具有重要的影响。从广义来说，缓冲策略包括缓冲器设置方式、缓冲器的数量、队列的存取控制、以及缓冲器的管理。缓冲器设置方式简称为缓冲方式，是缓冲策略中首先要解决的基本问题。4缓冲方式可分为外部缓冲和内部缓冲两大类。外部缓冲(externalbuffering)是指缓冲器设置在交换结构的外部．内部缓冲(internalbuffering)则是指缓冲器设置在交换结构的内部。由于外部缓冲方式中的缓冲器不是在交换结构的内部．因而通常是没有内部竞争的无阻塞网络才采用外部缓冲方式。对于具有内部竞争的网络，则通常采用内部缓冲方式。外部缓冲主要有输入缓冲、输出缓冲、输入与输出缓冲、环回缓冲等4种方式。内部缓冲可有交叉点缓冲、共享缓冲以及输入或／和输出缓冲等方式。5图1外部缓冲方式6图2内部缓冲方式72.排头阻塞现象输入缓冲存在排头阻塞(Headoflineblocking一HoLBlocking)现象。所谓HOL阻塞，是指在发生出线竞争时，排在竞争中失败的信元(处于排头位置)之后的去向空闲出线的信元也不能传送的现象。8由于HOL阻塞，会使出线的传送效率降低。这里用吞吐率(throughput)来表征信元通过的效率，可理解为在1个时隙内平均每条出线传送的信元数。显然，吞吐率最大为1。分析表明，在随机的均匀业务流模型下，当入线数N很大时，采用FIFO规则的输入缓冲方式的吞吐率为0.5860。93．输入缓冲方式提高吞吐率的方法为了提高输入缓冲方式的吞吐率，可以对输入缓冲器的队列设置和排队规则加以改进，当然这会不同程度地带来硬件和控制的复杂性。以下介绍几种改进方式。(1)窗口(window)方法每个输入缓冲器规定一定的窗口宽度W，使得在一个时隙内每个输入队列可以有W个信元依次参与出线竞争。为了判别出线竞争与控制调度，一个时隙应划分为竞争仲裁与信元传送时间，采用窗口方法时，竞争仲裁时间应划分为W个子区间。在第1个子区间，对所有输入队列的排头信元进行出线竞争；在第2个子区间，由第1次竞争失败的信元所在的各个输入队列中排在第2位的信元，对尚未占用的出线进行第2次出线竞争；以此类推，直到所有出线均被占用或窗口已尽为止。10图3时隙结构11(2)输入扩展所谓输入扩展，就是将每条输入线在进入交换结构之前扩展为S个端口，使得原为n×n的交换网络成为ns×n的交换网络。这样，每个输入队列可有S个信元参与出线竞争。当扩展度S等于窗口方法中的窗口宽度W，可望具有更高的吞吐率，因为输入扩展方法可使得输入队列在同一时隙内传送多于1个的信元。12(3)加速方法如果使交换结构工作速度和输出端口传送速率均为输入端口速度的V倍，则在同一时隙内，输出端口可传送多于1个的信元，从而提高了吞吐率。如输出端口速率等于输入端口速率而不提高，则还应在输出端口处加FIFO缓冲器。13(4)多重队列每条输入线可以设置多个缓冲器队列，例如可有以下几种方式：①奇偶队列每条输入线设置2个FIFO队列；1个称为奇队列，存放目的出线号码为奇数的信元；另1个称为偶队列，存放目的出线号码为偶数的信元。每个时隙的竞争仲裁分为2个子区间，在第1个子区间里，对各条入线的偶队列的队首信元作出线竞争仲裁，在第2个子区间里，对在偶队列出线竟争中失败的入线的奇队列队首信元再作竞争仲裁。每条入线有2次竞争机会，增加了吞吐率。14②W重队列每条入线设置W个FIFO队列，W相当于窗口方法的窗口宽度，所以也可以看成是一种窗口方法。在子区间i，1≤i≤W，对各条入线的第i个队列的队首信元作出线竞争的解析。每个时隙可从N×W个HOL信元中选择最多为N个不同目的出线号码的信元，N为网络入(出)线数。每个输入在每个时隙最多发送1个信元。15③N重队列N重队列输入缓冲方式是在每条入线设置N个FIFO队列，每个队列对应于1个输出端口。这样，对于N×N的交换结构，要有N2个输入队列。在每个时隙，每个入端仍只能传送1个信元，但可以按照最有利于提高吞吐率的方法来选择哪一个队列的信元。显然，这种方式时处理速度要求更高，可以借助于神经网络的控制。分析表明，在神经网络控制下，当N较大时，吞吐率可接近于1。164.输出缓冲为了解决出线竞争，一个理想的采用输出缓冲的无阻塞交换结构最好使得每个出端能够同时接收所有入端发来的信元。这就是说，当入线数为N，考虑到最不利情况，每个出端在一个时隙中最多应可接收N个信元。要做到这一点，就要提高处理速度和存储器的访问速度，于是引入了加速因子(speed-factor)的概念。应该注意的是、尽管在同一时隙可能有多个信元进入同一出端的缓冲器中，但出端的速率仍保持不变，每个时隙只向外发送1个信元。17加速因子等于N时，完全消除了出线竞争，吞吐率可为1，但对速率的要求较高。为此，可使加速因子小于N，例如等于k：1＜k＜N。这样，每一出端同时最多只能接收k个信元；如果有多于k个信元去向同一端口，就要按一定准则选取其中的k个信元，其余的信元就将丢弃。应选择合适的k值，以保持较好的性能。输出缓冲方式不存在HOL阻塞现象，在合适的加速因子取值下，可以得到高吞吐率和良好的性能。185.输入与输出缓冲前已述及，采用单纯的输出缓冲时，如果加速因子小于N，会发生信元丢失。如果同时在入端也设置缓冲器，在发生出线竞争时，受加速因子限制而不能同时传送到出端缓冲器的信元可以暂时保存在入端缓冲器中，从而避免了信元的丢失，这就是输入与输出缓冲方式。入端缓冲器的容量并不需要太大。196).环回缓冲环回缓冲(recirculationbuffering)是使竞争中失败的信元能通过环回缓冲器回送到入端，再与新到来的信元一起进行下一轮的竞争。环回缓冲的交换结构可以具有较高的吞吐率和较低的信元丢失率，但交换结构要增加用于环回的端口，环回还会使得属于同一虚连接的信元失序，时延也较大。环回缓冲还可与输出缓冲结合使用。207.交叉点缓冲交叉点缓冲(crosspointbuffering)是在交换结构中的每个交叉点设置缓冲器。交叉点缓冲的SE可以用作单级网络或多级网络内部的交换单元(SE)。用作单级网络时，由于单级网络不存在内部阻塞，因此交叉点缓冲实际上是解决出线竞争问题；用作多级网络中的SE时，除了最末一级SE以外，都是针对内部竞争问题。218.共享缓冲共享缓冲相当于共享存储器的时分结构，可作为单级结构，也可用作多级结构中的交换单元(SE)。共享缓冲是一种内部缓冲方式，由所有输入和输出端口共享缓冲区。为便于信元的调度和输出。在共享缓冲区内是按各个输出端排队，也就是每个输出端有一个队列，当信元输入时，按信元的目的出端号码写入相应的输出队列，排队等待调度。各个输出队列为逻辑队列，队列中各个信元的存储地址在物理位置上并不连续，而是用地址链的方法。229.多级网络的内部缓冲内部缓冲(internalbuffering)是将缓冲器设置在交换结构的内部。无阻塞多级结构不需要内部缓冲。对于多级有阻塞网络而言．采用内部缓冲就是构成MIN的各个SE中含有缓冲器。有阻塞多级网络内部的缓冲器主要用来暂存在内部竞争中失败的信元，最后一级的内部缓冲则用于出线竞争中失败信元的暂存。23采用内部缓冲的多级有阻塞网络可以减少信元丢失，但是也有两个主要缺点：一个是增加信元的时延和时延抖动，这是因为每级缓冲会引入不确定的排队时延，另一个是对于多通路网络，如果属于同一虚连接的信元在交换结构中可以选用不同的通路(内部无连接选路)，则会发生信元失序现象，这是因为不同通路的排队时延不同。244.2竞争消除1.竞争消除的基本功能与分类ATM交换结构从是否存在内部竞争来划分．可以分为无阻塞结构和有阻塞结构，不论是否存在内部竞争，总是存在出线竞争。因此，为了解决竞争问题以将信元丢失率降低到可以接受的范围，ATM交换结构必须具有竞争消除的控制机理。竞争消除的方法对交换结构或交换单元硬件的复杂性和服务质量均有重要的影响。25竞争消除(contentionresolution)机理的基本功能是检出多个信元在同一时刻对交换结构内部资源(如级间链路)或对出线的争抢，从而按一定策略挑选竞争的优胜者，对竞争中失败的信元作出适当的处理，并尽可能采用减少竞争而提高吞吐率的信元调度算法。竞争消除在信元传送阶段高速执行，应由硬件实现。26不同的交换结构和缓冲方式可有不同的竞争消除机理，对同一交换结构也可能采用不同的竞争解决方法。事实上已出现了多种消除竞争的控制机理。这里从技术特征的角度，较全面地将这些不同的方法进行分类，如图所示。这些方法分成4大类：ACK/NACK．偏转／环回，时隙预留和加速／并行。27图4竞争消除分类282.基于ACK／NACK的外部仲裁基于ACK／NACK方法的特点是在竞争解决中要向参与竞争的输入端口发送证实(ACK)或负证实(NACK)信号。这一类型又可分为两个子类：外部仲裁和网络仲裁。1)外部仲裁主要用于具有输入缓冲的无阻塞空分交换结构。顾名思义，外部仲裁就是专门设置外部仲裁器。ACK／NACK信号不通过交换网络而在外部传送。基于ACK／NACK的外部仲裁又可分为HOL信元仲裁、多重队列仲裁和窗口仲裁等方法。29(1)HOL信元仲裁在交换网络外部设置了仲裁器(arbitrator)。各个输入端口控制器在每个时隙开始要将排头(HOL)信元的目的地址作为请求发送给仲裁器，由仲裁器按预定策略选择优胜者，并向相应输入端口回送控制信号(ACK信号)。收到ACK信号的输入端口可将HOL信元发送，而未收到ACK信号(或收到NACK信号)而在竞争中失败的输入端口的HOL信元，将留在输入缓冲器以等待参与下一个时隙的选路和竞争。从多个竞争的信元中挑选优胜者的策略可有多种，包括随机(random)选择、循环(cyclic或roundrobin)选择、最长队列选择、最长等待时间选择以及按优先级(priority)选择。30(2)多重队列仲裁N重队列的竞争消除。此时，每条入线设置N个输入队列，对于N×N交换结构，将有N2个队列。对N重队列的仲裁就要考察每条入线的N个队列的HOL信元。由于每个队列对应于不同的出线地址，这就消除了HOL阻塞现象，提高了吞吐率。但是、在竞争消除的控制逻辑上如果将时隙分为N个子区间，对N个队列进行顺序操作，对硬件速度的要求将大大提高。为此，可采用并行处理的流水线(pipeline)操作方法。一种称为RC-BB的交换结构就采用N重队列和流水线并行仲裁的方法。31图5RC-BB结构32(3)窗口仲裁窗口仲裁基本方法是顺序字仲裁，就是在规定的窗口宽度内，依次对各个输入队列中处于窗口中同一位置序列的信元进行竞争仲裁，直到每个输入队列可有1个信元在竞争中获胜或窗口结束为止。显然，在窗口某个位置上的竞争仲裁只能针对当前尚未被占用的出线进行。由于窗口每个位置上的竞争仲裁是按照既定策略孤立地进行，顺序仲裁不能获得最佳的信元调度方案，而且由于每个时隙要分成多个子区间，对速度要求较高。33窗口整体仲裁整体仲裁是对窗口范围内的所有信元作通盘考察，力求获得最佳的信元调度方案和最高的吞吐率。为进行高速的并行分布式处理，要借助于神经网络(NeuralNetwork-NN)的控制。343.基于ACK／NACK的网络仲裁所谓网络仲裁，是指竞争的消除与网络本身的结构相关联，ACK／NACK信号要通过交换网络来传送。如果交换结构用的是排序-选路网络，例如B-B网络，可以