BATON Překrytí - BATON Overlay

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Listopadu 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) tento článek obsahuje obsah, který je napsán jako reklama. Prosím pomozte vylepši to odstraněním propagační obsah a nevhodné externí odkazy, a přidáním encyklopedického obsahu napsaného z a neutrální hledisko. (Listopadu 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) Téma tohoto článku nemusí splňovat požadavky Wikipedie obecný pokyn k notabilitě. Pomozte prosím určit notabilitu citováním spolehlivé sekundární zdroje to jsou nezávislý tématu a poskytnout jeho významné pokrytí nad rámec pouhé triviální zmínky. Pokud nelze určit významnost, je pravděpodobné, že článek bude sloučeny, přesměrovánnebo smazáno. Najít zdroje: „Překrytí BATON“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Listopadu 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

OBUŠEK„BAlanced Tree Over-lay Network, je distribuovaná stromová struktura pro peer-to-peer (P2P) systémy. Liší se od ostatních překryvů, které používají a distribuovaná hash tabulka (DHT), například v Akord systém, BATON organizuje vrstevníky v distribuovaném stromu na podporu vyhledávání rozsahu. Kromě toho se BATON snaží udržovat strom vyváženě jako Strom AVL. A proto jsou náklady na vyhledávání omezeny ${displaystyle O (log N)}$.

Architektura

BATON je binární strom. Každý uzel v BATONU uchovává čtyři druhy odkazů:

1. odkaz na jeho nadřazený uzel
2. odkazy na jeho podřízené uzly
3. odkazy na sousední uzly v pořadí
4. odkazy na směrovací uzly na stejné úrovni

V každé úrovni stromu je uzel pojmenován podle jeho polohy ve stromu. Například uzel h je pojmenován 3: 0, uzel i je pojmenován 3: 1 a uzel p se jmenuje 4: 6. Pro uzel na pozici ${displaystyle p}$, vyplní svoji směrovací tabulku vlevo uzly na pozici ${displaystyle p-2 ^ {x}}$ pro všechny platné ${displaystyle xgeq 0}$ a vyplňte její pravou směrovací tabulku uzly na pozici ${displaystyle p + 2 ^ {y}}$ pro všechny platné ${displaystyle ygeq 0}$.

Uzel se připojí a odejde

Žádost o připojení nového uzlu bude vždy předána do uzlu listu. Uzel listu zkontroluje, zda je směrovací tabulka plná. Pokud je směrovací tabulka plná, je tato úroveň plná uzlů a listový uzel může přijmout nový uzel jako svůj podřízený a vytvořit nový uzel úrovně. Jinak musí předat nový uzel, aby převzal jednu z prázdných pozic.

Když uzel chce opustit síť, musí aktualizovat směrovací tabulky svého nadřazeného uzlu, podřízených uzlů, sousedních uzlů a směrovacích uzlů. Pokud je tento uzel listovým uzlem, může bezpečně opustit síť. V opačném případě musí najít uzel listu, který nahradí jeho polohu.

Směrování

V BATONu každý uzel udržuje souvislý klíčový prostor. Jakmile se nový uzel připojí jako své dítě, rozdělí svůj prostor a přiřadí jeho polovinu dítěti. Tímto způsobem oddílu, pokud cestujeme stromem v pořadí, můžeme prohledávat celý prostor v sestupném pořadí. Proto BATON podporuje dotazy na rozsah.

U dotazu na rozsah q BATON nejprve vyhledá jeho levou vazbu, q.low. Poté bude proces hledání procházet stromem v pořadí (sousedním odkazem), dokud nedosáhne horní hranice, q.up. Pro vyhledání jednoho klíče provádí BATON podobnou směrovací strategii jako Akord. Nejprve je požadavek směrován do nejvzdálenějších směrovacích uzlů, které nepřekročí klíč. Pokud takové směrovací uzly neexistují, použije se nadřazený odkaz, podřízený odkaz nebo sousední odkaz.

Restrukturalizace

Když uzel x přijme spojující uzel y jako své dítě a zjistí, že je narušena rovnováha stromu, zahájí proces restrukturalizace. Bez ztráty obecnosti předpokládejme, že tato restrukturalizace směřuje doprava. Předpokládejme, že y se připojí jako levé dítě x. Pro vyvážení systému x upozorní y, aby nahradil svou pozici, a upozorní svůj pravý sousední uzel z, že x nahradí pozici z. z potom zkontroluje svůj pravý sousední uzel t, aby zjistil, zda je jeho levé dítě prázdné. Pokud je a přidání dítěte do t neovlivní rovnováhu stromu, z zaujme pozici levého dítěte t jako svou novou pozici a proces restrukturalizace se zastaví. Pokud je levé dítě t plné nebo t nemůže přijmout x jako své levé dítě bez porušení vlastnosti vyvážení, zaujímá z pozici t, zatímco t potřebuje najít novou pozici pro sebe pokračováním do svého pravého sousedního uzlu.

Vyrovnávání zatížení

BATON přijímá dva druhy strategie vyrovnávání zatížení. Jakmile uzel n zjistí, že je přetížen,

1. Pokud je jeho levý nebo pravý sousední uzel lehce načtený, uzel přenese některá data do sousedního uzlu, aby snížil jeho zatížení
2. Pokud jeho sousední uzly nejsou schopny sdílet zátěž, uzel vyvolá proces k nalezení náhodně osvětleného uzlu v síti. Lehce nabitý uzel opouští svou původní polohu a připojuje se jako podřízený přetížený uzel, aby převzal část svých dat. Může být vyvolán proces restrukturalizace.

Viz také

• UMĚT
• Pečivo

Reference

• H. V. Jagadish; Beng Chin Ooi & Quang Hieu Vu (2005). „BATON: vyvážená stromová struktura pro sítě typu peer-to-peer“ (PDF). Sborník z 31. mezinárodní konference o velmi velkých databázích, Trondheim, Norsko. 661–672. ISBN  1-59593-154-6.

Další čtení

• H. V. Jagadish; Beng Chin Ooi; Quang Hieu Vu; Rong Zhang & Aoying Zhou (2006). „VBI-Tree: Peer-to-Peer Framework pro podporu schémat vícerozměrného indexování“ (PDF). Sborník z 22. mezinárodní konference o datovém inženýrství. p. 34. ISBN  0-7695-2570-9.
• H. V. Jagadish; Beng Chin Ooi; Kian-Lee Tan; Quang Hieu Vu & Rong Zhang (2006). „Urychlení vyhledávání v sítích typu peer-to-peer s vícecestnou stromovou strukturou“ (PDF). Sborník příspěvků z mezinárodní konference ACM SIGMOD 2006 o správě dat. s. 1–12. ISBN  1-59593-434-0.
• Shiyuan Wang; Beng Chin Ooi; Tung, A.K.H. & Lizhen Xu (2007). „Efektivní zpracování dotazů na panorama v sítích peer-to-peer“ (PDF). Sborník z 22. mezinárodní konference o datovém inženýrství. str. 1126–1135. ISBN  1-4244-0803-2.
• A. Gonzalez-Beltran; P. Milligan & P. ​​Sage (2008). "Rozsah dotazů přes stromové grafy přeskočení" (PDF). Počítačová komunikace. str. 358–374. ISSN  0140-3664.

externí odkazy

• Webové stránky projektu BestPeer