Improving the Efficiency of Content-Addressable Networks Using Small-World Models
Date Issued
2005
Date
2005
Author(s)
Chiang, Meng-Jue
DOI
en-US
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.
Subjects
同儕式網路
小世界現象
內容可定址網路
分散式系統
分散式雜湊表
疊加層網路
Small-World
Peer-to-Peer Networks
Content-Addressable Networks
Distributed Hash Table
Overlay Routing
Type
other
File(s)![Thumbnail Image]()
Loading...
Name
ntu-94-R92725032-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):5212e9548f8a439c8945c244b9e1b91e