臺灣博碩士論文加值系統

近年有些index caching的機制被應用於改善Gnutella-like P2P網路的scalability，其中部份research也修改了網路架構以及搜尋(search)方式以配合其index caching的機制。Index caching的方式可以大幅減少搜尋受歡迎物件的traffic，但是在網路上存有過多相同的index是其一個問題點。
在我們的Active Index Diffusing scheme，我們嘗試將各物件的index數量作平均化。被要求率接近的資源，他們的index會被群聚在一起，搜尋也會優先連去存有較高被要求率的index的節點。模擬的結果顯示出我們的架構可以提供更高的搜尋成功率比，搜尋的花費也是有顯著的減少。

In order to improve the scalability and reduce the traffic of Gnutella-like unstructured peer-to-peer networks, index caching mechanisms had been discussed in recent years. Some of them had modified the network architecture and adapted existing search methods for their mechanisms. Although the traffic of querying popular keywords could be reduced by using index caching mechanisms, the cached indices too redundant replications in the whole network.

We try to make the amount of indices fair for each file name in our index diffusing scheme. In our scheme, the indices with similar request rate would be grouped together, and the peers of the group who have indices with
higher request rate will receive query messages earlier. In the simulations, our architecture could perform queries with higher success rates than existing research in multilayer peer-to-peer networks, and the traffic is also decreasing conspicuously.

List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii
Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . 1
1.1 History and Characteristic . . . . . . . . . . . . . . . . . . . . 1
1.2 Categorizations . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Index Caching Mechanism . . . . . . . . . . . . . . . . . . . . 4
1.4 Multilayer Peer-to-Peer Network . . . . . . . . . . . . . . . . . 4
Chapter 2 Related Works . . . . . . . . . . . . . . . . . . . . 6
2.1 Why Not Use DHT . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Blind Search Methods . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Informed Search Methods . . . . . . . . . . . . . . . . . . . . 9
2.4 Caching Mechanisms . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Population of File . . . . . . . . . . . . . . . . . . . . . . . . . 11
Chapter 3 Approaches . . . . . . . . . . . . . . . . . . . . . . 12
3.1 Request Popularity and Disposition . . . . . . . . . . . . . . . 12
3.2 Central Control of Indices . . . . . . . . . . . . . . . . . . . . 13
3.2.1 Clustering peers who share the same file name . . . . . 15
3.2.2 Index update when hit occurs the index . . . . . . . . 16
3.2.3 Actively diffusing indices . . . . . . . . . . . . . . . . . 16
3.2.4 Copy indices when peer joins . . . . . . . . . . . . . . 17
3.3 Network Architecture . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Search Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4.1 Flooding Size and Success Rate . . . . . . . . . . . . . 19
3.4.2 Flooding of Query . . . . . . . . . . . . . . . . . . . . 20
3.4.3 Modified Search Methods . . . . . . . . . . . . . . . . 23
Chapter 4 Simulations and Results . . . . . . . . . . . . . . 26
4.0.4 Simulation Environment . . . . . . . . . . . . . . . . . 26
4.0.5 Experimental Results . . . . . . . . . . . . . . . . . . . 27
Chapter 5 Conclusion . . . . . . . . . . . . . . . . . . . . . . 34
Appendix A References . . . . . . . . . . . . . . . . . . . . . 35

[1] A. Fisk. Gnutella dynamic query protocol v0.1, http://www9.limewire.com/developer/dynamic query.html , May 2003.
[2] An-Hsun Cheng, Yuh-Jzer Joung, “Probabilistic file indexing and searching in unstructured peer-to-peer networks,” in Computer Networks: The International Journal of Computer and Telecommunications Networking, Vol. 50, Issue 1, pp. 106-127, Jan. 2006.
[3] B. Yang and H. Garcia-Molina, “Improving Search in Peer-to-Peer Networks,” in Proceedings of the 22nd International Conference on Distributed Computing Systems (ICDCS''02), pp. 5, Jun. 2002.
[4] C. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, “Search and Replication in Unstructured Peer-to-Peer Networks,” in Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, pp.258-259. Jun 2002.
[5] Chord, http://www.pdos.lcs.mit.edu/chord
[6] Clay Shirky, “What Is P2P … And What Isn’t”, http://www.openp2p.com/pub/a/p2p/2000/11/24/shirky1-whatisp2p.html , Nov. 2000.
[7] D. Menasc’e and L. Kanchanapalli, “Probabilistic Scalable P2P Resource Location Services,” ACM Sigmetrics Performance Evaluation Review, Vol. 30, No. 2, Sep. 2002.
[8] D. Tsoumakos and N. Roussopoulos, “Analysis and Comparison of P2P Search Methods,” Proceedings of the 1st International Conference on Scalable Information Systems (INFOSCALE 2006), No. 25, May 2006.
[9] Gnutella website, http://www.gnutella.com
[10] H. Jiang and S. Jin, "Exploiting dynamic querying like flooding techniques in unstructured peer-to-peer networks," in Proc. IEEE Internet Conference on Network Protocol (ICNP), pp. 122-131, Oct. 2005.
[11] KaZaA, http://www.kazaa.com
[12] Li, J., Loo, B. T., Hellerstein, J., Kaashoek, F., Karger, D. R., and Morris, R. “On the Feasibility of Peer-to-Peer Web Indexing and Search,” in 2nd International Workshop on Peer-to-Peer Systems (IPTPS), pp. 207-215, Feb. 2003.
[13] LimeWire, http://www.limewire.com
[14] N. Ambastha, I. Beak, S. Gokhale, and A. Mohr, “A cache-based resource location approach for unstructured P2P network architectures,” In Graduate Research Conference, Department of Computer Science, Stony Brook University, May 2003.
[15] O. Saleh and M. Hefeeda, “Modeling and Caching of Peer-to-Peer Traffic,” In Proc. of 14th IEEE International Conference on Network Protocols (ICNP''06), pp. 249-258, Nov, 2006.
[16] Share, via Freenet http://127.0.0.1:8888/SSK@szGkEWGmpXKoQHqsu9ubZze-kOgPAgM/CAT/17//
[17] Stephanos Androutsellis-Theotokis and Diomidis Spinellis, “A Survey of Peer-to-Peer Content Distribution Technologies,” ACM Computing Surveys, Vol. 36, issue 4, pp. 335-371, Dec. 2004.
[18] Tang, C., Xu, Z., and Mahalingam, M. “pSearch: Information Retrieval in Structured Overlays,” ACM SIGCOMM Computer Communication Review, vol. 33, issue 1, pp. 89-94, Jan. 2003.
[19] Ultrapeer, http://rfc-gnutella.sourceforge.net/src/Ultrapeers_1.0.html
[20] V. Kalogeraki, D. Gunopulos, and D. Zeinalipour-Yazti, “A Local Search Mechanism for Peer-to-Peer Networks,” in Proceedings of the Eleventh International Conference on Information and Knowledge Management, pp. 300-307, Nov. 2002.
[21] Wang, C. Xiao, L. Liu, Y. Zheng, P., “Distributed caching and adaptive search in multilayer P2P networks,” in International Conference on Distributed Computing Systems (ICDCS’04), pp. 219-226, Mar. 2004.
[22] Winny, http://www.geocities.co.jp/SiliconValley/2949/
[23] Xie Yinglian, O''Hallaron D. “Locality in Search Engine Queries and Its Implications for Caching,” In Proc IEEE Infocom, pp. 1238-1247, 2002.
[24] Y. Chawathe, S. Ratnasamy,. L. Breslau, N. Lanham, S. Shenker, "Making Gnutella-like P2P Systems Scalable," in Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pp. 407-418, Aug. 2003.
[25] Z. Silagadze, “Citations and the Zipf-Mandelbrot’s law,” Complex Systems, Vol. 11, pp. 487-499, 1997.