Article

Compact routing schemes

Authors:

Mikkel Thorup,

Uri ZwickAuthors Info & Claims

SPAA '01: Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures

Pages 1 - 10

https://doi.org/10.1145/378580.378581

Published: 03 July 2001 Publication History

Get Access

Abstract

We describe several compact routing schemes for general weighted undirected networks. Our schemes are simple and easy to implement. The routing tables stored at the nodes of the network are all very small. The headers attached to the routed messages, including the name of the destination, are extremely short. The routing decision at each node takes constant time. Yet, the stretch of these routing schemes, i.e., the worst ratio between the cost of the path on which a packet is routed and the cost of the cheapest path from source to destination, is a small constant. Our schemes achieve a near-optimal tradeoff between the size of the routing tables used and the resulting stretch. More specifically, we obtain:

A routing scheme that uses only O (n ^1/2) bits of memory at each node of an n-node network that has stretch 3. The space is optimal, up to logarithmic factors, in the sense that every routing scheme with stretch < 3 must use, on some networks, routing tables of total size Ω(n²), and every routing scheme with stretch < 5 must use, on some networks, routing tables of total size Ω(n^3/2). The headers used are only (1 + O(1)) log²> n-bits long and each routing decision takes constant time. A variant of this scheme with [log₂ n] -bit headers makes routing decisions in O(log log n) time.

Also, for every integer k > 2, a general handshaking based routing scheme that uses O (n^1/k) bits of memory at each node that has stretch 2k - 1. A conjecture of Erdös from 1963, settled for k = 3, 5, implies that the routing tables are of near-optimal size relative to the stretch. The handshaking is similar in spirit to a DNS lookup in TCP/IP. Headers are O(log² n) bits long and each routing decision takes constant time. Without handshaking, the stretch of the scheme increases to 4k - 5. One ingredient used to obtain the routing schemes mentioned above, may be of independent practical and theoretical interest:

A shortest path routing scheme for trees of arbitrary degree and diameter that assigns each vertex of an n-node tree a (1 + O(1)) log² n-bit label. Given the label of a source node and the label of a destination it is possible to compute, in constant time, the port number of the edge from the source that heads in the direction of the destination.

The general scheme for k > 2 also uses a clustering technique introduced recently by the authors. The clusters obtained using this technique induce a sparse and low stretch tree cover of the network. This essentially reduces routing in general networks into routing problems in trees that could be solved using the above technique.

References

[1]

S. Abiteboul, T. Milo, and H. Kaplan. Compact labeling schemes for ancestor queries. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Washington, D.C., pages 547-556, 2001.

Abstract

References

Cited By

Index Terms

Recommendations

Compact routing schemes with improved stretch

Scale-Free Compact Routing Schemes in Networks of Low Doubling Dimension

Average stretch analysis of compact routing schemes

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations