Building small worlds in unstructured P2P networks using a multiagent Bayesian inference mechanism

ABSTRACT

Over the past few years, peer-to-peer(p2p) unstructured networks have emerged as an attractive paradigm for enabling online interactions between a large number of users in a decentralized manner. However, the decentralized nature of unstructured p2p networks makes load balancing a challenging problem. Specifically, the self-interested nature of users on the nodes of a p2p network and dynamic changes in network topology give rise to an unbalanced distribution of nodes across an unstructured p2p network. This results in network congestion and significant search latencies for all nodes. In this paper, we describe a small-world network model and a Bayesian inference mechanism within a multiagent setting to address these issues. Simulation results for a file sharing p2p application show that our algorithm achieves an exponential reduction in number of messages exchanged and improves load-balancing across the network.

REFERENCES

• 1: P. Oscar Boykin , Vwani P. Roychowdhury, Leveraging Social Networks to Fight Spam, Computer, v.38 n.4, p.61-68, April 2005 [doi>10.1109/MC.2005.132]
• 2: Prithviraj Dasgupta, A Multi-agent Mechanism for Topology Balancing in Unstructured P2P Networks, Proceedings of the IEEE/WIC/ACM international conference on Intelligent Agent Technology, p.389-392, December 18-22, 2006 [doi>10.1109/IAT.2006.16]
• 3: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 4: T. Klingberg and R. Manfredi. Gnutella 0.6 protocol specification draft. 2002.
• 5: Shashidhar Merugu , Sridhar Srinivasan , Ellen Zegura, Adding structure to unstructured peer-to-peer networks: the use of small-world graphs, Journal of Parallel and Distributed Computing, v.65 n.2, p.142-153, February 2005 [doi>10.1016/j.jpdc.2004.09.004]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Design, Experimentation, Management

Keywords:
P2P networks, small world graphs, topology balancing