Victor Firoiu Providing Hard Guarantees through Rate-Based and Rate-Controlled Service Discipline I will start with a look at the motivation for hard guarantees and the debate over hard versus soft guarantees. I will introduce the notion of envelope as an upper bound on a flow's traffic and some particular envelopes (leaky buckets). In the second part of the talk I will present Weighted Fair Queuing, WFQ, aka Generalized Processor Sharing, GPS, as a rate-based service discipline. Some historical and initial rationale [1] are followed by some important results and techniques developed by Parekh and Gallager [2,3]. Simple applications for Rate Proportional Processor Sharing, RPPS, and for the Internet Integrated Services "Guaranteed Service" model [4] concludes this part. In the third part I will present schedluability conditions for rate-controlled Earlies Deadline First, EDF, [5] and a simple EDF admission control algorithm for leaky bucket flows [6]. In the last part I will show that EDF outperforms WFQ in both single node and network settings [7] and present some practical utilization of EDF scheduling [8]. References. [1] @article{Demers:WFQ, author = {A. Demers and S. Keshav and S. Shenker}, title = {{Analysis and Simulation of a Fair Queuing Algorithm}}, journal = {Computer Communication Review (ACM SIGCOMM'89)}, volume = {19}, number = 4, year = 1989 } [2] @article{Parekh93:GPS, author = {A. Parekh and R. Gallager}, title = {{A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single Node Case}}, journal = {IEEE/ACM Transactions on Networking}, volume = {1}, number = 3, year = 1993 } [3] @article{Parekh94:GPS, author = {A. Parekh and R. Gallager}, title = {{A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Multiple Node Case}}, journal = {IEEE/ACM Transactions on Networking}, volume = {2}, number = 2, year = 1994 } [4] @unpublished{Shenker:GuarQoS, author = {S. Shenker and C. Partridge and R. Guerin}, title = {{Specification of Guaranteed Quality of Service}}, note = {Internet draft-ietf-intserv-guaranteed-svc-06.txt}, month = {August}, year = 1996 } http://ds.internic.net/internet-drafts/draft-ietf-intserv-guaranteed-svc-06.txt [5] @techreport{Liebeherr94, author = {J. Liebeherr and D. Wrege and D. Ferrari}, title = {{Exact Admission Control for Networks with Bounded Delay Services}}, institution = {University of Virginia}, number = {CS-94-29}, year = 1994 } ftp://ftp.cs.virginia.edu/pub/techreports/CS-94-29.ps.Z [6] @conference{Firoiu97:EDFAC, author = {V. Firoiu and J. Kurose and D. Towsley}, title = {{Efficient Admission Control for EDF Schedulers}}, booktitle = {IEEE INFOCOM}, year = 1997 } ftp://gaia.cs.umass.edu/pub/Firoiu96:edfac-INFOCOM97.ps.Z [7] @conference{Georgiadis96:PerNode, author = {L. Georgiadis and R. Gu\'{e}rin and V. Peris and K. Sivarajan}, title = {{Efficient Network QoS Provisioning Based on per Node Traffic Shaping}}, booktitle = {IEEE INFOCOM}, year = 1996 } [8] @conference{Georgiadis96:DelayRateGuar, author = {L. Georgiadis and R. Gu\'{e}rin and V. Peris and R. Rajan}, title = {{Efficient Support of Delay and Rate Guarantees in an Internet}}, booktitle = {ACM SIGCOMM}, year = 1996 }