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:
- 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:
- 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.