Чтение онлайн

Если два или более маршрутизатора соединены с помощью широковещательной связи (например, коммутатора, кольцевой сети или классического Ethernet), ситуация несколько усложняется. На илл. 5.11 (а) изображена широковещательная LAN, к которой напрямую подключены три маршрутизатора: A, C и F. Каждый из них соединен с одним или несколькими дополнительными маршрутизаторами.

Илл. 5.11. Широковещательная LAN. (а) Девять маршрутизаторов и широковещательная LAN. (б) Графовая модель той же системы

Широковещательная LAN обеспечивает связь между каждой парой подключенных маршрутизаторов. Однако моделирование такой сети в виде системы связей «точка-точка» увеличивает топологию и ведет к неэкономной передаче. Существует более подходящая модель, в которой LAN представляет собой узел графа. На илл. 5.11 (б) она изображена в виде нового, искусственного узла N, с которым соединены A, C и F. Один из маршрутизаторов сети — отмеченный маршрутизатор (designated router) — выполняет роль N в протоколе маршрутизации. Маршрут от A до C по LAN в этом случае выглядит как путь ANC.

Определение стоимости связи

Алгоритм маршрутизации с учетом состояния линии требует, чтобы у каждого соединения был параметр расстояния или стоимости, необходимый для вычисления кратчайшего пути. Стоимость пути до соседних маршрутизаторов может быть задана автоматически или определена оператором сети. Чаще всего она обратно пропорциональна пропускной способности. Так, сеть Ethernet со скоростью 1 Гбит/с может иметь стоимость 1, а Ethernet со скоростью 100 Мбит/с — 10. Благодаря этому в качестве наилучшего выбирается путь с более высокой пропускной способностью.

Если узлы сети находятся далеко друг от друга, определить стоимость пути можно на основе задержки соединения. В этом случае наилучшим считается более короткий путь. Самый простой способ определения задержки — отправка специального пакета ECHO. Другая сторона обязана немедленно на него ответить. Измерив время прохождения пакета в оба конца и разделив его на два, отправитель получает приблизительное значение задержки.

Создание пакетов состояния линий

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

Илл. 5.12. (а) Сеть. (б) Пакеты состояния линий для этой сети

Создать пакет состояния линий несложно; труднее всего — правильно выбрать момент. Пакеты можно создавать периодически через равные временные интервалы либо когда происходит какое-то конкретное событие. Например, если линия или соседний маршрутизатор вышли из строя либо, наоборот, снова появились в сети или если они изменили свои свойства.

Распределение пакетов состояния линий

Самая сложная часть алгоритма состоит в распространении пакетов состояния линий. Все маршрутизаторы должны принимать такие пакеты быстро и безотказно. Если маршрутизаторы используют разные версии топологии, это может привести к проблемам — зацикленным путям, недоступным устройствам и т.д.

Мы начнем с базового алгоритма распределения, а затем расскажем о некоторых его модификациях. В его основе лежит алгоритм лавинной адресации, с помощью которого происходит отправка пакетов состояния линии на все маршрутизаторы. Чтобы держать этот процесс под контролем, в каждый пакет добавляют порядковый номер, который увеличивается на единицу для каждого следующего пакета. Маршрутизаторы записывают все пары «источник + порядковый номер», которые им встречаются. Когда приходит новый пакет состояния линий, маршрутизатор ищет адрес отправителя и порядковый номер пакета в своем списке. Если это новый пакет, он рассылается дальше по всем линиям, кроме той, по которой он пришел. Дубликаты удаляются. Если номер нового пакета меньше, чем номер уже полученного от того же отправителя, он также удаляется как устаревший, поскольку очевидно, что у маршрутизатора есть более свежие данные.

С этим алгоритмом связано несколько проблем, но они решаемы. Во-первых, если порядковый номер обнулится, достигнув максимального значения, возникнет путаница. Чтобы этого избежать, используются 32-битные номера. Даже если рассылать пакеты каждую секунду, для обнуления понадобится 137 лет, поэтому о нем можно не беспокоиться.

Во-вторых, если маршрутизатор выйдет из строя, будет потерян его порядковый номер. Если он снова запустится с нулевым номером, следующий отправленный им пакет будет проигнорирован как устаревший.

В-третьих, может произойти искажение порядкового номера — например, вместо номера 4 будет принято число 65,540 (ошибка в одном бите); в этом случае пакеты с 5-го по 65,540-й будут игнорироваться маршрутизаторами как устаревшие.

Решение указанных проблем заключается в указании возраста пакета после его порядкового номера. Каждую секунду этот параметр уменьшается на единицу. Когда возраст снижается до нуля, информация от соответствующего маршрутизатора удаляется. В нормальной ситуации новый пакет приходит, скажем, каждые 10 с; таким образом, сведения о маршрутизаторе устаревают, только когда он выключается (или в случае потери шести пакетов подряд, что маловероятно). Кроме того, каждый маршрутизатор уменьшает поле Возраст (Age) на единицу во время первоначальной лавинной адресации, чтобы гарантировать, что ни один пакет не потеряется и не будет существовать вечно (пакет с нулевым возрастом удаляется).

Для повышения надежности данный алгоритм был слегка доработан. Когда пакет состояния линий приходит на маршрутизатор для рассылки, он не сразу ставится в очередь на отправку. Вместо этого он ненадолго помещается в область промежуточного хранения на случай появления новых связей или разрыва старых. Если за это время от того же отправителя успевает прийти еще один пакет, маршрутизатор сравнивает их порядковые номера и удаляет устаревший. Если номера одинаковые, то удаляется дубликат. Для защиты от ошибок получение всех пакетов состояния линий подтверждается.

Структура данных, используемая маршрутизатором B для работы с сетью на илл. 5.12 (а), показана на илл. 5.13. Каждая строка соответствует недавно полученному, но еще не полностью обработанному пакету состояния линий. В таблицу записывается адрес отправителя, порядковый номер, возраст и данные. Кроме того, в ней содержатся флаги отправки и подтверждения для каждой из трех линий маршрутизатора B (к A, C и F). Флаги отправки означают, что пакет нужно отослать по указанной линии, а флаги подтверждения — что нужно сообщить о его получении.