Mor Harchol-Balter
Abstract
Is it possible to reduce the expected response time of every request at a web server, simply by changing the order in which we schedule the requests? That is the question we ask in this paper.This paper proposes a method for improving the performance of web servers servicing static HTTP requests. The idea is to give preference to requests for small files or requests with short remaining file size, in accordance with the SRPT (Shortest Remaining Processing Time) scheduling policy.The implementation is at the kernel level and involves controlling the order in which socket buffers are drained into the network. Experiments are executed both in a LAN and a WAN environment. We use the Linux operating system and the Apache and Flash web servers.Results indicate that SRPT-based scheduling of connections yields significant reductions in delay at the web server. These result in a substantial reduction in mean response time and mean slowdown for both the LAN and WAN environments. Significantly, and counter to intuition, the requests for large files are only negligibly penalized or not at all penalized as a result of SRPT-based scheduling.
- Almeida, J., Dabu, M., Manikutty, A., and Cao, P. 1998. Providing differentiated quality-of-service in Web hosting services. In Proceedings of the First Workshop on Internet Server Performance.Google Scholar
- Almesberger, W. 1999. Linux network traffic control---implementation overview. White paper available at http://diffserv.sourceforge.net/.Google Scholar
- Almesberger, W., Salim, J. H., and Kuznetsov, A. 1999. Differentiated services on Linux. White paper available at http://lrcwww.epfl.ch/linux-diffserv/.Google Scholar
- Apache. 2001. Apache web server. http://httpd.apache.org.Google Scholar
- Arlitt, M., Friedrich, R., and Jin, T. 1999. Workload characterization of a web proxy in a cable modem environment. ACM Perform. Eval. Rev. 27, 2 (August), 25--36. Google Scholar
- Banga, G. and Druschel, P. 1999. Measuring the capacity of a web server under realistic loads. World Wide Web 2, 1--2, 69--83. Google Scholar
- Banga, G., Druschel, P., and Mogul, J. 1998. Better operating system features for faster network servers. ACM SIGMETRICS Performance Evaluation Review 26, 3, 23--30. Google Scholar
- Bansal, N. and Harchol-Balter, M. 2001. Analysis of SRPT scheduling: Investigating unfairness. In Proceedings of ACM SIGMETRICS '01. 279--290. Google Scholar
- Barford, P. and Crovella, M. E. 1998. Generating representative Web workloads for network and server performance evaluation. In Proceedings of SIGMETRICS '98. 151--160. Google Scholar
- Bender, M., Chakrabarti, S., and Muthukrishnan, S. 1998. Flow and stretch metrics for scheduling continuous job streams. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. Google Scholar
- Bestavros, A., Carter, R. L., Crovella, M. E., Cunha, C. R., Heddaya, A., and Mirdad, S. A. 1995. Application-level document caching in the Internet. In Proceedings of the Second International Workshop on Services in Distributed and Networked Environments (SDNE'95). Google Scholar
- Braun, H. and Claffy, K. 1994. Web traffic characterization: an assessment of the impact of caching documents from NCSA's Web server. In Proceedings of the Second International WWW Conference.Google Scholar
- Cockcroft, A. 1996. Watching your web server. The Unix Insider at http://www.unixinsider.com.Google Scholar
- Crovella, M. and Bestavros, A. 1997. Self-similarity in World Wide Web traffic: Evidence and possible causes. IEEE/ACM Trans. Netw. 5, 6 (December), 835--846. Google Scholar
- Crovella, M., Frangioso, R., and Harchol-Balter, M. 1999. Connection scheduling in web servers. In USENIX Symposium on Internet Technologies and Systems. Google Scholar
- Crovella, M., Taqqu, M. S., and Bestavros, A. 1998. Heavy-tailed probability distributions in the World Wide Web. In A Practical Guide To Heavy Tails. Chapman & Hall, New York, 3--26. Google Scholar
- Downey, A. B. 1997. A parallel workload model and its implications for processor allocation. In Proceedings of High Performance Distributed Computing. 112--123. Google Scholar
- Druschel, P. and Banga, G. 1996. Lazy receiver processing (LRP): A network subsystem architecture for server systems. In Proceedings of OSDI '96. 261--275. Google Scholar
- Feldmann, A.1999. Web performance characteristics. IETF plenary Nov. http://www.research. att.com/∼anja/feldmann/papers.html.Google Scholar
- Gwertzman, J. and Seltzer, M. 1994. The case for geographical push-caching. In Proceedings of HotOS '94. Google Scholar
- Harchol-Balter, M. and Downey, A. 1997. Exploiting process lifetime distributions for dynamic load balancing. ACM Trans. Comput. Syst. 15, 3, 253--285. Google Scholar
- Harchol-Balter, M., Schroeder, B., Bansal, N., and Agrawal, M. 2000. Implementation of SRPT scheduling in web servers. Tech. Rep. CMU-CS-00-170.Google Scholar
- ITA. 2002. The internet traffic archives. Available at http://town.hall.org/Archives/pub/ITA/.Google Scholar
- Kaashoek, M., Engler, D., Wallach, D., and Ganger, G. 1996. Server operating systems. In SIGOPS European Workshop '96. 141--148. Google Scholar
- Krishnamurthy, B. and Rexford, J. 2001. Web Protocols and Practice: HTTP/1.1, Networking Protocols, Caching, and Traffic Measurement. Addison-Wesley. Google Scholar
- Little, J. 1961. A proof of the theorem L = λW. Operations Research 9, 383--387.Google Scholar
- Maggs, B. 2001. Personal communication with Vice President of Research, Akamai Technologies, Bruce Maggs.Google Scholar
- Manley, S. and Seltzer, M. 1997. Web facts and fantasy. In Proceedings of the 1997 USITS. Google Scholar
- Microsoft. 2001. The arts and science of Web server tuning with internet information services 5.0. Microsoft TechNet---Insights and Answers for IT Professionals: At http://www.microsoft. com/technet/.Google Scholar
- Mogul, J. C. 1995. Network behavior of a busy Web server and its clients. Tech. Rep. 95/5, Digital Western Research Laboratory. October.Google Scholar
- NISTNet. 2002. National institute of standards and technology. http://snad.ncsl.nist.gov/itg/nistnet/.Google Scholar
- Padmanabhan, V. N. and Mogul, J. 1995. Improving HTTP latency. Comput. Netw. ISDN Syst. 28, 25--35. Google Scholar
- Pai, V. S., Druschel, P., and Zwaenepoel, W. 1999. Flash: An efficient and portable Web server. In Proceedings of USENIX 1999. Google Scholar
- Radhakrishnan, S. 1999. Linux---advanced networking overview version 1. Available at http://qos.ittc.ukans.edu/howto/.Google Scholar
- Rizzo, L. 1997. Dummynet: a simple approach to the evaluation of network protocols. ACM Comput. Commun. Rev. 27, 1. Google Scholar
- Roberts, J. and Massoulie, L. 1998. Bandwidth sharing and admission control for elastic traffic. In ITC Specialist Seminar.Google Scholar
- Schrage, L. E. and Miller, L. W. 1966. The queue M/G/1 with the shortest remaining processing time discipline. Operations Research 14, 670--684.Google Scholar
- Silberschatz, A., Galvin, P., and Gagne, G. 2002. Operating System Concepts, Sixth Edition. John Wiley & Sons. Google Scholar
- Stallings, W. 2001. Operating Systems, Fourth Edition. Prentice Hall.Google Scholar
Index Terms
- Size-based scheduling to improve web performance
Recommendations
Web servers under overload: How scheduling can help
This article provides a detailed implementation study on the behavior of web serves that serve static requests where the load fluctuates over time (transient overload). Various external factors are considered, including WAN delays and losses and ...
Improving peer-to-peer performance through server-side scheduling
We show how to significantly improve the mean response time seen by both uploaders and downloaders in peer-to-peer data-sharing systems. Our work is motivated by the observation that response times are largely determined by the performance of the peers ...
On scalable and locality-aware web document sharing
Scalable web services and architectureWe propose a scalable Web document sharing infrastructure model called Browsers-Aware Proxy Server. In this design, a proxy server connecting to a group of networked clients maintains an index file of data objects of all clients' browser caches. If a ...
Comments