Škálovatelné směrování zdroje - Scalable Source Routing

Škálovatelné směrování zdroje (SSR) je a směrovací protokol pro nestrukturované sítě, jako je mobilní sítě ad hoc, síťové sítě nebo senzorové sítě. Kombinuje to směrování zdroje se směrováním po virtuálním kruhu a je založen na myšlence „tlačit Akord do podložky ".[1]

Koncepty

Virtuální prsten

SSR pracuje na plochém adresním prostoru, který je organizován jako virtuální kruh. Toto je populární koncept v peer-to-peer překryvné sítě jako Akord. Společné znalosti o kruhové struktuře umožňují uzlům směrovat pakety bez znalosti topologie podkladové fyzické sítě. Zatímco fyzická síť může být velmi dynamická, struktura virtuálního kruhu zůstává spíše statická. Proto, záplavy fyzické síti se lze vyhnout.

Pakety cestují po kruhu tak, že zmenšují virtuální vzdálenost k cíli (tj absolutní rozdíl adres). Když každý uzel zná svého správného předchůdce a následníka ve virtuálním kruhu, je zaručeno doručení správnému přijímajícímu uzlu. Prsten je prý konzistentní.

Často se předpokládá, že směrování má definovanou orientaci v kruhu, ale to je jen pomůcka ke zjednodušení teorie. V praxi to není nutné a dokonce škodlivé pro výkon.

The prstový stůl v Akord, který poskytuje zkratky ve virtuálním kruhu, je nahrazen mezipamětí trasy.

Směrování zdroje

Ve fyzické síti využívá SSR směrování zdroje. Přenosové uzly příležitostně ukládají do mezipaměti projetou část zdrojové trasy daného paketu. To usnadňuje shromažďování informací o směrování a zároveň inhibuje znečišťující mezipaměti tras uzlů se zastaralými informacemi.

Agregace trasy

Uzel nemusí mít ve své mezipaměti trasy úplnou cestu k cíli, aby mohl použít linku mezipaměti. Místo toho je zpráva směrována směrem k fyzickému nejbližšímu uzlu, který dělá pokrok ve virtuálním kruhu. Když zpráva dorazí do tohoto mezilehlého uzlu, přidá tento uzel informace ze své mezipaměti trasy ke zdrojové trase. Tento krok se podle potřeby opakuje. Když zpráva dorazí do konečného cíle, po optimalizaci cesty (pomocí Dijkstrův algoritmus ) do uzlu původce se odešle zpráva o aktualizaci trasy, čímž se aktualizuje mezipaměť trasy původce. Tato technika usnadňuje použití mezipaměti trasy s pevnou velikostí, což omezuje stav jednotlivých uzlů a činí SSR životaschopnou volbou pro prostředí s nízkou pamětí.[2]

Funkce distribuované tabulky hash (DHT)

Zatímco SSR je kompletní směrovací protokol (srov. OSI model je síťová vrstva ), poskytuje také sémantiku a distribuovaná hash tabulka. To snižuje režijní náklady na to, že bude mít overlay protokol navíc k tradičnímu směrovací protokol a výrazně urychluje vyhledávací operace ve Windows MANETY na které by se jinak spolehli záplavy,[3][4] za předpokladu, že aplikace podporuje (nebo je upravena tak, aby podporovala) klíčové směrování. Poskytovanou funkci DHT lze také použít k implementaci škálovatelných síťových služeb při absenci serverů.[5]

Přehled algoritmů

Bootstrapping (spuštění sítě)

Každý uzel pravidelně vysílá zprávu „ahoj“ svým fyzickým sousedům a upozorňuje sousedy na jejich existenci. „Ahoj“ zprávy obsahují seznam fyzických sousedů každého uzlu. Pokud se uzel ocitne ve zprávě „ahoj“ jiného uzlu, předpokládá obousměrné připojení a přidá druhý uzel do seznamu fyzických vrstevníků (pro pozdější použití pro směrování).

Uzel také odešle zprávu „oznámení souseda“ svému předpokládanému nástupci, aby se připojil k virtuálnímu kruhu. Pokud kontaktovaný uzel zjistí, že se nejedná o správného nástupce, odpoví zprávou obsahující nejlepší odhad nástupce dotazujícího se uzlu. To se opakuje, dokud se nenajdou správní virtuální sousedé. (Podrobný popis tohoto procesu zvaného ISPRP viz.[6] Dalším způsobem bootstrappingu je linearizace.[7])

Kresba virtuálního kruhu (horní polovina) a grafu fyzické sítě (dolní polovina)
SSR: Směrování bez zaplavení. Uzel 1 směrování zprávy přes uzel 17, 32, 39 do cílového uzlu 42 (podrobný popis viz [1]).

Směrování

Když uzel směruje zprávu

  1. vypadá ve své mezipaměti trasy. Pokud existuje trasa do cíle, použije se.
  2. a není známa žádná trasa do cíle, uzel směruje zprávu k prakticky blízkému předchůdci cíle. Tento mezilehlý uzel poté opakuje proces směrování.
  3. a mezipaměť trasy uzlu ještě neobsahuje odpovídající trasu, protože jako záložní uzel předá zprávu svému nástupci ve virtuálním kruhu. Virtuální nástupce nemusí být fyzicky blízko uzlu, ale proces bootstrappingu by měl k němu vytvořit cestu. Jak se tento záložní krok opakuje, zpráva cestuje po kruhu, nakonec dosáhne cíle nebo vyprší časový limit.

Klasifikace

SSR má reaktivní stejně jako proaktivní komponenty, což z něj dělá hybridní směrovací protokol. Směrování virtuálního kruhu je koncepčně podobný, největším rozdílem je použití směrování zdroje v SSR ve srovnání s vybudováním stavu podle uzlu (směrovací tabulky) ve VRR.

Výhody

  • Efektivní pro zprávy: Pouze místní vysílání, žádné globální záplavy.
  • Nízké nároky na paměť. Malý a omezený stav na uzel.
  • Funkce DHT může urychlit vyhledávání nebo se může použít k vybudování infrastruktury bez serveru.

Nevýhody

  • Nalezené trasy mohou být delší, než je nutné.
  • Zdrojové trasy zvyšují velikost záhlaví zpráv. Na užitečné zatížení tak zbývá méně místa.

Viz také

Reference

  1. ^ A b Fuhrmann, Thomas; Pengfei Di; Kendy Kutzner; Curt Cramer (červen 2006). „Strčení akordu do podkladu: škálovatelné směrování pro hybridní MANETY“ (PDF). System Architecture Group, Technical University of Karlsruhe (TH), Germany. Citováno 15. dubna 2010. Citovat deník vyžaduje | deník = (Pomoc)
  2. ^ Fuhrmann, Thomas (květen 2005). "Schéma samoorganizace směrování pro náhodné sítě". SÍŤOVÁNÍ 2005 (PDF). Přednášky z informatiky. 3462/2005. Springer Berlin / Heidelberg. str. 1366–1370. doi:10.1007/11422778_116. Citováno 15. dubna 2010.
  3. ^ Castro, Marcel C .; Andreas J. Kassler; Carla-Fabiana Chiasserini (březen 2010). „Překrytí typu peer-to-peer v mobilních sítích ad hoc“. Příručka sítí peer-to-peer. Springer Verlag. str. 1045–1080. doi:10.1007/978-0-387-09751-0_37. ISBN  978-0-387-09750-3.
  4. ^ Zahn, Thomas; Greg O'Shea; Antony Rowstron (2009). „Empirická studie povodní v sítích mesh“ (PDF). SIGMETRICS Proveďte. Eval. Rev. ACM. 37 (2): 57–58. doi:10.1145/1639562.1639584. Citováno 16. dubna 2010.
  5. ^ Caesar, Matthew; Edmund B. Slavík; Greg O'Shea; Antony Rowstron (září 2006). „Virtual Ring Routing: Network routing Inspired by DHTs“ (PDF). Recenze počítačové komunikace SIGCOMM. ACM. 36 (4): 351–362. doi:10.1145/1151659.1159954. Citováno 16. dubna 2010.
  6. ^ Cramer, Curt & Fuhrmann, Thomas (31. ledna 2005). „Samostabilizační kruhové sítě na připojených grafech“ (PDF). Citováno 26. dubna 2010. Citovat deník vyžaduje | deník = (Pomoc)
  7. ^ Kendy Kutzner a Thomas Fuhrmann (březen 2007). „Využití linearizace pro globální konzistenci v SSR“ (PDF). Sborník ze 4. Int. Workshop IEEE o aktuálních tématech v systémech P2P. Citováno 20. dubna 2010.

externí odkazy