An Improved Adaptive Routing Algorithm Based on Link Analysis

DHT (Distributed Hash Tables) has been applied to the structured P2P system to achieve information retrieval and positioning efficiently. KAD is a large-scale network protocol based on the XOR metric in practice, which uses DHT technology to improve network salability without central server. However, the increasing malicious pollutes routing tables to reduce seriously the query performance. Thus, an improved adaptive algorithm based on social network is proposed in order to improve routing table updating algorithm. Firstly, the data structure of routing table is adjusted to store value of centrality and prestige. Secondly, the request nodes can adaptive select nodes to send messages. Then when a find process is terminated, the node will calculate the two values for all participating nodes using the corresponding centrality and prestige algorithms based on XOR metric. Finally, the node updates the routing table depend on the above result. The above algorithm was implemented in an open source project named LibTorrent to test effectiveness. This experiment last a month to verify the change of the search success ratio in a KAD network with about 30% malicious nodes. The results show that the optimized adaptive routing algorithm can effectively resist the attack for routing table and improve the search success ratio of the node. Moreover, this lightweight algorithm is conducive to the deployment in practice without extra network burden.