Building small-world peer-to-peer networks based on hierarchical structures

Hung-Chang Hsiao, Yung Chih Lin, Hao Liao

Research output: Contribution to journalArticle

9 Citations (Scopus)

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 χ) hops, where χ 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.

Original languageEnglish
Pages (from-to)1023-1037
Number of pages15
JournalIEEE Transactions on Parallel and Distributed Systems
Volume20
Issue number7
DOIs
Publication statusPublished - 2009 Jul 1

Fingerprint

Small-world networks
Peer to peer networks
Routing algorithms

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

@article{966df7c613f34ca6866ef0c4e6521905,
title = "Building small-world peer-to-peer networks based on hierarchical structures",
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 χ) hops, where χ 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.",
author = "Hung-Chang Hsiao and Lin, {Yung Chih} and Hao Liao",
year = "2009",
month = "7",
day = "1",
doi = "10.1109/TPDS.2008.173",
language = "English",
volume = "20",
pages = "1023--1037",
journal = "IEEE Transactions on Parallel and Distributed Systems",
issn = "1045-9219",
publisher = "IEEE Computer Society",
number = "7",

}

Building small-world peer-to-peer networks based on hierarchical structures. / Hsiao, Hung-Chang; Lin, Yung Chih; Liao, Hao.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 20, No. 7, 01.07.2009, p. 1023-1037.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Building small-world peer-to-peer networks based on hierarchical structures

AU - Hsiao, Hung-Chang

AU - Lin, Yung Chih

AU - Liao, Hao

PY - 2009/7/1

Y1 - 2009/7/1

N2 - 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 χ) hops, where χ 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.

AB - 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 χ) hops, where χ 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.

UR - http://www.scopus.com/inward/record.url?scp=67649371397&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67649371397&partnerID=8YFLogxK

U2 - 10.1109/TPDS.2008.173

DO - 10.1109/TPDS.2008.173

M3 - Article

VL - 20

SP - 1023

EP - 1037

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 7

ER -