Computational algorithms for blocking probabilities in circuit-switched networks. (English) Zbl 0760.90042

Summary: We develop two new general purpose recursive algorithms for the exact computation of blocking probabilities in multi-rate product-form circuit- switched networks with fixed routing. The first algorithm is a normalization constant approach based on the partition function of the state distribution. The second is a mean-value type of algorithm with a recursion cast in terms of blocking probabilities and conditional probabilities. The mean value recursion is derived from the normalization constant recursion. Both recursions are general purpose ones that do not depend on any specific network topology. The relative advantage of the mean-value algorithm is numerical stability, but this is obtained at the expense of an increase in computational costs.


90B18 Communication networks in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming


Full Text: DOI


[1] J. Aein, A multi-user class, blocked calls cleared demand access model, IEEE Trans. Commun. COM-26(1978)378–385. · Zbl 0368.94021 · doi:10.1109/TCOM.1978.1094081
[2] E. Arthurs and J. Kaufman, Sizing a message store subject to blocking criteria, in:Performance of Computer Systems, ed. M. Arato, A. Butrimenko and E. Gelenbe (North-Holland, Amsterdam, 1979), pp. 547–564. · Zbl 0405.68037
[3] G. Barberis and R. Brignolo, Capacity allocation in a DAMA satellite system, IEEE Trans. Commun. COM-30(1982)1750–1757. · doi:10.1109/TCOM.1982.1095640
[4] S. Bruell and G. Balbo,Computational Algorithms for Closed Queueing Networks (Elsevier, New York, 1980). · Zbl 0452.68044
[5] D. Burman, J. Lehoczky and Y. Lim, Insensitivity of blocking probabilities in a circuit-switched network, J. Appl. Prob. 21(1984)850–859. · Zbl 0555.60052 · doi:10.2307/3213701
[6] K. Chandy and D. Neuse, Linearizer: A heuristic algorithm for queueing network models of computing systems, C. ACM 25(1982)126–134. · doi:10.1145/358396.358403
[7] A. Conway, E. de Souza c Silva and S. Lavenberg, Mean value analysis by chain of product form queueing networks, IEEE Trans. Comput. C-38(1989)432–442. · doi:10.1109/12.21129
[8] A. Conway and N. Georganas, A new method for computing the normalization constant of multiple-chain queueing networks, INFOR 24(1986)184–198. · Zbl 0633.90019
[9] A. Conway and N. Georganas, RECAL – A new efficient algorithm for the exact analysis of multiple chain closed queueing networks, J. ACM 33(1986)768–791. · Zbl 0637.90038 · doi:10.1145/6490.6495
[10] A. Conway and N. Georganas,Queueing Networks – Exact Computational Algorithms: A Unified Theory Based on Decomposition and Aggregation (The MIT Press, Cambridge, MA, 1989).
[11] R. Cooper,Introduction to Queueing Theory (North-Holland, New York, 1981). · Zbl 0486.60002
[12] E. de Souza c Silva, S. Lavenberg and R. Muntz, A perspective on iterative methods for the approximate analysis of closed queueing networks, in:Mathematical Computer Performance and Reliability, ed. G. Iazeolla, P. Courtois and A. Hordijk (North-Holland, 1984).
[13] Z. Dziong and J. Roberts, Congestion probabilities in a circuit-switched integrated services network, Perform. Eval. 7(1987)267–284. · doi:10.1016/0166-5316(87)90013-7
[14] G. Foschini and B. Gopinath, Sharing memory optimally, IEEE Trans. Commun. COM-31(1983)352–360. · Zbl 0504.94037 · doi:10.1109/TCOM.1983.1095819
[15] G. Fredrikson, Analysis of channel utilization in traffic concentrators, IEEE Trans. Commun. COM-22(1974)1122–1129. · doi:10.1109/TCOM.1974.1092341
[16] A. Gersht and K. Lee, Virtual circuit load control in fast packet-switched broadband networks, in:Proc. IEEE INFOCOM, Miami, FL (April 1988), pp. 214–220.
[17] L. Gimpelson, Analysis of mixtures of wide and narrow band traffic, IEEE Trans. Commun. COM-13(1965)258–266. · doi:10.1109/TCOM.1965.1089121
[18] L. Green, A queueing system in which customers require a random number of servers, Oper. Res. 28(1980)1335–1346. · Zbl 0447.60080 · doi:10.1287/opre.28.6.1335
[19] M. Irland, Buffer management in a packet switch, IEEE Trans. Commun. COM-26(1978)328–337. · Zbl 0378.94024 · doi:10.1109/TCOM.1978.1094076
[20] A. Jafari, T. Saadawi and M. Schwartz, Blocking probability in two-way distributed circuit-switched CATV, IEEE Trans. Commun. COM-34(1986)977–984. · doi:10.1109/TCOM.1986.1096440
[21] D. Jagerman, Methods in traffic calculations, Bell Syst. Tech. J. 63(1984)1283–1310.
[22] F. Kamoun and L. Kleinrock, Analysis of shared finite storage in a computer network node environment under general traffic conditions, IEEE Trans. Commun. COM-28(1980)992–1003. · Zbl 0447.68026 · doi:10.1109/TCOM.1980.1094756
[23] J. Kaufman, Blocking in a shared resource environment, IEEE Trans. Commun. COM-29(1981)1474–1481. · doi:10.1109/TCOM.1981.1094894
[24] F. Kelly, Blocking probabilities in large circuit-switched networks, Adv. Appl. Prob. 18(1986)473–505. · Zbl 0597.60092 · doi:10.2307/1427309
[25] F. Kelly, Routing in circuit-switched networks: Optimization, shadow prices and decentralization, Adv. Appl. Prob. 20 (1988). · Zbl 0644.60096
[26] S. Lam, Store-and-forward buffer requirements in a packet switching network, IEEE Trans. Commun. COM-24(1976)394–403. · Zbl 0375.90032 · doi:10.1109/TCOM.1976.1093320
[27] S. Lavenberg,Computer Performance Modeling Handbook (Academic Press, New York, 1983). · Zbl 0601.68005
[28] D. Mitra, Some results from an asymptotic analysis of a class of simple circuit-switched networks, in:Teletraffic Analysis and Computer Performance Evaluation, ed. O.J. Boxma et al. (North-Holland, 1986), pp. 47–63.
[29] E. Pinsky and A. Conway, Exact computation of blocking probabilities in state-dependent multifacility blocking models, in:Proc. Int. Conf. on the Performance of Distributed Systems and Integrated Communication Networks, Kyoto, Japan (Sept. 1991), pp. 353–362.
[30] K. Ross and D. Tsang, Teletraffic engineering for product-form circuit switched networks, Adv. Appl. Prob. 22(1990)657–675. · Zbl 0715.60112 · doi:10.2307/1427463
[31] D. Tsang and K. Ross, Algorithms to determine exact blocking probabilities for multi-rate tree networks, IEEE Trans. Commun. COM-38(1990)1266–1271. · Zbl 0706.94028 · doi:10.1109/26.58760
[32] W. Whitt, Blocking when service is required from several facilities simultaneously, Bell Syst. Tech. J. 64(1985)1807–1856. · Zbl 0591.90035
[33] T. Yum and C. Dou, Buffer allocation strategies with blocking requirements, Perform. Eval. 4(1984)285–295. · doi:10.1016/0166-5316(84)90013-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.