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í 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 ((1-P)Ö- • Pravděpodobnost, že graf G e G(n,p) obsahuje k hran má binomické rozložení lJ)pk(l-pp- □ S *■ ■* ^ > Prahy náhodných grafů Mějme model náhodného grafu G(n,p) a necht p = c-^-. 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 vrcholu v grafu G E G(n,p). • Pak horní hranice E [X] = n(l - p)*""1) « a/1"^ • Pravděpodobnost, že X = 0 je přibližně W^j. • E[X] se blíží 0, pokud c > 1, tedy počet izolovaných vrcholu se blíži 0. 9 Naopak, pro c < 1 se E[X] blíži nekonečnu, a tedy pravděpodobnost, že graf G nemá izolovaný uzel, se blíží 0. u n 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í. Pokud r > Jc '°g -, kde c je konstanta > 4, pak G(n, r) je asymptoticky prakticky určitě souvislý graf, tj. Pravděpodobnost(G(n, r) je souvislý graf) se blíži 1 jak se n blíži 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 = Jc'°6", 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] < nl~c/\ tj. E[X] se blíží nule, pokud c> 4. • Pravděpodobnost^ > 0) < E[X] -»■ 0. Power-law grafy Definice Power la měřítku. w je jakýkoliv polynomiální vztah, který nezávisí na Pro dvě proměnné se nejčastěji vyjadřuje vztahem f(x) = = axk + o(xk) kde a a k jsou konstanty a zanedbatelná) funkce x. o(xk) je asymptoticky malá (tj. ------------------------------------------------—< 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 c/c_/?. Příklady: • Internet a WWW: ß = 2,1 • Sociální sítě (např. citační grafy): ß = 3 • Biologické sítě (grafy interakce proteinů): ß = 2,5 Většina grafů reprezentujících reálný svět má ß E (1,4). Power-law grafy - příklad Obrázek: Príklad site ilustrující vedeckou spolupráci - vrcholy reprezentují autory vědeckých prací, hrany společné publikace autorů. PB165 - Grafy 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 neskáluje (Google má > 100.000 serverů) • Decentralizované • Gnutella: Primitivní hledání: záplava • Chytřejší algoritmy Základ výzkumu v oblasti peer to peer sítí s Gnutella • Protokol: záplava dotazů • Ping/Pong • Uzel se hlásí při připojení do sítě a dále průběžně • Připojení: najdi nějakého člena, pošli ping zprávu a sbírej pong zprávy • Dotaz • Údaje o úspěchu se vrací cestou, kterou putoval dotaz Gnutella - charakter sítě • Power-law distribuce stupňů uzlů • Je zcela nezávislá na distribucí uzlů v Internetu • Prohledávání založeno na záplavě • Nastavena délka prohledávání (zpravidla 7) • Vysoce neefektivní • Obrovská spotřeba pásma (kapacity hran) • Obrovský počet redundantních zpráv • Paralelní aktivita uživatelů: lokální zátěž roste lineárně s velikostí sítě Decentralizace • Co můžeme ovlivnit: » Topologii peer to peer sítě • Umístění objektů (replikací) • Power-law sítě • Základní principy: • Je-li distribuce stupně vrcholu pu, pak distribuce stupně sousedů je úměrná kpk. • Uzly mohou snadno uchovávat indexy objektů sousedů • Důsledky • Uzly s vysokým stupněm je možné snadno najít • Tyto uzly drží údaje (index) o velké části sítě Prohledávání v power-law sítích • Náhodná procházka (RW, Random Walk) • Nevracet se do naposled navštíveného uzlu • Náhodná procházka ovlivněná stupněm vrcholu (DS) • Začni v ještě nenavštíveném vrcholu s nejvyšším stupněm • Následně sestupuj na uzly s nižším stupněm • Dokazatelně nejlepší pokrytí Prohledávání v power-law sítích - shrnutí Maximální flexibilita (libovolný algoritmus shody - např. full textové prohledávání) vykoupeno nepříliš vysokou efektivitou » Výhody • Sublineární časová složitost • Nevýhody • Problém s nalezením vzácných objektů • Velmi vysoká zátěž uzlů s vysokým stupněm Modifikace algoritmů Expanze rozsahu • Záplava s postupně narůstajícím TTL (dokud se objekt nenajde nebo nedosáhne hranice) • Smyslem je nezaplavit příliš velkou část sítě okamžitě K-walker • K nezávislých náhodných procházek, žádná záplava • Různé varianty • Např. kontrola: po každých 4 krocích dotaz, zda druzí nenašli cíl Další vlastnosti • Distribuce dotazu • Podíl dotazů na jednotlivé objekty • Uniformní: všechny objekty jsou stejně populární • Power-law: malý počet objektů je mimořádně populární • Replikace • Kopie rozeslány po síti: populárnější objekty se snáze naleznou (a jejich hledání méně zatíží síť) • Replikace zpravidla úměrná popularitě • Optimální replikace je úměrná odmocnině frekvence dotazů Motivace dalších rozšíření • Výhody nestrukturovaných sítí • Robustnost a fault tolerance • Nemají omezení na typ dotazů • Záplava je velmi neefektivní • Náhodné procházky • Lepší než záplava • Stále nepříliš efektivní bez dodatečné podpory (např. algoritmus DS uvedený výše) • Hlavním problémem je rozložení zátěže (příliš mnoho práce dělají uzly s vysokým stupněm) Nový přístup • Replikace přes sousedy • Adaptace topologie • Zajistit, aby většina uzlů byla blízko uzlům s vysokým stupněm • Dynamická adaptace » Každý uzel se snaží zlepšit své sousedy • Podle posledních dotazů žádá konkrétní uzly, zda jej nevezmou za své sousedy » Řízení toku • Modifikace protokolu prohledávání • Náhodná procházka přes uzly s vysokou kapacitou (ne stupněm) • Neexistuje souvislost mezi kapacitou a stupněm uzlu Řízení toku • Výběr uzlu ovlivněn existencí tokenu • Tokeny přidělovány podle kapacity uzlů • Důvěryhodnost: sděluje uzel korektně svou kapacitu? • Při prohledávání se soustřeď na sousedy s největší kapacitou a volným tokenem • Tímto způsobem přispíváme k dynamickému rozložení zátěže Shrnutí » Hlavní komponenty úspěšného prohledávání • Vlastní algoritmus prohledávání » Topologie (překryvová síť) • Strategie tvorby replik • Řízení toku • Všechny tyto komponenty lze ovlivnit • Topologie a replikace jsou ovlivněny agregovaným chováním uživatelů • Stále nedostatečné pro řídce se vyskytující objekty • Distributed hash tables (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 • Hash tabulky v p2p sítích: hledáme data podle klíče 9 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 • 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 Nejrozšířenější jednoduchá implementace: Chord • Velmi populární (více jak 3000 citací). • Překryvová síť: orientovaná kružnice • Uzly spojeny do orientované kružnice • Každý uzel zná svého předchůdce a následníka • Klíče i uzly hashovány SHA-1 (160 bitové ID), identifikátory jsou rovnoměrně rozloženy po celém prostoru • Klíče jsou přiřazeny uzlům s použitím konzistentního hashování • Náhodnost: Každý uzel dostane zhruba stejný počet objektů • Lokalita: Přidání či ubrání uzlu znamená, že 0(1/N) klíčů získá nové přiřazení uzlům • Vlastní vyhledávání: • Složitost 0(log/V) vyměněných zpráv je možné dosáhnout při znalosti jen 0(log A/) uzlů (plus předchůdce a následníka uzlu, který iniciuje hledání) □ g - = ^•00*0 83 • Naivní: • Pošlu dotaz předchůdci nebo následníku (podle identifikátoru); rekurzivně pokračuji • Možnost optimalizace: 9 Každý uzel má tzv. finger table • Obsahuje log2 n — 1 položek (n je počet uzlů v Chord síti) • Každá položka nese číslo uzlu, na němž je k + 2'~1-tý klíč (k je identifikátor aktuálního uzlu). • Vyhledávání • Nalezni v tabulce uzel, který bud obsahuje klíč nebo předchází uzlu, který klíč obsahuje. • Přejdi na tento uzel a pokračuj stejným způsobem • Celkem 0(log/V) přechodů (zpráv) □ g - = ■=•00*0 Chord - příklad -^ Key 6 Key 2 & • Striktní algoritmus • Nový uzel musí nalézt svého předchůdce, následníka a naplnit finger tabulku • Musí rovněž oznámit svou existenci všem uzlům, kteří by na něj měli ukazovat ze své finger tabulky • Zvládnutelné v 0(log/V) čase, ale velmi složitým protokolem. • Relaxovaný algoritmus • Využívá toho, že údaje ve finger tabulce nemusí být přesné • V nejhorším případě se prohledávání redukuje na naivní algoritmus • Stabilizační protokol: přepočtení finger tabulky (periodicky každý uzel) • Přidání uzlu: nalezne následníka a spustí stabilizační protokol Chord - reakce na výpadky uzlů • Replikací • Místo jednoho následníka si držíme r následníků • Alternativní cesty • Pokud uzel nepřebere hledání, využij předchozí uzel z finger tabulky nebo uzel s nejbližší replikou Hybridní přístup • DHT pro méně časté objekty • Náhodná procházka pro populární objekty Gnutella a vzácné objekty: • 41% dotazů nalezen jen méně jak 10 objektů • 18% dotazů nenalezne žádný objekt (přitom jen 6% dotazů vedlo na neexistující objekty) Nutno identifikovat vzácné objekty a ty zpřístupnit přes DHT • Také možné časové omezení: • Jestli náhodná procházka nenalezne objekt do 30 s, přepni na DHT