Skalbar källrouting
Scalable Source Routing (SSR) är ett routingprotokoll för ostrukturerade nätverk som mobila ad hoc-nätverk , mesh-nätverk eller sensornätverk . Den kombinerar källrouting med routing längs en virtuell ring, och är baserad på idén att "skjuta in Chord i underlaget".
Begrepp
Virtuell ring
SSR arbetar på ett platt adressutrymme som är organiserat som en virtuell ring. Detta är ett populärt koncept i peer-to-peer- överlagringsnätverk som Chord . Den gemensamma kunskapen om ringstrukturen gör det möjligt för noder att dirigera paket utan att känna till topologin för det underliggande fysiska nätverket. Även om det fysiska nätverket kan vara mycket dynamiskt, förblir den virtuella ringens struktur ganska statisk. Därför kan översvämning av det fysiska nätverket undvikas.
Paket färdas längs ringen så att de minskar det virtuella avståndet till destinationen (det vill säga den absoluta skillnaden mellan adresserna). När varje nod känner till sin rätta föregångare och efterföljare i den virtuella ringen garanteras leverans till rätt mottagande nod. Ringen sägs vara konsekvent .
Ofta antas routing ha en definierad orientering i ringen, men det är bara en hjälp för att förenkla teorin. I praktiken är detta inte nödvändigt och till och med skadligt för prestandan.
Fingertabellen i Chord , som ger genvägar i den virtuella ringen , ersätts av en ruttcache.
Källa routing
I det fysiska nätverket använder SSR källrouting . Relänoder cachelagrar opportunistiskt den korsade delen av källrutten för ett givet paket. Detta underlättar insamlingen av routinginformation samtidigt som det förhindrar nedsmutsning av nodernas ruttcacher med föråldrad information.
Ruttaggregation
En nod behöver inte ha den fullständiga sökvägen till destinationen i sin ruttcache för att använda en cachelinje. Istället dirigeras meddelandet till den fysiska närmaste noden som gör framsteg i den virtuella ringen. När meddelandet kommer till denna mellannod lägger den noden till information från sin ruttcache till källrutten. Detta steg upprepas vid behov. När meddelandet anländer till slutdestinationen, efter vägoptimering (med användning av Dijkstras algoritm ) skickas ett ruttuppdateringsmeddelande till ursprungsnoden, vilket uppdaterar ursprungsruttcachen. Denna teknik underlättar användningen av ruttcacher med fast storlek, vilket begränsar tillståndet per nod och gör SSR till ett genomförbart alternativ för miljöer med lågt minne.
Distributed Hash Table (DHT) funktionalitet
Även om SSR är ett komplett routingprotokoll (jfr OSI-modellens nätverkslager ) , tillhandahåller det också semantiken för en distribuerad hashtabell . Detta reducerar overheaden till att ha ett överlagringsprotokoll ovanpå ett traditionellt routningsprotokoll och påskyndar kraftigt uppslagsoperationer i MANETs som annars skulle förlita sig på flooding , förutsatt att applikationen stöder (eller modifieras för att stödja) nyckelbaserad routing . Den tillhandahållna DHT-funktionaliteten kan också användas för att implementera skalbara nätverkstjänster i frånvaro av servrar.
Algoritmöversikt
Bootstrapping (starta nätverket)
Varje nod sänder med jämna mellanrum ett "hej"-meddelande till sina fysiska grannar och meddelar grannarna om dess existens. "Hej"-meddelanden inkluderar en lista över de fysiska grannarna till varje nod. Om noden finner sig själv inkluderad i "hej"-meddelandet från en annan nod, antar den en dubbelriktad anslutning och lägger till den andra noden till sin lista över fysiska peers (för att senare använda dem för routing).
Noden skickar också ett "grannemeddelande" till sin antagna efterträdare för att gå med i den virtuella ringen. Om den kontaktade noden upptäcker att den inte är rätt efterträdare, svarar den med ett meddelande som innehåller dess bästa gissning för efterträdaren till den frågande noden. Detta upprepas tills rätt virtuella grannar hittas. (För en detaljerad beskrivning av denna process, kallad ISPRP, se. Ett annat sätt att bootstrapping är linjärisering.)
Routing
När en nod dirigerar ett meddelande
- det ser ut i sin ruttcache. Om det finns en rutt till destinationen används den.
- och ingen rutt till destinationen är känd, dirigerar noden meddelandet till en praktiskt taget nära föregångare till destinationen. Denna mellannod upprepar sedan routingprocessen.
- och nodens ruttcache innehåller ännu inte en matchande rutt, som en reserv överlämnar noden meddelandet till sin efterträdare i den virtuella ringen. Den virtuella efterträdaren kanske inte är fysiskt nära noden, men bootstrapping-processen borde ha etablerat en väg till den. När detta reservsteg upprepas, färdas meddelandet längs ringen och når så småningom destinationen eller får timeout.
Klassificering
SSR har reaktiva såväl som proaktiva komponenter, vilket gör det till ett hybrid routingprotokoll. Virtual Ring Routing är konceptuellt lika, den största skillnaden är användningen av källrouting i SSR jämfört med att bygga upp per-nodstillstånd (routingtabeller) i VRR.
Fördelar
- Budskapseffektiv: Endast lokala sändningar, inga globala översvämningar.
- Lågt minnesbehov. Litet och begränsat tillstånd per nod.
- DHT-funktionalitet kan påskynda uppslagningar eller användas för att bygga en serverlös infrastruktur.
Nackdelar
- De hittade rutterna kan vara längre än nödvändigt.
- Källvägarna lägger till rubrikstorleken på meddelandena. Det blir alltså mindre utrymme kvar för nyttolasten.
Se även
- Lista över ad hoc routingprotokoll
- Virtuell ringdirigering
- Mesh-nätverk
- Trådlöst mesh-nätverk
- Mobilt ad hoc-nätverk
externa länkar