 |
La construction et la maintenance de structures de communication sont des mécanismes fondamentaux dans les réseaux de communication. Ils permettent à deux entités distantes d'acheminer des messages à travers le graphe de communication sous-jacent. Les réseaux actuels ont des contraintes de plus en plus complexes à gérer : dynamicité, occurrence multiple de défaillances, hétérogénéité des supports de communication, gestion large échelle... Nombre de solutions fonctionnent par agrégations successives des visions locales de chaque noeud du graphe et par larges diffusions à travers le réseau.
Nous avons introduit et utilisé la combinaison des concepts de mot circulant (jeton collecteur et diffuseur d'informations) et de marches aléatoires. Un mot circulant est un message qui collecte et diffuse de l'information au sein d'un réseau. Ce mot se déplace donc aléatoirement à travers le graphe de communication. Notre stratégie s'adapte aux contraintes de scalabilité [1] et permet de reconfigurer suffisamment souvent les chemins empruntés pour faire face à l'occurrence de défaillances [2].
Le mot circulant, en se déplaçant, collecte de l'information topologique. Chaque entité qui le reçoit est donc en mesure de construire une image partielle du graphe de communication. La principale difficulté est alors de juger de la pérennité des informations collectées au sein du mot circulant : le réseau étant dynamique, il est tout-à-fait envisageable qu'une information collectée à un moment dans une partie du réseau ne soit plus d'actualité, et engendre donc une structure de communication erronée. L'objet de notre étude consiste donc à établir quelles sont les informations pertinentes et comment réduire au mieux la taille du mot circulant pour permettre à chaque entité de pouvoir communiquer avec les autres.
[1] T.Bernard, A.Bui, L.Pilard and D.Sohier. A Distributed Clustering Algorithm for Large-Scale Dynamic Networks, in Cluster Computing: the Journal of Networks, Software Tools and Applications Springer Verlag, vol 15(4), pp 335-350, 2012.
[2] T.Bernard, A.Bui, and D.Sohier. Universal adaptive self-stabilizing traversal scheme: random walk and reloading wave, in International Journal of Parallel and Distributed Computing, Elsevier eds, vol 73(2), pp 137--149, 2013.
