Сеть с адресацией по содержанию - Content addressable network

В Сеть с адресацией к содержанию (МОЖЕТ) является распределенным, децентрализованным P2P инфраструктура, обеспечивающая хеш-таблица функциональность на Интернет -подобная шкала. CAN был одним из первых четырех распределенная хеш-таблица предложения, внесенные одновременно с Аккорд, Кондитерские изделия, и Гобелен.

Обзор

Как и другие распределенные хеш-таблицы, CAN предназначена для масштабируемый, отказоустойчивой, и самоорганизующийся. Архитектурный дизайн - это виртуальный многомерный Декартово координатное пространство, тип оверлейная сеть, на мульти-тор. Это n-мерное координатное пространство является виртуальный логический адрес, полностью независимого от физического расположения и физической связи узлов. Точки внутри пространства отождествляются с координатами. Все координатное пространство динамически разделено между всеми узлами в системе, так что каждый узел обладает по крайней мере одной отдельной зоной в общем пространстве.[1]

Маршрутизация

Узел CAN поддерживает таблица маршрутизации который держит айпи адрес и виртуальная координатная зона каждого из его соседей. Узел направляет сообщение к точке назначения в координатном пространстве. Узел сначала определяет, какая соседняя зона является ближайшей к точке назначения, а затем ищет IP-адрес узла этой зоны через таблицу маршрутизации.[1]

Присоединение к узлу

Чтобы присоединиться к CAN, присоединяющийся узел должен:

  1. Найдите узел уже в оверлейной сети.
  2. Определите зону, которую можно разделить
  3. Обновите таблицы маршрутизации узлов, соседних с новой разделенной зоной.[1]

Чтобы найти узел уже в оверлейной сети, узлы начальной загрузки может использоваться для информирования присоединяющегося узла об IP-адресах узлов, находящихся в настоящее время в оверлейной сети.[1]

После того, как присоединяющийся узел получает IP-адрес узла, уже находящегося в CAN, он может попытаться идентифицировать зону для себя. Присоединяющийся узел случайным образом выбирает точку в координатном пространстве и отправляет запрос на присоединение, направленный в случайную точку, на один из полученных IP-адресов. Узлы, уже находящиеся в оверлейной сети, направляют запрос на присоединение к правильному устройству через свои таблицы маршрутизации зон-IP. Как только узел, управляющий зоной точки назначения, получает запрос на присоединение, он может удовлетворить запрос на присоединение, разделив свою зону пополам, выделив себе первую половину и выделив присоединяющемуся узлу вторую половину. Если он не выполняет запрос на присоединение, присоединяющийся узел продолжает выбирать случайные точки в координатном пространстве и отправлять запросы на присоединение, направленные на эти случайные точки, до тех пор, пока он не присоединится к сети.[1]

После завершения разделения и выделения зон соседние узлы обновляются с координатами двух новых зон и соответствующими IP-адресами. Таблицы маршрутизации обновляются, и обновления распространяются по сети.[1]

Узел отправляется

Чтобы обработать уходящий узел, CAN должен

  1. определить, что узел удаляется
  2. объединить зону отходящего узла или взять на себя соседний узел
  3. обновлять таблицы маршрутизации по сети.[1]

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

После определения уходящего узла его зона должна быть либо объединена, либо захвачена. Сначала зона ушедшего узла анализируется, чтобы определить, может ли зона соседнего узла объединиться с зоной ушедшего узла, чтобы сформировать действительную зону. Например, зона в двумерном координатном пространстве должна быть квадратной или прямоугольной и не может иметь L-образную форму. Проверочный тест может циклически проходить через все соседние зоны, чтобы определить, может ли произойти успешное слияние. Если одно из потенциальных слияний считается действительным слиянием, зоны затем объединяются. Если ни одно из потенциальных слияний не считается действительным, то соседний узел с наименьшей зоной берет на себя управление зоной уходящего узла.[1] После перехода под контроль переходный узел может периодически пытаться объединить свои дополнительно контролируемые зоны с соответствующими соседними зонами.

Если слияние прошло успешно, таблицы маршрутизации узлов соседних зон обновляются, чтобы отразить слияние. Сеть будет видеть часть оверлейной сети как одну единственную зону после слияния и обрабатывать всю обработку маршрутизации с этим мышлением. Чтобы осуществить переход, захватывающий узел обновляет таблицы маршрутизации узлов соседних зон, так что запросы к любой из зон разрешаются к передающему узлу. И, как таковая, сеть по-прежнему видит подсекцию оверлейной сети как две отдельные зоны и обрабатывает всю обработку маршрутизации с этим мышлением.

Разработчики

Сильвия Ратнасами, Пол Фрэнсис, Марк Хэндли, Ричард Карп, Скотт Шенкер

Смотрите также

Рекомендации

  1. ^ а б c d е ж грамм час я Ратнасами; и другие. (2001). «Масштабируемая сеть с адресацией к контенту» (PDF). В материалах ACM SIGCOMM 2001. Получено 2013-05-20. Цитировать журнал требует | журнал = (помощь)