How fair is fair queuing

Abstract. 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 disciphne 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 possibihty 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 ‘Lfam share ” of serwce. In this paper, we consider two variants of the fair queuing discipline, and rigorously establish their fairness wa sample path comparisons with the head-of-line processor sharing disclphne, a mathematical idealization that prowdes 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.