請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/32013
標題: | 改良式內容可定址網路之設計與實作 The Design and Implementation of an Improved Content-Addressable Network |
作者: | Zi-Hau Yang 楊智皓 |
指導教授: | 蔡益坤(Yih-Kuen Tsay) |
關鍵字: | 內容可定址網路,小世界模型, CAN,small-world,routing stretch, |
出版年 : | 2006 |
學位: | 碩士 |
摘要: | Distributed Hash Tables (DHTs) are a popular model for the object location problem in peer-to-peer overlay networks. Many DHT schemes have been proposed that achieve a short routing latency with a small per-node state space. However, most of these schemes are complicated and are difficult to maintain in dynamic environments where nodes join and leave frequently. Content-Addressable Networks (CANs), proposed by Ratnasamy et al., employs a virtual address space constructed as a d-dimension torus and are relatively easy to maintain.However, the CAN scheme is not very efficient when d is small. Meanwhile, small-world networks, proposed by Kleinberg, are a family of random graphs allowing an average path length of O(log^2n) with only O(1) links per node using greedy routing.
The idea of embedding a small-world graph into a CAN-like network has been proposed. We consider and embed the small-world model into a 2-dimension network, referred to as the ``small-world CAN'. The small-world CAN constructs the network as a 2-dimension torus and enjoys the advantages of both CAN and the small-world model. However, the small-world CAN's underlying network topology does not match that of the physical Internet. We propose a new scheme by modifying the small-world CAN. We change the model's virtual network space into a 2-dimensional cylindrical space to improve the routing stretch. Although we have changed the virtual network topology, it still keeps the advantages of the two schemes. Each node in the overlay network is equipped with a constant number of links, connecting to the immediate neighbors and to a long-distant node chosen randomly according to a probability distribution function randomly. Based on the modified small-world CAN scheme, we have implemented a prototype system that also supports keyword search. Typical DHT schemes only support a simple map from keys to values, but not keyword search. In order to support keyword search on a network scheme, some distributed inverted index is needed. We choose a keyword search scheme that has been designed to work on top of CAN. The scheme has a good load balancing and incur little network traffic overhead. The implementation could be seen as a beginning of combining the DHT scheme with upper layer applications. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/32013 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊管理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 604.35 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。