Ion Stoica
Hui Zhang
ABSTRACT
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 band-width 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 over-head.
- 1.J.C.R. Bennett and H. Zhang. Hierarchical packet fair queueing algorithms. In Proceedings of the A CM-SIGCOMM 96, pages 143-156, Pale Alto, CA, August 1996. Google Scholar
Digital Library
- 2.J.C.R. Bennett and H. Zhang. WF2Q: Worst-case fair weighted fair queueing. In Proceedings of IEEE INFO- COM'96, pages 120--128, San Francisco, CA, March 199(}. Google ScholarDigital Library
- 3.R. Brown. Calendar queues: A fast O(1) priority queue implementation for the simulation event set problem. Com. munications of the A CM, 31(10):1220--1227, October 1988. Google ScholarDigital Library
- 4.R. Cruz. Service burstiness and dynamic burstiness measures: A framework. Journal of High Speed Networks, 1(2):105-127, 1992.Google ScholarDigital Library
- 5.R. Cruz. Quality of service guaranteed in virtual circuit switched network. IEEE Journal on Selected Areas in Communications, 13(6):1048-1056, August 1995. Google ScholarDigital Library
- 6.S. Floyd and V. Jacobsen. Link-sharing and resource management models for packet networks. IEEE/A CM Transac. tions on Networking, 3(4), August 1995. Google ScholarDigital Library
- 7.L. Georgiadis, R. Gu~rin, and V. Peris. Efficient network QoS provisioning based on per node traffic shaping. In IEEE INFOCOM'~6, San Francisco, CA, March 1996. Google ScholarDigital Library
- 8.S. Golestani. A self-clocked fair queueing scheme for broadband applications. In Proceedings of IEEE INFOCOM'94, pages 636-646, Toronto, CA, June 1994.Google ScholarCross Ref
- 9.P. Goyai, H.M. Vin, and H. Chen. Start-time Fair Queuing: A scheduling algorithm for integrated services. In Proceedings of the A CM-SiGCOMM 96, pages 157-168, Pale Alto, CA, August 1996. Google ScholarDigital Library
- 10.A. Parekh. A Generalized Processor Sharing Approach to Flow Control in integrated Services Networks. PhD dissertation, Massachusetts Institute of Technology, February 1992.Google Scholar
- 11.H. Sariowan, R.L. Cruz, and G.C. Polyzo$. Scheduling for quality of service guarantees via service curves, in Proceedings of the international Conference on Computer Communications and Networks (ICCCN) 1995, pages 512-520, September 1995. Google ScholarDigital Library
- 12.S. Shenker, D. Clark, and L. Zhang. A scheduling service model and a scheduling architecture for an integrated services network, 1993. preprint.Google Scholar
- 13.I. Stoica and H. Abdel-Wahab. Earliest eligible virtual deadline first: A flexible and accurate mechanism for proportional share resource allocation. Technical Report TR-95-22, Old Dominion University, November 1995. Google ScholarDigital Library
- 14.I. Stoica, H. Abdel-Wahab, K. Jeffay, S. Baruah, J. Gehrke, and G. Plaxton. A proportional share resource allocation for real-time, time-shared systems. In Proceedings of the IEEE RTSS 96, pages 288 - 289, December 1996. Google ScholarDigital Library
- 15.I. Stoica, H. Zhang, and T.$. E. Fig. A hierarchical fair service curve algorithm for link-sharing, real-time and priority services. Technical Report CMU-CS-97-154, Carnegie Mellon University, July 1997.Google ScholarCross Ref
- 16.Z. Liu Z.-L. Zhang and D. Towsley. Closed-form deterministic performance bounds for the generalized processor sharing scheduling discipline, 199}'. To appear journal of Combinatorial Optimaization.Google Scholar
- 17.H. Zhang. Service disciplines for guaranteed performance service in packet-switching networks. Proceedings of the iEEE, 83(10):1374-1399, October 1995.Google ScholarCross Ref
- 18.H. Zhang and D. Ferrari. Rate-controlled service disciplines. Journal of High Speed Networks, 3(4):389-412, 1994.Google ScholarCross Ref
Index Terms
- A hierarchical fair service curve algorithm for link-sharing, real-time and priority services
Recommendations
A hierarchical fair service curve algorithm for link-sharing, real-time and priority services
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 ...
A generalized hierarchical fair service curve algorithm for high network utilization and link-sharing
The number of real-time applications, such as video-on-demand and video conferencing, is rapidly increasing. Real-time data now occupies a significant portion of network traffic. These applications require real-time service; as such, they need to bound ...
Comments