4824
правки
P2P: различия между версиями
Материал из WEGA
м
→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| (не показаны 2 промежуточные версии этого же участника) | |||
| Строка 65: | Строка 65: | ||
'''Оверлейная маршрутизация, вдохновленная сетями типа «Мир тесен»''' | '''Оверлейная маршрутизация, вдохновленная сетями типа «Мир тесен»''' | ||
Алгоритм '''Symphony''' [24] эмулирует маршрутизацию в «тесном» мире. Узлы имеют <math>k</math> связей с узлами, виртуальные идентификаторы которых выбираются случайным образом в соответствии с маршрутизируемым распределением тесного мира [22]. Ожидается, что при <math>k</math> связях Symphony найдет цель за <math>log^2/k</math> переходов. | Алгоритм '''Symphony''' [24] эмулирует маршрутизацию в «тесном» мире. Узлы имеют <math>k</math> связей с узлами, виртуальные идентификаторы которых выбираются случайным образом в соответствии с маршрутизируемым распределением тесного мира [22]. Ожидается, что при <math>k</math> связях Symphony найдет цель за <math>log^2 \; n/k</math> переходов. | ||
'''Оверлейные сети с поддержкой диапазонных запросов''' | '''Оверлейные сети с поддержкой диапазонных запросов''' | ||
Один из недостатков сетей с распределенной хэш-таблицей (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. | ||
Оверлейная схема поиска | {| class="wikitable" style="text-align:center" | ||
Chord | ! Оверлейная схема поиска !! Похожая топология !! Число переходов !! Степень | ||
Viceroy Бабочка log n 5 | |- | ||
AAABMP, сеть с делением расстояний пополам, Koorde, D2B De Bruijn log n 4 | | Chord | ||
Symphony «Тесный мир» | | Гиперкуб | ||
| log n | |||
CAN Тор | | log n | ||
|- | |||
| Viceroy | |||
| Бабочка | |||
| log n | |||
| 5 | |||
|- | |||
| AAABMP, сеть с делением расстояний пополам, Koorde, D2B | |||
| De Bruijn | |||
| log n | |||
| 4 | |||
|- | |||
| Symphony | |||
| «Тесный мир» | |||
| <math>log^2 \; n/k</math> | |||
| k | |||
|- | |||
| SkipGraphs/SkipNet | |||
| Список пропусков | |||
| log n | |||
| log n | |||
|- | |||
| CAN | |||
| Тор | |||
| <math>dn^{1/d}</math> | |||
| d | |||
|} | |||
Таблица 1 | Таблица 1. Сравнение различных показателей схем поиска, не обладающих осведомленностью о локальности | ||
Сравнение различных показателей схем поиска, не обладающих осведомленностью о локальности | |||
'''Осведомленность о локальности''' | '''Осведомленность о локальности''' | ||
Проблема с перечисленными выше подходами заключается в том, что они игнорируют близость узлов в базовых сетях и позволяют «прыгать» туда-сюда через большие физические расстояния в поисках контента. Недавние исследования масштабируемых сетей обмена контентом [ ] показали, что до 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 не была развернута на практике. | ||
== Применение == | == Применение == | ||
'''Кэширование''' | '''Кэширование''' | ||
Сеть Coral [ ] из Нью-Йоркского университета, построенная на основе DSHT [15], функционирует примерно с 2004 года. Она предоставляет бесплатные услуги по доставке контента на базе распределенного испытательного стенда PlanetLab [ ], аналогичные коммерческим услугам, предлагаемым сетью Akamai. Подписчики используют ее для предоставления нескольких быстрых точек доступа к контенту, который они хотят опубликовать в Сети. | Сеть Coral [14] из Нью-Йоркского университета, построенная на основе DSHT [15], функционирует примерно с 2004 года. Она предоставляет бесплатные услуги по доставке контента на базе распределенного испытательного стенда PlanetLab [9], аналогичные коммерческим услугам, предлагаемым сетью Akamai. Подписчики используют ее для предоставления нескольких быстрых точек доступа к контенту, который они хотят опубликовать в Сети. | ||
| Строка 118: | Строка 144: | ||
'''Многоадресная рассылка''' | '''Многоадресная рассылка''' | ||
В некоторых работах служба уведомления о событиях или публикации и подписки развертывается поверх существующего оверлея маршрутизации путем построения многоадресных путей с обратной маршрутизацией от одной «цели» ко всем «источникам». Например, к многоадресным системам, построенным таким образом, относятся сеть Bayeux [ ], построенная на базе Tapestry [36], и SCRIBE [ ], построенная на Pastry. Чтобы опубликовать файл, источник рекламирует с помощью «затопления» кортеж, содержащий семантическое имя сеанса многоадресной рассылки и уникальный идентификатор. Этот кортеж хешируется для получения идентификатора узла, который становится корневым узлом сеанса. Каждый узел может присоединиться к сеансу многоадресной рассылки, отправив сообщение корневому узлу. Узлы по пути следования сохраняют информацию о членстве, так что дерево многоадресной рассылки формируется в обратном направлении. Содержимое файла (и любые обновления) распространяется по дереву путем затопления. Narada [ ] построена на той же общей архитектуре, но отличается выбором связей и обслуживанием данных. | В некоторых работах служба уведомления о событиях или публикации и подписки развертывается поверх существующего оверлея маршрутизации путем построения многоадресных путей с обратной маршрутизацией от одной «цели» ко всем «источникам». Например, к многоадресным системам, построенным таким образом, относятся сеть Bayeux [38], построенная на базе Tapestry [36], и SCRIBE [5], построенная на Pastry. Чтобы опубликовать файл, источник рекламирует с помощью «затопления» кортеж, содержащий семантическое имя сеанса многоадресной рассылки и уникальный идентификатор. Этот кортеж хешируется для получения идентификатора узла, который становится корневым узлом сеанса. Каждый узел может присоединиться к сеансу многоадресной рассылки, отправив сообщение корневому узлу. Узлы по пути следования сохраняют информацию о членстве, так что дерево многоадресной рассылки формируется в обратном направлении. Содержимое файла (и любые обновления) распространяется по дереву путем затопления. Narada [8] построена на той же общей архитектуре, но отличается выбором связей и обслуживанием данных. | ||
'''Инфраструктура маршрутизации''' | '''Инфраструктура маршрутизации''' | ||
DHT может служить для хранения маршрутизации и (потенциально динамической) информации о местоположении виртуальных имен хостов. Эта идея была использована в ряде проектов. Система именования для Интернета под названием CoDoNS [30] была построена в Корнельском университете на основе оверлея BeeHive [29]. CoDoNS обеспечивает безопасность и является возможной заменой системы доменных имен, которая в настоящее время служит для поиска имен хостов. Поддержка виртуальных сетевых адресов IPv6 обеспечивается в [ ] путем сопоставления имен с их актуальными, достижимыми адресами IPv4. Инфраструктура Internet Indirection Infrastructure [34], созданная в Калифорнийском университете в Беркли, поддерживает виртуальные адреса хостов Интернета, обеспечивая возможность мобильности. | DHT может служить для хранения маршрутизации и (потенциально динамической) информации о местоположении виртуальных имен хостов. Эта идея была использована в ряде проектов. Система именования для Интернета под названием CoDoNS [30] была построена в Корнельском университете на основе оверлея BeeHive [29]. CoDoNS обеспечивает безопасность и является возможной заменой системы доменных имен, которая в настоящее время служит для поиска имен хостов. Поддержка виртуальных сетевых адресов IPv6 обеспечивается в [37] путем сопоставления имен с их актуальными, достижимыми адресами IPv4. Инфраструктура Internet Indirection Infrastructure [34], созданная в Калифорнийском университете в Беркли, поддерживает виртуальные адреса хостов Интернета, обеспечивая возможность мобильности. | ||
| Строка 134: | Строка 160: | ||
Очень популярной сетью распространения файлов является система BitTorrent [10]. Узлы в BitTorrent делятся на узлы- | Очень популярной сетью распространения файлов является система BitTorrent [10]. Узлы в BitTorrent делятся на узлы-''сиды'' (источники) и ''клиентов''. Узлы-сиды содержат желаемый контент в полном объеме (либо являясь оригинальными поставщиками, либо недавно загрузив его). Клиентские узлы соединяются с одним или несколькими сидами, а также с узлом-''трекером'', целью которого является отслеживание клиентов, загружающих контент в данный момент. Каждый клиент выбирает группу (в настоящее время размером около 20) других клиентов, осуществляющих загрузку, и обменивается с ними фрагментами данных, полученных от сидов. BitTorrent использует несколько сложных стратегий для выбора того, какие куски запрашивать у других клиентов, чтобы добиться справедливого распределения нагрузки при раздаче контента и, в то же время, обеспечить высокую скорость загрузки. | ||
| Строка 143: | Строка 169: | ||
Недавно ряд работ Microsoft Research продемонстрировал преимущества сетевого кодирования для эффективной многоадресной рассылки, например [ ] и Avalanche [ ]. Вкратце изложим ключевые идеи, лежащие в их основе. | Недавно ряд работ Microsoft Research продемонстрировал преимущества сетевого кодирования для эффективной многоадресной рассылки, например [7] и Avalanche [16]. Вкратце изложим ключевые идеи, лежащие в их основе. | ||
