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

分组交换三级Clos网络信元调度算法可分为集中式和分布式两种实现方式.分布式调度具有良好的可扩展性,适于在高速大容量环境中应用.然而由于分布式调度会带来同一分组各个信元间的乱序问题,给其实现带来困难.该文提出了一种具有信元保序能力的三级Clos网络分布式调度算法.该算法包括第一级的均匀负载分配、中间级的并行调度和第三级的按序输出调度三部分.文中对算法的性能进行了严格的理论证明和相关的仿真分析,表明该算法可以很好地解决传统分布式调度中的信元乱序问题,具有良好的性价比.

A Distributed Scheduling Algorithm Maintaining Cells Order for Three-Stage Clos Networks

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.