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: E. Arthurs , J. S. Kaufman, Sizing a Message Store Subject to Blocking Criteria, Proceedings of the Third International Symposium on Modelling and Performance Evaluation of Computer Systems: Performance of Computer Systems, p.547-564, February 06-08, 1979
• 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: Adrian E. Conway , Nicolas D. Georganas, Queueing networks—exact computational algorithms: a unified theory based on decomposition and aggregation, MIT Press, Cambridge, MA, 1989
• 7: ~COURTOIS, P. J. 1977. Deconzposabdity: Queuebzg and Computer Systenz Applications. Academic ~Press, Orlando, Fla.
• 8: Zbigniew Dziong , James W. Roberts, Congestion probabilities in a circuit-switched integrated services network, Performance Evaluation, v.7 n.4, p.267-284, Nov. 1987 [doi>10.1016/0166-5316(87)90013-7]
• 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: J. S. Kaufman, Blocking with retrials in a completely shared resource environment, Performance Evaluation, v.15 n.2, p.99-113, June 1992 [doi>10.1016/0166-5316(92)90058-O]
• 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: Simon S. Lam , Y. Luke Lien, A tree convolution algorithm for the solution of queueing networks, Communications of the ACM, v.26 n.3, p.203-215, March 1983 [doi>10.1145/358061.358075]
• 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 Mitra, Some results from an asymptotic analysis of a class of simple, circuit-switched networks, Proc. of the international seminar on Teletraffic analysis and computer performance evaluation, p.47-61, December 1986, Amsterdam, The Netherlands
• 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: Eugene Pinsky , Adrian E. Conway, Computational algorithms for blocking probabilities in circuit-switched networks, Annals of Operations Research, v.35 n.1-4, p.31-41, April 1992
• 27: Eugene Pinsky , Adrian E. Conway, Exact computation of blocking probabilities in state-dependent multi-facility blocking models, Proceedings of the IFIP WG 7.3 International Conference on Performance of Distributed Systems and Integrated Communication Networks, p.383-392, September 10-12, 1991
• 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: Keith W. Ross , Jie Wang, Solving product form stochastic networks with Monte Carlo summation, Proceedings of the 22nd conference on Winter simulation, p.270-275, December 09-12, 1990, New Orleans, Louisiana, United States
• 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: William Stallings, ISDN and Broadband ISDN (2nd ed.), Macmillan Publishing Co., Inc., Indianapolis, IN, 1992
• 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

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Stochastic analysis

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication
      D.4.8 Performance
          Subjects: Queueing theory; Modeling and prediction

General Terms:
Algorithms, Performance, Theory, Verification

Keywords:
blocking models, circuit-switched networks, decomposition methods, exact analysis, locality, product-form, recursion, sparsity