Směrování v malém světě - Small-world routing

v teorie sítí, směrování malého světa odkazuje na metody směrování pro sítě malého světa. Sítě tohoto typu jsou zvláštní v tom, že mezi libovolnými dvěma uzly existují relativně krátké cesty. Určení těchto cest však může být obtížným problémem z pohledu jednotlivého směrovacího uzlu v síti, pokud nejsou známy žádné další informace o síti jako celku.

Chamtivé směrování

Téměř každé řešení problému směrování v malém světě zahrnuje použití chamtivý směrování. Tento druh směrování závisí na relativním referenčním bodě, kterým si každý uzel v cestě může vybrat další uzel, o kterém se domnívá, že je nejblíže cíli. To znamená, že musí existovat něco, na čem by měl být chamtivý. Může to být například zeměpisná poloha, adresa IP atd. V případě Milgramův originální experiment v malém světě, účastníci znali polohu a zaměstnání konečného příjemce, a proto mohli na základě těchto parametrů přeposílat zprávy.^{[Citace je zapotřebí ]}

Vytvoření referenční základny

Chamtivé směrování nebude snadno fungovat, pokud neexistuje zřejmá referenční základna. K tomu může dojít například v překryvné sítě kde nejsou k dispozici informace o umístění cíle v podkladové síti. Přítel-přítel konkrétním příkladem tohoto problému jsou sítě. V takových sítích je důvěra zajištěna skutečností, že znáte pouze základní informace o uzlech, se kterými jste již sousedem.^{[Citace je zapotřebí ]}

Jedním z řešení v tomto případě je zavedení nějakého umělého adresování na uzly takovým způsobem, aby bylo možné toto adresování efektivně využít metodami chamtivého směrování. A Papír 2005 vývojář Projekt Freenet popisuje, jak toho lze dosáhnout v přítel příteli sítí. Vzhledem k předpokladu, že tyto sítě vykazují vlastnosti malého světa, často jako výsledek vztahů v reálném světě nebo známých, by mělo být možné obnovit vložený Kleinberg graf malého světa. Toho je dosaženo výběrem náhodných párů uzlů a jejich potenciálním prohozením na základě Objektivní funkce který minimalizuje součin všech vzdáleností mezi daným uzlem a jeho sousedy.^{[Citace je zapotřebí ]}

Důležitým problémem spojeným s tímto řešením je možnost místní minima. K tomu může dojít, pokud jsou uzly v situaci, která je optimální pouze s ohledem na místní sousedství, zatímco ignoruje možnost vyšší optimality vyplývající ze swapů se vzdálenými uzly. Ve výše uvedeném příspěvku autoři navrhli a simulované žíhání metoda, kde byly s malou pravděpodobností provedeny méně než optimální swapy. Tato pravděpodobnost byla úměrná hodnotě výroby přepínačů. Další možný metaheuristické metoda optimalizace je a tabu vyhledávání, který přidává paměť rozhodnutí o výměně. Ve své nejjednodušší podobě je pamatována omezená historie minulých swapů, takže budou vyloučeny ze seznamu možných uzlů swapu.^{[Citace je zapotřebí ]}

Tuto metodu pro konstrukci referenční základny lze také přizpůsobit distribuovaným nastavením, kde lze rozhodovat pouze na úrovni jednotlivých uzlů, kteří nemají žádnou znalost celkové sítě. Ukazuje se, že jedinou nezbytnou úpravou je metoda výběru párů náhodných uzlů. V distribuovaném nastavení se to provádí tak, že každý uzel pravidelně odesílá a náhodný chodec končí na uzlu, který má být považován za swap.^{[Citace je zapotřebí ]}

Kleinbergův model

Kleinbergův model sítě účinně demonstruje účinnost chamtivého směrování malého světa. Model používá síť n x n uzlů k reprezentaci sítě, kde je každý uzel připojen neorientovanou hranou k sousedům. Abychom tomu dodali efekt „malého světa“, je do sítě přidána řada hran s dlouhým dosahem, které mají sklon upřednostňovat uzly blíže vzdálenosti, nikoli dál. Při přidávání hran je pravděpodobnost připojení nějakého náhodného vrcholu ${displaystyle v}$ k jinému náhodnému vrcholu w je úměrný ${displaystyle 1 / d (v, w) ^ {q}}$, kde ${displaystyle q}$ je shlukovací exponent.^[1]

Chamtivé směrování v Kleinbergově modelu

Je snadné vidět, že a chamtivý algoritmus, bez použití hran s dlouhým dosahem, lze navigovat z náhodných vrcholů ${displaystyle v-> w}$ na mřížce v ${displaystyle O (n)}$ čas. Sledováním zaručeného spojení s našimi sousedy můžeme přesouvat jednu jednotku po druhé ve směru našeho cíle. To je také případ, kdy klastrování komponent ${displaystyle q}$ je velký a okraje „dlouhého dosahu“ zůstávají velmi blízko; jednoduše nevyužíváme výhod slabších vazeb v tomto modelu. Když ${displaystyle q = 0}$, hrany dlouhého dosahu jsou rovnoměrně spojeny náhodně, což znamená, že hrany dlouhého dosahu jsou „příliš náhodné“, aby mohly být efektivně použity pro decentralizované vyhledávání. Kleinberg ukázal, že optimální shlukovací koeficient pro tento model je ${displaystyle q = 2}$nebo inverzní čtvercové rozdělení.^[2]

Důvod, proč tomu tak je, je-li kolem počátečního uzlu nakreslen kruh o poloměru r, bude mít hustotu uzlu ${displaystyle n / (pi r ^ {2})}$ kde n je počet uzlů v kruhové oblasti. Jak se tento kruh dále rozšiřuje, úměrně se zvyšuje počet uzlů v dané oblasti ${displaystyle r ^ {2}}$ protože pravděpodobnost náhodného spojení s jakýmkoli uzlem zůstává proporcionální ${displaystyle 1 / r ^ {2}}$, což znamená, že pravděpodobnost, že původní uzel bude mít slabý vztah s jakýmkoli uzlem v dané vzdálenosti, je účinně nezávislá na vzdálenosti. Proto se dospělo k závěru, že s ${displaystyle q = 2}$, hrany dlouhého dosahu jsou rovnoměrně rozloženy na všechny vzdálenosti, což je efektivní pro to, že nás necháme trychtýřem do našeho konečného cíle.^{[Citace je zapotřebí ]}

Některé strukturované systémy Peer-to-peer založené na DHT často implementují varianty Kleinbergovy topologie Small-World, aby umožnily efektivní směrování v síti Peer-to-peer s omezeným počtem uzlů.^[3]

Viz také

• Sociální síť - Sociální struktura tvořená souborem sociálních aktérů
• Síť malého světa - Matematický graf, kde lze dosáhnout většiny uzlů v malém počtu kroků
• Watts-Strogatzův model

Reference