Degree-optimal routing for P2P systems

We define a family of Distributed Hash Table systems whose aim is to combine the routing efficiency of randomized networks -- e.g. optimal average path length O(log^2 n/delta log delta) with delta degree -- with the programmability and startup efficiency of a uniform overlay -- that is, a deterministic system in which the overlay network is transitive and greedy routing is optimal. It is known that Omega(log n) is a lower bound on the average path length for uniform overlays with O(log n) degree. Our work is inspired by neighbor-of-neighbor (NoN) routing, a recently introduced variation of greedy routing that allows to get optimal average path length in randomized networks. Our proposal has the advantage of allowing the NoN technique be implemented without adding any overhead to the corresponding deterministic network. We propose a family of networks parameterized with a positive integer c which measures the amount of randomness that is used. Varying the value c, the system goes from the deterministic case (c=1) to an ``almost uniform'' system. Increasing c to relatively low values allows routing with asymptotically optimal average path length while retaining most of the advantages of a uniform system, such as easy programmability and quick bootstrap of the nodes entering the system. We also provide a matching lower bound for the average path length of the routing schemes for any c.