WikiDer > BATON Overlay

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) Эта статья включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшать эта статья введение более точные цитаты. (Ноябрь 2018) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья в значительной степени или полностью полагается на один источник. Соответствующее обсуждение можно найти на страница обсуждения. Пожалуйста помоги улучшить эту статью путем введения цитаты к дополнительным источникам. Найдите источники: "BATON Overlay" – Новости · газеты · книги · ученый · JSTOR (Ноябрь 2018) Эта статья содержит контент, который написан как Реклама. Пожалуйста помоги Улучши это путем удаления рекламный контент и неуместно внешняя ссылка, а также путем добавления энциклопедического содержания, написанного с нейтральная точка зрения. (Ноябрь 2018) (Узнайте, как и когда удалить этот шаблон сообщения) Тема этой статьи может не соответствовать Википедии общее руководство по известности. Пожалуйста, помогите установить известность, указав надежные вторичные источники которые независимый темы и предоставить подробное ее освещение, помимо банального упоминания. Если известность не может быть установлена, статья, вероятно, будет слился, перенаправлен, или же удалено. Найдите источники: "BATON Overlay" – Новости · газеты · книги · ученый · JSTOR (Ноябрь 2018) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

BATON, BAlanced Tree Over-Lay Network, представляет собой распределенную древовидную структуру для пиринговый (P2P) системы. В отличие от других оверлеев, в которых используется распределенная хеш-таблица (DHT), например, в Аккорд В системе BATON одноранговые узлы организуются в распределенное дерево для поддержки поиска по диапазону. Кроме того, BATON пытается сохранить дерево сбалансированным образом, поскольку AVL дерево. Следовательно, стоимость поиска ограничена ${displaystyle O (log N)}$.

Архитектура

BATON - это двоичное дерево. Каждый узел в BATON поддерживает четыре типа ссылок:

1. ссылка на его родительский узел
2. ссылки на его дочерние узлы
3. ссылки на соседние узлы по порядку
4. ссылки на узлы маршрутизации на том же уровне

На каждом уровне дерева узел назван по его положению в дереве. Например, узел час называется 3: 0, узел я называется 3: 1 и узел п назван 4: 6. Для узла в позиции ${displaystyle p}$, он заполнит свою левую таблицу маршрутизации узлами в позиции ${displaystyle p-2 ^ {x}}$ для любого действительного ${displaystyle xgeq 0}$ и заполните его правую таблицу маршрутизации узлами в позиции ${displaystyle p + 2 ^ {y}}$ для любого действительного ${displaystyle ygeq 0}$.

Присоединение к узлу и выход из него

Запрос на присоединение нового узла всегда будет перенаправлен на листовой узел. Конечный узел проверит, заполнена ли таблица маршрутизации. Если таблица маршрутизации заполнена, этот уровень заполнен узлами, и конечный узел может принять новый узел в качестве своего дочернего для создания узла нового уровня. В противном случае он должен переслать новый узел, чтобы занять одну из пустых позиций.

Когда узел хочет покинуть сеть, он должен обновить таблицы маршрутизации своего родительского узла, дочерних узлов, соседних узлов и узлов маршрутизации. Если этот узел является листовым, он может безопасно покинуть сеть. В противном случае он должен найти листовой узел, чтобы заменить его позицию.

Маршрутизация

В BATON каждый узел поддерживает непрерывное пространство ключей. Как только новый узел присоединяется к нему в качестве дочернего, он разделяет свое пространство и назначает половину его дочернему элементу. Таким способом разделения, если мы путешествуем по дереву по порядку, мы можем искать все пространство в порядке возрастания. Вот почему BATON поддерживает запросы диапазона.

Для запроса диапазона q BATON сначала определяет его левую границу q.low. Затем процесс поиска будет перемещаться по дереву по порядку (по соседней ссылке), пока не достигнет верхней границы q.up. Для поиска единственного ключа BATON использует стратегию маршрутизации, аналогичную Аккорд. Во-первых, запрос направляется на самые дальние узлы маршрутизации, которые не перехватывают нажатие клавиши. Если таких узлов маршрутизации не существует, используется родительская ссылка, дочерняя ссылка или смежная ссылка.

Реструктуризация

Когда узел x принимает присоединяющийся узел y в качестве своего дочернего элемента и обнаруживает, что баланс дерева нарушен, он инициирует процесс реструктуризации. Не теряя общности, предположим, что эта реструктуризация идет вправо. Предположим, что y присоединяется как левый потомок x. Чтобы перебалансировать систему, x уведомляет y о замене своей позиции и уведомляет свой правый соседний узел z, что x заменит положение z. Затем z проверяет свой правый соседний узел t, чтобы убедиться, что его левый дочерний элемент пуст. Если это так, и добавление дочернего элемента к t не влияет на баланс дерева, z принимает положение левого дочернего элемента t в качестве своей новой позиции, и процесс реструктуризации останавливается. Если левый дочерний элемент t заполнен или t не может принять x в качестве своего левого дочернего элемента, не нарушая свойства баланса, z занимает позицию t, в то время как t необходимо найти новую позицию для себя, перейдя к своему правому соседнему узлу.

Балансировка нагрузки

BATON использует два типа стратегии балансировки нагрузки. Как только узел n обнаруживает, что он перегружен,

1. Если его левый или правый соседний узел слегка загружен, этот узел будет передавать некоторые данные в соседний узел, чтобы снизить свою нагрузку.
2. Если его соседние узлы не могут разделить нагрузку, узел вызовет процесс, чтобы найти случайно загруженный узел в сети. Легко загруженный узел покидает свое исходное положение и присоединяется как дочерний элемент перегруженного узла, чтобы взять на себя часть его данных. Может быть запущен процесс реструктуризации.

Смотрите также

• МОЖЕТ
• Кондитерские изделия

Рекомендации

• Х. В. Джагадиш; Бенг Чин Оои и Куанг Хиеу Ву (2005). «BATON: сбалансированная древовидная структура для одноранговых сетей» (PDF). Материалы 31-й международной конференции по очень большим базам данных, Тронхейм, Норвегия. С. 661–672. ISBN 1-59593-154-6.

дальнейшее чтение

• Х. В. Джагадиш; Бенг Чин Оои; Куанг Хиеу Ву; Жун Чжан и Аойин Чжоу (2006). «VBI-Tree: одноранговая структура для поддержки многомерных схем индексирования» (PDF). Материалы 22-й Международной конференции по инженерии данных. п. 34. ISBN 0-7695-2570-9.
• Х. В. Джагадиш; Бенг Чин Оои; Киан-Ли Тан; Куанг Хиеу Ву и Ронг Чжан (2006). «Ускорение поиска в одноранговых сетях с многосторонней древовидной структурой» (PDF). Материалы международной конференции ACM SIGMOD 2006 г. по управлению данными. С. 1–12. ISBN 1-59593-434-0.
• Шиюань Ван; Бенг Чин Оои; Тунг, A.K.H. И Личжэнь Сюй (2007). «Эффективная обработка запросов Skyline в одноранговых сетях» (PDF). Материалы 22-й Международной конференции по инженерии данных. С. 1126–1135. ISBN 1-4244-0803-2.
• А. Гонсалес-Бельтран; П. Миллиган и П. Сейдж (2008). «Диапазон запросов по графам дерева пропуска» (PDF). Компьютерные коммуникации. С. 358–374. ISSN 0140-3664.

внешняя ссылка

• Сайт проекта BestPeer