tanenbaum_seti_all.pages (525408), страница 116
Текст из файла (страница 116)
Причем, зто происходит спонтанно, безо всяких предупреждений. Надо ли говорить о том, что в таких условиях маршрутизация будет сильно отличаться от маршрутизации в стационарных сетях, Известно множество алгоритмов выбора маршрута для специализированных сетей. Один из наиболее интересных — это алгоритм АОь»У (Аг( Ьос Оп-бещапб П(згапсе Уесгог — маршрутизация по требованию в специализированных сетях на основе вектора расстояний). Об этом можно прочитать у (Регй(пэ эпб Коуег, 1999).
АОЭЧ является дальним родственником алгоритма Беллмана †Фор (Вейщап — Рогб) (метод векторов расстояний), адаптированным для работы в мобильной среде и принимающим в расчет ограниченность пропускной способности и срока службы элементов питания — свойства, характерные для мобильных сетей. Еще одной необычной характеристикой является то, что АОЭЧ вЂ” это алгоритм «по требованию», то есть он вычисляет маршрут только в тот момент, когда появляется желающий отправить пакет тому или иному адресату. Посмотрим, что зто значит. Постровние маршрута Специализированная сеть в любой момент времени может быть описана с помощью графа узлов (маршрутизаторов и хостов).
Два узла считаются соединенными (то есть между ними проведена дуга), если они могут связываться напрямую посредством радио. Поскольку у одного из них может быть более мощный передатчик, чем у другого, то возможна ситуация, когда узел А соединен с В, но В не соединен с А. Однако для простоты мы будем считать, что все соединения симметричны. Следует заметить, что нахождение одного из узлов в зоне действия другого еще не означает наличия связи между ними. Их могут разделять холмы, здания и другие местные предметы, блокирующие соединение. Для описания алгоритма воспользуемся рис.
5,18, на котором изображен процесс, запущенный на узле А, которому необходимо отправить пакет на узел В Алгоритм АООД' на каждом узле ведет таблицу, доступ к которой осуществляется с помощью поля адреса. Таблица содержит информацию об адресате, в том числе Алгоритмы маршрутизации 435 адрес ближайшего соседа, которому необходимо переслать пакет, чтобы он мог достичь пункта назначения. Допустим, А просматривает эту таблицу и не находит записи для й Значит, нужно найти маршрут, ведущий к этому узлу. Итак, алгоритм начинает заниматься поисками маршрутов только тогда, когда они реально требуются. Это и делает его алгоритмом чпо требованию». на широковещания А Рис.
6.16. Зона широковещания А (е); состояние после получения узлами В и 0 широковещательного пекете от Я (б); состояние после получения узлами С, ни 0 широковещательного пакета от Я (в); состояние после получения узлами Е, Н и ) широковещательного пакете от А (г). Затененными кружочками обозначены новые получатели. Стрелками показаны возможные обратные маршруты Для поиска 1 узел А генерирует специальный пакет запроса маршрута ЕЗДИТЕ ЙЕ()ЦЕ5Т и распространяет его по сети широковещательным способом. На рис. 5.18, а показано, что этот пакет достигает узлов В и .О.
На самом деле, причиной установления именно узлами В и Р соединения с А является то, что они могут получать пакеты от А. Например, г не соединен дугой с А потому что он ие может принимать радиосигнал от этого узла. То есть Г не соединен с А. Формат пакета запроса маршрута показан на рис. 5.19. В нем, как видно из этого рисунка, содержатся адреса источника и приемника (обычно 1р-адреса), с помощью которых можно понять, кто кого ищет. Также содержится поле Идентифштдлюр защюса, которое представляет собой локальный счетчик, обновляемый каждым узлом независимо и инкрементируюшийся всякий раз, когда распространяется пакет запроса маршрута. Поля Адрес исглочника и Идентификатор запроса вместе единственным образом идентифицируют пакет ЙО()ТЕ ЕЕ()()ЕБТ, что позволяет узлам обнаруживать и отвергать любые дубликаты.
Адрес Идентификатор Адрес Порядковый Порядковый Счетчик отправителя запросе получателя номер отправителя номер получателя переколов Рис. 6.19. Формат пакете ПОНТЕ ПЕСОЕЗТ В дополнение к счетчику Идентификатор запросп каждый узел имеет второй счетчик, который инкрементируется всякий раз при отправке пакета для запроса маршрута или ответе на такой пакет. Его работа напоминает часы, и используется 43В Глава 6. Сетевой ровень он для того, чтобы можно было отличить новые маршруты от старых, Четвертое поле, показанное на рис.
5,19, это счетчик узла А; пятое — последнее значение порядкового номера пакета, полученного от! (оно равно О, если такого пакета не было). Вскоре мы более подробно раскроем назначение этих полей Наконец, последнее поле — Скверик переходов — запоминает количество пересылок, совершенных пакетом, В начале работы алгоритма оно равно нулю, Когда пакет запроса маршрута прибывает на узел (например, па узлы В и Ю), с ним происходит следующее; 1, Пара значений полей Адрес исягочкика и Идвктификапюр запроса ищется в таблице локальной истории. С их помощью можно выяснить, приходил ли уже этот запрос и обрабатывался ли он, Если обнаруживается, что пакет является дубликатом, он отвергаетея и его обработка прекращаетея.
В противном случае указанная пара значений заносится в таблицу истории, чтобы в будущем можно было обнаружить дубликаты. Обработка запроса продолжается. 2. Приемник ищет адрес назначения в таблице маршрутов, Если известен достаточно свежий маршрут, отправителю посылается пакет наличия маршрута РООТСИ кссР~Т, сообщающий ему о том, как можно достичь получателя (в двух словах: «Используй меняв), Что значит «свежий маршрута? Имеется в виду, что поле Порядковый комер получашвля в таблице маршрутизации имеет значение большее или равное Порядковому номеру получателя из пакета запроса маршрута.
Если оно меньше, значит, хранящийся в таблице маршрут является более старым, нежели предыдущий маршрут, имевшийся у отправителя к тому же пункту назначения. В этом случае выполняется пункт 3. 3. Поскольку у приемника отсутствует свежий маршрут к адресату, он инкрементирует поле Счвпгчик переходов и вновь широковещательным образом распространяет пакет запроса маршрута. Из пакета извлекаются данные и сохраняются в виде новой записи в таблице обратных маршрутов.
Эти данные будут использоваться для построения обратного пути, по которому впоследствии необходимо будет послать ответный пакет отправителю. Стрелки на рис. 5.18 как раз показывают процесс построения обратного пути. Для записи о только что созданном обратном пути запускается таймер. Прн наступлении тайм- аута запись удаляется. Ни В, ни )г не знают, где находится узел Т поэтому каждый из них создает обратный путь к А, как показано стрелками на рнс. 5.18, н широковещательным способом распространяет пакет со Сметчиком переходов, установленным в единицу.
Этот пакет от В достигает С н )). Узел С делает запись в таблице обратных путей и, в свою очередь, тоже широковещательным способом распространяет пакет далее. Что касается О, то он отвергает пакет: для него это дубликат. Разумеется, н В отвергает пакеты, полученные от Р, Тем не менее, Е н С принимают широковещательное сообщение от 1) и сохраняют его, как показано на рис, 5.18, в. После того как Е, Н и Т получают широковещательный пакет, запрос маршрута наконец достигает узла назначения (1). Этот счастливый мнг запечатлен на рнс. 5.18, а Обратите внимание: несмотря на то, что мы показали распрострзне- Алгоритмы маршрутизации 437 ние широковещательного пакета в виде трех стадий, на самом деле рассылка этого пакета разными узлами никак не координируется.
В ответ на пришедший запрос узел 1 генерирует пакет наличия маршрута йООТЕ йЕРЛТ, показанный на рис. 5.20. Поля Адрес отправителя, Адрес получателя и Счегпчик переходов копируются из йООТЕ йЕООЕЬТ, а Порядковый номер получателя берется из собственного счетчика, хранящегося в памяти.
Поле Счетчик переходов устанавливается в О. Поле Время существования используется для управления реализуемостью маршрута. Данный пакет распространяется методом одно- адресной передачи на тот узел, с которого пришел запрос маршрута. В данном случае он уходит на узел С. Затем, в соответствии с установленным обратным путем, он попадет на 1л и наконец на А. При проходе каждого узла Счетчик переходов инкрементируется, так что узел-отправитель может увидеть, насколько далеко от него находится узел-получатель (1). Рио. 5.20.
Формат пакета ЯООТЕ ПЕР!Л' Кюкдый узел, через который проходит пакет на обратном пути (к А), проверяет его. При выполнении хотя бы одного из трех условий на его основе строится запись в локальной таблице маршрутов о пути к 1. Вот эти условия: 1. Не известен ни один маршру~ к 1. 2. Последовательный номер для 1 в пакете йООТЕ йЕРЕТ больше, чем значение в таблице маршрутизации. 3. Последовательные номера равны, но новый путь короче. Таким образом, все узлы, стоящие на обратном пути к А, совершенно бесплатно получают информацию о маршруте к узлу 1. Это как бы побочный продукт построения маршрута для А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
