HOW FAIR IS FAIR QUEUING

Fair Queuing is a novel queuing discipline with important applications to data networks that support variable-size packets and to systems where the cost of preempting jobs from service is high. The discipline controls a single server shared by N job arrival streams with each stream allotted a separate queue. After every job completion, the server is assigned to serve, without possibility of interruption, the job at the head of one of the queues (as soon as at least one job appears in the system). Fair Queuing is designed to handle arbitrary job arrival sequences with essentially no a priori knowledge of their attributes, such that each stream receives its "fair share" of service. In this paper, we consider two variants of the fair queuing discipline, and rigorously establish their fairness via sample path comparisons with the head-of-line processor sharing discipline, a mathematical idealization that provides a fairness paradigm. An efficient implementation of one of the fair queuing disciplines is presented. In passing, a new, fast method for simulating processor sharing is derived. Simulation results are presented to further explore the comparison between fair queuing and processor sharing.