Traditional Packet Fair Queueing (PFQ) algorithms such as Weighted
Fair Queueing (WFQ) allocate to each backlogged flow at least a
weighted fair share of service and achieve instantaneous
fairness. When used with reservation, PFQ can provide a minimum
bandwidth guarantee; on the other hand, when used without reservation,
PFQ can provide fair service and protection against malicious flows
for best effort traffic. For these reasons, PFQ has become the most
popular QoS mechanism for integrated services.
While PFQ represents a major step in evolving the Internet into an
integrated services network, it has two limitations:
HFSC is designed to address both of these limitations.
- limited resource management capability
- coupled delay and bandwidth allocation
Hierarchical Resource Management Under PFQ, each traffic flow
is treated as an independent entity, even though some flows may belong
to the same application program, the same company, or the same
ISP. When excess bandwidth becomes available, since PFQ does not have
any notion of organizational structures, it distributes such excess
bandwidth among all backlogged flows in the system rather than
distributing excess bandwidth among flows within an organizational
boundary. Thus, PFQ has limited resource management capability.
A powerful abstraction for resource management is the hierarchical
link-sharing model. The figure below illustrates an example of how a
link may be hierarchically shared between Carnegie Mellon University
and University of Pittsburgh.
In this example, the link bandwidth is first divided among the two
universities, and then further sub-divided among applications and
individual flows. Under the hierarchical link-sharing model, if the
CMU Video class is not utilizing all of its 10 Mbps, the CMU Audio
class and the CMU Data class have priority to receive this excess
bandwidth first. Only if CMU cannot use up all the excess, the
remaining bandwidth is distributed over to University of Pittsburgh.
In contrast, under PFQ, no structuring is possible (i.e. a flat
structure) and thus any excess bandwidth from CMU is shared between
both universities. This model also makes constructing virtual networks
on top of physical networks possible.
Based on the hierarchical link-sharing model,
Hierarchical Packet Fair Queueing (HPFQ) was proposed to extend
basic PFQ algorithms to support hierarchical link-sharing. HFSC is
also designed based on the hierarchical link-sharing model and
therefore is equally powerful for resource management. However, HFSC
has an important additional benefit over HPFQ: it can decouple the
allocation of delay and bandwidth.
Decoupled Delay/Bandwidth Allocation
Under PFQ or HPFQ, only
one parameter is used to characterize the performance of a flow -- its
guaranteed bandwidth. Given a guaranteed bandwidth, a worst case packet
delay bound can be derived. Unfortunately, the only way to reduce
this worst case delay is to increase the bandwidth reservation. This
may lead to inefficient resource utilization in the presence of
low-bandwidth low-delay flows.
In order to decouple delay and bandwidth allocation, HFSC is designed
based on the service curve service model. In HFSC, only two-piece
linear service curves are used for simplicity. A two-piece linear
service curve is characterized by three parameters:
The following figure illustrates the two types of two-piece linear
service curves used in HFSC. For a convex curve (when m1 is less than
m2), m1 is always zero.
- m1, the slope of the first segment
- m2, the slope of the second segment
- d, the x-projection of the intersection point of the two segments
Note that PFQ's bandwidth guarantee can be thought of as a straight
line service curve. In general, a concave service curve (m1,m2,d) can
achieve a lower delay than a straight line service curve of slope m2,
and it in turn achieves a lower delay than a convex service curve of
(0,m2,d). Thus using a concave service curve under HFSC, a flow can
achieve lower delay than under PFQ without over-reserving link
bandwidth. As a result, HFSC provides decoupled delay and bandwidth
allocation in an integrated fashion.