2002 · 512 citations · 18 references
BusinessComputer EngineeringComputer ScienceAlgorithmsQueuing TheorySchedulingQueue ManagementQueueing AnalysisQueueing NetworksQueueing ProcessesQueueing SystemsQueueing TheoryInput QueueingInput-queued SwitchingLyapunov FunctionsQueue OccupancyQueueing Control PoliciesQueueing-based Scheduling
Head‑of‑line blocking limits input‑queued switch throughput to about 58 % under FIFO, but non‑FIFO policies can increase throughput; achieving 100 % throughput for all independent arrival processes had not been shown. The paper proves that a suitable queueing policy and scheduling algorithm can achieve 100 % throughput for all independent arrival processes. The authors use a linear‑programming argument and quadratic Lyapunov function, assuming each input maintains a separate FIFO queue per output and scheduling with a maximum‑weight bipartite matching algorithm.
It is well known that head-of-line (HOL) blocking limits the throughput of an input-queued switch with FIFO queues. Under certain conditions, the throughput can be shown to be limited to approximately 58%. It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used then it is possible to achieve 100% throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm.
18
High-speed switch scheduling for local-area networks
Thomas E. Anderson, Susan Owicki, James B. Saxe et al. · ACM Transactions on Computer Systems · 1993 · 896 citations · Full text