Topics in Distributed Systems – Quality of Service


Instructor: Matei Ripeanu

Schedule: Monday 5:00-7:30

Location: KAIS4018 (might change)



[01/09] Subscribe to mailing list

[01/16] Register with the H2O system and join project EECE571R. To submit your paper review please go to the appropriate “Rotisserie Discussion”. Reviews for Monday class are due by midnight on Sunday.


Course description (please see syllabus for more details)

The design of complex large-scale computing systems that provide controlled quality of service is an outstanding challenge for networking and distributed systems research. This graduate-level course uses an inclusive definition of quality of service (QoS) in computing systems: we will investigate issues related to providing predictable performance at multiple levels of the computing stack (operating system, network, middleware, application layer), using different elements of the computing infrastructure (e.g., network, storage) for different end-user applications (e.g., multimedia delivery, scientific workflows).

The course will cover fundamentals of: queuing theory, operating system and network support for offering controlled QoS; QoS enabled middleware and applications; the interplay between low-level QoS metrics and the quality of experience perceived by application users.  Advances in all these directions are key ingredients for recent efforts to build cyber-infrastructure. Students will be exposed to a range of quality of service technologies from networking (IntServ, DiffServ, RSVP), operating system (fair scheduling), and distributed systems (SLA, advance reservations) and their integration with massive computing systems.


Course format

The course is structured to provide (i) an in-depth understanding of current topics in large-scale, distributed system research; (ii) experience with reviewing and presenting advanced technical material; (iii) exercising writing and critically reviewing research papers. The class workload has a participation component and a final project.

·        Participation. In each class we discuss one or two research papers. Read the papers before class (be an efficient reader!)  and write a review for each paper that includes the following:

1.     State the main contribution of the paper

2.     Critique the main contribution. 

a.     Rate the significance of the paper on a scale of 5 (breakthrough), 4 (significant contribution), 3 (modest contribution), 2 (incremental contribution), 1 (no contribution or negative contribution). More importantly: Explain your rating in a sentence or two.

b.     Rate how convincing the methodology is. You may consider some of the following questions (use what is relevant): Do the claims and conclusions follow from the experiments? Are the assumptions realistic? Are the experiments well designed? Are there different experiments that would be more convincing? Are there other alternatives the authors should have considered? (And, of course, is the paper free of methodological errors?)

c.      What are the most important limitations of the approach?

3.     What are the two strongest and/or most interesting ideas in the paper?

4.     What are the two most striking weaknesses in the paper?

5.     Name two questions that you would like to ask the authors.

6.     Detail an interesting extension to the work not mentioned in the future work section.

7.     Optional comments on the paper that you’d like to see discussed in class.

Reviews must be submitted by midnight the day before the class to the relevant Rotisserie Discussion on H2O. Papers are discussed in class. Discussions will be lead by one or more students and may include a brief (10-minute) presentation of the paper. Discussion leaders do not need to submit reviews, but they need to: (a) Prepare discussion plan, (b) Post a brief discussion summary on H2O based on in-class discussions (due before the following class).

·        Final Project: The final project is an opportunity for hands-on research in distributed systems. It involves literature survey, programming, running experiments or analytical modeling, analyzing results and writing a 10-page report. A list of project ideas is posted, but students are highly encouraged to propose topics of their own interest.  Teams of two students are highly recommended. Please see me if you want to form a larger team.


Schedule (tentative):

Last year’s course schedule (topic: data-intensive computing systems) is here.





Papers / Other links



Introduction. Overview of current research problems, technologies, and applications. [slides]

1.      Scott Shenker, Fundamental Design Issues for the Future Internet, IEEE Journal on Selected Areas in Communication, 1995 [link]

2.      Lee Breslau, Scott Shenker,  Best-Effort versus Reservations: A Simple Comparative Analysis, SIGCOMM’98 [link][slides]



Project: discussion of project themes.




Pricing. Capacity management. Current experience introducing network QoS 




3.      Paris Metro Pricing for the Internet, A. M. Odlyzko, Proc. ACM Conference on Electronic Commerce (EC'99), ACM, 1999, pp. 140-147. [pdf]

4.      J. Crowcroft, S. Hand , R. Mortier, T. Roscoe, A. Warfield, QoS`s Downfall: At the bottom, or not at all!, ACM Sigcomm RIPQOS Workshop, August 2003

5.      B. Davie, Deployment Experience with Differentiated Services, ACM Sigcomm RIPQOS Workshop, August 2003



6.      The evolution of price discrimination in transportation and its implications for the Internet, A. M. Odlyzko, Review of Network Economics, vol. 3, no. 3, September 2004, pp. 323-346. [pdf]

7.      B. Teitelbaum, S. Shalunov, What QoS Research Hasn`t Understood About Risk, ACM Sigcomm RIPQOS Workshop, August 2003 [slides]

8.      ACM SIGCOMM 2003 RIPQOS Workshop [link] Report [link]




Support for QoS (router, operating system)

[Project: submit a one-page proposal by Sunday 01/27]

9.      V. P. Kumar, T. V. Lakshman, D. Stiliadis, Beyond Best Effort: Router Architectures for the Differentiated Services of Tomorrow's Internet, IEEE Communications, vol. 36, no. 5, May 1998, pp. 152-163.

10.  Gaurav Banga et al., Resource containers: A new facility for resource management in server systems, OSDI’99.


11.  S. Keshav, R. Sharma, Issues and Trends in Router Design, IEEE Communications, vol. 36, no. 5, May 1998, pp. 144-151



Network level support for QoS: DiffServ, RSVP, IntServ

12.  Lee Breslau, Edward W. Knightly, Scott Shenker, Ion Stoica, Hui Zhang: Endpoint admission control: Architectural issues and performance. SIGCOMM 2000: 57-69 [link]

13.  RFC 2638



14.  K. Kilkki: "Differentiated Services for the Internet"
Macmillan Technical Publishing, Indianapolis, IN, USA, June 1999.
Contents, Introduction, Chapter 1, Chapter 2, Chapter 3, Chapter 4, Chapter 5, Chapter 6, Chapter 7, Chapter 8, Chapter 9, Glossary, Bibliography

15.  A Quantitative Study of Differentiated Services for the Internet
S. Sahu, D. Towsley, J. Kurose, SIGCOMM’99

16.  On Achievable Service Differentiation with Token Bucket Marking for TCP
S. Sahu, P. Nain, D. Towsley, C. Diot, V. Firoiu, Univertsity of Massachusetts at Amberst, INRIA Sophia Antipolis, Sprint ATL, and Nortel Networks
ACM SIGMETRICS 2000, August 2000.



QoS at higher levels: QoS for Internet services, overlays

17.  Blanquer, J., Batchelli, A., Schauser, K., and Wolski, R., Quorum: Flexible Quality of Service for Internet Services, USENIX 2nd Symposium on Networked Systems Design and Implementation (NSDI), May 2-4, 2005 [pdf].

18.  Lakshminarayanan Subramanian, Ion Stoical, Hari Balakrishnan, Randy Katz, OverQoS: An Overlay Based Architecture for Enhancing Internet QoS,  NSDI’04. [pdf]



[Project: midterm presentation, three-page midterm report]





QoS for data storage

19.  Using Utility to Provision Storage Systems, John D. Strunk, Eno Thereska, Christos Faloutsos, Gregory R. Ganger, FAST’08 [pdf]

20.  Joel Wu, Scott A. Brandt, Providing Quality of Service Support in Object-Based File System, 24th IEEE Conference on Mass Storage Systems and Technologies (MSST 2007).



More QoS for data storage

21.  Triage: performance differentiation for storage systems using adaptive control, Magnus Karlsson, Christos Karamanolis and Xiaoyun Zhu, ACM Transactions on Storage, Vol 1, No 4, pp. 458-480, November 2005.  [link]

22.  Lan Huang, Gang Peng, and Tzi-cker Chiueh. Multidimensional Storage Virtualization. SIGMETRICS'04, New York, June 2004. [pdf]


More links:

23.  UCSD projects [link]

24.  Zoran Dimitrijevic, Quality-of-Service Scheduling in Storage Systems.
Ph.D. Dissertation, UCSB, June 2004. [pdf]

25.  Lin Qiao, Balakrishna R. Iyer, Divyakant Agrawal, Amr El Abbadi: Automated Storage Management with QoS Guarantee in Large-scale Virtualized Storage Systems. IEEE Data Eng. Bull. 29(3): 47-54 (2006) [link]

26.  Façade: Virtual storage devices with performance guarantees, Christopher Lumb, Arif Merchant and Guillermo Alvarez, FAST'03, pp. 131-144, March/April 2003, San Francisco, CA. [pdf]

27.  Polus: Growing Storage QoS Management Beyond a  “Four-year Old Kid”, Sandeep Uttamchandani Kaladhar Voruganti Sudarshan Srinivasan, USENIX’03 [pdf]

28.  QoS Provisioning Framework for an OSD-Based Storage System, 22nd IEEE Conference on Mass Storage Systems and Technologies [pdf]

29.  Efficient and Adaptive Proportional Share I/O Scheduling, Gulati, Ajay; Merchant, Arif; Uysal, Mustafa; Varman, Peter J., HPL-2007-186, 20071120 [link]

30.  J. Chuang and M. Sirbu, Distributed Network Storage with Quality-of-Service Guarantees.  Journal of Network and Computer Applications 23(3): 163-185, July 2000. Also in Proceedings of the Internet Society INET'99 Conference, San Jose CA, June 22-25 1999. [html, pdf]



UBC closed




Miscellaneous: Quality of Experience,  Middleware vs. native OS support

31.  Quantifying Skype user satisfaction, Kuan-Ta Chen, Chun-Ying Huang, Polly Huang, Chin-Laung Lei:  SIGCOMM 2006 [link]

32.  Middleware versus Native OS Support: Architectural Considerations for Supporting Multimedia Applications, Prashant Shenoy, Saif Hasan, Purushottam Kulkarni, Krithi Ramamritham, RTAS’02 [link]


§    More Skype-related papers



Miscellaneous: Multimedia applications.

33.  Cloud Control with Distributed Rate Limiting, Barath Raghavan, Kashi Vishwanath, Sriram Ramabhadran, Kenneth Yocum, Alex Snoeren, SIGCOMM’07

34.  On the Impact of Policing and Rate Guarantees in Diff-Serv Networks: A Video Streaming Application Perspective W. Ashmawi, R. Guerin, S. Wolf, M. Pinson, SIGCOMM’01




[Project: presentations and wrap-up




1.      Zygaria: Storage performance as a managed resource (PDF)

2.      Polus: Growing Storage QoS Management Beyond a “4-Year Old Kid”

3.      Hippodrome: Running Circles Around Storage Administration. Eric Anderson, Michael Hobbs, Kimberly Keeton, Susan Spence, Mustafa Uysal, and Alistair Veitch. USENIX FAST' 02.

4.      G. Alvarez, E. Borowsky, S. Go, T. Romer, R. Becker-Szendy, R. Golding, A. Merchant, M. Spasojevic, A. Veitch, and J. Wilkes. Minerva: an automated resource provisioning tool for large-scale storage systems, ACM Transactions on Computer Systems 19(4):483-518, Nov. 2001

5.      W. Jin, J. Chase, and J. Kaur. Interposed Proportional Sharing for a Storage Service Utility, Pro ceedings of the ACM Sigmetrics (SIGMETRICS'04), New York, June 2004.

Other papers:

6.      P-Clock: An Arrival Curve Based Approach for QoS Guarantees in Shared Storage Systems, A. Gulati, A. Merchant, P. Varman, ACM International Conference on Measurement and Modeling of Computer Systems , (SIGMETRICS 2007), June, 2007 (pdf)


1.      Probabilistic congestion control for non-adaptable flows, Jorg Widmer, Martin Mauve, Jan Peter Damm, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video (NOSSDAV 2002), paper

2.      Networked games - a QoS-sensitive application for QoS-insensitive users?, Tristan Henderson and Saleem Bhatti, ACM SIGCOMM 2003 Revisiting IP QOS workshop, August 2003. paper


1.      MapReduce: simplified data processing on large clusters, Jeffrey Dean, Sanjay Ghemawat, Communications of the ACM 51(1), January 2008.