2014/07/27 by Hani Salah, Salah, Hani, Stefanie Roos +3
Computer Science · #Distributed #FOS: Computer and information sciences #Networking and Internet Architecture (cs.NI) #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.NI
paper · pdf · doi:10.48550/arxiv.1408.3079
13 pages, 8 figures, conference version 'Diversity Entails Improvement: A new Neighbour Selection Scheme for Kademlia-type Systems' at IEEE P2P 2014
arxiv created 2014/07/27 · arxiv updated 2014/08/14
Discovery of nodes and content in large-scale distributed systems is generally based on Kademlia, today. Understanding Kademlia-type systems to improve their performance is essential for maintaining a high service quality for an increased number of participants, particularly when those systems are adopted by latency-sensitive applications. This paper contributes to the understanding of Kademlia by studying the impact of diversifying neighbours' identifiers within each routing table bucket on the lookup performance. We propose a new, yet backward-compatible, neighbour selection scheme that attempts to maximize the aforementioned diversity. The scheme does not cause additional overhead except negligible computations for comparing the diversity of identifiers. We present a theoretical model for the actual impact of the new scheme on the lookup's hop count and validate it against simulations of three exemplary Kademlia-type systems. We also measure the performance gain enabled by a partial deployment for the scheme in the real KAD system. The results confirm the superiority of the systems that incorporate our scheme.