Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-27T08:57:38.948Z Has data issue: false hasContentIssue false
  • English
  • Français

Bounds on the Mean Delay in Multiclass Queueing Networks under Shortfall-Based Priority Rules

Published online by Cambridge University Press:  27 July 2009

Sridhar Seshadri  and
Michael Pinedo
Sridhar Seshadri
Affiliation:
Department of Statistics and Operations Research & Operations Management Area, Leonard N. Stern School of Business, New York University, New York, New York 10012
Michael Pinedo
Affiliation:
Department of Statistics and Operations Research & Operations Management Area, Leonard N. Stern School of Business, New York University, New York, New York 10012
Get access Rights & Permissions [Opens in a new window]

Abstract

A significant amount of recent research has been focused on the stability of multiclass open networks of queues (MONQs). It has been shown that these networks may be unstable under various queueing disciplines even when at each one of the nodes the arrival rate is less than the service rate. Clearly, in such cases the expected delay and the expected number of customers in the system are infinite. In this paper we propose a new class of scheduling rules that can be used in multiclass queueing networks. We refer to this class as the stable shortfall-based priority (SSBP) rules. This SSBP class itself belongs to a larger class of rules, which we refer to as the shortfall-based priority (SBP) rules. SBP is a generalization of the standard non-preemptive priority rule in which customers of the same priority class are served first-come, first-served (FCFS). Rules from SBP can mimic FCFS as well as the so-called strict or head-of-the-line priority disciplines. We show that the use of any rule from the SSBP class ensures stability in a broad class of MONQs found in practice. We proceed with the construction of a sample path inequality for the work done by an SSBP server and show how this inequality can be used to derive upper bounds for the delay when service times are bounded. Bounds for the expected delay of each class of customers in an MONQ are then obtained under the assumptions that the external arrival processes have i.i.d. interarrival times, the routings are deterministic and the service times at each step of the route are bounded. In order to derive these bounds for the average delay in an MONQ we make use of some of the classical ideas of Kingman.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 12 , Issue 3 , July 1998 , pp. 329 - 350
Copyright
Copyright © Cambridge University Press 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Bertsekas, D. & Gallagher, R.G. (1992). Data networks. Englewood Cliffs, NJ: Prentice Hall.Google Scholar
2.Bramson, M. (1994). Instability of FIFO queueing networks. Annals of Applied Probability 4: 414–431.Google Scholar
3.Bramson, M. (1994). Instability of FIFO queueing networks with quick service times. Annals of Applied Probability 4: 693–718.Google Scholar
4.Bramson, M. (1996). Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks. Queueing Systems 23: 1–26.Google Scholar
5.Bramson, M. (1996). Convergence to equilibria for fluid models of FIFO queueing networks. Queueing Networks 22: 5–45.CrossRefGoogle Scholar
6.Buzacott, J.A. & Shanthikumar, J.G. (1993). Stochastic models of manufacturing systems. Englewood Cliffs, NJ: Prentice Hall.Google Scholar
7.Chang, C.-S. (1994). Stability, queue length, and delay of deterministic and stochastic queueing networks. IEEE Transactions on Automatic Control 39(5): 913–931.Google Scholar
8.Chang, C.S., Thomas, J.A., & Kiang, S.H. (1994). On the stability of open networks: A unified approach by stochastic dominance. Queueing Systems 15: 239–260.Google Scholar
9.Chen, H. & Yao, D.D. (1994). Stable priority disciplines for multiclass networks. In Glasserman, P., Sigman, K., & Yao, D.D. (eds.), Stochastic networks: Stability and rare events. New York: Springer.Google Scholar
10.Cobham, A. (1954). Priority assignment in waiting line problems. Operations Research 2: 70–76.Google Scholar
11.Cruz, R.L. (1991). A calculus for network delay, Part I: Network elements in isolation. IEEE Transactions on Information Theory 37(1): 114–131.CrossRefGoogle Scholar
12.Cruz, R.L. (1991). A calculus for network delay, Part II: Network analysis. IEEE Transactions on Information Theory 37(1): 132–141.Google Scholar
13.Cruz, R.L. & Liu, H. (1993). Single-server queues with loss: A formulation. Proceedings 1993 CISS, Johns Hopkins Univ.Google Scholar
14.Dai, J.G. (1994). On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models. Annals of Applied Probability 5: 49–77.Google Scholar
15.Dai, J.G. & Wang, Y. (1993). Nonexistence of Brownian models of certain multiclass queueing networks. Queueing Systems 13: 41–46.Google Scholar
16.Demers, A., Keshav, S., & Shenker, S. (1990). Analysis and simulation of a fair queueing algorithm. Internetworking: Research and Experience 1.Google Scholar
17.Gafni, E. & Bertsekas, D. (1984). Dynamic control of session input rates in communication networks. IEEE Transactions 29(10): 1009–1016.Google Scholar
18.Georgadis, L., Guerin, R., & Parekh, A. Optimal multiplexing on a single link: Delay and buffer requirements. [Unpublished manuscript], Yorktown Heights, NY: IBM TJ Watson Research Center.Google Scholar
19.Georgadis, L., Guerin, R., Peris, V., & Sivarajan, K.N. Efficient network provisioning based on per node traffic shaping. [Unpublished manuscript], Yorktown Heights, NY: IBM TJ Watson Research Center.Google Scholar
20.Greenberg, A. & Madras, N. (1992). How fair is fair queueing? Journal of the Association for Computing Machinery 39(3): 568–598.Google Scholar
21.Harrison, J.M. (1973). The heavy traffic approximation for single-server queues in series. Journal of Applied Probability 10: 613–629.Google Scholar
22.Harrison, J.M. & Nguyen, V. (1993). Brownian models of multiclass queueing networks: Current status and open problems. Queueing Systems: Theory and Applications 13: 5–40.CrossRefGoogle Scholar
23.Kelly, F.P. (1979). Reversibility and stochastic networks. New York: John Wiley.Google Scholar
24.Kingman, J.F.C. (1962). Some inequalities for the queue GI/G/1. Biometrika 49: 315–324.CrossRefGoogle Scholar
25.Kleinrock, L. (1976). Queueing systems. vol. 2: Computer applications. New York: John Wiley.Google Scholar
26.Kumar, P.R. & Seidman, T.I. (1990). Dynamic instabilities and stabilization methods in distributed real-time scheduling of manufacturing systems. IEEE Transactions on Automatic Control 35: 289–298.Google Scholar
27.Lu, S.H. & Kumar, P.R. (1991). Distributed scheduling based on due date and buffer priorities. IEEE Transactions on Automatic Control 36: 1406–1416.Google Scholar
28.Parekh, A.J. (1992). A generalized processor sharing approach to flow control in integrated service networks. Ph.D. thesis, MIT, Boston, MA.Google Scholar
29.Parekh, A J. & Gallagher, R.G. (1993a). A generalized processor sharing approach to flow control in integrated service networks: The single node case. IEEE/ACM Transactions on Networking 1(1): 344–357.Google Scholar
30.Parekh, A.J. & Gallagher, R.G. (1993b). A generalized processor sharing approach to flow control in integrated service networks: The multiple node case. Proceedings IEEE/INFOCOM '93: 521–530.Google Scholar
31.Perkins, J.R. & Kumar, P.R. (1989). Stable distributed real-time scheduling of manufacturing/assembly/disassembly systems. IEEE Transactions on Automatic Control AC-34: 139–148.Google Scholar
32.Seidman, T.I. (1993). First come, first served is unstable! [Manuscript], University of Maryland, Baltimore County.Google Scholar
33.Shanthikumar, J.G. & Yao, D.D. (1989). Stochastic monotonicity in general queueing networks. Journal of Applied Probability 26: 413–417.Google Scholar
34.Stidham, S. & El-Taha, M. (1995). Sample-path techniques in queueing theory. In Dshalalow, J.H. (ed.), Advances in queueing: Theory, methods, and open problems. Boca Raton, PL: CRC Press.Google Scholar
35.Wein, L.M. (1990). Optimal control of a two-station Brownian network. Mathematics of Operations Research 15(2): 215–242.Google Scholar
36.Whitt, W. (1993). Large fluctuations in a deterministic multiclass network of queues. Management Science 39: 1020–1028.Google Scholar
37.Wolff, R.W. (1989). Stochastic modeling and the theory of queues. Englewood Cliffs, NJ: Prentice Hall.Google Scholar
38.Yaron, O. & Sidi, M. (1993). Performance of stability of communication networks via robust exponential bounds. IEEE/ACM Transactions on Networking 1(3): 372–385.CrossRefGoogle Scholar
39.Zhang, Z.L., Towsley, D., & Kurose, J. (1995). Statistical analysis of the generalized processor sharing discipline. IEEE Journal on Selected Areas of Communications 13: 1071–1080.Google Scholar