Nowe podejście do łączności Vertex może zmaksymalizować przepustowość sieci

Informatycy nieustannie poszukują sposobów na wyciśnięcie coraz większej przepustowości z sieci komunikacyjnych.

Teraz nowe podejście do zrozumienia podstawowej koncepcji w teorii grafów, znanej jako łączność wierzchołków, może ostatecznie doprowadzić do powstania protokołów komunikacyjnych — reguł rządzących sposobem wymiany wiadomości cyfrowych — które zapewniają jak największą przepustowość sieci.

Teoria grafów odgrywa kluczową rolę w matematyce i informatyce i służy do opisywania relacji między różnymi obiektami. Każdy graf składa się z wielu węzłów lub wierzchołków reprezentujących obiekty i łączących je linii, zwanych krawędziami, które oznaczają relacje między nimi. Na przykład sieć komunikacyjna może być reprezentowana jako graf, przy czym każdy węzeł w sieci jest jednym wierzchołkiem, a połączenie między dwoma węzłami jest przedstawione jako krawędź.

Jednym z podstawowych pojęć w teorii grafów jest łączność, która ma dwa warianty: łączność krawędzi i łączność wierzchołków. Są to liczby, które określają, ile linii lub węzłów musiałoby zostać usuniętych z danego wykresu, aby go rozłączyć. Im niższa jest liczba łączności krawędzi lub wierzchołków grafu, tym łatwiej jest go odłączyć lub rozbić.

W ten sposób obie koncepcje pokazują, jak odporna jest sieć na awarie i jak duży przepływ może przez nią przepływać — czy to przepływ informacji w sieci komunikacyjnej, przepływ ruchu w systemie transportowym, czy przepływ płynu w hydraulice.

Zmniejszenie krawędzi łączności krawędzi

Jednakże, chociaż przeprowadzono wiele badań w matematyce w celu rozwiązania problemów związanych z łącznością brzegową, stosunkowo niewiele udało się odpowiedzieć na pytania dotyczące łączności wierzchołków.

Ale na sympozjum ACM-SIAM na temat algorytmów dyskretnych w Portland w stanie Oregon w styczniu Mohsen Ghaffari, doktorant Laboratorium Informatyki i Sztucznej Inteligencji na MIT przedstawi nową technikę rozwiązywania problemów z łącznością wierzchołków.

To może ostatecznie pomóc nam zrozumieć, jak budować solidniejsze i szybsze sieci, mówi Ghaffari, który opracował nowe podejście wraz z Kerenem Censor-Hillelem z Technion i Fabianem Kuhnem z Uniwersytetu we Fryburgu.

W latach sześćdziesiątych matematycy William Tutte i Crispin Nash-Williams osobno opracowali teorie dotyczące struktur zwanych rozłącznymi drzewami rozpinającymi krawędzie, które obecnie służą jako jedno z kluczowych narzędzi technicznych w wielu problemach dotyczących łączności krawędzi.

Drzewo opinające to podgraf — lub graf w grafie — w którym wszystkie węzły są połączone najmniejszą liczbą krawędzi. Zbiór drzew opinających w grafie nazywamy rozłącznymi krawędziami, jeśli nie dzielą one żadnej z tych linii łączących.

Jeśli sieć zawiera na przykład trzy rozłączne krawędziowe drzewa opinające, informacje mogą płynąć równolegle wzdłuż każdego z tych drzew w tym samym czasie, co oznacza trzykrotnie większą przepustowość niż byłoby to możliwe w przypadku grafu zawierającego tylko jedno drzewo. Ghaffari mówi, że im większa liczba drzew spinających o rozłącznych krawędziach, tym większy przepływ informacji. Wyniki Tutte'a i Nasha-Williamsa pokazują, że każdy wykres zawiera prawie tyle drzew opinających, co jego łączność krawędziowa, mówi.

Teraz zespół stworzył analogiczną teorię dotyczącą łączności wierzchołków. Zrobili to, dzieląc wykres na oddzielne grupy węzłów, znane jako połączone zbiory dominujące. W teorii grafów grupa węzłów nazywana jest połączonym zbiorem dominującym, jeśli wszystkie wierzchołki w jej obrębie są ze sobą połączone, a każdy inny węzeł w grafie sąsiaduje z przynajmniej jednym z wierzchołków znajdujących się w grupie.

W ten sposób informacje mogą być rozpowszechniane pomiędzy węzłami zbioru, a następnie przekazywane do dowolnego innego węzła w sieci.

Tak więc, podobnie jak wyniki Tutte'a i Nasha-Williamsa dla łączności krawędzi, każdy wykres zawiera prawie tyle samo rozłącznie połączonych zestawów dominujących, co jego łączność wierzchołków, mówi Ghaffari.

Więc jeśli pomyślisz o aplikacji, takiej jak przesyłanie informacji przez sieć, możemy teraz rozłożyć sieć na wiele grup, z których każda stanowi jeden połączony, dominujący zestaw, mówi. Każda z tych grup będzie następnie odpowiedzialna za nadawanie pewnego zestawu komunikatów, a wszystkie grupy pracują równolegle, aby szybko nadawać wszystkie komunikaty — prawie tak szybko, jak to możliwe.

Zespół opracował teraz algorytm, który może ostrożnie rozłożyć sieć na wiele połączonych, dominujących zestawów. W ten sposób może tworzyć tzw. bezprzewodowe sieci ad hoc, w których poszczególne węzły kierują dane, przekazując je od jednego do drugiego, aby zapewnić możliwie najlepszą prędkość przepływu informacji. Chcemy móc rozpowszechniać jak najwięcej informacji w jednostce czasu, aby tworzyć coraz szybsze sieci, mówi Ghaffari. A kiedy graf ma lepszą łączność wierzchołków, pozwala na większy przepływ [informacji], dodaje.

Zastosowania w ocenie odporności

Naukowcy mogą również wykorzystać swoje nowe podejście do analizy odporności sieci na przypadkowe awarie. Te nowe techniki pozwalają nam również analizować, czy sieć prawdopodobnie pozostanie połączona, gdy jej węzły ulegną losowej awarii z określonym prawdopodobieństwem, mówi Ghaffari. Niezawodność w przypadku losowych awarii krawędzi jest dobrze zrozumiana, ale znacznie mniej wiedzieliśmy o tym w przypadku awarii węzłów — dodaje.

Noga Alon, profesor matematyki i informatyki na Uniwersytecie w Tel Awiwie, mówi, że Ghaffari i jego koledzy autorzy zidentyfikowali pojęcie, które determinuje największy możliwy do osiągnięcia przepływ podczas nadawania wiadomości przy użyciu routingu w sieciach komunikacyjnych.

Badanie tego pojęcia, rozłącznie połączonych wierzchołków zbiorów dominujących, zostało potraktowane w tym artykule przez eleganckie połączenie technik kombinatorycznych, probabilistycznych i algorytmicznych, mówi.

ukryć