Load balance with imperfect information in structured peer-to-peer systems

Hung Chang Hsiao, Hao Liao, Ssu Ta Chen, Kuo Chan Huang

Research output: Contribution to journalArticle

36 Citations (Scopus)

Abstract

With the notion of virtual servers, peers participating in a heterogeneous, structured peer-to-peer (P2P) network may host different numbers of virtual servers, and by migrating virtual servers, peers can balance their loads proportional to their capacities. The existing and decentralized load balance algorithms designed for the heterogeneous, structured P2P networks either explicitly construct auxiliary networks to manipulate global information or implicitly demand the P2P substrates organized in a hierarchical fashion. Without relying on any auxiliary networks and independent of the geometry of the P2P substrates, we present, in this paper, a novel load balancing algorithm that is unique in that each participating peer is based on the partial knowledge of the system to estimate the probability distributions of the capacities of peers and the loads of virtual servers, resulting in imperfect knowledge of the system state. With the imperfect system state, peers can compute their expected loads and reallocate their loads in parallel. Through extensive simulations, we compare our proposal to prior load balancing algorithms.

Original languageEnglish
Article number5473220
Pages (from-to)634-649
Number of pages16
JournalIEEE Transactions on Parallel and Distributed Systems
Volume22
Issue number4
DOIs
Publication statusPublished - 2011 Jan 31

Fingerprint

Servers
Resource allocation
Peer to peer networks
Substrates
Probability distributions
Geometry

All Science Journal Classification (ASJC) codes

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

Cite this

@article{5ac514fc26db43f383460d05c7e0d247,
title = "Load balance with imperfect information in structured peer-to-peer systems",
abstract = "With the notion of virtual servers, peers participating in a heterogeneous, structured peer-to-peer (P2P) network may host different numbers of virtual servers, and by migrating virtual servers, peers can balance their loads proportional to their capacities. The existing and decentralized load balance algorithms designed for the heterogeneous, structured P2P networks either explicitly construct auxiliary networks to manipulate global information or implicitly demand the P2P substrates organized in a hierarchical fashion. Without relying on any auxiliary networks and independent of the geometry of the P2P substrates, we present, in this paper, a novel load balancing algorithm that is unique in that each participating peer is based on the partial knowledge of the system to estimate the probability distributions of the capacities of peers and the loads of virtual servers, resulting in imperfect knowledge of the system state. With the imperfect system state, peers can compute their expected loads and reallocate their loads in parallel. Through extensive simulations, we compare our proposal to prior load balancing algorithms.",
author = "Hsiao, {Hung Chang} and Hao Liao and Chen, {Ssu Ta} and Huang, {Kuo Chan}",
year = "2011",
month = "1",
day = "31",
doi = "10.1109/TPDS.2010.105",
language = "English",
volume = "22",
pages = "634--649",
journal = "IEEE Transactions on Parallel and Distributed Systems",
issn = "1045-9219",
publisher = "IEEE Computer Society",
number = "4",

}

Load balance with imperfect information in structured peer-to-peer systems. / Hsiao, Hung Chang; Liao, Hao; Chen, Ssu Ta; Huang, Kuo Chan.

In: IEEE Transactions on Parallel and Distributed Systems, Vol. 22, No. 4, 5473220, 31.01.2011, p. 634-649.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Load balance with imperfect information in structured peer-to-peer systems

AU - Hsiao, Hung Chang

AU - Liao, Hao

AU - Chen, Ssu Ta

AU - Huang, Kuo Chan

PY - 2011/1/31

Y1 - 2011/1/31

N2 - With the notion of virtual servers, peers participating in a heterogeneous, structured peer-to-peer (P2P) network may host different numbers of virtual servers, and by migrating virtual servers, peers can balance their loads proportional to their capacities. The existing and decentralized load balance algorithms designed for the heterogeneous, structured P2P networks either explicitly construct auxiliary networks to manipulate global information or implicitly demand the P2P substrates organized in a hierarchical fashion. Without relying on any auxiliary networks and independent of the geometry of the P2P substrates, we present, in this paper, a novel load balancing algorithm that is unique in that each participating peer is based on the partial knowledge of the system to estimate the probability distributions of the capacities of peers and the loads of virtual servers, resulting in imperfect knowledge of the system state. With the imperfect system state, peers can compute their expected loads and reallocate their loads in parallel. Through extensive simulations, we compare our proposal to prior load balancing algorithms.

AB - With the notion of virtual servers, peers participating in a heterogeneous, structured peer-to-peer (P2P) network may host different numbers of virtual servers, and by migrating virtual servers, peers can balance their loads proportional to their capacities. The existing and decentralized load balance algorithms designed for the heterogeneous, structured P2P networks either explicitly construct auxiliary networks to manipulate global information or implicitly demand the P2P substrates organized in a hierarchical fashion. Without relying on any auxiliary networks and independent of the geometry of the P2P substrates, we present, in this paper, a novel load balancing algorithm that is unique in that each participating peer is based on the partial knowledge of the system to estimate the probability distributions of the capacities of peers and the loads of virtual servers, resulting in imperfect knowledge of the system state. With the imperfect system state, peers can compute their expected loads and reallocate their loads in parallel. Through extensive simulations, we compare our proposal to prior load balancing algorithms.

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

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

U2 - 10.1109/TPDS.2010.105

DO - 10.1109/TPDS.2010.105

M3 - Article

AN - SCOPUS:79952071474

VL - 22

SP - 634

EP - 649

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

SN - 1045-9219

IS - 4

M1 - 5473220

ER -