Масштабируемая исходная маршрутизация
Алгоритм маршрутизации для неструктурированных сетей

Scalable Source Routing (SSR) — это протокол маршрутизации для неструктурированных сетей, таких как мобильные ad hoc-сети , ячеистые сети или сенсорные сети . Он объединяет маршрутизацию источника с маршрутизацией по виртуальному кольцу и основан на идее «вставки Chord в подложку». [1]

Концепции

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

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

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

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

Таблица пальцев в Chord , которая обеспечивает ярлыки в виртуальном кольце, заменена кэшем маршрутов.

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

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

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

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

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

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

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

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

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

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

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

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

Когда узел маршрутизирует сообщение

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

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

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

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

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

Недостатки

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

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

Ссылки

  1. ^ ab Fuhrmann, Thomas; Pengfei Di; Kendy Kutzner; Curt Cramer (июнь 2006 г.). "Pushing Chord into the Underlay: Scalable Routing for Hybrid MANETs" (PDF) . System Architecture Group, Technical University of Karlsruhe (TH), Германия . Получено 15 апреля 2010 г. . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  2. ^ Фурманн, Томас (май 2005 г.). «Самоорганизующаяся схема маршрутизации для случайных сетей». NETWORKING 2005 (PDF) . Lecture Notes in Computer Science. Vol. 3462/2005. Springer Berlin / Heidelberg. pp.  1366– 1370. doi :10.1007/11422778_116. ISBN 978-3-540-25809-4. Получено 15 апреля 2010 г.
  3. ^ Кастро, Марсель К.; Андреас Дж. Касслер; Карла-Фабиана Чиассерини (март 2010 г.). «Peer-to-Peer Overlay in Mobile Ad-hoc Networks». Справочник по одноранговым сетям . Springer Verlag . С.  1045–1080 . doi :10.1007/978-0-387-09751-0_37. hdl :11693/38342. ISBN 978-0-387-09750-3. S2CID  16386810.
  4. ^ Зан, Томас; Грег О'Ши; Энтони Роустрон (2009). "Эмпирическое исследование затопления в ячеистых сетях" (PDF) . SIGMETRICS Perform. Eval. Rev . 37 (2). ACM: 57– 58. doi :10.1145/1639562.1639584. S2CID  11285886 . Получено 16 апреля 2010 г. .
  5. ^ Крамер, Курт и Фурманн, Томас (31 января 2005 г.). "Самостабилизирующиеся кольцевые сети на связных графах" (PDF) . Получено 26 апреля 2010 г. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  6. ^ Кенди Катцнер и Томас Фурманн (март 2007 г.). «Использование линеаризации для глобальной согласованности в SSR» (PDF) . Труды 4-го Международного семинара IEEE по актуальным темам в системах P2P . Получено 20 апреля 2010 г.
  • Репозиторий оригинальных статей Томаса Фурмана и др.
Взято с "https://en.wikipedia.org/w/index.php?title=Масштабируемая_маршрутизация_источников&oldid=1185271297"