一种具有信元保序能力的Clos网络分布式调度算法.doc

一种具有信元保序能力的Clos网络分布式调度算法

摘 要 分组交换三级Clos网络信元调度算法可分为集中式和分布式两种实现方式。分布式调度具有良好的可扩展性，适于在高速大容量环境中应用。然而由于分布式调度会带来同一分组各个信元间的乱序问题，给其实现带来困难。本文提出了一种具有信元保序能力的三级Clos网络分布式调度算法。该算法包括第一级的均匀负载分配、中间级的并行调度和第三级的按序输出调度三部分。文中对算法的性能进行了严格理论证明和相关的仿真分析,表明该算法可以很好的解决传统分布式调度中的信元乱序问题，具有良好性价比。
关键词：三级Clos网络；分布式控制；调度算法；信元保序
A Distributed Scheduling Algorithm Maintaining Cells Order
for Three-stage Clos Networks
Abstract: The cell scheduling algorithm for packet switching three-stage Clos networks can be implemented by centralized or distributed controlling scheme. The latter becomes more attractive as the switch becomes larger, because of its good scalability. However, this scheme may cause the cells of a flow mis-sequence, which limits its application. A distributed scheduling algorithm that could maintain cells order is proposed in this paper. It consists of three parts: load-balanced dispatch in the first stage, parallel scheduling in the second stage and scheduling cells in order at an output port in the third stage. The good performance and economy of this algorithm are shown by theoretical and simulation analysis in this paper.
Key Words：three-stage Clos networks; distributed control; scheduling algorithm;
maintaining cells order.

1． 引言
Clos网络[1]由于其模块化性强和良好的可扩展能力，成为实现大容量路由器交换网络的理想选择之一[1,2]。目前对分组交换三级Clos网络结构研究可分为集中式[2~6]和分布式[8]两种。集中式结构又可分为两大类：无缓存（Bufferless）Clos网络和缓存式（Buffered）Clos网络[2]。无缓存Clos网络的三级都采用空分交换结构（3S：Space-Space-Space），不带任何缓存，这种交换结构的好处是交换网络实现简单，但需要一个专门的分组调度（PS：Packet Scheduling）网络和调度算法来完成信息在网络中转发时的路径选择[2~4]。这样会增加网络的实现成本，同时调度算法复杂，实现困难；缓存式Clos网络是在网络的第一级和第三级采用共享缓存方式，中间级采用不带缓存的空分交换方式，这样网络变为一个MSM（Memory-Space-Memory）结构[5,6]，MSM结构需要第一（三）级为共享缓存方式，极大的限制了网络的扩展能力[7]。因此，集中式结构随着网络规模的增加，会带来调度算法复杂性的提高，降低其可扩展能力，同时，不利于网络的分布式实现,提高了其实现难度[7]。为了克服集中式结构的缺点，文献【8】提出了一种分布式调度的三级Clos网络新结构－分布式Clos网络（D-Clos：Distributed Clos）和基于负载均衡的调度思想。采用这种结构和调度思想可以把三级Clos网络中的调度问题分解为第一级的负载均衡和第二（三）级各个交换单元内部调度两个子问题来解决，网络的三级在调度中不需要相互交换控制信息，便于在多机架上实现；同时后两级的调度可以利用现有单Crossbar网络调度算法十分丰富的研究成果[9~14]，使网络具有良好的继承性。然而分布式调度三级Clos网络可能引起同一分组的信元乱序，解决信元乱序问题是分布式调度Clos网络需要解决的重要问题之一[8]。本文提出了一种Clos网络分布式调度算法-负载分配并发式调度算法（LDVSA：Load Dispatched and Volleyed Scheduling Algorithm），该算法在保持分布式调度优点的基础上，可以将信元按照进入交换网络的顺序输出，很好的解决了信元乱序问题。
为了讨论方便，本文假设整个交换网络的输入（出）端口数为N，三级Clos网络第一级为n×n交换单元，单元数为r＝N/n个，中间级交换单元为r×r，个数为n个，第三级交换单元为n×n，个数为r个，用C（n，n，r）来表示该Clos网络* 在本文中假设三级Clos网络第一级为n×n对称结构，只是为了讨论方便，本文算法同样适用所有C（n，K，r）结构。
。分别用IM（i）、CM（k）和OM（j）表示第一级的第i个交换单元，中间级的第k个交换单元和第三级的第j个交换单元。本文讨论采用定长信元交换方式，将按端口速率传输一个信元的时间称为一个时隙（Timeslot）。
2． 算法概述
三级Clos网络分布式调度算法分为三部分，即输入级的负载分配算法，中间级解决输出单元竞争的调度算法以及输出级解决输出端口竞争的调度算法[8]。相应的LDVSA调度算法也包括输入级的完全负载均匀分配算法（FLBDA: Full Load－Balanced Dispatch Algorithm）、中间级的轮询式n－并行（RRnP：Round-Robin based n-Parallel）调度算法和输出级迭代式最老信元顺序输出（iOCOO：iterative Oldest Cell Order Output）调度算法三部分。LDVSA结构如图1所示。在输入级采用输入排队，每个输入端口对到达各个OM的信元独自建立队列，每个队列分为n个子队列，对应IM的n个输出端口（也就是网络的n个中间级）；中间级的RRnP算法是由文献【10】中的K并行调度算法（K-parallel scheduling algorithm）改进得到的。这种算法在一个时隙内对n个中间级采用同样的调度安排。调度算法首先按照轮询方式选择一个CM，然后根据该CM的排队情况进行计算得到本时隙的调度匹配。在每个CM的一个输出端口只需要一个容量为N个信元的缓存就可以将同一分组的各个信元以不乱序的方式送到OM级；原则上讲每个OM采用任何适用于单Crossbar，保证信元FIFO（First In First Out先入先出）的调度算法，都可以保证信元流以不乱序的方式输出。为了实现简单，本文采用由单Crossbar中iOCF(iterative Oldest Cell First)算法[13,14]进行简单修改得到的iOCOO调度算法来解决OM输出端口竞争问题。下面对LDVSA算法的各个部分分别进行讨论。

图1 LDVSA算法示意图
3．输入级完全负载均匀分配算法（FLBDA）
由输入级的队列组织结构可知，一个输入级交换单元的每个输入端口总共有n×r个子队列，称这种队列为VOSQ（Virtual Output Switch Queued虚拟输出交换单元排队）。做以下符号定义：
：表示到达的第个输入端口经过到达的信元在端口的排队队列；
：表示队列的长度，以信元为单位；
：表示在时隙t到达输入端口转发到OM（j）的信元；
由于各个的对称性，用来说明输入级负载分配算法，在不发生混淆的情况下，分别用，和来代替，和。不失一般性，下面选择的第个输入端口来讨论。
定义1 完全负载均匀分配算法（FLBDA） 令集合M＝{k| k=}；，集合Γ＝{}。在时隙t，输入端口和该交换单元的输出端口u相连，。令t＝hn＋s（0≤s<n，h为自然数），如果在时隙hn选择的队头信元输出，那么在时隙t选择的队头信元输出；输入端口将放到队列 中，如果满足以下两个条件之一：（1）在时隙t－1的末端且是M的唯一元素；（2）在时隙t－1的末端，是集合M多个元素中的一个，是按轮询方向最接近u的值，既若，那么。
FLBDA算法简单示意图如图2所示：

图2. FLBDA算法简单示意图
由定义1可以看出，FLBDA算法是将到达信元放到信元数最少的VOSQ，而信元输出是按n个时隙为周期的轮询方式选择，这样有以下引理。
引理1：如果交换网络到达业务是可允许的（admissible）[9]，输入级采用FLBDA算法，那么在时隙t末，当t＝hn（h为正整数）时，对于，有，当t为其它值时，有。
证 明：采用归纳法。假设输入级各个队列在时隙0时都是空的，交换网络从时隙1开始到达信元，信元到达在时隙的开始，离开在时隙末端。用t表示时隙t，当t＝1,...,n时，由于一个时隙内最多到达一个信元，结合FLBDA算法很容易验证引理1成立；设在t＝T＋1，T＋2，..，T＋n时，引理1都成立，下面证明在t＝T＋n＋1时隙，引理1仍然成立。设，任选两个VOSQ队列VOSQ（i，p，j）和VOSQ（i，q，j）进行分析。先证引理前半部分，当T＝（h－1）n－1，那么T＋n＋1＝hn，由假设知，在T＋1时隙末，，因为在T+1到T＋n+1的n个时隙内VOSQ（i，p，j）和VOSQ（i，q，j）两个队列最多各自离开一个信元，而两个队列最多各自到达l个信元，且选择最短队列插入，所以在 T＋n+1，依然成立；再证引理后半部分，如果在时隙T＋n＋1，VOSQ（i，p，j）和VOSQ（i，q，j）都没有信元离开，而信元到达最多一个，还是先选择最短队列，由假设在T＋n时隙末引理1成立，所以在时隙T＋n＋1末，引理1依然成立；如果在时隙T＋n＋1离开的是VOSQ（i，p，j）或VOSQ（i，q，j）的队头信元，不妨假设在时隙T＋n＋1离开的是VOSQ（i，p，j）队头信元。由，令（T＋v）mod n＝0，，由假设在时隙T＋v末，，如果，显然在时隙T＋n＋1末引理1成立；如果，由于在时隙T＋n＋1离开的是VOSQ（i，p，j），如果在时隙T＋v＋1到T＋n＋1，VOSQ（i，q，j）没有信元离开，那么；反之，。综上所证，可以证明引理1。
定义2 队间保序特性 如果对两个FIFO队列的信元从队头到队尾从小到大编号，C1和C2是分属于两个队列的信元，如果C1先于C2到达，那么C1的序号一定不大于C2，称这两个队列具有队间保序特性。
引理2 按照FLBDA分配的任意两个队列VOSQ（i，p，j）和VOSQ（i，q，j）在时隙hn（h为自然数）末，具有队间保序特性。
证明：很显然，VOSQ（i，p，j）和VOSQ（i，q，j）队列都是FIFO队列，采用反证法。由引理1，不失一般性，假设在时隙t＝hn末，（如果两个队列等长可以按同样的方法证明）。设VOSQ（i，p，j）和VOSQ（i，q，j）队列的队尾信元C1和C2在时隙hn末不具有队间保序特性。也就是C1的序号小于C2，但C2先于C1到达。假设C1是在时隙（h－1）n＋v（）到达，那么在C1信元到达的前一个时隙末，；从引理1的证明过程可以看出，的情况仅出现在（h－1）n末，，且在（h－1）n＋1到（h－1）n＋v时隙之间，VOSQ（i，p，j）队列有信元离开，而VOSQ（i，q，j）队列没有信元离开的情况，按照FLBDA分配算法，从时隙（h－1）n＋v到时隙hn，只要VOSQ（i，q，j）队列非空（按假设很显然），肯定要离开一个信元，而VOSQ（i，p，j）不再会有信元离开，所以在时隙hn有，与假设相矛盾。
4．中间级调度算法
中间级交换单元采用带VOQ的输入排队，首先按本单元输出端口组成r个VOQ队列，每一个对应本单元的一个输出端口（同样也对应网络的一个输出交换单元），将一个VOQ进一步分为n个子队列，每一个对应一个输入模块的一个输入端口，称这种队列组织方式为CVIOQ（Combined Virtual Input Output Queued组合虚拟输入输出排队）。用表示从IM（p）的第i个输入端口转发到CM（k），从CM（k）的第j个输出端口输出的信元队列，表示CM（k）的第p个输入端口存放到达CM（k）第j个输出端口信元的队列组。在不发生混淆时，用代替。很显然，输入级的输出信元就是的输入信元，这两个队列相对应。
4.1算法描述和相关性质
定义3 轮询式n并行调度算法（RRnP） 在时隙t，按照轮询的方式，选择一个
CM（k）（k=t mod n），按照CM（k）在该时隙的排队情况计算一个匹配，并将该匹配应用到所有n个中间级交换单元。CM（k）的匹配计算按以下规则：（1）应用适合于K并行的调度算法[10]，计算出一个输入输出端口的匹配；即对于CM（k）,如果，那么先选定，很显然一定非空；（2）在选定的n个子队列中，按以下规则确定一个子队列的队头信元输出：（a）如果存在队列的长度大于1，那么选择该的队头信元；（b）如果不存在满足（a）中条件的i值，因为非空，那么至少存在一个子队列非空，如果非空的子队列是唯一的，选择该队列队头信元；如果非空的子队列有多个，那么需要看其它中间交换单元相应的队列的非空情况，选择其它n－1个CM相对应子队列非空总数最多的一个队头信元；（3）选定各个（p＝1，2，..，n）后，将同样的匹配在本时隙应用到其它的n－1个中间交换单元。
定义4 队间FIFO特性 如果对两个FIFO队列的信元从队头到队尾由小到大编号，按照某种离开规则，分别从两个队列中读取信元，一个队列中序号小的信元离开时隙总不晚于另一个队列中序号比它大的信元离开时隙，那么称这种排队和离开方式具有队间FIFO特性。
根据引理1和引理2以及定义3和定义4可以得出以下推论。
推论 输入级采用FLBDA分配，中间级采用RRnP调度算法的三级Clos网络，中间级的输入排队满足以下特性：对于，和队列的长度最多相差一个，n个（k＝1，..，n）队列和RRnP调度算法具有队间FIFO特性。
证明：因为输入级的输出信元就是的输入信元，由引理1、引理2和定义3、定义4很容易证明推论成立。
引理3 如果在三级Clos网络中，输入级采用FLBDA负载分配算法，中间级采用RRnP调度算法，那么在各个中间级交换单元的每个输出端口只需容量为N个信元的缓存就可以使经过交换网络的信元不乱序地进入到输出级各个交换单元。
证明：如果在CM（k）输出端口j为每个（）队列来的信元各自建立虚拟输入排队（Virtual Input Queued），显然这样的队列共有个。如果对（k=1,…,n）中的信元从队头到队尾按从小到大进行编号，由推论，当中标号为v的信元到达时，其它（）中编号为v－1的信元肯定已经到达，那么编号是v－1的信元可以离开（k＝1，..，n）不乱序的进入到输出级，所以一个只需要一个信元容量的缓存。因此，CM（k）的一个输出端口j需要N个信元容量的缓存。
从引理3的证明过程，可以设计CM（k）第j个输出端口的每个信元输出规则。即只要任一个有第2个信元到达，那么所有非空（k＝1，..，n）中的信元就可以输出到输出级。由于RRnP调度算法由一个调度器来完成所有n个中间级交换单元的调度，所以可以很简单的实现当一个有第2个信元到达时，通知所有的（k＝1，..，n）将缓存腾空。前面讨论了RRnP调度算法对整个交换网络的性能影响，下面重点分析一下RRnP调度算法自身的一些特性。
4.2 RRnP调度算法的性能
为了更好的讨论RRnP算法的性能，首先给出单Crossbar中调度算法的一些定义。
定义5 基于流水线式调度算法[10]（Pipeline－Based Scheduling pPBS） 一个交换网络有p个子调度器，以p个时隙为周期，每一个时隙只有一个子调度器完成调度决定。
在单Crossbar中pPBS一般用在带有VOQ的输入排队中，将一个VOQ中的请求分散到p个子调度器，在每一个时隙，由一个子调度器根据在其中的请求，完成调度决定，各个子调度器轮流进行，这样可以降低对调度时间的要求，使调度器的调度时间从一个时隙变为p个时隙。同时由于各个子调度器之间是相互独立的，可以保持单调度器调度算法的优点，图3示出了3PBS的一般工作原理。

图3 3PBS一般工作原理
一般来讲，所有实用的基于MWM（最大权重匹配）和极大匹配的调度算法都可以采用流水线方式实现，同时能保持原有算法在吞吐量等方面的性能，如DRRM（Dual Round－Robin Matching）[4]、iSLIP[12]、OCF（Oldest Cell First）[13,14]等。
定义6 倍K调度[10]（K-serial Scheduling） 在单Crossbar中，倍K调度是指调度器应用一个匹配连续K次才重新计算下一个匹配。
定义7 K并行匹配[10]（K-parallel Matching） 在K个交换单元中，每一个时隙只由一个交换单元的调度器完成调度决定，并将得到的匹配用到所有K个交换单元。
定义8 调度能力相当 同样输入业务通过两个采用不同调度算法的交换网络，如果在每一个时隙，一个交换网络转发的信元数总不少于另一个交换网络转发的信元数，那么就称这个交换网络的调度能力相当于另一个交换网络。
定理1 采用FLBDA和RRnP调度算法的C（n，n，r）网络的前两级和一个n×n的单Corssbar交换网络，如果三级Clos网络中间级各个交换单元和单Crossbar采用同类的调度算法，单Corssbar是基于流水线nPBS，加速为n的倍n调度，那么这种三级Clos网络前两级的调度能力相当于单Crossbar网络。
证 明：采用nPBS的单Crossbar将每个VOQ的请求采用轮询方式分配到各个子调度器，因为VOQ中每个排队的信元对应一个请求，所以可以等价的看作将VOQ进一步分为n个子队列，每个子调度器根据相应队列的排队情况进行调度，用PVOQ（i，j，p）表示VOQ（i，j）中对应子调度器p的子队列，用来对应PVOQ（i，j，p），因为单Corssbar具有n倍的加速，采用的倍n调度，所以在时隙t如果匹配中包含PVOQ（i，j，p），设PVOQ（i，j，p）中的信元个数为L，那么将会有min{L，n}个信元从PVOQ（i，j，p）队列中转发出去；在三级Clos网络中，由推论，可知的信元被均匀的分到各个（r＝1，..，n）中；又因为RRnP计算匹配的算法和单Crossbar的相同，所以在时隙t，RRnP算法也将选择队列，那么很显然两个交换网络的调度能力相当。
由定理1可以看出，如果将单Crossbar中性价比良好的调度算法，进行简单的修改就可以应用到RRnP中，同时可以保持原有算法在单Crossbar中良好的性价比。在文献【10】中，已经证明很多实用于Crossbar的调度算法，经过简单修改，就可以适用在k并行调度中。同时由于大多数调度算法可以通过流水线方式实现[11]，所以可以找到很多实用于RRnP的调度算法,因此该算法具有良好的继承性。
4.3 RRnP算法的通信开销
图4是RRnP调度器示意图，每一个子调度器和一个中间级交换单元相对应，从图中和定义3可以得出在每个时隙，首先由此时隙被选中的子调度器（称为主调度器）完成匹配计算，并将计算结果通过总线广播给各个子调度器，这需要比特的通信开销，如果需要（定义3规则（b）中情况），每一个子调度器要将已选中各个VOQ中的队列情况上传给

图4 RRNP调度器示意图
本时隙的主调度器，用1个比特表示一个子队列空还是非空，最多需要N个比特，最后再由本时隙的主调度器将最终匹配结果广播给其它的子调度器，需要比特，所以整个RRnP调度器在一个时隙内需要的通信开销为N＋＋比特。如果取N＝64，r＝n＝8，交换网络信元的长度为64个字节，线路速率为10Gb/s，那么通信开销为2.1875Gb/s，采用2.5Gb/s的数据总线就可以满足要求，这在目前技术下完全可以实现。
5． 输出级调度算法
在输出级各个交换单元同样采用带有VOQ的输入排队，每一个输入端口排队分为n个子队列，对应本单元的n个输出端口。iOCOO调度算法是对启发式iOCF调度算法[13,14]进行简单修改得到的。和iOCF一样，iOCOO调度算法以信元在交换单元中排队等待的时间长短来划分信元优先级。在交换单元中等待时间最长的信元称为最老信元（Oldest Cell），在输出端口发生竞争时，优先选择最老信元输出。iOCOO算法和iOCF算法一样分为请求（request）、授权（grant）、接受（accept）和多次迭代四步。iOCOO算法和iOCF算法唯一的区别在于第2步授权。当一个输出端口接收到多个最老信元的请求时，iOCF算法是按轮询的方式来进行选择，而iOCOO算法是按信元到达交换网络的先后顺序来进行选择，这是由iOCOO算法特殊的应用场合所决定的。很显然iOCOO 算法是一种极大匹配调度算法，由于OCOO算法和OCF算法[13,14]思路相同，所以OCOO算法具有和OCF算法同样优秀的性能。另外， iOCOO算法仅在一个交换单元中实施，而交换网络中一个交换单元的端口数比整个交换网络要少的多，这样通信开销不会成为交换网络扩展的瓶颈，所以具有更好的可扩展性。
下面证明iOCOO算法结合FLBDA算法和RRnP算法可以保证进入三级Clos网络的信元以和输入同样的顺序从网络输出。
定理2 采用LDVSA算法调度的三级Clos网络能够保证输入到交换网络的信元以同样的顺序从交换网络输出。
证明：采用LDVSA调度三级Clos网络是指输入级采用FLBDA，中间级采用RRnP，输出级采用iOCOO算法，由推论和RRnP算法信元从中间级到输出级输出的规则可知，在每一个时隙，如果该时隙所有非空（p＝1，..，n）到达OM（j）一个输出端口q的信元为r个（），这r个信元肯定是在同一个时隙到达OM（j）的r个输入端口，按照iOCOO算法它们肯定是按序离开交换网络的，所以从交换网络i端口入到q端口出的信元通过LDVSA算法调度后，可以按和输入同样的顺序输出。
6. LDVSA调度算法性能分析
6.1 理论分析
在文献【8】中说明了在分布式调度三级Clos网络中，研究的重点是第一级负载均衡算法的性能。LDVSA算法是第一级FLBDA负载分配算法、第二级RRnP轮询调度算法和第三级iOCOO算法结合而成。由定理1和前面的算法描述可以得出，RRnP轮询调度算法和iOCOO算法是在单Crossbar相应调度算法的基础上修改而来，保持着原有算法的良好性能，其性能保证的主要前提是要求第一级的负载分配算法可以保证到达它们的业务是允许的。下面讨论FLBDA负载分配算法的性能。
定义表示从交换网络输入端口到达输出端口信息的平均转发流量，为从转发的百分比，称为对的均衡系数。有以下定理：
定理3 在分布式Clos网络中采用FLBDA负载分配算法，如果交换网络的输入业务是允许的，该网络的中间级和第三级各个交换单元的输入业务也是允许的。
证 明：从文献【8】知道，分布式调度Clos网络第一级负载分配算法满足（1）式，就可以保证当交换网络的输入业务是允许的，该网络的中间级和第三级各个交换单元的输入业务也是允许的。
， 且（） （1）
由引理1可以知道，对于，在任何时隙都有：，这说明，都有。否则，如果存在一个有，那么对所有的，都有，那么按照FLBDA的定义和排队系统不稳定的定义，有到达第输入端口转发到的信元个数在每个时隙内都大于1，这样违背了网络到达业务允许的要求，因此是不可能的。同时，由于FLBDA算法对（）队列的输出是按照轮询方式同等对待的，所以各个队列得到信元输出的机会是相同的。这样在FLBDA算法和网络业务到达允许的情况下，有（2）式成立。
， （2）
同时，由网络业务是允许的有：
， （3）
将（2）式和（3）式联合代入（1）式就会得出（1）式成立。这样定理3可证。
6.2 仿真分析
为了进一步说明LDVSA算法的性能,对该算法在OPNET仿真平台下建立仿真模型,对其时延性能进行分析,并将其和CRRD算法[5]以及SLBSA算法[8]进行比较。为了提高仿真的可信度，采用文献【15】的业务模型，将整个网络业务分为：非突发的高度均匀业务、非突发的低度均匀业务、非突发的低度不均匀业务和突发的高度均匀业务、突发的低度均匀业务、突发的低度不均匀业务6种业务类型，仿真结果如图5和图6所示：
图5 突发各种业务下三种不同算法性能对比图 图6 非突发各种业务下三种不同算法性能对比图
从图5和图6可以看出，无论在突发业务还是非突发业务下，LDVSA算法都继承了分布式调度算法的优点，和集中式的CRRD算法相比，在任何网络允许负载下，都是平稳的；而CRRD算法虽然在低负载时可以保证良好的网络性能，但是到了中高负载（负载在0.6～0.7以上）网络性能就会急剧恶化。和分布式SBLSA算法相比，LDVSA算法时延稍大，这是因为在中间级采用k并行调度算法，相当于在单Crossbar中采用流水线方式实现调度，带来了实现的简单，但是会引入一定的时延代价，但是LDVSA算法相对于SLBSA算法节省了网络成本。
从前面的讨论可以看出，LDVSA算法是一种建立在分布式Clos网络结构和负载均衡调度思想基础之上的调度算法，相比与传统的集中式调度算法，具有可扩展性好，调度算法实现简单，可以良好的继承现有单Crossbar交换网络调度算法成果等优点；相对于文献【8】所提出的SLBSA算法，很好的解决了信元乱序问题，不需要在网络输出端口加重排序缓存来进行信元重排序，降低了网络实现成本。
7. 结论
在三级Clos网络中采用分布式调度，可是充分发挥网络良好可扩展性的优势，调度算法实现简单，具有良好的继承性，很适于在高速大容量环境下应用。然而，由于在分布式Clos交换网络结构中，中间级存在缓存会引起属于同一分组的各信元发生乱序问题。乱序问题的存在直接影响了Clos网络分布式调度的应用。本文提出了一种可以很好克服信元乱序问题的三级Clos网络分布式调度算法－LDVSA算法。该算法继承了现有分布式调度算法的优点，不仅可以很好的解决信元乱序问题，同时因为该算法是在本地端口进行队列管理和指针轮询，不需要信息在不同单元的交互，算法实现不需要网络加速，所以不会使网络成本大幅度增加，具有很好的经济性。因此，该算法是一种具有良好性价比的调度算法。
参考文献：
[1] Clos C.. A study of nonblocking switching fabric networks. Bell Systems Technical
Journal,1953,32(5): 406~424
[2] Chao H. J., Jing Zhigang, Liew S. Y.. Matching algorithms for three-Stage
bufferless Clos network switches. IEEE Communication Magazine, 2003,41(10): 46~54
[3] Chao H. J., Liew S. Y., Jing Zhigang. A dual-level matching algorithm for 3-stage Clos-network packet switches. In: Proceedings of the 11th symposium on high performance interconnects, Stanford University, 2003, 38-43
[4]ChaoH.J..Saturn: a terabit switch using dual round robin. IEEE Communication Magazine, 2000,38(12):78~84
[5] Oki E., Jing Z., Rojas-Cessa R., Chao H. J.. Concurrent round-robin-based dispatching schemes for Clos-network switches. IEEE/ACM Transaction Networking, 2002,10(6):830-844
[6] Pun K., Hamdi M.. Distro: a distributed static round-robin scheduling algorithm for bufferless Clos-network switches. In: Proceedings of the IEEE Globecom, Taipei, Taiwan,2002, 2298-2302
[7] Isaac Keslassy, Chuang S.T., et al. Scaling internet Routers using optics. Computer Communication Review, 2003,33(4): 189-200
[8] YANG Jun-Gang, QIU Zhi-Liang, LIU Zeng-Ji, et al. Study on distributed scheduling algorithm in three-stage Clos networks. Tien Tzu Hsueh Pao/Acta Electronica Sinica, 2006,34(4):590-595 (in Chinese)
(杨君刚，邱智亮，刘增基 等. 三级Clos网络中分布式调度算法研究. 电子学报，2006,34(4):590-595)
[9] Dai J.G., prabhakar B.. The throughput of data switches with and without speedup.In: Proceedings of the IEEE INFOCOM, TelAviv,Israel,2000: 556-564
[10]Mneimneh S.,Sharma V., Siu Kai-yeung. Switching using parallel input-output queued switches with no speedup. IEEE/ACM Transaction on Networking,2002,10(5):653~665
[11] Oki Eiji, Roberto Rojas-Cessa, chao H.J.. A pinpline-based approach for maximal-sized matching scheduling in input-buffered switches.IEEE Communication Letters,2001,5(6):263~265
[12] McKeown N.. iSLIP: a scheduling algorithm for input-queued switches. IEEE Transaction on Networking, 1999,7(2): 188-201
[13] Mckeown N.. Scheduling algorithms for input-queued cell switches[D]. Berkeley ,USA: University of California,1995
[14] Charmy A.. Providing QoS guarantees in input buffered crossbar switches with speedup [D].Massachusettes USA: Massachusettes Institute of Technology(MIT) , 1998
[15] Goudreau M. W., et al. Scheduling algorithms for input-queued switches: randomized techniques and experimental evaluation. In: Proceedings of the IEEE INFOCOM, TelAviv,Israel,2000，1624-1643

This work is supported in part by National 863 High-tech Research Development Program of China under grant No.2002AA103062, the Open Subject Program of National Key Lab of Integrated Service Network under grant No.ISN8-03, the Research Funding Subject of Zhong-Xing Corporation under grant No. ZXJS200609120159.
Switching fabric is the key element of a Router or Switch. It functioned as forwarding the cells from input port to correctly output port according their address. The performance of the switching fabric plays a very important role in the performance of Router or Switch.
The scheduling scheme is critical in a switching fabric,