Evaluating Scheduling Algorithms for Packet Switches with Multiple Input Queues by Simulation

摘要

Input-queued switches are being used increasingly for high-bandwidth switches and routers. In previous studies, several centralized and distributed scheduling algorithms for such switches have been proposed. The performance of these algorithms was evaluated in terms of throughput. While all of the previously proposed algorithms report a 100% throughput, this alone does not inform us how the algorithms compare against each other. For example, it is desirable that the high throughput is achieved without the cost of a high waiting time for a packet. In this paper, we simulate several of the previously proposed scheduling algorithms, using the same traffic pattern, to evaluate how they perform in terms of average wait-time, average queue occupancy, throughput and fairness. We also propose a variation on the adaptive round robin scheduling algorithm. Simulation results show that our variation improves the performance with respect to wait time, queue occupancy and throughput. From these findings, we propose future research directions for scheduling algorithms.