以小世界模型增加效能之內容可定址網路

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.