INTERNETWORKING: RESEARCH AND EXPERIENCE, VOL. 1, 3-26(1990) Analysis and Simulation of a Fair Queueing Algorithm ALAN DEMERS Xerox PARC 3333 Coyote Hill Road Palo Alto, ca94304 U.S.A. SRINIVASAN KESHAV Computer Science Division Department of EECS University of California at Berkeley Berkeley, CA94720, U.S.A. SCOTT SHENKER Xerox PARC 3333 Coyote Hill Road Palo Alto CA94304 U.S.A. SUMMARY We discuss gateway queueing algorithms and their role in controlling congestion in datagram networks. fair queueing algorithm, based on an earlier suggestion by Nagle, is proposed. Analysis and simulations are used to compare this algorithm to other congestion control schemes. We find queueing algorithm: fair allocation of bandwidth lower delay for sources using less than their full share of bandwidth, and protection from ill-behaved sources. KEY WORDS Congestion control Queueing algorithms Fair queueing INTRODUCTION Datagram networks have long suffered from performance degradation in the presence of congestion(Gerla and Kleinrock, 1980. The rapid growth, in both use and size, of 1049-8915/90/010003-24$12.00 Received January 1990 1990 by John Wiley&sons,ltd Revised 10 April 1990
A DEMERs, S KESHAV AND S SHENKER computer networks has sparked a renewed interest in methods of congestion control (Jain and Ramakrishnan, 1988; Ramakrishnan and Jain, 1988; Chiu and Jain, 1989 Ramakrishnan Chiu and Jain, 1987; Jain Ramakrishnan and Chiu. 1987: Jacobson 1988 Mankin and Thompson, 1989; Nagle, 1984, 1987). These methods have two points of implementation. The first is at the source, where flow control algorithms vary the rate at which the source sends packets. Of course, flow control algorithms are designed primarily to ensure the presence of free buffers at the destination host, but we are more concerned with their role in limiting the overall network traffic. The second point of oplementation is at the gateway. Congestion can be controlled at gateways through routing and queueing algorithms. Adaptive routing, if properly implemented, lessens congestion by routing packets away from network bottlenecks. Queueing algorithms, which control the order in which packets are sent and the usage of the gateway's buffer space, do not affect congestion directly, in that they do not change the total traffic on the gateway's outgoing line. Queueing algorithms do, however, determine the way in which packets from different sources interact with each other which, in turn, affects the collective behavior of flow control algorithms. We shall argue that this effect, which is often ignored, makes queueing algorithms a crucial component in eff ective congestion control Queueing algorithms can be thought of as allocating three nearly independent quantities bandwidth(which packets get transmitted), promptness(when do those packets get transmitted), and buffer space (which and when packets get discarded by the gateway) Currently, the most common queueing algorithm is first-come-first-served(FCFS).FCFS queueing essentially relegates all congestion control to the sources, since the order of arrival completely determines the bandwidth, promptness, and buffer space allocations Thus, FCFS inextricably intertwines these three allocation issues. There may indeed be flow control algorithms that, when universally implemented throughout a network with FCFS gateways, can overcome these limitations and provide reasonably fair and efficient congestion control. This point is discussed more fully later in the paper, when several flow control algorithms are compared. However, with today's diverse and decentralized omputing environments, it is unrealistic to expect universal implementation of any given flow control algorithm. This is not merely a question of standards, but also one of compliance. Even if a universal standard such as OSI(International Organization for Standardization, 1986)were adopted, malfunctioning hardware and software could violate the standard, and there is always the possibility that individuals would alter the algorithms on their own machine to improve their performance at the expense of others. Consequently congestion control algorithms should function well even in the presence of ill-behaved sources. Unfortunately, irrespective of the flow control algorithm used by the well behaved sources, networks with FCFS gateways do not have this proper gle source, sending packets to a gateway at a sufficiently high speed, can capture an arbitrarily high fraction of the bandwidth of the outgoing line. Thus, FCFS queueing is not adequate more discriminating queueing algorithms must be used in conjunction with source flow control algorithms to control congestion effectively in noncooperative environments Following a similar line of reasoning, Nagle(1987)proposed a fair queueing(FQ) algorithm in which gateways maintain separate queues for packets from each individual source. The queues are serviced in a round-robin manner. This prevents a source from arbitrarily increasing its share of the bandwidth or the delay of other sources. In fact when a source sends packets too quickly, it merely increases the length of its own queue
FAIR QUEUEING ALGORITHM Nagle's algorithm, by changing the way packets from different sources interact, does not reward, nor leave others vulnerable to, antisocial behavior. On the surface, this proposal appears to have considerable merit, but we are not aware of any published data on the performance of datagram networks with such fair queueing gateways. In this paper, we will first describe a modification of Nagle's algorithm, and then provide simulation data comparing networks with FQ gateways and those wi The three different components of congestion control algorithms introduced above source flow control, gateway routing and gateway queueing algorithms, interact in interesting and complicated ways. It is impossible to assess the effectiveness of any algorithm without reference to the other components of congestion control in operation We will evaluate our proposed queueing algorithm in the context of static routing and several widely used flow control algorithms. The aim is to find a queueing algorithm that functions well in current computing environments. The algorithm might, indeed it should enable new and improved routing and flow control algorithms, but it must not require We had three goals in writing this paper. The first was to describe a new fair queueing algorithm. In the next section, we discuss the design requirements for an effective ueueing algorithm, outline how Nagle's original proposal fails to meet them, and then propose a new fair queueing algorithm which does meet these requirements. Our second goal was to provide some rigorous understanding of the performance of this new fair queueing algorithm; we present a delay-throughput curve given by this algorithm for a specific configuration of sources, and then compare this performance to that given by the FCFS algorithm. Our third goal was to evaluate our new queueing proposal in the context of real networks. To this end we discuss some currently implemented flow control algorithms and present simulation data comparing several combinations of flow control and queueing algorithms on six benchmark networks In circuit-switched networks where there is explicit buffer reservation and uniform packet sizes, it has been established that round-robin service disciplines allocate bandwidth fairly(Hahne, 1986; Katevenis, 1987). Recently Morgan (1989)has examined the role such queueing algorithms play in controlling congestion in circuit switched networks although his application context is quite different from ours, his conclusions are qualitatively similar. In other related work, the datAKIt queueing algorithm combines round-robin service and FIFO Priority service, and has been analyzed extensively (Lo 1987; Fraser and Morgan, 1984). Also, Luan and Lucantoni(1988) present a different form of bandwidth management policy for circuit switched networks Since the completion of this work, we have learned of similar work by Zhang(1989); her Virtual Clock gateway queueing algorithm is essentially identical to the fair queueing agorithm presented here. Zhang analyzes this algorithm in the context of a proposed resource reservation scheme. the flow Network, whereas we do not consider resource reservation. Heybey and Davin(1989)have simulated a simplified version of our fair queueing algorithm, investigating issues of buffer allocation and policy-based bandwidth allocation. McKenney(1990)and Keshav(1990) have investigated the implementation pects of fair queueing. In addition, Greenberg and Madras(1990)have established some performance bounds on the fairness of our fair queueing scheme and other similar DATAKIT is a Trademark of AT&T
A DEMERS, S KESHAV AND S SHENKER FAIR QUEUEING Motivation What are the requirements for a queueing algorithm that will allow source fow control algorithms to provide adequate congestion control even in the pre sence of ill-behaved sources? We start with Nagle's observation that such queueing algorithms must provide otection, so that ill-behaved sources can only have a limited negative impact on well- behaved sources. Allocating bandwidth and buffer space in a fair manner, to be defined later, automatically ensures that ill-behaved sources can get no more than their fair share This led us to adopt, as our central design consideration, the requirement that the queueing algorithm allocate bandwidth and buffer space fairly. Ability to control the promptness, or delay, allocation somewhat independently of the bandwidth and bufter allocation is also desirable. Finally, we require that the gateway should provide service that, in some sense, does not depend discontinuously on a packet,'s time of arrival(this continuity condition will be made precise in the context of defining our algorithm). This continuity requirement attempts to prevent the efficiency of source flow control implementations from being overly sensitive to timing details(timers are the Bermuda Triangle of Aow control algorithms ). Nagle's proposal does not satisfy these requiremen The most obvious faw is its lack of consideration of packet lengths. A source using long ackets gets more bandwidth than one using short packets, so bandwidth is not allocated airly. Also, the proposal has no explicit promptness allocation other than that provided by the round-robin service discipline. In addition, the static round-robin ordering violates the continuity requirement. These defects are corrected in our version of fair queueing which we define after first dicussing our definition of fairness In stating our requirements for queueing algorithms, we have left the term fair undefined. The term fair has a clear colloquial meaning but it also has a technical definition(actually several, but only one is considered here). Consider, for example, the allocation of a single resource among N users. Assume there is an amount total of this resource and that each of the users requests an amount p; and, under a particular llocation. receives an amount u What is a fair allocation The max-min fairness criterion(Ramakrishnan, Chiu and Jain, 1987; Hahne, 1986; Gafni and Bertsekas, 1984) states that an allocation is fair if (1)no user receives more than its request, (2)no other allocation scheme satisfying condition 1 has a higher minimum allocation, and (3)condition 2 remains recursively true as we remove the minimal user and reduce the total resource accordingly, ptotale-H-total-Hmin. This condition reduces to w =MIN(Wrair p) in the simple example, with Pfair, the fair share, being set so that Total 2 H This concept of fairness easily generalizes to the multiple resource case(Ramakrishnan, Chiu and Jain, 1987) Note that implicit in the max-min definition of fairness is the assumption that the users have equal rights to the resource In our communication application, the bandwidth and buffer demands are clearly represented by the packets that arrive at the gateway( Demands for promptness are not explicitly communicated, and we return to this issue later. )However, it is not clear what constitutes a user. The user associated with a packet could refer to the source of the packet, the destination, the source-destination pair, or even refer to an individual process running on a source host. Each of these definitions has limitations. Allocation per source
FAIR QUEUEING ALGORITHM unnaturally restricts sources such as file servers which typically consume considerable bandwidth. Ideally the gateways could know that some sources deserve more bandwidth than others, but there is no adequate mechanism for establishing that knowledge in days networks. Allocation per receiver allows a receiver's useful incoming bandwidth to be reduced by a broken or malicious source sending unwanted packets to it. Allocation per process on a host encourages human users to start several processes communicating simultaneously, thereby avoiding the original intent of fair allocation. Allocation per source-destination pair allows a malicious source to consume an unlimited amount of bandwidth by sending many packets all to different destinations. While this does not allow the malicious source to do useful work, it can prevent other sources from obtaining sufficient bandwidth Overall, allocation on the basis of source-destination pairs, or conversations, seems the best trade-off between security and efficiency and will be used here. However, our treatment will apply to any of these interpretations of user. Given the requirements for an adequate queueing algorithm, coupled with the definitions of fairness and user, we now turn to the description of our fair queueing algorithm Definition It is simple to allocate buffer space fairly by dropping packets, when necessary, from the conversation with the largest queue. Allocating bandwidth fairly is less straightforward Pure round-robin service provides a fair allocation of packets-sent but fails to guarantee a fair allocation of bandwidth because of variations in packet sizes, To see how this unfairness can be avoided, we first consider a hypothetical service discipline where transmission occurs in a bit-by-bit round-robin(BR)fashion (as in a head-of-queue processor sharing discipline). This service discipline allocates bandwidth fairly since at every instant in time each conversation is receiving its fair share. Let R(r) denote the number of rounds made in the round-robin service discipline up to time t(r(t)is a continuous function, with the fractional part indicating partially completed rounds). Let Nac(t) denote the number of active conversations, i. e. those that have bits in their queue at time t. Then, aR/at=u/Nac(), where u is the linespeed of the gateway's outgoing line(we will, for convenience, work in units such that u=1). a packet of size P whose first bit gets serviced at time fo will have its last bit serviced P rounds later, at time t such that R(O=R(Lo)+ P. Let ro be the time that packet i belonging to conversation a arrives at the gateway, and define the numbers S and Fa as the values of R(r) when the packet started and finished service. With Pa denoting the size of the packet, the following relations hold: F9= S?+Po and S,= MAX(F-i, R(e9)). Since R(t)is a strictly monotonically increasing function whenever there are bits at the gateway, the ordering of the Fa values is the same as the ordering of the finishing times of the various packets in the br discipline Sending packets in a bit-by-bit round-robin fashion, while satisfying our requirements for an adequate queueing algorithm, is obviously unrealistic. We hope to emulate this impractical algorithm by a practical packet-by-packet transmission scheme. Note that the functions R(o and Nac(o) and the quantities S and F depend only on the packet arrival times r and not on the actual packet transmission times, as long as we define a conversation to be active whenever R(osFa for i=MAX(Irsn). We are thus free to use these quantities in defining our packet-by-packet transmission algorithm. A natural