DONUT: Building Shortcuts in Large-Scale Decentralized Systems
with Heterogeneous Peer Distributions.
Abstract:
Large-scale distributed systems gather thousands of peers spread
all over the world. Such systems need to offer good routing
performances regardless of their size and despite high churn
rates. To achieve that requirement, the system must add appropriate shortcuts to its logical graph (overlay). However, to
choose efficient shortcuts, peers need to obtain information
about the overlay topology. In case of heterogeneous peer
distributions, retrieving such information is not
straightforward. Moreover, due to churn, the topology rapidly
evolves, making gathered information obsolete. State-of- the-art
systems either avoid the problem by enforcing peers to adopt a
uniform distribution or only partially fulfill these
requirements. To cope with this problem, we propose DONUT, a
mechanism to build a local map that approximates the peer
distribution, allowing the peer to accurately estimate graph
distance to other peers with a local algorithm. The evaluation
performed with real latency and churn traces shows that our map
increases the routing process efficiency by at least 20%
compared to the state-of-the-art techniques. It points out that
each map is lightweight and can be efficiently propagated
through the network by consuming less than 10 bps on each peer.