Compact Routing in Power-Law Graphs

Message routing is a fundamental service in communication networks. When routing a message from a source to a destination in the network, to decide where to forward the message to, a node may only use its local information, which includes its local routing table, the destination address, and a message header. A routing scheme is expected to route messages between all source-destination pairs along shortest or approximate shortest paths. A key measure of the quality of a routing scheme is its worst-case multiplicative stretch, which is defined as the maximum ratio of the length of the message route between a pair of nodes s and t by the scheme and the actual shortest path length between s and t, among all s-t pairs in the network.