Soutenance mémoire
Conception de systèmes de coordonnées réseau
Les bases théoriques des coordonnées réseau
Dans un système de coordonnées, chaque nœud choisie un nombre constant de voisins. Le but d’un tel système est d’assigner à chaque nœud un e nsemble de coordonnées, de telle sorte que, les distances entre les coordonnées des nœuds pourront prédire les délais mesurés avec précision. Les connections entre tous les voisins (nœuds voisins) forment un graphe de voisin G(V,E), où V est l’ensemble des nœuds du réseau, et E l’ensemble des arêtes de voisin. Le calcul des coordonnées peut être généralement formulé comme un problème d’encastrement du graphe. Le problème est de déterminer la localisation xi de chaque nœud dans un espace à d dimensions, tel que pour chaque pair de voisin (i,j), la distance entre xi et xj peut prédire le délai entre i et j.
Structure du système
Tous les systèmes de coordonnées peuvent être absorbés dans un système de framework général. Comme montré dans la figure 1, un système de coordonnées est composé de quatre composants majeurs : l’architecture, le model, la procédure d’optimisation et les processus assistants.
Architecture : l’architecture est définie comme étant le graphe de voisin utilisé dans un système de coordonnées. Apres la procédure de sélection de voisins, tous les nœuds peuvent former un gr aphe de voisin. Ce graphe de voisin ainsi connu comme l’architecture du système, constitue une base pour la mesure de délai et le calcul de coordonnées. Un système de coordonnées peut utiliser différentes architectures :
• Une architecture centralisée, dans laquelle tous les nœuds peuvent seulement choisir un ensemble fixe de hôtes référence comme ses voisins ;
• Une architecture complètement décentralisé, dans laquelle tous les nœuds peuvent choisir n’importe quels pairs de nœuds comme voisins.
Modèle : c’est le modèle compact que les systèmes de coordonnées utilisent pour se rapprocher de l’espace de délai d’internet, de sorte que la distance entre les coordonnées virtuelles puisses prédire le délai d’internet avec précision. Plusieurs modèles peuvent être utilisés pour assigner des coordonnées virtuelles et estimer les délais d’internet, tels que le modèle des espaces métriques, et le modèle de matrice de factorisation.
Procédures d’optimisation : Les procédures d’optimisation sont des algorithmes utilisés pour calculer les coordonnées virtuelles, ils se basent sur les mesures de délai et sur un modèle particulier, qui peut être le Downhill Simplex Algorithm [11], ou l ’algorithme de simulation Big-Bang proposé dans [12].
Processus auxiliaires (assistants) : en plus de ces composants indispensables, un système de coordonnées peut aussi avoir quelques processus assistant, qui vont lui permettre d’améliorer sa performance sur quelques aspects spécifiques. Par exemple une technique de gravité est proposée dans [13] pour réduire les mouvements des coordonnées, et aussi la technique du filtre Kalman, qui a été proposée dans [14] pour la protection du système des attaques malicieuses.
Les objectifs de performance du système
Notons que dans la littérature, les chercheurs tentent à atteindre plusieurs objectifs de performance sur la conception de système de coordonnées, tels que :
La Précision : une des applications majeures des systèmes de coordonnées est l’estimation de délai d’internet, ce qui fait que la précision reste un objectif important. En effet un bon système de coordonnées doit pouvoir prédire les délais d’internet, avec précision en utilisant les distances entre les coordonnées des nœuds.
Evolutivité : plusieurs applications, telles que la construction de réseau de recouvrement et le routage géométrique, nécessitent que les systèmes de coordonnées puissent être exécutés dans de très larges réseaux. Dans ce scenario, l’évolutivité devient un objectif non négligeable pour les concepteurs de système. Donc les systèmes de coordonnées doivent être très évolutifs, de sorte qu’on n’assiste pas à des dégradations de performance significatives, s’ils sont exécutés sur de très larges réseaux,
La stabilité : la stabilité des coordonnées est caractérisée par l’oscillation rapide des coordonnées du réseau. C’est-à-dire les mouvements rapides des nœuds du réseau. En effet si les coordonnées présentent des oscillations, cela implique qu’elles périment facilement et qu’elles ne sont pas gardables.
Quand un programme d’utilisateur veut utiliser les coordonnées d’un autre nœud dans le réseau, il questionnera ce nœud très fréquemment pour avoir la plus récente cordonnée. D’après les perspectives de conception de système, un bon s ystème de coordonnées doit pouvoir fournir des coordonnées stables. Ainsi ces coordonnées seront gardables et pourront être facilement utilisées par les programmes d’utilisateur.
Fiabilité : la fiabilité d’un système fait référence à l a performance du système dans des scenarios imprévus. La fiabilité d’un système est spécialement importante lors du déploiement du système dans un environnement réel. Quant le système est exécuté dans un environnement réel d’internet, il est possible que quelques nœuds dans le réseau soient malicieux. Les nœuds malicieux peuvent fournir de mauvais délais, ou de mauvaises coordonnées pour tromper les autres nœuds du réseau. Ainsi les concepteurs de système ont pris en considération la fiabilité des coordonnées. Un bon s ystème de coordonnées doit pouvoir tolérer les attaques malicieuses.
les systèmes de positionnement réseau à base de coordonnées
Dans cette section, nous présentons une vue d’ensemble des différentes architectures proposées dans le domaine des systèmes de positionnement Internet à base de coordonnées [15]. Elles peuvent être reparties en deux classes principales: Les systèmes de coordonnées basés sur les balises fixes (landmarks), et les systèmes de coordonnées distribués. Nous parlerons aussi des violations d’inégalité triangulaire et de leurs effets sur les systèmes de coordonnées.
Pourquoi l’utilisation des systèmes de positionnement à base de coordonnées
Pour combler l’écart entre les objectifs contradictoires d’optimisation de performance et d’évolutivité plusieurs approches de prédiction de distances réseau (délai de propagation et de transmission aller/retour « RTT ») à base de coordonnées ont été proposées. l’idée principale de tels systèmes est de modeler l’internet comme un espace géométrique (exemple : un espace euclidien à 3 dimensions), et de définir la position de chaque nœud dans l’internet par une position dans cet espace.
La distance réseau entre deux nœuds est ainsi prédite comme la distance entre leurs coordonnées sans faire de mesures explicites. En d’autres termes, si un nœud x connait la coordonnée d’un nœud y, x n’aura pas besoin de faire une mesure explicite pour déterminer le RTT à y ; à la place, la distance entre x et y dans l’espace de coordonnées est une prédiction précise du RTT. En d’autres mots, tant qu’une position précise et raisonnable pour un nœud peut être obtenue avec de petits efforts, beaucoup de coût de mesures de distance par sondage peuvent être éliminées.
|
Table des matières
INTRODUCTION
CHAPITRE I : INTRODUCTION
CHAPITRE II : LES SYSTEMES DE COORDONNEES DANS L’INTERNET
II.1. Conception de systèmes de coordonnées réseau
II.1.1. Les bases théoriques des coordonnées réseau
II.1.2. Structure du système
II.1.3. Les objectifs de performance du système
II.2. les systèmes de positionnement réseau à base de coordonnées
II.2.1. Pourquoi l’utilisation des systèmes de positionnement à base de coordonnées
II.2.2. Systèmes de coordonnées centralisés
II.2.2.1. La technique Global Network Positioning (GNP)
II.2.2.2. La technique Lighthouses
II.2.2.3. La technique Network Positioning System (NPS)
Vue plus détaillée sur le système NPS
II.2.3. Systèmes de coordonnées distribuées
II.2.3.1. La technique Pratical Internet Coordinates (PIC)
II.2.3.2. La technique Big-Bang Simulation (BBS)
II.2.3.3. Le système Vivaldi
II.3. Discussion
CHAPITRE III : LIMITATIONS DES SYSTEMES DE COORDONNEES RESEAU
III.1. Les nœuds balises (Landmarks)
III.2. Sécurité dans les systèmes de coordonnées
III.2.1. Sécurité de NPS
III.2.2. Sécurité de PIC
III.1. Violation du principe d’inégalité triangulaire
CHAPITRE IV : CARACTERISATION DES TIVS DANS L’INTERNET
IV.1. L’impact de la violation d’inégalité triangulaire sur les systèmes de coordonnées
IV.2. Les paramètres de détection de TIVs
IV.2.1. Proposition de métrique pour la détection de TIV
IV.2.2. Comparaison des paramètres
CONCLUSION
REFERENCES
