Компьютерные сети. 6-е изд.

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

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

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

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

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

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

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

Как видно из илл. 5.13, пакет состояния линий от маршрутизатора A пришел напрямую, поэтому он должен быть отправлен C и F, а подтверждение о его получении следует направить A, что и показывают флаговые биты. Аналогично пакет от F следует переслать маршрутизаторам A и C, а F отослать подтверждение.

Илл. 5.13. Буфер пакетов маршрутизатора B, показанного на илл. 5.12 (а)

Однако ситуация с третьим пакетом, полученным от маршрутизатора E, отличается. Он приходит дважды, по линиям EAB и EFB. Следовательно, его нужно отослать только C, но подтверждения необходимо выслать и A, и F, как указывают биты.

Если дубликат пакета приходит в тот момент, когда оригинал еще находится в буфере, значение битов должно измениться. Например, если копия пакета состояния C прибудет от F, прежде чем четвертая строка таблицы будет разослана, шесть флаговых битов примут значение 100011, и это будет означать, что нужно подтвердить получение пакета от F, но не пересылать его F.

Вычисление новых маршрутов

Собрав весь комплект пакетов состояния линий, маршрутизатор может построить полный граф сети, так как у него есть данные обо всех линиях. На самом деле каждая линия представлена даже дважды, по одному значению для каждого направления. Иногда эти значения различаются, поэтому результаты вычисления кратчайшего пути от A до B и от B до A могут не совпадать.