P2P: различия между версиями

Одним из первых проектов оверлейных сетей был Chord [35], в честь которого названа запись в энциклопедии (2001; Стойка, Моррис, Каргер, Каашук, Балакришнан). Более подробная информация о Chord приведена ниже.

Система Chord была создана в Массачусетском технологическом институте и далее развивалась в рамках проекта IRIS научной установки ядерного синтеза (FNSF) (http://project-iris.net/). Некоторые аспекты дизайна Chord [35] оказали влияние на последующие системы. Кратко поясним основную структуру Chord. Узлы имеют двоичные идентификаторы, назначаемые равномерно случайным образом. Узлы расположены в связанном кольце в соответствии с их виртуальными идентификаторами. Кроме того, каждый узел имеет короткие ссылки на другие узлы вдоль кольца, связывающие узел i с узлом, находящимся на расстоянии 2i от него в пространстве виртуальных идентификаторов. Таким образом, можно постепенно продвигаться к цели, уменьшая расстояние в два раза на каждом шаге. Маршрутизация в среднем требует log n переходов для достижения любой цели в сети, содержащей n узлов. Каждый узел поддерживает примерно log n связей, обеспечивая возможность маршрутизации на геометрически возрастающие расстояния.

Несколько алгоритмов оверлейных сетей были разработаны с целью свести к минимуму объем информации о состоянии сети, хранимой каждым узлом в оверлее. Мы называем состояние, хранимое узлом, его степенью, поскольку она в основном отражает количество связей с другими узлами. Viceroy [23] стала первым примером динамической сети, в которой каждый узел хранит только пять связей с другими узлами сети и прокладывает маршрут к любому другому узлу за логарифмическое число переходов – log n для сети из узлов. Viceroy обеспечил динамическую эмуляцию сети типа «бабочка» (см. в [ ] справочное описание сетей взаимосвязей типа «бабочка»). Позже появилось несколько эмуляций сетей De Bruijn, включая базовую сеть Абрахама и др. (AAABMP) [ ], сеть с делением расстояний пополам [26], D2B [13] и Koorde [ ]. Оверлейные сети с константными степенями слишком хрупки для практических целей и могут легко снизить производительность или даже распасться при возникновении сбоев. Исследование оверлейных сетей в условиях оттока пользователей продемонстрировало эти моменты [ ]. И в самом деле, насколько известно, ни одна из таких сетей с константной степенью не была построена. Их главный вклад и основная причина упоминания этих работ здесь – это знание того, что в принципе возможно привести состояние каждого узла к простой и небольшой константе.

Сеть с адресуемым содержимым (CAN) [ ], разработанная в ICSI, строит сеть как виртуальное d-мерное пространство, присваивая каждому узлу d-мерный идентификатор. Топология маршрутизации напоминает d-мерный тор. Маршрутизация осуществляется по евклидовым координатам в каждом измерении, что дает стратегию маршрутизации с dn1 переходов. Параметр d может быть настроен администратором сети. Отметим, что при d = log n характеристики CAN такие же, как и в Chord, а именно: логарифмическая степень и логарифмическое число переходов маршрутизации.

Алгоритм Symphony [ ] эмулирует маршрутизацию в «тесном» мире. Узлы имеют k связей с узлами, виртуальные идентификаторы которых выбираются случайным образом в соответствии с маршрутизируемым распределением тесного мира [22]. Ожидается, что при k связях Symphony найдет цель за log 2/k переходов.

Один из недостатков сетей с распределенной хэш-таблицей (DHT) заключается в том, что они поддерживают только точный поиск ключей, а значит, плохо решают задачи поиска диапазона ключей или нечеткого поиска, например, поиска любого ключа, соответствующего некоторому префиксу. SkipGraphs [4] и схема SkipNet [19] от Microsoft (проект Herald) независимо друг от друга разработали аналогичную сеть DHT на основе рандомизированного списка пропусков [28], которая поддерживает запросы по диапазону в распределенной сети. Подход в обеих этих сетях заключается в объединении объектов в двухсвязный список, отсортированный по именам объектов, над которым строятся «короткие» указатели. Указатели от каждого объекта переходят на геометрическую последовательность расстояний в отсортированном списке, то есть первый указатель переходит через два элемента, второй – через четыре, и так далее, вплоть до указателя log n - 1, который переходит через половину списка. Логарифмический, сбалансированный по нагрузке поиск достигается в этой схеме таким же образом, как и в Chord. Поскольку пространство идентификаторов сортируется по именам объектов, а не по хэш-идентификаторам, диапазоны объектов можно эффективно сканировать, просто переходя к наименьшему значению в диапазоне; остальные узлы диапазона располагаются смежно вдоль кольца.

Каждая из упомянутых выше сетей отличается одним или несколькими следующими свойствами: (интуитивно) эмулируемая топология; ожидаемое количество переходов, необходимых для достижения цели; степень каждого узла. Эти свойства сведены в таблице 1.

Оверлейная схема поиска Степень

AAABMP, сеть с делением расстояний пополам, Koorde, D2B De Bruijn log n 4

Проблема с перечисленными выше подходами заключается в том, что они игнорируют близость узлов в базовых сетях и позволяют «прыгать» туда-сюда через большие физические расстояния в поисках контента. Недавние исследования масштабируемых сетей обмена контентом [ ] показали, что до 80% запросов в Интернет могут быть удовлетворены локальными узлами в пределах собственной организации автора запроса. Поэтому даже один далекий переход может оказаться слишком дорогим. Следующие системы учитывают отношения близости между узлами, чтобы обеспечить осведомленность о локальности, то есть чтобы стоимость поиска была пропорциональна реальному расстоянию между взаимодействующими сторонами.

Несколько сетей поиска с учетом локальности были построены на основе протокола исправления битов, взятого из фундаментальной работы Плакстона и коллег [27] (PRR). Модель сети с ограниченным ростом, для которой предназначена эта схема, рассматривает сеть как метрическое пространство и предполагает, что плотность узлов в разных частях сети не слишком сильно различается. Схема поиска PRR [27] использует префиксную маршрутизацию, аналогичную Chord. Она отличается от Chord тем, что ссылка для «переворачивания» i-го бита идентификатора соединяется с любым узлом, чей префикс длины i совпадает со следующим переходом. Таким образом, схема отдает предпочтение ближайшему узлу в сети. Эта стратегия позволяет построить геометрическую маршрутизацию, особенностью которой является то, что шаги маршрутизации по направлению к цели увеличиваются в геометрической прогрессии. Это достигается за счет большой гибкости в выборе связей для каждого префикса в начале маршрута и сужения их списка по мере продвижения по маршруту. В результате получается схема оверлейной маршрутизации, которая находит любую цель с затратами, пропорциональными кратчайшему расстоянию до нее.

К системам, использующим алгоритм PRR, относятся Pastry [33], Tapestry [36] и Bamboo [32]. Очень близким вариантом является Kademlia [ ], в которой связи симметричны. Стоит отметить, что схема LAND [2] улучшает схем у PRR, обеспечивая почти оптимальную гарантию локальности; однако LAND не была развернута на практике.

Сеть Coral [ ] из Нью-Йоркского университета, построенная на основе DSHT [15], функционирует примерно с 2004 года. Она предоставляет бесплатные услуги по доставке контента на базе распределенного испытательного стенда PlanetLab [ ], аналогичные коммерческим услугам, предлагаемым сетью Akamai. Подписчики используют ее для предоставления нескольких быстрых точек доступа к контенту, который они хотят опубликовать в Сети.

В некоторых работах служба уведомления о событиях или публикации и подписки развертывается поверх существующего оверлея маршрутизации путем построения многоадресных путей с обратной маршрутизацией от одной «цели» ко всем «источникам». Например, к многоадресным системам, построенным таким образом, относятся сеть Bayeux [ ], построенная на базе Tapestry [36], и SCRIBE [ ], построенная на Pastry. Чтобы опубликовать файл, источник рекламирует с помощью «затопления» кортеж, содержащий семантическое имя сеанса многоадресной рассылки и уникальный идентификатор. Этот кортеж хешируется для получения идентификатора узла, который становится корневым узлом сеанса. Каждый узел может присоединиться к сеансу многоадресной рассылки, отправив сообщение корневому узлу. Узлы по пути следования сохраняют информацию о членстве, так что дерево многоадресной рассылки формируется в обратном направлении. Содержимое файла (и любые обновления) распространяется по дереву путем затопления. Narada [ ] построена на той же общей архитектуре, но отличается выбором связей и обслуживанием данных.

DHT может служить для хранения маршрутизации и (потенциально динамической) информации о местоположении виртуальных имен хостов. Эта идея была использована в ряде проектов. Система именования для Интернета под названием CoDoNS [30] была построена в Корнельском университете на основе оверлея BeeHive [29]. CoDoNS обеспечивает безопасность и является возможной заменой системы доменных имен, которая в настоящее время служит для поиска имен хостов. Поддержка виртуальных сетевых адресов IPv6 обеспечивается в [ ] путем сопоставления имен с их актуальными, достижимыми адресами IPv4. Инфраструктура Internet Indirection Infrastructure [34], созданная в Калифорнийском университете в Беркли, поддерживает виртуальные адреса хостов Интернета, обеспечивая возможность мобильности.

Очень популярной сетью распространения файлов является система BitTorrent [10]. Узлы в BitTorrent делятся на узлы-«сиды» (источники) и клиентов. Узлы-сиды содержат желаемый контент в полном объеме (либо являясь оригинальными поставщиками, либо недавно загрузив его). Клиентские узлы соединяются с одним или несколькими сидами, а также с узлом-«трекером», целью которого является отслеживание клиентов, загружающих контент в данный момент. Каждый клиент выбирает группу (в настоящее время размером около 20) других клиентов, осуществляющих загрузку, и обменивается с ними фрагментами данных, полученных от сидов. BitTorrent использует несколько сложных стратегий для выбора того, какие куски запрашивать у других клиентов, чтобы добиться справедливого распределения нагрузки при раздаче контента и, в то же время, обеспечить высокую скорость загрузки.

Недавно ряд работ Microsoft Research продемонстрировал преимущества сетевого кодирования для эффективной многоадресной рассылки, например [ ] и Avalanche [ ]. Вкратце изложим ключевые идеи, лежащие в их основе.