Ny metod för Vertex-anslutning kan maximera nätverkens bandbredd

Datavetare söker ständigt efter sätt att pressa ut allt mer bandbredd från kommunikationsnätverk.

Nu kan ett nytt tillvägagångssätt för att förstå ett grundläggande koncept inom grafteori, känd som vertex-anslutning, i slutändan leda till kommunikationsprotokoll - reglerna som styr hur digitala meddelanden utbyts - som coaxar så mycket bandbredd som möjligt från nätverk.

Grafteori spelar en central roll inom matematik och datavetenskap, och används för att beskriva förhållandet mellan olika objekt. Varje graf består av ett antal noder, eller hörn, som representerar objekten, och förbindande linjer mellan dem, så kallade kanter, som anger förhållandet mellan dem. Ett kommunikationsnätverk, till exempel, kan representeras som en graf där varje nod i nätverket är en vertex, och en förbindelse mellan två noder avbildad som en kant.

Ett av de grundläggande begreppen inom grafteorin är connectivity, som har två varianter: edge connectivity och vertex connectivity. Dessa är siffror som bestämmer hur många linjer eller noder som skulle behöva tas bort från en given graf för att koppla bort den. Ju lägre kantanslutnings- eller vertexanslutningsnummer för en graf, desto lättare är det därför att koppla från eller bryta isär.

På detta sätt visar båda begreppen hur robust ett nätverk är mot fel, och hur mycket flöde som kan passera genom det – oavsett om informationsflödet i ett kommunikationsnät, trafikflöde i ett transportsystem eller vätskeflöde i hydraulik.

Minskar kantanslutningens kant

Men även om en hel del forskning har utförts inom matematik för att lösa problem associerade med kantanslutningar, har det varit relativt liten framgång med att svara på frågor om vertexanslutning.

Men på ACM-SIAM Symposium on Discrete Algorithms i Portland, Oregon, i januari, Mohsen Ghaffari, en doktorand i Laboratoriet för datavetenskap och artificiell intelligens vid MIT, kommer att presentera en ny teknik för att ta itu med problem med vertex-anslutningar.

Detta kan i slutändan hjälpa oss att förstå hur man bygger mer robusta och snabbare nätverk, säger Ghaffari, som utvecklade det nya tillvägagångssättet tillsammans med Keren Censor-Hillel vid Technion och Fabian Kuhn vid University of Freiburg.

På 1960-talet utvecklade matematikerna William Tutte och Crispin Nash-Williams separat teorier om strukturer som kallas kant-disjunkt spännande träd, som nu fungerar som ett av de viktigaste tekniska verktygen i många problem om kantanslutningar.

Ett spännträd är en subgraf - eller en graf-i-en-graf - där alla noder är sammankopplade med det minsta antalet kanter. En uppsättning spännande träd i en graf kallas kant-disjunkt om de inte delar någon av dessa förbindande linjer.

Om till exempel ett nätverk innehåller tre kant-disjunkta spännande träd, kan information flöda parallellt längs vart och ett av dessa träd samtidigt, vilket betyder tre gånger mer bandbredd än vad som skulle vara möjligt i en graf som bara innehåller ett träd. Ju högre antal kant-disjunkande träd, desto större informationsflöde, säger Ghaffari. Resultaten från Tutte och Nash-Williams visar att varje graf innehåller nästan lika många spännande träd som dess kantanslutningar, säger han.

Nu har teamet skapat en analog teori om vertexanslutning. De gjorde detta genom att dela upp grafen i separerade grupper av noder, kända som anslutna dominerande uppsättningar. I grafteorin kallas en grupp av noder för en ansluten dominerande uppsättning om alla hörn inom den är anslutna till varandra, och vilken annan nod som helst i grafen ligger intill åtminstone en av dem i gruppen.

På detta sätt kan information spridas bland noderna i uppsättningen och sedan skickas till vilken annan nod som helst i nätverket.

Så, på ett liknande sätt som Tutte och Nash-Williams resultat för kantanslutningar, innehåller varje graf nästan lika många vertex-disjunkte anslutna dominerande uppsättningar som dess vertexanslutning, säger Ghaffari.

Så om du tänker på en applikation som att sända information genom ett nätverk, kan vi nu dela upp nätverket i många grupper, som var och en är en ansluten dominerande uppsättning, säger han. Var och en av dessa grupper kommer sedan att ansvara för att sända någon uppsättning av meddelanden, och alla grupper arbetar parallellt för att sända alla meddelanden snabbt - nästan så snabbt som möjligt.

Teamet har nu utvecklat en algoritm som försiktigt kan dekomponera ett nätverk i många anslutna dominerande uppsättningar. På så sätt kan den strukturera så kallade trådlösa ad hoc-nätverk, där enskilda noder dirigerar data genom att överföra den från den ena till den andra för att säkerställa bästa möjliga hastighet i informationsflödet. Vi vill kunna sprida så mycket information som möjligt per tidsenhet, för att skapa snabbare och snabbare nätverk, säger Ghaffari. Och när en graf har en bättre vertexanslutning tillåter den ett större informationsflöde, tillägger han.

Tillämpningar vid bedömning av robusthet

Forskarna kan också använda sin nya metod för att analysera ett nätverks robusthet mot slumpmässiga fel. Dessa nya tekniker tillåter oss också att analysera om ett nätverk sannolikt kommer att förbli uppkopplat när dess noder misslyckas slumpmässigt med viss sannolikhet, säger Ghaffari. Tillförlitlighet mot random edge-fel är väl förstått, men vi visste mycket mindre om det mot nodfel, tillägger han.

Noga Alon, professor i matematik och datavetenskap vid Tel Aviv University, säger att Ghaffari och hans medförfattare har identifierat den idé som bestämmer det största möjliga flödet när man sänder meddelanden med hjälp av routing i kommunikationsnätverk.

Utredningen av detta begrepp, vertex disjunkt anslutna dominerande uppsättningar, behandlas i denna artikel med en elegant kombination av kombinatoriska, probabilistiska och algoritmiska tekniker, säger han.

Dölj