Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-05T15:26:34.114Z Has data issue: false hasContentIssue false
  • English
  • Français

Resource pooling in queueing networks with dynamic routing

Part of: Special processes Operations research and management science

Published online by Cambridge University Press:  01 July 2016

C. N. Laws
C. N. Laws*
Affiliation:
University of Cambridge
*
∗Present address: Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UK.
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we investigate dynamic routing in queueing networks. We show that there is a heavy traffic limiting regime in which a network model based on Brownian motion can be used to approximate and solve an optimal control problem for a queueing network with multiple customer types. Under the solution of this approximating problem the network behaves as if the service-stations of the original system are combined to form a single pooled resource. This resource pooling is a result of dynamic routing, it can be achieved by a form of shortest expected delay routing, and we find that dynamic routing can offer substantial improvements in comparison with less responsive routing strategies.

Keywords

NETWORK FLOWHEAVY TRAFFICBROWNIAN NETWORK MODELSSHORTEST DELAY ROUTINGDYNAMIC SEQUENCING

MSC classification

Primary: 90B15: Network models, stochastic
Secondary: 60K25: Queueing theory
Type
Research Article
Information
Advances in Applied Probability , Volume 24 , Issue 3 , September 1992 , pp. 699 - 726
Copyright
Copyright © Applied Probability Trust 1992 

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.)

Footnotes

Supported by SERC grants 8700117X and GR/F 94194.

References

[1] Chen, H. and Mandelbaum, A. (1991) Stochastic discrete flow networks: diffusion approximations and bottlenecks. Ann. Prob. 19, 1463–1519.CrossRefGoogle Scholar
[2] Cohen, J. E. and Kelly, F. P. (1990) A paradox of congestion in a queueing network. J. Appl. Prob. 27, 730–734.CrossRefGoogle Scholar
[3] Ford, L. R. and Fulkerson, D. R. (1962) Flows in Networks. Princeton University Press.Google Scholar
[4] Foschini, G. J. (1977) On heavy traffic diffusion analysis and dynamic routing in packet switched networks. In Computer Performance , ed. Chandy, K. M. and Reiser, M., pp. 499–513. North-Holland, Amsterdam.Google Scholar
[5] Foschini, G. J. and Salz, J. (1978) A basic dynamic routing problem and diffusion. IEEE Trans. Comm. 26, 320–327.CrossRefGoogle Scholar
[6] Gallager, R. G. (1977) A minimum delay routing algorithm using distributed computation. IEEE Trans. Comm. 25, 73–85.CrossRefGoogle Scholar
[7] Gondran, M. and Minoux, M. (1984) Graphs and Algorithms. Wiley-Interscience, New York.Google Scholar
[8] Harrison, J. M. (1985) Brownian Motion and Stochastic Flow Systems. Wiley, New York.Google Scholar
[9] Harrison, J. M. (1988) Brownian models of queueing networks with heterogeneous customer populations. In Stochastic Differential Systems, Stochastic Control Theory and Applications , IMA Volume 10, ed. Fleming, W. and Lions, P. L., pp. 147–186, Springer-Verlag, New York.CrossRefGoogle Scholar
[10] Harrison, J. M. and Wein, L. M. (1989) Scheduling networks of queues: heavy traffic analysis of a simple open network. QUESTA 5, 265–280.Google Scholar
[11] Harrison, J. M. and Wein, L. M. (1990) Scheduling networks of queues: heavy traffic analysis of a two-station closed network. Operat. Res. 38, 1052–1064.CrossRefGoogle Scholar
[12] Harrison, J. M. and Williams, R. J. (1987) Brownian models of open queueing networks with homogeneous customer populations. Stochastics 22, 77–115.CrossRefGoogle Scholar
[13] Hu, T. C. (1969) Integer Programming and Network Flows. Addison-Wesley, Reading, Massachusetts.Google Scholar
[14] Johnson, D. P. (1983) Diffusion Approximations for Optimal Filtering of Jump Processes and for Queueing Networks. PhD thesis, Dept. of Mathematics, University of Wisconsin, Madison.Google Scholar
[15] Kelly, F. P. (1979) Reversibility and Stochastic Networks. Wiley, Chichester.Google Scholar
[16] Kelly, F. P. (1991) Loss networks. Ann. Appl. Prob. 1, 319–378.CrossRefGoogle Scholar
[17] Laws, C. N. (1990) Dynamic Routing in Queueing Networks. PhD thesis, Statistical Laboratory University of Cambridge.Google Scholar
[18] Laws, C. N. and Louth, G. M. (1990) Dynamic scheduling of a four-station queueing network. Prob. Eng. Inf. Sci. 4, 131–156.CrossRefGoogle Scholar
[19] Lomonosov, M. V. (1985) Combinatorial approaches to multiflow problems. Discrete Appl. Math. 11, 1–93.Google Scholar
[20] Martins, L. F. and Kushner, H. J. (1990) Routing and singular control for queueing networks in heavy traffic. SIAM J. Control Optim. 28, 1209–1233.CrossRefGoogle Scholar
[21] Minoux, M. (1981) Optimum synthesis of a network with non-simultaneous multicommodity flow requirements. In Ann. Discrete Math. 11, Studies on Graphs and Discrete Programming , ed. Hansen, P., pp. 269–277, North-Holland, Amsterdam.CrossRefGoogle Scholar
[22] Papernov, B. A. (1976) On existence of multicommodity flows. In Studies in Discrete Optimization , ed. Fridman, A. A., pp. 230–261, Nauka, Moscow (in Russian).Google Scholar
[23] Peterson, W. P. (1991) A heavy traffic limit theorem for networks of queues with multiple customer types. Math. Operat. Res. 16, 90–118.CrossRefGoogle Scholar
[24] Reiman, M. I. (1983) Some diffusion approximations with state space collapse. In Proc. Internat. Seminar on Modelling and Performance Evaluation Methodology , ed. Baccelli, F. and Fayolle, G., pp. 209–240, Lecture Notes in Control and Information Science 60, Springer-Verlag, Berlin.Google Scholar
[25] Reiman, M. I. (1984) Open queueing networks in heavy traffic. Math. Operat. Res. 9, 441–458.CrossRefGoogle Scholar
[26] Schwartz, M. (1987) Telecommunication Networks. Addison-Wesley, Reading, MA.Google Scholar
[27] Stidham, S. (1974) A last word on L = ?W. Operat. Res. 22, 417–421.CrossRefGoogle Scholar
[28] Wein, L. M. (1990) Optimal control of a two-station Brownian network. Math. Operat. Res. 15, 215–242.CrossRefGoogle Scholar
[29] Whitt, W. (1971) Weak convergence theorems for priority queues: preemptive-resume discipline. J Appl. Prob. 8, 74–94.CrossRefGoogle Scholar
[30] Whittle, P. (1971) Optimization under Constraints. Wiley, Chichester.Google Scholar