Optimal message routing without complete routing tables

Greg N. Frederickson, Ravi Janardan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

Classes of network topologies are identified in which shortest paths information can be succinctly stored at the nodes, if suitable names are assigned to them. The naming allows each edge at a node to be labelled with zero or more intervals of integers, representing all nodes reachable by a shortest path via that edge. Starting with the class of outerplanar networks, a natural hierarchy is established, based on the number of intervals required. The outerplanar networks are shown to be precisely the networks requiring just one interval per edge. An optimal algorithm is given for determining the labels for edges in outerplanar networks.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages88-97
Number of pages10
ISBN (Electronic)0897911989
DOIs
StatePublished - Nov 1 1986
Externally publishedYes
Event5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986 - Calgary, Canada
Duration: Aug 11 1986Aug 13 1986

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986
Country/TerritoryCanada
CityCalgary
Period8/11/868/13/86

Bibliographical note

Publisher Copyright:
© 1986 ACM.

Fingerprint

Dive into the research topics of 'Optimal message routing without complete routing tables'. Together they form a unique fingerprint.

Cite this