  Overlay Routing using Coordinate SystemsCantin, François  ; Gueye, Cheikh Ahmadou Bamba ; Kaafar, Mohamed Ali et alPoster (2008, December) We address the problem of finding indirect overlay paths that reduce the latency between pairs of nodes in an overlay. To this end we propose to rely on an Internet Coordinate System (ICS), namely Vivaldi ... [more ▼] We address the problem of finding indirect overlay paths that reduce the latency between pairs of nodes in an overlay. To this end we propose to rely on an Internet Coordinate System (ICS), namely Vivaldi, to estimate RTTs and help find these interesting detours. We define two initial criteria to illustrate our approach and assess their true/false positive rates. [less ▲] Detailed reference viewed: 96 (48 ULg)A Self-Organized clustering scheme for overlay networksCantin, François ; Gueye, Cheikh Ahmadou Bamba ; Kaafar, Mohamed Ali et alin Lecture Notes in Computer Science (2008, December), 5343 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 46 (19 ULg)Towards a Two-Tier Internet coordinate system to mitigate the impact of Triangle Inequality ViolationsKaafar, Mohamed Ali ; Gueye, Cheikh Ahmadou Bamba ; Cantin, François et alin Lecture Notes in Computer Science (2008, May), 4982 Routing policies or path inflation can give rise to violations of the Triangle Inequality with respect to delay (RTTs) in the Internet. In network coordinate systems, such Triangle Inequality Violations ... [more ▼] Routing policies or path inflation can give rise to violations of the Triangle Inequality with respect to delay (RTTs) in the Internet. In network coordinate systems, such Triangle Inequality Violations (TIVs) will introduce inaccuracy, as nodes in this particular case could not be embedded into any metric space. In this paper, we consider these TIVs as an inherent and natural property of the Internet; rather than trying to remove them, we consider characterizing them and mitigating their impact on distributed coordinate systems. In a first step, we study TIVs existing in the Internet, using different metrics in order to quantify various levels of TIVs’ severity. Our results show that path lengths do have an effect on the impact of these TIVs. In particular, the shorter the link between any two nodes is, the less severe TIVs involved in are. In a second step, we do leverage our study to reduce the impact of TIVs on coordinate systems. We focus on the particular case of the Vivaldi coordinate system and we explore how TIVs may impact its accuracy and stability. In particular, we observed correlation between the (in)stability and high effective error of nodes’ coordinates with respect to their involvement in TIVs situations. We finally propose a Two-Tier architecture opposed to a flat structure of Vivaldi that do mitigate the effect of TIVs on the distances predictions. [less ▲] Detailed reference viewed: 68 (19 ULg)Explication et réduction de l’impact des violations d’inégalités triangulaires dans VivaldiCantin, François ; Gueye, Cheikh Ahmadou Bamba ; Kaafar, Mohamed Ali et alin CFIP'2008 (2008, March) Les systèmes de coordonnées sont des systèmes distribués ayant pour but, à partir de mesures de distance (par exemple RTT) entre certaines paires de noeuds, d’associer des coordonnées à chaque noeud dans ... [more ▼] Les systèmes de coordonnées sont des systèmes distribués ayant pour but, à partir de mesures de distance (par exemple RTT) entre certaines paires de noeuds, d’associer des coordonnées à chaque noeud dans un espace métrique. Toutefois, de tels systèmes ne fonctionnent pas correctement lorsque les distances mesurées ne respectent pas les inégalités triangulaires. Or, les violations de ces inégalités, appelées TIV, sont fréquentes dans l’Internet. Nous proposons une étude approfondie de l’impact des TIV sur le système de coordonnées Vivaldi. Nous quantifions et expliquons les erreurs de prédiction de distance et l’instabilité des coordonnées causées par les TIV selon leur fréquence et leur sévérité. Nous montrons aussi que la distance entre deux noeuds, mesurée par le RTT, est corrélée à la probabilité d’existence d’une TIV. Enfin, nous recommandons un système de coordonnées hiérarchique, et nous montrons, par des simulations sur une matrice de délais réelle, qu’une telle approche réduit l’impact des TIV. [less ▲] Detailed reference viewed: 45 (12 ULg) |
||
