Modeling, analysis, and optimal routing of flow-controlled communication networks

ABSTRACT

Closed queueing networks have been advocated by several authors to be a more desirable model than open queueing networks (Kleinrock's model) for network design. We compare open and closed network models and demonstrate the accuracy of a particular closed network model with experimental results. The proportional approximation method (PAM) is presented for evaluating performance measures of closed queueing networks. PAM algorithms have computational time and space requirements of O(KM), where M denotes the number of queues and K denotes the number of virtual channels in the network. Thus, PAM is the first (and only) method that can be used for solving industrial-strength network design problems using a closed network model. We formulate the following optimal routing problem: Find a route for a new virtual channel to be added to a network with existing flow-controlled virtual channels. A fast heuristic algorithm is presented. The algorithm uses PAM and exploits the following empirical observation: The route that maximizes the individual throughput of a virtual channel coincides in most cases with the route that maximizes the total network throughput (this is not true in general). We present statistical results from studies of 100 randomly generated networks to demonstrate the accuracy of PAM algorithms and the effectiveness of the optimal routing algorithm. (Exact solutions obtained by the tree convolution algorithm were used as benchmarks in our statistical studies.)

REFERENCES

• 1: F. D. George and G. E. Young, "SNA Flow Control: Architecture and Implementation," IBM Systems Journal, Vol. 21, No. 2, 1982, pp. 179-210.
• 2: M. Gerla and L. Kleinrock, "Flow Control: A Comparative Survey," IEEE Trans. on Commun., Vol. COM-28, No. 4, April 1980, pp. 553-574.
• 3: C.-T. Hsieh, Models and algorithms for the design of store-and-forward communication networks, University of Texas at Austin, Austin, TX, 1987
• 4: Ching-Tarng Hsieh , Simon S. Lam, Two classes of performance bounds for closed queueing networks, Performance Evaluation, v.7 n.1, p.3-30, February 1, 1987 [doi>10.1016/0166-5316(87)90054-X]
• 5: Ching Hsieh , Simon S. Lam, Pamma Noniterative Approximate Solution Method for Closed MultichainQueueing Networks, University of Texas at Austin, Austin, TX, 1987
• 6: Leonard Kleinrock, Communication nets; stochastic message flow and delay, Dover Publications, Incorporated, 1972
• 7: L. Kleinrock, Queueing Systems, Vol. 2: Computer Applications, John Wiley, New York, 1976.
• 8: Hiroshi Kobayashi , Mario Gerla, Optimal routing in closed queuing networks, ACM Transactions on Computer Systems (TOCS), v.1 n.4, p.294-310, Nov. 1983 [doi>10.1145/357377.357381]
• 9: S. S. Lam and C.-T. Hsieh, "Models and Algorithms for the Design of Store-and-Forward Communication Networks, Conf. Record International Conf. on Communications, Chicago, $une 1985, pp. 43.1.1-43.1.6.
• 10: Simon S. Lam , Y. Luke Lien, Modeling and analysis of flow controlled packet switching networks, Proceedings of the seventh symposium on Data communications, p.98-107, October 27-29, 1981, Mexico City, Mexico
• 11: S. S. Lain and Y. L. Lien, "Congestion Control of Packet Communication Networks by Input Buffer Limits--A Simulation Study," IEEE Trans. on Computers, Vol. C-30, No. 10, October 1981, pp. 733-742.
• 12: 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]
• 13: S. S. Lain and J. W. Wrong, "Queueing Network Models of Packet Switching Networks, Part 2: Networks with Population Size Constraints," Performance Evaluation, Vol. 2, No. 3, October 1982, pp. 161-180.
• 14: Yeong-Chang Luke Lien, Modelling and analysis of flow-controlled computer communication networks, 1981
• 15: M. Reiser, "A Queueing Network Analysis of Computer Communication Networks with Window Flow Control," IEEE Trans. on Communication, Vol. COM-27, pp. 1199-1209, 1979.
• 16: M. Reiser and H. Kobayashi, "Queueing Networks with Multiple Closed Chains: Theory and Computational Algorithms," IBM J. Res. Develop., Vol. 21, pp. 283-294, 1975.
• 17: M. Reiser , S. S. Lavenberg, Mean-Value Analysis of Closed Multichain Queuing Networks, Journal of the ACM (JACM), v.27 n.2, p.313-322, April 1980 [doi>10.1145/322186.322195]
• 18: Mischa Schwartz, Telecommunication networks: protocols, modeling and analysis, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Design, Experimentation, Performance, Theory