
Design and Analysis of Framebased Fair Queueing:
A New Traffic Scheduling Algorithm for PacketSwitched Networks
Dimitrios Stiliadis and Anujan Varma
Computer Engineering Department
University of California
Santa Cruz, CA 95064
Abstract
In this paper we introduce and analyze framebased fair queueing, a novel traffic scheduling algorithm for packetswitched networks. The algorithm provides endtoend delay bounds identical to those of PGPS (packetlevel generalized processor sharing), without the complexity of simulating the fluidmodel 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. Framebased fair queueing belongs to a general class of scheduling algorithms, which we call RateProportional Servers. This class of algorithms provides the same endtoend 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.
I. Introduction
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 fixedsize cells, the scheduling algorithm is usually implemented in hardware. In a packet network with larger packetsizes, the algorithm may be implemented in software. Several scheduling algorithms are known in the literature for bandwidth allocation and transmission scheduling in outputbuffered switches. These include the packetbypacket version of Generalized Processor Sharing
This research is supported by the NSF Young Investigator Award
No. MIP9257103.
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 965/96 Philadelphia, PA, USA
c 1996 ACM
(PGPS) [1] (also known as Weighted Fair Queueing [2]), VirtualClock [3], SelfClocked Fair Queueing (SCFQ) [4], DelayEarliestDueDate (DelayEDD) [5], Weighted Round Robin [6], and Deficit Round Robin [7]. Many of these algorithms are also capable of providing deterministic upper bounds on the endtoend 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: sortedpriority and framebased
[8]. In a sortedpriority 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 [3], Weighted Fair Queueing [2],
and DelayEDD [5] follow this architecture. A framebased
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 framebased schedulers include Hierarchical
Round Robin [9], StopandGo Queueing [10], Weighted
Round Robin [6] and Deficit Round Robin [7].
A traffic scheduling algorithm must possess several desirable
features to be useful in practice:
1. Isolation of flows: The algorithm must isolate an endtoend
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 endtoend delays: Realtime applications require
from the network low endtoend 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