Design and Analysis of Frame-based Fair Queueing:
A New Traffic Scheduling Algorithm for Packet-Switched Networks
Dimitrios Stiliadis and Anujan Varma
Computer Engineering Department
University of California
Santa Cruz, CA 95064
In this paper we introduce and analyze frame-based fair queueing, a novel traffic scheduling algorithm for packetswitched networks. The algorithm provides end-to-end delay bounds identical to those of PGPS (packet-level generalized processor sharing), without the complexity of simulating the fluid-model system in the background as required in PGPS. The algorithm is therefore ideally suited for implementation in packet switches supporting a large number of sessions. We present a simple implementation of the algorithm for a general packet switch. In addition, we prove that the algorithm is fair in the sense that sessions are not penalized for excess bandwidth they received while other sessions were idle. Frame-based fair queueing belongs to a general class of scheduling algorithms, which we call Rate-Proportional Servers. This class of algorithms provides the same end-toend delay and burstiness bounds as PGPS, but allows more flexibility in the design and implementation of the algorithm. We provide a systematic analysis of this class of schedulers and obtain bounds on their fairness.
Providing QoS guarantees in a packet network requires the use of traffic scheduling algorithms in the switches (or routers). The function of a scheduling algorithm is to select, for each outgoing link of the switch, the packet to be transmitted in the next cycle from the available packets belonging to the flows sharing the output link. Implementation of the algorithm may be in hardware or software. In ATM networks, where information is transmitted in terms of small fixed-size cells, the scheduling algorithm is usually implemented in hardware. In a packet network with larger packet-sizes, the algorithm may be implemented in software. Several scheduling algorithms are known in the literature for bandwidth allocation and transmission scheduling in output-buffered switches. These include the packet-by-packet version of Generalized Processor Sharing
This research is supported by the NSF Young Investigator Award
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
SIGMETRICS 96-5/96 Philadelphia, PA, USA
c 1996 ACM
(PGPS)  (also known as Weighted Fair Queueing ), VirtualClock , Self-Clocked Fair Queueing (SCFQ) , Delay-Earliest-Due-Date (Delay-EDD) , Weighted Round Robin , and Deficit Round Robin . Many of these algorithms are also capable of providing deterministic upper bounds on the end-to-end delay seen by a session when the burstiness of the session traffic is bounded (for example, shaped by a leaky bucket).
Based on their internal structure, traffic schedulers can
be classified into two main types: sorted-priority and framebased
. In a sorted-priority scheduler, there is a global
variable | usually referred to as the virtual time | associated
with each outgoing link of the switch. Each time
a packet arrives or gets serviced, this variable is updated.
A timestamp, computed as a function of this variable, is
associated with each packet in the system. Packets are
sorted based on their timestamps, and are transmitted in
that order. VirtualClock , Weighted Fair Queueing ,
and Delay-EDD  follow this architecture. A frame-based
scheduler, on the other hand, does not require a priorityqueue
of packets to be maintained. Instead, bandwidth
guarantees are provided by splitting time into frames of
fixed or variable length, and limiting the amount of traffic
a session is allowed to transmit during a frame period.
Examples for frame-based schedulers include Hierarchical
Round Robin , Stop-and-Go Queueing , Weighted
Round Robin  and Deficit Round Robin .
A traffic scheduling algorithm must possess several desirable features to be useful in practice:
1. Isolation of flows: The algorithm must isolate an endto-end session from the undesirable effects of other (possibly misbehaving) sessions. Note that isolation is necessary even when policing mechanisms are used to shape the flows at the entry point of the network, as the flows may accumulate burstiness within the network. 2. Low end-to-end delays: Real-time applications require from the network low end-to-end delay guarantees. 3. Utilization: The algorithm must utilize the link bandwidth efficiently.
4. Fairness: The available link bandwidth must be divided among the connections sharing the link in a fair manner. An unfair scheduling algorithm may offer widely different service rates to two connections with the same reserved rate over short intervals.
5. Simplicity of implementation: The scheduling algorithm must have a simple implementation. In an ATM network, the available time for completing a scheduling decision is very short and the algorithm must be implemented in hardware. In packet networks with larger