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

Система 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.