Towards a two-tier Internet coordinate system to mitigate the impact of triangle inequality violations

Mohamed Ali Kaafar, Bamba Gueye, Francois Cantin, Guy Leduc, Laurent Mathy

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

14 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationNETWORKING 2008
Subtitle of host publicationAdHoc and Sensor Networks, Wireless Networks, Next Generation Internet : 7th International IFIP-TC6 Networking Conference, proceedings
EditorsAmitabha Das, Hung Keng Pung, Francis Bu Sung Lee, Lawrence Wai Choong Wong
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages397-408
Number of pages12
ISBN (Print)3540795480, 9783540795483
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event7th International IFIP-TC6 Networking Conference - NETWORKING 2008: AdHoc and Sensor Networks, Wireless Networks, Next Generation Internet - , Singapore
Duration: 5 May 20085 Sep 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4982
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th International IFIP-TC6 Networking Conference - NETWORKING 2008: AdHoc and Sensor Networks, Wireless Networks, Next Generation Internet
CountrySingapore
Period5/05/085/09/08

Keywords

  • experimentation
  • Internet coordinate systems
  • performance
  • triangle inequality violations

Fingerprint Dive into the research topics of 'Towards a two-tier Internet coordinate system to mitigate the impact of triangle inequality violations'. Together they form a unique fingerprint.

Cite this