Schaalbare Source Routing

Schaalbare Source Routing is een routing protocol voor ongestructureerde netwerken zoals mobiele ad hoc netwerken, mesh-netwerken of sensornetwerken. Het combineert de bron routing met routing langs een virtuele ring, en is gebaseerd op het idee van "duwen Chord in de onderlaag".

Concepten

Virtual ring

SSR werkt op een vlakke adresruimte die is georganiseerd als een virtueel ring. Dit is een populaire concept in de peer-to-peer-overlay-netwerken zoals Chord. De gemeenschappelijke kennis over de ringstructuur maakt knooppunten om pakketten zonder de topologie van het onderliggende fysieke netwerk. Terwijl het fysieke netwerk zeer dynamisch zijn, de structuur van de virtuele ring blijft vrij statisch. Daarom overstromingen het fysieke netwerk kan worden vermeden.

Pakketten zich langs de ring zodat ze verminderen de virtuele afstand naar de bestemming. Bij elk knooppunt weet de juiste voorganger en opvolger in de virtuele ring, wordt de levering aan de juiste ontvangende knooppunt gegarandeerd. De ring wordt gezegd consistent.

Vaak wordt routing verondersteld een gedefinieerde oriëntatie in de ring hebben, maar dat is slechts een hulp voor theorie vereenvoudigen. In de praktijk is dit niet noodzakelijk en zelfs schadelijk voor prestaties.

De vinger tafel in Chord, die snelkoppelingen in de virtuele ring biedt, wordt vervangen door een route cache.

Source routing

In het fysieke netwerk maakt gebruik van SSR bron routing. Doorgeven knooppunten opportunistisch cache het doorlopen deel van de bron route van een bepaald pakket. Dit vergemakkelijkt het verzamelen van de route-informatie, terwijl het remmen van vervuilende route caches de knooppunten 'met verouderde informatie.

Route aggregatie

Een knooppunt hoeft niet het volledige pad naar de bestemming in de route cache te maken van een cache-lijn te maken. In plaats daarvan wordt de boodschap gerouteerd naar de fysieke dichtstbijzijnde knooppunt dat vooruitgang in de virtuele ring maakt. Als het bericht aankomt in deze tussenliggende knooppunt dat knooppunt voegt informatie van de route cache de bronroute. Deze stap wordt herhaald als nodig is. Wanneer het bericht aankomt op de eindbestemming, na optimalisering van de vliegroute van een routeactualiseringsbericht wordt verzonden naar de opdrachtgever knooppunt, waardoor het updaten van de grondleggers route cache. Deze techniek maakt het gebruik van vaste grootte route caches, die de per-node staat beperkt en maakt SSR een haalbare optie voor weinig geheugen omgevingen.

Distributed Hash Table functionaliteit

Terwijl SSR is een complete routing protocol, het biedt ook de semantiek van een gedistribueerde hash tafel. Dit reduceert de overhead die een overlay protocol op een traditionele routing protocol en sterk versnelt lookup behandelingen Manets die anders afhankelijk overstromingen, mits de applicatie ondersteunt sleutelgebaseerde routing. De DHT-functionaliteit ook kunnen worden gebruikt voor de uitvoering schaalbare netwerkdiensten in afwezigheid van servers.

Algoritme overzicht

Bootstrapping

Elk knooppunt zendt periodiek een "hello" bericht naar de fysieke buren, een kennisgeving aan de buren van zijn bestaan. "Hello" berichten bevatten een lijst van de fysieke buren van elk knooppunt. Wanneer het knooppunt zich bevindt in het "Hello" bericht van een ander knooppunt, veronderstelt een bidirectionele verbinding, en voegt het andere knooppunt aan de lijst van fysische peers.

Het knooppunt stuurt ook een "buurman melding" bericht naar de veronderstelde opvolger, naar de virtuele ring te sluiten. Indien de gecontacteerde knooppunt detecteert dat het niet de juiste opvolger, antwoordt met een bericht met daarin de beste schatting voor de opvolger van de onderzoekende knooppunt. Dit wordt herhaald totdat de juiste virtuele buren worden gevonden.

Routing

Wanneer een knooppunt routes een bericht

  • het ziet er in de route cache. Als een route naar de bestemming bestaat, wordt gebruikt.
  • en geen route naar de bestemming bekend is, het knooppunt routeert het bericht naar een vrijwel nauwe voorloper van de bestemming. Deze tussenliggende knooppunt herhaalt vervolgens de routing proces.
  • en route cache van het knooppunt nog niet bevatten een bijpassende route, als een fallback het knooppunt overhandigt het bericht naar zijn opvolger in de virtuele ring. De virtuele opvolger niet fysiek dicht bij het knooppunt, maar het bootstrap proces moet een route te zijn vastgesteld. Aangezien dit fallback stap wordt herhaald, de boodschap reist langs de ring, uiteindelijk het bereiken van de bestemming of wordt een time-out.

Classificatie

SSR heeft reactief en proactief componenten, waardoor het een hybride routing protocol. Virtual Ring Routing is conceptueel vergelijkbaar, het grootste verschil is het gebruik van de bron routing in SSR in vergelijking met de opbouw per node staat in VRR.

Voordelen

  • Message-Efficient: Alleen lokale uitzendingen, geen wereldwijde overstromingen.
  • Weinig geheugen eis. Kleine en beperkte staat per node.
  • DHT functionaliteit kan lookups versnellen of te worden gebruikt om een ​​server-minder-infrastructuur te bouwen.

Nadelen

  • De routes gevonden kan langer dan nodig zijn.
  • De bron routes toevoegen headergrootte van de berichten. Aldus wordt minder ruimte voor de lading.
(0)
(0)
Commentaren - 0
Geen commentaar

Voeg een reactie

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tekens over: 3000
captcha