Ny tilgang til Vertex-forbindelse kan maksimere netværks båndbredde

Dataloger søger konstant efter måder at presse stadig mere båndbredde fra kommunikationsnetværk.

Nu kan en ny tilgang til at forstå et grundlæggende koncept i grafteori, kendt som vertex-forbindelse, i sidste ende føre til kommunikationsprotokoller - de regler, der styrer, hvordan digitale meddelelser udveksles - som lokker så meget båndbredde som muligt fra netværk.

Grafteori spiller en central rolle i matematik og datalogi, og bruges til at beskrive forholdet mellem forskellige objekter. Hver graf består af et antal knudepunkter eller hjørner, som repræsenterer objekterne, og forbindende linjer mellem dem, kendt som kanter, som angiver forholdet mellem dem. Et kommunikationsnetværk, for eksempel, kan repræsenteres som en graf, hvor hver knude i netværket er ét vertex, og en forbindelse mellem to knudepunkter afbildet som en kant.

Et af de grundlæggende begreber inden for grafteori er forbindelse, som har to varianter: kantforbindelse og toppunktsforbindelse. Disse er tal, der bestemmer, hvor mange linjer eller noder, der skal fjernes fra en given graf for at afbryde den. Jo lavere kantforbindelses- eller vertex-forbindelsesnummer for en graf, desto lettere er det derfor at afbryde eller bryde fra hinanden.

På denne måde viser begge begreber, hvor robust et netværk er mod fejl, og hvor meget flow der kan passere gennem det - uanset om informationsstrømmen i et kommunikationsnetværk, trafikstrømmen i et transportsystem eller væskestrømmen i hydraulik.

Reducerer kantforbindelsens kant

Men mens en stor del af forskningen er blevet udført i matematik for at løse problemer forbundet med kantforbindelse, har der været relativt lille succes med at besvare spørgsmål om vertex-forbindelse.

Men på ACM-SIAM Symposium on Discrete Algorithms i Portland, Oregon, i januar, Mohsen Ghaffari, en kandidatstuderende i Datalogi og kunstig intelligens laboratorium på MIT, vil præsentere en ny teknik til at løse problemer med toppunktsforbindelse.

Dette kan i sidste ende hjælpe os med at forstå, hvordan man bygger mere robuste og hurtigere netværk, siger Ghaffari, der udviklede den nye tilgang sammen med Keren Censor-Hillel ved Technion og Fabian Kuhn ved University of Freiburg.

I 1960'erne udviklede matematikerne William Tutte og Crispin Nash-Williams hver for sig teorier om strukturer kaldet kant-disjunkte-spændende træer, som nu fungerer som et af de vigtigste tekniske værktøjer i mange problemer om kantforbindelse.

Et spændingstræ er en undergraf - eller en graf-i-en-graf - hvor alle knuderne er forbundet med det mindste antal kanter. Et sæt spændende træer i en graf kaldes kant-disjunkte, hvis de ikke deler nogen af ​​disse forbindelseslinjer.

Hvis et netværk for eksempel indeholder tre kant-disjunkte spændende træer, kan information flyde parallelt langs hvert af disse træer på samme tid, hvilket betyder tre gange mere båndbredde, end det ville være muligt i en graf, der kun indeholder ét træ. Jo højere antallet af kant-usammenhængende træer, jo større informationsflow, siger Ghaffari. Resultaterne af Tutte og Nash-Williams viser, at hver graf indeholder næsten lige så mange spændingstræer som dens kantforbindelse, siger han.

Nu har holdet skabt en analog teori om toppunktsforbindelse. De gjorde dette ved at opdele grafen i adskilte grupper af noder, kendt som forbundne dominerende sæt. I grafteori kaldes en gruppe knudepunkter for et forbundet dominerende sæt, hvis alle knudepunkter i den er forbundet med hinanden, og enhver anden knude i grafen støder op til mindst én af dem i gruppen.

På denne måde kan information spredes blandt noderne i sættet og derefter videregives til enhver anden node i netværket.

Så på samme måde som Tutte og Nash-Williams' resultater for kantforbindelse, indeholder hver graf næsten lige så mange toppunkt-disjunkte forbundne dominerende sæt som dens toppunktforbindelse, siger Ghaffari.

Så hvis du tænker på en applikation som at udsende information gennem et netværk, kan vi nu dekomponere netværket i mange grupper, der hver især er et forbundet dominerende sæt, siger han. Hver af disse grupper vil derefter være ansvarlige for at udsende nogle sæt af beskederne, og alle grupper arbejder parallelt med at udsende alle beskederne hurtigt - næsten så hurtigt som muligt.

Holdet har nu udviklet en algoritme, der omhyggeligt kan dekomponere et netværk i mange forbundne dominerende sæt. På den måde kan den strukturere såkaldte trådløse ad hoc-netværk, hvor individuelle noder dirigerer data ved at videregive dem fra den ene til den næste for at sikre den bedst mulige hastighed i informationsflowet. Vi vil gerne kunne sprede så meget information som muligt pr. tidsenhed, for at skabe hurtigere og hurtigere netværk, siger Ghaffari. Og når en graf har en bedre toppunktsforbindelse, tillader den et større flow [af information], tilføjer han.

Anvendelser til vurdering af robusthed

Forskerne kan også bruge deres nye tilgang til at analysere et netværks robusthed mod tilfældige fejl. Disse nye teknikker giver os også mulighed for at analysere, om et netværk sandsynligvis vil forblive forbundet, når dets noder fejler tilfældigt med en given sandsynlighed, siger Ghaffari. Pålidelighed mod tilfældige kantfejl er godt forstået, men vi vidste meget mindre om det mod knudefejl, tilføjer han.

Noga Alon, professor i matematik og datalogi ved Tel Aviv Universitet, siger, at Ghaffari og hans medforfattere har identificeret den idé, der bestemmer det største opnåelige flow, når de udsender beskeder ved hjælp af routing i kommunikationsnetværk.

Undersøgelsen af ​​denne forestilling, vertex disjoint forbundne dominerende sæt, behandles i dette papir af en elegant kombination af kombinatoriske, probabilistiske og algoritmiske teknikker, siger han.

skjule