4824
правки
P2P: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 69: | Строка 69: | ||
'''Оверлейные сети с поддержкой диапазонных запросов''' | '''Оверлейные сети с поддержкой диапазонных запросов''' | ||
Один из недостатков сетей с распределенной хэш-таблицей (DHT) заключается в том, что они поддерживают только точный поиск ключей, а значит, плохо решают задачи поиска диапазона ключей или нечеткого поиска, например, поиска любого ключа, соответствующего некоторому префиксу. '''SkipGraphs''' [4] и схема '''SkipNet''' [19] от Microsoft (проект Herald) независимо друг от друга разработали аналогичную сеть DHT на основе рандомизированного списка пропусков [28], которая поддерживает запросы по диапазону в распределенной сети. Подход в обеих этих сетях заключается в объединении объектов в двухсвязный список, отсортированный по именам объектов, над которым строятся «короткие» указатели. Указатели от каждого объекта переходят на геометрическую последовательность расстояний в отсортированном списке, то есть первый указатель переходит через два элемента, второй – через четыре, и так далее, вплоть до указателя <math>log \; n - 1</math>, который переходит через половину списка. Логарифмический, сбалансированный по нагрузке поиск достигается в этой схеме таким же образом, как и в Chord. Поскольку пространство идентификаторов сортируется по именам объектов, а не по хэш-идентификаторам, диапазоны объектов можно эффективно сканировать, просто переходя к наименьшему значению в диапазоне; остальные узлы диапазона располагаются смежно вдоль кольца. | Один из недостатков сетей с распределенной хэш-таблицей (DHT) заключается в том, что они поддерживают только точный поиск ключей, а значит, плохо решают задачи поиска диапазона ключей или нечеткого поиска, например, поиска любого ключа, соответствующего некоторому префиксу. '''SkipGraphs''' [4] и схема '''SkipNet''' [19] от Microsoft (проект Herald) независимо друг от друга разработали аналогичную сеть DHT на основе рандомизированного списка пропусков [28], которая поддерживает запросы по диапазону в распределенной сети. Подход в обеих этих сетях заключается в объединении объектов в двухсвязный список, отсортированный по именам объектов, над которым строятся «короткие» указатели. Указатели от каждого объекта переходят на геометрическую последовательность расстояний в отсортированном списке, то есть первый указатель переходит через два элемента, второй – через четыре, и так далее, вплоть до указателя <math>log \; n - 1</math>, который переходит через половину списка. Логарифмический, сбалансированный по нагрузке поиск достигается в этой схеме таким же образом, как и в Chord. Поскольку пространство идентификаторов сортируется по именам объектов, а не по хэш-идентификаторам, диапазоны объектов можно эффективно сканировать, просто переходя к наименьшему значению в диапазоне; остальные узлы диапазона располагаются смежно вдоль кольца. | ||
| Строка 79: | Строка 80: | ||
'''Обзор сетей, не учитывающих локальность''' | '''Обзор сетей, не учитывающих локальность''' | ||
Каждая из упомянутых выше сетей отличается одним или несколькими следующими свойствами: (интуитивно) эмулируемая топология; ожидаемое количество '''переходов''', необходимых для достижения цели; '''степень''' каждого узла. Эти свойства сведены в таблице 1. | Каждая из упомянутых выше сетей отличается одним или несколькими следующими свойствами: (интуитивно) эмулируемая '''топология'''; ожидаемое количество '''переходов''', необходимых для достижения цели; '''степень''' каждого узла. Эти свойства сведены в таблице 1. | ||
| Строка 122: | Строка 123: | ||
'''Осведомленность о локальности''' | '''Осведомленность о локальности''' | ||
Проблема с перечисленными выше подходами заключается в том, что они игнорируют близость узлов в базовых сетях и позволяют «прыгать» туда-сюда через большие физические расстояния в поисках контента. Недавние исследования масштабируемых сетей обмена контентом [ ] показали, что до 80% запросов в Интернет могут быть удовлетворены локальными узлами в пределах собственной организации автора запроса. Поэтому даже один далекий переход может оказаться слишком дорогим. Следующие системы учитывают отношения близости между узлами, чтобы обеспечить осведомленность о локальности, то есть чтобы стоимость поиска была пропорциональна реальному расстоянию между взаимодействующими сторонами. | Проблема с перечисленными выше подходами заключается в том, что они игнорируют близость узлов в базовых сетях и позволяют «прыгать» туда-сюда через большие физические расстояния в поисках контента. Недавние исследования масштабируемых сетей обмена контентом [17] показали, что до 80% запросов в Интернет могут быть удовлетворены локальными узлами в пределах собственной организации автора запроса. Поэтому даже один далекий переход может оказаться слишком дорогим. Следующие системы учитывают отношения близости между узлами, чтобы обеспечить осведомленность о локальности, то есть чтобы стоимость поиска была пропорциональна реальному расстоянию между взаимодействующими сторонами. | ||
'''Сети с ограниченным ростом ''' | '''Сети с ограниченным ростом ''' | ||
Несколько сетей поиска с учетом локальности были построены на основе протокола исправления битов, взятого из фундаментальной работы Плакстона и коллег [27] (PRR). Модель сети с ограниченным ростом, для которой предназначена эта схема, рассматривает сеть как метрическое пространство и предполагает, что плотность узлов в разных частях сети не слишком сильно различается. Схема поиска PRR [27] использует префиксную маршрутизацию, аналогичную Chord. Она отличается от Chord тем, что ссылка для «переворачивания» i-го бита идентификатора соединяется с любым узлом, чей префикс длины i совпадает со следующим переходом. Таким образом, схема отдает предпочтение ближайшему узлу в сети. Эта стратегия позволяет построить геометрическую маршрутизацию, особенностью которой является то, что шаги маршрутизации по направлению к цели увеличиваются в геометрической прогрессии. Это достигается за счет большой гибкости в выборе связей для каждого префикса в начале маршрута и сужения их списка по мере продвижения по маршруту. В результате получается схема оверлейной маршрутизации, которая находит любую цель с затратами, пропорциональными кратчайшему расстоянию до нее. | Несколько сетей поиска с учетом локальности были построены на основе протокола исправления битов, взятого из фундаментальной работы Плакстона и коллег [27] (PRR). Модель ''сети с ограниченным ростом'', для которой предназначена эта схема, рассматривает сеть как метрическое пространство и предполагает, что плотность узлов в разных частях сети не слишком сильно различается. Схема поиска PRR [27] использует префиксную маршрутизацию, аналогичную Chord. Она отличается от Chord тем, что ссылка для «переворачивания» <math>i</math>-го бита идентификатора соединяется с любым узлом, чей префикс длины <math>i</math> совпадает со следующим переходом. Таким образом, схема отдает предпочтение ближайшему узлу в сети. Эта стратегия позволяет построить ''геометрическую маршрутизацию'', особенностью которой является то, что шаги маршрутизации по направлению к цели увеличиваются в геометрической прогрессии. Это достигается за счет большой гибкости в выборе связей для каждого префикса в начале маршрута и сужения их списка по мере продвижения по маршруту. В результате получается схема оверлейной маршрутизации, которая находит любую цель с затратами, пропорциональными кратчайшему расстоянию до нее. | ||
К системам, использующим алгоритм PRR, относятся Pastry [33], Tapestry [36] и Bamboo [32]. Очень близким вариантом является Kademlia [ ], в которой связи симметричны. Стоит отметить, что схема LAND [2] улучшает схем у PRR, обеспечивая почти оптимальную гарантию локальности; однако LAND не была развернута на практике. | К системам, использующим алгоритм PRR, относятся '''Pastry''' [33], '''Tapestry''' [36] и '''Bamboo''' [32]. Очень близким вариантом является '''Kademlia''' [25], в которой связи симметричны. Стоит отметить, что схема LAND [2] улучшает схем у PRR, обеспечивая почти оптимальную гарантию локальности; однако LAND не была развернута на практике. | ||
== Применение == | == Применение == | ||
