Silk: A Resilient Routing Fabric for Peer-to-Peer Networks
Simon S. Lam, Huaiyu Liu · 2003
Several proposed peer-to-peer networks use hypercube routing for scalability. In a previous paper, we showed that consistency of neighbor tables in hypercube routing guarantees the existence of a path from any source node to any destination node. Consistency, however, can be broken by the failure of one node. To improve the robustness of hypercube routing, we generalize the concept of consistency to K-consistency for K # #. We then show that a K-consistent hypercube routing network provides at least K disjoint paths from any source node to any destination node with a probability close to 1. The first objective of this report is the design and specification of a new join protocol together with a proof that it generates K-consistent neighbor tables for an arbitrary number of concurrent joins (under the assumption that there is no concurrent leave or failure). To do so, we construct a more general definition of C-set tree than our previous one as the conceptual foundation for protocol design and reasoning about K- consistency. Both the new protocol and proof require major extensions to the ones in our previous paper to generalize them from 1-consistency to K-consistency.