Fair scheduling in input-queued switches under inadmissible traffic

In recent years, several high-throughput low-delay scheduling algorithms have been designed for input-queued (IQ) switches, assuming admissible traffic. In this paper, we focus on queueing systems that violate admissibility criteria. We show that in a single-server system with multiple queues, the longest queue first (LQF) policy disallows a fair allocation of service rates. We also describe the duality shared by LQF’s rate allocation and a fair rate allocation. In general, we demonstrate that the rate allocation performed by the maximum weight matching (MWM) scheduling algorithm in overloaded IQ switches is unfair. We attribute this to the lack of coordination between admission control and scheduling, and propose fair scheduling algorithms that minimize delay for nonoverloaded queues.