TY - GEN

T1 - A self-organized clustering scheme for overlay networks

AU - Cantin, Francois

AU - Gueye, Bamba

AU - Kaafar, Mohamed Ali

AU - Leduc, Guy

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - clustering

KW - ICS

KW - performance

KW - triangle inequality violations

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

U2 - 10.1007/978-3-540-92157-8_6

DO - 10.1007/978-3-540-92157-8_6

M3 - Conference proceeding contribution

SN - 9783540921561

T3 - Lecture Notes in Computer Science

SP - 59

EP - 70

BT - Self-Organizing Systems

A2 - Hummel, Karin Anna

A2 - Sterbenz, James P. G.

PB - Springer, Springer Nature

CY - Berlin

ER -