tanenbaum_seti_all.pages (525408), страница 112
Текст из файла (страница 112)
Обнаруживать своих соседей и узнавать их сетевые алреса. 2. Измерять задержку или стоимость связи с каждым из своих соседей. 3. Создавать пакет, содержащий всю собранную информацию. 4. Посылать этот пакет всем маршрутизаторам. 5. Вычислять кратчайший путь ко всем маршрутизаторам. 418 Глава б. Сетевой уровень В результате каждому маршрутизатору высылаются полная топология и все измеренные значения задержек. После этого для обнаружения кратчайшего пути к каждому маршрутизатору может применяться алгоритм Дейкстры. Далее мы рассмотрим каждый из этих пяти этапов более подробно. Знакомство с соседями Когда маршрутизатор загружается, его первая задача состоит в получении информации о своих соседях.
Он достигает этой цели, посылая специальный пакет )(ШО по всем двухточечным линиям. При этом маршрутизатор на другом конце линии должен послать ответ, сообщая информацию о себе. Имена маршрутизаторов должны быть совершенно уникальными, поскольку, если удаленный маршрутизатор слышит, что три маршрутизатора являются соседями маршрутизатора Г, не должно возникать разночтений по поводу того, один и тот же маршругизатор Г имеется в виду или нет. Когда два или более маршрутизаторов объединены в локальную сеть, ситуация несколько усложняется, На рис. 5.9, а изображена ЛВС, к которой напрямую подключены три маршрутизатора — А, С и Е Каждый из них, как показано на рисунке, соединен также с одним или несколькими дополнительными маршрутизаторами.
Маршрутизатор Локальная сеть е б Рнс. 6.9. девять мершрутиееторое и локальная сеть (е); трефовая модель той же оистемм (б) Один нз способов моделирования локальной сети состоит в том, что ЛВС рассматривается в виде узла графа, как и маршрутизаторы. Это показано на рис. 5.9, б. На рисунке сеть изображена в виде искусственного узла У, с которым соединены маршрутизаторы А, С и Е Возможность передачи пакетов от А к С по локальной сети отражается здесь наличием пути АУС. Измерение стоимости линии Алгоритм маршрутизации с учетом состояния линии требует от каждого маршрутизатора знания или хотя бы обоснованной оценки задержки для всех линий связи со своими соседями. Наиболее прямой способ определить эту задержку заключается в посылке по линии специального пакета ~ОНО, на который другая сто- Алгоритмы маршрутизации 419 рона обязана иемедленно ответить.
Измерив время двойного оборота этого пакета и разделив его иа два, отправитель получает приемлемую оценку задержки. Чтобы получить более точный результат, это действие можно повторить несколько раз, после чего вычислить среднее арифметическое. Коиечио, такой метод предполагает, что задержки являются симметричными, что ие всегда так, Возникает интересный вопрос: надо ли учитывать нагрузку иа линию во время измерения задержкиг Чтобы учесть загруженность линии, таймер должен включаться при отправке пакета ЕНО. Чтобы игнорировать загрузку, таймер следует включать, когда пакет ЕНО достигает начала очереди, Оба способа могут быть аргументированы. Учет трафика в линии при измереиии задержки означает, что когда у маршрутизатора есть выбор между двумя ливиями с одинаковой пропускной способностью, маршрут по менее загружениой линии рассматривается как более короткий.
Такой выбор приведет к более сбалансированному использованию линий связи и, следовательно, к более эффективной работе системы. К сожалеиию, можно привести аргумент и против учета загруженности ликии при расчете задержек. Рассмотрим подсеть, показанную иа рис. 5.10, Оиа разделена иа две части — восточную и западную, которые соединены двумя ливиями, СГи Е1.
Рис. В.10. Подсеть, в которой восточная и западная части соединены двумя линиями Предположим, что основная часть потока данных между востоком и западом использует линию СВ В результате эта линия оказывается сильно загруженной и с большими задержками. учет времени стояния пакета в очередях при подсчете кратчайшего пути сделает линию Е1 более привлекательной. После установки Повых таблиц маршрутизации большая часть потока данных между востоком и западом переместится на линию Е1, и ситуация повторится с точностью до смены одной линии на другую.
Аналогично, после еще одного обновления уже ливия СЕ окажется более привлекательной. В результате таблицы маршрутизации ' будут страдать от незатухающих колебаний, что сильно снизит эффективность 420 Глава 5. Сетевой уровень работы системы. Если же нагрузку не учитывать, то эта проблема не возникнет. Можно поступать по-другому: распределять нагрузку между двумя линиями. Однако такое решение приведет к неполному использованию наилучшего пути. Тем не менее, во избежание колебаний системы при выборе оптимального пути, по видимому, лучше всего распределять нагрузку между несколькими линиями, пуская определенные части трафика по каждой из них.
Создание пакетов состояния линий После того как информация, необходимая для обмена, собрана, следующий шаг, выполняемый каждым маршрутизатором, заключается в создании пакета, содержащего все зти данные. Пакет начинается с идентификатора отправителя, за которым следует порядковый номер и возраст (описываемый далее), а также список соседей. Для каждого соседа указывается соответствующая ему задержка. Пример подсети приведен на рис. 5,11, а, на котором показаны задержки для каждой линии.
Соответствующие пакеты состояния линий для всех шести маршрутизаторов показаны на рис. 5.11, б, В 2 С е 3 Пакеты состояния линий б Рис. 5.11. Подсеть (ей пакеты состояния линий для втой подсети (б] Создаются пакеты состояния линий несложно. Самое трудное заключается в выборе момента времени для их создания. Их можно создавать периодически чеРез равные интервалы времени, другой вариант состоит в создании пакетов, когда происходит какое-нибудь значительное событие — например, линия или сосед выходит иэ строя или, наоборот, снова появляется в сети либо существен- но изменяет свои свойства. Алгоритмы маршрутизации 421 Распространение пакетов состояния линий Самая сложная часть алгоритма заключается в распространении пакетов состояиия линий.
По мере распрострапеиия и установки пакетов маршрутизаторы, получившие первые пакеты, начинают изменять свои маршруты. Соответственно разные маршрутизаторы будут пользоваться разными версиями топологии, что может привести к противоречиям, появлению в маршрутах петель, недоступных машин, а также к другим проблемам. Сначала мы опишем основной алгоритм распространения.
Затем расскажем о некоторых улучшеииях. Основная идея алгоритма распространения пакетов состояния линии состоит в использовании алгоритма заливки. Чтобы держать этот процесс под контролем, в каждый пакет помещают порядковый номер, увеличивающийся иа единицу для каждого следующего пакета. Маршрутизаторы записывают все пары (источиик, порядковый помер), которые им попадаются. Когда приходит новый пакет состояния линий, маршрутизатор ищет адрес его отправителя и порядковый номер пакета в своем списке.
Если это новый пакет, ои рассылается дальше по всем линиям, кроме той, по которой ои пришел. Если же это дубликат, ои удаляется. Если порядковый номер прибывшего пакета меньше, чем номер уже полученного пакета от того же отправителя, то такой пакет также удаляется как устаревший, поскольку очевидно, что у маршрутизатора есть более свежие данные, С этим алгоритмом связано несколько проблем, ио с ними можно справиться, Во-первых, если последовательный номер, достигнув максимально возможного значения, обиулится, возникнет путаница. Решение состоит в использоваиии 32-разрядиых порядковых номеров.
Даже если рассылать каждую секунду по пакету, то для переполнения 4-байтового целого числа понадобится 137 лет. Во-вторых, если маршрутизатор выйдет из строя, будет потерян его порядковый номер. Если ои будет снова загружен с нулевым порядковым номером, его пакеты будут игнорироваться как устаревшие. В-третьих, может произойти искажение порядкового номера — например, вместо номера 4 будет принято число 65 540 (ошибка в 1-м бите); в этом случае пакеты с 5-го по 65 540-й будут игнорироваться некоторыми маршрутизаторами как устаревшие. Решение этих проблем заключается в помещении в пакет после его порядкового номера возраста пакета и уменьшении его иа единицу каждую секунду.
Когда возраст уменьшается до нуля, информация от этого маршрутизатора удаляется. В иормальиой ситуации новый пакет приходит, например, каждые 10 секунд; таким образом, сведения о маршрутизаторе устаревают, только когда маршрутизатор выключен (или в случае потери шести пакетов подряд, что маловероятно). Поле возраста также уменьшается иа единицу каждым маршрутизатором во время иачальиого процесса заливки, чтобы гарантировать, что ии одим пакет ие потеряется и ие будет жить вечно. Для повышения надежности этого алгоритма используются некоторые усовершеиствоваиия.
Когда пакет состояния линий приходит иа маршрутизатор для заливки, он ие ставится сразу в очередь иа отправку. Вместо этого ои сохраняет- 422 Глава Б. Сетевой уровень ся в течение некоторого периода времени в области промежуточного хранения, Если за это время от того же отправителя успевает прийти еще один пакет, маршрутизатор сравнивает их порядковые номера. Более старый пакет удаляется. Если номера одинаковые, то удаляется дубликат. Для защиты от ошибок на линиях связи между маршрутизаторами получение всех пакетов состояния линий подтверждается.
Когда линия освобождается, маршрутизатор сканирует область промежуточного хранения, нз которой выбираются для передачи пакеты илн подтверждения. Структура данных, используемая маршрутизатором В для работы с подсетью, изображенной на рис. 5.11, а, показана на рис. 5.12. Каждый ряд здесь соответствует недавно полученному, но еще не полностью обработанному пакету состояния линий, В таблице записываются адрес отправителя, порядковый номер, возраст и данные, Кроме того, в таблице содержатся флаги рассылки и подтверждений для каждой из трех линий маршрутизатора В (к А, С и Р соответственно).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
