{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:09:13Z","timestamp":1761401353847,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,3,1]],"date-time":"2007-03-01T00:00:00Z","timestamp":1172707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMETRICS Perform. Eval. Rev."],"published-print":{"date-parts":[[2007,3]]},"abstract":"<jats:p>In queueing theory, it has been known for a long time that the scheduling policy used in a system greatly impacts user-perceived performance. For example, it has been proven in the 1960's that size-based scheduling policies that give priority to short jobs are optimal with respect to mean response time. Yet, virtually no systems today implement these policies. One reason is that real systems are significantly more complex than a theoretical M\/M\/1 or M\/G\/1 queue and it is not obvious how to implement some of these policies in practice. Another reason is that there is a fear that the big jobs will \"starve\", or be treated unfairly as compared to Processor-Sharing (PS). In this article we show, using two important real world applications, that size-based scheduling can be used in practice to greatly improve mean response times in real systems, without causing unfairness or starvation. The two applications we consider are connection scheduling in web servers and packet scheduling in network routers.<\/jats:p>","DOI":"10.1145\/1243401.1243407","type":"journal-article","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T14:37:16Z","timestamp":1181140636000},"page":"21-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Scheduling in practice"],"prefix":"10.1145","volume":"34","author":[{"given":"Ernst W.","family":"Biersack","sequence":"first","affiliation":[{"name":"Institut Eurecom, Sophia-Antipolis, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bianca","family":"Schroeder","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Urvoy-Keller","sequence":"additional","affiliation":[{"name":"Institut Eurecom, Sophia-Antipolis, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,3]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"523","volume-title":"Journal of Applied Probability","author":"Aalto S.","year":"2006","unstructured":"S. Aalto and U. Ayesta . On the non-optimality of the fb discipline for imrl service times . Journal of Applied Probability , pages 523 -- 534 , 2006 . S. Aalto and U. Ayesta. On the non-optimality of the fb discipline for imrl service times. Journal of Applied Probability, pages 523--534, 2006."},{"key":"e_1_2_1_2_1","volume-title":"Proc. IEEE INFOCOM","author":"Avrachenkov K.","year":"2004","unstructured":"K. Avrachenkov , U. Ayesta , P. Brown , and N. Nyberg . Differentiation between short and long tcp flows: Predictability of the response time . In Proc. IEEE INFOCOM , March 2004 . K. Avrachenkov, U. Ayesta, P. Brown, and N. Nyberg. Differentiation between short and long tcp flows: Predictability of the response time. In Proc. IEEE INFOCOM, March 2004."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019292504731"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/378420.378792"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/277851.277897"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1215956.1215965"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of INET","author":"Claffy K.","year":"1998","unstructured":"K. Claffy , G. Miller , and K. Thompson . The nature of the beast: Recent traffic measurements from an internet backbone . In Proceedings of INET , July 1998 . K. Claffy, G. Miller, and K. Thompson. The nature of the beast: Recent traffic measurements from an internet backbone. In Proceedings of INET, July 1998."},{"key":"e_1_2_1_8_1","volume-title":"Operating Systems Theory","author":"Coffman E. G.","year":"1973","unstructured":"E. G. Coffman and P. J. Denning . Operating Systems Theory . Prentice-Hall Inc ., 1973 . E. G. Coffman and P. J. Denning. Operating Systems Theory. Prentice-Hall Inc., 1973."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2005.845544"},{"key":"e_1_2_1_10_1","volume-title":"The Fifth Workshop of Mathematical Performance Modeling and Analysis (MAMA 2003","author":"Feng H.","year":"2000","unstructured":"H. Feng and M. Misra . Mixed scheduling disciplines for network flows . In The Fifth Workshop of Mathematical Performance Modeling and Analysis (MAMA 2003 ), San Diego, California, USA , June 2000 . H. Feng and M. Misra. Mixed scheduling disciplines for network flows. In The Fifth Workshop of Mathematical Performance Modeling and Analysis (MAMA 2003), San Diego, California, USA, June 2000."},{"key":"e_1_2_1_12_1","volume-title":"1st workshop on Wireless Network Measurements (Winmee), Riva Del Garda","author":"Franceschinis M.","year":"2005","unstructured":"M. Franceschinis , M. Mellia , M. Meo , and M. Munaf . Measuring TCP over wifi: A real case . In 1st workshop on Wireless Network Measurements (Winmee), Riva Del Garda , Italy , 2005 . M. Franceschinis, M. Mellia, M. Meo, and M. Munaf. Measuring TCP over wifi: A real case. In 1st workshop on Wireless Network Measurements (Winmee), Riva Del Garda, Italy, 2005."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2005.30"},{"key":"e_1_2_1_14_1","volume-title":"Proc. of IEEE MASCOTS","author":"Gong M.","year":"2004","unstructured":"M. Gong and C. Williamson . Simulation evaluation of hybrid SRPT scheduling policies . In Proc. of IEEE MASCOTS , 2004 . M. Gong and C. Williamson. Simulation evaluation of hybrid SRPT scheduling policies. In Proc. of IEEE MASCOTS, 2004."},{"key":"e_1_2_1_15_1","volume-title":"SPIE ITCOM'2002: Scalability and Traffic Control in IP Networks","author":"Guo L.","year":"2002","unstructured":"L. Guo and I. Matta . Differentiated control of web traffic: A numerical analysis . In SPIE ITCOM'2002: Scalability and Traffic Control in IP Networks , August 2002 . L. Guo and I. Matta. Differentiated control of web traffic: A numerical analysis. In SPIE ITCOM'2002: Scalability and Traffic Control in IP Networks, August 2002."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.825799"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/762483.762486"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1080148.1080155"},{"key":"e_1_2_1_19_1","volume-title":"Queuing Systems, Volume II: Computer Applications","author":"Kleinrock L.","year":"1976","unstructured":"L. Kleinrock . Queuing Systems, Volume II: Computer Applications . Wiley , New York , 1976 . L. Kleinrock. Queuing Systems, Volume II: Computer Applications. Wiley, New York, 1976."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-5316(01)00046-3"},{"key":"e_1_2_1_21_1","volume-title":"Proc. of IEEE MASCOTS","author":"Lu D.","year":"2004","unstructured":"D. Lu , H. Sheng , and P. A. Dinda . Size-based scheduling policies with inaccurate scheduling information . In Proc. of IEEE MASCOTS , 2004 . D. Lu, H. Sheng, and P. A. Dinda. Size-based scheduling policies with inaccurate scheduling information. In Proc. of IEEE MASCOTS, 2004."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/977401.978097"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.78"},{"key":"e_1_2_1_24_1","volume-title":"Proc. of the 18th International Teletraffic Congress (ITC-18)","author":"Murta C. D.","year":"2003","unstructured":"C. D. Murta and T. P. Corlassoli . Fastest connection first: A new scheduling policy for web servers . In Proc. of the 18th International Teletraffic Congress (ITC-18) , 2003 . C. D. Murta and T. P. Corlassoli. Fastest connection first: A new scheduling policy for web servers. In Proc. of the 18th International Teletraffic Congress (ITC-18), 2003."},{"key":"e_1_2_1_25_1","volume-title":"The foreground-background queue: a survey. Technical report, under submission","author":"Nuyens M.","year":"2006","unstructured":"M. Nuyens and A. Wierman . The foreground-background queue: a survey. Technical report, under submission , 2006 . M. Nuyens and A. Wierman. The foreground-background queue: a survey. Technical report, under submission, 2006."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.392383"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.2005.1383435"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/781027.781055"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005686.1005702"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/824470.825318"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005686.1005704"},{"key":"e_1_2_1_33_1","volume-title":"Feb.","author":"Salvatori A.","year":"2005","unstructured":"A. Salvatori . LAS scheduler implementation and performance analysis, institut eurecom , Feb. 2005 . A. Salvatori. LAS scheduler implementation and performance analysis, institut eurecom, Feb. 2005."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.13.7.466"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1125274.1125276"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.11"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.78"},{"key":"e_1_2_1_38_1","volume-title":"Proc. of Usenix NSDI","author":"Schroeder B.","year":"2006","unstructured":"B. Schroeder , A. Wierman , and M. Harchol-Balter . Open vs. closed systems: A cautionary tale . In Proc. of Usenix NSDI , 2006 . B. Schroeder, A. Wierman, and M. Harchol-Balter. Open vs. closed systems: A cautionary tale. In Proc. of Usenix NSDI, 2006."},{"key":"e_1_2_1_39_1","unstructured":"Standard Performance Evaluation Corporation. SPECweb99. http:\/\/www.specbench.org\/osg\/web99\/.  Standard Performance Evaluation Corporation. SPECweb99. http:\/\/www.specbench.org\/osg\/web99\/."},{"key":"e_1_2_1_40_1","volume-title":"February","author":"Transaction Processing Performance Council","year":"2002","unstructured":"Transaction Processing Performance Council . TPC benchmark W (web commerce). Number Revision 1.8 , February 2002 . Transaction Processing Performance Council. TPC benchmark W (web commerce). Number Revision 1.8, February 2002."},{"key":"e_1_2_1_41_1","unstructured":"G. Trent and M. Sake. WebStone: The first generation in HTTP server benchmarking http: - \/\/www.mindcraft.com\/webstone\/paper.html.  G. Trent and M. Sake. WebStone: The first generation in HTTP server benchmarking http: - \/\/www.mindcraft.com\/webstone\/paper.html."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00061-0"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/781027.781057"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064212.1064238"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064212.1064236"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2004.826280"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135866"}],"container-title":["ACM SIGMETRICS Performance Evaluation Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1243401.1243407","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1243401.1243407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:47:49Z","timestamp":1750258069000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1243401.1243407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,3]]}},"alternative-id":["10.1145\/1243401.1243407"],"URL":"https:\/\/doi.org\/10.1145\/1243401.1243407","relation":{},"ISSN":["0163-5999"],"issn-type":[{"type":"print","value":"0163-5999"}],"subject":[],"published":{"date-parts":[[2007,3]]},"assertion":[{"value":"2007-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}