Алгоритмы маршрутизации могут быть классифицированы по типам. Например, алгоритмы могут быть:

1. Статическими или динамическими

2. Одномаршрутными или многомаршрутными

3. Одноуровневыми или иерархическими

4. С интеллектом в главной вычислительной машине или в маршрутизаторе

5. Внутридоменными и междоменными

6. Алгоритмами состояния канала или вектора расстояний

Статические или динамические алгоритмы

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

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

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

Одномаршрутные или многомаршрутные алгоритмы

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

Одноуровневые или иерархические алгоритмы

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

Системы маршрутизации часто устанавливают логические группы узлов, называемых доменами, или автономными системами (AS), или областями. В иерархических системах одни маршрутизаторы какого-либо домена могут сообщаться с маршрутизаторами других доменов, в то время как другие маршрутизаторы этого домена могут поддерживать связь с маршрутизаторы только в пределах своего домена. В очень крупных сетях могут существовать дополнительные иерархические уровни. Маршрутизаторы наивысшего иерархического уровня образуют базу маршрутизации.

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

Алгоритмы с игнтеллектом в главной вычислительной машине или в маршрутизаторе

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

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

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

Внутридоменные или междоменные алгоритмы

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

Алгоритмы состояния канала или вектора расстояния

Алгоритмы состояния канала (известные также как алгоритмы "первоочередности наикратчайшего маршрута") направляют потоки маршрутной информации во все узлы об'единенной сети. Однако каждый маршрутизатор посылает только ту часть маршрутной таблицы, которая описывает состояние его собственных каналов. Алгоритмы вектора расстояния ( известные также как алгоритмы Бэлмана-Форда) требуют от каждогo маршрутизатора посылки всей или части своей маршрутной таблицы, но только своим соседям. Алгоритмы состояния каналов фактически направляют небольшие корректировки по всем направлениям, в то время как алгоритмы вектора расстояний отсылают более крупные корректировки только в соседние маршрутизаторы.

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

Решение о пересылке данных по определенному маршруту принимается на основании сведений о том, какие адреса сетей (или идентификаторы (коды) сетей) доступны в объединенной сети. Эти сведения содержатся в базе данных, называемой таблицей маршрутизации. Таблица маршрутизации представляет собой набор записей, называемых маршрутами, которые содержат информацию о расположении сетей с данными идентификаторами в объединенной сети. Таблицы маршрутизации могут существовать не только на маршрутизаторах. Узлы, не являющиеся маршрутизаторами, могут также вести свои таблицы маршрутизации для определения оптимальных маршрутов.

Типы записей в таблице маршрутизации

Каждая запись в таблице маршрутизации считается маршрутом и может иметь один из следующих типов.

1) Маршрут к сети

Маршрут к сети ведет к сети, входящей в объединенную сеть и имеющей указанный код (идентификатор).

2) Маршрут к узлу

Маршрут к узлу ведет к конкретному узлу в объединенной сети, обладающему указанным адресом (кодом сети и кодом узла). Маршруты к узлу обычно используются для создания пользовательских маршрутов к отдельным узлам с целью оптимизации или контроля сетевого трафика.

3) Маршрут по умолчанию

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

Структура таблицы маршрутизации

Каждая запись таблицы маршрутизации состоит из следующих информационных полей.

1) Код сети

Код сети (или адрес узла для маршрута к узлу). На IP-маршрутизаторах существует дополнительное поле маски подсети, позволяющее выделить код IP-сети из IP-адреса назначения.

2) Адрес пересылки

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

3) Интерфейс

Сетевой интерфейс, используемый при перенаправлении пакетов, предназначенных для сети с данным кодом. Он может задаваться номером порта или другим логическим идентификатором.

4) Метрика

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

Примечание

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

Маршрутные таблицы содержат информацию, которую используют программы коммутации для выбора наилучшего маршрута. Чем характеризуется построение маршрутных таблиц? Какова особенность природы информации, которую они содержат? В данном разделе, посвященном показателям алгоритмов, сделана попытка ответить на вопрос о том, каким образом алгоритм определяет предпочтительность одного маршрута по сравнению с другими.

В алгоритмах маршрутизации используется много различных показателей. Сложные алгоритмы маршрутизации при выборе маршрута могут базироваться на множестве показателей, комбинируя их таким образом, что в результате получается один отдельный (гибридный) показатель. Ниже перечислены показатели, которые используются в алгоритмах маршрутизации:

1. Длина маршрута

2. Надежность

3. Задержка

4. Ширина полосы пропускания

5. Нагрузка

6. Стоимость связи

Длина маршрута

Длина маршрута является наиболее общим показателем маршрутизации. Некоторые протоколы маршрутизации позволяют администраторам сети назначать произвольные цены на каждый канал сети. В этом случае длиной тракта является сумма расходов, связанных с каждым каналом, который был траверсирован. Другие протоколы маршрутизации определяют "количество пересылок", т.е. показатель, характеризующий число проходов, которые пакет должен совершить на пути от источника до пункта назначения через изделия об'единения сетей (такие как маршрутизаторы).

Надежность

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

Задержка

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

Полоса пропускания

Полоса пропускания относится к имеющейся мощности трафика какого-либо канала. При прочих равных показателях, канал Ethernet 10 Mbps предпочтителен любой арендованной линии с полосой пропускания 64 Кбайт/сек. Хотя полоса пропускания является оценкой максимально достижимой пропускной способности канала, маршруты, проходящие через каналы с большей полосой пропускания, не обязательно будут лучше маршрутов, проходящих через менее быстродействующие каналы.

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

В этом разделе собраны сведения по следующим вопросам.

а) Среда со статической маршрутизацией

б) Вопросы проектирования среды со статической маршрутизацией

в) Безопасность статической маршрутизации

г) Развертывание статической маршрутизации

Среда со статической маршрутизацией

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

а) Под термином «небольшая объединенная сеть» понимается сеть, содержащая от 2 до 10 сетей.

б) Термин «сеть с единственными путями» означает, что передача пакетов в) между любыми двумя конечными точками объединенной сети возможна только по одному маршруту.

г) Термином «статическая сеть» называются сети, топология которых со временем не меняется.

Среды со статической маршрутизацией могут использоваться в следующих случаях:

1) малый бизнес;

2) небольшая офисная объединенная IP-сеть;

3) единственная сеть офиса подразделения.

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

Статическая маршрутизация имеет следующие недостатки.

1) Отсутствие отказоустойчивости Если маршрутизатор или канал связи перестают функционировать, статические маршрутизаторы не обнаруживают сбой и не информируют о нем другие маршрутизаторы. Эта проблема существенна, главным образом, для больших объединенных сетей организаций; небольшие офисные сети (с двумя маршрутизаторами и тремя локальными сетями) испытывают такие трудности недостаточно часто для того, чтобы рассматривать вопрос о развертывании топологии с множественными путями и протоколом маршрутизации.

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

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

Конфигурация периферийного маршрутизатора

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

Маршруты по умолчанию и циклические маршруты

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

Среды с использованием вызова по требованию

Статическую маршрутизацию при использовании вызова по требованию можно реализовать одним из двух способов.

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

2) Автостатические маршруты Автостатические маршруты — это статические маршруты, которые автоматически добавляются в таблицу маршрутизации маршрутизатора после запроса маршрутов с помощью протокола RIP для IP при подключении по требованию. Преимущество автостатических маршрутов заключается в том, что для недостижимых узлов маршрутизатор не подключается к главному офису. Недостаток автостатических маршрутов состоит в необходимости их периодического обновления в соответствии с достижимыми сетями в главном офисе. Если в главном офисе добавлена новая сеть, а в офисе подразделения не было выполнено автостатическое обновление, то все узлы в этой новой сети будут недостижимы из офиса подразделения.

Безопасность статической маршрутизации

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

1) Реализовать физическую защиту, чтобы пользователи не имели физического доступа к маршрутизаторам.

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

Развертывание статической маршрутизации

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

1. Создайте схему топологии объединенной IP-сети, на которой должны быть показаны отдельные сети и места расположения маршрутизаторов и узлов (компьютеров, использующих протокол TCP/IP и не являющихся маршрутизаторами).

2. Каждой IP-сети (системе кабелей, связанной с другими такими системами с помощью одного или нескольких маршрутизаторов) присвойте уникальный код (идентификатор) IP-сети (также называемый адресом IP- сети).

3. Назначьте IP-адреса всем интерфейсам маршрутизаторов. Общепринятой практикой является назначение интерфейсам маршрутизаторов первых IP-адресов из выделенного данной сети диапазона адресов. Например, если IP-сеть имеет код 192.168.100.0 и маску подсети 255.255.255.0, то интерфейсу маршрутизатора назначается IP-адрес 192.168.100.1.

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

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

6. На каждый из маршрутизаторов, не являющийся периферийным, добавьте вычисленные на шаге 5 статические маршруты. Статические маршруты можно добавить в окне «Маршрутизация и удаленный доступ» или с помощью команды route. Если используется команда route, укажите параметр -p, чтобы сделать статические маршруты постоянными.

7. После завершения настройки проверьте связь между узлами по всем маршрутам с помощью команд ping и tracert. Дополнительные сведения о командах ping и tracert см. в разделах Использование команды ping и Использование команды tracert.

Прежде чем вникать в подробности и особенности динамической маршрутизации обратим внимание на двухуровневую модель, в рамках которой рассматривается все множество машин Internet. В рамках этой модели весь Internet рассматривают как множество автономных систем (autonomous system - AS). Автономная система - это множество компьютеров, которые образуют довольно плотное сообщество, где существует множество маршрутов между двумя компьютерами, принадлежащими этому сообществу. В рамках этого сообщества можно говорить об оптимизации маршрутов с целью достижения максимальной скорости передачи информации. В противоположность этому плотному конгломерату, автономные системы связаны между собой не так тесно как компьютеры внутри автономной системы. При этом и выбор маршрута из одной автономной системы может основываться не на скорости обмена информацией, а надежности, безотказности и т.п.

Схема взаимодействия автономных систем

Сама идеология автономных систем возникла в тот период, когда ARPANET представляла иерархическую систему. В то время было ядро системы, к которому подключались внешние автономные системы. Информация из одной автономной системы в другую могла попасть только через маршрутизаторы ядра. Такая структура до сих пор сохраняется в MILNET.

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

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

Внешние протоколы служат для обмена информацией о маршрутах между автономными системами.

Внутренние протоколы служат для обмена информацией о маршрутах внутри автономной системы.

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

К внешним протоколам относятся Exterior Gateway Protocol (EGP) и< Protocol Gateway> .

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

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

К внутренним протоколам относятся протоколы Routing Information Protocol (RIP), HELLO, Intermediate System to Intermediate System (ISIS), Shortest Path First (SPF) и Open Shortest Path First (OSPF).

Протокол RIP (Routing Information Protocol) предназначен для автоматического обновления таблицы маршрутов. При этом используется информация о состоянии сети, которая рассылается маршрутизаторами (routers). В соответствии с протоколом RIP любая машина может быть маршрутизатором. При этом, все маршрутизаторы делятся на активные и пассивные. Активные маршрутизаторы сообщают о маршрутах, которые они поддерживают в сети. Пассивные маршрутизаторы читают эти широковещательные сообщения и исправляют свои таблицы маршрутов, но сами при этом информации в сеть не предоставляют. Обычно в качестве активных маршрутизаторов выступают шлюзы, а в качестве пассивных - обычные машины (hosts).

В основу алгоритма маршрутизации по протоколу RIP положена простая идея: чем больше шлюзов надо пройти пакету, тем больше времени требуется для прохождения маршрута. При обмене сообщениями маршрутизаторы сообщают в сеть IP-номер сети и число "прыжков" (hops), которое надо совершить, пользуясь данным маршрутом. Надо сразу заметить, что такой алгоритм справедлив только для сетей, которые имеют одинаковую скорость передачи по любому сегменту сети. Часто в реальной жизни оказывается, что гораздо выгоднее воспользоваться оптоволокном с 3-мя шлюзами, чем одним медленным коммутируемым телефонным каналом.

Другая идея, которая призвана решить проблемы RIP, - это учет не числа hop'ов, а учет времени отклика. На этом принципе построен, например, протокол OSPF. Кроме этого OSPF реализует еще и идею лавинной маршрутизации. В RIP каждый маршрутизатор обменивается информацией только с соседями. В результате, информации о потере маршрута в сети, отстоящей на несколько hop'ов от локальной сети, будет получена с опозданием. Лавинная маршрутизация позволяет решить эту проблему за счет оповещения всех известных шлюзов об изменениях локального участка сети.

К сожалению, многовариантную маршрутизацию поддерживает не очень много систем. Различные клоны Unix и NT, главным образом ориентированы на протокол RIP. Достаточно посмотреть на программное обеспечение динамической маршрутизации, чтобы убедится в этом. Программа routed поддерживает только RIP, программа gated поддерживает RIP, HELLO, OSPF, EGP и BGP, в Windows NT поддерживается только RIP.

Протокол OSPF (Open Shortest Pass First, RFC-1245-48, RFC-1583-1587, алгоритмы предложены Дикстрой) является альтернативой RIP в качестве внутреннего протокола маршрутизации. OSPF представляет собой протокол состояния маршрута (в качестве метрики используется - коэффициент качества обслуживания). Каждый маршрутизатор обладает полной информацией о состоянии всех интерфейсов всех маршрутизаторов (переключателей) автономной системы. Протокол OSPF реализован в демоне маршрутизации gated, который поддерживает также RIP и внешний протокол маршрутизации BGP.

Автономная система может быть разделена на несколько областей, куда могут входить как отдельные ЭВМ, так и целые сети. В этом случае внутренние маршрутизаторы области могут и не иметь информации о топологии остальной части AS. Сеть обычно имеет выделенный (designated) маршрутизатор, который является источником маршрутной информации для остальных маршрутизаторов AS. Каждый маршрутизатор самостоятельно решает задачу оптимизации маршрутов. Если к месту назначения ведут два или более эквивалентных маршрута, информационный поток будет поделен между ними поровну. Переходные процессы в OSPF завершаются быстрее, чем в RIP. В процессе выбора оптимального маршрута анализируется ориентированный граф сети. Ниже описан алгоритм Дикстры по выбору оптимального пути. На иллюстративном рисунке 4.7 приведена схема узлов (A-J) со значениями метрики для каждого из отрезков пути. Анализ графа начинается с узла A (Старт). Пути с наименьшим суммарным значением метрики считаются наилучшими.

Именно они оказываются выбранными в результате рассмотрения графа (“кратчайшие пути“).

Ниже дается формальное описание алгоритма. Сначала вводим некоторые определения.

Пусть D(v) равно сумме весов связей для данного пути.

Пусть C(i,j) равно весу связи между узлами с номерами i и j.

Далее следует последовательность шагов, реализующих алгоритм.

1. Устанавливаем множество узлов N = {1}.

2. Для каждого узла v не из множества N устанавливаем D(v)= c(1,v).

3. Для каждого шага находим узел w не из множества N, для которого D(w) минимально, и добавляем узел w в множество N.

4. Актуализируем D(v) для всех узлов не из множества N
D(v)=min{D(v), D(v)+c(w,v)}.

5. Повторяем шаги 2-4, пока все узлы не окажутся в множестве N.

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

Иллюстрация работы алгоритма Дикстры

Реализация алгоритма

Множество Метрика связи узла A с узлами
Шаг N ........................B C D E F G H I J
0 {A}......................... 3 - 9 - - - - - -
1 {A,B} ....................(3) 4 9 7 - 10 - - -
2 {A,B,C} ..................3 (4) 6 6 10 10 8 - 14
3 {A,BC,D} ................3 4 (6) 6 10 10 8 9 14
4 {A,B,C,D,E}............ 3 4 6 (6) 10 10 8 9 14
5 {A,B,C,D,E,H} .........3 4 6 6 10 10 (8) 9 14
6 {A,B,C,D,E,H,I} .......3 4 6 6 10 10 8 (9) 14
7 {A,B,C,D,E,H,I,F} .....3 4 6 6 (10) 10 8 9 14
8 {A,B,C,D,E,H,I,F,G} ..3 4 6 6 10 (10) 8 9 14
9 {A,B,C,D,E,H,I,F,G,J} 3 4 6 6 10 10 8 9 (14)

Таблица может иметь совершенно иное содержимое для какого-то другого вида сервиса, выбранные пути при этом могут иметь другую топологию. Качество сервиса (QOS) может характеризоваться следующими параметрами:

1) пропускной способностью канала;

2) задержкой (время распространения пакета);

3) числом дейтограмм, стоящих в очереди для передачи;

4) загрузкой канала;

5) требованиями безопасности;

6) типом трафика;

7) числом шагов до цели;

8) возможностями промежуточных связей (например, многовариантность достижения адресата).

Определяющими являются три характеристики: задержка, пропускная способность и надежность. Для транспортных целей OSPF использует IP непосредственно, т.е. не привлекает протоколы UDP или TCP. OSPF имеет свой код (89) в протокольном поле IP-заголовка. Код TOS (Type Of Service) в IP-пакетах, содержащих OSPF-сообщения, равен нулю, значение TOS здесь задается в самих пакетах OSPF. Маршрутизация в этом протоколе определяется IP-адресом и типом сервиса. Так как протокол не требует инкапсуляции пакетов, сильно облегчается управление сетями с большим количеством бриджей и сложной топологией (исключается циркуляция пакетов, сокращается транзитный трафик). Автономная система может быть поделена на отдельные области, каждая из которых становится объектом маршрутизации, а внутренняя структура снаружи не видна. Этот прием позволяет значительно сократить необходимый объем маршрутной базы данных. В OSPF используется термин опорной сети (backbone) для коммуникаций между выделенными областями. Протокол работает лишь в пределах автономной системы. В пределах выделенной области может работать свой протокол маршрутизации.

При передаче OSPF-пакетов фрагментация не желательна, но не запрещается. Для передачи статусной информации OSPF использует широковещательные сообщения HELLO. Для повышения безопасности предусмотрена авторизация процедур. OSPF-протокол требует резервирования двух мультикастинг-адресов:

224.0.0.5 предназначен для обращения ко всем маршрутизаторам, поддерживающим этот протокол.

224.0.0.6 служит для обращения к специально выделенному маршрутизатору.

Любое сообщение OSPF начинается с 24-октетного заголовка рисунок 4.9

Поле версия определяет версию протокола (= 2). Поле тип идентифицирует функцию сообщения согласно таблице 4.3:

Коды поля тип

Тип Значение
1 Hello (используется для проверки доступности маршрутизатора).
2 Описание базы данных (топология).
3 Запрос состояния канала.
4 Изменение состояния канала.
5 Подтверждение получения сообщения о статусе канала.

Поле длина пакета определяет длину блока в октетах, включая заголовок. Идентификатор области - 32-битный код, идентифицирующий область, которой данный пакет принадлежит. Все OSPF-пакеты ассоциируются с той или иной областью. Большинство из них не преодолевает более одного шага. Пакеты, путешествующие по виртуальным каналам, помечаются идентификатором опорной области (backbone) 0.0.0.0. Поле контрольная сумма содержит контрольную сумму IP-пакета, включая поле типа идентификации. Контрольное суммирование производится по модулю 1. Поле тип идентификации может принимать значения 0 при отсутствии контроля доступа, и 1 при наличии контроля. В дальнейшем функции поля будут расширены. Важную функцию в OSPF-сообщениях выполняет одно-октетное поле опции, оно присутствует в сообщениях типа HELLO, объявление состояния канала и описание базы данных. Особую роль в этом поле играют младшие биты E и Т:

Бит E характеризует возможность внешней маршрутизации и имеет значение только в сообщениях типа HELLO, в остальных сообщениях этот бит должен быть обнулен. Если E=0, то данный маршрутизатор не будет посылать или принимать маршрутную информацию от внешних автономных систем. Бит T определяет сервисные возможности маршрутизатора (TOS). Если T=0, это означает, что маршрутизатор поддерживает только один вид услуг (TOS=0) и он не пригоден для маршрутизации с учетом вида услуг. Такие маршрутизаторы, как правило, не используются для транзитного трафика.

Протокол OSPF использует сообщение типа Hello для взаимообмена данными между соседними маршрутизаторами. Структура пакетов этого типа показана на рисунке 4.10.

Поле сетевая маска соответствует маске субсети данного интерфейса. Например, если интерфейс принадлежит сети класса B и третий байт служит для выделения нужной субсети, то сетевая маска будет иметь вид 0xFFFFFF00.

Поле время между Hello содержит значение времени в секундах, между сообщениями HELLO. Поле опции характеризует возможности, которые предоставляет данный маршрутизатор. Поле приоритет характеризует уровень приоритета маршрутизатора (целое положительное число), используется при выборе резервного (backup) маршрутизатора. Если приоритет равен нулю, данный маршрутизатор никогда не будет использован в качестве резервного. Поле время отключения маршрутизатора определяет временной интервал в секундах, по истечении которого "молчащий" маршрутизатор считается вышедшим из строя. IP-адреса маршрутизаторов, записанные в последующих полях, указывают место, куда следует послать данное сообщение. Поля IP-адрес соседа k образуют список адресов соседних маршрутизаторов, откуда за последнее время были получены сообщения Hello.

Формат сообщения Hello в протоколе OSPF

Формат OSPF-сообщений о маршрутах

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

Поля, начиная с тип канала, повторяются для каждого описания канала. Так как размер базы данных может быть велик, ее содержимое может пересылаться по частям. Для реализации этого используются биты I и М. Бит I устанавливается в 1 в стартовом сообщении, а бит M принимает единичное состояние для сообщения, которые являются продолжением. Бит S определяет то, кем послано сообщение (S=1 для сервера, S=0 для клиента, этот бит иногда имеет имя MS). Поле номер сообщения по порядку служит для контроля пропущенных блоков. Первое сообщение содержит в этом поле случайное целое число M, последующие M+1, M+2,...M+L. Поле тип канала может принимать следующие значения:

Коды типов состояния каналов (LS)

LS-тип Описание объявления о маршруте
1 Описание каналов маршрутизатора, то есть состояния его интерфейсов.
2 Описание сетевых каналов. Это перечень маршрутизаторов, непосредственно связанных с сетью.
3 или 4 Сводное описание каналов, куда входят маршруты между отдельными областями сети. Эта информация поступает от пограничных маршрутизаторов этих зон. Тип 3 приписан маршрутам, ведущим к сетям, а тип 4 характеризует маршруты, ведущие к пограничным маршрутизаторам автономной системы.
5 Описания внешних связей автономной системы. Такие маршруты начинаются в пограничных маршрутизаторах AS.

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

Формат OSPF-запроса маршрутной информации

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

Такое сообщение содержит список объявлений, имеющих формат (рисунок 4.14).

Сообщения об изменениях маршрутов могут быть вызваны следующими причинами:

1. Возраст маршрута достиг предельного значения (LSRefreshTime).

2. Изменилось состояние интерфейса.

3. Произошли изменения в маршрутизаторе сети.

4. Произошло изменение состояния одного из соседних маршрутизаторов.

5. Изменилось состояние одного из внутренних маршрутов (появление нового, исчезновение старого и т.д.)

6. Изменение состояния межзонного маршрута.

7. Появление нового маршрутизатора, подключенного к сети.

8. Вариация виртуального маршрута одним из маршрутизаторов.

9. Возникли изменения одного из внешних маршрутов.

10. Маршрутизатор перестал быть пограничным для данной AS (например, перезагрузился).

Каждое сообщение о состоянии канала начинается с заголовка - "объявление состояния канала" (LS – Link State). Формат этого типа заголовка приведен ниже (20 октетов):

Формат OSPF-сообщения, описывающего состояние канала

Поле возраст LS информации (рисунок 4.15) определяет время в секундах с момента объявления состояния канала. Поле опции содержит значения типов сервиса (TOS), поддерживаемые маршрутизатором, рассылающим маршрутную информацию. Поле тип LS (тип состояния канала) может принимать значения, описанные выше в таблице 4.5. Следует обратить внимание, что код, содержащийся в этом поле, определяет формат сообщения. Поле длина задает размер сообщения в октетах, включая заголовок. В результате получается сообщение с форматом, показанным на рисунке 4.15. Зарезервированный октет должен быть обнулен. Идентификатор связи определяет тип маршрутизатора, подключенного к каналу. Действительное значение этого поля зависит от поля тип. В свою очередь информация о канале также зависит от поля тип. Число TOS определяет многообразие метрик, соответствующих видам сервиса, для данного канала. Последовательность описания метрик задается величиной кода TOS. Таблица кодов TOS, принятых в OSPF протоколе приведена ниже.

Коды типа сервиса (TOS)

OSPF-код
TOS-коды TOS (RFC 1349)
0 0000 Обычный сервис
2 0001 Минимизация денежной стоимости
4 0010 Максимальная надежность
8 0100 Максимальная пропускная способность
16 1000 Минимальная задержка

Если бит V=1 (virtual), маршрутизатор является оконечной точкой активного виртуального канала. Если бит E (external) равен 1, маршрутизатор является пограничным для автономной системы. Бит B=1 (border) указывает на то, что маршрутизатор является пограничным для данной области. Поле тип может принимать значения, приведенные в таблице 4.6.

Таблица 4.6 - Коды типов связей (см. рисунок 4.16)

Код типа связи Описание
1 Связь с другим маршрутизатором по схеме точка-точка
2 Связь с транзитной сетью
3 Связь с оконечной сетью
4 Виртуальная связь (например, опорная сеть или туннель)

Формат описания типа канала с LS=1

Поле идентификатор канала характеризует объект, с которым связывается маршрутизатор. Примеры идентификаторов представлены в таблице:

Таблица 4.7 - Коды идентификаторов канала

Код идентификатора Описание
1 Идентификатор соседнего маршрутизатора
2 IP-адрес основного маршрутизатора (по умолчанию)
3 IP-адрес сети/субсети
4 Идентификатор соседнего маршрутизатора

Маршрутизатор, получивший OSPF-пакет, посылает подтверждение его приема. Этот вид пакетов имеет тип=5 и структуру, отображенную на рисунок 4.17. Получение нескольких объявлений о состоянии линий может быть подтверждено одним пакетом. Адресом места назначения этого пакета может быть индивидуальный маршрутизатор, группа маршрутизаторов или все маршрутизаторы автономной системы.

Формат сообщения о получении OSPF-пакета

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

Формат сообщения о сетевых связях (тип LS=2)

Сообщение о сетевых связях должно содержать информацию обо всех маршрутизаторах, подключенных к сети, включая тот, который рассылает эту информацию. Расстояние от сети до любого подключенного маршрутизатора равно нулю для всех видов сервиса (TOS), поэтому поля TOS и метрики в этих сообщениях отсутствуют. Формат сообщения о транзитных сетевых связях показан на рисунок 4.18.

Следует помнить, что приведенные ниже сообщения должны быть снабжены стандартными 24-октетными OSPF-заголовками (на рисунке 4.19 отсутствует).

Сетевая маска относится к описываемой сети, а поле подключенный маршрутизатор содержит идентификатор маршрутизатора, работающего в сети. Информация об адресатах в пределах автономной системы передается LS-сообщениями типа 3 и 4. Тип 3 работает для IP-сетей. В этом случае в качестве идентификатора состояния канала используется IP-адрес сети. Если же адресатом является пограничный маршрутизатор данной AS, то используется LS-сообщение типа 4, а в поле идентификатор состояния канала записывается OSPF-идентификатор этого маршрутизатора. Во всех остальных отношениях сообщения 3 и 4 имеют идентичные форматы (рисунок 4.20):

Формат сообщений об адресатах в пределах автономной системы

Поля, следующие после заголовка, повторяются в соответствии с числом описываемых объектов. Рекламирование внешних маршрутов относится к пятому типу. Эта информация рассылается пограничными маршрутизаторами. Информация о каждом внешнем адресате, известном маршрутизатору, посылается независимо. Этот вид описания используется и для маршрутов по умолчанию, для которых идентификатор состояния канала устанавливается равным 0.0.0.0 (аналогичное значение принимает при этом и сетевая маска)

Формат описания внешних маршрутов.

Сетевая маска характеризует место назначения рекламируемого маршрута. Так для сети класса A маска может иметь вид 0xFF000000. Последующий набор полей повторяется для каждого вида TOS. Поля для TOS=0 заполняются всегда, и это описание является первым. Бит E характеризует внешнюю метрику. Если E=0, то она может непосредственно (без преобразования) сравниваться с метриками других каналов. При E=1 метрика считается больше любой метрики. Поле адрес пересылки указывает на место, куда будут пересылаться данные, адресованные рекламируемым маршрутом. Если адрес пересылки равен 0.0.0.0, данные посылаются пограничному маршрутизатору автономной системы - источнику данного сообщения. Метка внешнего маршрута - 32-битовое число, присваиваемое каждому внешнему маршруту. Эта метка самим протоколом OSPF не используется и предназначена для информирования других автономных систем при работе внешних протоколов маршрутизации. Маршрутная таблица OSPF содержит в себе:

1) IP-адрес места назначения и маску;

2) тип места назначения (сеть, граничный маршрутизатор и т.д.);

3) тип функции (возможен набор маршрутизаторов для каждой из функций TOS);

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

5) тип пути (характеризует путь как внутренний, межобластной или внешний, ведущий к AS);

6) цена маршрута до цели;

7) очередной маршрутизатор, куда следует послать дейтограмму;

8) объявляющий маршрутизатор (используется для межобластных обменов и для связей автономных систем друг с другом).

Преимущества OSPF:

1) Для каждого адреса может быть несколько маршрутных таблиц, по одной на каждый вид IP-операции (TOS).

2) Каждому интерфейсу присваивается безразмерная цена, учитывающая пропускную способность, время транспортировки сообщения. Для каждой IP-операции может быть присвоена своя цена (коэффициент качества).

3) При существовании эквивалентных маршрутов OSFP распределяет поток равномерно по этим маршрутам.

4) Поддерживается адресация субсетей (разные маски для разных маршрутов).

5) При связи точка-точка не требуется IP-адрес для каждого из концов. (Экономия адресов!)

6) Применение мультикастинга вместо широковещательных сообщений снижает загрузку не вовлеченных сегментов.

Недостатки:

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

2) OSPF является лишь внутренним протоколом.

Этот протокол маршрутизации предназначен для сравнительно небольших и относительно однородных сетей (алгоритм Белмана-Форда). Протокол разработан в университете Калифорнии (Беркли), базируется на разработках фирмы Ксерокс и реализует те же принципы, что и программа маршрутизации routed, используемая в ОC UNIX (4BSD). Маршрут здесь характеризуется вектором расстояния до места назначения. Предполагается, что каждый маршрутизатор является отправной точкой нескольких маршрутов до сетей, с которыми он связан. Описания этих маршрутов хранится в специальной таблице, называемой маршрутной. Таблица маршрутизации RIP содержит по записи на каждую обслуживаемую машину (на каждый маршрут). Запись должна включать в себя:

IP-адрес места назначения. Метрика маршрута (от 1 до 15; число шагов до места назначения). IP-адрес ближайшего маршрутизатора (Gateway) по пути к месту назначения. Таймеры маршрута.

Первым двум полям записи мы обязаны появлению термина вектор расстояния (место назначение – направление; метрика – модуль вектора). Периодически (раз в 30 сек) каждый маршрутизатор посылает широковещательно копию своей маршрутной таблицы всем соседям-маршрутизаторам, с которыми связан непосредственно. Маршрутизатор-получатель просматривает таблицу. Если в таблице присутствует новый путь или сообщение о более коротком маршруте, или произошли изменения длин пути, эти изменения фиксируются получателем в своей маршрутной таблице. Протокол RIP должен быть способен обрабатывать три типа ошибок:

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

2. Для подавления нестабильностей RIP должен использовать малое значение максимально возможного числа шагов (<16).

3. Медленное распространение маршрутной информации по сети создает проблемы при динамичном изменении маршрутной ситуации (система не поспевает за изменениями). Малое предельное значение метрики улучшает сходимость, но не устраняет проблему.

Несоответствие маршрутной таблицы реальной ситуации типично не только для RIP, но характерно для всех протоколов, базирующихся на векторе расстояния, где информационные сообщения актуализации несут в себе только пары кодов: адрес места назначение и расстояние до него.

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

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

В качестве примера мы рассмотрим сеть (см. Рисунок 4.2) из нескольких последовательно соединенных маршрутизаторов, где метрикой является число транзитных узлов на пути к точке назначения (как в протоколе RIP).

Распространение "хорошей" новости в сети

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

Во время первого обмена узел B узнает, что A заработал и вносит в свою таблицу маршрутизации "1" как расстояние до A; все остальные узлы в этот момент по-прежнему считают A недоступным. При следующем обмене, спустя несколько секунд, узел C также узнает о появлении маршрутизатора A. В результате последовательности таких обменов информация достигнет и узла E, для которого стоимость маршрута до А будет "4".

Таким образом, для сети с максимальной длиной маршрута N сообщение о новом маршрутизаторе дойдет до самого удаленного узла в сети через N-1 циклов обмена таблицами маршрутизации. На этом этапе никаких проблем не возникает.

Теперь мы рассмотрим обратный случай (см. Рисунок 4.3), когда узел А перестает работать вследствие сбоя. При очередном обмене (мы будем считать его первым в этой серии) узел В не получает никакого сообщения от молчащего маршрутизатора А. Это верный сигнал о том, что у А возникли проблемы, и информацию о нем необходимо удалить из таблицы. Однако в то же самое время узел C сообщает, что ему известен путь до А и стоимость этого пути "2". Тот факт, что путь до А, объявленный узлом C, проходит через сам B (т. е. образуется петля), ускользает от внимания маршрутизатора, и он заносит в таблицу путь до неработающего А стоимостью "3".

Проблема возрастания до бесконечности.

Во время следующего обмена C замечает, что оба его соседа рекламируют путь до A стоимостью "3", и немедленно делает поправки в своей таблице. Теперь длина пути от С до A - "4". Если этот процесс не остановить, то он может продолжаться до бесконечности, и никто так и не узнает, что маршрутизатор А давно вышел из строя. Соответственно данные к А будут посылаться и дальше.

Эта проблема алгоритма вектора расстояний получила название проблемы возрастания до бесконечности (count-to-infinity problem). Она является основной причиной задания ограничений на максимальную длину пути во всех протоколах вектора расстояния.

Протокол RIP, например, считает маршрут длиной более чем в 15 транзитных узлов бесконечным. Такой путь будет немедленно удален из таблицы маршрутизации. Т. е. в последнем примере узел B поймет, что узел А недоступен, когда получит объявление пути до А со стоимостью "15". К сожалению, такая процедура занимает слишком много времени.

Для предотвращения образования ложных маршрутов используется несколько методов, один из них - метод расщепления горизонта (split-horizon). Данное правило не так сложно, как может показаться из названия: "Если известно, что путь до узла X лежит через соседний узел Y, то узлу Y не надо посылать объявления маршрута до X".

Мы рассмотрим тот же пример, что и на Рисунке 4.3 , но в условиях, когда действует правило расщепления горизонта. После выхода из строя маршрутизатора А узел В узнает о недееспособности А при первом же обмене. Узлу С правило расщепления горизонта запрещает посылать информацию об А на В, так как путь к А лежит через В. Таким образом, узел С не может теперь (непреднамеренно) обманывать своего соседа слева, и узел В тут же помечает маршрутизатор А как недоступный. После следующего обмена уже С узнает от В о недоступности А, вместе с тем ложная информация от узла D, который все еще считает маршрутизатор А действующим, на С не поступит.

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

Рассмотрим пример сети с избыточной топологией (см. Рисунок 3). В начальный момент времени А и B знают, что расстояние до узла D равно "2". После выхода D из строя маршрутизатор C, не получив от D сообщения, определяет, что узел D недоступен. А и В продолжают считать D доступным, но правило расщепления горизонта запрещает им сообщать эту ложную информацию маршрутизатору С. При следующем обмене C уведомляет A и B о недоступности D. Но одновременно с этим узел А получает от В сообщение о пути до D стоимостью "2", а узел В получает аналогичное сообщение от А.

Информация об аварии на D не будет услышана. Проблема возрастания до бесконечности возникла вновь.

В качестве метрики RIP использует число шагов до цели. Если между отправителем и приемником расположено три маршрутизатора (gateway), считается, что между ними 4 шага. Для всех непосредственно подключенных интерфейсов счетчик пересылок равен 1. Рассмотрим маршрутизаторы и сети, показанные на рисунке 4.5. Четыре пунктирные линии показывают широковещательные сообщения RIP.

Маршрутизатор R1 объявляет маршрут к N2 со счетчиком пересылок равным 1, послав широковещательное сообщение на N1. (Бессмысленно объявлять маршрут к N1 в широковещательном сообщении, посланном на N1.) Он также объявляет маршрут к N1 со счетчиком пересылок равным 1, послав широковещательное сообщение на N2. Точно так же, R2 объявляет маршрут к N2 с показателем 1 и маршрут к N3 с показателем 1. Если смежный с нами маршрутизатор объявил маршрут к удаленной сети со счетчиком пересылок равным 1, то для нас показатель к этой сети будет равен 2, так пакет необходимо послать сначала на наш маршрутизатор, чтобы получить доступ к сети. В примере, приведенном выше, показатель к N1 для R2 равен 2, так же как и показатель к N3 для R1.

Пример маршрутизаторов и сетей.

Так как каждый маршрутизатор посылает свои таблицы маршрутизации соседям, определяется каждая сеть в каждой автономной системе (AS). Если внутри AS существует несколько путей от маршрутизатора к сети, маршрутизатор выбирает путь с наименьшим количеством пересылок и игнорирует другие пути.

Величина счетчика пересылок ограничена значением 15, что означает, что RIP может быть использован только внутри AS, где максимальное количество пересылок между хостами составляет 15. Специальное значение показателя, равное 16, указывает на то, что на данный IP адрес не существует маршрута.

Такой вид метрики не учитывает различий в пропускной способности или загруженности отдельных сегментов сети. Применение вектора расстояния не может гарантировать оптимальность выбора маршрута, ведь, например, два шага по сегментам сети Ethernet обеспечат большую пропускную способность, чем один шаг через последовательный канал на основе интерфейса RS-232.

Маршрут по умолчанию имеет адрес 0.0.0.0 (это верно и для других протоколов маршрутизации). Каждому маршруту ставится в соответствие таймер тайм-аута и "сборщика мусора". Тайм-аут-таймер сбрасывается каждый раз, когда маршрут инициализируется или корректируется. Если со времени последней коррекции прошло 3 минуты или получено сообщение о том, что вектор расстояния равен 16, маршрут считается закрытым. Но запись о нем не стирается, пока не истечет время "уборки мусора" (2мин). При появлении эквивалентного маршрута переключения на него не происходит, таким образом, блокируется возможность осцилляции между двумя или более равноценными маршрутами.

RIP сообщения инкапсулируются в UDP-дейтограммы, при этом передача осуществляется через порт 520.

Инкапсуляция RIP сообщения в UDP датаграмму.

Формат сообщения протокола RIP имеет вид, показанный на рис. 3.5. Поле команда определяет выбор согласно следующей таблице 4.1:

Таблица 4.1 - Значения кодов поля команда

Команда Значение

1 Запрос на получение частичной или полной маршрутной информации;

2 Отклик, содержащий информацию о расстояниях из маршрутной таблицы отправителя;

3 Включение режима трассировки (устарело);

4 Выключение режима трассировки (устарело);

5-6 Зарезервированы для внутренних целей SUN Microsystem.

Поле версия для RIP равно 1 (для RIP-2 двум). Поле набор протоколов сети i определяет набор протоколов, которые используются в соответствующей сети (для Интернет это поле имеет значение 2). Поле расстояние до сети i содержит целое число шагов (от 1 до 15) до данной сети. В одном сообщении может присутствовать информация о 25 маршрутах. При реализации RIP можно выделить следующие режимы:

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

Получен запрос. В зависимости от типа запроса высылается адресату полная таблица маршрутизации, или проводится индивидуальная обработка.

Получен отклик. Проводится коррекция таблицы маршрутизации (удаление, исправление, добавление).

Формат сообщения RIP

Регулярные коррекции. Каждые 30 секунд вся или часть таблицы маршрутизации посылается всем соседним маршрутизаторам. Могут посылаться и специальные запросы при локальном изменении таблицы. RIP достаточно простой протокол, но, к сожалению не лишенный недостатков:

a. RIP не работает с адресами субсетей. Если нормальный 16-бит идентификатор ЭВМ класса B не равен 0, RIP не может определить является ли не нулевая часть cубсетевым ID, или полным IP-адресом.

b. RIP требует много времени для восстановления связи после сбоя в маршрутизаторе (минуты). В процессе установления режима возможны циклы.

c. Число шагов важный, но не единственный параметр маршрута, да и 15 шагов не предел для современных сетей.

Протокол RIP-2 (RFC-1388, 1993 год) является новой версией RIP, которая в дополнение к широковещательному режиму поддерживает мультикастинг; позволяет работать с масками субсетей. На рис. 3.8 представлен формат сообщения для протокола RIP-2. Поле маршрутный демон является идентификатором резидентной программы-маршрутизатора. Поле метка маршрута используется для поддержки внешних протоколов маршрутизации, сюда записываются коды автономных систем. При необходимости управления доступом можно использовать первые 20 байт с кодом набора протоколов сети 0xFFFF и меткой маршрута =2. Тогда в остальные 16 байт можно записать пароль.

Формат сообщений протокола RIP-2

Протокол внешних маршрутизаторов (Exterior Gateway Protocol-EGP) является протоколом междоменной досягаемости, который применяется в Internet - международной сети, об'единяющей университеты, правительственные учреждения, научно-исследовательские организации и частные коммерческие концерны. EGP документально оформлен в Запросах для Комментария (RFC) 904, опубликованных в апреле 1984 г.

Являясь первым протоколом внешних маршрутизаторов, который получил широкое признание в Internet, EGP сыграл важную роль. К сожалению, недостатки EGP стали более очевидными после того, как Internet стала более крупной и совершенной сетью. Из-за этих недостатков EGP в настоящее время не отвечает всем требованиям Internet и заменяется другими протоколами внешних маршрутизаторов, такими, как Протокол граничных маршрутизаторов (Border Gateway Protocol - BGP) и Протокол междоменной маршрутизации (Inter-Domain Routing Protocol - IDRP).

Основы технологии

EGP первоначально предназначался для передачи информации о досягаемости в стержневые маршрутизаторы ARPANET и получения ее от них. Информация передавалась из отдельных узлов источника, находящихся в различных административных доменах, называемых автономными системами (AS), вверх в стержневые маршрутизаторы, которые передавали эту информацию через стержневую область до тех пор, пока ее можно было передать вниз к сети пункта назначения, находящейся в пределах другой AS. Эти взаимоотношения между EGP и другими компонентами ARPANET показаны на Рисунке 4.29.

Несмотря на то, что EGP является динамическим протоколом маршрутизации, он использует очень простую схему. Он не использует показатели, и следовательно, не может принимать по настоящему интеллектуальных решений о маршрутизации. Корректировки маршрутизации EGP содержат информацию о досягаемости сетей. Другими словами, они указывают, что в определенные сети попадают через определенные маршрутизаторы.

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

Формат пакета EGP

Первым полем в заголовке пакета EGP является поле номера версии EGP (EGP version number). Это поле обозначает текущую версию EGP и проверяется приемными устройствами для определения соответствия между номерами версий отправителя и получателя.

Следующим полем является поле типа (type), которое обозначает тип сообщения. EGP выделяет 5 отдельных типов сообщения.

За полем типа следует поле кода (code). Это поле определяет различие между подтипами сообщений.

Следующее поле - поле состояния (status), которое содержит информацию о состоянии, зависящую от сообщения. В число кодов состояния входят коды недостатка ресурсов (insufficient resources), неисправных параметров (parameter problem), нарушений протокола (protocol violation), и другие.

За полем состояния идет поле контрольной суммы (checksum). Контрольная сумма используется для обнаружения возможных проблем, которые могли появиться в пакете в результате транспортировки.

За полем контрольной суммы идет поле номера автономной системы (autonomous system number). Оно обозначает AS, к которой принадлежит маршрутизатор- отправитель.

Последним полем заголовка пакета EGP является поле номера последовательности (sequence number). Это поле позволяет двум маршрутизаторам EGP, которые oбмениваются сообщениями, согласовывать запросы с ответами. Когда определен какой-нибудь новый сосед, номер последовательности устанавливается в исходное нулевое значение и инкрементируется на единицу с каждой новой транзакцией запрос-ответ.

За заголовком EGP идут дополнительные поля. Содержимое этих полей различается в зависимости от типа сообщения (определяемого полем типа).

Типы сообщений

За заголовком EGP идут дополнительные поля. Содержимое этих полей различается в зависимости от типа сообщения (определяемого полем типа).

Приобретение соседа

Сообщение "приобретение соседа" включает в себя интервал приветствия (hello interval) и интервал опроса (poll interval). Поле интервала приветствия определяет период интервала проверки работоспособности соседей. Поле интервала опроса определяет частоту корректировки маршрутизации.

Досягаемость соседа

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

Опрос

Чтобы обеспечить правильную маршрутизацию между AS, ЕGP должен знать об относительном местоположении отдаленных хостов. Сообщение опроса позволяет маршрутизаторам EGP получать информацию о досягаемости сетей, в которых находятся эти машины. Такие сообщения имеют только одно поле помимо обычного заголовка - поле сети источника IP (source network). Это поле определяет сеть, которая должна использоваться в качестве контрольной точки для запроса.

Корректиравка маршрутизации

Сообщения о корректировке маршрутизации дают маршрутизаторам EGP возможность указывать местоположение различных сетей в пределах своих AS. В дополнение к обычному заголовку эти сообщения включают несколько дополнительных полей. Поле числа внутренних маршрутизаторов (number of interior gateways) указывает на число внутренних маршрутизаторов, появляющихся в сообщении. Поле числа внешних маршрутизаторов (number of exterior gateways) указывает на число внешних маршрутизаторов, появляющихся в сообщении. Поле сети источника IP (IP source network) обеспечивает адрес IP той сети, от которой измерена досягаемость. За этим полем идет последовательность блоков маршрутизаторов (gateway blocks). Каждый блок маршрутизаторов обеспечивает адрес IP какого-нибудь маршрутизатора и перечень сетей, а также расстояний, связанных с достижением этих сетей.

В пределах одного блока маршрутизатора EGP перечисляет сети по расстояниям. Например, на расстоянии три может быть четыре сети. Эти сети перечислены по адресам. Следующей группой сетей могут быть сети, находящиеся на расстоянии 4, и т.д.

ЕGP не расшифровывает показатели расстояния, содержащиеся в сообщениях о корректировке маршрутов. EGP фактически использует поле расстояния для указания существования какого-либо маршрута; значение расстояния может быть использовано только для сравнения трактов, если эти тракты полностью находятся в пределах одного конкретного AS. По этой причине EGP является скорее протоколом досягаемости, чем протоколом маршрутизации. Это ограничение приводит также к ограничениям в структуре Internet. Характерно, что любая часть EGP сети Internet должна представлять собой структуру дерева, у которого стержневой маршрутизатор является корнем, и в пределах которого отсутствуют петли между другими AS. Это ограничение является основным ограничением EGP; оно стало причиной его постепенного вытеснения другими, более совершенными протоколами внешних маршрутизаторов.

Сообщения о неисправностях

Сообщения о неисправностях указывают на различные сбойные ситуации. В дополнение к общему заголовку EGP сообщения о неисправностях обеспечивают поле причины (reason), за которым следует заголовок сообщения о неисправности (message header). В число типичных неисправностей (причин) EGP входят неисправный формат заголовка EGP (bad EGP header format), неисправный формат поля данных EGP (bad EGP data field format), чрезмерная скорость опроса (excessive polling rate) и невозможность достижения информации (unavailability of reachability information). Заголовок сообщения о неисправности состоит из первых трех 32-битовых слов заголовка EGP.

Протокол BGP (RFC-1267, BGP-3; RFC-1268; RFC-1467, BGP-4; -1265-66, 1655) разработан компаниями IBM и CISCO. Главная цель BGP - сократить транзитный трафик. Местный трафик либо начинается, либо завершается в автономной системе (AS); в противном случае – это транзитный трафик. Системы без транзитного трафика не нуждаются в BGP (им достаточно EGP для общения с транзитными узлами). Но не всякая ЭВМ, использующая протокол BGP, является маршрутизатором, даже если она обменивается маршрутной информацией с пограничным маршрутизатором соседней автономной системы. AS передает информацию только о маршрутах, которыми она сама пользуется. BGP-маршрутизаторы обмениваются сообщениями об изменении маршрутов (UPDATE-сообщения, рисунок 4.25). Максимальная длина таких сообщений составляет 4096 октетов, а минимальная 19 октетов. Каждое сообщение имеет заголовок фиксированного размера. Объем информационных полей зависит от типа сообщения.

Формат BGP-сообщений об изменениях маршрутов

Поле маркер содержит 16 октетов и его содержимое может легко интерпретироваться получателем. Если тип сообщения "OPEN", или если код идентификации в сообщении OPEN равен нулю, то поле маркер должно быть заполнено единицами. Маркер может использоваться для обнаружения потери синхронизации в работе BGP-партнеров. Поле длина имеет два октета и определяет общую длину сообщения в октетах, включая заголовок. Значение этого поля должно лежать в пределах 19-4096. Поле тип представляет собой код разновидности сообщения и может принимать следующие значения:

1 OPEN (открыть)
2 UPDATE (изменить)
3 NOTIFICATION (внимание)
4 KEEPALIVE (еще жив)

После того как связь на транспортном протокольном уровне установлена, первое сообщение, которое должно быть послано - это OPEN. При успешном прохождении этого сообщения партнер должен откликнуться сообщением KEEPALIVE ("Еще жив"). После этого возможны любые сообщения. Кроме заголовка сообщение OPEN содержит следующие поля (рисунок 4.26):

Формат сообщения OPEN

Поле версия описывает код версии используемого протокола, на сегодня для BGP он равен 4. Двух-октетное поле моя автономная система определяет код AS отправителя. Поле время сохранения характеризует время в секундах, которое отправитель предлагает занести в таймер сохранения. После получения сообщения OPEN BGP-маршрутизатор должен выбрать значение времени сохранения. Обычно выбирается меньшее из полученного в сообщении OPEN и значения, определенного при конфигурации системы (0-3сек). Время сохранения определяет максимальное время в секундах между сообщениями KEEPALIVE и UPDATE или между двумя UPDATE- сообщениями. Каждому узлу в рамках BGP приписывается 4-октетный идентификатор (BGP-identifier, задается при инсталляции и идентичен для всех интерфейсов локальной сети). Если два узла установили два канала связи друг с другом, то согласно правилам должен будет сохранен канал, начинающийся в узле, BGP- идентификатор которого больше. Предусмотрен механизм разрешения проблемы при равных идентификаторах.

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

Длина сообщения = 29 + длина поля идентификационных данных.

Минимальная длина сообщения OPEN составляет 29 октетов, включая заголовок.Сообщения типа UPDATE (изменения) используются для передачи маршрутной информации между BGP-партнерами. Этот тип сообщения позволяет сообщить об одном новом маршруте или объявить о закрытии группы маршрутов, причем объявление об открытии нового и закрытии старых маршрутов возможно в пределах одного сообщения. Сообщение UPDATE всегда содержит стандартный заголовок и может содержать другие поля в соответствии со схемой:

Формат UPDATE-сообщения

Если длина списка отмененных маршрутов равна нулю, ни один маршрут не отменен, а поле отмененные маршруты в сообщении отсутствует. Поле отмененные маршруты имеет переменную длину и содержит список IP-адресных префиксов маршрутов, которые стали недоступны. Каждая такая запись имеет формат:

Длина префикса (в битах), равная нулю означает, что префикс соответствует всем IP-адресам, а сам имеет нулевой размер. Поле префикс содержит IP-адресные префиксы, за которыми следуют разряды, дополняющие их до полного числа октетов. Значения этих двоичных разрядов смысла не имеют.

Нулевое значение полной длины списка атрибутов пути говорит о том, что информация о доступности сетевого уровня в UPDATE-сообщении отсутствует. Список атрибутов пути присутствует в любом UPDATE-сообщении. Этот список имеет переменную длину, а каждый атрибут содержит три составные части: тип атрибута, длину атрибута и значение атрибута. Тип атрибута представляет собой двух- октетное поле со структурой:

Старший бит (бит0) поля флаги атрибута определяет, является ли атрибут опционным (бит0=1) или стандартным (well-known, бит0=0). Бит 1 этого поля определяет, является ли атрибут переходным (бит1=1) или непереходным (бит1=0). Для обычных атрибутов этот бит должен быть равен 1. Третий бит (бит 2) поля Флагов атрибута определяет, является ли информация в опционном переходном атрибуте полной (бит2=0) или частичной (бит2=1). Для обычных и для опционных непереходных атрибутов этот бит должен быть равен нулю. Бит 3 поля флагов атрибута информирует о том, имеет ли длина атрибута один (бит3=0) октет или два октета (бит3=1). Бит3 может быть равен 1 только в случае, когда длина атрибута более 255 октетов. Младшие 4 бита октета флагов атрибута не используются (и должны обнуляться). Если бит3=0, то третий октет атрибута пути содержит длину поля данных атрибута в октетах. Если же бит3=1, то третий и четвертый октеты атрибута пути хранят длину поля данных атрибута. Остальные октеты поля атрибут пути характеризуют значение атрибута и интерпретируются согласно флагам атрибута.

Атрибуты пути бывают "стандартные обязательные" (well-known mandatory), "стандартные на усмотрение оператора", "опционные переходные" и "опционные непереходные". Стандартные атрибуты должны распознаваться любыми BGP- приложениями. Опционные атрибуты могут не распознаваться некоторыми приложениями. Обработка нераспознанных атрибутов задается битом 1 поля флагов. Пути с нераспознанными переходными опционными атрибутами должны восприниматься, как рабочие. Один и тот же атрибут может появляться в списке атрибутов пути только один раз.

Предусмотрены следующие разновидности кодов типа атрибута:

ORIGIN (код типа = 1) - стандартный обязательный атрибут, который определяет происхождение путевой информации. Генерируется автономной системой, которая является источником маршрутной информации. Значение атрибута в этом случае может принимать следующие значения:

Код атрибута Описание
0 IGP - информация достижимости сетевого уровня является внутренней по отношению к исходной автономной системе;
1 EGP - информация достижимости сетевого уровня получена с помощью внешнего протокола маршрутизации;
2 INCOMPLETE - информация достижимости сетевого уровня получена каким-то иным способом.

AS_PATH (код типа = 2) также является стандартным обязательным атрибутом, который составлен из совокупности сегментов пути. Атрибут определяет автономные системы, через которые доставлена маршрутная информация. Когда BGP-маршрутизатор передает описание маршрута, которое он получил от своего BGP-партнера, он модифицирует AS_PATH-атрибут, соответствующий этому маршруту, если информация передается за пределы автономной системы. Каждый сегмент AS_PATH состоит из трех частей <тип сегмента пути, длина сегмента пути и оценка сегмента пути>. Тип сегмента пути представляет в свою очередь однооктетное поле, которое может принимать следующие значения:

Код типа сегмента Описание
1 AS_SET: неупорядоченный набор маршрутов в UPDATE сообщении;
2 AS_SEQUENCE: упорядоченный набор маршрутов автономной системы в UPDATE-сообщении.

Длина сегмента пути представляет собой одно-октетное поле, содержащее число AS, записанных в поле оценка сегмента пути. Последнее поле хранит один или более кодов автономной системы, по два октета каждый.

NEXT_HOP (код типа = 3) - стандартный обязательный атрибут, определяющий IP- адрес пограничного маршрутизатора, который должен рассматриваться как цель следующего шага на пути к точке назначения.

MULI_EXIT_DISC (код типа = 4) представляет собой опционный непереходной атрибут, который занимает 4 октета и является положительным целым числом. Величина этого атрибута может использоваться при выборе одного из нескольких путей к соседней автономной системе.

LOCAL_PREF (код типа = 5) является опционным атрибутом, занимающим 4 октета. Он используется BGP-маршрутизатором, чтобы сообщить своим BGP-партнерам в своей собственной автономной системе степень предпочтения объявленного маршрута.

ATOMIC_AGGREGATE (код типа = 6) представляет собой стандартный атрибут, который используется для информирования партнеров о выборе маршрута, обеспечивающего доступ к более широкому списку адресов.

AGGREGATOR (код типа = 7) - опционный переходной атрибут с длиной в 6 октетов. Атрибут содержит последний код автономной системы, который определяет агрегатный маршрут (занимает два октета), и IP-адрес BGP-маршрутизатора, который сформировал этот маршрут (4 октета). Объем информации о достижимости сетевого уровня равен (в октетах):

Поле длина определяет длину IP-адресного префикса в битах. Если длина равна нулю, префикс соответствует всем IP-адресам. Префикс содержит IP-адресные префиксы и двоичные разряды, дополняющие код до целого числа октетов.

Информация о работоспособности соседних маршрутизаторов получается из KEEPALIVE-сообщений, которые должны посылаться настолько часто, чтобы уложиться во время, отведенное таймером сохранения (HOLD). Обычно это время не должно превышать одной трети от времени сохранения, но не должно быть и меньше 1 секунды. Если выбранное значение времени сохранения равно нулю, периодическая посылка KEEPALIVE-сообщений не обязательна.

NOTIFICATION-сообщения посылаются, когда обнаружена ошибка. BGP-связь при этом немедленно прерывается. Помимо заголовка NOTIFICATION-сообщение имеет следующие поля:

Код ошибки представляет собой одно-октетное поле и указывает на тип данного сообщения. Возможны следующие коды ошибки:

Коды ошибок

Код ошибки Описание
1 Ошибка в заголовке сообщения.
2 Ошибка в сообщении OPEN
3 Ошибка в сообщении UPDATE
4 Истекло время сохранения
5 Ошибка машины конечных состояний
6 Прерывание

При отсутствии фатальной ошибки BGP-партнер может в любой момент прервать связь, послав NOTIFICATION-сообщение с кодом ошибки прерывание.

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

Субкоды ошибок

Ошибка .............................Субкод .......................................Описание
Заголовок .........................1
2
3 ........................Соединение не синхронизовано
Неверная длина сообщения
Неверный тип сообщения
Сообщения OPEN ..............1
2
3
4
5
6 .........................Неверный код версии
Ошибочный код AS-партнера
Ошибочный идентификатор BGP
Ошибка в коде идентификации
Ошибка при идентификации
Неприемлемое время сохранения
Сообщения UPDATE ...............1
2
3
4
5
6
7
8
9
10
11 ........................Ошибка в списке атрибутов
Не узнан стандартный атрибут
Отсутствует стандартный атрибут
Ошибка в флагах атрибута
Ошибка в длине атрибута
Неправильный атрибут ORIGIN
Циклический маршрут
Ошибка в атрибуте NEXT_HOP
Ошибка в опционном атрибуте
Ошибка в сетевом поле
Ошибка в AS_PATH

Вся маршрутная информация хранится в специальной базе данных RIB (Routing Information Base). Маршрутная база данных BGP состоит из трех частей:

1. Adj-RIBs-In: Запоминает маршрутную информацию, которая получена из UPDATE-сообщений. Это список маршрутов, из которого можно выбирать. (Policy Information Base - PIB).

2. Loc-RIB: Содержит локальную маршрутную информацию, которую BGP-маршрутизатор отобрал, руководствуясь маршрутной политикой, из Adj-RIBs-In.

3. Adj-RIBs-Out: Содержит информацию, которую локальный BGP-маршрутизатор отобрал для рассылки соседям с помощью UPDATE-сообщений.

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

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

BGP использует три таймера:

ConnectRetry (сбрасывается при инициализации и коррекции; 120 сек),

Holdtime (запускается при получении команд Update или KeepAlive; 90сек) и

KeepAlive (запускается при посылке сообщения KeepAlive; 30сек).

BGP отличается от RIP и OSPF тем, что использует TCP в качестве транспортного протокола. Две системы, использующие BGP, связываются друг с другом и пересылают посредством TCP полные таблицы маршрутизации. В дальнейшем обмен идет только в случае каких-то изменений. ЭВМ, использующая BGP, не обязательно является маршрутизатором. Сообщения обрабатываются только после того, как они полностью получены.

BGP является протоколом, ориентирующимся на вектор расстояния. Вектор описывается списком AS по 16 бит на AS. BGP регулярно (каждые 30сек) посылает соседям TCP-сообщения, подтверждающие, что узел жив (это не тоже самое что "keepalive" функция в TCP). Если два BGP-маршрутизатора попытаются установить связь друг с другом одновременно, такие две связи могут быть установлены. Такая ситуация называется столкновением, одна из связей должна быть ликвидирована. При установлении связи маршрутизаторов сначала делается попытка реализовать высший из протоколов (например, BGP-4), если один из них не поддерживает эту версию, номер версии понижается.

Протокол BGP-4 является усовершенствованной версией (по сравнению с BGP-3). Эта версия позволяет пересылать информацию о маршруте в рамках одного IP-пакета. Концепция классов сетей и субсети находятся вне рамок этой версии. Для того чтобы приспособиться к этому, изменена семантика и кодирование атрибута AS_PASS. Введен новый атрибут LOCAL_PREF (степень предпочтительности маршрута для собственной AS), который упрощает процедуру выбора маршрута. Атрибут INTER_AS_METRICS переименован в MULTI_EXIT_DISC (4 октета; служит для выбора пути к одному из соседей). Введены новые атрибуты ATOMIC_AGGREGATE и AGGREGATOR, которые позволяют группировать маршруты. Структура данных отражается и на схеме принятия решения, которая имеет три фазы:

1. Вычисление степени предпочтения для каждого маршрута, полученного от соседней AS, и передача информации другим узлам местной AS.

2. Выбор лучшего маршрута из наличного числа для каждой точки назначения и укладка результата в Loc-RIB.

3. Рассылка информации из Loc_RIB всем соседним AS согласно политике, заложенной в RIB. Группировка маршрутов и редактирование маршрутной информации.