Компьютерные сети. 6-е изд. - Эндрю Таненбаум

года он был заменен протоколом состояния каналов. В 1988 году IETF начал работу над протоколом внутридоменной маршрутизации, учитывающим состояние линий. Он получил название открытого алгоритма предпочтительного выбора кратчайшего маршрута (Open Shortest Path First, OSPF) и был признан стандартом в 1990 году. Идея была заимствована из протокола связи между промежуточными системами (Intermediate System to Intermediate System, IS-IS), ставшего стандартом ISO. У OSPF и IS-IS больше сходств, чем различий. Более подробное описание см. в RFC 2328.

Это основные протоколы внутридоменной маршрутизации. Сегодня они поддерживаются многочисленными производителями маршрутизаторов. OSPF чаще используется в корпоративных сетях, IS-IS — в сетях интернет-провайдеров. Ниже дано краткое описание работы протокола OSPF.

Учитывая большой опыт работы с алгоритмами, группа разработчиков согласовывала свои действия с длинным списком требований, которые нужно было соблюсти. Во-первых, алгоритм должен публиковаться в открытых источниках, отсюда буква «О» (Open — открытый) в OSPF. Патентованный алгоритм, принадлежащий одной компании, не подходит. Во-вторых, новый протокол учитывает широкий спектр параметров: физическое расстояние, задержку и т.д. В-третьих, это динамический алгоритм, который автоматически и быстро адаптируется к изменениям топологии.

В-четвертых (это требование впервые было предъявлено именно к OSPF), он должен поддерживать выбор маршрутов, основываясь на типе службы. Новый протокол должен уметь по-разному выбирать путь трафика реального времени и других видов трафика. В то время IP-пакет содержал поле Type of service, но ни один из имевшихся протоколов маршрутизации не использовал его. Это поле было и в OSPF, но и здесь оно игнорировалось. Поэтому в результате его убрали. Возможно, это требование опередило свое время, так как появилось до дифференцированного обслуживания, возродившего классы обслуживания.

В-пятых, протокол должен уметь распределять нагрузку на линии. Это связано с предыдущим пунктом. Большинство предыдущих протоколов отправляли все пакеты по одному наилучшему маршруту, даже если таких маршрутов два. Следующий по оптимальности маршрут не использовался совсем. Между тем во многих случаях распределение нагрузки по нескольким линиям дает лучшую производительность.

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

В-седьмых, необходим оптимальный минимум безопасности, который защищает маршрутизаторы от студентов-шутников, присылающих неверную информацию о пути. Наконец, требовалась поддержка для маршрутизаторов, подключенных к интернету по туннелю. Прежние протоколы справлялись с этим плохо.

OSPF поддерживает двухточечные линии (например, SONET) и широковещательные сети (большинство LAN). Он также поддерживает сети с множественными маршрутизаторами, каждый из которых может напрямую соединяться с любым другим (сети множественного доступа — multi-access networks), даже если в них невозможно широковещание. Предыдущие протоколы не так хорошо справлялись с этой задачей.

На илл. 5.65 (а) показан пример АС. Здесь не указаны хосты, так как обычно они не играют большой роли в OSPF. Значительно важнее — маршрутизаторы и сети (которые могут содержать хосты). Большинство маршрутизаторов соединены между собой двухточечными линиями, а также с сетями, к хостам

Илл. 5.65. Сеть множественного доступа. (а) Автономная система. (б) Представление (а) в виде графа

которых им нужен доступ. Но R3, R4 и R5 соединены широковещательной LAN, например коммутируемой Ethernet.

В основе работы OSPF лежит обобщенное представление о множестве сетей, маршрутизаторов и каналов в виде направленного графа, каждому ребру которого присвоен весовой коэффициент (расстояние, задержка и т.д.). Двухточечное соединение между двумя маршрутизаторами представляется в виде пары ребер, по одному в каждом направлении. Их веса могут различаться. Широковещательная сеть представляется в виде узла для самой сети, а также в виде узла для каждого маршрутизатора. Ребра, идущие от сетевого узла к узлам маршрутизаторов, обладают нулевым весом. Но они все равно важны, так как без них не будет пути через сеть. У других сетей, состоящих исключительно из хостов, имеются ребра, ведущие только к ним; ребра в обратном направлении отсутствуют. То есть маршруты к хостам возможны, а через них — нет.

Сеть на илл. 5.65 (а) представлена в виде графа на илл. 5.65 (б). По сути, как раз это и делает OSPF. Когда представление в виде графа получено, маршрутизаторы могут вычислить кратчайшие пути до всех остальных узлов с помощью метода, учитывающего состояние линий. Возможно, некоторые пути одинаково короткие. Тогда OSPF запоминает оба пути и использует их для разделения трафика. Этот метод называется использованием множества равноценных маршрутов (Equal Cost MultiPath, ECMP). С его помощью нагрузка распределяется более равномерно.

Многие АС в интернете сами по себе довольно крупные, и управлять ими непросто. OSPF позволяет делить их на пронумерованные области (areas), то есть на сети или множества смежных сетей. Области не должны перекрываться, но не обязаны быть исчерпывающими: некоторые маршрутизаторы могут не принадлежать ни к одной из них. Если маршрутизатор полностью принадлежит к какой-то области, он называется внутренним маршрутизатором (internal router). Область — это обобщение отдельной сети. За пределами области видны ее адреса, но не ее топология. Это упрощает масштабирование процесса маршрутизации.

У каждой АС есть магистральная область (backbone area), область 0. Маршрутизаторы, расположенные в ней, называются магистральными маршрутизаторами (backbone routers). Все области соединены с магистралью, например, туннелями, так что по магистрали можно попасть из одной области АС в любую другую. Туннель представляется на графе в виде ребра и обладает стоимостью. Как и в случае других областей, топология магистрали за ее пределами не видна.

Маршрутизатор, подключенный одновременно к двум или нескольким областям, называется пограничным маршрутизатором области (area border router). Он также должен быть частью магистрали. Его задача — собирать сведения об адресах одной области и передавать их другим областям. Эти сведения включают стоимость передачи, но не содержат полной информации о топологии области. Зная стоимость, хосты других областей могут выбрать пограничный маршрутизатор, через который они войдут в эту область. Отсутствие информации о топологии уменьшает трафик и упрощает вычисление кратчайших путей для маршрутизаторов вне данной области. Но если вне области есть только один пограничный маршрутизатор, эти сведения передавать бессмысленно. Все пути за ее пределы начинаются с указания «Идите на пограничный маршрутизатор». Такая область называется тупиковой областью (stub area).

Последний тип маршрутизаторов — пограничные маршрутизаторы автономной системы (AS boundary routers). Они прокладывают пути на внешние адреса в других АС области. Внешние маршруты становятся адресатами, до которых можно добраться через пограничный маршрутизатор АС с определенными затратами. Внешний путь может проходить один или несколько таких маршрутизаторов. Связь между АС, областями и разными типами маршрутизаторов показана на илл. 5.66. Один маршрутизатор может играть несколько ролей —