Fairness and efficiency in web server protocols

ABSTRACT

We consider the problem of designing a preemptive protocol that is both fair and efficient when one is only concerned with the sojourn time of the job and not intermediate results. Our Fair Sojourn Protocol (FSP) is both efficient, in a strong sense (similar to the shortest remaining processing time protocol: SRPT), and fair, in the sense of guaranteeing that it weakly outperforms processor sharing (PS) for every job on any sample path.Our primary motivation is web serving in which the standard protocol is PS, while recent work proposes using SRPT or variants. Our work suggests both a framework in which to evaluate proposed protocols and an attractive new protocol, FSP.

REFERENCES

• 1: Nikhil Bansal , Mor Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.279-290, June 2001, Cambridge, Massachusetts, United States
• 2: Michael A. Bender , Soumen Chakrabarti , S. Muthukrishnan, Flow and stretch metrics for scheduling continuous job streams, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.270-279, January 25-27, 1998, San Francisco, California, United States
• 3: Ludmila Cherkasova, Scheduling Strategy to improve Response Time for Web Applications, Proceedings of the International Conference and Exhibition on High-Performance Computing and Networking, p.305-314, April 21-23, 1998
• 4: Hervé Crès , Hervé Moulin, Scheduling with Opting Out: Improving upon Random Priority, Operations Research, v.49 n.4, p.565-577, July 2001 [doi>10.1287/opre.49.4.565.11224]
• 5: A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. Journal of Internetworking, 1(1):3--26, Jan. 1990.
• 6: M. Harchol-Balter, N. Bansal, B. Schroeder, and M. Agrawal. Size-based scheduling to improve web performance. Mimeo, CMU, 2001.
• 7: E. Modiano. Scheduling algorithms for message transmission over a satellite broadcast system. In Proceedings of IEEE MILCOM'97, pages 628---634, 1997.
• 8: E. Modiano, Scheduling packet transmissions in a multi-hop packet switched network based on message length, Proceedings of the 6th International Conference on Computer Communications and Networks, p.350, September 22-25, 1997
• 9: H. Moulin. Axioms of Cooperative Decision Making. Cambridge University Press, New York, 1991.
• 10: H. Moulin. Axiomatic cost and surplus-sharing. In Arrow, Sen, and Suzumura, editors, Handbook of Social Choice and Welfare. North-Holland, New York, 2002.
• 11: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 12: L. Schrage. A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 16:687---690, 1968.
• 13: D. Smith. A new proof of the optimality of the shortest remaining processing time discipline. Operations Research, 26:197---199, 1976.
• 14: W. Stallings. Operating Systems. Prentice Hall, 2nd edition, 1995.
• 15: Andrew S. Tanenbaum, Modern operating systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 16: H. P. Young. Cost Allocation: Methods, Principles and Applications. Elsevier Science, New York, 1985.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Performance

Keywords:
processor sharing, starvation avoidance