Введение
Tapestry - это одноранговая сеть, которая обеспечивает распределенную хэш-таблицу, маршрутизацию и мультикастинг инфраструктуру для распределенных приложений. Система "Tapestry" предлагает эффективную, масштабируемую, самовосстанавливающуюся, ориентирующуюся на местоположение маршрутизацию к близлежащим ресурсам.
Введение
Первое поколение одноранговых приложений, включая Napster, Gnutella, имело ограничивающие ограничения, такие как центральная директория для Napster и объемные запросы для Gnutella, ограничивающие масштабируемость. Для решения этих проблем было разработано второе поколение P2P-приложений, включая Tapestry, Chord, Pastry и CAN. Эти наложения реализуют основной основанный на ключе механизм маршрутизации. Это позволяет осуществлять детерминированную маршрутизацию сообщений и адаптацию к сбоям узлов в сети накладок. Из названных сетей Pastry очень близка к Tapestry, поскольку они оба используют один и тот же алгоритм маршрутизации Plaxton et al. Tapestry - это расширяемая инфраструктура, которая обеспечивает децентрализованное расположение объектов и маршрутизацию, ориентированную на эффективность и минимизацию задержки сообщений. Это достигается, поскольку Tapestry создает локально оптимальные таблицы маршрутизации с момента инициализации и поддерживает их для того, чтобы уменьшить расширение маршрутизации. Кроме того, Tapestry позволяет определять распределение объектов в соответствии с потребностями данного приложения. Аналогичным образом, Tapestry позволяет приложениям реализовывать мультикастинг в накладной сети.
Маршрутизационная сетка
Каждый идентификатор соотносится с живым узлом, называемым корнем. Если nodeID узла G, то это корень, иначе используйте nodeID и IP-адреса таблицы маршрутизации, чтобы найти соседей узлов. При каждом прыжке сообщение постепенно направляется ближе к G путем инкрементального маршрутизации суффикса. Каждая соседняя карта имеет несколько уровней, где каждый уровень содержит ссылки на узлы, соответствующие определенной позиции цифр в идентификаторе. Первичная i-я запись в j-м уровне - это идентификатор и местоположение ближайшего узла, который начинается с префикса (N, j 1) + i. Это означает, что уровень 1 имеет ссылки на узлы, которые не имеют ничего общего, уровень 2 имеет первую цифру в общем, и т.д. Из-за этого маршрутизация занимает приблизительно прыжки в сети размера N и идентификаторы базы B (шестиугольника: B = 16). Если точный идентификатор не может быть найден, таблица маршрутизации будет маршрутизировать ближайший соответствующий узел. Для устранения ошибок узлы сохраняют вторичные ссылки таким образом, чтобы таблица маршрутизации имела размер .
Объект публикации и местоположение
Участники сети могут публиковать объекты, периодически направляя сообщение о публикации к корневому узлу. Каждый узел вдоль пути хранит указатель, отображающий объект. Несколько серверов могут публиковать указатели на один и тот же объект. Избыточные ссылки распределяются по приоритетам по времени ожидания и/или локальности. Объекты локализуются путем маршрутизации сообщения к корню объекта. Каждый узел вдоль пути проверяет сопоставление и перенаправляет запрос соответствующим образом. Эффект маршрутизации - это сближение близлежащих путей, направляющихся к одному и тому же месту назначения.
Вставка узла
Новый узел становится корнем для его nodeID. Корень находит длину самого длинного префикса идентификатора, который он использует. Затем он отправляет сообщение, которое достигает всех существующих узлов, имеющих один и тот же префикс. Затем эти узлы добавляют новый узел в свои таблицы маршрутизации. Новый узел может стать корнем для некоторых объектов корня. Узлы свяжутся с новым узлом, чтобы предоставить временный список соседств. Затем новый узел выполняет итеративный поиск ближайшего соседа, чтобы заполнить все уровни в своей таблице маршрутизации.
Отправление узла
Чтобы покинуть сеть, узел передает свое намерение покинуть сеть и передает заменяющий узел для каждого уровня в таблицах маршрутизации других узлов. Объекты на исходящем узле перераспределяются или пополняются из лишних копий.
Неисправность узла
Неожиданные сбои узлов обрабатываются через избыточность в сети и резервные указатели для восстановления поврежденных ссылок.
Разработчики
Гобелен был разработан Беном Я. Чжао, Линг Хуан, Джереми Стриблингом, Шонам С. Реа, Энтони Д. Джозефом и Джоном Д. Кубиатовичем.