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_MESSAGE
Сообщения 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 — соединение потеряно.
- Neighbor Types — тип соседа:
- Link Message Size
- Размер сообщения в байтах начиная с поля Link Code до следующего поля Link Code или до конца сообщения.
TC_MESSAGE
Используется для передачи информации о 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)
- Порядковый номер сообщения. Должен увеличиваться на единицу каждый раз, когда составляется новое сообщение. Характеризует свежесть информации в сообщении.
Примечания
- Кирьянов А., Сафонов А., Хоров Е. Методы исследования переходных характеристик протокола OLSR при включении/выключении узла связи // Труды 33-й конференции ИППИ РАН "Информационные технологии и системы (ИТиС)". — 2010.
- Neighbor detection
- Two hop neighbor detection
- 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.