OLSR

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

OLSR (англ. Optimized Link-State Routing) — протокол маршрутизации для MANET, который также может использоваться в других беспроводных сетях. OLSR — проактивный протокол маршрутизации, использующий обмен сообщениями приветствия (hello) и контроля (topology control) для получения информации о топологии сети. Узлы используют эту информацию для определения следующего прыжка в пути маршрутизируемого пакета. Является одним из наиболее популярных протоколов, которые используются для маршрутизации в беспроводных сетях MANET[1].

Принцип работы

[править | править код]

OLSR основан на механизме широковещательной рассылки для обновления информации о топологии сети. Особенностью протокола является то, что эта информация известна каждому узлу сети. В OLSR узел сети отправляет так называемое HELLO-сообщение. Изменение в топологии сети узлы обнаруживают с помощью принятых HELLO-сообщений от соседей. В этих сообщениях содержится собственный адрес узла, отправившего данное оповещение, а также перечень всех его доступных соседей, их адреса с указанием типа соединения (симметричное или асимметричное). Таким образом узел сообщает своим соседям о доступных ему связях. Каждый абонент сохраняет у себя информацию о своих одно- (neighbors)[2] и двухшаговых соседях (two-hop neighbors)[3]. Отправка HELLO-сообщений производится с заданным интервалом. В случае, если в течение определенного времени узел не принимает HELLO-сообщение от соседа, то связь с ним считается разорванной. Соответствующее изменение вносится в таблицу топологии сети абонента.

Помимо всего в сети узлы периодически передают широковещательное TC-сообщение (topology control). В этом сообщении содержится информация о соединении абонента с одношаговыми соседями. По полученной информации из ТС- и HELLO-сообщений, узел строит граф, который описывает представление о построении сети для данного узла. С помощью этого графа строится таблица кратчайших путей передачи информации до каждого узла.

Очевидно, что в таком способе организации связи между узлами есть существенный недостаток. Естественна ситуация, когда двухшаговый сосед может являться одношаговым для двух и более одношаговых соседей передающего узла. Тогда создастся ситуация, в которой двухшаговый сосед будет получать одно и то же HELLO-сообщение несколько раз. Для решения таких ситуаций в OLSR предусмотрен метод оптимизации рассылки сетевой информации о состояниях Multipoint Relay (MPR). По таблице топологии сети узел выбирает таких одношаговых соседей с симметричной связью, которые являются одношаговыми соседями хотя бы одному двушаговому соседу данного узла. Этот метод позволяет уменьшить трафик широковещательной рассылки[4].

Формат пакетов

[править | править код]

Заголовок пакета

[править | править код]

В схеме заголовки IP и UDP были пропущены.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Packet length Packet sequence number
Заголовок сообщения
Сообщение
Заголовок сообщения
Сообщение
Packet Length
Размер пакета в байтах.
Packet Sequence Number
Порядковый номер пакета. Должен увеличиваться на единицу каждый раз, когда отправляется новый.

Заголовок сообщения

[править | править код]
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Message Type Vtime Message Size
Originator Address
Time To Live Hop Count Message Sequence Number
Сообщение
Message Type
Тип пересылаемого сообщения. Значения от 0 до 127 зарезервированы.
  • 1 — HELLO_MESSAGE
  • 2 — TC_MESSAGE
  • 3 — MID_MESSAGE
  • 4 — HNA_MESSAGE
Vtime (validity time)
Срок, на который сообщение считается актуальным, пока не будет получено новое сообщение.
Message Size
Размер сообщения.
Originator Address
Адрес создателя сообщения.
Time To Live
Максимальное количество «прыжков» (англ. hops), которое должно совершить сообщение. Если оно равно 0 или 1, то сообщение не должно передаваться дальше. При каждом прыжке должно уменьшаться на единицу.
Hop Count
Количество «прыжков», которое сообщение совершило. Должно увеличиваться на 1 при каждом «прыжке».
Message Sequence Number
Порядковый номер сообщения. Должен увеличиваться на единицу каждый раз, когда составляется новое сообщение. Используются для того, чтобы предотвратить повторную пересылку одного и того же сообщения.

Сообщения HELLO используются для уточнения текущей конфигурации сети. Отправляются периодически.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Зарезервировано Htime Willingness
Link Code Зарезервировано Link Message Size
Адрес соседа
Зарезервировано Htime Willingness
Link Code Зарезервировано Link Message Size
Адрес соседа
Адрес соседа

Для соблюдения спецификации зарезервированные биты должны быть равны 0.

Htime (Hello emission interval)
Периодичность отправки сообщений HELLO.
Willingness
Готовность узла передавать полученные сообщения дальше. Может принимать значение от 0 (WILL_NEVER, не будет передавать) до 7 (WILL_ALWAYS, будет передавать всегда) включительно. Значение может меняться в зависимости от состояния узла, то есть, если устройство работает от батареи, то оно может понижать уровень готовности по мере снижения заряда.
Link Code
Характеризует последующий список соседей этого узла. По спецификации должно быть меньше 16 и должно содержать в себе два поля по два бита каждое
7 6 5 4 3 2 1 0
0 0 0 0 Neighbor Type Link Type
  • Neighbor Types — тип соседа:
    • SYM_NEIGH — имеет хотя бы одно симметричное соединение с узлом.
    • MPR_NEIGH — имеет хотя бы одно симметричное соединение с узлом и был выбран как MPR.
    • NOT_NEIGH — сообщает о том, что симметричное соединение было разорвано или ещё не установлено.
  • Link Types — тип соединения:
    • UNSPEC_LINK — нет никакой информации о типе соединения.
    • ASYM_LINK — соединение асимметрично.
    • SYM_LINK — соединение симметрично.
    • LOST_LINK — соединение потеряно.
Link Message Size
Размер сообщения в байтах начиная с поля Link Code до следующего поля Link Code или до конца сообщения.

Используется для передачи информации о MPR соседях узла.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
ANSN Зарезервировано
Адрес соседа
Адрес соседа
ANSN (Advertised Neighbor Sequence Number)
Порядковый номер сообщения. Должен увеличиваться на единицу каждый раз, когда составляется новое сообщение. Характеризует свежесть информации в сообщении.

Примечания

[править | править код]
  1. Кирьянов А., Сафонов А., Хоров Е. Методы исследования переходных характеристик протокола OLSR при включении/выключении узла связи // Труды 33-й конференции ИППИ РАН "Информационные технологии и системы (ИТиС)". — 2010. Архивировано 5 марта 2016 года.
  2. Neighbor detection. Дата обращения: 22 октября 2012. Архивировано 13 ноября 2015 года.
  3. Two hop neighbor detection. Дата обращения: 22 октября 2012. Архивировано 4 марта 2016 года.
  4. T. H. Clausen, G. Hansen, L. Christensen, and G. Behrmann. The optimized link state routing protocol, evaluation through experiments and simulation // Proceedings of the IEEE conference on Wireless Personal Multimedia Communications (WPMC). — October 2001.