Routing indices for peer-to-peer systems
Tóm tắt
Finding information in a peer-to-peer system currently requires either a costly and vulnerable central index, or flooding the network with queries. We introduce the concept of routing indices (RIs), which allow nodes to forward queries to neighbors that are more likely to have answers. If a node cannot answer a query, it forwards the query to a subset of its neighbors, based on its local RI, rather than by selecting neighbors at random or by flooding the network by forwarding the query to all neighbors. We present three RI schemes: the compound, the hop-count, and the exponential routing indices. We evaluate their performance via simulations, and find that RIs can improve performance by one or two orders of magnitude vs. a flooding-based system, and by up to 100% vs. a random forwarding system. We also discuss the tradeoffs between the different RI schemes and highlight the effects of key design variables on system performance.
Từ khóa
#Routing #Peer to peer computing #System performance #Distributed computing #Robustness #Costs #Web search #Search engines #Computer hackingTài liệu tham khảo
gravano, 1994, The effectiveness of gloss for the text-database discovery problem, Proceedings of SIGMOD, 10.1145/191843.191869
10.1109/PDIS.1994.331726
gravano, 2000, Gloss: Text-source discovery over the internet, TODS
10.1145/371578.371598
10.1145/378993.379239
adamic, 2001, Search in power-law networks. Technical report, HP Labs
miller, 1998, Multicast Networking and Applications
0, Napster
10.1145/964723.383072
rowstron, 2001, Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems, Middleware
10.1109/ICDCS.2002.1022239
0, Clip2.com, at, Gnutella To the Bandwidth and Beyond
ford, 1962, Flows in Networks
10.1145/316194.316229
0, Gnutella
0, Freenet
10.1016/S0169-7552(98)00110-X
gravano, 1995, Generalizing gloss for vector-space databases and broker hierarchies, Proceedings of VLDB
bellman, 1957, Dynamic Programming
0, Seti at Home
tanenbaum, 1999, Operating Systems Design and Implementation
10.1145/383059.383071
yang, 2001, Comparing hybrid peer-to-peer systems, VLDB
tanenbaum, 1996, Computer Networks
zhao, 2001, Tapestry: An infrastructure for fault-tolerant wide-area location and routing, Technical Report UCB/CSD-01–1141 Computer Science Division
yang, 2002, Efficient search in peer-to-peer networks, ICDCS