改良式內容可定址網路之設計與實作

Abstract

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.