Mixed scheduling disciplines for network flows

ABSTRACT

We introduce a novel method to prove that the FBPS discipline has optimal mean sojourn time and mean slowdown ratio for DHR service time distributions in an M/G/1 queue. We then discuss the problems related to FBPS, and propose a new scheduling discipline to overcome these problems.

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: Liang Guo , Ibrahim Matta, Scheduling flows with unknown sizes: approximate analysis, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 3: L. Kleinrock , R. R. Muntz, Processor Sharing Queueing Models of Mixed Scheduling Disciplines for Time Shared System, Journal of the ACM (JACM), v.19 n.3, p.464-482, July 1972 [doi>10.1145/321707.321717]
• 4: L. Kleinrock, R. R. Muntz and J. Hsu, Tight bounds on average response time for processor-sharing models of time-shared computer systems, Information Processing 71, TA-2, 50--58, August 1971.
• 5: Adam Wierman, Nikhil Bansal and Mor Harchol-Balter, A note on comparing response times in the M/GI/1/FB and M/GI/1/PS queues, technique report CMU-CS-02-177, School of Computer Science, Carnegie Mellon University (Pittsburgh, PA 15213), September 2002.