PB165 - Grafy a sítě 11. Zajímavé grafy a peer to peer sítě PB165 - Grafy a 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 PB165 - Grafy a sítě Náhodné grafy (Erdôs-Renyi) • Pravděpodobnostní modely grafů Definice G(/7, p) model náhodného grafu: Mějme graf s n vrcholy, pak neorientovaná hrana vznikne mezi dvojicí vrcholu s pravděpodobností p, nezávisle na ostatních dvojicích uzlů. • Pravděpodobnost, že graf G má k hran je dána výrazem p*(i - Pp-k • Pravděpodobnost, že graf G 6 G(n,p) obsahuje k hran má binomiální rozložení PB165 - Grafy a sítě Prahy náhodných grafů Mějme model náhodného grafu G{n, p) a nechť p = c^. Je-// 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) « n^~^ • Pravděpodobnost, že X = 0 je přibližně • f [X] se blíží 0, pokud c > 1, tedy počet izolovaných vrcholů se blíží 0. • Naopak, pro c < 1 se f [X] blíží nekonečnu, a tedy pravděpodobnost, že graf G nemá izolovaný uzel, se blíží 0. PB165 - Grafy a sítě 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,j/2) je definována jako d(u, v) = max(|xi - x2|, |yi - y2|). Jedná se o oblíbený model senzorových sítí PB165 - Grafy a sítě Souvislost Věta Pokud r > yj£±2MJlf kde c je konstanta > 4, pak G(/7, r) je asymptoticky prakticky určitě souvislý graf, tj. Pravděpodobnost(G(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(/7, r) je souvislé, pokud žádná přihrádka není prázdná. • Nechť r = ^£^J1, pak pravděpodobnost, že přihrádka je prázdná je menší nebo rovna n~c^. • Nechť X je počet prázdných přihrádek. Pak E[X] < nl~c'\ tj. E[X] se blíží nule, pokud o 4. Pravděpodobnost^ > 0) < E[X] -> 0 PB165 - Grafy a sítě Power-law grafy 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~^. Příklady: • Internet a WWW: /3 = 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 100.000 serverů) • Decentralizované • Gnutella: Primitivní hledání: záplava • Chytřejší algoritmy Základ výzkumu v oblasti peer to peer (P2P) sítí PB165 - Grafy a sítě Srovnání komunikační struktury PB165 - Grafy a sítě P řek ry vo vé 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 PB165 - Grafy a sítě P řek ry vo vá síť Obrázek: Překryvová vs. fyzická (základová) síť. 4 □ ► 4 S" ► 4 PB165 - Grafy a sítě P řek ry vo vá síť Obrázek: Překryvová vs. fyzická (základová) síť. 4 □ ► 4 S" ► 4 PB165 - Grafy a sítě P řek ry vo vá síť Obrázek: Překryvová vs. fyzická (základová) síť. < □ ► 4 S" ► < PB165 - Grafy a sítě P řek ry vo vá síť Obrázek: Překryvová vs. fyzická (základová) síť. 4 □ ► 4 S" ► 4 PB165 - Grafy a sítě Základní členění P2P systémů Static configuration Re-configurable Topology Structured Probabilistic Obrázek: Základní členění P2P systémů PB165 - Grafy a sítě Základní členění P2P systémů Centralizované P2P systémy Peer A Obrázek: 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. PB165 - Grafy a sítě Základní členění P2P systémů Decentralizované P2P systémy Peer D Peer H Obrázek: Decentralizované P2P systémy: (Peer A požaduje určitá data, 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. PB165 - Grafy a sítě Základní členění P2P systémů Hybridní P2P systémy C9 C6 Obrázek: 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. PB165 - Grafy a sítě • směrování zpráv/požadavků je jednou z klíčových operací P2P systému o 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 • + způsob organizace daných informací o žádná metadata =^ neexistuje žádná jiná cesta pro vyhledání požadované informace než záplava/broadcast požadavku skrze celou síť uzly P2P sítě Perfect information (Napster-like) No information (Gnutella-like) Structured Unstructured PB165 - Grafy a sítě Směrování v P2P sítích Problém vyhledávání — Client Get(key="title") PB165 - Grafy a sítě Směrování v P2P sítích Problém vyhledávání - Centralizovaný přístup (Napster) SetLocftitle", N4) N, N2 N Client Publisher@N4 Key="title" Value=file data... DB Lookupftitle") N9 N7 Ns N6 7 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. PB165 - Grafy a sítě Směrování v P2P sítích Problém vyhledávání - Záplava dotazy (Gnutella) Publisher@N4 Key="title" Value=file data... N Lookupftitle") Client Robustní, avšak v nejhorším případě je pro každý dotaz sítí přenášeno O(n) zpráv (neškáluje). PB165 - Grafy a sítě Směrování v P2P sítích Problém vyhledávání - DHT-based systémy (Chord, CAN, Pastry, Tapestry, . ..) Publisher Key=H(audio data) Value={artist, album title, track title} N, Client Lookup(H(audio data)) N 8 PB165 - Grafy a sítě 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, broadcast) • 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) • 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 PB165 - Grafy a sítě Heuristické směrovací strategie Postupné vnořování (Iterative Deepening) • 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 buď 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,..., Dn, kde Di < D2 < ... < Dn • 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í >r>o,o PB165 - Grafy a sítě 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 o 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. >Oo,o PB165 - Grafy a sítě 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ů PB165 - Grafy a sítě Heuristické směrovací strategie Lokální indexy (Local Indices Search) • 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ě) PB165 - Grafy a sítě Heuristické směrovací strategie Náhodná procházka (Random Walk) I. • idea: • 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: o trpí na dlouhé latence zpracování dotazů k-walker Random Walk Algorithm • 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 PB165 - Grafy a sítě Heuristické směrovací strategie Náhodná procházka (Random Walk) II. • detaily (pokračování): • Rančom 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 PB165 - Grafy a sítě Heuristické směrovací strategie Adaptivní pravděpodobnostní prohledávání (Adaptive Probabilistic Search, APS) I. • idea: • prohledávací metoda, která kombinuje /c-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": • 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 PB165 - Grafy a sítě 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) PB165 - Grafy a sítě Heuristické směrovací strategie Interest-Based Shortcuts I. • 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) PB165 - Grafy a sítě Heuristické směrovací strategie Interest-Based Shortcuts II. PB165 - Grafy a sítě 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, atd. i □ i ^ igi i vOQ^o PB165 - Grafy a sítě 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 o 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 PB165 - Grafy a sítě 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 PB165 - Grafy a sítě Distribuované hash tabulky (DHT) každý uzel P2P sítě spravuje určitou část globální hashovací tabulky uložení/zjištění položky s znamená oslovení uzlu, který spravuje hodnotu hash(s) Data A Data B Data C Data D Data E DHT Klíč: 0x45A23 Klíč: Qx8C39A Klíč: 0x6C561 Klíč: 0x6C563 Klíč: 0xBF4D2 PB165 - Grafy a sítě 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ů projeden objekt/klíč) • Rozložení zátěže může dynamicky měnit přiřazení klíče Nej rozšířenější jednoduchá implementace: Chord • Velmi populární (více jak 3000 citací). • Překryvová síť: orientovaná kružnice PB165 - Grafy a sítě 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.) o 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 PB165 - Grafy a sítě Směrovací strategie založené na DHT Chord II. Obrázek: Kružnice identifikátorů založená na logické kružnice - klíče K6 a K18 jsou přiřazeny stejnému uzlu s identifikátorem A/30 (zjištěn hashováním jeho IP adresy „202.120.224.102"). Klíč K5e (získán hashováním slova „Sailing") je přiřazen uzlu s identifikátorem A/70; klíč K100 je přiřazen uzlu s identifikátorem A/115; uzly A/42 a A/120 nemají žádné datové položky. PB165 - Grafy a sítě Směrovací strategie založené na DHT Chord III. - Jednoduchý vyhledávací algoritmus 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áto 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) PB165 - Grafy a sítě 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 < n'.id < k o 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 • 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 o složitost vyhledávání je 0(log N) (N = počet uz^jj v systémy^ ^ PB165 - Grafy a sítě Směrovací strategie založené na DHT Chord III. - Škálovatelný vyhledávací algoritmus II. Obrázek: Příklad směrovací tabulky (vlevo) a příklad vyhledání datové položky s identifikátorem Km začínající v uzlu N-? (vpravo). PB165 - Grafy a sítě Směrovací strategie založené na DHT Chord III. - Škálovatelný vyhledávací algoritmus III. Algorithm 2 : Chord_Lookup (Node n, Key-Id k) 1: for i = m down to 1 do 2: nr — 77.routingtable.get(0 3: if /?.id < /?r.id < k then 4: Chord_Lookup(n/, k) 5: return 6: end if 7: end for 8: nf = n.successor 9: if /?.id < nf .Id < k then 10: Chord_Lookup(rc', k) 11: else 12: result = Local_Search(/:) 13: return result to the query issuer node 14: end if PB165 - Grafy a sítě 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ů PB165 - Grafy a sítě Směrovací strategie založené na DHT Content Addressable Network (CAN) I. • idea: • směrovací systém utvořený nad virtuálním af-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 af-tice) • detaily: • vkládání nové datové položky: O hodnota datové položky je namapována na bod p souřadnicového systému O 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 blíže cílové zóně PB165 - Grafy a sítě Směrovací strategie založené na DHT Content Addressable Network (CAN) II. (0.5-0.75,0.5-1.0) c (0.0-0.5,0.5-1.0) D E — A (0.0-0.5,0.0-0.5) B (0.5-1.0,0.0-0.5) >(0.75-1.0,0.5-1.0) A Node E's Virtual cordinate zone E's neighbors: D and B Obrázek: CAN P2P systém využívající dvoudimenzionální prostor spravovaný 5 uzly PB165 - Grafy a sítě Směrovací strategie založené na DHT Content Addressable Network (CAN) III. 0,5 0 + + + + ^ A + ft + A i + + A 0 0,5 More paths might be used to reach the destination Looking for the data item having the key (0,6;0,8) Obrázek: Příklad vyhledání datové položky v CAN P2P systému PB165 - Grafy a sítě Směrovací strategie založené na DHT Content Addressable Network (CAN) IV. Algorithm 3 : CAN_Lookup (Node n, Point p) 1: if n .zone covers p then 2: result = Local_Search(/?) 3: return result to the query issuer node 4: else 5: find a neighbor node nf whose zone is closer to p 6: CAN_Lookup(rc', p) 7: end if PB165 - Grafy a sítě 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é PB165 - Grafy a sítě 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ů) (= \log2b(A/)]) a v rámci každého řádku/levelu pak obsahující pevný počet položek (= 2b - 1) • ID řádku = délka společného prefixu s hledaným uzlem • ID sloupce = další možný krok PB165 - Grafy a sítě Směrovací strategie založené na DHT Pastry II. 0 1 2 3 4 7 s 9 a b c d e f X X X X x X x x x X x x x x x _ _ - .—■ ——" It ti 6 6 6 6 6 6 6 6 6 6 6 (i 6 0 1 2 3 4 6 7 8 i) a b c d e f \ X X v x x \ \ v A x x _—i — - 6 ti 6 6 6 ti 6 ti ti 6 6 6 ii ti 5 5 s 5 s 5 s $ :> s $ s j s 5 0 1 2 3 4 6 7 8 9 b c d e f X X X x x X x x x x x x x x x __— —- — i _^ ti 6 6 6 ti 6 ti ti 6 6 6 6 6 ti 6 5 s 5 s 5 5 s 5 5 5 5 5 5 5 5 p then 5: PRP_Routing(£, i) 6: else 7: j as the closest node to i 8: end if PB165 - Grafy a sítě Směrovací strategie založené na DHT Pastry VI. Budování systému: • nově připojený uzel (s identifikátorem X): O kontaktuje libovolný (již připojený) uzel A a zasílá mu zprávu join(X) O uzel A směruje zprávu join(X) uzlu Z, který je nejblíže klíči X O uzel X přijme leaf set uzlu Z jako svou vlastní a naplní si svou směrovací tabulku (/-tý řádek tabulky je převzat z /-tého uzlu na cestě z A do Z) O uzel X informuje uzly, které by si jej měly přidat do svých směrovacích tabulek při odpojení existujícího uzlu ze sítě: • musí tento předat jim spravovaná data vybranému sousedovi • směrovací tabulky se časem zupdatují automaticky • daný uzel bude nahrazen uzlem z jeho nejbližšího okolí (získán z jeho leaf set) PB165 - Grafy a sítě Směrovací strategie založené na DHT Tapestry Tapestry: • další směrovací strategie pro P2P sítě založená na PRR stromech • velmi podobná Pastry (vznikaly však nezávisle na sobě) • hlavní rozdíl mezi Pastry a Tapestry: • v rámci Pastry se v každém kroku hledání prodlužuje nejdelší společný prefix (s hledaným uzlem) • v rámci Tapestry se v každém kroku hledání prodlužuje nejdelší společný suffix (s hledaným uzlem) • (lze identifikovat i několik dalších, většinou drobných rozdílů) PB165 - Grafy a sítě Směrovací strategie založené na DHT Srovnání CAN Chord Pastry Routing performance 0( d * N1M) O(log N) 0(logBN) Routing state 2 d log N B * logBN + B Peers join/leave 2 d (log N)2 logBN B = 2b Obrázek: Srovnání prezentovaných směrovacích mechanismů strukturovaných P2P sítí založených na DHT (co do rychlosti/účinnosti hledání, nezbytné úložné kapacity na jednotlivých uzlech a složitosti reorganizace při připojení/odpojení uzlu). < n ► < g ► < ^1 ► < ^1 ► 1: ^)0,O PB165 - Grafy a sítě Směrovací strategie založené na Skip Listech Struktura Skip List I. skip list je datová struktura určená pro uložení setřízeného seznamu položek, která (pro snadné vyhledání/uložení) využívá hierarchii zřetězených seznamů seznamy jsou sestaveny do úrovní: • nejnižší úroveň (level 0) je běžný setřízený seznam • každá z vyšších vrstev pak funguje jako „expresní linka" pro seznamy nižších úrovní o element z vrsty / se vyskytuje ve vrstvě / + 1 s určitou pravděpodobností p • (obvykle p = 1/2 or p = 1/4) head 1 8 10 NIL NIL NIL NIL PB165 - Grafy a sítě Směrovací strategie založené na Skip Listech Struktura Skip List II. Hledání cílového elementu: • začíná na začátku seznamu umístěného v nejvyšší úrovni a Dokračuje horizontálně, dokud není nalezena položka, ii i AA R 101 A 100 J 000 001 011 110 > R W M 110 101 A ' 100 ' J 001 001 011 \Membersh p vectors ŕ > R v 001 100 001 011 110 101 Vektor prí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řízeny). PB165 - Grafy a sítě Směrovací strategie založené na Skip Listech Skip Graph III. 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): PB165 - Grafy a sítě Směrovací strategie založené na Skip Listech Skip Graph IV. Algorithm 5 : SkipGraph_Search (Node w, Key k) 1: / = the highest level of n 2: while / > 0 do 3: find a neighbor node n' at level / that is closer to k 4: if/?' exists then 5: SkipGraph_Search(nr, k) 6: return 7: end if 8: / =/ - 1 9: end while 10: result = Local_Search(£) 11: return result to the query issuer node PB165 - Grafy a sítě 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) • 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 / PB165 - Grafy a sítě Směrovací strategie založené na Skip Listech Skip Graph VI. .3 Si .3 001 001 001 100 100 100 AA 011 AA 011 110 110 í 110 new no W J 101 i-1 101 M w F ■ A 1 f w R -■ ■ 101 001 Obrázek: Krok 1: Začínaje v libovolném uzlu, najdi uzel s nejbližším (datovým) klíčem na úrovni 0. PB165 - Grafy a sítě Směrovací strategie založené na Skip Listech Skip Graph VII. CM "ČÍ! 001 100 001 011 110 w_ 101 bbi 100 01 _M bii 110 101 A 1 k. J 1 M w "Si J R -■ iľ 001 100 001 011 110 101 Obrázek: Kro/c 2; Na každé úrovni / se připoj do seznamu, s nímž sdílíš stejný prefix vektoru příslušnosti (o délce /). PB165 - Grafy a sítě 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 PB165 - Grafy a sítě Směrovací strategie založené na Skip Listech SkipNet II. Ring Ring Ring Ring Ring Ring Ring Ring 000 001 010 011 100 101 110 111 Obrázek: Kompletní směrovací informace uzlu 8 v rámci SkipNet sítě (včetně identifikátorů jednotlivých kruhů). < n ► < g ► < ^1 ► < ^1 ► 1: ^)0,O PB165 - Grafy a sítě Směrovací strategie založené na Skip Listech SkipNet III. Obrázek: Směrovací tabulky pro uzly /la 1/. PB165 - Grafy a sítě 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 L=0 Obrázek: Zpráva je nejprve přeposlána uzlu T, neboť tento je blíže hledanému uzlu. PB165 - Grafy a sítě 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 =2 L =1 L =0 Obrázek: Směrovací tabulka uzlu T. PB165 - Grafy a sítě Směrovací strategie založené na Skip Listech SkipNet VI. Příklad vyhledávání: Nalezení uzlu V (počátek hledání v uzlu A) Ring 000 Ring Ring Ring Ring Ring Ring Ring 001 010 011 100 101 110 111 (Äf~Rtng 0 • účelem těchto linek je zabránění zahlcení kořene (resp. kořenového uzlu) vyhledávacími dotazy PB165 - Grafy a sítě Stromově-orientované směrovací strategie BATON II. PB165 - Grafy a sítě 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í bud' svému potomkovi (pokud existuje) nebo přilehlému uzlu ve směru vyhledávání (tj. s využitím tzv. adjacent linky) PB165 - Grafy a sítě Stromově-orientované směrovací strategie BATON IV. [0-5) [8-12) [17-23) [38-41) [50-54)[57-61)[64-67)[69-73) [79-83)[86-90)[95-100) Obrázek: Příklad vyhledávání v systému BATON: uzel H vyhledává datovou položku (s klíčem 74) uloženou na uzlu C. PB165 - Grafy a sítě Stromově-orientované směrovací strategie baton v. Algorithm 8 : BATON_Search(Node n, Key k) 1: if n covers the search key then 2: result = Local_Search(#) 3: return result to the query issuer node 4: else 5: if there exists a neighbor nf ofn that is closer to k then 6: BATON_Search(n', k) 7: else 8: if there exists a child nf of n that is closer to k then 9: BATON_Search(n', k) 10: else 11: nf is an adjacent node of n that is closer to k 12: BATON.SearcrV, k) 13: end if 14: end if 15: end if PB165 - Grafy a sítě Směrování v hybridních P2P sítích • hybridní P2P systémy organizují peery do hierarchických struktur • vybrané (mocné, powerfuí) uzly (superpeers, supernodes) jsou umístěny do vyšší úrovně, a • běžné peer uzly (často nazývané taky klientské uzly) jsou umístěny do nižších úrovní • každý klientský uzel náleží k jednomu superpeer uzlu a nekomunikuje s ostatními uzly jinak než přes svého superpeera • obecné směrovací schéma hybridních P2P sítí: O klientský uzel zasílá požadavek na vyhledání svému superpeer uzlu Q superpeer prohledává svůj adresář za účelem zjištění, který jemu náležející klientský uzel či který jiný superpeer (do jehož oblasti spadá hledaný uzel) obsahuje odpověď na hledaný dotaz Q požadavek je přeposlán superpeerovi, který by měl mít požadovanou odpověď • tento superpeer pak s využitím svého adresáře informací o jim spravovaných klientech vyhledává peera, který obsahuje hledaná data Q IP adresa vyhledaného peera je pak zaslána zdrojovému uzlu • následná komunikace (získání dat) pak probíhá napřímo mezi zdrojovým a vyhledaným uzlem • příklady hybridních sítí: • KaZaA, BestPeer, Edutella, atd. PB165 - Grafy a sítě Směrování v hybridních P2P sítích Edutella Obrázek: Síť Edutella. Požadavek na vyhledání je nejprve směrován na superpeery, kteří jsou organizováni do tzv. in HyperCuP sítě (= HyperCube P2P), v rámci které může být využito směrovací schéma na bázi nejdelšího společného suffixu. PB165 - Grafy a sítě Směrování v hybridních P2P sítích Ultrapeers Obrázek: Modifikovaná síť Gnutella s ultrapeery. Předpokládejme, že data požadované peerem C12 jsou umístěny na peerovi C9: peer C12 nejprve zasílá svůj požadavek na vyhledání svému ultrapeerovi L/4, který s využitím mechanismu záplavy rozesílá požadavek do sítě, který se tak skrze uzel Ul dostane na uzel U2; uzel U2 prohledává svůj index jim spravovaných uzlů a zjišťuje, že požadovaná data jsou na uzlu C9 —> zasílá IP adresu uzlu C9 dotazujícímu se uzlu C12. PB165 - Grafy a sítě Směrování v hybridních P2P sítích Structured Superpeers Obrázek: 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. PB165 - Grafy a sítě 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 PB165 - Grafy a sítě Celkové shrnutí přednášky • Grafy velmi důležitou diskrétní konstrukcí matematiky i informatiky • Řada 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 PB165 - Grafy a sítě