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 appro- priate 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 distri- bution 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.Les systèmes distribués à grande échelle rassemblent des milliers de noeuds répartis dans le monde. Ces systèmes doivent offrir de bonnes performances de routage indépendamment de leur taille et malgré le taux élevé de connexion\slash déconnexion. Pour cela, le système doit ajouter des raccourcis à son graphe logique (\emph{overlay} en anglais). Cependant, pour construire raccourcis efficaces, les pair ont besoin d'avoir des informations sur la topologie de l'overlay. En cas de distributions de pairs hétérogènes, la récupération de ces informations n'est pas simple. En outre, en raison du fort taux de connexion/déconnexion, la topologie évolue rapidement, ce qui rend vite les informations recueillies obsolètes. Les systèmes de l'état de l'art, soit évitent le problème en forçant les pairs à adopter une distribution uniforme, soit ne satisfont que partiellement les exigences de performances de routage. Pour faire face à ce problème, nous proposons DONUT, un mécanisme de construction d'une carte locale qui se rapproche de la distribution des pairs. Cette carte permet d'estimer localement, avec précision, la distance graphique avec les autres pairs. L'évaluation réalisée avec une matrice de latences réelles et des traces de connexion/déconnexion montre que notre carte augmente l'efficacité du routage d'au moins 20%, comparativement aux techniques de l'état de l'art. Elle montre également que chaque carte est petite et peut être propagé efficacement à travers le réseau en consommant moins de 10 bps sur chaque pair