pfSense Traffic Shaping: Part Two (Hierarchical Fair Service Curve)

Hierarchical Fair Service CurveIn Part One, I gave a brief overview of the traffic shaping wizard. Underlying pfSense’s traffic shaping capabilities are several traffic shaping algorithms. In this article, I will cover one of them: Hierarchical Fair Service Curve.

Hierarchical Fair Service Curve (HFSC)

Traditional Packet Fair Queuing algorithms such as Weighted Fair Queueing allocate to each backlogged flow at least a weighted fair share of service and achieve instantaneous fairness. When used with reservation (in which resources are reserved), PFQ can provide a minimum bandwidth guarantee, 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 remains popular, it has two limitations: [1] limited resource management capability; and [2] coupled delay and bandwidth allocation. Hierarchical Fair Service Curve (HFSC) is designed to address both these limitations.

With PFQ, each traffic flow is treated as an independent entity, and excess bandwidth is distributed 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.

Hierarchical Packet Fair Queuing was proposed to extend basic PFQ algorithms to support link-sharing. Under this model, hierarchical link-sharing is implemented, whereby there is a class hierarchy associated with each link that specifies the resource allocation policy for the link. A class represents a traffic stream or some aggregate of traffic streams that are grouped according to administrative affiliation, protocol, traffic type, or other criteria.

Hierarchical Fair Service Curve

Example of a concave service curve.

Hierarchical link-sharing can be illustrated using a hypothetical scenario involving a 45 Mbps link that is shared by two organizations, Carnegie Mellon University (CMU) and University of Pittsburgh (U.Pitt.).1  There are several important goals that the hierarchical link-sharing service is aimed to achieve. First, each class should receive a certain minimum amount of resource if there is enough demand. In this example, CMU’s traffic should receive at least 25 Mbps of bandwidth during a period when the aggregate traffic from CMU has a higher arrival rate. Similarly, if there is resource contention between traffic classes within CMU, the video traffic should get at least 10 Mbps. Also, if there are only audio and video streams from CMU, the audio and video traffic should receive all the bandwidth that is allocated to CMU if the demand is high enough. While the above policy specifies that the CMU audio and video traffic classes have priority to use any excess bandwidth unused by the data traffic, there is also the issue of how the excess bandwidth will be distributed between the audio and video classes. The second goal of hierarchical link-sharing service is to have a policy to distribute the excess bandwidth unused by a class to other classes. In this case, the policy could be set so if the CMU Video class is not utilizing all its 10 Mbps, the CMU Audio class and CMU Data class have priority to receive the excess bandwidth first. Only if CMU cannot use up all the excess, the remaining bandwidth is distributed over to the University of Pittsburgh. HFSC is designed based on this hierarchical link-sharing model and thus proves more powerful resource management than PFQ. However, HFSC has an important additional benefit over HPFQ: it can decouple the allocation of delay and bandwidth.

Under PFQ (or for that matter, HPFQ), only one parameter is used to characterize the performance of a flow: its guaranteed bandwidth. A worst case packet delay bound can be derived from a given guaranteed bandwidth. In this case, the only way to reduce worst case delay is to increase the bandwidth reservation. This may lead to inefficient resource utilization when there are low-bandwidth low-delay flows.

Hierarchical Fair Service Curve

Example of a convex service curve.

The solution to this problem used by HFSC is to use the service curve service model. It is actually a two-piece linear curve, in which m1 is the slope of the first segment, m2 is the slope of the second segment, and d is the intersection point of the two segments. Delay on the x-axis, while bandwidth is on the y-axis. We call the curve concave if m1 > m2, and convex if m2 > m1. By using a concave service curve, HFSC can achieve a lower delay than under PFQ without over-reserving link bandwidth. As a result, HFSC provides decoupled delay and bandwidth allocation in an integrated fashion.

With these advantages, it is not surprising that HFSC is gaining acceptance and is one of the traffic shaping algorithms implemented in pfSense. In part three of this series on traffic shaping, I will cover class based queuing and priority queuing.


[1] This was given as an example in “A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Services”, Ion Stoica, Hui Zhang, T. S. Eugene Ng, Carnegie Mellon University, Pittsburgh, PA.

External Links:

Ion Stoica et. al, “A Hierarchical Fair Service Curve Algorithm for Link-Sharing, Real-Time and Priority Services”

Hierarchical Packet Schedulers

Hierarchical Fair Service Curve at Wikipedia

Be Sociable, Share!

Speak Your Mind


© 2013 David Zientara. All rights reserved. Privacy Policy