Computer Science Department
School of Computer Science, Carnegie Mellon University


A Hierarchical Fair Service Curve Algorithm for
Link-Sharing, Real-Time and Priority Services

Ion Stoica, Hui Zhang, T.S. Eugene Ng

September 1997

An earlier version of this paper appeared in
Proceedings of ACM SIGCOMM'97.

Keywords: Resource management, scheduling, link-sharing, real-time, fairness

In this paper, we study hierarchical resource management models and algorithms that support both link-sharing and guaranteed real-time services with decoupled delay (priority) and bandwidth allocation. We extend the service curve based QoS model, which defines both delay and bandwidth requirements of a class, to include fairness, which is important for the integration of real-time and hierarchical link-sharing services. The resulting Fair Service Curve link-sharing model formalizes the goals of link-sharing and real-time services and exposes the fundamental tradeoffs between these goals. In particular, with decoupled delay and bandwidth allocation, it is impossible to simultaneously provide guaranteed real-time service and achieve perfect link-sharing. We propose a novel scheduling algorithm called Hierarchical Fair Service Curve (H-FSC) that approximates the model closely and efficiently. The algorithm always guarantees the performance for leaf classes, thus ensures real-time services, while minimizing the discrepancy between the actual services provided to the interior classes and the services defined by the Fair Service Curve link-sharing model. We have implemented the H-FSC scheduler in the NetBSD environment. By performing simulation and measurement experiments, we evaluate the link-sharing and real-time performances of H-FSC, and determine the computation overhead.

62 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by