Масштабируемая маршрутизация от источника - Scalable Source Routing

Масштабируемая маршрутизация от источника (SSR) - это протокол маршрутизации для неструктурированных сетей, таких как мобильные специальные сети, ячеистые сети, или же сенсорные сети. Он сочетает в себе исходная маршрутизация с маршрутизацией по виртуальному кольцу и основан на идее "проталкивания" Аккорд в подкладку ".[1]

Концепции

Виртуальное кольцо

SSR работает в плоском адресном пространстве, которое организовано как виртуальное кольцо. Это популярная концепция в пиринговый наложенные сети подобно Аккорд. Общие сведения о кольцевой структуре позволяют узлам маршрутизировать пакеты, не зная топологии базовой физической сети. Хотя физическая сеть может быть очень динамичной, структура виртуального кольца остается довольно статичной. Следовательно, наводнение физической сети можно избежать.

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

Часто предполагается, что трасса имеет определенную ориентацию в кольце, но это просто помогает упростить теорию. На практике это не обязательно и даже ухудшает производительность.

В стол для пальцев в Аккорд, который предоставляет ярлыки в виртуальном кольце, заменяется кешем маршрута.

Маршрутизация источника

В физической сети SSR использует исходная маршрутизация. Узлы ретрансляции случайно кэшируют пройденную часть исходного маршрута данного пакета. Это облегчает сбор информации о маршрутизации, запрещая загрязнение кешей маршрутов узлов с устаревшей информацией.

Агрегация маршрутов

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

Функциональность распределенной хеш-таблицы (DHT)

Пока SSR - это полная протокол маршрутизации (ср. Модель OSI с сетевой уровень ), он также обеспечивает семантику распределенная хеш-таблица. Это снижает накладные расходы на наличие протокола наложения поверх традиционного. протокол маршрутизации и значительно ускоряет поиск в МАНЕЦ который в противном случае полагался бы на наводнение,[3][4] при условии, что приложение поддерживает (или модифицировано для поддержки) маршрутизация на основе ключей. Предоставляемые функции DHT также могут использоваться для реализации масштабируемых сетевых служб при отсутствии серверов.[5]

Обзор алгоритма

Начальная загрузка (запуск сети)

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

Узел также отправляет сообщение «уведомление соседа» своему предполагаемому преемнику, чтобы присоединиться к виртуальному кольцу. Если узел, с которым установили контакт, обнаруживает, что это неправильный преемник, он отвечает сообщением, содержащим наилучшее предположение для преемника запрашивающего узла. Это повторяется до тех пор, пока не будут найдены правильные виртуальные соседи. (Подробное описание этого процесса, называемого ISPRP, см.[6] Другой способ начальной загрузки - линеаризация.[7])

Рисование виртуального кольца (верхняя половина) и графа физической сети (нижняя половина)
SSR: Маршрутизация без флуда. Узел 1 направляет сообщение через узел 17, 32, 39 к узлу назначения 42 (подробное описание см. [1]).

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

Когда узел направляет сообщение

  1. он смотрит в свой кеш маршрута. Если маршрут к месту назначения существует, он используется.
  2. и маршрут к пункту назначения не известен, узел направляет сообщение практически ближайшему предшественнику пункта назначения. Затем этот промежуточный узел повторяет процесс маршрутизации.
  3. а кэш маршрута узла еще не содержит совпадающего маршрута, поскольку в качестве запасного варианта узел передает сообщение своему преемнику в виртуальном кольце. Виртуальный преемник может не находиться физически близко к узлу, но процесс начальной загрузки должен был установить к нему маршрут. Когда этот шаг возврата повторяется, сообщение перемещается по кольцу, в конечном итоге достигая пункта назначения или истекает время ожидания.

Классификация

ССР имеет реактивный а также активный компоненты, что делает его гибридный протокол маршрутизации. Виртуальная кольцевая маршрутизация концептуально похож, самая большая разница заключается в использовании исходная маршрутизация в SSR по сравнению с созданием состояния для каждого узла (таблиц маршрутизации) в VRR.

Преимущества

  • Эффективность сообщений: только локальные трансляции, без глобального флуда.
  • Низкие требования к памяти. Небольшое и ограниченное состояние на узел.
  • Функциональность DHT может ускорить поиск или использоваться для построения безсерверной инфраструктуры.

Недостатки

  • Найденные маршруты могут быть длиннее, чем необходимо.
  • Исходные маршруты увеличивают размер заголовков сообщений. Таким образом, для полезной нагрузки остается меньше места.

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

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

  1. ^ а б Фурманн, Томас; Пэнфэй Ди; Кенди Кутцнер; Курт Крамер (июнь 2006 г.). «Аккорд в основе: масштабируемая маршрутизация для гибридных MANET» (PDF). Группа системной архитектуры, Технический университет Карлсруэ (TH), Германия. Получено 15 апреля 2010. Цитировать журнал требует | журнал = (помощь)
  2. ^ Фурманн, Томас (май 2005 г.). «Самоорганизующаяся схема маршрутизации для случайных сетей». СЕТИ 2005 (PDF). Конспект лекций по информатике. 3462/2005. Springer Berlin / Heidelberg. С. 1366–1370. Дои:10.1007/11422778_116. Получено 15 апреля 2010.
  3. ^ Castro, Marcel C .; Андреас Дж. Касслер; Карла-Фабиана Кьяссерини (март 2010 г.). «Одноранговое наложение в мобильных Ad-Hoc сетях». Справочник по одноранговой сети. Springer Verlag. С. 1045–1080. Дои:10.1007/978-0-387-09751-0_37. ISBN  978-0-387-09750-3.
  4. ^ Зан, Томас; Грег О'Ши; Энтони Роустрон (2009). «Эмпирическое исследование наводнения в ячеистых сетях» (PDF). СИГМЕТРИКА Выполнить. Eval. Rev. ACM. 37 (2): 57–58. Дои:10.1145/1639562.1639584. Получено 16 апреля 2010.
  5. ^ Цезарь, Матфей; Эдмунд Б. Найтингейл; Грег О'Ши; Энтони Роустрон (сентябрь 2006 г.). «Виртуальная кольцевая маршрутизация: сетевая маршрутизация, основанная на DHT» (PDF). Обзор компьютерных коммуникаций SIGCOMM. ACM. 36 (4): 351–362. Дои:10.1145/1151659.1159954. Получено 16 апреля 2010.
  6. ^ Крамер, Курт и Фурманн, Томас (31 января 2005 г.). «Самостабилизирующиеся кольцевые сети на связных графах» (PDF). Получено 26 апреля 2010. Цитировать журнал требует | журнал = (помощь)
  7. ^ Кенди Кутцнер и Томас Фурманн (март 2007 г.). «Использование линеаризации для глобальной согласованности в SSR» (PDF). Материалы 4-й Междунар. Семинар IEEE по актуальным темам в системах P2P. Получено 20 апреля 2010.

внешняя ссылка