Packet Loss and Overlay Size Aware Broadcast in the Kademlia P2P System
Zoltán Czirkos, György Bognár and Gábor Hosszú
Journal Title:ACEEE International Journal on Communication
Kademlia is a structured peer-to-peer (P2P) application level network, which implements a distributed hash table (DHT). Its key-value storage and lookup service is made efficient and reliable by its well-designed binary tree topology and dense mesh of connections between participant nodes. While it can carry out data storage and retrieval in logarithmic time if the key assigned to the value in question is precisely known, no complex queries of any kind are supported. In this article a broadcast algorithm for the Kademlia network is presented, which can be used to implement such queries. The replication scheme utilized is compatible with the lookup algorithm of Kademlia, and it uses the same routing tables. The reliability (coverage) of the algorithm is increased by assigning the responsibility of disseminating the broadcast message to many nodes at the same time. The article presents a model validated with simulation as well. The model can be used by nodes at runtime to calculate the required level of replication for any desired level of coverage. This calculation can take node churn, packet loss ratio and the size of the overlay into account.