Chinese Journal of Computers   Full Text
Title	A Distributed Scheduling Algorithm Maintaining Cells Order for Three-Stage Clos Networks
Authors	YANG Jun-Gang1),2) BAO Min-Quan1) LIU Zeng-Ji1) QIU Zhi-Liang1) ZHAO Rui-Qin1) SHI Zeng-Zeng1)
Address	1)(National Key Laboratory of Integrated Service Networks, Xidian University, Xi’an 710071) 2)(Xi’an Communication Institute, Xi’an 710106)
Year	2008
Issue	No.3(467—475)
Abstract &   Background	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. keywords three-stage Clos networks; distributed control; scheduling algorithm; maintaining cells order background This work is supported in part by the National High Technology Research and Development Program (863 Program) of China under grant No.2002AA103062, the Open Subject Program of National Key Laboratory 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, it is used to avoid competition for one output port. Clos network is a famous switching fabric, it possesses many merits such as good scalability, favorable network performance, etc. So the scheduling scheme in Clos network is a research hotspot. However, the scheduling schemes used in current Clos networks are of high complexity and can’t guarantee the networks performance. A distributed scheduling scheme is proposed to solve the above problems. Because the buffer is allocated at the central stage, the cells belong to the same packet through different central stages may suffer diverse queued delay, which cause the out-of-sequence of the cells. The mis-sequence is a serious problem faced by the distributed scheduling scheme. The main objective of this paper is to solve the out-of-sequence problem. In this paper, a distributed scheduling algorithm that could maintain cells order is proposed. Theoretical analysis proves that the algorithm is capable of maintaining the cells order correctly. The good performance and economy of this algorithm are also shown by theoretical and simulation analysis in this paper.