DONUT: Building Shortcuts in Large-Scale Decentralized Systems with Heterogeneous Peer Distributions

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 fulfil 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.