ABSTRACT
This paper develops and evaluates new share-based scheduling algorithms for differentiated service quality in network services, such as network storage servers. This form of resource control makes it possible to share a server among multiple request flows with probabilistic assurance that each flow receives a specified minimum share of a server's capacity to serve requests. This assurance is important for safe outsourcing of services to shared utilities such as Storage Service Providers.Our approach interposes share-based request dispatching on the network path between the server and its clients. Two new scheduling algorithms are designed to run within an intermediary (e.g., a network switch), where they enforce fair sharing by throttling request flows and reordering requests; these algorithms are adaptations of Start-time Fair Queuing (SFQ) for servers with a configurable degree of internal concurrency. A third algorithm, Request Windows (RW), bounds the outstanding requests for each flow independently; it is amenable to a decentralized implementation, but may restrict concurrency under light load. The analysis and experimental results show that these new algorithms can enforce shares effectively when the shares are not saturated, and that they provide acceptable performance isolation under saturation. Although the evaluation uses a storage service as an example, interposed request scheduling is non-intrusive and views the server as a black box, so it is useful for complex services with no internal support for differentiated service quality.
- Tarek F. Abdelzaher, Kang G. Shin, and Nina Bhatti. Performance guarantees for Web server end-systems: A control-theoretical approach. IEEE Transactions on Parallel and Distributed Systems, To appear 2001.]] Google ScholarDigital Library
- Darrell C. Anderson and Jeffrey S. Chase. Fstress: A flexible network file service benchmark. Technical Report CS-2002-01, Duke University, Department of Computer Science, January 2002.]]Google Scholar
- Darrell C. Anderson, Jeffrey S. Chase, and Amin M. Vahdat. Interposed request routing for scalable network storage. ACM Transactions on Computer Systems (TOCS) special issue: selected papers from the Fourth Symposium on Operating System Design and Implementation (OSDI), October 2000, 20(1), February 2002.]] Google ScholarDigital Library
- Mohit Aron. Differentiated and Predictable Quality of Service in Web Server Systems. PhD thesis, Department of Computer Science, Rice University, October 2000.]] Google ScholarDigital Library
- Gaurav Banga, Peter Druschel, and Jeffrey C. Mogul. Resource containers: A new facility for resource management in server systems. In Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI), February 1999.]] Google ScholarDigital Library
- Jon C. R. Bennett and Hui Zhang. wf2q: Worst-case fair weighted fair queuing. In Proceedings of IEEE INFOCOM'96, San Francisco, CA, March 1996.]] Google ScholarDigital Library
- Jon C. R. Bennett and Hui Zhang. Hierarchical packet fair queueing algorithms. IEEE/ACM Transactions on Networking, 5(5):675--689, October 1997.]] Google ScholarDigital Library
- Josep M. Blanquer and Banu Ozden. Fair queuing for aggregated multiple links. In ACM SIGCOMM, August 2001.]] Google ScholarDigital Library
- John Bruno, Jose Brustoloni, Banu Ozden, and Abraham Silberschatz. Disk scheduling with quality of service guarantees. In IEEE International Conference on Multimedia Computing and Systems (ICMCS '99), June 1999.]] Google ScholarDigital Library
- David D. Chambliss, Guillermo A. Alvarez, Prashant Pandey, Divyesh Jadav, and Tzongyu P. Lee Jian Xu, Ram Menon. Performance virtualization for large-scale storage systems. In 22nd International Symposium on Reliable Distributed Systems (SRDS '03), October 2003.]]Google Scholar
- Abhishek Chandra, Micah Adler, Pawan Goyal, and Prashant Shenoy. Surplus fair scheduling: A proportional-share CPU scheduling algorithm for symmetric multiprocessors. In Fourth Symposium on Operating System Design and Implementation (OSDI), October 2000.]] Google ScholarDigital Library
- Abhishek Chandra, Micah Adler, and Prashant Shenoy. Deadline fair scheduling: Bridging the theory and practice of proportionate fair scheduling in multiprocessor systems. In Seventh Real-Time Technology and Applications Symposium (RTAS '01), May 2001.]] Google ScholarDigital Library
- Jeffrey S. Chase, Darrell C. Anderson, Prachi N. Thakar, Amin M. Vahdat, and Ronald P. Doyle. Managing Energy and Server Resources in Hosting Centers. In Proceedings of the 18th ACM Symposium on Operating System Principles (SOSP), pages 103--116, October 2001.]] Google ScholarDigital Library
- Alan Demers, Srinivasan Keshav, and Scott Shenker. Analysis and simulation of a fair queuing algorithm. ACM SIGCOMM 89, 19(4):2--12, August 19-22, 1989.]] Google ScholarDigital Library
- Ron Doyle, Jeffrey S. Chase, Omer Asad, Wei Jin, and Amin Vahdat. Model-based resource provisioning in a Web service utility. In Proceedings of the Fourth Symposium on Internet Technologies and Systems (USITS), Seattle, Washington, USA, March 2003.]] Google ScholarDigital Library
- Boris Dragovic, Keir Fraser, Steve Hand, Tim Harris, Alex Ho, Ian Pratt, Andrew Warfield, Paul Barham, and Rolf Neugebauer. Xen and the Art of Virtualization. In Proceedings of the ACM Symposium on Operating Systems Principles, October 2003.]] Google ScholarDigital Library
- S. Jamal Golestani. A self-clocked fair queuing scheme for broadband applications. In Proceedings of the 13th Annual Joint Conference of the IEEE Computer and Communications Societies on Networking for Global Communciation. Volume 2, pages 636--646, Los Alamitos, CA, USA, June 1994. IEEE Computer Society Press.]]Google Scholar
- P. Goyal, X. Guo, and H. Vin. A hierarchical CPU scheduler for multimedia operating systems. In Proceedings of Operating System Design and Implementation (OSDI'96), Seattle, pages 107--122, October 1996.]] Google ScholarDigital Library
- Pawan Goyal and Harrick M. Vin. Generalized guaranteed rate scheduling algorithms: a framework. IEEE/ACM Transactions on Networking, 5(4):561--571, August 1997.]] Google ScholarDigital Library
- Pawan Goyal, Harrick M. Vin, and Haichen Chen. Start-time fair queuing: A scheduling algorithm for integrated services packet switching networks. IEEE/ACM Transactions on Networking, 5(5):690--704, October 1997.]] Google ScholarDigital Library
- Lan Huang, Gang Peng, and Tzi cker Chiueh. Multi-dimensional storage virtualization. In Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS/Performance '04), June 2004.]] Google ScholarDigital Library
- Zhen Liu, Mark Squillante, and Joel Wolf. On maximizing service-level-agreement profits. In Proceedings of the 3rd ACM Conference on Electronic Commerce (EC-01), pages 213--223, New York, October 14-17 2001. ACM Press.]] Google ScholarDigital Library
- Christopher Lumb, Arif Merchant, and Guillermo A. Alvarez. Facade: Virtual storage devices with performance guarantees. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies, San Francisco, CA, March 2003. ACM Press.]] Google ScholarDigital Library
- Kostas Magoutis, Salimah Addetia, Alexandra Fedorova, Margo Seltzer, Jeff Chase, Richard Kisley, Andrew Gallatin, Rajiv Wickremisinghe, and Eran Gabber. Structure and performance of the Direct Access File System. In USENIX Technical Conference, pages 1--14, June 2002.]] Google ScholarDigital Library
- Abhay K. Parekh and Robert G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: the single-node case. IEEE/ACM Transactions on Networking, 1(3):344--357, June 1993.]] Google ScholarDigital Library
- Prashant J. Shenoy and Harrick M. Vin. Cello: A disk scheduling framework for next generation operating systems. In Proceedings of the 1998 ACM Sigmetrics Conference on Measurement and Modeling of Computer Systems, pages 44--55, 1998.]] Google ScholarDigital Library
- Dimitrios Stiliadis and Anujan Varma. Latency-rate servers: a general model for analysis of traffic scheduling algorithms. IEEE/ACM Transactions on Networking, 6(5):611--624, October 1998.]] Google ScholarDigital Library
- Bhuvan Urgaonkar, Prashant Shenoy, and Timothy Roscoe. Resource overbooking and application profiling in shared hosting platforms. In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI), Boston, MA, USA, December 2002.]] Google ScholarDigital Library
- Carl A. Waldspurger. Memory Resource Management in VMware ESX Server. In Symposium on Operating Systems Design and Implementation, December 2002.]] Google ScholarDigital Library
- Carl A. Waldspurger and William E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management. In Proceedings of the First Symposium on Operating Systems Design and Implementation (OSDI), pages 1--11, November 1994.]] Google ScholarDigital Library
- John Wilkes. Traveling to Rome: QoS specifications for automated storage system management. Lecture Notes in Computer Science, 2092:75--92, 2001.]] Google ScholarDigital Library
- Kenneth G. Yocum, Darrell C. Anderson, Jeffrey S. Chase, and Amin Vahdat. Anypoint: Extensible transport switching on the edge. In Proceedings of the Fourth USENIX Symposium on Internet Technologies and Systems (USITS), March 2003.]] Google ScholarDigital Library
- Lixia Zhang. Virtual Clock: A new traffic control algorithm for packet switching networks. In SIGCOMM '90 Symposium: Communications Architectures and Protocols, pages 19--29, September 1990.]] Google ScholarDigital Library
Index Terms
- Interposed proportional sharing for a storage service utility
Recommendations
Interposed proportional sharing for a storage service utility
This paper develops and evaluates new share-based scheduling algorithms for differentiated service quality in network services, such as network storage servers. This form of resource control makes it possible to share a server among multiple request ...
Weighted fair sharing for dynamic virtual clusters
SIGMETRICS '08In a shared server infrastructure, a scheduler controls how quantities of resources are shared over time in a fair manner across multiple, competing consumers. It should support wide (parallel) requests for variable-sized pool of resources, provide ...
Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computingWe present Grouped Distributed Queues (GDQ), the first proportional share scheduler for multiprocessor systems that scales well with a large number of processors and processes. GDQ uses a distributed queue architecture, and achieves accurate ...
Comments