Nieuw algoritme moet ad-hoc-netwerken verbeteren

Onderzoekers van het Massachusetts Institute of Technology hebben een algoritme ontwikkeld om de invloed van bottlenecks in het verspreiden van informatie over ad-hoc-netwerken te verkleinen. Erg efficiënt is het algoritme nog niet.

Bij ad-hoc-netwerken is er geen centrale entiteit die het netwerkverkeer regelt, waardoor bij het verzenden van informatie geen rekening kan worden gehouden met bottlenecks, knooppunten in het netwerk met weinig bandbreedte. Wanneer elke node in het netwerk verbinding zou maken met een willekeurige andere node om informatie te verzenden, kunnen er bij tussengelegen bottlenecks grote vertragingen optreden.

Het door de MIT-onderzoekers ontwikkelde algoritme moet het mogelijk maken dat bottlenecks sneller worden bereikt en dat ze de gegevens sneller kunnen doorsturen. Het in theorie redelijk simpele algoritme werkt met 'rondes' waarin informatie wordt verzonden. In de eerste ronde zendt elke node naar de dichtstbijzijnde node op het netwerk. In de tweede ronde wordt informatie naar een node verzonden die nog niet is bereikt. In de ronde die daarop volgt wordt informatie naar een willekeurige andere node in het netwerk verstuurd.

Bij elke ronde wordt meegestuurd welke nodes in het netwerk de gegevens al hebben ontvangen. In de eerste ronde kan een node enkel van zichzelf aangeven dat hij de informatie heeft - hij is de bron. Er treedt echter een sneeuwbaleffect op: hoe vaker een node informatie ontvangt, des te meer informatie heeft hij over nodes die de informatie al hebben ontvangen. Dit proces herhaalt zich net zolang totdat alle nodes zijn bereikt.

De methode heeft één groot nadeel: er wordt veel bandbreedte verbruikt, omdat elk pakketje meerdere keren wordt verzonden. Keren Censor-Hillel, een van de onderzoekers, hoopt echter dat er een versie van het algoritme kan worden ontwikkeld die minder bandbreedte vereist.

Ad-hoc-netwerken worden onder meer door gaminghandhelds gebruikt, om spelers die bij elkaar in de buurt zijn samen te laten spelen. Ook in noodsituaties zijn ad-hoc-netwerken bruikbaar, omdat ze door individuele nodes kunnen worden opgezet zonder dat er een bestaande netwerkinfrastructuur hoeft te worden gebruikt.

Reacties (22)

[Eagle Creek]

Ad-hoc-netwerken worden onder meer door gaminghandhelds gebruikt, om spelers die bij elkaar in de buurt zijn samen te laten spelen.

Is er in die situaties van sprake van zoveel vertraging óf überhaupt van bottlenecks? Een groep DSI-ers zit toch in dezelfde ruimte en heeft dezelfde apparatuur lijkt me.

In noodsituaties kan iets dergelijks wel van pas komen, hoewel dat klinkt als een nichemarkt.

Ad hoc is een aardige functionaliteit maar volgens mij wordt het niet echt veel toegepast. Er zijn diverse handzame oplossingen voorhanden volgens mij (zoals Apple Airport Express).

Evenwel lijkt me dat 'sneller is beter' opgaat en dat vooruitgaan geen kwaad kan .

[Reactie gewijzigd door Eagle Creek op 23 juli 2024 01:35]

[Tuxie]

Grapjas. Ad-hoc wordt erg veel toegepast kan ik je vanuit mijn professie vertellen. Niet voor jouw consumentenproduct, maar wel om b.v. communicatie mogelijk te maken tussen legeronderdelen (landmacht tussen voertuigen, marine tussen schepen, luchtmacht tussen vliegtuig - schip - land). We hebben niet overal client-server!

[Eagle Creek]

Wat is daar grappig aan? Ik zei:
--maar volgens mij wordt het niet echt veel toegepast.--

Volgens mij is gebaseerd op mijn ervaring. In mijn omgeving zie ik slechts sporadisch ad-hocnetwerken. Mijn ervaring is dat men voor bestandsuitwisseling vaker gebruikmaakt van USB-sticks of bluetooth. En hoewel ik met grote regelmaat in IT-omgevingen in aanraking kom, heb ik nog nooit aan een ad-hoc mee hoeven te doen.
Windows 7 starter (populair bij netbooks) kan niet eens met ad-hocnetwerken omgaan (lees: niet opzetten en met een omweg joinen).

We hebben inderdaad niet overal client-server maar militaire toepassingen is niet iets waar ik dagelijks mee te maken heb. Verder neem ik aan dat een dergelijk militair netwerk geen gebruikmaakt van dezelfde apparatuur die jij en ik thuis hebben staan.

En jouw voorbeeld tussen vliegtuig-schip-land lijkt me ook niet echt op te gaan voor klassieke ad-hocverbindingen zoals wij ze allemaal kennen. Windows geeft aan dat de apparaten maximaal 10 meter van elkaar verwijderd mogen zijn, en dan word je op het strijdveld zo'n makkelijk doelwit . Dat lijkt me ver van een default netwerk, en het lijkt me eerlijk gezegd ook dat daar andere dan de standaardprotocollen voor worden gebruikt.
Vanuit dat opzich zou een dergelijk algoritme echter misschien wel van pas komen, maar dan nog lijkt me een specifieke markt.

[Reactie gewijzigd door Eagle Creek op 23 juli 2024 01:35]

[Rob Coops]

Ik denk inderdaad dat de toepassingen die men hier voor ogen had veel meer op dit soort dingen gericht zijn.

Het probleem met dit soort netwerken is dat je nooit weet welke andere nodes er zich in het netwerk bevinden hoelang ze onderdeel van je netwerk blijven en wat voor mogelijkheden zij hebben met betrekking tot bandbreedte, latency en dat soort dingen.

Als ik dan belangrijke informatie over dat netwerk moet verspreiden dan moet ik dat zo snel mogelijk doen gewon omdat het zo maar kan zijn dat een aantal nodes we valt of er een aantal nieuwe bijkomen etc...

Dit algoritme lijkt niets anders te doen dan een hallo wie is daar ronde uit te voeren dan een van de andere nodes de groeten doen om vervolgens een willekeurige node lastig te gaan vallen.

Ik weet te weinig van dit soort netwerken af om te begrijpen of dit een goed idee is of niet maar het klinkt me heel erg inefficient in de oren ik zou eerder denken dat het handiger is om juist alleen de nodes in je directe omgeving op de hoogte te stellen van jouw gegevens als zij vervolgens het zelfde doen (wetende dat jij de data al naar nodes X, Y en Z gestuurd hebt) dan kunnen al deze nodes de data door sturen met de informatie dat zij deze gegevens al hebben. Zij hoeven dan niet door te sturen dat jij de data al hebt maar alleen dat zij de data al hebben en welke andere nodes zij dit naar toegestuurd hebben. Op die manier hoef je de hoeveelheid data niet te laten groeien en kun je er redeljik zeker van zijn dat je jouw eigen data niet terug krijgt.
Het probleem hier is dat je natuurlijk een bottleneck tegen kunt komen die de data maar heel langzaam naar de nodes om zich heen kan verspreiden iets dat er dus voor zorgt dat alle data in die richting van het netwerk vertraagt wordt.
Omdat er geen centraal beheer is is er niemand die dit op kan merken, en dus niemand die die hoek van het netwerk sneller van data zou kunnen voorzien.

Maar als je het random node idee combineert met dit idee en elke node stuurt niet alleen naar zijn buren maar ook naar 1 random node, dan kun je denk ik het probleem van de bottleneck die een deel van het netwerk in de weg zit voorkomen en de overhead laag houden de kans dat een node data ontvangt die deze node al heeft is er natuurlijk wel en hoe groter het netwerk hoe vaker het gebeurt, en hoe meer nodes de data al hebben hoe groter de kans. Aan de andere kant deze nodes zullen deze data niet verder sturen en neem ik aan bij aanvang van de transmissie al bedanken omdat zij de data al hebben en niet alles op nieuwe hoeven ontvangen.

Hoe dan ook het idee om steeds de hele topologie van het ontdekte netwerk mee te sturen want dat is wat dit MIT idee in feite doet lijkt me een zeer slecht idee. Omdat je zeker bij een groter netwerk een enorme overhead creëert die niets toevoegt en voor alle nieuwe data binnen het netwerk herhaald moet worden.

[still_the_same]

Niet om je te bashen, maar je vertelt dat je er eigenlijk niet veel van weet en vervolgens zeg je dat MIT, toch een uni waar veel erg slimme mensen rond dolen in jouw ogen een slecht idee hebben. Misschien je eerst verdiepen in de info, zodat je er wel veel van weet voordat je kritiek uit?

[Anoniem: 117071]

Juist omdat spelers dicht bij elkaar zitten is dit algoritme, maar eigenlijk een ad-hoc netwerk in het algemeen, niet interessant: de communicatie is maar 1-hop. Het algoritme wat hier beschreven is, wordt waarschijnlijk gebruikt om efficiënter te routen in een multi-hop netwerk waarin de topologie constant verandert.

Ad Hoc netwerken worden inderdaad nog niet op grote commerciële schaal toegepast maar een nichemarkt zou ik het ook niet willen noemen. Vooral binnen het leger is er grote belangstelling voor deze technologie en in de toekomst zal car-to-car communicatie een belangrijke toepassing van ad-hoc networking worden.

[Reactie gewijzigd door Anoniem: 117071 op 23 juli 2024 01:35]

[Garyu]

Dat zou ik een mesh-netwerk noemen, waar inderdaad (on)regelmatig nodes aan toegevoegd en verwijderd worden, en daardoor een constante netwerkarchitectuur niet mogelijk is.

Denk bijvoorbeeld aan de smart-meters die door bepaalde producenten worden gemaakt, en een mesh-netwerk gebruiken om gegevens via elkaar door te sturen tot ze een smart-meter vinden die een "echte" internetverbinding heeft, of inderdaad een basis-station.

Dit soort systemen zijn in principe ideaal als je weinig of geen basis-stations hebt, maar de netwerken zijn lastig in te richten en te managen en de efficientie is relatief laag. Lijkt me een goede zaak als hier onderzoeks-tijd aan besteed wordt! Gaming lijkt me hier niet echt de eerste doelgroep trouwens.

[Neut72]

Het belangrijke punt hier is dat "mesh-networking" in de komende jaren een enorme vlucht zal gaan maken. Uiteindelijk zullen we over een x aantal jaren allemaal gebruik maken van mesh-networking om op Internet te komen aangezien de voordelen van dergelijke 'provider-loze' netwerken die vele vierkante kilometers tegelijk kunnen afdekken enorm zijn.

Vooral de ontwikkelingen op het gebied van 'whitespace' zullen hier een grote bijdrage aan leveren.

Het is dus heel belangrijk dat er systemen worden gevonden om deze bottlenecks soepel te kunnen omzeilen.

[Aivy]

Nou ik ben niet helemaal mee ens dat ad hoc netwerk word niet veel verbruikt

ik maak het bijna elke dag gebruik van op school . voor all als je moet een project maken met meerdere personen is dat handig. je kan natuurlijk ook router gebruiken maar dat kan niet altijd. dus betere ad hoc algoritme is welkom

[ldegheest]

"Het door de MIT-onderzoekers ontwikkelde algoritme moet het mogelijk maken dat bottlenecks sneller worden bereikt"

Lijkt me toch een net niet de bedoeling ?

[Reactie gewijzigd door ldegheest op 23 juli 2024 01:35]

[analog_]

Jawel, een volle lijn, is een goed gebruikte lijn. Net zoals het concept van vrij 'ram' ook onzinnig is omdat leeg geheugen geen nut heeft voor de draaiende programma's. Je kan het beter zoveel mogelijk vol laten lopen.

[DLGandalf]

Volgens mij is ad hoc gewoon verzenden naar iemand anders zonder tussenkomst van een ander adhoc station. Dus het bereik gaat niet verder dan je eigen bereik.
Doe je dit wel mbv tussenstations, om zo je bereik te vergroten, dan heet het volgens mij een mesh netwerk

Volgens mij gaat dit artikel dan ook specifieker over mesh netwerken.

[Reactie gewijzigd door DLGandalf op 23 juli 2024 01:35]

[Johan van den Heuvel]

Zit de oplossing niet al in wireless network meshing?
http://en.wikipedia.org/wiki/Wireless_mesh_network

edit: ik zie net dat DLGandalf ook al over mesh network heeft

[Reactie gewijzigd door Johan van den Heuvel op 23 juli 2024 01:35]

[Johan van den Heuvel]

Ik zit een beetje te surfen over wireless netwerken en zie dat er van alles gaande is, daarbij vraag ik me gelijk af of wat het MIT nu aan het ontwikkelen is, niet al achterhaald is.

Bijv. hoe zit met Wi-FI Direct?
http://en.wikipedia.org/wiki/Wi-Fi_Direct

Ik vond ook nog andere artikelen over Wireless LAN's maar ik weet niet of ik dat mag posten.

Google bijv. op het volgende:
- Advances in Wireless LANS
- 60 GHz standardisation
- mesh network
:
Reactie op Tuxie: ik vermoed dat je een mesh network bedoeld?

[Reactie gewijzigd door Johan van den Heuvel op 23 juli 2024 01:35]

[sirdupre]

Ik vind het verwarrend dat er in het artikel gesproken wordt over een centrale entiteit die het netwerkverkeer regelt. Op internet is dat namelijk ook niet geval, en doet het Border Gateway Protocol (en andere gedistribueerde Dijkstra varianten) min of meer hetzelfde als in het artikel wordt beschreven - het doorsturen van informatie totdat alles bekend is bij iedereen. En ook deze algoritmen hebben gewoon technieken om bottlenecks te voorkomen, etc.

Grote verschil lijkt me dat elke node op het internet weet wat de topologie van zijn naaste omgeving is (je zit immers met draadjes aan elkaar vast). Bij ad-hoc netwerken is de situatie heel anders, en ik vermoed dat juist in die wazige topologie de echt grote uitdaging zit, maar daar wordt in dit artikel niet op ingegaan. Het feit dat er geen bronvermelding is (al is het maar de naam van een artikel), maakt ook nog eens dat ik niet kan nalezen hoe de vork nu echt in de steel zit.

[Luukje01]

bandbreedte is tegenwoordig toch genoeg. en als dan een bottleneck verhopen kan geworden. ideaal.

het is of een trage bottleneck of meer paktjes versturen, wat in paktijk sneller is (tests!)

[Reactie gewijzigd door Luukje01 op 23 juli 2024 01:35]

[Anoniem: 16536]

Bottleneck en bandbreedte kunnen in dit onderwerp ook wel aan elkaar gekoppeld zijn hoor.

Als er een node tussen zit die een erg trage interface heeft (een enkele 802.11B node in een verder G netwerk) is hij door zijn beperkte bandbreedte ook meteen de bottleneck.

Verder vind ik het jammer dat er in dit artikel niet wordt verklaard wat dan precies de bottlneck is, wat voor soort vertragingen er dan plaatsvinden, en hoe het systeem nu dan precies werkt.

Het artikel haalt zelf al aan dat Ad-Hoc netwerken niet veel gebruikt worden. Althans, niet actief. Het gebruik in gaming-handhelds en dergelijke is passief omdat alles voor je geregeld wordt.

[TDeK]

Een ander punt van zorg lijkt me privacy, aangezien ik hier lees dat elke node precies weet wat een andere node heeft ontvangen. Bij een Freenet doen ze het juist precies andersom en delen ze zo min mogelijk met de aangrenzende nodes. Maar goed, dat project heeft ook een heel ander uitgangspunt.

[ThorX]

Wat is de bron van dit artikel?

[foliant]

http://web.mit.edu/newsof...ing-bottlenecks-0111.html

Zo moeilijk is googelen toch niet?

[ericcgg]

Veel gezeur over gebruik. Belangrijk is dat je geen egoïstische gebruikers(selfish nodes) hebt. Want waarom zou ik het pakketje van mijn buurman versturen. Kost mij energy en rekenkracht.