Techniques d’exploitation de la proximité

Techniques d’exploitation de la proximité

Les premières DHTs ont été développées indépendamment de la topologie sous-jacente. Toutefois, Pastry [RD01] utilise certaines heuristiques pour explorer la proximité des pairs dans le réseau sous-jacent afin de pouvoir construire ses tables de routage overlay (notamment le neighborhood set). Cependant les impacts sur le routage P2P sont assez peu importants puisqu’une décision de router vers un pair de cette table de proximité n’est prise qu’en dernier recours face à un choix de nœuds. La localité dans Pastry n’est donc pas exploitée pour une stratégie de prise en compte du réseau sous-jacent. construit indépendamment du réseau sous-jacent. Durant le mécanisme de routage, si un pair a l’opportunité de choisir parmi k prochains sauts possibles, il choisit de router le message vers le nœud qui, parmi ces k nœuds, est le plus proche de lui dans le réseau sous-jacent. Une alternative serait de choisir de router vers le nœud qui représente le meilleur compromis entre la proximité et la progression dans l’espace d’identification overlay. En tout cas, les performances globales de cette technique dépendent de k, qui est proportionnel à la taille de la table de routage. Par ailleurs, des petits sauts risquent d’être contrecarrés par l’augmentation du nombre de sauts. La technique de l’agencement géographique vise à reporter l’espace d’identification overlay sur la topologie sous-jacente, et biaise l’attribution des nodeIds. Ceci entraîne forcément une diminution des délais, mais les nodeIds ne sont plus uniformément distribués dans l’espace d’identification overlay. D’où des problèmes d’équilibrage de charge. Les nœuds voisins sont aussi susceptibles de subir des pannes ou attaques corrélées, ce qui affaiblit la robustesse et la sécurité du système. Malgré ces revers, cette technique a bien  espaces d’identification à une seule dimension, comme est le cas de la majorité des DHT (e.g. Chord [SML+01], Pastry [RD01], etc.)

Choix du voisin à proximité

Comme la technique d’agencement géographique, la technique du choix du voisin à proximité (proximity neighbor selection ou PNS) [RSS02] intervient dans la construction d’un overlay conscient de la topologie sous-jacente. Mais au lieu de biaiser l’attribution des nodeIds, cette technique choisit pour les entrées de sa table de routage des références vers les nœuds de son voisinage qui satisfont les contraintes algorithmiques du protocole mis en œuvre. La technique PNS n’est alors susceptible de satisfaire ses ambitions que si elle est appliquée à un algorithme qui permet une certaine liberté dans la construction des tables de routage sans affecter le diamètre du réseau. Elle peut donc être appliquée à la construction du neighborhood set de Pastry [RD01], par exemple, mais pas à la construction de DHTs CAN [RFH+01, Rat02] ou Chord [SML+01], où chaque entrée de la table de routage fait référence à un point bien précis de l’espace d’identification overlay. Mais quand elle est mise en œuvre, la technique PNS introduit un surcoût assez faible et facilite la gestion de l’antémémoire (puisque les nœuds voisins dans le réseau overlay sont alors susceptibles d’être voisins au niveau sous-jacent). Cette technique de choix du voisin à proximité s’adapte à des caractéristiques de réseau variables. Elle peut être considérée aussi comme un bon compromis qui diminue le diamètre du réseau et préserve l’équilibre de charge. Cependant, la découverte des voisins est étroitement liée au protocole.

Solutions de prise en compte de la topologie du réseau sous-jacent

Les trois techniques d’exploitation de l’information de proximité présentées au paragraphe précédent ont des limites importantes, et parfois s’impliquent dans le protocole de routage overlay. Voilà pourquoi de nouvelles solutions structurelles ont émergé. Elles sont nombreuses et la liste continue à s’allonger. Dans ce paragraphe, nous présentons brièvement les principaux systèmes P2P utilisant des DHTs et connus pour prendre en dessus d’un réseau P2P utilisant une DHT. Ce réseau secondaire exploite les caractéristiques du réseau sous-jacent au réseau P2P initial. Il est constitué en fait des pairs ayant de grandes capacités réseau (en termes de bande passante, puissance du processeur, etc.) et situés près des points d’accès au réseau IP (e.g. passerelles, routeurs). Ces pairs particuliers sont dits des super-nœuds et agissent comme des points de repère (landmarks) pour chaque domaine du réseau IP. Chaque super-nœud gère un groupe de pairs locaux afin de réduire le trafic dans le réseau. En même temps, chaque super-nœud garde des informations de tous les pairs de son domaine ; ce qui peut les engorger.