Optimal message routing without complete routing tables

Greg N. Frederickson; Ravi Janardan

doi:10.1145/10590.10598

Optimal message routing without complete routing tables

Greg N. Frederickson, Ravi Janardan

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
Publisher	Association for Computing Machinery
Pages	88-97
Number of pages	10
ISBN (Electronic)	0897911989
DOIs	https://doi.org/10.1145/10590.10598
State	Published - Nov 1 1986
Externally published	Yes
Event	5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986 - Calgary, Canada Duration: Aug 11 1986 → Aug 13 1986

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other	5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986
Country/Territory	Canada
City	Calgary
Period	8/11/86 → 8/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.

Publisher link

10.1145/10590.10598

Find It

Find It at U of M Libraries

Cite this

Optimal message routing without complete routing tables. / Frederickson, Greg N.; Janardan, Ravi.

Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 1986. p. 88-97 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Frederickson, GN & Janardan, R 1986, Optimal message routing without complete routing tables. in Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, pp. 88-97, 5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986, Calgary, Canada, 8/11/86. https://doi.org/10.1145/10590.10598

@inproceedings{dcde03d277ec4e5ea7de23319b5b8ee3,

title = "Optimal message routing without complete routing tables",

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.",

author = "Frederickson, {Greg N.} and Ravi Janardan",

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: {\textcopyright} 1986 ACM.; 5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986 ; Conference date: 11-08-1986 Through 13-08-1986",

year = "1986",

month = nov,

day = "1",

doi = "10.1145/10590.10598",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "88--97",

booktitle = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

}

TY - GEN

T1 - Optimal message routing without complete routing tables

AU - Frederickson, Greg N.

AU - Janardan, Ravi

N1 - 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.

PY - 1986/11/1

Y1 - 1986/11/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0347843592&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347843592&partnerID=8YFLogxK

U2 - 10.1145/10590.10598

DO - 10.1145/10590.10598

M3 - Conference contribution

AN - SCOPUS:0347843592

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 88

EP - 97

BT - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 5th Annual ACM Symposium on Principles of Distributed Computing, PODC 1986

Y2 - 11 August 1986 through 13 August 1986

ER -

Optimal message routing without complete routing tables

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this