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

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

В отличие от маршрутизации по вектору расстояния, маршрутизация с учетом состояния линий требует большего количества вычислений и памяти. В сети из 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, необходимое для их обработки. При этом растет число служебных пакетов, которыми обмениваются маршрутизаторы, что увеличивает нагрузку на линию. Даже если бы каждый маршрутизатор мог хранить всю топологию сети, повторное вычисление кратчайших путей при каждом ее изменении привело бы к чрезмерной трате ресурсов. Представьте, что будет, если мы станем заново рассчитывать оптимальные пути при каждом отказе или восстановлении соединения в очень крупной сети. Когда-нибудь сеть вырастет до таких размеров, при которых будет невозможно хранить на каждом маршрутизаторе всю необходимую информацию. Поэтому в больших сетях маршрутизация осуществляется иерархически, с применением областей маршрутизации (routing areas).

При иерархической маршрутизации вся совокупность маршрутизаторов разбивается на отдельные регионы (regions), или области (areas). Каждый маршрутизатор знает все детали выбора пути в пределах своей области, но ему ничего не известно об устройстве других регионов. При объединении нескольких сетей логично рассматривать их как отдельные регионы, при этом маршрутизаторы одной сети не обязаны знать топологию других сетей.