Efficient decomposition methods for the analysis of multi-facility blocking models

Abstract

Three new decomposition methods are developed for the exact analysis of stochastic multi-facility blocking models of the product-form type. The first is a basic decomposition algorithm that reduces the analysis of blocking probabilities to that of two separate subsystems. The second is a generalized M-subsystem decomposition method. The third is a more elaborate and efficient incremental decomposition technique. All of the algorithms exploit the sparsity of locality that can be found in the demand matrix of a system. By reducing the analysis to that of a set of subsystems, the overall dimensionality of the problem is diminished and the computational requirements are reduced significantly. This enables the efficient computation of blocking probabilities in large systems. Several numerical examples are provided to illustrate the computational savings that can be realized.

References

1. ~AEIN, J. 1978. A multi-user-class blocked calls cleared demand access model. IEEE Trans. ~Commun. 26, 3, 378-385.
2. ~AEIN, J., AND KOSOVYCH, S. 1977. Satellite capacity allocation. IEEE Proc. 65, 3, 332 342.
3. ~ARTHURS, E., AND KAUFMAN, J. 1979. Sizing a message store subject to blocking criteria. In ~Performance of Computer Systems. M. Arato, A. Butrimenko, and E. Gelenbe, eds., North-Hol- ~land, Amsterdam, The Netherlands, pp. 547 564.
4. ~BARBERIS, G., AND BRIGNOLO, R. 1982. Capacity allocation in a DAMA satellite system. IEEE ~Trans. Conzmun. 30, 7, 1750-1757.
5. ~BURMAN, D. Y., LEHOCZKY, J. P., AND LIM, Y. 1984. Insensitivity of blocking probabilities in a ~circuit-switching network. J. Appl. Prob. 21,850-859.
6. ~CONWA~', A. E., AND GEORGANAS, N. D. 1989, Queueing Networks-Exact Computattonal Algo- ~rittnns: A Untried Theory Based on Decomposttion and Aggregauon. The MIT Press, Cambridge, ~Mass.
7. ~COURTOIS, P. J. 1977. Deconzposabdity: Queuebzg and Computer Systenz Applications. Academic ~Press, Orlando, Fla.
8. ~DZIONG, Z., AND ROBERTS, J. W. 1987. Congestion probabilities in a circuit-switched integrated ~services network. Perf. Eval., 7, 267-284.
9. ~FOSCmNI, G., AND GOPINATH, B. 1983. Sharing memory optimally. IEEE Trans. Commun. 31, 3, ~352 360.
10. ~FREDRIKSON, G. 1974. Analysis of channel utilization in traffic concentrators. IEEE Trans. ~Commun. 22, 8, 1122 1129.
11. ~GERSHT, A., AND LEE, K. 1988. Virtual circuit load control in fast packet-switched broadband ~networks. In Proceedbzgs oflEEE INFOCOM'88 (Miami, Fla.). IEEE, New York, pp. 214-220.
12. ~GIRARD, A., AND OUIMET, Y. 1983. End-to-end blocking for circuit switched networks: Polyno-mial algorithms for some special cases, iEEE Trans. Commun. 31, 12, 1269-1273.
13. ~HOLTZMANN, J. 1971. Analysis of dependence effects in telephone trunking networks. Bell Syst. ~Tech. J. 50, 8, 2647-2662.
14. ~JAFARI, A., SAADAWI, T., AND SCHWARTZ, M. 1986. Blocking probability in two-way distributed ~circuit-switched CATV. 1EEE Trans. Commun, 34, 10, 977 984.
15. ~JORDAN, S., AND VARAIYA, P. P. 1991. Throughput in multiple service, multiple resource ~communication networks. IEEE Trans. Commun 39, 8, 1216-1222.
16. ~KATZ, S. 1967. Statistical performance analysis of a switched communication network. In ~Proceedmgs of the 5th Internatzonal Teletraffic Congress (New York, N.Y.). pp. 566 575.
17. ~KAUFMAN, J. 1981. Blocking in a shared resource environment. IEEE Trans. Commun. 29, 10, ~pp. 1474-1481.
18. ~KAUFMAN, J. 1992. Blocking with retrials in a completely shared resource environment. Perf. ~Ecal. 15, 99-113.
19. ~KELLY, F. P. 1979. Reversbthty and Stochasnc Nem,orks. Wiley, New York.
20. ~KELLY, F. P. 1986. Blocking probabilities m large circmt-switched networks. Adv. Appl. Prob., ~10, 473-505.
21. ~KELLY, F. P. 1991.Loss networks. Ann. AppL Prob., 1, 3, 319-378.
22. ~LAM, g. S., AND LIEN, Y. L. 1983. A trcc convolution algorithm for the solution of qucueing ~networks. Commun. ACM, 26, 203 215.
23. ~LIN, P., LEON, B., AND STEWART, C. 1978. Analysis of circuit switched networks employing ~originating-office control with spill-over. {EEE Trans. Conzmun. 26, 6, 754-765.
24. D. 1986. Some results from an asymptotic analysis of a class of simple circuit-switched ~networks. In Teletra~ir Analysis and Computer Performance Evahtation. O. J. Boxma, J. W. ~Cohen, and H. C. Toms, eds., North-Holland, Amsterdam, The Netherlands, pp. 47-61.
25. ~PINSKY, E., AND CONWAY, A. E. 1990. Performance analysis of sharing policies for broadband ~networks. In Proceedings of the 7th ITC Seminar on Broadband Technologies (Morristown, N.J., ~Oct.). pp. 11.4.1 11.4.8.
26. ~PINSKY, E., AND CONWA'~, A. E. 1992a. Computational algorithms for blocking probabilities in circuit-switched networks. Ann. Oper. Res. 35, 31 41.
27. ~PINSKY, E., AND CONWAY, A. E. 1992b. Exact computation of blocking probabilities in state-de- ~pendent multi-facility blocking models. In Performance of Distrtbuted Systems and Integrated ~Communication Networks. T. Hasegawa, H. Takagi, and Y. Takahashi, eds. North-Holland, ~Amsterdam, The Netherlands, pp. 383-392.
28. ~ROSS, K., AND TSANG, D. 1990. Teletraffic engineering for product-form circuit switched net- ~works. Adv. Appl. Prob., 22, 3, pp. 657-675.
29. ~ROSS, K. AND WANG, J. 1990. Solving product form stochastic networks with Monte Carlo ~summation. In Proceedings of the Winter Simulation Conference. 0. Balci, R. Sadowski, R. ~Nance, eds. IEEE, New York, pp. 270-275.
30. ~RUBIN, I., AND LEE, J. 1988. Performance analysis of interconnected metropolitan area circuit- ~switched telecommunications networks. IEEE Trans. Commun. 36, 2, 171-185.
31. ~SIMON, H. h., AND ANDO, A. 1961. Aggregation of variables in dynamic systems. Econometriea ~29, pp. 111-138.
32. ~STALLINGS, W. 1992. ISDN and Broadband ISDN, Macmillan, New York.
33. ~TSANG, D., AND ROSS, K. 1990. Algorithms to determine exact blocking probabilities for ~multi-rate tree networks. IEEE Trans. Commun., 38, 8, 1266-1271.
34. ~WniTT, W. 1985. Blocking when service is required from several facilities simultaneously. Bell ~Syst. Techo J., 64, 8, 1807-1856.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Mathematics of computing

  • Probability and statistics

    • Statistical paradigms

      • Queueing theory

• Networks

  • Network protocols

• Software and its engineering

  • Software creation and management

    • Software development process management

      • Software development methods

  • Software organization and properties

    • Contextual software domains

      • Operating systems

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization

      • Continuous optimization

        • Stochastic control and optimization