臺灣博碩士論文加值系統

在對等網路的架構中，網路上的每個節點都擁有相等的地位，所有的資源也都分散在網路中的每個節點，因此資源發現的問題也就隨著對等網路的架構不同而有各種不同的解決方法。傳統的架構（如Napster[3]）採用數台伺服器負責使用者的查詢要求，但是這樣的架構卻造成大部分的網路流量集中在伺服器端，且一旦伺服器遭受惡意攻擊則整個網路就隨之崩潰。
Gnutella[21]和FreeNet[22]皆採用完全分散不需要伺服器的架構，Gnutella利用泛洪(flooding)的方式來傳送查詢訊息，並且採用類似TCP/IP TTL的方法限制訊息在一定的範圍內傳送，但是利用泛洪方式來傳送控制訊息造成網路極大的負擔，而且並無法保證在一定的轉送（forwarding）次數後可以找到查詢的目標。FreeNet也是採用類似泛洪的方式，與Gnutella不同的是它採用的是深度優先搜尋（Depth-first search）而Gnutella是採用廣度優先搜尋（Broad-first search）。
OceanStone[27]、Chord[26]、PAST[31]等新的架構解決了以上的缺點，而且如果目標存在的話可以保證在一定的轉送次數後找到，他們主要是利用分散式的路由表作為查詢的基礎，以上三者都建構在overlay network上的虛擬網路結構（virtual network topology）。值得注意的是虛擬網路上相鄰的節點對應到實際的網路可能是距離很遠的兩點。相反的，虛擬網路上相距很遠的兩點，可能實際距離很近。因此本論文以叢集的方式針對Chord的架構作變形，利用區域網路中廣播（broadcasting）的優勢結合同一區域網路中的節點，以期能減低因為節點加入與離開所產生的訊息溝通，並加強系統的強健性。

In peer-to-peer network architecture, every node play the equal roles in the network. All resources are distributed among the nodes in the network. Resource discovery problems can be solved with various architectures. Napster[3], which is a popular P2P software, uses several centralized servers to handle clients’ lookup requests. However, such architecture would bring much flow to the server-side. Furthermore, once the centralized servers are under attack, the peer-to-peer network will crush.
Gnutella[21] and FreeNet[22] use pure decentralized architecture. Gnutella floods its lookup query messages to a limit range of its neighbors by preset hop counts. However, flooding mass control messages will make heavy network loading. It also cannot guarantee that the target will be found. FreeNet use the similar way as Gnutella does. The difference between FreeNet and Gnutella is that the former uses depth-first search and the other uses broad-first search.
New architectures like OceanStone[27], Chord[26], and PAST[31], make an improvement which can guarantee the target will be found if the target exists. They mainly use distributed hash tables to handle the lookup queries. The above architectures are all built in virtual network topology. Two nodes which are neighbors on virtual network topology may be far away in the real network, and two nodes nearby geographically may be far away in the virtual network topology. In this thesis, we study a variation of Chord network architecture to compromise the inconsistent mapping between physical and virtual networks by clustering technology. A computer simulation was made to evaluate the network architecture.

第一章 序論 1
1.1 前言 1
1.2 研究動機 7
1.3 論文架構 8
第二章 近來相關研究 9
2.1 GUTELLA和FREENET 9
2.2 OCEANSTORE 10
2.3 PAST 11
2.4 CHORD 12
2.5 綜合比較 12
2.6 CHORD架構說明 17
2.7 CHORD 協定(PROTOCOL) 19
2.7.1 協定導覽 19
2.7.2 Consistent Hashing 19
2.7.3 Simple Key Location 21
2.7.4 Scalable Key Location 22
2.7.5 節點加入(join)與穩定(stabilize) 26
2.7.6 節點加入時查詢所受到的影響 31
2.7.7 節點失敗的處置與對策 32
第三章 系統架構與模擬 34
3.1 系統架構 34
3.1.1 Member加入(Join)和穩定(Stabilize) 35
3.1.2 Member離開(leave) 38
3.1.3 查詢(Find)和插入(Insert)文件(Documents) 38
3.2 系統模擬與資料結構 39
3.2.1 traffic_gen程式 39
3.2.2 sim程式 41
3.3 模擬數據與分析 46
第四章.結論與未來展望 48
4.1 結論 48
4.2 未來展望 49
參考文獻 50
附錄A 53

[1] http://www.twnic.net.tw/dn/dn_g_01.htm#4
[2] http://www.sun.com/executives/sunjournal/v4n3/feature3.html
[3] Napster website http://www.napster.com.
[4] Morpheus website http://www.musiccity.com.
[5] KaZaA website. http://www.kazaa.com.
[6] Limewire website. http://www.limewire.com.
[7] Seti@Home website http://setiathome.ssl.berkely.edu.
[8] Folding@home. http://www.stanford.edu/group/pandegroup/Cosm.
[9] PopularPower website. http://www.popularpower.com
[10] Intel. Peer to Peer Computing: NetBatch Case Study. available in http://www.intel.com/eBusiness/pdf/it/wp014703.pdf ( August 2000).
[11] AOL Instant Messenger. http://www.aim.com.
[12] ICQ website http://www.icq.com/.
[13] MSN Messenger website: http://www.msn.com/.
[14] Jabber website. http://www.jabber.com.
[15] Freehaven website. http://freehaven.net.
[16] Publius website http://www.publius.com.
[17] MojoNation website. http://www.mojonation.net.
[18] Edonkey website. http://ed2k.ok.to.
[19] Ezpeer website. http://www.ezpeer.com.tw.
[20] Music.com.tw,. http://www.kuro.com.tw.
[21] Gnutella website http://www.gnutella.com.
[22] Freenet website http://freenet.sourceforge.com/.
[23] WinMX website http://www.winmx.com/.
[24] BearShare website http://www.bearshare.com/
[25] eMule website http://www.emule-project.net.
[26] Stoica I., Morris R., Karger D., Kaashoek F. and Balakrishnan H. (2001) Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. ACM SIGCOMM 2001, pp. 160-177., San Diego.
[27] Zhao B. Y., Kubiatowicz J. D. and Joseph A. D. (2001) Tapestry: An infrastructure for fault-resilient wide-area location and routing, Tech. Rep. UCB//CSD-01-1141, U. C. Berkeley, April 2001.
[28] Rowstron A. and Druschel P. (2001) Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. 18th IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), Heidelberg, Germany.
[29] Ratnasamy S., Francis P., Handley M., Karp R. and Shenker S. (2001) A scalable content addressable network. ACM SIGCOMM 2001, pp. 149-160, San Diego, CA.
[30] Plaxton C., Rajaraman R. and Richa A. (1997) Accessing nearby copies of replicated objects in a distributed environment. Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA97), pp. 311-320, Newport, Rhode Island.
[31] Druschel P. and Rowstron A. (2001) PAST: A large-scale, persistent peer-to-peer storage utility. Eighth Workshop on Hot Topics in Operating Systems (HotOS-VIII, 2001), Schloss Elmau, Germany.
[32] Daswani N., Garcia-Molina H. and Yang B. (2003) Open Problems in Data-Sharing Peer-to-Peer Systems. 9th International Conference on Database Theory (ICDT03), Siena, Italy.
[33] Ratnasamy S., Shenker S. and Stoica I. (2002) Routing Algorithms for DHT: Some Open Questions. IPTPS 2002.
[34] Malkhi D., Naor M. and Ratajczak D. (2002) Viceroy: A Scalable and Dynamic Lookup Network. 21st ACM Symposium on Principles of Distributed Computing (PODC02), Monterey, CA, USA.
[35] H.J. Siegel. (1979) Interconnection networks for SIMD machines. IEEE Computer 12(6):57-65, 1979.
[36] J. Kleinberg. (200) The small world phenomenon: An algorithmic perspective. 32nd ACM Symposium on Theory of Computing , May 2000, pp. 163-170.
[37] Manku G. S., Bawa M. and Raghavan P. (2003) Symphony: Distributed Hashing In a Small World. 4th USENIX Symposium on Internet Technologies and Systems (USITS03), Seattle, WA.
[38] Considine J. and FLorio T. A. (2002) Scalable Peer-to-Peer Indexing with Constant State, Technical Report, 2002.
[39] Pandurangan G., Raghavan P. and Upfal E. (2001) Building lowdiameter peer-to-peer networks. 42nd Annual IEEE Symposium on the Foundations of Computer Science (FOCS01).
[40] Ripeanu M., Foster I. and Iamnitchi A. (2002) Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design. IEEE Internet Computing 6(1).
[41] Saroiu S., Gummadi P. and Gribble S. (2002) A Measurement Study of Peer-to-Peer File Sharing Systems. Multimedia Computing and Networking (MMCN02), San Jose, CA.
[42] Sen S. and Wang J. (2002) Analyzing peer-to-peer traffic across large networks. ACM SIGCOMM Internet Measurement Workshop(IMW02).
[43] Ratnasamy S., Handley M., Karp R. and Shenker S. (2002) Topologically-Aware Overlay Construction and Server Selection. INFOCOM 2002.
[44] Yang B. and Garcia-Molina H. (2003) Designing a super-peer network. ICDE 2003.
[45] Yang B. and Garcia-Molina H. (2001) Comparing hybrid peer-to-peer systems. Tweenty-first International Conference on Very Large Databases (VLDB01).
[46] Krishnamurthy B., Wang J. and Xie Y. (2001) Early Measurements of a CLuster-based Architecture for P2P Systems. ACM SIGCOMM Internet Measurement Workshop(IMW01).
[47] Ganesan P., Sun Q. and Garcia-Molina H. (2003) YAPPERS: A Peer-to-Peer Lookup Service over Arbitrary Topology. INFOCOM 2003.
[48] Fiat A. and Saia J. (2002) Censorship Resistant Peer-to-Peer Content Addressable Networks. Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA02).
[49] Datar M. (2002) Butterfliers and Peer-to-Peer Networks. 10th European Symposium on Algorithms (ESA02).
[50] http://home.pchome.com.tw/cute/xian2/S-picture/eDonkey2000/P2P.htm