История разработки OSPF

Уважаемые читатели, перед вами перевод Главы 3 книги OSPF: Anatomy of an Internet Routing Protocol за авторством John T. Moy. Эта глава проливает свет на историю появления одного из самых распространенных протоколов динамической маршрутизации и сопровождавшие это появление трудности, интриги и скандалы, в период с 1987 по 1993 год XX века. Чтение этой главы меня настолько увлекло, что не мог не поделиться с уважаемым сообществом. В переводе сохранены оригинальные ссылки на библиографию, так же учитывайте, что это уже историческое произведение, книга подписана в печать в 1998 году.

Глава 3. Разработка протокола OSPF

Разработка протокола маршрутизации OSPF началась в 1987 году. OSPF был одним из первых протоколов, полностью разработанных Internet Engineering Task Force (IETF).

Спустя десятилетие, рабочая группа IETF по разработке OSPF всё еще существует и протокол OSPF продолжает дополняться, хотя базовые функции были зафиксированы при первой публикации спецификации OSPF Version 2 (OSPFv2) в 1991 году.

Если мы проследим процесс разработки OSPF, то мы сможем понять процесс появления новых функций и почему они являются столь важными. Как и Интернет, OSPF изменяется с течением времени. Некоторые имеющиеся функции, например Point-to-Multi-Point interface, не планировались в оригинальном дизайне, а функция TOS based routing была включена в дизайн, но не была реализована.

Функциональные требования

Для понимания первоначальных целей OSPF Working Group вам необходимо понять, как выглядел Internet в 1987 году. Это была в значительной мере академическая и исследовательская сеть, финансируемая правительством США, её ядро, ARPANET, было замещено бэкбонами сети NSFNET и ее региональными сетями. В большинстве случаев используется статическая маршрутизация, внутри автономных систем используется Routing Information Protocol (RIP), в то время как для маршрутизации между автономными системами используется Exterior Gateway Protocol (EGP).

Оба этих протокола имеют свои проблемы. Размер автономных систем растет, что приводит к увеличению объема таблиц маршрутизации Internet, для рассылки обновлений маршрутной информации протоколу RIP требуется всё больше полосы пропускания, время схождения сети становится неприемлемым из-за растущего количества изменений маршрутов. Размер обновлений EGP так же увеличивается и вследствие топологических ограничений (техническое требование древовидной топологии, описываемое термином "протокол доступности" более точно, чем "протокол маршрутизации") EGP быстро становится неуправляемым.

В результате, было принято решение искать замену RIP, так как на это имелось две причины, перевешивающие необходимость устранения проблем EGP. Во-первых, проблема RIP казалась проще вследствие локальности масштаба, чем работа с протоколом, необходимым для функционирования всего Internet. Во-вторых, замена RIP будет иметь более широкое применение, будучи применима как в Internet, так и в коммерческих сетях TCP/IP (то, что люди сегодня называют intranet).

Таким образом, основным требованием было создание протокола маршрутизации, используемого внутри автономной системы (также называемого Interior Gateway Protocol, или IGP), более эффективного, чем RIP. Хотелось, что-бы новый протокол потреблял меньше ресурсов, чем RIP и при этом имел более быструю сходимость в случае изменений на сети, таких как отказ маршрутизатора, интерфейса или канала связи. После отказа произойдет изменение лучшего маршрута к точке назначения, что занимает определенное время для любого протокола, в течение которого используемый путь может быть неоптимальным или вовсе нефункционирующим. Процесс нахождения нового пути был назван "сходимостью".

Другие начальные функциональные требования для OSPF указаны ниже.

• Более содержательная метрика маршрута. В качестве метрики маршрута, RIP использует число хопов и стоимость пути может принимать значения от 1 до 15. Это создает две проблемы для сетевых администраторов - ограничивается диаметр сети до 15 маршрутизаторов и администраторы не имеют возможности учитывать факторы пропускной способности и/или задержки при конфигурировании системы маршрутизации. Для OSPF был установлен диапазон конфигурируемой метрики канала от 1 до 65535, без ограничения по общей стоимости линка. Такой дизайн позволил убрать ограничение на диаметр сети и сделал возможным реализацию топологии с преобладанием промежуточных линков над прямым.

• Балансировка по равнозначным линкам. Мы хотели дать OSPF возможность найти несколько лучших путей к месту назначения, если они существуют. Тем не менее, мы не определяли, как маршрутизатор будет использовать эти пути для передачи пакетов, в результате, могут использоваться различные стратегии - round-robin, хэш от адреса источника или что-то другое. Таким образом, маршрутизаторы с различными стратегиями могут смешиваться в пределах сети с предсказуемым успешным результатом.

• Иерархия маршрутизации. Мы хотели иметь возможность строить очень большие домены маршрутизации, включающие тысячи маршрутизаторов. Единственным известным путём масштабирования является внедрение иерархии. Иерархия OSPF была реализована через схему маршрутизации с двухуровневыми областями.

• Разделение внешних и внутренних маршрутов. Автономные системы, использующие RIP, имели проблемы с определением информации, заслуживающей доверия. Вы всегда больше доверяете внутренней информации, полученной от ваших маршрутизаторов, по сравнению с внешними маршрутами, инжектированными в ваш домен. RIP не делает различия между этими двумя типами маршрутов. В OSPF внешние маршруты должны быть явно обозначены и могут быть переписаны любыми внутренними маршрутами.

• Поддержка более гибкой схемы деления на подсети. Когда разрабатывался OSPF, Internet продолжал использовать классовую адресацию - A,B,C. Разделение на подсети существовало, но оно всегда происходило делением существующих классов на равные семядоли. Тем не менее, мы чувствовали, что люди хотят более оптимально использовать имеющееся адресное пространство, поэтому мы указали требование к OSPF работать с произвольными комбинациями адресов и масок. Так же, мы хотели иметь возможность работать с так называемыми масками подсети переменной длины (VLSMs), что позволило бы нарезать сети классов A, B, C на сети разного размера. Это требование в значительной степени соответствовало бесклассовой адресации (CIDR). Тем не менее, она должна была быть немного изменена, чтобы полностью соответствовать CIDR.

• Безопасность. Мы хотели иметь возможность в административном порядке контролировать присоединение маршрутизаторов к домену OSPF. Проблемой RIP является то, что любой может установить в сети маршрутизатор, выдающий маршрут по умолчанию (или любой другой маршрут), нарушив тем самым маршутизацию. При проверке подлинности принятых пакетов OSPF, отправляющий маршрутизатор должен был бы указать правильный ключ, прежде чем он сможет присоединиться к домену маршрутизации OSPF. Это требование привело нас к необходимости зарезервировать место в пакетах OSPF для данных аутентификации, но развитие алгоритмов аутентификации заставило нас ждать появление этого функционала в OSPF еще несколько лет.

• Маршрутизация на базе типа сервиса. Мы хотели иметь возможность рассчитывать маршрут исходя из значений IP Type of Service(TOS). TCP/IP поддерживает пять классов TOS: normal service, minimize monetary cost, maximize reliability, maximize throughput и minimize delay. Идея заключается в том, что IP-пакеты могут быть помечены конкретным TOS, и впоследствии по разному обработаны, в том числе, возможно, маршрут может указывать на то, что пакет будет приниматься через Интернет (так называемая TOS-маршрутизация). OSPF поддерживает TOS-маршрутизацию с самого начала, позволяя назначать разные метрики линкам и строить отдельные таблицы маршрутизации для каждого TOS. Например, на рисунке 3.2, может быть назначена вторая метрика для maximize-bandwidth TOS, позволяя нам использовать спутниковый канал как предпочтительный для передачи файлов, в тоже время, избегая использовать его для передачи других типов данных. Поддержка TOS была сделана опциональной, так как было множество вопросов о том, что должно произойти с пакетом, обозначенного, например, как minimize monetary cost, когда такого пути не существовало, но имеется путь для normal service. Будет ли пакет отброшен, или он должна быть отправлен по пути для normal service?

Дизайнерские решения

После разработки требований, можно приступать к дизайну протокола. Этот раздел описывает некоторые из основных проектных решений, принятых в ходе первоначальной разработки протокола OSPF. Некоторые решения были спорными, другие вполне обоснованными.

Одним из неоспоримых дизайнерских решений был формат пакета OSPF. Как и для
большинства протоколов TCP / IP, мы хотели выровнять пакеты OSPF таким образом, чтобы они могли легко обрабатываться имеющимися аппаратными платформами: 4-байтовые поля, начинающиеся со смещением, кратным 4-м байтам, 2-байтовые поля, начинающиеся с четного смещения и т.д. Хорошо выровненные пакеты помогут при реализации протокола на таких языках, как C, делая возможным использования структур данных в качестве шаблонов, упрощая прием и передачу пакетов.

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

Дистанционно-векторный алгоритм против протокола состояния канала

Дистанционно-векторные протоколы были общепринятым выбором при использовании в Интернет, при этом RIP является главным представителем этого семейства. Дистанционно-векторный протокол использует модель распределенной обработки – это означает, что каждый маршрутизатор выполняет расчет таблицы маршрутизации на основе текущей информации, полученной от своих соседей. Затем маршрутизатор отправляет промежуточные результаты этого расчета (как правило, текущую таблицу маршрутизации) всем своим соседям, заставляя их переделывать свои расчеты на основе обновленной информации. Соседи, в свою очередь отправляют свои обновленные таблицы маршрутизации своим соседям, и так далее. Этот процесс итерационно повторяется до тех пор, пока все маршрутизаторы не определятся с лучшими маршрутами к сетям назначения.

Протоколы состояния канала (также называемые протоколами определения кратчайшего пути, SPF, поскольку, обычно, используют алгоритм Дейкстры для определения кратчайшего пути к узлам графа для расчета таблицы маршрутизации) реализуют модель распределенной базы данных. Каждый маршрутизатор, на котором выполняется алгоритм SPF описывает своё локальное окружение используя объявления состояния канала, LSA. Локальное окружение включает в себя активные интерфейсы, стоимость отправки трафика из интерфейса, а также к чему подключен интерфейс. Эти LSA рассылаются всем другим маршрутизаторам в рамках процесса, называемого flooding(далее по тексту "лавинообразная рассылка"). В конечном итоге, маршрутизаторы, имея единый набор LSA строят базу данных состояния каналов. Используя эту базу данных маршрутизаторы строят собственную таблицу маршрутизации с помощью алгоритма Дейкстры.

Как указывалось ранее, в некоторых больших автономных системах сети Интернет были проблемы при использовании RIP. RIP имел большое время сходимости и потреблял много полосы пропускания а так же медленно удалял недоступные маршруты, используя процедуру, называемую «counting to infinity». Действительно, как показано в ссылках полной версии книги ([20] и [120]), когда изменение сети вызывает пересчет наилучшего пути к месту назначения, запись в таблице маршрутизации до сети назначения будет, для дистанционно-векторного алгоритма, при определенных обстоятельствах, принимать все промежуточные значения между старой и новой стоимостью, прежде чем, наконец, сойдется на новом значении.

BBN(Примечание переводчика: похоже, речь идет о компании Raytheon BBN(в девичестве Bolt Beranek and Newman Inc.)) видела подобное поведение в первоначальном алгоритме маршрутизации ARPANET, который являлся дистанционно-векторным. Недостатки этого алгоритма включали в себя медленную реакцию на изменения топологии сети, большой трафик пакетов обновления, которые влияли на трафик данных, а также склонность к образованию петель, которые могли сохраняются в течение секунд. В качестве ответа на эти проблемы, BBN разработала первый алгоритм состояния канала, который хорошо зарекомендовал себя после замены первоначального алгоритма маршрутизации ARPANET.

После успеха BBN в применении первого алгоритма состояния канала, мы решили разработать алгоритм состояния канала для TCP/IP. Имелось значительное расхождение во взглядах по этому вопросу, однако протоколы маршрутизации на основании состояния канала являются более сложными для описания и реализации, чем дистанционно-векторные протоколы. И хотя маршрутизация на основании состоянии канала выглядела весьма многообещающим, на тот момент еще не было случая реализации многовендорного протокола маршрутизации, в связи с чем некоторые люди считали эту задачу невыполнимой.

По факту, конфликты были столь обширны, что пришлось сменить наименование рабочей группы с Open Interior Gateway Protocol (OIGP) Working Group на Open Shortest Path First Interior Gateway Protocol (OSPFIGP, позднее сокращенной до OSPF) и, существовавшая недолгое время прямо конкурирующая Open Distance Vector Working Group.

Оглядываясь назад, можно увидеть общее стремление индустрии к протоколам определения состояния канала. Помимо протокола OSPF для TCP/IP, протоколы маршрутизации на основании состояния канала были разработаны для всех других основных семействах протоколов: IS-IS для OSI, NetWare Link Services Protocol (NLSP) для Novell Netware, Advanced Peer-To-Peer Networking (APPN) для IBM SNA и Private Network-to-Network Interface (PNNI) для ATM. Тем не менее, споры о преимуществах и недостатках дистанционно-векторных протоколов и протоколов состояния канала продолжаются в более приглушенной форме до сих пор. Исследования в части устранения недостатков дистанционно-векторных алгоритмов продолжаются, с некоторыми из этих улучшений можно ознакомиться в пропиетарной реализации протокола IGRP компании Cisco. RIP, квинтэссенция дистанционно-векторных алгоритмов был расширен для работы в бесклассовых сетях и по-прежнему широко используется в Интернете. Протокол BGP также является дистанционно-векторным.

Основы протоколов состояния канала

Сделав выбор в пользу создания протокола состояния канала для TCP/IP , мы обнаружили, что на тот момент было совсем немного технологий, которые можно было бы использовать. BBN был пионером в этой области, развернув в сети ARPANET первую реализацию протокола маршрутизации по состоянию канала в мае 1979 года. ARPANET, для протокола маршрутизации, был одновременно простой и сложной средой, так как ARPANET была сетью с пакетной коммутацией, которая предоставляет услуги на двух уровнях эталонной модели OSI, подобно сети передачи данных Х.25 (PDN). Среда ARPANET была простой из-за своей однородности: все маршрутизаторы были изготовлены одним и тем же производителем, работали на одинаковом программном обеспечении и были соединены между собой последовательными каналами со скоростями от 9.6Kb до 56kb. Тем не менее, процесс маршрутизации в ARPANET был дополнен работой, не выполнявшейся ни одним из протоколов маршрутизации TCP/IP: он не только осуществлял маршрутизацию, но и занимался контролем перегрузки в сети.

Протокол, используемый ARPANET, обладал всеми базовыми механизмами протокола состояния канала: база данных состояния каналов, передача базы между хостами и подсчет кратчайшего пути. Маршрутизация на базе зон так же была разработана, но так и не была внедрена. Тем не менее, протокол требовал усовершенствования, например, объем трафика протокола был довольно высок и частота обновления базы данных была обратно пропорциональна скорости канала. В качестве примера можно привести один из известных сбоев сети, когда из-за уязвимости в алгоритме распространения базы данных сеть смогла быть восстановлена только после одновременного отключения всех коммутаторов сети. Меры по устранению этих проблем были предложены Перлманом в своей статье 1983 года.

BBN также провела работы по преобразованию из протокола состояния канала ARPANET в протокол маршрутизации для TCP/IP [152]. Однако этот протокол был слишком неэффективным при использовании с физическими средами, распространенными в Интернете, такими как Ethernet, потому что BBN имитировала среду ARPANET, относясь к маршрутизаторам, подключенным к Ethernet, так, как если бы они были попарно соединены последовательными линиями.

В то же время, когда мы разрабатывали OSPF для TCP/IP, организация стандартов ISO разрабатывала протокол маршрутизации состояния канала под названием IS-IS для стека протоколов OSI [112]. Для протокола IS-IS уже был разработан эффективный механизм для работы протоколов состояния канала по широковещательным каналам, таким как локальные сети Ethernet, выбирая Designated Router для контроля лавинообразной передачи и сокращения объема информации для каждой локальной сети.

Это был хороший опыт по реализации протокола маршрутизации по состоянию канала, который мы могли использовать в качестве основы для разработки нашего протокола. В то время некоторые люди задавались вопросом: «Почему бы просто не принять протокол маршрутизации IS-IS OSI в качестве нового протокола маршрутизации?» IS-IS разрабатывался одновременно с разработкой OSPF, но глядя на новый протокол IS-IS, мы увидели ряд препятствий на пути его превращения в протокол маршрутизации TCP/IP. Упомянем некоторые из этих проблем в качестве примера. Во-первых, IS-IS работает непосредственно на канальном уровне, что, как мы считаем, было неправильным выбором для протокола маршрутизации TCP/IP, почему, объясняется далее. В то время у IS-IS не было возможности фрагментировать LSA, при этом маршрутизатору приходилось указывать все данные по маршрутизации внутри одного LSA. В некоторых средах TCP/IP, в которых маршрутизаторы импортируют множество внешних маршрутов, такая конструкция будет неработоспособной. IS-IS имел схему маршрутизации по зонам(area), но он не допускал каких-либо суммаризаций между зонами, которые, по нашему мнению, были необходимы для протокола маршрутизации Интернета. Кроме того, IS-IS не предпринял никаких попыток выровнять поля в форматах пакетов, что усложняло жизнь разработчикам протоколов.

Учитывая эти и другие технические проблемы, мы посчитали, что проще разработать новый, чем пытаться модифицировать такой протокол, как IS-IS. Были и не технические соображения. Многие люди считали, что было бы лучше, если IETF имел полный контроль над разработкой протокола OSPF, а не зависел от комитета ISO, чьи цели, а именно создание протокола маршрутизации для стека протоколов OSI, были несколько иными. Столь же спорное, как и решение о выборе протокола состояния канала в сравнении с дистанционно-векторным, решение о разработке совершенно нового протокола маршрутизации оставалось яблоком раздора в течение многих лет, вплоть до 1992 года, когда OSPF был выбран в качестве рекомендованного IGP для сети Internet.

Инкапсуляция

При разработке протокола маршрутизации TCP/IP у вас есть три варианта инкапсуляции пакетов вашего нового протокола: они могут проходить непосредственно через канальный уровень, через сетевой уровень IP или через транспортные протоколы IP - UDP или TCP.

Работа непосредственно через канальный уровень проблематична по нескольким причинам. Большинство сред канального уровня не предоставляют услуги фрагментации и повторной сборки, поэтому ваш протокол маршрутизации должен будет реализовать собственную фрагментацию. Вам также потребуется назначить идентификаторы для всех различных сред канального уровня, на которых работает ваш протокол, например тип «Ethernet» для работы через Ethernet.

Работа через IP позволяет вашему протоколу использовать все службы сетевого уровня IP. Вы можете использовать фрагментацию и повторную сборку протокола IP вместо реализации своего собственного алгоритма. IP работает практически по любому типу канала; поэтому, если ваш протокол работает через IP, вам не нужно беспокоиться о назначении идентификаторов для различных сред канального уровня. Если вы хотите отправлять пакеты протокола маршрутизации более чем на один переход и если вы достаточно благоразумны, вы даже можете использовать службы переадресации(forwarding) уровня IP (OSPF делает это для своих виртуальных каналов; см. Раздел 6.1.1). Однако вы должны быть осторожны, чтобы не попасть в ситуацию «курица и яйцо», когда ваш протокол маршрутизации зависит от переадресации, которая, в свою очередь, зависит от данных, предоставляемых вашим протоколом маршрутизации.

Использование UDP дает вам несколько дополнительных преимуществ. Он предоставляет вам дополнительную контрольную сумму для проверки целостности пакетов вашего протокола. Каждому протоколу UDP назначается порт UDP для мультиплексирования на уровне UDP, и этих портов UDP гораздо больше, чем номеров протоколов IP, поскольку они занимают 16-битное, а не 8-битное пространство. Кроме того, протокол UDP легче использовать во многих операционных системах: часто для отправки или получения пакетов непосредственно по IP требуются особые привилегии (например, статус «суперпользователя» в системе UNIX), тогда как интерфейс UDP обычно доступен всем пользователям и их приложения(Примечания переводчика: похоже, речь идет о особенностях программирования raw sockets, datagram sockets и stream sockets). При работе через TCP дополнительным преимуществом является использование гарантированной доставки (например, BGP [208]).

Нам не нужна была надежность TCP, так как протоколы маршрутизации по состоянию канала имеют свои собственные механизмы обеспечения надежности, встроенные в их алгоритмы лавинообразной рассылки, и TCP будет только мешать. Кроме того, простота приложений в UNIX и других операционных системах для отправки и получения пакетов UDP рассматривалась некоторыми как недостаток; необходимость получения привилегий ОС рассматривалась как обеспечение некоторой небольшой степени безопасности. Дополнительные небольшие преимущества инкапсуляции UDP перевешивались дополнительными 8 байтами заголовка UDP, которые появлялись в каждом пакете протокола. Поэтому мы решили реализовать OSPF непосредственно на сетевом уровне IP и получили от IANA номер IP-протокола 89 [212].

Еще одна проблема, связанная с инкапсуляцией, возникла при работе в широковещательных сетях, таких как локальные сети Ethernet. Существующие протоколы маршрутизации TCP/IP, такие как RIP, передают пакеты протокола маршрутизации в виде широковещательной рассылки(broadcast) в этих сетях. Однако это означало, что все хосты в локальной сети будут получать пакеты RIP, даже если на них не используется RIP (или даже если они не используют стек TCP/IP). Новая технология — многоадресная IP-адресация(multicast) — решила эту проблему, позволив отправлять и затем получать один IP-пакет только тем хостам, которые заинтересованы в этом пакете. Проблема с многоадресной IP-адресацией заключалась в том, что она не поддерживалась большинством операционных систем. Например, если вы хотите использовать многоадресную рассылку IP на рабочей станции UNIX, вам придется собрать собственное ядро UNIX с поддержкой multicast. Но многоадресная рассылка явно была лучшим решением, чем широковещательная, поэтому мы запросили пару IP-адресов многоадресной рассылки для использования OSPF через Ethernet и другие широковещательные сети (см. раздел 5.2).

Фрагментация LSA

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

В OSPF мы могли бы сделать LSA довольно большими; поскольку OSPF имеет доступ к возможностям фрагментации и повторной сборки уровня IP-сети, длина LSA OSPF могла достигать 65 000 байт. Однако обычно следует избегать фрагментации IP [125]. Поэтому мы определенно хотели сделать LSA OSPF меньше, чем MTU обычных каналов, найденных в Интернете. Обычно, MTU в сетях Ethernet составляет 1500 байт [165].

Максимально большие размеры LSA минимизируют статический размер базы данных о состоянии каналов, поскольку накладные расходы на заголовок LSA уменьшаются при большем количестве данных. Однако мы решили сделать LSA OSPF как можно меньшими, объявив каждую отдельную часть данных маршрутизации в отдельном LSA. Увеличение размера базы данных о состоянии каналов фактически сводит к минимуму общий объем передаваемой маршрутной информации; когда что-то в домене маршрутизации OSPF меняется, перезагружается только измененная информация о маршрутизации.

Сохранение данных в LSA небольшого размера и фиксированного формата также упростило сборку и анализ пакетов LSA. Это было важно для тех из нас, кто потратил много времени на написание кода для сборки пакетов в таких протоколах маршрутизации, как BGP [162], со сложными форматами пакетов.

Обратите внимание, что мы не сделали формат LSA гибким и открытым, как это делается в других протоколах состояния канала. Хотя гибкие форматы позволяют некоторым реализациям экспериментировать с эффективными алгоритмами упаковки, они усложняют разработку кода приема пакетов и тестирование совместимости из-за увеличения количества тестовых комбинаций. Хуже того, гибкие форматы делают сеть уязвимой для плохих алгоритмов упаковки в других реализациях.

Общие механизмы в различных физических сетях

В Интернете используется множество видов технологий канального уровня с различными свойствами. Некоторые могут соединять только два маршрутизатора, например синхронные последовательные линии. Другие могут подключать множество маршрутизаторов, например, такие как Frame Relay. Некоторые из них могут разрешать широковещательную или многоадресную рассылку пакетов, например Ethernet. Другие — нет, например, сети ATM. Технологии связи также имеют разные MTU, скорости передачи и частоту ошибок. Маршрутизация по состоянию канала, первоначально разработанная для ARPANET, была разработана для маршрутизаторов, соединенных между собой через выделенные последовательные линии (называемые в OSPF каналами «точка-точка»). Однако мы хотели, чтобы OSPF работал со всеми технологиями и типами каналов Интернета и работал одинаково с каждой технологией каналов или, по крайней мере, минимизировал любые функции, специфичные для канала. Далее последует несколько примеров.

Первым примером была лавинообразная рассылка LSA по широковещательным локальным сетям. Мы могли бы смоделировать набор из n маршрутизаторов, подключенных к широковещательной локальной сети asn*(n-l)/2 соединений «точка-точка»(по одному на каждую пару маршрутизаторов), а затем запустить алгоритм двухточечной лавинообразной рассылки для каждого соединения. Несмотря на простоту, этот подход обходится слишком дорого с точки зрения объема трафика, который будет передаваться по локальной сети. Вместо этого мы использовали обходной путь: мы смоделировали подключение к локальной сети с точки зрения алгоритма лавинообразной рассылки как сеть я топологией «звезда» из n двухточечных соединений. В локальной сети выбирается специальный маршрутизатор, называемый Designated Router, и всем остальным маршрутизаторам в локальной сети необходимо рассылать LSA только на DR или от него. Использование такого механизма позволяет минимизировать трафик лавинообразной рассылки в локальной сети (см. раздел 5.2.2).

Другим примером является работа OSPF поверх сетей X.25. За исключением отсутствующих возможностей широковещательной/многоадресной рассылки, что касается работы протокола состояния канала, сеть X.25 имела те же свойства, что и Ethernet: множество маршрутизаторов, подключенных к общей среде, каждая пара которых может обмениваться данными напрямую. Для подобных сетей мы придумали термин NBMA (nonbroadcast multiaccess, нешироковещательный множественный доступ). Работа OSPF через NBMA практически идентична работе OSPF в широковещательных локальных сетях: при лавинообразной рассылке используется Designated Router, и обе сети одинаково представлены в базе данных состояния каналов OSPF с помощью Network-LSA (см. раздел 5.2.3). Единственная реальная разница между широковещательными сетями и сетями NBMA заключается в обнаружении соседних маршрутизаторов. В широковещательных сетях маршрутизатор может динамически обнаруживать своих соседей, отправляя многоадресные запросы (в OSPF называемые пакетами Hello); в сетях NBMA может потребоваться настройка соседей маршрутизатора (см. раздел 5.3.1).

К сожалению, не все технологии связи могут быть напрямую сопоставлены с выделенными линиями или сетями Ethernet. Например, для поддержки OSPF по коммутируемым телефонным линиям пришлось разработать набор существенно отличающихся механизмов (см. раздел 7.3).

Backup Designated Router

При работе с широковещательными сетями и сетями NBMA OSPF полагается на Designated Router. Все LSA, передаваемые по широковещательной сети или сети NBMA, проходят через Designated Router этой сети, который отвечает за предоставление данных о локальной топологии сети через network-LSA. Однако такое поведение приводит к проблемам с надежностью. При выходе из строя Designated Router ни LSA, ни пользовательские данные не могут пересылаться по сети до тех пор, пока не будет установлен новый Designated Router.

Даже непреднамеренная замена текущего DR другим приводит к некоторым сбоям, поскольку все маршрутизаторы должны синхронизироваться с новым DR, а новая network-LSA рассылается на все маршрутизаторы OSPF, заставляя все маршрутизаторы повторно выполнять расчеты маршрутизации. Чтобы гарантировать, что переключение DR происходит только в случае сбоя, мы разработали процедуру выбора DR, чтобы маршрутизаторы, вновь добавленные в сеть, всегда подчинялись существующему DR.

Затем, чтобы обеспечить максимально быстрое переключение в случае сбоев, мы представили концепцию Backup Designated Router. BDR также проходит процедуру выборов, а затем проходит предварительную квалификацию, чтобы стать DR, при этом текущий DR продолжает работать в штатном режиме. Если DR выходит из строя, BDR поддерживает лавинообразную рассылку по сети даже до того, как будет обнаружен сбой DR (см. Раздел 5.2.2). Как только сбой обнаружен, BDR становится DR; поскольку все остальные маршрутизаторы в сети уже синхронизированы с BDR, переключение происходит относительно безболезненно.

External Route Tag

Мы разработали способ импорта внешних маршрутов в домен маршрутизации OSPF. Внешние маршруты — это маршруты, полученные из других источников: маршруты, полученные из протоколов маршрутизации, таких как RIP или BGP, или из статики, настроенной лихими сетевиками. Каждый внешний маршрут импортируется в отдельный LSA. По настоянию одного из членов рабочей группы OSPF Майло Медина мы также импортировали каждый маршрут с 32-битным тегом, называемым внешним тегом маршрута. Этот тег не используется самим протоколом OSPF, а вместо этого должен был использоваться для прозрачной для OSPF передачи информации через домен маршрутизации OSPF. Хотя при первоначальном проектировании OSPF мы не знали точно, для чего будет использоваться этот тег, с годами он оказался очень полезным.

Первое использование тега заключалось в передаче информации о политике между маршрутизаторами на границе домена OSPF. В Интернете один маршрутизатор может импортировать тысячи внешних маршрутов в домен маршрутизации OSPF. Другие маршрутизаторы на границе домена OSPF после изучения маршрутов должны решить, следует ли повторно объявлять их в других доменах маршрутизации. Маршрутизатор обычно принимает это решение путем сканирования вручную настроенных списков фильтров маршрутизации. Этот тег упрощает настройку фильтров маршрутизации, позволяя группировать маршруты по политике при импорте в домен OSPF. Тогда политика маршрутизации может просто сказать: «Переобъявить маршруты с тегом X», а не «Переобъявить маршруты X lr X2,..., Xn». Аналогичная функциональность обеспечивается в BGP при использовании BGP communities [39].

Были написаны правила обмена информацией о маршрутизации между протоколами маршрутизации OSPF и BGP (см. раздел 11.6.1). Использование тега внешнего маршрута позволяет маршрутизаторам OSPF импортировать маршруты (а именно, маршруты RIP, статически настроенные маршруты или маршруты, полученные через BGP с короткими AS paths) с достаточной дополнительной информацией для создания правильных атрибутов BGP на другой стороне домена маршрутизации OSPF. Эта возможность устраняет необходимость также объявлять такие маршруты в домене маршрутизации OSPF в IBGP. Хотя это еще не реализовано, использование тега также позволяет полностью заменить IBGP альтернативным механизмом OSPF (см. раздел 7.6).

Иерархическая абстракция

Чтобы иметь возможность строить большие сети OSPF, мы разрешили разделить домен маршрутизации OSPF на регионы или зоны(areas). Детали любой конкретной зоны должны были быть скрыты от всех других зон, а адресная информация суммировалась при анонсе за пределами зоны. Обе эти функции уменьшат размер таблицы маршрутизации маршрутизатора и базы данных состояний каналов, тем самым позволяя увеличить размер общего домена маршрутизации. Разделение домена маршрутизации OSPF на зоны также можно рассматривать как двухуровневую иерархическую схему маршрутизации (см. главу 6 «Иерархическая маршрутизация в OSPF»).

Необходимо было принять несколько проектных решений по организации зон. Во-первых, что будет находиться на границе зоны — маршрутизаторы, сегменты сети или и то, и другое? Как обсуждалось ранее, Интернет разделен на автономные системы, границы которых состоят из сетевых сегментов. Однако для зон OSPF мы пошли противоположным путем, выбрав маршрутизаторы в качестве границ зоны. Это решение означало, что каждый сегмент сети будет принадлежать одной и только одной зоне, и это свойство, как мы думали, облегчит агрегацию адресов через границы зон.

Во-вторых, как бы мы описали одну зону другим зонам? Чтобы достичь желаемых свойств масштабирования, нам пришлось сократить объем информации, связанной с определенной зоной, прежде чем объявлять ее в других зонах. Такое сокращение информации называется абстракцией. Абстракция в алгоритме маршрутизации по состоянию канала является сложной проблемой. Мы рассмотрели аналог OSPF network-LSA, который абстрагирует соединения OSPF в заданной широковещательной сети (см. раздел 5.2.3); однако такая абстракция имеет тенденцию искажать метрическую информацию. Вместо этого мы решили просто суммировать список адресов, доступных в этой зоне. Эти адреса затем передаются из зоны в зону точно так же, как маршруты объявляются от маршрутизатора к маршрутизатору в рамках дистанционно-векторного протокола (см. раздел 2.3). Другие схемы абстракции маршрутизации по состоянию канала см. в [9] и [38].

OSPFv1: фальшстарт

Спецификация протокола OSPF была впервые опубликована в октябре 1989 года как RFC 1131 [174]. Как и большинство интернет-протоколов, OSPF имеет номер версии. RFC 1131 документирует версию 1 протокола OSPF.

Девиз IETF — грубый консенсус и работающий код. Завершение проектирования OSPF было первой частью работы рабочей группы OSPF; теперь нам нужно было доказать, что протокол работает, реализовав его.

Были написаны две реализации OSPFv1: одна для работы на маршрутизаторах Proteon, а другая, написанная Робом Колтаном из Университета Мэриленда, для работы на рабочих станциях UNIX. Последняя реализация была доступна в виде исходного кода за весьма символическую плату. Эта реализация позже получила достаточно широкое распространение и теперь доступна как часть программного продукта, реализующего набор протоколов динамической маршрутизации GATED [83].

Реализация нового протокола неизменно обнаруживает проблемы, и OSPFv1 не стал исключением. Первая проблема, которую мы заметили, заключалась в том, что OSPFv1 мог не удалить информацию из таблицы маршрутизации. Информация удаляется в OSPF с помощью так называемых MaxAge LSA (см. раздел 4.7.2). Однако в OSPFv1 MaxAge LSA часто циркулировали между маршрутизаторами уже после того, как выполнили свою функцию. Помимо того, что такое поведение несколько сбивает с толку, оно может помешать публикации новой информации. Хотя мы исправили эту проблему в следующей версии OSPF, проблемы с удалением MaxAge LSA сохранялись во многих реализациях в течение многих лет.

Другая проблема носила более гипотетический характер. Первоначальный протокол маршрутизации по состоянию канала ARPANET имел недостаток, который мог привести к «расплавлению» всей сети, поскольку обновления маршрутизации продолжали циркулировать по сети с огромной скоростью до тех пор, пока сама сеть не должна была быть отключена в качестве корректирующего действия [221]. В основе этой проблемы лежал способ, которым протокол ARPANET определял, обновляется ли LSA. Во всех алгоритмах состояния канала LSA имеют порядковые номера: когда маршрутизатор получает две копии одного и того же LSA, копия с «более высоким» порядковым номером является обновлением другой копии. Что означает слово «выше» зависит от того, как организовано пространство последовательностей. В исходном алгоритме ARPANET пространство порядковых номеров было циклическим, и повреждение данных могло затруднить определение того, какой LSA является обновлением. В OSPFv1 мы внесли исправления, предложенные в [189], чтобы избежать этой проблемы, но эти исправления не были полностью надежными. Чтобы исправить последнюю уязвимость, нам нужно было изменить пространство последовательностей LSA на простое линейное пространство, как описано в разделе 4.2.2.

Внедрение OSPFv1 выявило несколько мест, где OSPF можно оптимизировать. Например, OSPFv1 требовал, что после того, как интерфейс маршрутизатора стал работоспособным, маршрутизатор должен был подождать фиксированный интервал времени, прежде чем устанавливать отношения соседства OSPF через интерфейс. Однако оказалось, что информация, содержащаяся в пакетах OSPF, полученных по интерфейсу, может значительно уменьшить этот интервал. Другой пример: OSPF требует, чтобы вы обменивались информацией о полной базе данных состояний каналов с недавно обнаруженным соседом OSPF. OSPFv1 требовал того, что вам необходимо отправить описание всей вашей базы данных, прежде чем запрашивать получение фрагментов базы данных вашего соседа. Однако оказалось, что для маршрутизаторов OSPF гораздо эффективнее смешивать объявления базы данных и запросы.

Также выяснилось, что не были определены полностью ряд моментов спецификации OSPFv1. Например, OSPFv1 давал подробное описание того, как построить таблицу маршрутизации маршрутизатора OSPF, но не объяснял, как маршрутизатор выполняет поиск в таблице маршрутизации и выбор «наиболее подходящей» записи таблицы маршрутизации для данного IP-адресата. Фактически, до этого момента ни один протокол IP-маршрутизации не имел полностью определенного алгоритма поиска в таблице маршрутизации.

Все эти проблемы заставили нас пересмотреть спецификацию OSPFv1. Исправление пространства последовательностей LSA не могло быть обратно совместимым; любое изменение в пространстве последовательностей LSA привело бы к путанице порядковых номеров LSA между маршрутизаторами, использующими старую и новую версии спецификации, чего мы и пытались избежать в первую очередь. Поэтому мы увеличили номер версии OSPF, создав спецификацию OSPFv2, которая в конечном итоге была опубликована как RFC 1247 в июле 1991 года [176].

Сбой взаимодействия OSPFv1 и OSPFv2 не был проблемой, поскольку OSPFv1 никогда не был развернут. Поскольку нам не пришлось беспокоиться об обратной совместимости, мы воспользовались этой возможностью, чтобы упростить форматы пакетов OSPF. Также стало ясно, что существуют некоторые функции OSPF, такие как способность маршрутизации OSPF учитывать метку ToS IP-пакета, которые не все будут реализовывать. Чтобы сделать такие функции необязательными, мы предоставили маршрутизаторам возможность согласовывать возможности, добавив поле Options в пакеты OSPF и LSA (см. главу 7, Расширения OSPF).

Переход с OSPFv1 на OSPFv2 был последним разом, когда мы могли внести радикальные изменения в OSPF. OSPFv2 вскоре будет развернут в Интернете, и все будущие изменения придется вносить с прицелом на поддержание работоспособности установленной базы маршрутизаторов OSPF. Хотя спецификация OSPF переиздавалась несколько раз с момента публикации RFC 1247, в текущей спецификации номер версии OSPF по-прежнему установлен на 2, и она по-прежнему способна взаимодействовать с реализациями исходного RFC 1247.

Тестирование совместимости

Для создания хорошего протокола важно убедиться в том, что несколько независимых реализаций протокола могут взаимодействовать. Пока не будет продемонстрирована совместимость, нельзя быть уверенным в том, что спецификация протокола ясна и недвусмысленна. Часто тестирование совместимости выявляет дыры в спецификации протокола; неписаные предположения, сделанные разработчиками протоколов, не всегда очевидны разработчикам, когда они впервые читают спецификацию. Тестирование совместимости особенно важно для протоколов маршрутизации, которые представляют собой распределенные алгоритмы, требующие согласованного взаимодействия многих маршрутизаторов (а не просто взаимодействия двух хостов, как, например, с транспортными алгоритмами, такими как TCP). По этой причине совместимость независимых реализаций является одним из требований для развития протоколов маршрутизации в стандартном процессе IETF [98].

Во время первоначальной разработки протокола OSPF, с 1990 по 1994 год, было проведено шесть организованных сессий по функциональной совместимости. Эти сессии на самом деле больше напоминали периодические испытания различных интернет-протоколов. Одна компания вызвалась провести сеанс взаимодействия, а затем разработчики OSPF из других компаний приехали со своими маршрутизаторами на несколько дней тестирования. Первая сессия прошла в компании Proteon, Inc., в ней приняли участие три производителя маршрутизаторов. Затем последовали сессии, организованные SURANet (региональной сетью NSF, с тех пор приобретенной BBN Planet), 3Com, FTP Software и Xyplex. Заключительная сессия, проведенная лабораторией Корпорации открытых систем в Рестоне, штат Вирджиния, собрала 12 поставщиков маршрутизаторов.

Эти тесты были организованы неформально, в коллегиальной атмосфере. Большую часть первого дня обычно тратили на протягивание Ethernet и serial-кабелей. Затем мы договаривались о нескольких топологиях сети и сценариях сбоев, которые можно было бы попробовать. Попутно мы находили ошибки, обычно в реализациях, хотя иногда и в самом протоколе OSPF. Иногда сразу несколько разработчиков проверяли трассировку пакетов, чтобы попытаться изолировать проблему. Обнаружив ошибку, разработчики обычно меняли свой код (некоторые полностью перенесли свою среду разработки на портативные ПК, тогда как другие подключались по telnet к системам разработки своих компаний), перезагружали свои маршрутизаторы и повторяли тесты. На этих сессиях было обычным явлением видеть, как разработчики из нескольких компаний склонялись над плечом конкурента, пытаясь исправить ошибку!

Тестовые топологии обычно были небольшими, поскольку каждый производитель маршрутизаторов мог предоставить только пару маршрутизаторов. Например, одна из сетевых топологий, использованных во время сеанса тестирования в компании 3Com, изображена на рис. 3.3. В этом и других сеансах тестирования использовалось активное подключение к Интернету (на этот раз к BARRNet, региональной сети Bay Area NSF, которая с тех пор была приобретена BBN Planet) для импорта некоторых интернет-маршрутов в среду тестирования.

На сегодняшний день тестирование реализации OSPF больше не запланировано. Тем не менее, по-прежнему существуют места, где поставщики могут использовать свои реализации OSPF для тестирования, например Лаборатория совместимости Университета Нью-Гемпшира [251].

Инструментарий

Чтобы определить, насколько хорошо работает OSPF, и отслеживать проблемы при их возникновении, нам понадобились некоторые инструменты. Чтобы выяснить, строит ли OSPF правильные маршруты, мы использовали стандартные интернет-инструменты, такие как traceroute и ping (см. главу 12 «Отладка проблем маршрутизации»). Но для мониторинга производительности протокола OSPF пришлось создать новые инструменты.

Во-первых, нам нужен был способ видеть пакеты OSPF, отправляемые и получаемые во время тестирования. Сетевые анализаторы, такие как Network General Sniffer, были подключены к нашей тестовой сети для сбора пакетов (см. раздел 12.8). Однако эти анализаторы не умели декодировать пакеты OSPF, а ручное декодирование дампов шестнадцатеричных пакетов было громоздким. Поэтому мы модифицировали программное обеспечение анализаторов, чтобы оно декодировало пакеты OSPF и имело возможность фильтровать пакеты, отличные от OSPF, чтобы упростить анализ оставшихся пакетов OSPF.

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

Контрольная сумма базы данных и другие статистические данные, которые мы сочли полезными во время тестирования, в конечном итоге были добавлены в MIB OSPF (см. раздел 11.2), чтобы эту информацию можно было извлечь через SNMP.

Большая часть испытаний совместимости ограничивалась небольшими сетями. Однако во время тестирования COS в 1994 году Роб Колтун модифицировал свою реализацию OSPF так, чтобы рабочая станция UNIX могла участвовать в тестировании как маршрутизатор OSPF и моделировать дополнительное количество маршрутизаторов OSPF. Эта модифицированная реализация позволила нам протестировать, как другие реализации OSPF ведут себя в относительно больших сетях, увеличив размер области OSPF до 240 маршрутизаторов и импортировав количество внешних маршрутов, равное полной таблице маршрутизации Интернета на тот момент (10 000 записей).

Обнаруженные проблемы

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

Однако в ходе тестирования также было обнаружено немало ошибок в спецификации OSPF. Ниже приведены некоторые показательные примеры.

Наиболее распространенной проблемой была неполная спецификация, обычно в форматах пакетов OSPF и LSA. Например, в первом раунде тестирования возникли разногласия по поводу того, как представлять маршрут по умолчанию в OSPF. Маршруты представлены в OSPF как пары [сеть, маска]. Однако спецификация OSPF определила маршрут по умолчанию как маршрут с сетью, равной 0.0.0.0, без указания связанного значения маски. Во время тестирования одна реализация создала маршрут с сетью, равной 0.0.0.0, и ненулевой маской. Некоторые реализации интерпретировали это как маршрут по умолчанию, другие — нет, поскольку ожидали маску 0.0.0.0.

Тестирование часто приводило к быстро меняющейся среде: маршрутизаторы постоянно перезагружались, интерфейсы включались и отключались, менялись адреса и так далее. Эти быстрые изменения усилили механизмы протокола OSPF. Например, после обнаружения друг друга соседние маршрутизаторы OSPF синхронизируют свои базы данных OSPF с помощью процедуры, называемой Database Exchange (см. раздел 4.7.1). Эта процедура предполагала, что порядковый номер в LSA всегда увеличивается. Но в быстро меняющейся сети мы увидели, что это не обязательно так. Вполне возможно, что во время обмена базами данных LSA может быть удален, а затем повторно создан с начальным (наименьшим) порядковым номером, создавая впечатление, что порядковый номер LSA идет в обратном направлении! Спецификацию Database Exchange пришлось соответствующим образом изменить; Дополнительные сведения об этой проблеме см. в разделе часто задаваемых вопросов под названием «Зачем устанавливать MaxAge LSA в базе данных состояния каналов, если предыдущих экземпляров нет?» в главе 8.

Выбор сетевых конфигураций для тестирования был довольно случайным: на доске рисовали сразу несколько человек. Иногда это приводило к ситуациям, непредвиденным при разработке OSPF. Например, в пятом раунде тестирования была создана конфигурация virtual-link, которая привела к сбою расчета маршрутизации OSPF. В результате расчет маршрутов OSPF при использовании virtual-link был существенно изменен, когда спецификация OSPF была переиздана в марте 1994 года [177].

Демонстрация на INTEROP

В октябре 1991 года мы провели тестирование совместимости другого типа: мы провели демонстрацию совместимости на осенней выставке INTEROP 91. В отличие от предыдущих тестов OSPF, маршрутизаторы OSPF на этот раз использовались в продуктовой среде, включая ShowNet компании INTEROP. ShowNet обеспечивал соединение TCP/IP между стендами на выставке и Интернетом, предоставляя подключение Ethernet и/или Token Ring к каждому стенду. Кольца FDDI соединяли сегменты Ethernet и Token Ring, а маршрутизатор, работающий по протоколу BGP, был подключен через соединение T1 к Интернету(Примечание переводчика: Т1 — аналог европейского Е1, обеспечивал скорость 1.544 Mbps). Схема сети INTEROP 91 ShowNet показана на рисунке 3.4. Все изображенные маршрутизаторы работали под управлением OSPF, а на стендах 11 поставщиков, поставляющих маршрутизаторы, были дополнительные маршрутизаторы с поддержкой OSPF.

Трудно создать яркую демонстрацию протокола маршрутизации. Когда протокол маршрутизации работает, никто особо не замечает, что он вообще есть. У нас была станция HP Openview Network Management Station, модифицированная для отображения контрольных сумм базы данных маршрутизаторов OSPF. Глядя на дисплей, можно было определить, когда поступает новая информация OSPF. Мы также модифицировали сетевой анализатор Excelan LANalyzer, чтобы он отображал уровень трафика протокола OSPF, разделенный по типам пакетов OSPF (см. раздел 4.5).

Демонстрация OSPF на INTEROP 91 была разовым мероприятием. В дальнейшем INTEROP ShowNets использовала OSPF не как демонстрационную версию, а как неотъемлемую часть своей продуктовой среды.

Полевые испытания

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

Но сначала нам пришлось начать использовать его самим. Лучший способ получить превосходный продукт — заставить людей, которые его разрабатывают, использовать его изо дня в день. В 1990 году, когда я работал в Proteon, Inc., у нас была собственная сеть маршрутизаторов, которая использовалась для ведения бизнеса компании. Если сеть выйдет из строя, вы сразу узнаете об этом, поскольку рабочая станция или компьютер на вашем столе практически перестанут функционировать. Эта сеть состояла примерно из 20 маршрутизаторов, работающих по протоколу RIP, соединяющих локальные сети Ethernet и 802.5 Token Ring с помощью собственной высокоскоростной технологии локальных сетей под названием Pronet-80. Однажды вечером 1990 года, после того как реализация Proteon OSPF была хорошо протестирована в лабораторной среде, я начал переводить сеть Proteon с RIP на OSPF. После того как примерно шестой роутер был перенестроен, роутеры начали глючить. Поэтому я убрал OSPF и повторил попытку на следующую ночь, внеся соответствующие изменения в программное обеспечение. Этот сценарий продолжался несколько ночей подряд, пока сеть не заработала бесперебойно. С этого момента сеть стала работать под управлением OSPF. Со временем сеть Proteon выросла до более чем 60 маршрутизаторов и всегда была важным испытательным полигоном для новых версий программного обеспечения OSPF. Со временем в сети Proteon также использовались расширения OSPF, такие как MOSPF и механизмы переполнения базы данных OSPF.

На тот момент мы уже знали, что OSPF можно запускать в действующей сети, но мы не были уверены, что OSPF может управляться кем-то, кроме самихразработчиков программного обеспечения OSPF. Мы начали искать другие сети, где можно было бы попробовать внедрить OSPF. Региональные сети NSF(National Science Foundation Network) казались самыми подходящими кандидатами. Эти сети были самыми крупными и наиболее требовательными из всех существовавших в то время сетей TCP/IP, и именно эти сети в первую очередь послужили основой для разработки протокола OSPF (см. раздел 3.1).

Первой сетью, которую мы попытались преобразовать в OSPF, была региональная сеть SURANet NSF в 1990 году. В то время в SURANet было около 60 маршрутизаторов, все из которых работали с RIP. Мы решили переводить сеть на новый механизм маршрутизации постепенно, переводя по одному маршрутизатору с RIP на OSPF. Для реализации плана было необходимо, чтобы маршрутизаторы работали с обоими протоколами одновременно, преобразуя маршруты RIP в маршруты OSPF и наоборот; это может быть зело опасно, если обращаться с с ними неправильно (см. раздел 11.6). Кроме того, при переводе были предъявлены еще два требования. Во-первых, таблицы маршрутизации в маршрутизаторах должны были выглядеть одинаково независимо от того, использовал ли маршрутизатор OSPF, RIP или оба протокола одновременно (см. раздел 11.6.2). Во-вторых, во время перенастройки маршрутизаторов нам пришлось управлять всеми маршрутизаторами через TELNET и SNMP по тем же самым каналам связи, по которым шёл основной трафик. Из-за этих ограничений преобразование SURANet было прекращено после нескольких попыток. Такой переход сегодня был бы довольно простым делом, но тогда было слишком сложно отслеживать работу с помощью внутриполосного управления, а механизмы одновременного запуска OSPF и RIP не были должным образом спроектированы, что приводило к переизбытку трафика протоколов маршрутизации.

Первое развертывание OSPF в Интернете произошло в апреле 1990 года. Майло Медин и Джефф Бурган преобразовали NASA Science Internet network с RIP на OSPF, а днем позже Винс Фуллер начал использовать OSPF в региональной сети BARRNet NSF [170]. В обоих случаях все маршрутизаторы были преобразованы одновременно. В NASA Science Internet network это было намного проще, поскольку всеми маршрутизаторами можно было управлять внеполосно через модемные соединения к консолям маршрутизаторов.

Запросы функционала

Практическое применение протокола часто обнаруживает места, где его можно улучшить. Процесс разработки стандартов Интернета признает важность внедрения, уделяя особое внимание реализации протокола и опыту его эксплуатации по мере продвижения протокола вверх по лестнице стандартов Интернета [98]. Внедрение OSPF привело к ряду модификаций протокола, направленных на повышение удобства его использования в Интернете.

Люди, которые управляют сетями, очень озабочены оптимизацией путей, по которым данные проходят по их сетям. И им не нравятся петли маршрутизации. Как только первые инсталляции OSPF были развернуты в Интернете, было обнаружено, что OSPF может способствовать появлению петель на границе между доменом маршрутизации OSPF и другой автономной системой. В то время эти границы назывались DMZ, заимствовав военную терминологию, и обычно реализовывались как общие сети Ethernet, где маршрутизаторы двух или более AS подключались к одной сети и обменивались информацией о маршрутизации через протокол EGP. (Сегодня границы называются Network Access Points или NAP и обычно реализуются в виде колец FDDI, сетей ATM и так далее, а вместо EGP используется BGP, но в остальном применяются те же идеи.) Пример петли маршрутизации показан на рисунке 3.5.

Домен маршрутизации OSPF в AS 1 разместил два маршрутизатора в DMZ Ethernet, но только один из этих маршрутизаторов, маршрутизатор A, обменивается информацией о маршрутизации с маршрутизатором из AS 2, маршрутизатором C. Маршрутизатор A затем импортирует маршруты в домен маршрутизации OSPF. Однако при импорте этих маршрутов маршрутизатор A говорил: «Отправляйте мне трафик для сетей в AS 2». Это означало, что маршрутизатор B сначала будет отправлять такой трафик маршрутизатору A, а не напрямую маршрутизатору C. Чтобы избавиться от этой петли, мы ввели в OSPF концепцию адреса пересылки(forwarding address). Эта концепция позволяет маршрутизатору A сказать: «Отправляйте трафик, предназначенный для сетей AS 2, непосредственно на маршрутизатор C». Протокол маршрутизации EGP также имел концепцию адреса пересылки, называемую third-party EGP, а позже адреса пересылки были добавлены к протоколам маршрутизации BGP и RIP-II.

Люди, развернувшие OSPF, также хотели запустить OSPF на как можно большем количестве своих маршрутизаторов, чтобы свести к минимуму количество протоколов маршрутизации, с которыми им приходилось иметь дело. Однако некоторые из их маршрутизаторов имели лишь минимальные ресурсы, особенно когда дело касалось доступной памяти. Поэтому были изобретены stub area OSPF — зоны на границе автономной системы, маршрутизаторы которых будут полагаться в основном на маршрут по умолчанию (см. раздел 7.2). В результате маршрутизаторы в stub area будут иметь только небольшие таблицы маршрутизации, но, при этом, все равно смогут участвовать в маршрутизации OSPF

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

Обнаруженные проблемы

Продуктовые среды также часто могут быть более требовательными, чем тесты на совместимость. Самый очевидный пример — размер сети; Собирать очень большие испытательные стенды непрактично, и даже если бы вы могли это сделать, вы никогда не смогли бы полностью воспроизвести модели трафика, которые вы видите в реальной сети. Таким образом, в продуктовых сетях часто обнаруживаются проблемы протоколов, которые раньше не наблюдались. Далее следует несколько примеров, взятых из опыта использования OSPF в реальных сетях.

Люди пытались использовать OSPF на очень медленных каналах. Запросы на удаление информации о маршрутизации OSPF, называемые MaxAge LSA, могут стоять в очереди на этих медленных каналах по нескольку секунд в периоды перегрузки. Это, в свою очередь, может препятствовать появлению новой информации в OSPF, еще больше увеличивая перегрузку. Чтобы решить эту проблему, механизм лавинообразной рассылки OSPF был изменен. Неудивительно, что это изменение лавинообразной рассылки также потребовалось для работы OSPF по коммутируемым каналам (так называемые Demand Circuit extensions OSPF, как описано в разделе 7.3).

Когда OSPF был первоначально разработан, всего несколько различных общих технологий связи использовали IP: Ethernet и последовательные линии «точка-точка», использующие собственную инкапсуляцию каналов передачи данных. PPP и FDDI только развивались. Позже стали использоваться технологии каналов передачи данных, которые имели довольно нечеткий IP MTU (maximum transmission unit) — два примера — 802.5 Token Ring и Frame Relay. При передаче данных по этим каналам возможна ситуация, что два соседних маршрутизатора не смогут определить самый большой пакет, который может быть отправлен по каналу, что вызовет проблемы при пересылке. Поскольку один маршрутизатор отправляет пакет, который слишком велик для приема другим, доставка больших пакетов по определенным путям становится невозможной. (Казалось бы, что фрагментация IP поможет справиться с этой ситуацией, но хотя фрагментация хорошо обрабатывает каналы с разными MTU, она предполагает, что все маршрутизаторы, подключенные к данному каналу, согласовали общее MTU в этом канале.) В результате OSPF был модифицирован для обнаружения и неиспользования каналов с несоответствием MTU.

Становление стандарта

Начиная с 1992 года IETF начал процесс выбора общего IGP для Интернета. Де-факто, ни IGP, ни RIP уже больше не считались адекватными. Реально было два кандидата на общий IGP: OSPF и Integrated IS-IS [30].

И OSPF, и протокол маршрутизации OSI IS-IS являются протоколами состояния канала. Между ними, конечно, есть технические различия. Integrated IS-IS был усовершенствованием IS-IS, позволяющим рассчитывать маршруты IP и OSI с помощью единого протокола маршрутизации. Разработчики OSPF считали, что их первоначальные причины не выбирать IS-IS в качестве базы для разработки (см. раздел 3.2) по-прежнему актуальны, что делало, по из мнению, OSPF лучшим выбором. У разработчиков IS-IS были свои технические причины отдать предпочтение IS-IS. Эти технические вопросы обсуждались в списках рассылки и на других технических форумах ([156] и [191]).

Однако вместо технических деталей в дебатах доминировали два других вопроса. Во-первых, дискуссии между сторонниками OSPF и Integrated IS-IS было продолжением противоречий между наборами протоколов TCP/IP и OSI, подобно дебатам о SNMP и CMIP в предыдущие годы и дебатам по поводу различных вариантов IPv6 в последующие годы. Многие сторонники OSPF считали, что важно иметь протокол интернет-маршрутизации, изменения которого будут контролироваться IETF. С другой стороны, некоторые сторонники Integrated IS-IS рассматривали выбор общего IGP как возможность значительного развертывания набора протоколов OSI в Интернете.

Другая проблема заключалась в самой интегрированной маршрутизации. Если вы хотите одновременно поддерживать два отдельных набора протоколов, таких как TCP/IP и OSI, следует ли вам делать это с помощью одного интегрированного экземпляра протокола маршрутизации или каждый набор протоколов должен иметь свой собственный протокол маршрутизации? Сторонники интегрированной маршрутизации утверждали, что она более эффективна и проще для разработчиков программного обеспечения. Противники интегрированной маршрутизации, называемые сторонниками подхода «Ships-in-the-Night», или SIN, утверждали, что только отдельные протоколы маршрутизации обеспечивают необходимую гибкость для развертывания нескольких протоколов. Споры об интегрированной маршрутизации, как и дебаты Беллмана-Форда против маршрутизации по состоянию канала, продолжаются и сегодня, поскольку многие люди рассматривают возможность внедрения IPv6 в существующий Интернет.

IETF, чей девиз — грубый консенсус и работающий код, не создан для принятия быстрых решений при столкновении с множеством конкурирующих протоколов. В конце концов IETF выбрала OSPF в качестве общего IGP [85], [109]. Однако на тот момент выбор оказался пост-фактум, так как рынок уже принял решение и все основные производители оборудования предпочли реализовать OSPF в прошивках.

Одновременно с выбором общего протокола IGP для Интернета также определялись критерии стандартизации протоколов маршрутизации. Протоколы маршрутизации обычно предполагают взаимодействие многих маршрутизаторов, а не просто пары хостов, как для транспортного протокола, такого как TCP. По этой причине требовались более строгие критерии, включающие тестирование, развертывание и множество независимо разработанных реализаций [98]. Каждый протокол маршрутизации Интернета должен документировать, насколько он соответствует этим критериям; для OSPF эти документы можно найти в [170], [173] и [175].

Развитие протокола в Интернет

Базовая разработка OSPF была завершена в 1989 и 1990 годах. Однако Интернет постоянно меняется, и интернет-протоколы должны адаптироваться к этим изменениям или устареть. В этом разделе мы рассмотрим, как изменения в Интернете привели к изменениям в OSPF.

CIDR

В 1993 году стало очевидно, что рост Интернета вскоре приведет к тому, что маршрутизаторам, составляющим ядро Интернета, не хватит места в таблице маршрутизации. Чтобы обеспечить бесперебойную работу Интернета, была отменена предыдущая процедура разделения Интернет-адреса на части фиксированной длины (так называемые адреса классов A, B и C и их подсети фиксированной длины; см. раздел 1.2.2). Вместо этого маршрутизация в Интернете будет основана на префиксах адресов. Каждый протокол маршрутизации должен будет объявлять размер префиксов, сообщая количество значащих битов или, альтернативно, маску для каждого префикса. Этот новый метод адресации получил название бесклассовой междоменной маршрутизации (CIDR) [81].

Старые протоколы маршрутизации Интернета, форматы пакетов которых основывались на адресации классов A, B и C, были либо отвергнуты, либо обновлены. BGP и более ранние версии BGP были быстро заменены BGP-4 [208]. RIP и IGRP были обновлены и стали называться RIP-II и EIGRP соответственно.

OSPF всегда объявлял каждый префикс вместе с его маской и не зависел от адресации классов A, B и C. Однако по мере внедрения CIDR стала очевидна одна проблема. OSPF импортировал внешние маршруты (например, маршруты, полученные из BGP) в домен маршрутизации OSPF в AS-external-LSA. При импорте одним маршрутизатором несколько AS-external-LSA различались по идентификатору состояния канала(Link State ID); Предполагалось, что идентификатор состояния канала будет установлен в префикс адреса импортированного маршрута. Однако иногда маршрутизатору может потребоваться импортировать один и тот же префикс с двумя разными длинами — например, 192.9.0.0/16 и 192.9.0.0/24 — и это было невозможно, поскольку оба использовали бы идентификатор состояния канала 192.9.0.0. Поскольку казалось, что такие ситуации могут стать обычным явлением (например, когда организация меняет интернет-провайдера, сохраняя при этом свои IP-адреса), правила установки идентификаторов состояния канала в AS-external-LSA пришлось изменить.

Сети Frame Relay

OSPF был разработан для работы по различным типам каналов, включая каналы «точка-точка»; широковещательные среды, такие как Ethernet; и нешироковещательные, поддерживающие множество маршрутизаторов (см. главу 5, Типы сетей OSPF). Эти нешироковещательные подсети назывались non-broadcast multiaccess networks (NBMA). При работе через NBMA OSPF предполагает, что маршрутизатор, подключенный к NBMA, может взаимодействовать с другим маршрутизатором напрямую. Это предположение было справедливым для сетей X.25 PDNS с использованием SVC(Switched Virtual Circuits), исходной модели OSPF NBMA.

Позже сети Frame Relay, реализованные на базе PVC(Permanent Virtual Circuits), стали обычным явлением в Интернете. Применение NBMA в сетях Frame Relay было лишь частично успешным. Часто PVC не были настроены как полносвязная сеть, а даже если и были, отдельные PVC подвергались сбоям; любое условие нарушало предположение NBMA о прямой связи. Рекомендации по настройке были созданы для решения этих проблем путем указания одной сети Frame Relay как нескольких NBMA [65]. К сожалению, такая конфигурация часто сбивает с толку и чревата ошибками.

Чтобы решить эти проблемы при использовании OSPF через Frame Relay, в конечном итоге была разработана сеть «точка-многоточка»(Point-to-MultiPoint) как альтернатива поддержке NBMA в OSPF (см. раздел 5.4). Хотя сети «точка-многоточка» не так эффективны, как поддержка NBMA в OSPF, они могут автоматически настраиваться и устойчивы к сбоям PVC.

Multicast

В 1980-х годах началась работа по расширению возможностей multicast (возможности отправлять один пакет и доставлять его копию множеству получателей) из локальной сети в Интернет. Основополагающую работу по этому вопросу провел Стив Диринг, когда он учился в Стэнфорде [59], он разработал ориентированную на получателя модель многоадресной рассылки в Интернете и протокол членства в группах Интернета (IGMP), который сообщал о членстве в группе многоадресной рассылки между хостами и маршрутизаторами [56].

Протоколы многоадресной маршрутизации вычисляют путь многоадресной дейтаграммы от отправителя к множеству получателей. Первым протоколом многоадресной маршрутизации в Интернете был Distance Vector Multicast Routing Protocol (DVMRP) [202]. DVMRP реализован для рабочих станций UNIX в программе mrouted.

В 1992 году была создана Multicast Backbone (MBONE). MBONE предоставляет услуги многоадресной маршрутизации в Интернет и является наложенной сетью — это, в основном, рабочие станции UNIX, работающие под управлением DVMRP, соединенные между собой через туннели. MBONE транслирует аудио и видео с собраний IETF заинтересованным участникам по всему миру и является питательной средой для приложений многоадресной рассылки, таких как интерактивные доски [140]; инструменты телеконференций [139], [228]; видеоконференцсвязь [80], [246]; и крупномасштабное распространение изображений [55].

Как протокол дистанционно-векторный протокол, DVMRP страдает от тех же проблем сходимости, что и RIP (см. раздел 3.1). В надежде получить более стабильный и эффективный протокол многоадресной маршрутизации и развернуть многоадресную маршрутизацию непосредственно на маршрутизаторах Интернета в 1992 году были разработаны расширения многоадресной рассылки для OSPF (MOSPF) (см. главу 10, MOSPF).

Повышенная безопасность

Первым инцидентом в сфере интернет-безопасности, получившим широкое внимание, стал интернет-червь в 1988 году. В ноябре того же года Роберт Моррис, аспирант Корнелльского университета, написал компьютерный вирус, который реплицировался через Интернет, заражая тысячи рабочих станций UNIX, используя недостатки безопасности в операционной системе UNIX [87], [211].

Межсетевые экраны вскоре стали большим бизнесом, как один из способов защиты интернет-сайтов от незаконного проникновения. Люди также пришли к убеждению, что инфраструктуру Интернета, включая протоколы маршрутизации, необходимо защищать. Все новые спецификации интернет-протоколов теперь должны иметь раздел, посвященный вопросам безопасности, когда протокол публикуется как RFC [193]. Так же были сделаны предложения по обеспечению безопасности существующих протоколов Интернета [111].

Изначально, протокол OSPF разрабатывался с учетом требований безопасности. В пакеты протокола OSPF, были включены дополнительные поля для аутентификации. Идея состояла в том, чтобы предоставить маршрутизаторам, обменивающимся маршрутной информацией, ключ, а затем проверять пакеты OSPF на наличие этого ключа, для предотвращения изменений пакета. Однако для OSPF не было реализовано никакого реального механизма безопасности, механизм ключа был аналогичен паролям TELNET до появления Kerberos [238] и одноразовых паролей [90], и в результате его может взломать любой, кто наблюдает за обменом пакетами в сети. Для обеспечения аутентификации в OSPF, в конечном итоге, были разработаны криптографические алгоритмы хэширования, как описано в разделе 11.7.

IPv6

Помимо опасности, связанной с ростом таблицы маршрутизации для маршрутизаторов Интернета, в Интернете когда-нибудь закончатся адреса (когда именно это произойдет, остается лишь догадкой; см. [1]). Чтобы подготовиться к этому сценарию, в 1995 году была начата разработка следующего поколения Интернет-протокола, IPv6. IPv6 представляет собой развитие архитектуры IPv4; архитектура маршрутизации остается прежней, но размер адреса увеличивается с 32 до 128 бит ([49], [61], [99], [181]).

Чтобы иметь возможность предоставлять услуги маршрутизации для IPv6, протокол OSPF также был обновлен. Поскольку обратная совместимость не была проблемой, форматы пакетов и LSA были переделаны в реализации OSPF для IPv6 [46]. Вся семантика адресации была удалена из заголовков пакетов и LSA, что позволило использовать OSPF_IPv6 любым стеком протоколов. Все основные механизмы OSPF, такие как лавинообразная рассылка, организация зон и расчеты маршрутизации, остались прежними, поэтому большую часть программного обеспечения для OSPFv2 можно было использовать повторно.

Дальнейшее чтение

На протяжении многих лет в виде RFC публиковалась череда спецификаций протокола OSPF, каждая из которых вытесняла предыдущую ([174], [176], [177] и [178]). Каждая спецификация имеет приложение со списком изменений по сравнению с предыдущей, позволяющее отслеживать изменения в протоколе OSPF. Возможности, свойства и характеристики производительности OSPF описаны в [173]. Результаты тестирования совместимости OSPF и развертывания OSPF описаны в [168] и [175].

От переводчика

Ну, до сего момента дойдет только настырный читатель, или тот, кому действительно было интересно, буду рад, если это действительно так. Иногда бывает очень полезно оглянуться назад и посмотреть, а как оно там было? На плечах каких титанов мы стоим? Почему всё пошло именно так, а не иначе?

Я сам уже достаточно старый, чтоб своими руками трогать 1мб/с канал по E1, принимая его на PCI-карту Cronyx TAU-PCI, по протоколу HDLC с "маршрутизатором" под управлением RedHat 7.2(Enigma), поэтому мне приятно вспоминать те лихие времена.

А тут еще дети мне говорят, чтоб я развивал "личный бренд". Так что, подписывайтесь на канал, возможно, будет интересно.