article

Free access

Performance comparison of routing protocols under dynamic and static file transfer connections

Authors:

A. Udaya Shakar,

Cengiz Alaettinoğlu,

Klaudia Dussa-Zieger,

Ibrahim MattaAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 22, Issue 5

Pages 39 - 52

https://doi.org/10.1145/141809.141813

Published: 02 October 1992 Publication History

Abstract

We compare the performance of two recently proposed distance-vector algorithms (Merlin-Segall and Extended Bellman-Ford) with a link-state algorithm (SPF), under varying file transfer workload. (Unlike the traditional distance-vector algorithms, these new distance-vector algorithms do not suffer from long-lived loops.) Our comparison is done using a recently developed network simulator. MaRS. We consider both dynamic and static file transfer connections, and both uniform and hotspot distributions of source-sink pairs. Our conclusion is that Extended Bellman-Ford performs as well as SPF in terms of delay and throughput. This suggests that distance-vector algorithms are appropriate for very large wide-area networks, since their space requirements are less than that of link-state algorithms.

References

[1]

[1] C. Alaettino¿lu, K. Dussa-Zieger. I. Matta, and A. U. Shankar. MaRS (Maryland Routing Simulator) - Version 1.0 User's Manual. Technical Report UMIACS-TR-91-80. CS-TR-2687. Department of Computer Science, University of Maryland, College Park. MD 20742. June 1991.

Digital Library

[2]

[2] D. Bertsekas and R. Gallaher. Data Networks, pages 297-333. Prentice-Hall. Inc., 1987.

Digital Library

[3]

[3] C. Cheng. R. Riley. S. P. R. Kumar. and J. J. Garcia-Luna-Aceves. A Loop-free Bellman-Ford Routing Protocol Without Bouncing Effect. In Proc. ACM SIGCOMM'89, pages 224-237. September 1989.

Digital Library

[4]

[4] Wushow Chou. Arnold Bragg. and Arne Nilsson. The Need for Adaptive Routing in the Chaotic and Unbalanced Traffic. IEEE Transactions on Communications. 1981.

[5]

[5] E. Dijkstra. A Note on Two Problems in Connection with Graphs. Numer. Math., 1:269-271. 1959.

Digital Library

[6]

[6] E. Dijkstra and C. Scholten. Termination Detection for Diffusing Computations. Information Processing Letters, 11(1):1-4, 1980.

[7]

[7] A. Ephremides. P. Varaiya. and J. Walrand. A Simple Dynamic Routing Problem. IEEE Transactions on Automatic Control. 25(4):690-693, August 1980.

[8]

[8] A. Ephremides and S. Verdu. Control and Optimization Methods in Communication Network Problems. IEEE Transactions on Automatic Control. 34(9):930-942. September 1989.

[9]

[9] L. Ford and D. Fulkerson. Flows in Networks, pages 297-333. Prentice-Hall. Inc., 1962.

[10]

[10] R. Gallager. A Minimum Delay Routing Algorithm Using Distributed Computation. IEEE Transactions on Communications. COM-25:73-84, Jan 1977.

[11]

[11] J. J. Garcia-Luna-Aceves. A Unified Approach to Loop Free Routing Using Distance Vectors or Link States. In Proc. ACM SIGCOMM '89, pages 212-223, September 1989.

Digital Library

[12]

[12] S. A. Heimlich. Traffic Characterization of the NSFNET National Backbone. In Proc. USENIX '90. pages 207-227, Washington. D.C. January 1990.

Digital Library

[13]

[13] P. A. Humblet and S. R. Soloway. Algorithms for Data Communication Networks-Part 1. Technical report. Codex Corp. 1986.

[14]

[14] P. A. Humblet., S. R. Soloway. and B. Steinka. Algorithms for Data Communication Networks-Part 2. Technical report. Codex Corp. 1986.

[15]

[15] J. M. Jaffe and F. R. Moss. A Responsive Distributed Routing Algorithm for Computer Networks. IEEE Transactions on Communications, COM-30(7):1758-1762. July 1982.

[16]

[16] Dale Johnson. NSFnet. Report. In Proc. of the Nineteenth Internet Engineering Task Force, pages 377-382, University of Colorado, National Center for Atmospheric Research, December 1990.

[17]

[17] A. Khanna and J. Zinky. A Revised ARPANET Routing Metric. In Proc. ACM SIGCOMM '89. pages 45-56, September 1989.

Digital Library

[18]

[18] L. Kleinrock. Queueing Systems. Volume II: Computer Applications. John Wiley and Sons. Inc., 1976.

[19]

[19] J. M. McQuillan. I. Richer. and E. C. Rosen. The New Routing Algorithm for the ARPANET. IEEE Transactions on Communications. COM-28(5):711-719. May 1980.

[20]

[20] P. M. Merlin and A. Segall. A Failsafe Distributed Routing Protocol. IEEE Transactions on Communications, COM-27(9):1280-1287, September 1979.

[21]

[21] B. P. Mohanty, C. G. Cassandras. and D. Towsley. Performance Comparison of Routing Algorithms in Packet Switched Networks. In Proc. IEEE Globecom '90. San Diego, California. 1990.

[22]

[22] D. J. Nelson. K. Sayood, and H. Chang. An Extended Least-Hop Distributed Routing Algorithm. IEEE Transactions on Communications, 38(4):520-528. April 1990.

[23]

[23] B. Rajagopalan and M. Faiman. A New Responsive Distributed Shortest-Path Routing Algorithm. In Proc. ACM SIGCOMM '89, pages 237-246. September 1989.

Digital Library

[24]

[24] A. Segal. Advances in Verifiable Fail-Safe Routing Procedures. IEEE Transactions on Communications . COM-29(4):491-497, April 1981.

[25]

[25] A. Udaya Shankar. Cengiz Alaettino¿lu. Ibrahim Matta. and Klauclia Dussa-Zieger. Performance Comparison of Routing Protocols using MaRS: Distance-Vector versus Link-State. In Proc. ACM SIGMETRICS and PERFORMANCE, pages 181-192. Newport, Rhode Island. June 1992.

Digital Library

[26]

[26] W. T. Tsai, C. Ramamoorthy, W. K. Tsai, and O. Nishiguchi. An Adaptive Hierarchical Routing Protocol. IEEE Transactions on Computers. 38:1059-1075. August 1989.

Digital Library

[27]

[27] Z. Wang and J. Crowcroft. Shortest Path First with Emergency Exits. In Proc. ACM SIGCOMM '90. pages 166-176. September 1990.

Digital Library

[28]

[28] W. Zaumen and J. J. Garcia-Luna-Aceves. Dynamics of Distributed Shortest-path Routing Algorithms. In Proc. ACM SIGCMM '91, September 1991.

Digital Library

Cited By

Di Caro GDorigo M(2018)AntNetJournal of Artificial Intelligence Research10.5555/1622797.16228069:1(317-365)Online publication date: 17-Dec-2018
https://dl.acm.org/doi/10.5555/1622797.1622806
Di Caro GDorigo M(2006)Ant colonies for adaptive routing in packet-switched communications networksParallel Problem Solving from Nature — PPSN V10.1007/BFb0056909(673-682)Online publication date: 3-Jun-2006
https://doi.org/10.1007/BFb0056909
Rios MMarianov VAvagliano A(2005)Multiple path routing algorithm for IP networksComputer Communications10.1016/j.comcom.2004.11.01428:7(829-836)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1016/j.comcom.2004.11.014

Index Terms

Performance comparison of routing protocols under dynamic and static file transfer connections

Recommendations

Performance comparison of routing protocols using MaRS: distance-vector versus link-state
SIGMETRICS '92/PERFORMANCE '92: Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems

There are two approaches to adaptive routing protocols for wide-area store-and-forward networks: distance-vector and link-state. Distance-vector algorithms use O(N x e) storage at each node, whereas link-state algorithms use O(N²), where N is the number ...
Performance comparison of routing protocols using MaRS: distance-vector versus link-state

There are two approaches to adaptive routing protocols for wide-area store-and-forward networks: distance-vector and link-state. Distance-vector algorithms use O(N x e) storage at each node, whereas link-state algorithms use O(N²), where N is the number ...
Routing Protocols: RIP and BGP Rbsw05e

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 22, Issue 5

Oct. 1992

87 pages

ISSN:0146-4833

DOI:10.1145/141809

Editor:
David Oran
Digital Equipment Corporation, Littleton, MA

Issue’s Table of Contents

Copyright © 1992 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 October 1992

Published in SIGCOMM-CCR Volume 22, Issue 5

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
340
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)9

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Di Caro GDorigo M(2018)AntNetJournal of Artificial Intelligence Research10.5555/1622797.16228069:1(317-365)Online publication date: 17-Dec-2018
https://dl.acm.org/doi/10.5555/1622797.1622806
Di Caro GDorigo M(2006)Ant colonies for adaptive routing in packet-switched communications networksParallel Problem Solving from Nature — PPSN V10.1007/BFb0056909(673-682)Online publication date: 3-Jun-2006
https://doi.org/10.1007/BFb0056909
Rios MMarianov VAvagliano A(2005)Multiple path routing algorithm for IP networksComputer Communications10.1016/j.comcom.2004.11.01428:7(829-836)Online publication date: 1-May-2005
https://dl.acm.org/doi/10.1016/j.comcom.2004.11.014

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents