Контентно-адресуемая сеть

Сеть с адресацией по содержимому ( CAN ) представляет собой распределенную децентрализованную инфраструктуру P2P , которая обеспечивает хеш-таблиц функциональность в масштабах, подобных Интернету . CAN был одним из первых четырех предложений распределенных хеш-таблиц , представленных одновременно с Chord , Pastry и Tapestry .

Обзор

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

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

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

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

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

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

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

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

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

Узел выходящий

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

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

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

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

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

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

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

См. также

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Ратнасами; и др. (2001). «Масштабируемая сеть с адресацией по контенту» (PDF) . В материалах ACM SIGCOMM 2001 . Проверено 20 мая 2013 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[Ratnasamy01-1] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Ратнасами; и др. (2001). «Масштабируемая сеть с адресацией по контенту» (PDF) . В материалах ACM SIGCOMM 2001 . Проверено 20 мая 2013 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[1]