Эндрю Уэзеролл - Компьютерные сети. 5-е издание

1) обнаруживать своих соседей и узнавать их сетевые адреса;

2) задавать метрику расстояния или стоимости связи с каждым из своих соседей;

3) создавать пакет, содержащий всю собранную информацию;

4) посылать этот пакет всем маршрутизаторам и принять все пакеты, отправленные другими маршрутизаторами;

5) вычислять кратчайший путь ко всем маршрутизаторам.

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

Знакомство с соседями

Когда маршрутизатор загружается, его первая задача состоит в получении информации о своих соседях. Он достигает этой цели, посылая специальный пакетHELLO по всем линиям «точка-точка». При этом маршрутизатор на другом конце линии должен послать ответ, содержащий его имя. Имена маршрутизаторов должны быть совершенно уникальными, поскольку если удаленный маршрутизатор слышит, что три маршрутизатора являются соседями маршрутизатора F, то не должно возникать разночтений по поводу того, один и тот же маршрутизатор F имеется в виду или нет.

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

Рис. 5.9. Широковещательная ЛВС: а — девять маршрутизаторов и широковещательная локальная сеть; б — графовая модель той же системы

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

Задание стоимости связи

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

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

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