A Survey of Queuing and Scheduling Mechanism of Input-Queued Switches

Abstract

High-speed routers play an important role in the Internet. A main hindrance to high-speed router design is itsswitch architecture. It concerns with how packets are moved from switch input ports to output ports. The switcharchitecture can be classified as Output-Queued and Input-Queued switches. It is well known that Output-Queued switches can achieve optimal delay-throughput performance. Output-queued switches are generallyimpractical for high-speed implementation because of high speed needed for both switch fabric and output portbuffers. Input-queued switch architecture becomes the alternative since it needs no (or little) speedup. Inputqueuing is becoming increasingly used for high bandwidth switches and routers. In an input-queued switch,each input port can send at most one packet and each output port can at most receive one packet in each timeslot. In VOQ each input port maintains a separate queue for each output port. It has been shown that VOQ canachieve 100% throughput performance with an effective scheduling algorithm. It addresses a common problemknown as Head-Of-Line (HOL) blocking. The scheduling problem is equivalent to the matching problem in abipartite graph.Keywords: Scheduling, Queuing, Matching, Bipartite, Switch-fabric