Lookup Performance Deficiencies in the KAD Network

The KAD network is one of the largest distributed hash tables (DHT) deployed in the real world. DHT is designed to provide scalable peer-to-peer lookup service. Its real-world lookup performance, however, is recognized as inefficient. We ran wide-range measurements on the KAD network to evaluate this inefficiency by examining peer behaviors in publishing and retrieving information using routing tables and publishing tables. Our measurements show that even though routing tables are well maintained, the current refreshment scheme of publishing tables and lack of effective incentive policy cause lookup performance deficiency. Based on our findings, we propose three improvement schemes, analyze their strengths, and give suggestions to implementations.