Relaxed-2-Chord: Efficiency, flexibility and provable stretch

摘要

Several proposals have been presented to supplement the traditional measure of routing efficiency in P2P networks, i.e. the (average) number of hops for lookup operations, with measures of the latency incurred in the underlying network. So far, no solution has been presented to this ldquolatencyrdquo problem without incurring in extra and heavy management costs. We propose Relaxed-2-Chord, a new design of the traditional Chord protocol, that is able to fit the routing tables with low latency nodes, doing a parasitic measurement of nodes' latency without adding any overhead. The solution that we present is a distributed Hash table system whose aim is to combine the routing efficiency and flexibility of the Chord protocol - i.e. a good degree/diameter tradeoff - and a provable optimal hop by hop latency. Our work is inspired by the recent lookup-parasitic random sampling (LPRS) strategies which allow to improve the network stretch, that is, the ratio between the latency of two nodes on the overlay network and the unicast latency between those nodes. Relaxed-2-Chord reaches the same results as LPRS without introducing any overhead.