On the Efficient Implementation of Fair Queueing

                          Srinivasan Keshav
            Computer Science Division, Department of EECS,
                 University of California, Berkeley,
                          Berkeley, CA 94720
                   email: keshav@tenet.berkeley.edu





                               ABSTRACT
The performance of packet switched data networks is greatly influenced
by  the  queue service discipline in routers and switches. In particu-
lar, the Fair Queueing discipline [1] has several advantages over  the
traditional  first-come-first-served  discipline.  This  paper studies
data structures and algorithms for  the  efficient  implementation  of
Fair Queueing. We present novel performance evaluation methodology and
use it to evaluate the relative merits of several  alternative  imple-
mentations.