點對點網路在最近幾年已被廣泛地應用在分散式資源共享。在點對點網路中，資源搜尋是首要的挑戰，包括冗長的搜尋時間、大量的重複訊息與較低的成功率。既存的文獻提出許多解決之道，然而，絕大多數的方法都只適用在熱門資源的搜尋。在這篇論文中，我們提出以支配集合為根據的隨機複製行走者方法，使其能同時適用在點對點網路中熱門和冷門的資源搜尋，並在搜尋時間、訊息重複量與成功率中，試著去找出較佳的平衡點。

Peer-to-Peer (P2P) networks have been developed for resource sharing for years. In a Peer-to-Peer network, resource locating is the first and foremost challenge, including issues about long searching time, a large amount of query message duplication and a lower success rate. The existing literatures have proposed many efficient methods to resolve these issues. However, most of the proposals only benefit locating the popular object.
In this thesis, we propose a Cloning Random Walker with a Dominating Set method to adaptively locate the resources no matter the target object is popular or unpopular in an unstructured P2P network. Meanwhile, we try to perform a better trade-off among searching time, message duplication and success rate evaluation metrics.

[1]Q. Lv, P. Cao, E. Cohen, “Search and replication in unstructured peer-to-peer networks”, ICS 2002
[2]V. Kalogeraki, D. Gunopulos, D. Zeinalipour-Yazti, “A local search mechanism for peer-to-peer networks”, CIKM 2002
[3]A. Crespo, H. Garcia-Molina, “Routing indices for peer-to-peer Systems”, ICDCS 2002
[4]B. Yang, H. Garcia-Molina, “Improving search in peer-to-peer Networks”, ICDCS 2002
[5]D. Menasce, L. Kanchanapalli, “Probabilistic scalable P2P resource location services”, SIGMETRICS 2002
[6]S. Jiang, L. Guo, X. Zhang, H. Wang “LightFlood: Minimizing redundant messages and maximizing the scope of peer-to-peer search”, IEEE Transaction on Parallel and Distributed Systems, May. 2008.
[7]D. Tsoumakos, N. Roussopoulos, “Adaptive probabilistic search for peer-to-peer networks”, P2P 2003
[8]C. Gkantsidis, M. Mihail, “Hybrid search schemes for unstructured peer-to-peer network”, INFOCOM 2005
[9]S. Chen, Z. Zhang, S. Chen, B. Shi , “Efficient file search in non-DHT P2P networks”, Computer Communication, Feb. 2008
[10]K. Puttaswamy, A. Sala, B. Zhao, “Searching for rare objects using index replication”, INFOCOM 2008
[11]D. Tsoumakos, N. Roussopoulos, “A comparison of peer-to-peer search methods”, WebDB 2003
[12]W. Aiello, F. Chung, L. Lu, “A random graph model for massive graphs”, STOC 2000
[13]A. Kumar, J. Xu, E. W. Zegura, “Efficient and scalable query routing for unstructured peer-to-peer networks”, INFOCOM 2005
[14]Y. Chawathe, S. Ratnasamy, L. Breslau, “Making Gnutella-like P2P systems scalable”, SIGCOMM 2003
[15]H. Jiang, S. Jin, “Exploiting dynamic querying like flooding techniques in unstructured peer-to-peer networks, ICNP 2005”
[16]L. Jia, R. Rajaraman, T. Suel, “An efficient distributed algorithm for constructing small dominating sets”, PODC 2001
[17]B. Liang and Z. Hass., “Virtual backbone generation and maintenance in ad-hoc network mobility management”, INFOCOM 2000
[18]F. Kuhn and R. Wattenhofer., “Constant-time distributed dominating set approximation”, PODC 2003
[19]A. Rowstron and P. Druschel, “Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems,” Proc.Middleware, 2001.
[20]I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, “Chord: A scalable peer-to-peer lookup protocol for internet applications”, IEEE/ACM Transactions on Networking, vol. 11, 2003.
[21]B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz, “Tapestry: A resilient global-scale overlay for service deployment,” IEEE Journal on Selected Areas in Communications , Jan. 2004.
[22]P. Maymounkov and D. Mazi`eres, “Kademlia: A peer-to-peer information system based on the xor metric,” IPTPS 2002
[23]Freenet. http://freenetproject.org/
[24]Fasttrack http://www.fasttrack.nu/
[25]Kazaa media desktop. http://www.kazaa.com/
[26]Bittorrent. http://www.bittorrent.com/
[27]Limewire http://www.limewire.com/
[28]M. Zaharia, S. Keshav, “Gossip-based search selection in hybrid peer-to-peer networks,” IPTPS 2006
[29]X. Shi, J. Han, Y. Liu, L. M. Ni, “Popularity adaptive search in hybrid p2p systems.” IPTPS 2007
[30]H. Chen, H. Jin, Y. Liu, L. M. Ni, “Difficulty-aware hybrid search in peer-to-peer networks“, IEEE Transaction on Parallel and Distributed systems, Jan..2009
[31]B.T. Loo, R. Huebsch, I. Stoica, J.M. Hellerstein, “The case for a hybrid P2P search in frastructure”, IPTPS 2004.