NETOP: A Non-Cooperative Game Based Topology Optimization Model towards Improving Search Performance

Abstract

Resource searching is an important function for resource sharing and cooperative work in large-scale distributed networks like grid and peer-to-peer (P2P). Many works have focused on optimizing network topology in order to improve search performance. However, these works rarely take into account the interaction of nodes' optimizing behaviors and the connection cost. We propose a Non-cooperative game based Topology Optimization model (NETOP) to enhance search performance in unstructured P2P networks. Each participating node in NETOP is a rational player who selects optimizing strategy (its node degree) according to both its private information and the public information. We prove the existence and uniqueness of Nash Equilibrium (NE) of the game, and present the performance analysis of this model. Moreover, we also take network dynamics into account and extend our model to adapt to the node churn. Experimental results show that NETOP network converges rapidly and achieves higher performances. When compared with Power-law and Square-root topologies in a static condition, NETOP network achieves the same success rate with 33.3% and 6% lower connection cost, 18% and 13.2% lower average hop count, and 4.6% and 6.5% fewer messages, meanwhile in a dynamic condition, it achieves 28.9% and 11.5% lower connection cost, 14.3% and 7.7% lower average hop count, and 26.6% and 28.7% fewer messages.