33 - Sítě Peer-to-Peer: vlastnosti, chování, způsoby směrování. Strukturované a nestrukturované sítě.
pondělí 21. května 2018
17:25
P2P sítě
Logická síť: síť nad existující síťovou infrastrukturou. Definuje propojení uzlů, směrování, vyhledávání informací. Je základem P2P sítí.
P2P síť: Dynamický soubor nezávislých uzlů (peers), které jsou propojeny a jejichž zdroje (objekty) jsou k dispozici ostatním uzlům v této síti.
Typy:
Pravé sítě: odebrání libovolného uzlu ze sítě nemá vliv na ztrátu schopnosti sítě poskytovat služby. 
Hybridní sítě: pro svou činnost využívají centrální uzel pro poskytování části služeb (autentizace, indexování...)
Vlastnosti:
Spolehlivost: spolehlivost roste s rostoucím počtem uzlů. Kopie objektů jsou uloženy ve více objektech.
Životnost: Doba života uzlu je krátká a neodhadnutelná. Problem s garancí služby.
Samo-organizovatelnost: Decentralizovaná topologie, kde spolu uzly spolupracují na vytvoření a udržování. Každý uzel je zodpovědný za část zdrojů a svůj lokální stav
Autonomní chování: každý uzel se chová podle svého nejlepšího úsudku. Rozhodování je lokální a nepredikovatelné.
Architektura P2P sítě - P2P síť je šestice:
Jmenný prostor identifikátorů I
Množina uzlů P
Množina zdrojů R
Mapování zdrojů na identifikátory Fr
Mapování uzlů na indentifikátory Fp
Struktura logické sítě
Metrika blízkosti: Jmenný prostor obsahuje metriku blízkosti d (I x I -> R), která slouží ke sdružování uzlů podle vzdálenosti a lokalizaci služeb. Jedná se o presudometriku (musí být nezáporná, vzdálenost je 0 právě tehdy pokud měříme vzdálenost mezi stejným objektem). 
Funkce M (funkce Management): definuje odpovědnost uzlů z P za konkrétní identifikátory (M: I -> R^2). Identifikátoru zdroje je přiřazena množina uzlů spravující zdroj. M se dynamicky mění, jak se mění uzly. 
Směrování
Struktura sítě je popsána orientovaným grafem. Každý uzel obsahuje lokální směrovací tabulku, která je součástí globální konfigurace sítě. Tabulka obsahuje množinu sousedních uzlů a hran k nim.
Relace sousedství N: popisuje strukturu sítě. N: P -> 2^P
Směrování: distribuovaný proces nalazení cesty v síti na základě lokálních znalostí. R: P X I -> 2^P
Nestrukturované sítě P2P
Neexistuje struktura uložení informace: objekt je uložen v náhodně vybraném uzlu.  Uzly mohou posílat dotazy sousedním uzlům. Nebezpečí zacyklení (řeší se TTL). Směrování probíhá podle identifikátoru. Samoorganizující. Nový objekt se může vložit kamkoliv do sítě. 
Záplava (flooding): uzel pošle dotaz všem sousedům. Pokud soused nemá objekt, tak znovu pošle všem sousedům. 
Rozšiřující se kruh: podobné jako záplava, ale dotaz pošlu s malým TTL. Pokud objekt není nalezen, tak pošlu dotaz s vyšším TTL...
Náhodný průchod: zpráva zaslána náhodným sousedům (kromě toho uzlu odkud dotaz přišel).
Uzel U je lokálním minimem pro objekt O, pokud je ID Učka nejbližšší mezi sousedy Očka do vzdálenosti h kroků.
Potřeba metrika vzdálenosti mezi uzly
Algoritmus uložení objektu x do uzlu w: 
Mějme hodnotu walk-length. Nejdříve procházíme síť náhodným průchodem od vstupního bodu dokud walk-length > 0.
Poté vyhledáme z aktuálního uzlu, do kterého jsme se dostali, lokální minimum k uzlu w
Do daného uzlu uložíme objekt x
Strukturované sítě P2P
Využívají distribuované směrovací algoritmy. 
Síť Pastry: (podle slajdů z roku 2017, v roce 2018 se probírala síť Kademlia)
Jmenný prostor tvoří identifikátory uzlů a objektů
Směruje se do uzlu, kde NodeID je numericky nejblíže klíči. 
Každý uzel obsahuje:
Náhodně generované NodeID
Tabulku listů: uzly co jsou numericky nejblíže (LT). Používá se pro směrování.
Tabulka sousedů: uzly co jsou vzdálenostně nejbližší (NT). Používá se pro lokalizaci.
Směrovací tabulku R, sliuží pro hledání cesty.
Směrování zprávy s klíčem D v uzlu A:
Pokud se klíč == NodeID, tak ulož zde
Pokud je D v LT, pošli ho do nejbližšího uzlu v LT
Jinak najdi ve směrovací tabulce řádek s nejdelším společným prefixem a pokud je odpovídající hodnota neprázdná, pošli to tam
Jinak vyber uzel, která má nejdelší společný prefix s D a nižšší vzdálenost než aktuální uzel
Připojení nového uzlu X:
Najdi nejbližší uzel A (třeba rozšiřující se kruh)
A přepošle zprávu k Z, které je numericky nejblže
Uzel X si inicializuje tabulky takto: LTx = LTz a NTx = NTa
Uzel X přepošle svoje tabulky okolním uzlům
Odpojení uzlu X:
Uzel Y kontaktuje uzel z LT s numericky nejvyšším NodeID a požádá ho o zaslání TL a vybere si náhradníka za X.
Uzel Y vyhledá další záznam na řádku ve směrovací tabulce, kde byl X
Uzel Y požádá ostatní své sousedy o zaslání tabulek sousedů a z nich vybere náhraníka za X do NT
Notes*
Otazka (predmet) (okruh): Sítě Peer-to-Peer (P2P), Milgramův problém malého světa, model sítě P2P, směrování v P2P sítích, strukturované a nestrukturované sítě.
Kdo me primarne zkousel: Matoušek Petr, Ing., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Na papirku bylo smerovani v P2P sitich. Dr. Matousek me nenechal mluvit ani vterinu a hned zacal otazkou. Chtel vedet definici P2P, z ceho se sklada. Rekl jsem tedy ze jde o dynamickou mnozinu nezavislych uzlu, ktere jsou propojeny siti a poskytujou nejake zdroje. Dale jake zdroje to mohou byt, ze sit je overlay na IP a jeste neco o jmennych prostorech. Zeptal se na metriku, tu jsem mu zadefinoval a rekl ty tri podminky z MATu. To se mu ale nelibilo, ze pry je v P2P pouzivana nejaka pseudometrika a neplati tam trojuhelnikova nerovnost. Potom uz se zacal ptat na samotne smerovani, nejprve obecne, potom jak je to ve strukturovanych a nestrukturovanych sitich. Mel jsem naucene vyhledavani v nestrukturovanych, ale vubec me k tomu nepustil. Ke vsemu jsem neco rekl, ackoliv moje odpovedi asi nebyly 100%, neb k ni Dr. Matousek vzdy neco dodal. Nakonec se me zeptal za jak dlouho nalezneme zdroj nahodnym pruchodem. Vubec jsem netusil, snazil jsem se to obkecat ale chtel konkretni cislo, tak jsem nejake placl. Prozradil mi, ze je to 7 podle Milgrama. Toho jsem znal, ale jeho otazku jsem nepochopil (nechapu ji doted).
From <[link]> 
 PDS - Site Peer-to-Peer, 39
Kdo me primarne zkousel: Hladká Eva, doc. RNDr., Ph.D. FI MUNI, Brno
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Bylo tam obecne popsat, smerovani a strukturovane vs nestrukturovane. Takze jsem zacal obecne, ze je to sit na existujici infrastrukturou, kde se dynamicky uzly pripojuji a odpojuji a nabizi nejake zdroje. Nasledovala otazka na ktere vrstve tyto site funguji, takze jsem rekl, ze existujici vrstva funguje na L1 az L4 takze p2p musi byt na aplikacni vrstve. Kyvali. Pak nejake zakladni rozdili mezi strukturovanyma sitema a nestrukturovanyma. O tech nestrukturovanych chteli slyset, ze jsou samoorganizujici a ze se nemusi resit nejaky zarazeni do site jako u strukturovanych. Jeste se ptali na hybrdidni site, na co je dobry ten centralni prvek. Celkove to bylo prijmne, docentka doplnovala, kdyz jsem se u neceho zasekl.
Vysledna A.
From <[link]> 