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

Approximations of large trunk line systems under heavy traffic

Part of: Operations research and management science Markov processes Limit theorems

Published online by Cambridge University Press:  01 July 2016

Harold J. Kushner
Harold J. Kushner*
Affiliation:
Brown University
*
* Postal address: Division of Applied Mathematics, Brown University, Providence, RI 02912, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper deals with large trunk line systems of the type appearing in telephone networks. There are many nodes or input sources, each pair of which is connected by a trunk line containing many individual circuits. Traffic arriving at either end of a trunk line wishes to communicate to the node at the other end. If the direct route is full, a rerouting might be attempted via an alternative route containing several trunks and connecting the same endpoints. The basic questions concern whether to reroute, and if so how to choose the alternative path. If the network is ‘large’ and fully connected, then the overflow traffic which is offered for rerouting to any trunk comes from many other trunks in the network with no one dominating. In this case one expects that some sort of averaging method can be used to approximate the rerouting requests and hence simplify the analysis. Essentially, the overflow traffic that a trunk offers the network for rerouting is in some average sense similar to the overflow traffic offered to that trunk. Indeed, a formalization of this idea involves the widely used (but generally heuristic) ‘fixed point' approximation method. One sets up the fixed point equations for appropriate rerouting strategies and then solves them to obtain an approximation to the system loss. In this paper we work in the heavy traffic regime, where the external offered traffic to any trunk is close to the service capacity of that trunk. It is shown that, as the number of links and circuits within each link go to infinity and for a variety of rerouting strategies, the system can be represented by an averaged limit. This limit is a reflected diffusion of the McKean–Vlasov (propagation of chaos) type, where the driving terms depend on the mean values of the solution of the equation. The averages occur due to the symmetry of the network and the averaging effects of the many interactions. This provides a partial justification for the fixed point method. The concrete dynamical systems flavor of the approach and the representations of the limit processes provide a useful way of visualizing the system and promise to be useful for the development of numerical methods and further analysis.

Keywords

TRUNK LINE NETWORKSLOSS NETWORKSQUEUEING NETWORKSHEAVY TRAFFIC LIMITSPROPAGATION OF CHAOSREROUTING STRATEGIESWEAK CONVERGENCE

MSC classification

Primary: 60F05: Central limit and other weak theorems
Secondary: 60J60: Diffusion processes 90B15: Network models, stochastic 90B22: Queues and service
Type
Research Article
Information
Advances in Applied Probability , Volume 26 , Issue 4 , December 1994 , pp. 1063 - 1094
Copyright
Copyright © Applied Probability Trust 1994 

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] Denardo, E. V. and Park, H. (1990) Efficient routing of telecommunications traffic, i: Ranking unblocked routes. Technical report, Yale University; Dept. of Operations Research, 1990. Revised, Sept. 1992.Google Scholar
[2] Dobrushin, R. L. (1970) Prescribing a system of random variables by conditional distributions. Theory Prob. Appl. 15, 458–486.CrossRefGoogle Scholar
[3] Dupuis, P. and Ishii, H. (1991) On Lipschitz continuity of the solution mapping to the Skorokhod problem, with applications. Stochastics 35, 31–62.Google Scholar
[4] Ethier, S. N. and Kurtz, T. G. (1986) Markov Processes: Characterization and Convergence. Wiley, New York.Google Scholar
[5] Graham, C. and Meleard, S. (1993) Propogation of chaos for a fully connected loss network with alternate routing. Stoch. Proc. Appl. 44, 159–182.Google Scholar
[6] Graham, C. and Métivier, M. (1982) System of interacting particles and non-linear diffusion reflecting in a domain with sticky boundary. Prob. Theory Rel. Fields 82, 225–240.Google Scholar
[7] Kelly, F. P. (1991) Loss networks. Ann. Appl. Prob. 1, 319–377.Google Scholar
[8] Kushner, H. J. (1994) Control of trunk line systems in heavy traffic. Technical report, Brown University, Lefschetz Center for Dynamical Systems: Division of Applied Math. SIAM J. Control Optim. To appear.Google Scholar
[9] Kushner, H. J. and Ramachandran, K. M. (1989) Optimal and approximately optimal control policies for queues in heavy traffic. SIAM J. Control Optim. 27, 1293–1318.Google Scholar
[10] Mitra, D. and Gibbens, R. J. (1994) State dependent routing on symmetric loss networks with trunk reservations: asymptotics, optimal design. Ann. Operat. Res. To appear.Google Scholar
[11] Mitra, D. Gibbens, R. J. and Huang, B. D. (1991) Analysis and optimal design of aggregated-least-busy-alternative routing on symmetric loss networks with trunk reservation. In Teletraffic and Datatraffic in a Period of Change ed. Jensen, A. and Jensen, V. B.. Elsevier North-Holland, Amsterdam.Google Scholar
[12] Ott, T. J. and Krishnan, K. R. (1992) Separable routing: a scheme for state dependent routing of circuit switched telephone traffic. Ann. Operat. Res. 35, 43–68.CrossRefGoogle Scholar
[13] Reiman, ?. I. (1984) Open queueing networks in heavy traffic. Math. Operat Res., 9, 441–458.Google Scholar
[14] Reiman, M. (1991) Optimal trunk reservations for a critically loaded line. In Teletraffic and Datatraffc in a Period of Change, ed. Jensen, A. and Jensen, V. B., Elsevier North-Holland, Amsterdam.Google Scholar
[15] Sznitman, A.-S. (1984) Nonlinear reflecting diffusion process and the propagation of chaos and fluctuations associated. J. Functional Anal. 56, 311–336.Google Scholar
[16] Sznitman, A.-S. (1991) Topics in the propagation of chaos. In Ecole d'Éié de Probabilités de St.-Flour XIX–1989, pp. 166–247. Lecture Notes in Mathematics, Springer-Verlag, Berlin.Google Scholar