Switch scheduling based on round robin algorithms
Tony T. Lee, Man-Ting Choy · 2006
The input-queued switch architecture is widely used in Internet routers, due to its ability to run at very high speeds. A central problem in designing an input-queued switch is choosing the scheduling algorithm, i.e. deciding which packets to transfer from input ports to output ports in a given timeslot. Recent research in packet switch scheduling algorithms has moved beyond throughput maximization to quality of service (QoS) control. Recently, the Birkhoff-von Neumann (BvN) switch has become a typical model for providing QoS in input-queued switch. The major idea is to consider a set of predetermined permutation matrices as independent flows, and the scheduling problem in the input-queued switch can be simply handled by single-server scheduling algorithms, such as weighted fair queueing (WFQ). However, a number of problems are observed. Firstly, although WFQ is a fair algorithm, it has a poor delay performance that depends on the port counts. Secondly, the BvN switch does not perform well under certain traffic requirement, thus unable to provide tight performance guarantees. In this thesis, a set of admission control strategies and scheduling algorithms are therefore developed to improve the QoS performance.