Modeling, analysis, and optimal routing of flow-controlled communication networks
Pages 162 - 172
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-a2ut-Fo~ard Communication Networks, Ph.D. Dissertation, Deparunent of Computer Sciences, University of Texas at Austin, May 1987.
[4]
C.-T. Hsieh and S. S. Lam, "Two Classes of Performance Bounds for Closed Queueing Networks," Performance Evaluation, Vol. 7, No. 1, 1987, pp. 3-30.
[5]
C.-T. Hsieh and S. S. Lain, "PAM -- A Noniterative Approximate Solution Method for Closed Mull/chain Queueing Networks," Technical Report TR-87-28, Department of Computer Sciences, University of Texas at Austin, July 1987.
[6]
L. Kleinrock, Communication Nets: Stochastic Message Flow and Delay, McGraw-Hill, New York, 1964.
[7]
L. Kleinrock, Queueing Systems, Vol. 2: Computer Applications, John Wiley, New York, 1976.
[8]
H. Kobayashi and M. Gerla, "Optimal Routing in Closed Queueing Networks," ACM Transactions on Computer Systems, Vol. 1, No. 4, Nov. 1983, pp. 294-310.
[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]
S. S. Lain and Y. L. Lien, "Modeling and Analysis of Flow Controlled Packet Switching Networks," Proc. 7th Data Communications Symposium, Mexico City, October 1981.
[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]
S. S. Lain and Y. L. Lien, "A Tree Convolution Algorithm for the Solution of Queueing Networks," Comm. ACM, Vol. 26, No. 3, March 1983, pp. 203-215.
[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]
Y. L. Lien, Modeling and Analysis of Flow Controlled Computer Communication Networks, Ph.D. Dissertation, Department of Computer Sciences, University of Texas at Austin, 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 and S. Lavenberg, "Mean Value Analysis of Closed Multichain Queueing Networks," Journal of ACM, Vol. 27, No. 2, pp. 313-322, April 1980.
[18]
M. Schwartz, Telecommunication Networks: Protocols, Modeling and Analysis, Addison-Wesley, Reading, Mass., 1987.
Index Terms
- Modeling, analysis, and optimal routing of flow-controlled communication networks
Recommendations
Modeling, analysis, and optimal routing of flow-controlled communication networks
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 ...
Optimal routing in networks with flow-controlled virtual channels
Proceedings of the Computer Network Performance SymposiumPacket switching networks with flow-controlled virtual channels are naturally modeled as queueing networks with closed chains. Available network design and analysis techniques, however, are mostly based upon an open-chain queueing network model. In this ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Oct./Nov. 1987397 pages
Copyright © 1987 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 August 1987
Check for updates
Qualifiers
- Article
Conference
SIGCOMM87
Sponsor:
Acceptance Rates
Overall Acceptance Rate 462 of 3,389 submissions, 14%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations7Total Citations
- 535Total Downloads
- Downloads (Last 12 months)85
- Downloads (Last 6 weeks)22
Reflects downloads up to 13 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in