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 — соединение потеряно.
- 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)
- Порядковый номер сообщения. Должен увеличиваться на единицу каждый раз, когда составляется новое сообщение. Характеризует свежесть информации в сообщении.
Примечания
Ссылки
