Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-26T00:45:49.875Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic analysis and computational methods for a class of simple, circuit-switched networks with blocking

Published online by Cambridge University Press:  01 July 2016

Debasis Mitra
Debasis Mitra*
Affiliation:
AT & T Bell Laboratories
*
∗Postal address: AT & T Bell Laboratories, Murray Hill, NJ 07974, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the following circuit-switching problem which is one of the simplest possible extensions of the classical M/M/K/K model: there are p source centers connected to a hub by channels of various line-capacities and the hub is connected to a destination center by a common channel with its own line-capacity. A circuit requires a line from its source to the hub and another line from the hub to the destination. The holding times of circuits are independent, arbitrarily distributed random variables with means which depend on their source, and requests for circuits arrive in Poisson streams. Blocked calls are cleared. The problem is to calculate the blocking probabilities at each of the sources. The formal solution is well known but its calculation is exponentially hard in p.

We have developed a technique which extends recent results on integral representations and their asymptotic expansions to obtain the full expansion for the blocking probabilities in inverse powers of a large parameter N. The power of the method derives from two sources: first, an efficient recursive formula for calculating the general term of the expansion; second, tight upper and lower bounds which accompany the estimates. The computational complexity is polynomial in p. We report on computations.

Keywords

ASYMPTOTICSMULTIDIMENSIONAL INTEGRALSQUASI-REVERSIBLE STOCHASTIC NETWORKS
Type
Research Article
Information
Advances in Applied Probability , Volume 19 , Issue 1 , March 1987 , pp. 219 - 239
Copyright
Copyright © Applied Probability Trust 1987 

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. Brockmeyer, E., Halstrom, H. L. and Jensen, A. (1948) The Life and Works of A. K. Erlang. Academy of Technical Sciences, Copenhagen.Google Scholar
2. Bruel, S. C. and Balbo, G. (1980) Computational Algorithm for Closed Queueing Networks. Elsevier North-Holland, New York.Google Scholar
3. Buzen, J. P. (1973) Computational algorithms for closed queueing networks with exponential servers. Comm. Assoc. Comput. Mach. 16, 527–531.Google Scholar
4. Cooper, R. B. (1982) Introduction to Queueing Theory, 2nd edn. North-Holland, New York.Google Scholar
5. Girard, A. and Ouimet, Y. (1983) End-to-end blocking for circuit-switched networks: polynomial algorithms for some special cases. IEEE Trans. Comm. 31, 1269–1273.Google Scholar
6. Heffes, H. (1981) Moment formulae for a class of mixed multi-job-type queueing networks. Bell System Tech. J. 60, 599–641.Google Scholar
7. Holtzmann, J. M. (1971) Analysis of dependence effects in telephone trunking networks. Bell System Tech. J. 5, 2647–2662.Google Scholar
8. Jagerman, D. L. (1974) Some properties of the Erlang loss functions. Bell System Tech. J. 53, 525–551.Google Scholar
9. Katz, S. S. (1967) Statistical performance analysis of a switched communication network. 5th Internat. Teletraffic Congr., New York, 566–575.Google Scholar
10. Kelly, F. P. (1980) Reversibility and Stochastic Networks. Wiley, New York.Google Scholar
11. Kelly, F. P. (1986) Blocking probabilities in large circuit-switched networks. Adv. Appl. Prob. 18, 473–505.Google Scholar
12. Lin, P. M., Leon, B. J. and Stewart, C. R. (1978) Analysis of circuit-switched networks employing originating-office control with spill-forward. IEEE Trans. Comm. 26, 754–765.Google Scholar
13. Mckenna, J. and Mitra, D. (1982) Integral representations and asymptotic expansions for closed Markovian queueing networks: normal usage. Bell System. Tech. J. 61, 661–683.Google Scholar
14. Mckenna, J. and Mitra, D. (1984) Asymptotic expansions and integral representations of moments of queue lengths in closed Markovian networks. J. Assoc. Comput. Mach. 31, 346–360.Google Scholar
15. Mitra, D. and Mckenna, J. (1986) Asymptotic expansions for closed Markovian networks with state dependent service rates. J. Assoc. Comput. Mach. 33, 568–592.Google Scholar
16. Mitra, D. and Weinberger, P. J. (1984) Probabilistic models of database locking: solution, computational algorithms, and asymptotics. J. Assoc. Comput. Mach. 31, 855–878.Google Scholar
17. Olver, F. W. J. (1974) Introduction to Asymptotics and Special Functions. Academic Press, New York.Google Scholar
18. Riordan, J. (1962) Stochastic Service Systems. Wiley, New York.Google Scholar
19. Whitt, W. (1985) Blocking when service is required from several facilities simultaneously. AT&T Bell System Tech. J. 64, 1807–1856.Google Scholar
20. Wilkinson, R. I. (1956) Theory for toll traffic engineering in the U.S.A. Bell System Tech. J. 35, 421–513.Google Scholar