Hierarchical Fair Queueing

David Hogan
[email protected]

Basser Department of Computer Science
University of Sydney

ABSTRACT

In this paper, we present a new queueing algorithm for networks, called Hierarchi?
cal Fair Queueing (HFQ). This shares the bandwidth between classes of users, and (within each class) between subclasses. HFQ provides a guaranteed share of bandwidth to each class, but bandwidth is not wasted when a class is inactive. Unlike the Link Shar? ing scheme of Floyd?Jacobsen, HFQ is provably fair, in that throughput is a close approx? imation to the ideal sharing scheme for an infinitely divisible resource. HFQ extends the techniques of Fair Queueing of Demers?Keshav?Shenker, to deal with a hierarchy of classes. HFQ also provides bounded delays for real time traffic. We implemented HFQ as part of a real IP gateway, and performed a number of tests which demonstrate its fair? ness.

1. Introduction

The design of a service discipline to use in network gateways has received much attention in recent years. The traditional First Come First Served (FCFS) discipline used in most gateways has proved to be inadequate. With best?effort data applications, it allows ill?behaved users to obtain excessive bandwidth and starve others whose requests are more moderate. Similarly, FCFS does not provide a guaranteed rate of service to real?time multimedia applications. A number of alternatives have been suggested, some designed specifically for best?effort data applications, some for for real?time applications, and some for both.

Recent work by Floyd and Jacobsen [4] and colleagues [18] has drawn attention to the case where bandwidth on a link must be shared between users who are arranged in a hierarchy of classes. At each level of the hierarchy, the classes have predefined shares, such that the bandwidth allocated to the parent class is to be divided among the children in proportion to their shares. For example, the top?level classes might rep? resent organisations which have contributed to the cost of the link; the shares then represent the financial stake of each class. At a lower level, the classes might correspond to different protocol suites; with differ? ent end?point pairs defining the lowest level. Of course one could permanently reserve part of the band? width for each class, but this is very wasteful when a class is inactive. Instead we seek to divide the service fairly between those classes which are requesting it at any time.

One can easily recognise some service mechanisms as unfair; for example, FCFS will allow a class to obtain more service, simply by being more greedy in its requests. However, to allow rigorous evaluation of proposed queueing algorithms, we need a precise definition of fairness. For the case where there is a single level of classes, rather than a hierarchy, the natural definition was proposed (in the context of CPU schedul? ing) by Kleinrock [11]. Kleinrock's Processor Sharing model (PS) is an idealised, fluid flow model which serves as an intuitive definition of fairness: all active users are serviced at an equal rate, which requires that the resource be arbitrarily divisible. For situations where different users are actually entitled to different proportions of the resource, PS readily generalises to include a concept of weights which control the divi? sion of the instantaneous bandwidth. In this paper we present a natural extension of PS to deal with hierar? chical classes. We call this Hierarchical Processor Sharing (HPS).

Of course, a realistic queueing algorithm needs to choose a single packet to send, and then wait till