PB165 - Grafy a sítě 11. Zajímavé grafy a peer to peer sítě Obsah přednášky • Náhodné grafy • Náhodné geometrické grafy • Power-law sítě • Peer to peer sítě • Prohledávání v nestrukturovaných sítích • Strukturované sítě • Chord Náhodné grafy (Erdôs-Renyi) • Pravděpodobnostní modely grafů Definice G (n, p) model náhodného grafu: Mějme graf s n vrcholy, pak neorientovaná hrana vznikne mezi dvojicí vrcholů s pravděpodobností p, nezávisle na ostatních dvojicích uzlů. Q • Pravděpodobnost, že graf G má k hran je dána výrazem p\l - pp-k • Pravděpodobnost, že graf G E G(n,p) obsahuje k hran má binomiální rozložení Prahy náhodných grafů Věta Mějme model náhodného grafu G(n,p) a nechť p = c-2^. Je-li c > 1, pak prakticky všechny grafy nemají izolované (nespojené) vrcholy Je-li c < 1, pak prakticky všechny grafy mají alespoň jeden izolovaný vrchol. Důkaz si pouze naznačíme: • Nechť X je počet izolovaných vrcholů v grafu G e G{n,p). • Pak horní hranice E[X] = n(l - p) 1, tedy počet izolovaných vrcholů se blíží 0. • Naopak, pro c < 1 se E[X] blíží nekonečnu, a tedy pravděpodobnost, že graf G nemá izolovaný uzel, se Náhodné geometrické grafy Definice Rozhoďme n bodů náhodně na jednotkovou síť. Náhodný geometrický graf G(n, r) má n uzlů odpovídající n bodům a dva uzly jsou spojeny hranou pokud jsou ve vzdálenosti menší nebo rovné r. Vzdálenost mezi dvěma body u = (xi,yi) a v = (x2,y2) je definována jako d(u, v) = max(|xi - x2|, |yi - y2|). Jedná se o oblíbený model senzorových sítí. Věta Pokud r > ^fi", kde c je konstanta > 4, pak G(n, r) je asymptoticky prakticky určitě souvislý graf, tj. PravděpodobnostiG(n, r) je souvislý graf) se blíží 1 jak se n blíží nekonečnu. Důkaz je naznačen dále: • Rozdělme jednotkovou síť na schránky velikosti r/2 x r/2. Počet přihrádek je 4/r2 (r < 1). • G(n,r) je souvislé, pokud žádná přihrádka není prázdná. • Nechť r = \Jcio*n, pak pravděpodobnost, že přihrádka je prázdná je menší nebo rovna n~c/4. • Nechť X je počet prázdných přihrádek. Pak E[X] < n1 c/\ tj. E[X] se blíží nule, pokud c> 4. • Pravděpodobnost^ > 0) < E[X] ->0á^ Power-law grafy Definice Power law je jakýkoliv polynomiální vztah, který nezávisí na měřítku. Pro dvě proměnné se nejčastěji vyjadřuje vztahem f(x) = axk + o{xk) kde a a k jsou konstanty a o(xk) je asymptoticky malá (tj. zanedbatelná) funkce x. Pro reálné sítě platí následující empirické tvrzení: Distribuce stupně vrcholu sítě sleduje power law, tj. počet vrcholů stupně k je ck /3. Příklady: • Internet a WWW: 13 = 2,1 • Sociální sítě (např. citační grafy): (3 = 3 • Biologické sítě (grafy interakce proteinů): (3 = 2,5 Většina grafů reprezentujících reálný svět má (3dE> (<1^4 Prohledávání v nestrukturovaných sítích Máme rozsáhlou síť (graf), každý uzel nese nějaká data. Jak najdeme hledaná data? • Centrální index • Napster • Snadné, ale neškáluje (Google má > 100.000 serverů) • Decentralizované o Gnutella: Primitivní hledání: záplava • Chytřejší algoritmy Základ výzkumu v oblasti peer to peer (P2P) sítí Srovnání komunikační struktury Překryvové sítě & P2P • P2P síť je typicky „virtuální" síť utvořená nad existující síťovou infrastrukturou (např. nad sítí Internet) • překryvová síť je využita pro indexování a zjišťování sousedů (peerů) => P2P systém je tak nezávislý na topologii (základové) fyzické sítě • vlastní data jsou obvykle přenášena po fyzické síti • nový peer musí za účelem připojení se k P2P síti získat informaci o nejméně jednom jejím členovi • nezbytné síťové informace: IP adresa, port, atd. • informace o dalších peerech mohou být získány od něj řekryvová vs. fyzická (základ ryvová vs. fyzická (základová) síť. Základní členění P2P systémů P2P Architecture Obrázek: Základní členění P2P systémů. Centralizované P2P systémy: Peer A zasílá dotaz na seznam uzlů mající požadovaná data centrálnímu serveru. Jakmile uzel A od centrálního serveru získá požadovaný seznam uzlů splňujících jeho požadavky (tj. např. uzly B a C), provádí vlastní komunikaci „napřímo", tj. bez intervence centrálního serveru. která jsou uložena na peeru D a peeru H) Požadavek je broadcastován všem sousedům peera A, poté všem jejich sousedům, atd., až je doručen všem peerům v P2P síti. Hybridní P2P systémy: Požadavek na vyhledání určité informace je nejprve směrován na tzv. superpeer (ultrapeer) uzel nadřazený dotazujícímu se uzlu; daný uzel ve spolupráci s ostatními superpeer uzly vyhledá uzel, který požadovaná data spravuje, a dotazující se uzel na něj přesměruje. smerovaní zpráv/požadavků je jednou z klíčových operací P2P systému pro nalezení požadovaných zdrojů by měl být každý peer schopen přeposlat daný požadavek svému sousedovi, který je blíže cílovému uzlu —>• návrh vhodných směrovacích protokolů je jedním z nejvíce zkoumaných témat v oblasti P2P systémů klíčovou vlastností představených směrovacích schémat je množství dat (resp. metadat) spravovaných jednotlivými uzly P2P sítě r + způsob organizace daných informací žádná metadata => neexistuje žádná jiná cesta pro vyhledání požadované informace než záplava/broadcast požadavku skrze celou síť feet information (Napster-like) I No information! (Gnutella-like)l I Istructured Unstructured! iSetLocftitle", N4) |Publisher@N4 Key="title" Value=file data. N- Nc N- ^^Oient Lookupftitle") Jednoduché, avšak na jediném (centrálním) uzlu musí být spravováno O(n) stavových informací; centrální uzel je navíc tzv. single point of failure. Směrování v nestrukturovaných P2P sítích • každý peer typicky spravuje své vlastní (uložené) datové objekty a linky/spojení ke svým sousedům • nový uzel pouze kontaktuje nějaký již připojený uzel a zkopíruje si linky k jeho sousedům, čímž si ustaví množinu svých sousedů • (která je následně spravována nezávisle na původně kontaktovaném uzlu) • => žádný z peerů nemá globální znalost o umístění datových objektů v síti • vyhledávání probíhá formou záplavy (flooding, broadcasť) • pro zmírnění problému záplavy sítě vyhledávacími dotazy je ke každému dotazu připojena hodnota TTL (Time-To-Live), po jejímž vypršení je dotaz zahozen • výzvou pro vyhledávací strategie pak je, jak optimalizovat zpracování dotazu v rámci omezeného množství vyhledávacích kroků (omezeno hodnotou TTL) 9 navrženo mnoho technik pro vyhledávání v nestrukturovaných P2P sítích: • Prohledávání do šířky (Breadth-First Search, BFS) - e.g., Gnutella • Prohledávání do hloubky (Depth-First Search, DFS) - e.g., FreeNet • Heuristické směrovací strategie Heuristické směrovací strategie Postupné vnořování (Iterative Deepening) • idea: • každý dotaz je prováděn sekvencí několika tradičních BFS prohledávání s postupným zvětšováním prohledávacího dosahu • proces vyhledávání je ukončen bud' nalezením výsledku nebo dosažením maximální možné hloubky prohledávání • detaily algoritmu: • specifikací systémové politiky P je určeno množství a hloubka jednotlivých vyhledávacích iterací • P = Di, D2,..., D„, kde Di < D2 < ... < D„ • na základě této politiky vysílá zdrojový uzel nejprve vyhledávací dotaz (s využitím techniky BFS) s hloubkou hledání Di • jakmile je nalezen odpovídající výsledek, je vyhledávání ukončeno • jinak zdrojový uzel vysílá nový vyhledávácí dotaz (se stejným identifikátorem), nyní však s hloubkou BFS prohledávání D2 • uzly, které se nachází blíže než Di-skoků od zdrojového uzlu tento dotaz pouze přeposílají svým sousedům (již jej nezpracovávají) • dále vzdálené uzly dotaz zpracovávají stejně, jako byl zpracováván v první iteraci • podobně pro D3, D4, atd. • pokud není dotaz zodpovězen do hloubky D„, je prohledávání ukončeno s negativním výsledkem hledání Heuristické směrovací strategie Řízené BFS a Inteligentní prohledávání I. • idea: • při tradičním BFS přeposílá každý z uzlů daný dotaz všem svým sousedům • při Řízeném BFS (Directed BFS) posílá každý z uzlů dotaz pouze podmnožině svých sousedů • klíčovou vlastností daného směrovacího algoritmu je inteligentní výběr „vhodných" sousedů, u kterých existuje předpoklad možného zodpovězení daného dotazu • detaily k výběru sousedů: • každý z uzlů si spravuje určité statistiky o svých sousedech: počet dříve zodpovězených dotazů skrze daného souseda, počet získaných výsledků, či zpoždění přijetí výsledků • tyto statistiky může uzel využít pro „inteligentní" výběr sousedů, kterým nový dotaz přepošle, a to na základě mnoha heuristik, například: • vybrat souseda, který v minulosti poskytl největší množství výsledků • vybrat souseda, který v minulosti odpovídal na dotazy skrze nejmenší počet kontaktovaných uzlů („hop count") • vybrat souseda, který v minulosti přeposlal největší množství zpráv • vybrat souseda, který má nejkratší frontu nezpracovaných zpráv • atd. < ! ► S -o o, c Heuristické směrovací strategie Řízené BFS a Inteligentní prohledávání II. • Řízené BFS (Directed BFS) • výhoda: radikálně menší počet vyhledávacích zpráv oproti standardnímu BFS • nevýhoda: statistiky vedené vůči každému ze sousedů jsou příliš jednoduché • neobsahují žádné informace související s obsahem dotazů • =>- Inteligentní prohledávání (Intelligent Search) • každý peer hodnotí své sousedy na základě jejich relevantnosti k danému dotazu • dotaz je pak přeposlán pouze těm sousedům, kteří jsou danému dotazu nejvíce relevantní • tímto je dosaženo preciznějšího hodnocení sousedů než u Řízeného BFS • dobrých výsledků je dosaženo zejména na sítích s vysokým stupněm lokálnosti dotazů Heuristické směrovací strategie Lokální indexy (Local Indices Search) • idea: • každý uzel si vytváří a spravuje indexy jak pro svá lokální data, tak pro data svých sousedů, kteří jsou od něj vzdáleni k hopů • pokud k — 0, je tato metoda podobná tradičnímu BFS (uzly spravují indexy pouze lokálních dat) • výsledek navrácený takovýmto uzlem je pak stejný jako výsledek, který by byl navrácen všemi uzly v rozsahu k hopů od daného uzlu • detaily: • dotazy jsou zpracovávány podle globální politiky P, která specifikuje hloubky, ve kterých jsou dotazy zpracovávány • dotaz zpracovávají pouze uzly v uvedených hloubkách (P) od dotazujícího se uzlu • ostatní uzly daný dotaz pouze přeposílají svým sousedům (nezpracovávají jej) • výhoda: • redukce výpočetní náročnosti díky omezení zpracování dotazu na menší počet uzlů • nevýhody: • vyšší požadavky na úložnou kapacitu (větší indexy na uzlech) • vysoká režie na údržbu (aktualizaci) těchto indexů • nekonzistence/zastaralost indexů (díky dynamice sítě) Heuristické směrovací strategie Náhodná procházka (Random Walk) I. • idea: o jakmile uzel přijme nový dotaz, je tento přeposlán náhodně vybranému sousedovi ke zpracování • tento proces se opakuje tak dlouho, dokud není nalezena uspokojivá odpověď • nebo dokud neexpiruje TTL (pokud je využito) => výsledek nebyl nalezen • detaily: • hlavní nevýhoda: • trpí na dlouhé latence zpracování dotazů • => k-walker Random Walk Algorithm o původce dotazu (zdrojový uzel) zasílá k dotazovacích zpráv svým náhodně vybraným sousedům (místo jedné jediné zprávy = originální 1-walker algoritmus) • jakmile uzel přijme dotazovací zprávu (tzv. walker), zpracovává/přeposílá ji s využitím stejného principu jako v případě základního algoritmu náhodné procházky (tj. jedinému vybranému sousedovi) • počet zpráv (navštívených uzlů) je navýšen lineárně v porovnání s 1-walker algoritmem Heuristické směrovací strategie Náhodná procházka (Random Walk) II. • detaily (pokračování): • => Random Breadth First Search (RBFS) • podobné /c-walker Random Walk ° původce dotazu nejprve náhodně vybere podmnožinu svých sousedů, kterým dotaz přepošle • každý z těchto sousedů pak opět náhodně vybírá podmnožinu svých sousedů, kterým dotaz přepošle • atd. • počet zpráv (navštívených uzlů) je navýšen exponenciálně v porovnání s 1-walker algoritmem Heuristické směrovací strategie Adaptivní pravděpodobnostní prohledávání (Adaptive Probabilistic Search, APS) I. • prohledávací metoda, která kombinuje fc-walker náhodnostní prohledávání a pravděpodobnostní prohledávání • hlavní rozdíl mezi APS a algoritmy na bázi náhodnostních „walkers": a náhodností walkers zasílají dotaz náhodně vybraným sousedům, zatímco APS zasílá dotaz sousedům na vybraným na základě určité pravděpodobnosti • => na základě dřívějších výsledků spravuje každý uzel pro každého ze svých sousedů pravděpodobnost jeho vybrání (pro každý objekt, resp. kategorii objektů) • detaily: • dva přístupy aktualizace spravovaných pravděpodobností: • Optimistický přístup - systém proaktivně navyšuje pravděpodobnost aktuálně vybraným (=dotazovaným) sousedům a snižuje jejich pravděpodobnost pouze tehdy, když „walker" přes ně vyslaný skončí s chybou • Pesimistický přístup - systém proaktivně snižuje pravděpodobnost aktuálně vybraným (=dotazovaným) sousedům a zvyšuje jejich pravděpodobnost pouze tehdy, když „walker" přes ně vyslaný skončí úspěšným nalezením výsledku Heuristické směrovací strategie Adaptivní pravděpodobnostní prohledávání (Adaptive Probabilistic Search, APS) II. • detaily (pokračování): • swapping-APS - každý uzel průběžně přepíná mezi optimistickým a pesimistickým přístupem • na základě pozorování poměru úspěšných a neúspěšných „walkerů" (pozorováno pro každý objekt) • weighted-APS - bere v úvahu také lokalitu sousedů (bližší uzly mají vyšší pravděpodobnost) Heuristické směrovací strategie Interest-Based Shortcuts I. • idea: • každý uzel si spravuje doplňkové linky pro účely vyšší efektivity prohledávání • tyto linky (nazývané interest-based short-cuts) spojují dva uzly mající podobný „zájem" (podobná data) • detaily: • při zpracování dotazu uzlem jsou nejprve konzultovány tyto doplňkové linky (dotaz je přeposlán daným uzlům) • pokud je výsledek nalezen, prohledávání končí • jinak je použita běžná prohledávací metoda • vytváření zkratek (shortcutů): • při připojení uzlu do systému nemá tento žádné shortcuts • po každém úspěšně zodpovězeném dotazu si původce dotazu do své databáze přidá doplňkové linky k uzlům, které na dotaz odpověděly • každý z uzlů si ukládá/spravuje pouze omezený počet shortcutů (kvůli limitům na úložné kapacity) Směrování ve strukturovaných sítích I. • nestrukturované P2P sítě trpí problémem nedostatečné efektivity vyhledávání • narozdíl od nestrukturovaných sítí, uzly strukturované P2P sítě jsou organizovány do určité fixní topologie (uspořádání) • například kruh (Chord), vícerozměrná mřížka (CAN), mesh (Pastry and Tapestry) či několika seznamů (Skip Graph) • => nově připojený uzel se musí řídit definovanými procedurami za účelem zjištění a začlenění se na definovanou pozici v síti • lze garantovat, že pokud výsledek na zadaný dotaz v síti existuje, bude vždy nalezen • navíc efektivně - většina systémů dokáže na dotazy zodpovídat se složitostí 0(log N) kroků/zpráv (N = počet uzlů v síti) • nevýhoda: • nutnost udržování definované topologie vyžaduje další režii v podobě správy/udržování směrovacích tabulek • podle využité překryvné topologie lze strukturované P2P systémy dělit do následujících kategorií: • Systémy využívající distribuované hashovací tabulky - např., Chord, CAN, Tapestry a Pastry, Viceroy a Crescendo, atd. • Systémy využívající tzv. Skip-listy - např., Skip Graph, SkipNet, atd. • Systémy využívající stromové struktury - např., P-Grid, P-Tree, BATON, Směrování ve strukturovaných sítích II • Distributed hash tables, DHT (distribuované hash tabulky) • Řešení pro účinné hledání i řídce se vyskytujících objektů • Hash tabulky • Rychlé a levné nalezení dat indexovaných podle klíče » Výše jsme neomezovali způsob vyhledání dat • Pokud použijeme hash tabulky, pak ztrátu obecnosti musíme nějak kompenzovat (ale často i vyhledání podle klíče - např. název objektu - plně stačí) • Obětujeme obecnost za efektivitu a rychlost Distribuované hash tabulky (DHT) • Hash tabulky v p2p sítích: hledáme data podle klíče • Předpokládáme, že data jsou uložena v distribuovaných uzlech (ne v poli) • Důsledky: • Použijeme překryvovou síť která spojuje uzly pro nás vhodným způsobem • Počet uzlů neznáme a navíc se mění v čase • Pracujeme s idealizovanými vlastnostmi • Hash funkce mapuje na idealizovaný prostor • Samotný prostor je mapován na uzly dynamicky Hlavní principy • Přiřadíme klíči jedinečný uzel • Nalezneme tento uzel rychle a snadno v překryvové síti • Zavedeme replikaci (více uzlů pro jeden objekt/klíč) • Rozložení zátěže může dynamicky měnit přiřazení klíče Nejrozšířenější jednoduchá implementace: Chord • Velmi populární (více jak 3000 citací). • Překryvová síť: orientovaná kružnice Směrovací strategie založené na DHT Chord I. • jeden z nejznámějších mechanismů směrování ve strukturovaných P2P sítích • idea: • využívá jednosměrnou hashovací funkci pro mapování jak uzlů, tak datových položek do jednorozměrného prostoru m-bitových identifikátorů • pro vygenerování identifikátoru uzlu je využita IP adresa uzlu, a • pro vygenerování identifikátoru datové položky je využita vlastní položka (případně jiný klíč, metadata, atp.) • prostor identifikátorů je zapotřebí zvolit dostatečně velký, aby pravděpodobnost přiřazení stejného identifikátoru dvěma různým uzlům sítě byla minimální • detaily: • prostor identifikátorů je logická kružnice čísel v rozsahu [0,2m — 1] • systém přiřazuje datovou položku s klíčem k prvnímu uzlu n, jehož identifikátor je roven, případně je vyšší než identifikátor k (v prostoru kružnice) • t.j., datová položka s klíčem k je přiřazena prvnímu uzlu ve směru hodinových ručiček od k .120.224.102" Kružnice identifikátorů založená na logické kružnice - klíče Ke a Kis jsou přiřazeny stejnému uzlu s identifikátorem N30 (zjištěn hashováním jeho IP adresy „202.120.224.102"). Klíč K56 (získán hashováním slova „Sailing") je přiřazen uzlu s identifikátorem /V70; klíč K100 je přiřazen uzlu s identifikátorem /Vii5; uzly /V42 a /V120 nemají žádné datové položky. Jednoduchý vyhledávací algoritmus: každý uzel zná pouze svého bezprostředního následovníka jakmile uzel přijme požadavek na vyhledání: nejprve ověří, zda on sám nemá požadovanou datovou položku pokud ano, je výsledek dotazu navrácen dotazujícímu uzlu pokud ne, přeposílá požadavek svému bezprostřednímu následovníkovi vyhledávání končí, jakmile je výsledek dotazu nalezen je identifikátor bezprostředního následovníka větší než identifikátor vyhledávané datové položky => výsledek dotazu nelze nalézt složitost vyhledávání je O(N) (N = počet uzlů v systému) Směrovací strategie založené na DHT Chord III. - Škálovatelný vyhledávací algoritmus I. Škálovatelný vyhledávací algoritmus: • místo spravování pouze svého bezprostředního následovníka spravuje každý uzel svou vlastní směrovací tabulku (tzv. finger table) obsahující záznamy k jeho x následovníkům • jakmile uzel n přijme požadavek na vyhledání datové položky s identifikátorem k: • jestliže daný uzel nespravuje vyhledávaná data, prohledává svou směrovací tabulku a hledá takový uzel n, pro který platí podmínka n.id < rí.id < k • pokud takový uzel existuje, přepošle mu uzel n požadavek na vyhledání hledané datové položky • jinak uzel žádá svého bezprostředního následovníka, aby hledanou datovou položku vyhledal • vyhledávání končí, jakmile • je výsledek dotazu nalezen o je identifikátor bezprostředního následovníka větší než identifikátor vyhledávané datové položky => výsledek dotazu nelze nalézt • složitost vyhledávání je 0(log N) (N = počet uz^i v systémy.) Směrovací strategie založené na DHT Chord IV. Budování systému: • při připojení nového uzlu tento: O hledá svou pozici v Chord kruhu a přejímá data, za které by měl být zodpovědný (na základě klíčů) O inicializuje své směrovací tabulky O aktualizuje směrovací tabulky ostatních uzlů, které by měly reflektovat danou změnu • při odpojení existujícího uzlu není potřeba žádných kroků Směrovací strategie založené na DHT Content Addressable Network (CAN) I. • idea: • směrovací systém utvořený nad virtuálním d-dimenzionálním kartézským souřadnicovým systémem • systém rozděluje prostor datových klíčů do samostatných oblastí, kdy každá z oblastí je spravována jediným (vybraným) uzlem • tento uzel spravuje všechna datové položky spadající do jím spravované oblasti • systém využívá hashovací funkce pro mapování datové položky na bod p v souřadnicovém systému (klíčem je tak d-tice) • detaily: • vkládání nové datové položky: U hodnota datové položky je namapována na bod p souřadnicového systému Q je nalezen uzel n, do jehož zóny spadá p - tento je kontaktován a požádán o uložení položky • zpracování vyhledávacího dotazu je podobné • pokud výsledek existuje, musí být uložen na uzlu pokrývajícím danou zónu • každý z uzlů musí spravovat informace o svých sousedech • to jest, uzly spravující přilehlé zóny • směrování je založeno na jednoduchém hladovém algoritmu • v každém kroku je hledán uzel, jehož souřadnice jsou bjíža cílo^/é zóně Směrovací strategie založené na DHT Content Addressable Network (CAN) V. Budování systému: • při připojení nového uzlu k systému musí tento: O najít libovolný, již připojený uzel O identifikovat zónu, která může být rozdělena, a požádat jejího vlastníka/správce o její rozdělení na dvě části • jedna část bude spravována původním uzlem, druhá část bude spravována nově připojeným uzlem O vytvořit si svou směrovací tabulku a zaktualizovat směrovací tabulky svých sousedů • při odpojení uzlu ze systému musí tento požádat vybraného souseda o sloučení obou zón do jediné Směrovací strategie založené na DHT Pastry I. • idea: • směrovací systém založený na tzv. PRR stromech • PRR = Plaxton, Rajaraman a Richa (1997) • m-bitový identifikátor uzlu je rozdělen na sekvenci „číslic" se základem 2b • např. 128-bitový identifikátor je rozdělen na 32 4-bitových číslic (b = 4, základ = 24 => hexadecimální sekvence číslic) • b ... konfigurovatelný parametr • daná datová položka je pak uložena na uzel, jehož identifikátor sdílí nejdelší společný prefix s identifikátorem dané datové položky • v každém směrovacím kroku je hledán/vybrán uzel, který má s cílovým uzlem (datovou položkou) delší společný prefix než hledající uzel (delší o 1 číslici, tj. b bitů) • složitost hledání je 0(log2i, N) • detaily: • každý peer má svou směrovací tabulku • organizovaná do pevného počtu řádků (tzv. levelů) (= \log2i,(N)]) a v rámci každého řádku/levelu pak obsahující pevný počet položek (= 2fc-l) • ID řádku = délka společného prefixu s hledaným uzlem • ID sloupce = další možný krok Směrovací strategie založené na DHT Pastry II._ li ; J 3 4 ..i 7 8 9 a b ( d e t X v v v x v A x v x x A X V x li /ŕ (i (í 6 (í /ŕ << H ti 6 t> ť, ii u 0 ; J 4 7 8 9 M b C d ť ť .1 v v \ \ v v \ v v v i x Y --- - - _ 6 (i ŕ» ii f 6 6 ti 6 H ti t, ti ii f. 9 5 J .i S .í 5 5 5 s ,> > J .-, 0 I 4 5 6 7 ti n b f d C ť a x v x x a A .v \ A x A A v x - - "-- 6 t, ti Ír 6 -ŕ ii 6 ti ti t> ti ii u J 5 5 5 .1 .» :> :> :> :> i> .1 -> .t M a i .t ■ a O(logrí) 3roces hledání ve Skip List struktuře. Směrovací strategie založené na Skip Listech Skip Graph I. idea: • směrovací strategie založená na Skip Listech • originální skip-listy však nejsou vhodné, neboť by docházelo k přetěžování elementů na nejvyšší úrovni • narozdíl od originálních Skip-listů, kdy tyto využívají na každé úrovni právě jeden seznam, poskytuje Skip Graph na každé úrovni více takovýchto seznamů • každý uzel je na každé z úrovní umístěn do nějakého seznamu • seznamy, do kterých daný uzel náleží, jsou určovány podle náhodného vektoru příslušnosti (membership vector) (vytvářen v okamžiku připojování uzlu do systému) • počet úrovní je 0(log N) detaily vyhledávání: • při vyhledávání dotazu uzlem: • vyhledávání vždy začíná v nejvyšší úrovni v seznamu, do kterého daný uzel náleží • v každém kroku: pokud na dané úrovni existuje uzel, jehož hodnota je blíže vyhledávané, pak je tomuto uzlu dotaz přeposlán • jinak daný uzel s vyhledáváním pokračuje na nižší úrovni • cílový uzel je nalezen nejhůře v okamžiku sestoupení na nejnižší úroveň (do nejnižšího seznamu) • složitost vyhledávání je 0(log N) Vektor příslušnosti (membership vector) definuje pouze seznamy, do kterých daný uzel náleží (nemá žádnou spojitost s daty, podle kterých jsou seznamy setřízený). Omezením na seznamy obsahující počáteční element/uzel lze získat skip list (lze tak využít stejnou vyhledávací metodu určenou pro běžnou skip-list strukturu): o) > M M a) > a) M Směrovací strategie založené na Skip Listech Skip Graph V. Budování systému: • při připojení nového uzlu s identifikátorem X: • na základě jeho vektoru příslušnosti m(X) se uzel X připojuje do seznamů uzlů, jejichž vektor příslušnosti má shodný prefix s m(X) (délka společného prefixu závislá na úrovni seznamu) o specifičtěji: • X se nejprve připojí do úrovně 0 na pozici, na kterou dle své klíčové položky (dat) náleží • pro každou úroveň / > 1 se X připojuje k nejbližšímu uzlu Y sdílejícímu s uzlem X shodný prefix o délce / Směrovací strategie založené na Skip Listech SkipNet I._ idea: • směrovací systém velmi podobný systému Skip Graph • místo skip-listů jsou v rámci SkipNetu uzly organizovány do kruhů • organizovaných do úrovní/levelů (podobně jako u systému Skip Graph) • uzly jsou na každé úrovni setřízeny podle datového klíče • každý uzel má na každé ze svých úrovní ve směrovací tabulce uloženy dva ukazatele ke svým sousedům • ukazatele na úrovni h ukazují na uzly, které jsou zhruba 2h uzlů nalevo a napravo od daného uzlu • všechny uzly jsou na nejnižší úrovni (úroveň 0) propojeny tzv. kořenovým kruhem (root ring) • mechanismus vyhledávání a budování systému jsou podobné mechanismům představeným pro systém Skip Graph Směrovací strategie založené na Skip Listech SkipNet IV. _ Příklad vyhledávání: Nalezení uzlu V (počátek hledání v uzlu A) Ring Ring Ring Ring Ring Ring Ring Ring 000 001 010 011 100 101 110 111 [^^^M^ C^^^) ^Ring Sjgji (^Ŕingllg) L =1 Level: L =0 Obrázek: Zpráva je nejprve přeposlána uzlu T, neboť tento je blíže hledanému uzlu. Směrovací strategie založené na Skip Listech SkipNet V._ Příklad vyhledávání: Nalezení uzlu V (počátek hledání v uzlu A) Ring Ring Ring Ring Ring Ring Ring Ring 000 001 010 011 100 101 110 111 L=0 Obrázek: Směrovací tabulka uzlu T. Směrovací strategie založené na Skip Listech SkipNetVI. _ Obrázek: Jelikož má uzel T přímou informaci o hledaném uzlu V (na úrovni 0), vyhledávání končí (cíl je nalezen). Stromově-orientované směrovací strategie P-Grid I. idea: • systém P-Grid je založen na vybudovaném virtuálním binárním stromu, v rámci kterého každý z peerů spravuje jeden z listů daného stromu • systém každému z peerů přiřazuje identifikátor, který je zřetězením binárních bitů reprezentujících cestu od kořene stromu k danému uzlu • každý z peerů je pak zodpovědný za všechny datové položky, jejichž prefix identifikátoru klíče je shodný s identifikátorem daného uzlu • pro účely zvýšení odolnosti vůči výpadkům lze k jednomu identifikátoru přiřadit více peerů • pro účely vyhledávání pak každý z peerů spravuje svou směrovací tabulku Stromově-orientované směrovací strategie P-Grid III. mechanismus vyhledávání: • jakmile uzel n přijme požadavek na vyhledání datové položky k, nejprve ověří, zda jeho identifikátor není prefixem k • pokud ano, vyhledává výsledek mezi jim spravovanými daty » pokud ne, využívá svou směrovací tabulku pro vyhledání peera, který je blíže vyhledávanému klíčí; tomu je pak požadavek přeposlán • maximální počet vyhledávacích kroků je ohraničen hloubkou stromu • => složitost vyhledávání je O(log2 N) lgorithm 6 : PGrid_Search (Node n, Key A') 1: if w.id C k then 2: result = Local_Search(fc) 3: return result to the query issuer node 4: else {find a closer neighbor node to forward the query} 5: find / such that Prefix(A', /) = Invert(Prefix(«.id, /)) 6: n' = a randomly selected node from Routing(w) at level / 7: PGrid_Search(n', k) 8: end if Stromově-orientované směrovací strategie P-Tree I. the idea: • v rámci systému P-Grid nelze zaručit vyváženost stromové struktury • systém P-Tree je založen na virtuálních vyvážených B+-stromech vybudovaných nad Chord strukturou • každý z peerů spravuje: • uzel Chord sítě, který je listem dané stromové struktury, a • tzv. semi-independent B+-strom, což je peerova představa o tzv. fully independent B+-stromu • fully independent B+-strom peera je 6+-strom, ve kterém hodnota klíče uloženého na daném uzlu je považována za nejmenší v dané Chord struktuře • semi-independent B+-strom obsahuje pouze kořenové uzly a všechny uzly v nejlevější části daného fully-independent B+-stromu • pro účely snazší správy se mohou rozsahy uzlů daných B+-stromů překrývat (např. uzel C v následujícím obrázku) Stromově-orientované směrovací strategie BATON I. idea: • oproti standardním stromovým strukturám se systém BATON odlišuje zejména dvěma vlastnostmi: • data jsou uložena jak na listech stromu, tak na vnitřních uzlech • kromě linek k rodičům a potomkům jsou na každém z uzlů udržovány ještě tzv. linky k přilehlým uzlům (adjacent links) a linky k sousedům (neighbor links) • adjacent links jsou využity pro propojení daného uzlu s uzlem/uzly, které spravují jemu přilehlé rozsahy klíčů • neighbor links jsou využity pro propojení daného uzlu se sousedy (na stejné úrovni stromu), kteří se od něj nalézají ve vzdálenosti 2', / > 0 • účelem těchto linek je zabránění zahlcení kořene (resp. kořenového uzlu) vyhledávacími dotazy Stromově-orientované směrovací strategie BATON III. detaily vyhledávání: • jakmile uzel x přijme požadavek na vyhledání: O jestliže hledaný klíč spadá do jim spravovaného rozsahu, odpovídá na dotaz on sám O jinak požadavek přeposílá svému nejvzdálenějšímu sousedovi (na stejné úrovni), který spravuje k vyhledávanému klíči bližší (avšak nepřevyšující) záznamy O pokud takovýto uzel neexistuje, přeposílá uzel x požadavek na vyhledání buď svému potomkovi (pokud existuje) nebo přilehlému uzlu ve směru vyhledávání (tj. s využitím tzv. adjacent linky) lgorithm 8 : BATON_Search(Node n. Key k) 1: if n covers the search key then 2: result = Local_Search(• zasílá IP adresu uzlu C9 dotazujícímu se uzlu C12. Structured superpeers: superpeer uzly SO, SI, S2, a S3 spravují (po řadě) rozsahy klíčů (0,4], (4,8], (8,12] a (12,0]. Pokud např. peer Pl vyhledává data s klíčem key = 10, nejprve zasílá požadavek na vyhledání svému superpeer uzlu SO; SO předává dotaz uzlu S2 (jelikož S2 spravuje rozsah, kam vyhledávaná položka náleží), který pak uzlu Pl odpovídá s informací o IP adrese jim nalezeného uzlu, který vyhledávaná data obsahuje. P2P směrování: Závěr Strukturované vs. Nestrukturované P2P sítě - Srovnání structured P2P unstructured P2P routing based on a routing table flooding, random walk, ... lookup possibilities based on keys only possibility to ask more compex queries existing item is always found yes cannot be guaranteed critical part node join/disconnect lookup/routing Celkové shrnutí přednášky • Grafy velmi důležitou diskrétní konstrukcí matematiky i informatiky • Rada reálných problémů převeditelná na grafové problémy • Dobrá znalost alespoň základů teorie grafů pomůže • Znalost grafových algoritmů resp. problémů může pomoci při odhadu náročnosti řešení konkrétního praktického problému • Mapování na grafový problém může najít optimální řešení • Plánování jako grafový problém • Velmi významné optimalizace