A routing mechanism for unstructured peer-to-peer systems based on hop-limited shortest-path trees

ABSTRACT

We propose a simple mechanism for supporting routing control in unstructured P2P systems. In the proposal, each node keeps the information on the hop-limited shortest path trees whose roots are located around the neighbor. Here, the hop-limited tree means the one that is made of nodes within a certain number of hops (say n hops) from the root. When a node receives a unicast message, it transmits the message to the upstream neighbor on the shortest-path tree rooted at the message destination only if the destination is located within the n-hop radius. Otherwise, it generates duplicates of the original message and forwards them to downstream neighbors on the shortest-path tree rooted at the message source. The information of upstream and downstream neighbors on the shortest path trees is stored in the message forwarding or the routing tables, which are constructed and updated in a fully distributed fashion. Numerical examples show that our proposal can largely reduce the number of queries generated in a file search.

References

1. Gnutella. http://www.gnutella.com.
2. Freenet. http://freenet.sourceforge.net.
3. KaZaa. http://www.kazaa.com.
4. BitTorrent. http://bittorrent.com.
5. L. Adamic, R. Lukose, A. Puniyani, and B. Huberman. Search in power-law networks. Physical Review, E64 46135, 2001.
6. A. L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286:251--262, 1999.
7. B. M. Waxman. Routing of multipoint connections. IEEE Journal of Selected Areas in Communication, 6(9):1617--1622, 1988.
8. Y. Chawathe, S. Ratnasamy, L. Breslau, N. Lanham, and S. Shenker. Making Gnutella-like P2P systems scalable. In ACM SIGCOMM 2003, pages 407--418, 2003.
9. P. Druschel and A. Rowstron. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In the 18th IFIP/ACM International Conference on Distributed Systems Platform, 2001.
10. J. F. Kurose and K. W. Ross. Computer Networking 4th edition. Addison Wesley, 2007.
11. Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. In The 16th ACM International Conference on Supercomputing, 2002.
12. K. Ohtsuka, T. Satoh, and S. Shioda. An efficient technique for message flooding based on partial shortest-path trees in wired networks. In IEEE ICC, 2007.
13. S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable content-addressable network. In ACM SIGCOMM, pages 161--172, 2001.
14. S. Shioda, K. Ohtsuka, and T. Satoh. An efficient network-wide broadcasting based on hop-limited shortest-path trees. Computer Networks, 52:3284--3295, 2008.
15. I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In ACM SIGCOMM, 2001.
16. B. Yang and H. Garcia-Molina. Improving search in peer-to-peer networks. In IEEE ICDCS 2002, 2002.
17. B. Yang and H. Garcia-Molina. Designing a super-peer network. In IEEE ICDE, 2003.
18. B. Zhao, J. Kubiatowicz, and J. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, University of California at Berkeley, Computer Science Department, 2001.

Index Terms

• Computer systems organization

  • Architectures

    • Distributed architectures

  • Dependable and fault-tolerant systems and networks

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Networks

  • Network performance evaluation

  • Network protocols

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles