211service.com
Nieuwe benadering van Vertex-connectiviteit kan de bandbreedte van netwerken maximaliseren
Computerwetenschappers zijn voortdurend op zoek naar manieren om steeds meer bandbreedte uit communicatienetwerken te persen.
Nu zou een nieuwe benadering voor het begrijpen van een basisconcept in de grafentheorie, bekend als vertex-connectiviteit, uiteindelijk kunnen leiden tot communicatieprotocollen - de regels die bepalen hoe digitale berichten worden uitgewisseld - die zoveel mogelijk bandbreedte uit netwerken halen.
Grafentheorie speelt een centrale rol in wiskunde en informatica en wordt gebruikt om de relatie tussen verschillende objecten te beschrijven. Elke grafiek bestaat uit een aantal knooppunten, of hoekpunten, die de objecten vertegenwoordigen, en verbindingslijnen ertussen, ook wel randen genoemd, die de relaties ertussen aangeven. Een communicatienetwerk kan bijvoorbeeld worden weergegeven als een grafiek waarbij elk knooppunt in het netwerk één hoekpunt is en een verbinding tussen twee knooppunten wordt weergegeven als een rand.
Een van de fundamentele concepten binnen de grafentheorie is connectiviteit, die twee varianten heeft: edge-connectiviteit en vertex-connectiviteit. Dit zijn getallen die bepalen hoeveel lijnen of knopen er uit een bepaalde grafiek moeten worden verwijderd om deze los te koppelen. Hoe lager het nummer van de edge-connectivity of vertex-connectivity van een grafiek, hoe gemakkelijker het is om los te koppelen of uit elkaar te vallen.
Op deze manier laten beide concepten zien hoe robuust een netwerk is tegen storingen en hoeveel stroom er doorheen kan gaan - of het nu gaat om de informatiestroom in een communicatienetwerk, verkeersstroom in een transportsysteem of vloeistofstroom in hydrauliek.
De edge van edge-connectiviteit verminderen
Hoewel er in de wiskunde veel onderzoek is gedaan naar het oplossen van problemen die verband houden met edge-connectiviteit, is er relatief weinig succes geweest bij het beantwoorden van vragen over vertex-connectiviteit.
Maar op het ACM-SIAM-symposium over discrete algoritmen in Portland, Oregon, in januari, zei Mohsen Ghaffari, een afgestudeerde student in de Laboratorium voor computerwetenschappen en kunstmatige intelligentie aan het MIT, zal een nieuwe techniek presenteren voor het aanpakken van vertex-connectiviteitsproblemen.
Dit zou ons uiteindelijk kunnen helpen te begrijpen hoe we robuustere en snellere netwerken kunnen bouwen, zegt Ghaffari, die de nieuwe aanpak ontwikkelde samen met Keren Censor-Hillel aan de Technion en Fabian Kuhn aan de Universiteit van Freiburg.
In de jaren zestig ontwikkelden wiskundigen William Tutte en Crispin Nash-Williams afzonderlijk theorieën over structuren die edge-disjoint spanning trees worden genoemd en die nu dienen als een van de belangrijkste technische hulpmiddelen bij veel problemen met edge-connectiviteit.
Een opspannende boom is een subgraaf - of een grafiek-in-een-grafiek - waarin alle knooppunten zijn verbonden door het kleinste aantal randen. Een reeks opspannende bomen in een graaf wordt edge-disjunct genoemd als ze geen van deze verbindingslijnen delen.
Als een netwerk bijvoorbeeld drie edge-disjoint opspannende bomen bevat, kan informatie tegelijkertijd langs elk van deze bomen stromen, wat betekent dat er drie keer meer bandbreedte is dan mogelijk zou zijn in een grafiek met slechts één boom. Hoe meer edge-disjoint opspannende bomen, hoe groter de informatiestroom, zegt Ghaffari. De resultaten van Tutte en Nash-Williams laten zien dat elke grafiek bijna net zoveel opspannende bomen bevat als de randconnectiviteit, zegt hij.
Nu heeft het team een analoge theorie over vertex-connectiviteit ontwikkeld. Ze deden dit door de grafiek op te splitsen in afzonderlijke groepen knooppunten, ook wel verbonden dominante sets genoemd. In de grafentheorie wordt een groep knooppunten een verbonden dominerende verzameling genoemd als alle hoekpunten erin met elkaar zijn verbonden en elk ander knooppunt in de graaf grenst aan ten minste één van die binnen de groep.
Op deze manier kan informatie worden verspreid onder de knooppunten van de set en vervolgens worden doorgegeven aan elk ander knooppunt in het netwerk.
Dus, op een vergelijkbare manier als de resultaten van Tutte en Nash-Williams voor edge-connectiviteit, bevat elke grafiek bijna net zoveel vertex-disjuncte verbonden dominante sets als zijn vertex-connectiviteit, zegt Ghaffari.
Dus als je denkt aan een toepassing zoals het uitzenden van informatie via een netwerk, kunnen we het netwerk nu ontbinden in vele groepen, die elk een verbonden dominante set zijn, zegt hij. Elk van deze groepen zal dan verantwoordelijk zijn voor het uitzenden van een aantal berichten, en alle groepen werken parallel om alle berichten snel uit te zenden - bijna zo snel mogelijk.
Het team heeft nu een algoritme ontwikkeld dat een netwerk zorgvuldig kan ontleden in vele verbonden dominante sets. Op deze manier kan het zogenaamde draadloze ad-hocnetwerken structureren, waarin individuele knooppunten gegevens routeren door deze van de ene naar de andere door te geven om de best mogelijke snelheid van informatiestroom te garanderen. We willen zoveel mogelijk informatie per tijdseenheid kunnen verspreiden, om steeds snellere netwerken te creëren, zegt Ghaffari. En wanneer een grafiek een betere verbinding met de hoekpunten heeft, is er een grotere stroom [informatie] mogelijk, voegt hij eraan toe.
Toepassingen bij het beoordelen van robuustheid
De onderzoekers kunnen hun nieuwe aanpak ook gebruiken om de robuustheid van een netwerk tegen willekeurige storingen te analyseren. Deze nieuwe technieken stellen ons ook in staat om te analyseren of een netwerk waarschijnlijk verbonden zal blijven wanneer zijn knooppunten willekeurig en met een bepaalde waarschijnlijkheid falen, zegt Ghaffari. Betrouwbaarheid tegen willekeurige randstoringen is goed begrepen, maar we wisten daar veel minder van tegen knooppuntstoringen, voegt hij eraan toe.
Noga Alon, hoogleraar wiskunde en informatica aan de Universiteit van Tel Aviv, zegt dat Ghaffari en zijn collega-auteurs het idee hebben geïdentificeerd dat de grootste haalbare stroom bepaalt bij het uitzenden van berichten met behulp van routering in communicatienetwerken.
Het onderzoek naar dit begrip, vertex disjuncte verbonden dominerende sets, wordt in dit artikel behandeld door een elegante combinatie van combinatorische, probabilistische en algoritmische technieken, zegt hij.