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

Funding Information:
1. Introduction A basic activity in a distributed network is the routing of messages between pairs of nodes. Assuming a cost function on the edges of the network, it is desirable that the routing of each message be along a shortest path. A straightforward approach is to maintain a complete routing table at each of the n nodes, which gives for each potential destination the name of the next node on a shortest path to the destination. This approach * This research was supported in part by the National Science Foundation under grant DCR-8320124.

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