This paper presents and experimentally evaluates a new algorithm for efficient one-hop link-state routing in full-mesh networks. Prior techniques for this setting scale poorly, as each node incurs quadratic (n 2 ) communication overhead to broadcast its link state to all other nodes. In contrast, in our algorithm each node exchanges routing state with only a small subset of overlay nodes determined by using a quorum system. Using a two round protocol, each node can find an optimal one-hop path to any other node using only n 1.5 pernode communication. Our algorithm can also be used to find the optimal shortest path of arbitrary length using only n 1.5 log n pernode communication. The algorithm is designed to be resilient to both node and link failures. We apply this algorithm to a Resilient Overlay Network (RON) system, and evaluate the results using a large-scale, globally distributed set of Internet hosts. The reduced communication overhead from using our improved full-mesh algorithm allows the creation of all-pairs routing overlays that scale to hundreds of nodes, without reducing the system's ability to rapidly find optimal routes.
Sontag et al. REF proposed a protocol allowing each node to find an optimal one-hop path to any other node with a communication overhead O(n 1.5 ).
Scaling all-pairs overlay routing
CoNEXT '09
Computer Science