Une nouvelle approche de la connectivité Vertex pourrait maximiser la bande passante des réseaux

Les informaticiens sont constamment à la recherche de moyens d'extraire toujours plus de bande passante des réseaux de communication.

Désormais, une nouvelle approche pour comprendre un concept de base de la théorie des graphes, connue sous le nom de connectivité des sommets, pourrait finalement conduire à des protocoles de communication - les règles qui régissent la façon dont les messages numériques sont échangés - qui tirent le plus de bande passante possible des réseaux.

La théorie des graphes joue un rôle central en mathématiques et en informatique et est utilisée pour décrire la relation entre différents objets. Chaque graphique se compose d'un certain nombre de nœuds, ou sommets, qui représentent les objets, et de lignes de connexion entre eux, appelées arêtes, qui signifient les relations entre eux. Un réseau de communication, par exemple, peut être représenté sous la forme d'un graphique, chaque nœud du réseau étant un sommet et une connexion entre deux nœuds représentée sous la forme d'une arête.

L'un des concepts fondamentaux de la théorie des graphes est la connectivité, qui a deux variantes : la connectivité des bords et la connectivité des sommets. Ce sont des nombres qui déterminent combien de lignes ou de nœuds devraient être supprimés d'un graphique donné pour le déconnecter. Par conséquent, plus le nombre de connectivité de bord ou de connectivité de sommet d'un graphe est faible, plus il est facile de se déconnecter ou de se séparer.

De cette façon, les deux concepts montrent à quel point un réseau est robuste contre les pannes et quelle quantité de flux peut le traverser - qu'il s'agisse du flux d'informations dans un réseau de communication, du flux de trafic dans un système de transport ou du flux de fluide dans l'hydraulique.

Réduire la périphérie de la connectivité

Cependant, alors que de nombreuses recherches ont été menées en mathématiques pour résoudre les problèmes associés à la connectivité des bords, il y a eu relativement peu de succès pour répondre aux questions sur la connectivité des sommets.

Mais lors du Symposium ACM-SIAM sur les algorithmes discrets à Portland, Oregon, en janvier, Mohsen Ghaffari, un étudiant diplômé du Laboratoire d'informatique et d'intelligence artificielle au MIT, présentera une nouvelle technique pour résoudre les problèmes de connectivité des sommets.

Cela pourrait finalement nous aider à comprendre comment construire des réseaux plus robustes et plus rapides, explique Ghaffari, qui a développé la nouvelle approche aux côtés de Keren Censor-Hillel au Technion et de Fabian Kuhn à l'Université de Fribourg.

Dans les années 1960, les mathématiciens William Tutte et Crispin Nash-Williams ont développé séparément des théories sur les structures appelées arbres couvrants à bords disjoints, qui constituent désormais l'un des outils techniques clés dans de nombreux problèmes de connectivité des bords.

Un arbre couvrant est un sous-graphe - ou un graphe dans un graphe - dans lequel tous les nœuds sont connectés par le plus petit nombre d'arêtes. Un ensemble d'arbres couvrants dans un graphe est appelé edge-disjoint s'ils ne partagent aucune de ces lignes de connexion.

Si un réseau contient trois arbres couvrants séparés par les bords, par exemple, les informations peuvent circuler en parallèle le long de chacun de ces arbres en même temps, ce qui signifie trois fois plus de bande passante que ce qui serait possible dans un graphique contenant un seul arbre. Plus le nombre d'arbres couvrants séparés par les bords est élevé, plus le flux d'informations est important, explique Ghaffari. Les résultats de Tutte et Nash-Williams montrent que chaque graphique contient presque autant d'arbres couvrants que sa connectivité de bord, dit-il.

L'équipe a maintenant créé une théorie analogue sur la connectivité des sommets. Pour ce faire, ils ont décomposé le graphique en groupes de nœuds séparés, appelés ensembles dominants connectés. En théorie des graphes, un groupe de nœuds est appelé un ensemble dominant connecté si tous les sommets qu'il contient sont connectés les uns aux autres et que tout autre nœud du graphe est adjacent à au moins un de ceux à l'intérieur du groupe.

De cette manière, les informations peuvent être diffusées parmi les nœuds de l'ensemble, puis transmises à tout autre nœud du réseau.

Ainsi, de la même manière que les résultats de Tutte et Nash-Williams pour la connectivité des bords, chaque graphe contient presque autant d'ensembles dominants connectés disjoints aux sommets que sa connectivité aux sommets, explique Ghaffari.

Donc, si vous pensez à une application comme la diffusion d'informations via un réseau, nous pouvons maintenant décomposer le réseau en plusieurs groupes, chacun étant un ensemble dominant connecté, dit-il. Chacun de ces groupes sera alors responsable de la diffusion d'un ensemble de messages, et tous les groupes travaillent en parallèle pour diffuser tous les messages rapidement, presque aussi vite que possible.

L'équipe a maintenant développé un algorithme qui peut décomposer soigneusement un réseau en de nombreux ensembles dominants connectés. De cette façon, il peut structurer des réseaux dits ad hoc sans fil, dans lesquels des nœuds individuels acheminent des données en les faisant passer de l'un à l'autre pour assurer la meilleure vitesse possible de flux d'informations. Nous voulons pouvoir diffuser autant d'informations que possible par unité de temps, pour créer des réseaux de plus en plus rapides, explique Ghaffari. Et lorsqu'un graphe a une meilleure connectivité de sommets, il permet un plus grand flux [d'informations], ajoute-t-il.

Applications à l'évaluation de la robustesse

Les chercheurs peuvent également utiliser leur nouvelle approche pour analyser la robustesse d'un réseau contre les défaillances aléatoires. Ces nouvelles techniques nous permettent également d'analyser si un réseau est susceptible de rester connecté lorsque ses nœuds échouent de manière aléatoire avec une probabilité donnée, explique Ghaffari. La fiabilité contre les défaillances de bord aléatoires est bien comprise, mais nous en savions beaucoup moins à ce sujet contre les défaillances de nœuds, ajoute-t-il.

Noga Alon, professeur de mathématiques et d'informatique à l'Université de Tel Aviv, explique que Ghaffari et ses collègues auteurs ont identifié la notion qui détermine le plus grand flux possible lors de la diffusion de messages en utilisant le routage dans les réseaux de communication.

L'étude de cette notion, d'ensembles dominants connectés disjoints au sommet, est traitée dans cet article par une élégante combinaison de techniques combinatoires, probabilistes et algorithmiques, dit-il.

cacher