Fair scheduling for input-queued crossbar switches

To keep up with the fast growing demand of high bandwidth, current high performance routers and switches employ crossbar as switch fabric because a crossbar can transfer multiple packets simultaneously, and it is simple and easy to implement in hardware. However, because of both input and output contentions, output queuing is prohibitively difficult. Therefore input queuing is unanimously adopted in high performance routers/switches.; On the other hand, quality of service (QoS) becomes more and more important. Fair scheduling is deployed at outputs of a router or switch with an implied assumption of output queuing. With an input-queued (IQ) switch, such a QoS approach may not be effective. In this thesis, we address the problem of how to provide fair bandwidth sharing to best-effort traffic in an IQ crossbar switch.; To start with, we propose a heuristic called iterative deficit round-robin (iDRR) algorithm. Simulations show that it achieves high throughput for uniform traffic and provides fair sharing among competing flows under some situations. Next we study the fair scheduling problem in depth. We find that it is impossible to maximize throughput and maintain strict fairness at the same time, even in the case of admissible traffic. In addition, to maintain fairness without unnecessarily wasting bandwidth, a max-min fairness criterion should be used in a crossbar switch. Based on these two important observations, we describe a largest virtual waiting time first (LVWTF) algorithm which provides 100% throughput for admissible traffic and enforces max-min fairness for non-admissible traffic.; However, LVWTF is too complicated to implement in hardware. To deal with this complexity issue, we resort to a buffered crossbar, where a small buffer is put at each crosspoint. These crosspoint buffers separate the input and output contentions and make the crossbar scheduling much simpler than that in a non-buffered crossbar. We first propose a shortest crosspoint buffer first (SCBF) algorithm, and prove that it achieves 100% throughput for any admissible traffic. Finally, we present an adaptive max-min fair scheduling (AMFS) algorithm with O (log N) complexity. By introducing a dynamic max-min fairness criterion which implies 100% throughput for admissible traffic and max-min fairness for partially and fully overloaded traffic, we prove that AMFS is fair.