Transformation non linéaire des distances Une solution au problème des violations d'inégalités triangulaires dans les systèmes de coordonnées ?

Résumé : Les systèmes de coordonnées sont des systèmes distribués ayant pour but d'associer des coordonnées à chaque nœud dans un espace métrique à partir de mesures de distance (par exemple RTT) entre certaines paires de nœuds. Il est bien connu que de tels systèmes ne fonctionnent pas correctement lorsque les distances mesurées ne respectent pas les inégalités triangulaires. Pour contourner ce problème, il a été proposé [WAN 08] d'appliquer une transformation non linéaire aux distances mesurées de façon à éliminer les violations de l'inégalité triangulaire. Une telle approche permet potentiellement d'obtenir une matrice de distances estimées restituant les inégalités triangulaires par transformée inverse. Les perspectives sont intéressantes, mais cet ar- ticle montre que les résultats obtenusLes systèmes de coordonnées sont des systèmes distribués ayant pour but d'associer des coordonnées à chaque nœud dans un espace métrique à partir de mesures de distance (par exemple RTT) entre certaines paires de nœuds. Il est bien connu que de tels systèmes ne fonctionnent pas correctement lorsque les distances mesurées ne respectent pas les inégalités triangulaires. Pour contourner ce problème, il a été proposé [WAN 08] d'appliquer une transformation non linéaire aux distances mesurées de façon à éliminer les violations de l'inégalité triangulaire. Une telle approche permet potentiellement d'obtenir une matrice de distances estimées restituant les inégalités triangulaires par transformée inverse. Les perspectives sont intéressantes, mais cet article montre que les résultats obtenus ne sont pas aussi bons qu'espérés. A l'aide de simulations, nous avons observé que l'utilisation de transformations non linéaires simples permettait d'améliorer de façon significative la précision des estimations obtenues à l'aide d'un système de coordonnées comme Vivaldi. Toutefois, contrai- rement à ce que [WAN 08] laisse supposer, une telle approche permettra difficilement d'obtenir une matrice de distances estimées restituant exactement les violations de l'inégalité triangulaire présentes dans la matrice de distances mesurées entre les noeuds.
Type de document :
Communication dans un congrès
CFIP'2009, Oct 2009, Strasbourg, France. 12p., 2009
Liste complète des métadonnées


https://hal.inria.fr/inria-00417795
Contributeur : Olivier Festor <>
Soumis le : mercredi 16 septembre 2009 - 22:09:03
Dernière modification le : jeudi 17 septembre 2009 - 08:36:37
Document(s) archivé(s) le : mardi 16 octobre 2012 - 11:00:51

Fichier

19.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00417795, version 1

Collections

Citation

François Cantin, Guy Leduc, Bamba Gueye. Transformation non linéaire des distances Une solution au problème des violations d'inégalités triangulaires dans les systèmes de coordonnées ?. CFIP'2009, Oct 2009, Strasbourg, France. 12p., 2009. <inria-00417795>

Partager

Métriques

Consultations de
la notice

125

Téléchargements du document

306