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

Рис. 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.

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