P2P

Ключевые слова и синонимы

Одноранговая сеть (Peer to peer); перекрытие, оверлей (Overlay); оверлейная сеть (Overlay network); DHT; распределенная хэш-таблица (Distributed hash table); CDN; сеть доставки контента (Content delivery network); совместный доступ к файлам (File sharing); совместное использование ресурса (Resource sharing)

Постановка задачи

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

1. Протокол поиска с ключом позволяет найти информацию на сервере или серверах, где она хранится.

2. Операции хранения, обновления и извлечения данных поддерживают распределенное постоянное хранилище данных.

3. Широковещательная передача и многоадресная рассылка поддерживают распространение информации среди множества получателей.

Из-за своей симметричной и бессерверной природы такие сети называются P2P-сетями. В последующем обсуждении узлы, участвующие в сети, будут также называться пирами (peers).

Наиболее влиятельным механизмом в этой области является последовательное хэширование, впервые примененное в работе Каргера и др. [21]. Идея приблизительно заключается в следующем. Часто хорошим способом организации каталога поиска является хэш-таблица, обеспечивающая быстрый доступ к данным со сложностью O(1). Для масштабирования и обеспечения высокой доступности сервисов поиска мы разбиваем хэш-таблицу на части и назначаем разные части разным серверам. Например, если в хэш-таблице есть записи от 1 до [math]\displaystyle{ n }[/math], а в системе поиска участвуют [math]\displaystyle{ k }[/math] серверов, мы можем дать возможность каждому серверу выбрать виртуальный идентификатор от 1 до [math]\displaystyle{ n }[/math] случайным образом. Тогда сервер [math]\displaystyle{ i }[/math] будет отвечать за значения ключей, которые ближе к [math]\displaystyle{ i }[/math], чем к идентификатору любого другого сервера. При хорошей рандомизации хэш-ключей мы можем получить более или менее сбалансированное распределение информации между нашими [math]\displaystyle{ k }[/math] серверами. Ожидается, что каждый сервер будет отвечать за [math]\displaystyle{ (n/k) }[/math] ключей. Кроме того, отключение или подключение сервера затрагивает только один или два других сервера с соседними виртуальными идентификаторами.

Сеть серверов, реализующих последовательное хэширование, называется распределенной хэш-таблицей (DHT). Многие современные сети совместного использования ресурсов и практически все академические исследовательские проекты в этой области построены на идее DHT.

Задача поддержки DHT состоит из двух частей:

Оверлейная маршрутизация

Пусть имеется хэш-ключ [math]\displaystyle{ i }[/math]. Начиная с любого узла [math]\displaystyle{ r }[/math] в сети, задача заключается в том, чтобы найти сервер [math]\displaystyle{ s }[/math], диапазон ключей которого содержит [math]\displaystyle{ i }[/math]. Имя ключа [math]\displaystyle{ i }[/math] не имеет отношения к какому-либо реальному сетевому адресу, например IP-адресу узла, и поэтому мы не можем использовать базовую IP-инфраструктуру для поиска [math]\displaystyle{ s }[/math]. Оверлейная сеть маршрутизации связывает узлы и предоставляет им протокол маршрутизации, так что [math]\displaystyle{ r }[/math] может направиться к [math]\displaystyle{ s }[/math], используя цель маршрутизации [math]\displaystyle{ i }[/math].

Динамическая поддержка

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

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

Основные результаты

Сфера P2P очень динамична и быстро развивается. Данная статья представляет собой лишь краткий обзор, охватывающий доминирующие и типичные стратегии, но не дающий исчерпывающего представления.

Неструктурированные оверлеи

Многие из ныне развернутых широко распространенных сетей совместного использования ресурсов не имеют или почти не имеют определенной оверлейной структуры. Если говорить точнее, то ранние системы, такие как Gnutella версии 0.4, вообще не имели оверлейной структуры и позволяли каждому узлу произвольно подключаться к другим узлам. Это приводило к серьезным проблемам с нагрузкой и заторам.

Двухуровневые сети были предназначены для того, чтобы уменьшить накладные расходы на связь и решить проблемы масштабируемости, которые были у ранних сетей, таких как Gnutella 0.4. Двухуровневые сети состоят из одного уровня относительно стабильных и мощных узлов, называемых серверами (суперпирами, ультрапирами), и более крупного уровня клиентов, которые ищут в сети посредством серверов. Большинство современных сетей, включая Edonkey/Emule, KaZaa и Gnutella, построены в виде двух уровней. Серверы обеспечивают хранение каталогов и средства поиска. Поиск либо ограничивается серверами, к которым клиенты подключаются напрямую (eDon-key/eMule), либо осуществляется с помощью «волны» ограниченной глубины среди серверов (Gnutella). Двухуровневая конфигурация значительно повышает масштабируемость и надежность P2P-сетей. Тем не менее, соединения между серверами и между клиентом и сервером осуществляются совершенно ситуативно. Таким образом, эти сети не дают гарантии успешности поиска и не ограничивают затраты на него.

Структурированные оверлеи без учета локальности

Chord

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

Постоянное состояние каждого узла

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

Сеть с адресуемым содержимым

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

Оверлейная маршрутизация, вдохновленная сетями типа «Мир тесен»

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

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

Добавление имен организаций к именам объектов в вмиде префиксов позволяет SkipNet добиться сближенности узлов, принадлежащих одной организации, вдоль кольца, и возможности сопоставления объектов с узлами в их локальных организациях. Подобным образом SkipNet достигает близости ресурсов и изоляции – это единственная система, помимо RP [33], обладающая таким свойством.

В то время как работа SkipGraphs сосредоточена на рандомизированных стратегиях балансирования нагрузки и доказательствах, система SkipNet рассматривает вопросы динамического обслуживания, переменные размеры базы, и использует стратегию осведомленности о локальности из Pastry [33], которая описана ниже.

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

Оверлейная схема поиска	Похожая топология	Число переходов	Степень
Chord	Гиперкуб	log n	log n
Viceroy	Бабочка	log n	5
AAABMP, сеть с делением расстояний пополам, Koorde, D2B	De Bruijn	log n	4
Symphony	«Тесный мир»	[math]\displaystyle{ log^2 \; n/k }[/math]	k
SkipGraphs/SkipNet	Список пропусков	log n	log n
CAN	Тор	[math]\displaystyle{ dn^{1/d} }[/math]	d

Таблица 1. Сравнение различных показателей схем поиска, не обладающих осведомленностью о локальности

Осведомленность о локальности

Проблема с перечисленными выше подходами заключается в том, что они игнорируют близость узлов в базовых сетях и позволяют «прыгать» туда-сюда через большие физические расстояния в поисках контента. Недавние исследования масштабируемых сетей обмена контентом [ ] показали, что до 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. Подписчики используют ее для предоставления нескольких быстрых точек доступа к контенту, который они хотят опубликовать в Сети.

Coral оптимизирует локальность доступа и скорость загрузки, используя локально-ориентированный поиск, предоставляемый DSHT. DSHT в составе Coral используется для поддержки локально-ориентированного поиска объектов в двух вариантах применения. Во-первых, Coral содержит коллекцию HTTP-прокси-серверов, которые служат поставщиками контента; DSHT используется клиентами для локализации местоположения ближайшего прокси-сервера. Во-вторых, сами прокси-серверы используют DSHT для поиска близлежащей копии контента, запрашиваемого клиентом, тем самым используя копии контента, хранящиеся в сети, вместо того чтобы обращаться к источнику контента.

Многоадресная рассылка

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

Инфраструктура маршрутизации

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

Совместная доставка контента

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

SplitStream [6] использует оверлей маршрутизации Pastry для построения нескольких деревьев, таких, что каждый участвующий узел является внутренним узлом только одного дерева. Затем он поддерживает параллельную загрузку полос внутри всех деревьев. SplitStream [6] стремится добиться балансировки нагрузки между узлами многоадресной рассылки. Это достигается за счет разделения публикуемого контента на несколько частей, называемых полосами, и публикации каждой части по отдельности. Каждая полоса публикуется с помощью древовидной многоадресной рассылки. Рабочая нагрузка распределяется между участвующими узлами путем отправки каждой полосы по разным деревьям многоадресной рассылки. Баланс нагрузки достигается путем тщательного выбора деревьев многоадресной рассылки таким образом, чтобы каждый узел служил внутренним узлом не более чем в одном дереве. Это уменьшает количество «безбилетников», которые только получают данные.

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

В настоящее время BitTorrent не содержит средств P2P-поиска. Он полагается на централизованные сайты, называемые «трекерами», для поиска контента и координации процесса загрузки по BitTorrent. Согласно недавним заявлениям Брэма Коэна (создателя BitTorrent) и создателей других BitTorrent-клиентов, в скором времени появятся новые протоколы на базе BitTorrent, в которых роль трекеров будет исключена, а поиск и координация будут осуществляться исключительно P2P-методами.

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

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

Основной подход в сетевом кодировании заключается в повторном кодировании всех фрагментов, принадлежащих файлу, так что каждый из них, который передается в общий доступ, на самом деле является линейной комбинацией всех частей. Затем эти блоки распространяются вместе с описанием содержимого. Как только узел получает эти перекодированные фрагменты, он может генерировать новые комбинации из тех, что у него есть, и отправлять их другим пирам. Главное преимущество заключается в том, что пиры могут использовать любой новый кусочек, а не ждать, когда появятся конкретные фрагменты, которые отсутствуют. Это означает, что ни один пир не может стать узким местом процесса, поскольку ни один кусок не является более важным, чем любой другой. Когда пир соберет достаточное количество таких фрагментов, он может использовать их для восстановления всего файла.

Стоит отметить, что в неструктурированных средах, как недавно было показано, сетевое кодирование не дает никаких преимуществ [12].

См. также

• Геометрические остовы
• Маршрутизация
• Разреженные остовы графов

Литература

1. Abraham, I., Awerbuch, B., Azar, Y., Bartal, Y., Malkhi, D., Pavlov, E.: A generic scheme for building overlay networks in adversarial scenarios. In: Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS 2003), 2003

2. Abraham, I., Malkhi, D., Dobzinski, O.: LAND: Stretch (1 + ") locality aware networks for DHTs. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA04), 2004

3. Abraham, I., Badola, A., Bickson, D., Malkhi, D., Maloo, S., Ron, S.: Practical locality-awareness for large scale information sharing. In: The 4th Annual International Workshop on Peer-To-Peer Systems (IPTPS '05), 2005

4. Aspnes, J., Shah, G.: Skip graphs. In: Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, January 2003, pp. 384-393

5. Castro, M., Druschel, P., Rowstron, A.: Scribe: A large-scale and decentralised application-level multicast infrastructure, IEEE J. Sel. Areas Commun. (JSAC) (Special issue on Network Support for Multicast Communications) 20(8), 1489-1499 (2002). ISSN: 0733-8716

6. Castro, M., Druschel, P., Kermarrec, A.-M., Nandi, A., Rowstron, A., Singh, A.: Splitstream: High-bandwidth multicast in a cooperative environment. In: SOSP'03, October 2003

7. Chou, P., Wu, Y., Jain, K.: Network coding for the internet. In: IEEE Communication Theory Workshop, 2004

8. Chu, Y., Rao, S.G., Zhang, H.: A case for end system multicast. In: Proceedings of ACM SIGMETRICS, Santa Clara, June 2000, pp. 1-12

9. Chun, B., Culler, D., Roscoe, T., Bavier, A., Peterson, L., Wawrzoniak, M., Bowman, M.: Planetlab: An overlay testbed for broad-coverage services. ACM SIGCOMM Comput. Commun. Rev. 33, 3-12(2003)

10. Cohen, B.: Incentives build robustness in bittorrent. In: Proceedings of P2P Economics Workshop, 2003

11. Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to algorithms. MIT Press (1990)

12. Fernandess, Y., Malkhi, D.: On collaborative content distribution using multi-message gossip. In: Twentieth IEEE International Parallel and Distributed Processing Symposium (IPDPS 2006), Greece, April 2006

13. Fraigniaud, P., Gauron, P.: The content-addressable network D2B. Tech. Report 1349, LRI, Univ. Paris-Sud (2003)

14. Freedman, M.J., Freudenthal, E., Mazieres, D.: Democratizing content publication with coral. In: Proceedings of the 1st USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI '04), March 2004

15. Freedman, M.J., Mazieres, D.: Sloppy hashing and self-organizing clusters. In: Proceedings of the 2nd Intl. Workshop on Peer-to-Peer Systems (IPTPS '03), February 2003

16. Gkantsidis, C., Rodriguez, P.: Network coding for large scale content distribution. In: IEEE/INFOCOM, 2005

17. Gummadi, K.P., Dunn, R.J., Saroiu, S., Gribble, S.D., Levy, H.M., Zahorjan, J.: Measurement, modeling, and analysis of a peer-to-peer file-sharing workload. In: Proceedings of the nineteenth ACM symposium on Operating systems principles, pp. 314-329. ACM Press (2003)

18. Gummadi, K., Gummadi, R., Gribble, S., Ratnasamy, S., Shenker, S., Stoica, I.: The impact of DHT routing geometry on resilience and proximity. In: Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, pp. 381-394. ACM Press (2003)

19. Harvey, N.J.A., Jones, M.B., Saroiu, S., Theimer, M., Wolman, A.: Skipnet: A scalable overlay network with practical locality properties. In: Proceedings of Fourth USENIX Symposium on Internet Technologies and Systems (USITS '03), March 2003 20. Kaashoek, F., Karger, D.R.: Koorde: A simple degree-optimal hash table. In: 2nd International Workshop on Peer-to-Peer Systems (IPTPS'03), 2003

21. Karger, D., Lehman, E., Leighton, F.T., Levine, M., Lewin, D., Panigrahy, R.: Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), 1997, pp. 654-663 1997

22. Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: Proc. 32nd ACM Symposium on Theory of Computing (STOC 2000), 2000, pp. 163-170

23. Malkhi, D., Naor, M., Ratajczak, D.: Viceroy: A scalable and dynamic emulation of the butterfly. In: Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC '02), 2002, pp. 183-192

24. Manku, G.S., Bawa, M., Raghavan, P.: Symphony: Distributed hashing in a small world. In: Proc. 4th USENIX Symposium on Internet Technologies and Systems (USITS 2003) 2003, pp. 127-140

25. Maymounkov, P., Mazieres, D.: Kademlia: A peer-to-peer information system based on the XOR metric. In: Proc. 1 st Intl. Workshop on Peer-to-Peer Systems (IPTPS 2002), 2002, pp. 53-65

26. Naor, M., Wieder, U.: Novel architectures for p2p applications: the continuous-discrete approach. In: The Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'03), 2003

27. Plaxton, C., Rajaraman, R., Richa, A.: Accessing nearby copies of replicated objects in a distributed environment. In: Proceedings of the Ninth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 97), 1997, pp. 311-320

28. Pugh, W.: Skip lists: A probabilistic alternative to balanced trees. In: Workshop on Algorithms and Data Structures, 1989, pp. 437-449

29. Ramasubramanian, V., Sirer, E.G.: Beehive: O(1) lookup performance for power-law query distributions in peer-to-peer overlays. In: Proceedings of Networked System Design and Implementation (NSDI), 2004

30. Ramasubramanian, V., Sirer, E.G.: The design and implementation of a next generation name service for the internet. In: Proceedings of SIGCOMM, 2004

31. Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable content-addressable network. In: Proceedings of the ACM SIGCOMM 2001 Technical Conference, 2001

32. Rhea, S., Geels, D., Roscoe, T., Kubiatowicz, J.: Handling churn in a dht.Tech. Report Technical Report UCB//CSD-03-1299, The University of California, Berkeley, December 2003

33. Rowstron, A., Druschel, P.: Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: IFIP/ACM International Conference on Distributed Systems Platforms (Middleware), 2001, pp. 329-350

34. Stoica, I., Adkins, D., Zhuang, S., Shenker, S., Surana, S.: Internet Indirection Infrastructure. In: Proceedings of ACM SIGCOMM, pp. 73-88 (2002)

35. Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup service for internet applications. In: Proceedings of the SIGCOMM 2001

36. Zhao, B.Y., Huang, L., Stribling, J., Rhea, S.C., Joseph, A.D., Kubiatowicz, J.: Tapestry: A resilient global-scale overlay for service deployment. IEEE J. Sel. Areas Commun. (2003)

37. Zhou, L., van Renesse, R., Marsh, M.: Implementing IPv6 as a Peer-to-Peer Overlay Network. In: Proceedings of the 21st IEEE Symposium on Reliable Distributed Systems (SRDS'02), pp. 347 (2002)

38. Zhuang, S.Q., Zhao, B.Y., Joseph, A.D., Katz, R.H., Kubiatowicz, J.: Bayeux: An architecture for scalable and fault-tolerant wide-area data dissemination. In: Proceedings of the Eleventh International Workshopon Networkand Operating System Support for Digital Audio and Video (NOSSDAV 2001), 2001