請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38466完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 蔡益坤(Yih-Kuen Tsay) | |
| dc.contributor.author | Meng-Jue Chiang | en |
| dc.contributor.author | 蔣孟儒 | zh_TW |
| dc.date.accessioned | 2021-06-13T16:34:24Z | - |
| dc.date.available | 2005-07-11 | |
| dc.date.copyright | 2005-07-11 | |
| dc.date.issued | 2005 | |
| dc.date.submitted | 2005-07-08 | |
| dc.identifier.citation | [1] Napster. http://www.napster.com.
[2] Gnutella. http://gnutella.wego.com. [3] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, and Scott Schenker. A scalable content-addressable network. In Proceedings of the 2001 conference on applications, technologies, architectures, and protocols for computer communications, pages 161–172. ACM Press, 2001. [4] Ion Stoica, Robert Morris, David Karger, and M. Francs Kaashoekand Hari Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. In Proceedings of the Conference on Applications, Technologies, Architectures, and Pro- tocols for Computer Communications, pages 149–160, San Diego, California, United States, 2001. ACM Press. [5] Antony Rowstron and Peter Druschel. Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. Lecture Notes in Computer Science, 2218, 2001. [6] Ben Y. Zhao, John Kubiatowicz, and Anthony D. Joseph. Tapestry: a fault-tolerant wide-area application infrastructure. Computer Communication Review, 32(1):81, 2002. [7] D. Malkhi, M. Naor, and D. Ratajczak. Viceroy: A scalable and dynamic emulation of the butterfly. In Proceedings of the 21st annual ACM symposium on Principles of distributed computing. ACM Press, 2002. [8] M. Kochen. Ed. The Small World. Ablex, Norwood, 1989. [9] J. Guare. Six Degrees of Separation: A Play. Vintage Books, New York, 1990. [10] G. Manku, M. Bawa, and P. Raghavan. Symphony: Distributed hashing in a small world. In Proc. 4th USENIX Symposium on Internet Technologies and Systems (USITS) 2003, 2003. [11] Hui Zhang, Ashish Goel, and Ramesh Govindan. Using the small-world model to improve freenet performance. SIGCOMM Comput. Commun. Rev., 32(1):79–79, 2002. [12] Jon Kleinberg. The small-world phenomenon: an algorithm perspective. In STOC ’00: Proceedings of the thirty-second annual ACM symposium on Theory of comput- ing, pages 163–170, New York, NY, USA, 2000. ACM Press. [13] Po-An Chen and Yih-Kuen Tsay. Emulating Small-World Networks on Content- Addressable Networks. 2004. [14] D. Watts and S. Milgram. Collective dynamics of small-world networks. Nature, 393, 1998. [15] Moni Naor and Udi Wieder. Know thy neighbor’s neighbor: Better routing for skipgraphs and small worlds. In The Third International Workshop on Peer-to-Peer Systems (IPTPS), pages 269–277, 2004. [16] Gurmeet Singh Manku, Moni Naor, and Udi Wieder. Know thy neighbor’s neighbor: the power of lookahead in randomized p2p networks. In STOC ’04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 54–63, New York, NY, USA, 2004. ACM Press. [17] M. Kaashoek and D. Karger. Koorde: A simple degree-optimal distributed hash table. In Proc. 2nd IPTPS, Berkeley, CA, Feb 2003. [18] Gurmeet Singh Manku. Routing networks for distributed hash tables. In PODC ’03: Proceedings of the twenty-second annual symposium on Principles of distributed computing, pages 133–142, New York, NY, USA, 2003. ACM Press. [19] Po-An Chen. Fast and Scalable Object Location Based on the CAN Model. Master’s thesis, National Taiwan University, 2003. [20] C. Jin, Q. Chen, and S. Jamin. Inet: Internet Topology Generator. Technical Report CSE-TR443-00, Department of EECS, University of Michigan, 2000. [21] K. Gummadi, R. Gummadi, S. Gribble, S. Ratnasamy, S. Shenker, and I. Stoica. The impact of dht routing geometry on resilience and proximity. In SIGCOMM ’03: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pages 381–394, New York, NY, USA, 2003. ACM Press. [22] Po-Hung Chen. Efficient peer-to-peer keyword search using adaptive space partition. Master’s thesis, National Taiwan University, 2004 | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38466 | - |
| dc.description.abstract | Distributed Hash Tables (DHTs) are often used to address the routing problem in peer-to-peer overlay networks. A myriad of DHT routing protocols have been proposed, most of which achieve short routing latency with small state per node; however, they operate in a complicated way and are difficult to maintain in a highly dynamic environment where nodes arrive and depart frequently. Among the numerous schemes, Content-Addressable Networks (CANs), built on a d-torus, is simple, scalable and stable with small state per node. Unfortunately, it is inefficient when d is a small constant. Inspired by Kleinberg's small-world construction, we propose an advanced CAN called 'small-world CAN', which achieves a substantial improvement in routing efficiency. The key idea is to emulate a small-world model in a 2-dimensional CAN. Each CAN node is equipped with a constant number of links, connecting to a long-distance contact chosen randomly according to a probability distribution function. Greedy routing is first used to show our scheme's competitive performance compared with many other schemes. We
then introduce Manku's NoN-GREEDY routing algorithm and show that it offers more advantages to our system. Since the construction of a small-world CAN requires information about the current network's size, we present two approaches to estimate the network size. Both approaches guarantee that each node obtain an estimating network size lying in an acceptable range with a high probability. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T16:34:24Z (GMT). No. of bitstreams: 1 ntu-94-R92725032-1.pdf: 555202 bytes, checksum: a683a80b622f91d013318d51e06d667c (MD5) Previous issue date: 2005 | en |
| dc.description.tableofcontents | 1 Introduction 1
1.1 Background and Motivation . . . . . . . . . . . . . 1 1.2 Objectives . . . . . . . . . . . . . . . . . . . . . 3 1.3 Thesis Outline . . . . . . . . . . . . . . . . . . . 3 2 Related Work 5 2.1 The Content-Addressable Networks . . . . . . . . . . 5 2.1.1 Routing in CAN . . . . . . . . . . . . . . . . . . 5 2.1.2 Construction of the CAN Overlay Network . . . . . 6 2.1.3 How to Determine which Zone to be Split . . . . . 6 2.2 The Small-World Model . . . . . . . . . . . . . . . 8 2.3 Symphony . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Lookahead—NoN-GREEDY Algorithm . . . . . . . . . . 13 3 Our Small-World CAN 16 3.1 Protocol . . . . . . . . . . . . . . . . . . . . . . 16 3.2 Construction of Long Distance Links . . . . . . . . 17 3.3 Routing Algorithm . . . . . . . . . . . . . . . . . 19 3.3.1 Greedy Algorithm . . . . . . . . . . . . . . . . . 19 3.3.2 Design Improvements: NoN-GREEDY Algorithm . . . . 20 3.4 Estimation Mechanism . . . . . . . . . . . . . . . . 21 3.4.1 Partition Tree Approach . . . . . . . . . . . . . 22 3.4.2 Flooding Approach . . . . . . . . . . . . . . . . 27 3.5 Dynamic Operations, Maintenance and Recovery . . . . 33 3.5.1 Node Joins . . . . . . . . . . . . . . . . . . . . 33 3.5.2 Node Failure and Departure . . . . . . . . . . . . 33 3.5.3 Maintenance of Long-distance links . . . . . . . . 35 4 Experimental Results 36 4.1 Experimental Method . . . . . . . . . . . . . . . . 36 4.2 Routing Efficiency . . . . . . . . . . . . . . . . . 37 4.3 Lookup stretch . . . . . . . . . . . . . . . . . . . 38 4.4 Load Balancing . . . . . . . . . . . . . . . . . . . 39 4.5 Resilience to Failure . . . . . . . . . . . . . . . 40 4.6 Comparison between Different Estimation Mechanisms . 41 5 Comparison with other Protocols 47 5.1 Comparison with Random Long-Distance Links . . . . . 47 5.2 Comparison with Symphony . . . . . . . . . . . . . . 47 6 Conclusion 53 6.1 Contributions . . . . . . . . . . . . . . . . . . . 53 6.2 Future Work . . . . . . . . . . . . . . . . . . . . 54 bibliography. . . . . . . . . . . . . . . . . . . . . . .56 | |
| dc.language.iso | en | |
| dc.title | 以小世界模型增加效能之內容可定址網路 | zh_TW |
| dc.title | Improving the Efficiency of Content-Addressable Networks Using Small-World Models | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 93-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 莊裕澤(Yuh-Jzer Joung),林宗男(Tsung-Nan Lin) | |
| dc.subject.keyword | 同儕式網路,小世界現象,內容可定址網路,分散式系統,分散式雜湊表,疊加層網路, | zh_TW |
| dc.subject.keyword | Small-World,Peer-to-Peer Networks,Content-Addressable Networks,Distributed Hash Table,Overlay Routing, | en |
| dc.relation.page | 58 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2005-07-08 | |
| dc.contributor.author-college | 管理學院 | zh_TW |
| dc.contributor.author-dept | 資訊管理學研究所 | zh_TW |
| 顯示於系所單位： | 資訊管理學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-94-1.pdf 目前未授權公開取用 | 542.19 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。