article

Free access

Dynamics of distributed shortest-path routing algorithms

Authors:

William T. Zaumen,

J. J. Garcia-Luna AcevesAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 21, Issue 4

Pages 31 - 42

https://doi.org/10.1145/115994.115997

Published: 01 August 1991 Publication History

PDF eReader

References

[1]

D. Bertsekas and R. Oallager, 1987: Data Networks. Englewood Cliffs, NF: Prentice- Hall, Inc.]]

Digital Library

Google Scholar

[2]

T. Cegrell, 1975: '% Routing Procedure for the TIDAS Message-Switching Network," IEEE Transactions on Communications, Vol. COM-23, No. 6, pp. 575-585.]]

Google Scholar

[3]

C. Cheng, 1989: "A Loop-Free Extended BeUman-Ford Routing Protocol without Bouncing Effect," ACM Computer Communication Review, Vol. 19, No. 4, pp. 224-236.]]

Digital Library

Google Scholar

[4]

R. Coltun, 1989: "OSPF: An internet Routing Protocol," ConneXions, Vol. 3, No. 8, pp. 19-25.]]

Google Scholar

[5]

E.W. Dijkstra, 1959: "A Note on Two Problems in Connection with Graphs," Numer. Math., Vol. 1, pp. 269-271.]]

Digital Library

Google Scholar

[6]

E.W. Dijlcstra and C.S. Scholten, 1980: "T~ation Detection for Diffusing Computations,'' Information Processing Letters, Vol. 11, No. 1, pp. 1--4.]]

Crossref

Google Scholar

[7]

L.R. Ford and D.R. Fulkerson, 1962: Flows in Networks. Princeton, NJ: Princeton University Press.]]

Google Scholar

[8]

lJ. Garcia-Luna-Aceves, 1989: "A Minimum-Hop Routing Algorithm Based on Distributed Information," Computer Networks and ISDN Systems, Vol. 16, No. 5, pp. 367-382.]]

Digital Library

Google Scholar

[9]

l.J. Garcia-Luna-Aceves, 1989: "A Unified Approach for Loop-Free Routing Using Link States or Distance Vectors," ACM Computer Communication Review, Vol. 19, No. 4, pp. 212-223.]]

Digital Library

Google Scholar

[10]

C. Hedrick, 1988: "Routing Information Protocol," RFC 1058, Network Information Center, SRI International, Menlo Park, CA 94025 (June).]]

Digital Library

Google Scholar

[11]

R. Hinden and A. Sheltzer, 1982: "DARPA Internet Gateway," RFC 823, Network Information Center, SRI International, Menlo Park, CA 94025, (September).]]

Digital Library

Google Scholar

[12]

International Standards Organization, 1989: "Intra-Domain IS-IS Routing Protocol," ISO/IEC JTC1/SC6 WG2 N323, (September).]]

Google Scholar

[13]

J.M. Jaffe and F.M. Moss, 1982: '% Responsive Routing Algorithm for Computer Networks," IEEE Transactions on Communica. tions, Vol. COM-30, No. 7, pp. 1758-1762.]]

Google Scholar

[14]

J.M. laffe, A.E. Baratz, and A. Segall, 1986: "Subtle Design Issues in the Implementation of Distributed, Dynamic Routing Algorithms," Computer Networks and ISDN Systems, Vol. 12, No. 3, pp. 147-158.]]

Digital Library

Google Scholar

[15]

K. Lougheed and Y. Rekhter, "A Border Gateway Protocol," 1989: RFC 1105, SRi International, Menlo Park, CA 94025 (June).]]

Google Scholar

[16]

P.M. Merlin and A. Segall, 1979: "A Failsafe Distributed Routing Protocol," IEEE Transactions on Communication, Vol. COM-27, No. 9, pp. 1280-1288.]]

Google Scholar

[17]

J. McQuinan, 1974: "Adaptive Routing Algorithms for Distributed Computer Networks," BBN Rep. 2831, Bolt Beranek and Newman Inc., Cambridge MA (May).]]

Google Scholar

[18]

J. McQuillan, et al., 1980: "The New Routing Algorithm for the ARPANET," IEEE Transactions on Communications, Vol. COM-28, (May).]]

Google Scholar

[19]

D. Mills, 1983: "DCN Local-Network Protocols,'' RFC 891, Network Information Center, SKI International, Menlo Park, CA 94025 (December).]]

Digital Library

Google Scholar

[20]

D. Mills, 1983: "Exterior Gateway Protocol Formal Specification," RFC 904, Network Information Center, SKI International, Menlo Park, CA 94025, (December).]]

Digital Library

Google Scholar

[21]

W.E. Naylor 1975: "A Loop-Free Adaptive Routing Algorithm for Packet Switched Networks," Proceedings of the Fourth Data Commumcations Symposium, Quebec City, Canada, pp. 7.9-7.15 (October).]]

Google Scholar

[22]

M. Schwartz, 1986: Telecommunication Networks: Protocols, Modeling and Analysis, Chapter 6, Menlo Park CA: Addison-Wesley Publishing Co.]]

Digital Library

Google Scholar

[23]

K.G. Shin and M. Chert, 1987: "Performance Analysis of Distributed Routing Strategies Free of Ping-Pong-Type Looping," IEEE Transactions on Computers, Vol. COMP-36, No. 2, pp. 129-137.]]

Digital Library

Google Scholar

[24]

T.E. Stem, 1980: "An Improved Routing Algorithm for Distributed Computer Networks," IEEE International Symposium on Circuits and Systems, Workshop on Large- Scale Networks and Systems, Houston, Texas (April).]]

Google Scholar

[25]

W.T. Zaumen, 1991: "Simulations in Drama," Network Information System Center, SKI International, Menlo Park, CA 94025 (January).]]

Google Scholar

Cited By

View all

Wang KQuan WCheng NLiu MLiu YChan H(2019)Betweenness Centrality Based Software Defined RoutingACM Transactions on Internet Technology10.1145/335560519:4(1-19)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1145/3355605
Ray SGuérin RKwong KSofia R(2010)Always acyclic distributed path computationIEEE/ACM Transactions on Networking10.1109/TNET.2009.202537418:1(307-319)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1109/TNET.2009.2025374
Afek YBremler-Barr ASchwarz S(2006)Improved BGP convergence via ghost flushingIEEE Journal on Selected Areas in Communications10.1109/JSAC.2004.83600222:10(1933-1948)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/JSAC.2004.836002
Show More Cited By

Index Terms

Dynamics of distributed shortest-path routing algorithms

Recommendations

Asymptotic optimality of shortest path routing algorithms

Many communication networks use adaptive shortest path routing. By this we mean that each network link is periodically assigned a length that depends on its congestion level during the preceding period, and all traffic generated between length updates ...
Complexity of inverse shortest path routing
INOC'11: Proceedings of the 5th international conference on Network optimization

The inverse shortest path routing problem is to decide if a set of tentative routing patterns is simultaneously realizable. A routing pattern is defined by its destination and two arc subsets of required shortest path arcs and prohibited non-shortest ...
An Appraisal of Some Shortest-Path Algorithms

This paper treats five discrete shortest-path problems: 1 determining the shortest path between two specified nodes of a network; 2 determining the shortest paths between all pairs of nodes of a network; 3 determining the second, third, etc., shortest ...

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 21, Issue 4

Sept. 1991

300 pages

ISSN:0146-4833

DOI:10.1145/115994

Editor:
Craig Partridge
Bolt Beranek and Newman Inc., Cambridge, MA

Issue’s Table of Contents

SIGCOMM '91: Proceedings of the conference on Communications architecture & protocols
August 1991
336 pages
ISBN:0897914449
DOI:10.1145/115992
Chairman:
A. Lyman Chapin
Bolt Beranek and Newman, Cambridge, MA

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1991

Published in SIGCOMM-CCR Volume 21, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
1,421
Total Downloads

Downloads (Last 12 months)102
Downloads (Last 6 weeks)22

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang KQuan WCheng NLiu MLiu YChan H(2019)Betweenness Centrality Based Software Defined RoutingACM Transactions on Internet Technology10.1145/335560519:4(1-19)Online publication date: 1-Nov-2019
https://dl.acm.org/doi/10.1145/3355605
Ray SGuérin RKwong KSofia R(2010)Always acyclic distributed path computationIEEE/ACM Transactions on Networking10.1109/TNET.2009.202537418:1(307-319)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1109/TNET.2009.2025374
Afek YBremler-Barr ASchwarz S(2006)Improved BGP convergence via ghost flushingIEEE Journal on Selected Areas in Communications10.1109/JSAC.2004.83600222:10(1933-1948)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/JSAC.2004.836002
Bremler-Barr AAfek YSchwarz S(2003)Improved BGP convergence via ghost flushingIEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428)10.1109/INFCOM.2003.1208930(927-937 vol.2)Online publication date: 2003
https://doi.org/10.1109/INFCOM.2003.1208930
Zhongjie Li Zhiliang Wang Jianping Wu (2003)Automatic conformance testing of OSPF routersInternational Conference on Communication Technology Proceedings, 2003. ICCT 2003.10.1109/ICCT.2003.1209106(396-399)Online publication date: 2003
https://doi.org/10.1109/ICCT.2003.1209106
Pei DWang LMassey DWu SZhang L(2003)A study of packet delivery performance during routing convergence2003 International Conference on Dependable Systems and Networks, 2003. Proceedings.10.1109/DSN.2003.1209929(183-192)Online publication date: 2003
https://doi.org/10.1109/DSN.2003.1209929
Médard MLumetta S(2003)Network Reliability and Fault ToleranceWiley Encyclopedia of Telecommunications10.1002/0471219282.eot281Online publication date: 15-Apr-2003
https://doi.org/10.1002/0471219282.eot281
Thurston P(1999)Geometric node routing algorithms for low-Earth orbit global satellite communications systemsWCNC. 1999 IEEE Wireless Communications and Networking Conference (Cat. No.99TH8466)10.1109/WCNC.1999.797810(179-182)Online publication date: 1999
https://doi.org/10.1109/WCNC.1999.797810
Behrens JGarcia-Luna-Aceves J(1994)Distributed, scalable routing based on link-state vectorsACM SIGCOMM Computer Communication Review10.1145/190809.19032724:4(136-147)Online publication date: 1-Oct-1994
https://dl.acm.org/doi/10.1145/190809.190327
Behrens JGarcia-Luna-Aceves JCrowcroft J(1994)Distributed, scalable routing based on link-state vectorsProceedings of the conference on Communications architectures, protocols and applications10.1145/190314.190327(136-147)Online publication date: 1-Oct-1994
https://dl.acm.org/doi/10.1145/190314.190327
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

References

Cited By

Index Terms

Recommendations

Asymptotic optimality of shortest path routing algorithms

Complexity of inverse shortest path routing

An Appraisal of Some Shortest-Path Algorithms

Comments

Information

Published In

Publisher

Publication History

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations