Detecting and Reducing Partition Nodes in Limited-routing-hop Overlay Networks

Many Internet applications use overlay networks as their basic facilities, like resource sharing, collaborative com-puting, and so on. Considering the communication cost, most overlay networks set limited hops for routing mes-sages, so as to restrain routing within a certain scope. In this paper we describe partition nodes in such limited-routing-hop overlay networks, whose failure may poten-tially lead the overlay topology to be partitioned so that seriously affect its performance. We propose a proactive, distributed method to detect partition nodes and then re-duce them by changing them into normal nodes. The results of simulations on both real-trace and generated topologies, scaling from 500 to 10000 nodes, show that our method can effectively detect and reduce partition nodes and improve the connectivity and fault tolerance of overlay networks.