Compact routing schemes

TLDR

The paper proposes several compact routing schemes for general weighted undirected networks. The schemes use small routing tables, short headers, and constant‑time per‑hop decisions while maintaining a small constant stretch. The schemes achieve a near‑optimal tradeoff between routing table size and stretch.

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: