Statistical analysis of generalized processor sharing scheduling discipline

ABSTRACT

In this paper, we consider the problem of providing statistical guarantees (for example, on the tail distribution of delay) under the Generalized Processor Sharing (GPS) scheduling discipline. This work is motivated by, and is an extension of, Parekh and Gallager's deterministic study of GPS scheduling discipline with leaky-bucket token controlled sessions [PG93a,b, Parekh92]. Using the exponentially bounded burstiness (E.B.B.) process model introduced in [YaSi93a] as a source traffic characterization, we establish results that extend the deterministic study of GPS: for a single GPS server in isolation, we present statistical bounds on the tail distributions of backlog and delay for each session. In the network setting, we show that networks belonging to a broad class of GPS assignments, the so-called Consistent Relative Session Treatment (CRST) GPS assignments, are stable in a stochastic sense. In particular, we establish simple bounds on the tail distribution of backlog and delay for each session in a Rate Proportional Processor Sharing (RPPS) GPS network with arbitrary topology.

REFERENCES

• Brady68: P.T. Brady, A Statistical Analysis of On-Off Patterns in 16 Conversations, Bell System Technical Journal, Vol. 47, No. 1, Jan. 1968, pp. 73- 91.
• BD94: E. Buffet and N. G. Duffield, Exponential Upper Bounds via Martingales for Multiplexers with Markovlan Arrivals, J. Appl. Probabality., 1994. To appear.
• Chang93: C.S. Chang, Stability, Queue Length and Delay of Deterministic and Stochastic Queueing Networks, Preprint 1993. To appear in IEEE Transaction on Automatic Control.
• Cruz91a: R.L. Cruz, A Calculus for Network Delay, Part I: Network Elements in Isolation, IEEE Transaction on Information Theory, Vol. 37, No. 1, Jan. 1991, pp. 114-131.
• Cruz91b: R.L. Cruz, A Calculus for Network Delay, Part Ii: Network Analysis, IEEE Transaction on Information Theory, Vol. 37, No. 1, Jan. 1991, pp. 132-141.
• CSZ92: David D. Clark , Scott Shenker , Lixia Zhang, Supporting real-time applications in an Integrated Services Packet Network: architecture and mechanism, Conference proceedings on Communications architectures & protocols, p.14-26, August 17-20, 1992, Baltimore, Maryland, United States
• DKS89: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• EM92: Anwar I. Elwalid , Debasis Mitra, Effective bandwidth of general Markovian traffic sources and admission control of high speed networks, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.329-343, June 1993 [doi>10.1109/90.234855]
• GAN91: R. Gulrin, H. Ahmadi and M. Naghshineh, Equivalent Capacity and Its Application to Bandwidth Allocation in High-Speed Networks, IEEE Journal on Selected Areas in Cornrnunications, Vol. 9, No. 7, Sept.,1991, pp. 968-981.
• Go90: S. J. Golestani, A stop-and-go queueing framework for congestion management, Proceedings of the ACM symposium on Communications architectures & protocols, p.8-18, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• Go91: S.J. Golestani, Duration-Limited Statistical Multiplexing of Delay Sensitive Traffic in Packet Networks, In Proceedings of INFOCOMM '91, 1991.
• HL86: H. Heffes and D. M. Lucantoni, A Markov Modulated Characterization of Packetized Voice and Data Traffic and Related Statistical Multiplexer Performance, IEEE Journal on Selected Areas in Communications, SAC-4, 6, Sept., 1986, pp.856-868.
• HLP91: J. Hyman, A. Lazar and G. Pacifici, Real-Time Scheduling with Quality of Service Constraints, IEEE J. Select. Areas Commun., Vol. 9, No. 9, pp. 1052-1063, 1991.
• Kin70: J.F.C. Kingman, Inequalities in the Theory of Queues, J. Roy. Star. Soc., Series B, Vol. 32, 1970, pp.102-110.
• KKK90: C. Kalmanek, H. Kanakia and S. Keshav, Rate Controlled Servers for Very High-Speed Networks, In Proceedings of GlobalComm '90, pp. 300.3.1-300.3.9, 1990.
• KWC93: George Kesidis , Jean Walrand , Cheng-Shang Chang, Effective bandwidths for multiclass Markov fluids and other ATM sources, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.424-428, Aug. 1993 [doi>10.1109/90.251894]
• Kurose91: Jim Kurose, On computing per-session performance bounds in high-speed multi-hop computer networks, ACM SIGMETRICS Performance Evaluation Review, v.20 n.1, p.128-139, June 1992
• LNT94: Z. Liu, P. Nain and D. Towsley, Exponential Bounds for a Class of Stochastic Processes with Application to Call Admission Control in Networks. Submitted to the 33rd Conference on Decision and Control (CDC'93), February, 1994.
• MASKR88: B. Maglaris, D. Anastassiou, P. Sen, G. Karlsson and J. Robbin, Performance Models of Statistical Multiplexing in Packet Video Communications, IEEE Transaction on Communications, Vol. 36, No. 7, July, 1988, pp. 834-844.
• Parekh92: A.K. Parekh, A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks, Ph.D Thesis, Department of Electrical Engineering and Computer Science, MIT, February 1992.
• PG93a: 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]
• PG93b: Abhay K. Parekh , Robert G. Gallagher, A generalized processor sharing approach to flow control in integrated services networks: the multiple node case, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.137-150, April 1994 [doi>10.1109/90.298432]
• SW86: K. Sriram and W. Whitt, Characterizing Superposition Arrival Processes in Packet Multiplexers for Voice and Date, IEEE Journal on Selected Areas in Communications, SAC-4, 6, Sept., 1986, pp.833-846.
• VZF91: D. Verma, H. Zhang and D. Ferrari, Delay Jitter Control for Real-Time Traffic, in Proceedings of TriCom '91, pp. 35-43, 1991.
• YaSi93a: Opher Yaron , Moshe Sidi, Performance and stability of communication networks via robust exponential bounds, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.372-385, June 1993 [doi>10.1109/90.234858]
• YaSi93b: O. Yaron , M. Sidi, Generalized Processor Sharing Networks with Exponentially Bounded Burstiness Arrivals, submitted to Journal of High Speed Network, September, 1993.
• YKTH93: David Yates , James Kurose , Don Towsley , Michael G. Hluchyj, On per-session end-to-end delay distributions and the call admission problem for real-time applications with QOS requirements, Conference proceedings on Communications architectures, protocols and applications, p.2-12, September 13-17, 1993, San Francisco, California, United States
• ZF93: H. Zhang and D. Ferrari, Rate-Controlled Static-Priority Queueing, In Proceedingz of IEEE iNFOCOMM '93, pp. 227-236, April 1993.
• ZTK94: Z. Zhang , D. Towsley , J. Kurose, Statistical Analysis of Generalized Processor Sharing Scheduling Discipline, University of Massachusetts, Amherst, MA, 1995

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.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  G. Mathematics of Computing

General Terms:
Algorithms, Design, Performance