В-третьих, может произойти искажение порядкового номера — например, вместо номера 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 могут не совпадать.

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

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

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

Следует также сказать несколько общих слов об алгоритмах маршрутизации. Маршрутизация с учетом состояния линий или по вектору расстояния, а также другие алгоритмы предполагают, что маршрутизаторы вычисляют путь. Однако неисправности оборудования или программного обеспечения могут привести к очень серьезным проблемам во всей сети. Например, если маршрутизатор заявит о существовании линии, которой у него нет, или, наоборот, забудет об одной из своих линий, граф сети окажется неверным. Если маршрутизатор не сможет переслать пакеты или повредит их при передаче, маршрут не будет работать корректно. Наконец, различные неприятности могут возникнуть, если у маршрутизатора закончится свободная память или он неправильно рассчитает путь. Когда сеть достигает размера в несколько десятков или сотен тысяч маршрутизаторов, вероятность ошибки одного из них становится значительной. Единственное, что можно сделать, — попытаться свети ущерб к минимуму, когда случится неизбежное. Эти проблемы и методы их решения подробно обсуждаются в работе Перлман (Perlman, 1988).

5.2.6. Иерархическая маршрутизация внутри сети

По мере роста сети постоянно увеличивается размер таблиц маршрутизации. Они занимают все больше памяти маршрутизатора, кроме того, возрастает время CPU, необходимое для их обработки. При этом растет число служебных пакетов, которыми обмениваются маршрутизаторы, что увеличивает нагрузку на линию.