Name
Abstract | ||
|---|---|---|
Small-world (SW) networks possess two properties, namely low diameter and high clustering coefficient, which are often desired by large-scale peer-to-peer networks. Prior studies have shown that the construction of an SW network can be based on a d-regular graph, and each node in the graph maintains d local neighbors and a small constant number of long-distance contacts. However, it is commonly understood that it is difficult to construct a short route in an SW network, given source (s) and target (t) nodes, though an SW network guarantees that a short route from s to t exists. Prior work in [1] proposed a navigable SW network for a d-dimensional lattice such that a simple localized routing algorithm can be devised to route a message from s to t using O(log2,X) hops, where X is the number of nodes in the network. In this paper, we present a novel navigable SW network based on a hierarchical model. Compared to previous efforts, the novelty of our study presents 1) that our network construction based on a hierarchical model is decentralized, 2) that routing a message between any two nodes in our SW network takes logarithmic hopcount in expectation, 3) that our SW network has high cluster coefficient, and 4) that the performance of our proposal is mathematically provable. We support the performance of our proposal in this study through rigorous, thorough performance analysis and extensive simulations. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/TPDS.2008.173 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
peer-to-peer systems,hierarchical structures,overlay networks,small-world peer-to-peer network,tree hierarchy,routing algorithm,c.2.1.d distributed networks,building small-world peer-to-peer networks,novel navigable sw network,hierarchical structure,thorough performance analysis,large-scale peer-to-peer network,small world,cal x,network construction,peer-to-peer computing,telecommunication network routing,c.2.4 distributed systems,sw network,navigable sw network,short route,hierarchical model,performance analysis.,sw network guarantee,clustering coefficient,lattices,routing,overlay network,regular graph,distributed system,mathematical model | Lattice (order),Peer-to-peer,Computer science,Computer network,Theoretical computer science,Network construction,Logarithm,Clustering coefficient,Hierarchical database model,Overlay network,Distributed computing,Routing algorithm | Journal |
Volume | Issue | ISSN |
20 | 7 | 1045-9219 |
Citations | PageRank | References |
6 | 0.61 | 34 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hung-Chang Hsiao | 1 | 256 | 32.34 |
| Yung-chih Lin | 2 | 6 | 0.95 |
| Hao Liao | 3 | 51 | 5.37 |