A self-organized clustering scheme for overlay networks

Francois Cantin*, Bamba Gueye, Mohamed Ali Kaafar, Guy Leduc

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

6 Citations (Scopus)


Hierarchical approaches, where nodes are clustered based on their network distances, have been shown to allow for robust and scalable topology-aware overlays. Moreover, recent research works have shown that cluster-based deployments of Internet Coordinates Systems (ICS), where nodes estimate both intra-cluster and inter-cluster distances, do mitigate the impact of Triangle Inequality Violations (TIVs) on the distance predictions, and hence offer more accurate internet latency estimations. To allow the construction of such useful clusters we propose a self-organized distributed clustering scheme. For better scalability and efficiency, our algorithm uses the coordinates of a subset of nodes, known by running an ICS system, as first approximations of node positions. We designed and evaluated two variants of this algorithm. The first one, based on some cooperation among nodes, aims at reducing the expected time to construct clusters. The second variant, where nodes are selfish, aims at reducing the induced communication overhead.

Original languageEnglish
Title of host publicationSelf-Organizing Systems
Subtitle of host publicationThird International Workshop, IWSOS 2008 : proceedings
EditorsKarin Anna Hummel, James P. G. Sterbenz
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Number of pages12
ISBN (Electronic)9783540921578
ISBN (Print)9783540921561
Publication statusPublished - 2008
Externally publishedYes
Event3rd International Workshop on Self-Organizing Systems, IWSOS 2008 - Vienna, Austria
Duration: 10 Dec 200812 Dec 2008

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference3rd International Workshop on Self-Organizing Systems, IWSOS 2008


  • clustering
  • ICS
  • performance
  • triangle inequality violations

Fingerprint Dive into the research topics of 'A self-organized clustering scheme for overlay networks'. Together they form a unique fingerprint.

Cite this