Neuer Ansatz für Vertex-Konnektivität könnte die Bandbreite von Netzwerken maximieren

Informatiker suchen ständig nach Wegen, immer mehr Bandbreite aus Kommunikationsnetzen herauszuholen.

Nun könnte ein neuer Ansatz zum Verständnis eines grundlegenden Konzepts der Graphentheorie, bekannt als Vertex-Konnektivität, letztendlich zu Kommunikationsprotokollen führen – den Regeln, die den Austausch digitaler Nachrichten regeln – die den Netzwerken so viel Bandbreite wie möglich entlocken.

Die Graphentheorie spielt in der Mathematik und Informatik eine zentrale Rolle und wird verwendet, um die Beziehung zwischen verschiedenen Objekten zu beschreiben. Jeder Graph besteht aus einer Reihe von Knoten oder Scheitelpunkten, die die Objekte darstellen, und Verbindungslinien zwischen ihnen, die als Kanten bezeichnet werden und die Beziehungen zwischen ihnen anzeigen. Ein Kommunikationsnetzwerk kann beispielsweise als Graph dargestellt werden, wobei jeder Knoten im Netzwerk ein Knoten ist und eine Verbindung zwischen zwei Knoten als Kante dargestellt wird.

Eines der grundlegenden Konzepte der Graphentheorie ist die Konnektivität, die zwei Varianten hat: Kantenkonnektivität und Vertexkonnektivität. Dies sind Zahlen, die bestimmen, wie viele Linien oder Knoten aus einem bestimmten Graphen entfernt werden müssten, um ihn zu trennen. Je niedriger die Kantenkonnektivitäts- oder Knotenkonnektivitätszahl eines Graphen ist, desto einfacher ist es daher, die Verbindung zu trennen oder aufzubrechen.

Auf diese Weise zeigen beide Konzepte, wie robust ein Netz gegen Ausfälle ist und wie viel Durchfluss es durchströmen kann – sei es der Informationsfluss in einem Kommunikationsnetz, der Verkehrsfluss in einem Verkehrssystem oder der Flüssigkeitsfluss in der Hydraulik.

Reduzierung der Edge-Konnektivität

Während jedoch in der Mathematik viel Forschung betrieben wurde, um Probleme im Zusammenhang mit der Kantenkonnektivität zu lösen, war die Beantwortung von Fragen zur Vertexkonnektivität relativ wenig erfolgreich.

Aber auf dem ACM-SIAM Symposium on Discrete Algorithms in Portland, Oregon, im Januar, Mohsen Ghaffari, Doktorand der Labor für Informatik und künstliche Intelligenz am MIT, wird eine neue Technik zur Lösung von Vertex-Konnektivitätsproblemen vorstellen.

Dies könnte uns letztendlich helfen zu verstehen, wie wir robustere und schnellere Netzwerke aufbauen können, sagt Ghaffari, der den neuen Ansatz zusammen mit Keren Censor-Hillel vom Technion und Fabian Kuhn von der Universität Freiburg entwickelt hat.

In den 1960er Jahren entwickelten die Mathematiker William Tutte und Crispin Nash-Williams getrennt Theorien über Strukturen, die als kantendisjunkte Spannbäume bezeichnet werden und heute als eines der wichtigsten technischen Werkzeuge bei vielen Problemen der Kantenkonnektivität dienen.

Ein aufspannender Baum ist ein Teilgraph – oder ein Graph-im-Graph – in dem alle Knoten durch die kleinste Anzahl von Kanten verbunden sind. Eine Menge aufspannender Bäume innerhalb eines Graphen heißt kantendisjunkt, wenn sie keine dieser Verbindungslinien gemeinsam haben.

Enthält ein Netzwerk beispielsweise drei kantendisjunkte aufspannende Bäume, können Informationen entlang jedes dieser Bäume gleichzeitig parallel fließen, d. h. dreimal mehr Bandbreite als in einem Graphen mit nur einem Baum möglich wäre. Je höher die Anzahl der kantendisjunkten Spannbäume, desto größer der Informationsfluss, sagt Ghaffari. Die Ergebnisse von Tutte und Nash-Williams zeigen, dass jeder Graph fast so viele aufspannende Bäume enthält wie seine Kantenkonnektivität, sagt er.

Jetzt hat das Team eine analoge Theorie zur Vertex-Konnektivität erstellt. Sie taten dies, indem sie den Graphen in getrennte Gruppen von Knoten zerlegten, die als verbundene dominierende Mengen bekannt sind. In der Graphentheorie wird eine Gruppe von Knoten als verbundene dominierende Menge bezeichnet, wenn alle Knoten in ihr miteinander verbunden sind und jeder andere Knoten innerhalb des Graphen an mindestens einen der Knoten innerhalb der Gruppe angrenzt.

Auf diese Weise können Informationen unter den Knoten des Satzes verbreitet und dann an jeden anderen Knoten im Netzwerk weitergegeben werden.

Ähnlich wie die Ergebnisse von Tutte und Nash-Williams für die Kantenkonnektivität enthält jeder Graph fast so viele knotendisjunkte zusammenhängende dominierende Mengen wie seine Knotenkonnektivität, sagt Ghaffari.

Wenn Sie sich also eine Anwendung wie das Senden von Informationen über ein Netzwerk vorstellen, können wir das Netzwerk jetzt in viele Gruppen aufteilen, von denen jede eine verbundene dominierende Menge ist, sagt er. Jede dieser Gruppen ist dann für das Senden eines bestimmten Satzes der Nachrichten verantwortlich, und alle Gruppen arbeiten parallel, um alle Nachrichten schnell zu senden – fast so schnell wie möglich.

Das Team hat nun einen Algorithmus entwickelt, der ein Netzwerk sorgfältig in viele verbundene dominierende Mengen zerlegen kann. Auf diese Weise kann er sogenannte drahtlose Ad-hoc-Netzwerke aufbauen, in denen einzelne Knoten Daten durch Weiterleitung von einem zum nächsten weiterleiten, um eine bestmögliche Geschwindigkeit des Informationsflusses zu gewährleisten. Wir wollen in der Lage sein, so viele Informationen wie möglich pro Zeiteinheit zu verbreiten, um immer schnellere Netzwerke zu schaffen, sagt Ghaffari. Und wenn ein Graph eine bessere Vertex-Konnektivität hat, ermöglicht er einen größeren [Informationsfluss], fügt er hinzu.

Anwendungen zur Bewertung der Robustheit

Mit ihrem neuen Ansatz können die Forscher auch die Robustheit eines Netzwerks gegenüber zufälligen Ausfällen analysieren. Diese neuen Techniken ermöglichen es uns auch zu analysieren, ob ein Netzwerk wahrscheinlich verbunden bleibt, wenn seine Knoten mit einer bestimmten Wahrscheinlichkeit zufällig ausfallen, sagt Ghaffari. Die Zuverlässigkeit gegen zufällige Edge-Ausfälle ist gut bekannt, aber über Knotenausfälle wussten wir viel weniger, fügt er hinzu.

Noga Alon, Professor für Mathematik und Informatik an der Universität Tel Aviv, sagt, dass Ghaffari und seine Mitautoren den Begriff identifiziert haben, der den größten erreichbaren Fluss beim Senden von Nachrichten mithilfe von Routing in Kommunikationsnetzwerken bestimmt.

Die Untersuchung dieses Begriffs, vertexdisjunkte verbundene dominierende Mengen, wird in diesem Artikel durch eine elegante Kombination kombinatorischer, probabilistischer und algorithmischer Techniken behandelt, sagt er.

verbergen