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

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

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

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

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

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

Рис. 5.11.Буфер пакетов маршрутизатора B c рисунка 5.10

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

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

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

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

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

Теперь для построения кратчайших путей ко всем возможным адресатам может быть локально применен алгоритм Дейкстры. Результат вычислений сообщает маршрутизатору, какое соединение следует выбрать, чтобы добраться до нужного адреса назначения. Эта информация добавляется в таблицы маршрутов, после чего возобновляется нормальная работа маршрутизатора.

В отличие от маршрутизации по вектору расстояния, маршрутизация с учетом состояния линий требует большего количества вычислений и памяти. В сети, состоящей из n маршрутизаторов, у каждого из которых k соседей, количество памяти, необходимой для хранения входной информации, пропорционально kn , что как минимум соответствует размеру таблицы маршрутизации, содержащей все адреса назначения. Кроме того, даже при использовании эффективных структур данных время, требующееся для обработки информации, растет быстрее, чем kn . В больших сетях это может составлять проблему. Тем не менее во многих практических ситуациях маршрутизация с учетом состояния линий работает вполне удовлетворительно, поскольку ее не затрагивает проблема медленной конвергенции.

Маршрутизация с учетом состояния линий широко применяется в современных сетях, поэтому следует сказать несколько слов о некоторых примерах протоколов. Многие интернет-провайдеры используют протокол маршрутизации с учетом состояния линий IS-IS( Intermediate System to Intermediate System— связь между промежуточными системами) (Oran, 1990). Он был разработан достаточно давно для сети DECnet и был впоследствии принят Международной организацией по стандартизации ISO для использования вместе с протоколами OSI. После этого он был модифицирован для поддержки также и других протоколов, в частности, IP. Еще один из наиболее известных протоколов маршрутизации с учетом состояния линий — OSPF ( Open Shortest Path First— открытый алгоритм предпочтительного выбора кратчайшего маршрута). Он был разработан Специальной комиссией интернет-разработок (IETF) через несколько лет после IS-IS и включал многие новшества, применявшиеся при создании IS-IS. К этим новшествам относятся метод саморегуляции лавинного потока обновлений информации о состоянии линий, концепция отмеченного маршрутизатора в локальной сети, а также метод вычисления и поддержки расщепления пути и умножения метрик. Соответственно, между протоколами IS-IS и OSPF нет почти никакой разницы. Наиболее существенное различие между ними заключается в том, что в IS-IS возможна одновременная поддержка нескольких протоколов сетевого уровня (например, IP, IPX и AppleTalk). OSPF не обладает таким свойством, и это оказывается преимуществом в больших многопротокольных средах. Более подробно о протоколе OSPF будет рассказано в разделе 5.6.6.