RFC 2453 RIP Version 2

Network Working Group                                      G. Malkin
Request for Comments: 2453                              Bay Networks
Obsoletes: 1723, 1388                                  November 1998
STD: 56
Category: Standards Track

Протокол RIP версии 2

RIP Version 2

PDF

Статус документа

Этот документ содержит спецификации протокола для сообщества Internet и служит запросом для предложений и дальнейшего обсуждения в целях развития стандарта. Информацию о текущем статусе документа можно найти в Internet Official Protocol Standards (STD 1). Документ может распространяться свободно.

Авторские права

Copyright (C) The Internet Society (1998). All Rights Reserved.

Тезисы

Этот документ содержит расширение протокола RIP (Routing Information Protocol), описанного в работе [1], – новый вариант протокола позволяет передавать больше информации в сообщениях RIP и повышает уровень безопасности.

Дополнением к данному документу является определение объектов SNMP MIB для протокола RIP-2 [2]. Кроме того, в работе [3] рассмотрены вопросы криптографической защиты для протокола RIP-2 [3].

Благодарности

Автор благодарит членов рабочей группы IETF RIP за помощь в разработке протокола RIP-2. Значительные фрагменты обсуждения протоколов на базе вектора расстояния и некоторых других вопросов работы протокола RIP были заимствованы из работы [1] (C. Hedrick). Некоторые части окончательного варианта документа были написаны Скоттом Брэднером (Scott Bradner).

Оглавление

Исключено из версии HTML

1. Обоснование

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

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

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

2. Текущий вариант RIP

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

В протоколе RIP-1 не рассматриваются автономные системы и взаимодействие IGP/EGP, подсети (subnetting) [11] и аутентификация, поскольку все это было реализовано после создания RIP-1. Отсутствие масок подсетей является особенно серьезной проблемой для маршрутизаторов, поскольку они используют маски подсетей для определения маршрутов. Если маршрут RIP-1 направлен в сеть (все биты адреса, кроме номера сети, имеют значение 0), маска сети эквивалентна маске подсети. Однако если некоторые биты сверх номера сети имеют значение 1, маршрутизатор уже не может определить маску подсети. Более того, маршрутизатор не может отличить маршруты RIP-1 к хостам и подсетям. Некоторые маршрутизаторы в таких случаях для определения типа маршрута просто используют маску интерфейса, через который была получена информация о маршруте.

3. Базовый протокол

3.1 Введение

RIP представляет собой протокол маршрутизации на основе алгоритма Bellman-Ford (или вектора расстояния — distance vector). Этот алгоритм используется для расчета маршрутов в компьютерных сетях с первых дней существования сети ARPANET1. Форматы пакетов и описание протокола, приведенные здесь, базируются на программе routed из дистрибутива Berkeley Unix.

В международных сетях типа Internet может использоваться множество разных протоколов маршрутизации. Сеть, скорее, следует рассматривать как множество автономных систем (AS), каждая из которых, в общем случае, администрируется как единое целое. В каждой AS будет использоваться своя технология маршрутизации, которая может отличаться в разных AS. Протокол маршрутизации, используемый в AS, называют внутренним протоколом маршрутизации IGP (Interior Gateway Protocol). Отдельный протокол, называемый протоколом внешней маршрутизации EGP (Exterior Gateway Protocol), служит для обмена маршрутной информации между AS. Протокол RIP был разработан в качестве IGP для автономных систем средних размеров. Этот протокол не предназначен для работы в более сложных средах. Информацию о рабочем контексте RIP-1 можно найти в работе Брадена и Постела [6].

RIP использует один из алгоритмов маршрутизации, известный как алгоритм Distance Vector (вектор расстояния или DV). Первое описание этого класса алгоритмов содержится в работе Форда и Фулкерсона [8], поэтому иногда используют термин «алгоритм Форда-Фулкерсона». Используется также термин «алгоритм Беллмана-Форда», отражающий факт использования в алгоритме расчетов на основе уравнения Беллмана [4]. Описание алгоритма в данном документе основано на работе [5]. Настоящий документ содержит спецификацию протокола. Математические основы алгоритмов маршрутизации описаны в работе [1]. Базовый алгоритм, используемый протоколом, применялся еще в 1969 году в сети ARPANET. Однако основные корни данного протокола находятся в сетевых протоколах Xerox. Для обмена маршрутной информацией используются протоколы PUP [7]. Несколько измененная версия этого протокола была адаптирована для XNS (Xerox Network Systems) под названием Routing Information Protocol [9]. Berkeley routed, по сути, представляет собой Routing Information Protocol, в котором адреса XNS заменены более общим форматом, способным работать с IPv4 и другими типами адресов, а обновления маршрутизации передаются каждые 30 секунд. В силу этого сходства термин Routing Information Protocol (или просто RIP) используется для протоколов, применяемых как XNS, так и routed.

Протокол RIP предназначен для использования в IP-сетях. Сеть Internet организована как множество сетей, соединенных между собой через специальные шлюзы (gateway), называемые маршрутизаторами (router). Сети могут строиться на базе соединений точка-точка или использовать более сложные структуры типа Ethernet или token ring. Хосты и маршрутизаторы обмениваются дейтаграммами, содержащими IP-адрес получателя. Маршрутизация представляет собой метод, на основе которого хост или маршрутизатор принимает решение «куда переслать дейтаграмму». Возможна передача дейтаграммы непосредственно в сеть адресата, если этот адресат находится в одной из сетей, непосредственно подключенных к хосту или маршрутизатору. Однако более интересны случаи, когда адресат недоступен напрямую.

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

3.2 Ограничения протокола

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

  • Использование протокола ограничено сетями, где самый длинный путь (диаметр сети) не превышает 15 хопов (интервал между двумя маршрутизаторами). Разработчики протокола не предполагали его использование в более крупных сетях. Отметим, что это ограничение основано на допущении стоимости каждого маршрута, равной 1 (обычно для RIP используют именно такие значения). Если администратор сети задаст большие значения стоимости, ограничение числа хопов станет еще более жестким.
  • Работа протокола зависит от «вычисления бесконечности» (counting to infinity) для разрешения нештатных ситуаций (эта особенность будет рассмотрена ниже). Если в систему входит несколько сотен сетей и в маршрутизации имеются петли, «разрешение» этих петель потребует дополнительного времени (если ограничена частота обновления маршрутов) или полосы (если обновления передаются по факту их обнаружения). Пока такие петли не будут обнаружены и устранены, они будут поглощать значительную часть полосы сети. Будем надеяться, что в реальных сетях это не создаст дополнительных сложностей (за исключением случаев использования низкоскоростных каналов). Более того, эта проблема возникает достаточно редко, поскольку для ее предотвращения приняты специальные меры.
  • Протокол использует «фиксированную» метрику для сравнения альтернативных маршрутов. Такое решение не подходит для систем, где выбор маршрута должен основываться на параметрах, измеряемых в реальном масштабе времени (задержка, надежность доставки, степень загрузки). Простое добавление учета таких параметров приводит к нестабильности, с которой протокол не может работать.

3.3. Структура документа

Основная часть документа состоит из 2 разделов:

  • рассмотрение концепций алгоритмов DV в целом;
  • описание реального протокола.

Каждый из этих разделов также делится на фрагменты. В параграфе 3.4 делается попытка неформального представления математической базы алгоритма. Отметим, что это представление следует «спиральному» методу – сначала описывается простейший вариант алгоритма, а потом последовательно добавляется рассмотрение новых возможностей. В параграфе 3.5 дано описание реального протокола. За исключением некоторых специфических аспектов, указанных в параграфе 3.4, реализация протокола RIP полностью основана на приведенной в параграфе 3.5 спецификации.

3.4 Алгоритмы Distance Vector

Задачей маршрутизации является поиск пути между отправителем и получателем. В модели Internet это сводится к определению цепочки маршрутизаторов между сетями отправителя и получателя. Пока сообщение или дейтаграмма остается в пределах одной сети или подсети, все вопросы пересылки определяются используемой в сети технологией. Например, сети Ethernet и ARPANET определяют по-своему способ обмена пакетами между отправителем и получателем. IP-маршрутизация начинается с того момента, когда требуется доставка сообщений от отправителя в одной сети к получателю в другой сети. В таких случаях сообщение может проходить через один или несколько маршрутизаторов, соединяющих сети между собой. Если сети отправителя и получателя не являются соседними, сообщение может проходить через несколько промежуточных (intervening) сетей и подключенных к ним маршрутизаторов. После того, как сообщение попадет в маршрутизатор сети получателя, снова используется локальная сетевая технология для доставки сообщения адресату.

В этом параграфе термин «сеть» используется, прежде всего, для обозначения доменов широковещания (например, сеть Ethernet), каналов «точка-точка» или сети ARPANET. Важно понимать, что сеть в таком случае трактуется протоколом IP как единый объект – т.е., решений о пересылке принимать не требуется или они принимаются прозрачным для IP способом, что позволяет протоколу IP трактовать такую сеть как связную систему (например, Ethernet или ARPANET). Отметим, что при обсуждении адресации IP допускается использование термина «сеть» в иных трактовках (в тех случаях, когда слово «сеть» относится к подсетям при рассмотрении вопросов адресации подсетей).

Существует множество вариантов поиска маршрутов между сетями. Весьма полезно классифицировать эти способы по информации, которой должны обмениваться между собой маршрутизаторы для обеспечения возможности писка пути. Алгоритмы DV основаны на обмене очень незначительным объемом информации. Предполагается, что каждый объект (маршрутизатор или хост), участвующий в обмене информацией, хранит сведения обо всех получателях в системе. В общем случае информация обо всех подключенных к одной сети объектах собирается в единую запись (entry), которая описывает маршрут ко всем получателям в данной сети. Такое обобщение становится возможным потому, что для IP маршрутизация внутри сети невидима (отсутствует). Каждая запись в базе данных о маршрутах включает следующий маршрутизатор, которому должны передаваться дейтаграммы, адресованные объекту. Кроме того, запись включает «метрику» — параметр, определяющий общую протяженность маршрута до объекта. Протяженность маршрута является в значительной мере условным понятием и может учитывать такие параметры, как задержка, стоимость услуг по передаче трафика и т. п. Алгоритмы DV (distance vector – вектор расстояния) получили свое название потому, что в них можно рассчитать оптимальный маршрут, обмениваясь только данными о «протяженности». Более того, обмен информацией ведется только между соседними объектами, т. е., объектами, подключенными к одной сети.

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

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

  • адрес: в IP-реализациях этого алгоритма хранится IP-адрес хоста или сети;
  • маршрутизатор: первый маршрутизатор на пути к получателю;
  • интерфейс: физический интерфейс, используемый для связи с первым маршрутизатором;
  • метрика: число, показывающее «удаленность» получателя;
  • таймер: время, прошедшее с момента последнего обновления записи.

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

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

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

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

Формально объект j может получить информацию непосредственно от объекта i (минуя процесс передачи через другие маршрутизаторы по пути), т. е. стоимость d(i,j), связанную с интервалом между i и j. В нормальном случае, когда все объекты данной сети рассматриваются как единое целое, значение d(i,j) будет одинаково для всех получателей данной сети и представляет стоимость использования этой сети. Для получения метрики полного маршрута просто складываются стоимости всех интервалов на пути доставки для данного маршрута. В рамках данного документа мы будем предполагать, что стоимость выражается целыми положительными значениями.

Пусть D(i,j) представляет метрику лучшего маршрута от объекта i к объекту j. Эта метрика должна быть определена для каждой пары объектов. d(i,j) представляет стоимость отдельных шагов. Предположим (формально), что d(i,j) представляет стоимость прямой доставки от i к j. Эта стоимость будет бесконечной, если i и j не являются прямыми соседями3. Поскольку стоимость является аддитивной, легко показать, что лучшая метрика должна описываться выражением

D(i,i) = 0,
D(i,j) = min [d(i,k) + D(k,j)]

и лучший маршрут от i следует к соседу k, для которого d(i,k) + D(k,j) имеет минимальное значение4. Отметим, что второе уравнение относится к узлу k, являющемуся непосредственным соседом i. Для других случаев значение d(i,k) бесконечно и никогда не может давать минимума.

Из приведенного доказательства очевидно, что можно построить простой алгоритм расчета стоимости для любого маршрута. Объект i запрашивает у своего соседа k его оценку расстояний до адресата и после этого к каждому из полученных значений просто добавляется d(i,k) – стоимость доставки между i и k. После этого i может сравнить значения, полученные от всех соседей и определить самый «дешевый» путь.

В работе [2] доказана сходимость этого алгоритма к корректному значению D(i,j) за конечное время при отсутствии изменений в топологии. Авторы сделали лишь незначительные допущения о том, в каком порядке в котором объекты передают друг другу свою информацию и когда следует проводить новый расчет минимального значения. В общем случае объект не должен прекращать передачу обновлений и расчет метрики, а сети не могут задерживать сообщения навсегда (крах маршрутизации является изменением топологии сети). В доказательстве не делается каких-либо предположений о начальном значении D(i,j), кроме того, что оно предполагается неотрицательным. Использование в доказательстве лишь незначительных допущений весьма важно. Поскольку мы не можем сделать разумных предположений о том, когда следует передавать обновления, опасно запускать алгоритм в асинхронном режиме. В этом случае каждый объект будет рассылать обновления по своим часам. В результате обновления могут отбрасываться сетью, пока не будут отброшены полностью. Поскольку мы не можем сделать предположений о стартовых условиях, алгоритм может принять изменения. Когда система изменяется, алгоритм маршрутизации начинает переход к новому равновесному состоянию, используя старое состояние как стартовое. Важно, чтобы алгоритм сходился за конечное время независимо от стартового состояния. С другой стороны, некоторые изменения могут привести к невозможности сходимости.

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

Существует еще одно отличие между описанным выше алгоритмом и его реализациями в протоколах типа RIP – в теоретическом варианте каждый объект включает запись для самого себя (с нулевой дистанцией). На практике не возникает необходимости в такой записи – стоимости доставки всем объектам сети выражаются единственной записью для данной сети. Рассмотрим ситуацию, когда хост или маршрутизатор G подключен к сети A. C представляет стоимость использования сети A (обычно эта метрика имеет значение 1). Напомним, что мы предполагаем «невидимость» внутренней структуры сети для IP, таким образом, стоимость доставки будет одинаковой для всех объектов внутри сети. В принципе, узел G должен получить сообщение от каждого объекта H сети A, показывающее нулевую стоимость доставки внутри сети. Тогда G будет считать C + 0 расстоянием до H. Вместо того чтобы просматривать множество идентичных сообщений, узел G просто включает в таблицу одну запись для сети A, содержащую метрику C. Эта запись для сети A должна трактоваться как «квинтэссенция» записей для всех узлов сети A. Единственная информация, которая не может быть включена в суммарную запись для сети A, это сведения о самом объекте G, поскольку стоимость доставки из G в G равна 0, а не C. Но, поскольку такие записи с нулевой стоимостью реально не используются, можно обойтись одной записью для всей сети A. В виду того, что записи с нулевой стоимостью реально не используются, хосты, не выполняющие функций маршрутизации, не должны передавать никаких обновлений таблиц. Очевидно, что хосты, не выполняющие функций маршрутизации (т.е., подключенные к единственной сети) не имеют какой-либо полезной информации для передачи другим хостам, за исключением тривиальной записи D(i,i) = 0. Поскольку такие хосты используют единственный сетевой интерфейс, легко видеть, что маршрут в любую другую сеть через такой хост будет приводить на тот же интерфейс (т. е., назад). В результате стоимость такого маршрута не может быть меньше минимальной стоимости C. Поскольку нет нужды в сохранении записей с нулевой стоимостью, хосты, не являющиеся маршрутизаторами, просто не должны участвовать в работе протокола маршрутизации.

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

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

Выше был описан алгоритм DV (вектор расстояния). Отметим, что это не является описанием самого протокола RIP, поскольку последний содержит ряд дополнений к базовому алгоритму. Каждый объект, принимающий участие в работе протокола7, должен выполнять перечисленные ниже процедуры.

  • Поддержка таблицы с записью для каждого возможного получателя в системе. Запись содержит сведения о «расстоянии» до адресата D и первом маршрутизаторе (G) на пути к адресату. Концептуально должна также включаться запись о «маршруте к себе» с нулевой метрикой, но на практике такие записи не используются.
  • Периодическая рассылка каждому соседу сообщений об изменении маршрутов. Такое обновление представляет собой набор сообщений, содержащих всю информацию из маршрутной таблицы. Обновление содержит запись для каждого адресата с указанием дистанции до него.
  • Когда приходит обновление от соседа G’, в него добавляется стоимость для сети, связанной с G’ (это должна быть сеть, через которую принято обновление). После этого вычисляется результирующая дистанция D’ и проводится сравнение с записями текущей таблицы маршрутизации. Если новая дистанция D’ для адресата N меньше существующего значения D, принимается новый маршрут. Т. е. в запись для адресата N будет включать дистанцию D’ и маршрутизатор G’. Если маршрутизатор G’ является тем, с которого начинается существующий маршрут (т. е., G’ = G), новая метрика D’ должна включаться в таблицу даже в тех случаях, когда она превышает старую.

3.4.1 Работа с изменениями топологии

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

Теоретический вариант алгоритма использует информацию от всех ближайших соседей. При изменении топологии меняется и набор соседей. В результате такого изменения при последующем расчете эти изменения будут учтены. Однако, как было отмечено выше, в реальных приложениях используется вариант минимизации с учетом возрастания (incremental version of the minimization), при которой запоминается только лучший маршрут. Если маршрутизатор, включенный в этот маршрут «падает», или разрывается сетевое соединение, расчет может не отразить таких изменений. В реальных приложениях алгоритм зависит от способа, используемого маршрутизатором для передачи уведомлений об изменении топологии. Если маршрутизатор прекращает работать, у него уже нет возможности уведомить своих соседей об изменении топологии.

Для решения этой проблемы протоколы на основе алгоритмов DV должны использовать понятие тайм-аута для маршрутизаторов. Детали реализации зависят от конкретного протокола. Например, в протоколе RIP каждый участвующий маршрутизатор передает обновления всем своим соседям каждые 30 секунд. Предположим, что текущий путь в сеть N использует маршрутизатор G. Если мы не получаем сообщений от G в течение 180, мы можем предположить что маршрутизатор не работает или разорвано соединение с ним. В результате маршрут помечается как некорректный. Когда от другого соседа приходит информация о корректном маршруте в сеть N, этот маршрут указывается взамен некорректного. Отметим, что для объявления маршрута некорректным мы ждали в течение 180 секунд, тогда, как маршрутизаторы рассылают обновления каждые 30 секунд. Это сделано для того, чтобы избавиться от ложных тайм-аутов в результате потери пакетов при констатации тайм-аута в результате отсутствия одного сообщения.

Как было показано выше, полезно иметь способ уведомления соседей об отсутствии маршрута в ту или иную сеть. RIP (как и некоторые другие протоколы этого класса) делает это возможным за счет периодической рассылки обновлений. Для индикации недоступности сети используется специальное значение метрики (16 в текущей реализации протокола RIP). Это значение обычно трактуется как «бесконечность», поскольку оно превышает все остальные значения метрики. Может показаться, что число 16 слишком мало для таких целей. Выбор этого числа в значительной мере определялся простотой работы с ним – число 16 в двоичном выражении удобно использовать как битовый флаг для проверки корректности маршрута.

3.4.2 Предотвращение нестабильности

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

Математическую сторону алгоритма достаточно просто расширить для обработки ставших недоступными маршрутов. Предложенные выше соглашения позволяют это сделать, просто указав достаточно большое значение метрики для недоступных сетей. Это значение должно превышать любую реально используемую метрику. В нашем примере мы выбрали значение 16 в качестве метрики для недоступных сетей. Предположим, что сеть перестала быть доступной. Все соседние с ней маршрутизаторы перестанут видеть сеть и по истечении тайм-аута установят для нее метрику 16. Для нашего анализа мы можем предположить, что все соседние маршрутизаторы получили прямое соединение с исчезнувшей сетью и эти соединения характеризуются метрикой 16. Поскольку с исчезнувшей сетью имеется только одно соединение, все остальные маршрутизаторы в системе будут сходиться к новым маршрутам, проходящим через один из соседних с исчезнувшей сетью маршрутизаторов. Легко видеть, что после схождения расчета все соседние маршрутизаторы получат для исчезнувшей сети метрику не меньше 16. Маршрутизаторы, следующие за ближайшими соседями (1 хоп), получат метрику не менее 17, следующие за ними – не менее 18 и т. д. Поскольку все эти значения превышают максимум, для метрики будет установлено значение 16. Обычно системы будут сходиться на значении 16 в качестве метрики для пропавшей сети.

К несчастью, вопрос о времени схождения расчетов не столь прост. Прежде, чем пойти дальше, рассмотрим пример из работы [2]. Отметим, что приведенный пример не может реально произойти в системах с корректной реализацией RIP – мы просто попытаемся показать необходимость некоторых функций. На приведенном рисунке буквы обозначают маршрутизаторы, а линии — сети.

A-----B
 \   / \
  \ /  |
   C  / все сети имеют стоимость 1,
   | / за исключением прямого соединения между C и D,
   |/ стоимость которого равна 10
   D
   |<=== сеть получателя

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

D: прямое подключение с метрикой 1
B: маршрут через D, метрика 2
C: маршрут через B, метрика 3
A: маршрут через B, метрика 3

Предположим, что рвется канал связи между B и D. Маршруты в этом случае должны быть на использование канала между C и D. К несчастью, на такое переключение потребуется время. Изменение маршрутизации начнется после того, как маршрутизатор B обнаружит невозможность использования D. Для простоты будем предполагать, что все маршрутизаторы передают обновления одновременно. Ниже показана метрика для сети получателя с точки зрения каждого маршрутизатора.

время ------>
D: dir, 1  dir, 1 dir, 1 dir, 1 ... dir, 1 dir, 1
B: unreach C,   4 C,   5 C,   6     C,  11 C,  12
C: B, 3    A,   4 A,   5 A,   6     A, 11 D,   11
A: B, 3    C,   4 C,   5 C,   6     C, 11 C,   12
dir = прямое соединение
unreach = сеть недоступна

Здесь возникает проблема – маршрутизатор B может получить информацию о «падении» маршрута с использованием тайм-аута, но достаточно еще долго будет предполагать наличие маршрута в системе. Изначально, маршрутизаторы A и C продолжают думать, что они могут связаться с D по пути через B. Поэтому они будут передавать обновления, содержащие метрику 3. На следующем этапе B будет заявлять, что возможен доступ к D через A или C (естественно, это не так). Маршруты, заявляемые A и C, уже не существуют, но узнать об этом невозможно. И даже после обнаружения недоступности маршрутов через B каждый из маршрутизаторов A и C будет думать о доступности пути через другой маршрутизатор. В конце концов, будут найдены правильные маршруты, но это займет некоторое время. Самая плохая ситуация возникает в тех случаях, когда сеть становится полностью недоступной из какой-то части системы. В таких случаях метрика медленно увеличивается, пока не будет вычислена недоступность. Такие ситуации называются «вычислением бесконечности» (counting to infinity).

Из сказанного можно понять, почему для «бесконечной» метрики выбрано столь малое значение. Если сеть становится полностью недоступной, мы хотим обнаружить недоступность как можно скорей. Значение метрики для недоступной сети должно быть больше метрики любого реального маршрута, но ничто не требует увеличивать его дополнительно. Таким образом, выбор метрики для недоступной сети определяется компромиссом между размером сети и скоростью «вычисления бесконечности». Разработчики протокола RIP предполагали неочевидным практическое использование протокола в сетях, диаметр которых превышает 15.

Для предотвращения проблем, подобных описанной, существует несколько способов. Применительно к RIP — это расщепление горизонта с анонсированием недоступности обратного пути (split horizon with poisoned reverse) и обновления по триггеру (triggered updates).

3.4.3 Split horizon – расщепление горизонта

Отметим, что некоторые из описанных выше проблем вызваны тем, что A и C занимаются обманом друг друга. Каждый из этих маршрутизаторов сообщает о доступности D через другой маршрутизатор. Это можно предотвратить за счет более аккуратного отношения к передаваемой информации. В частности, нет никакой пользы от заявлений о доступности сети получателя для соседей, от которых был получен данный маршрут. Расщепление горизонта (Split horizon) представляет собой схему предотвращения проблем, вызываемых включением маршрута в обновления, передаваемые маршрутизатору, от которого была получена информация об этом маршруте. Простая схема расщепления горизонта (simple split horizon) опускает маршруты, полученные от соседа при передаче обновлений этому соседу. Схема «Split horizon with poisoned reverse» включает такие маршруты в обновления, но устанавливает для них бесконечную метрику (анонсирование недоступности обратного маршрута).

Если маршрутизатор A полагает, что он может связаться с D через узел C, его сообщения маршрутизатору C должны показывать недоступность узла D. Если маршрут через C реален, это говорит о том, что C имеет прямое соединение с D или соединение осуществляется через како-то иной маршрутизатор. Маршрут через C не может возвращаться в A, поскольку это будет порождать петлю. Говоря маршрутизатору C о недоступности D, маршрутизатор A просто пытается предотвратить возможное заблуждение C о доступности маршрута через A. Описанная ситуация достаточно типична для соединений «точка-точка». Рассмотрим теперь ситуацию, когда узлы A и C подключены к широковещательной сети (например, Ethernet) и присутствуют другие маршруты в эту сеть. Если узел A имеет маршрут через C, он должен показывать недоступность D при обмене информацией с любым другим маршрутизатором той же сети. Другие маршрутизаторы в сети могут непосредственно взаимодействовать с C и никогда не будут обращаться к C через узел A. Если лучший маршрут для A реально проходит через C, другим маршрутизаторам той же сети не нужно знать, что узел A имеет доступ к D. Это означает, что обновления, используемые для C, могут передаваться всем остальным маршрутизаторам в той же сети. Таким образом, обновления можно рассылать в широковещательном режиме.

В общем случае использование режима split horizon with poisoned reverse более безопасно по сравнению с простым вариантом split horizon. Если два маршрутизатора имеют указывающие друг на друга маршруты, анонсирование обратных маршрутов с метрикой 16 будет незамедлительно разрывать петли. Если обратные маршруты просто не анонсировать, для ошибочных маршрутов придется ждать тайм-аута. Однако вариант с анонсированием недоступности обратного маршрута (poisoned reverse) имеет недостаток – увеличивается размер маршрутных сообщений. Рассмотрим кампусную магистраль, соединенную со множеством зданий. В каждом здании имеется подключенный к магистрали маршрутизатор, связанный с ЛВС здания. Рассмотрим обновления, которые маршрутизаторы в широковещательном режиме рассылают через магистраль. Все, что требуется знать остальной части сети о каждом маршрутизаторе – это локальная сеть, с которой он соединен. При использовании простого расщепления горизонта в обновлениях будут появляться только те маршруты, которые маршрутизатор передает в магистральную сеть. Если использовать более сложный вариант расщепления горизонта (split horizon with poisoned reverse) маршрутизатор должен упомянуть все полученные из магистрали маршруты с метрикой 16. Если система достаточно велика, размер обновлений существенно возрастает и большинство записей в обновлениях показывают недоступность сетей.

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

Требования к маршрутизаторам, приведенные в работе [11], указывают, что все реализации RIP должны использовать расщепление горизонта и рекомендуется использовать split horizon with poisoned reverse, с возможностью отказа от этого режима.

3.4.4 Обновления по событию — Triggered updates

Расщепление горизонта с анонсированием недоступности обратного пути (Split horizon with poisoned reverse) будет предотвращать возникновение петель между парой маршрутизаторов. Однако возможны ситуации, когда в процесс «взаимообмана» вовлечены три маршрутизатора. Например, маршрутизатор A может предполагать наличие маршрута через B, B через C, а C через A. Расщепление горизонта не может предотвратить возникновение таких петель. Для разрешения этой проблемы метрика должна сойтись к бесконечности и соответствующая сеть должна быть объявлена недоступной. Обновления по событию (triggered update) являются попыткой ускорить процесс схождения метрики. Для использования triggered update просто добавляется правило, по которому маршрутизатор, меняя метрику для пути, должен передать уведомление об этом, не дожидаясь времени штатной передачи обновления. Промежуток времени, по истечении которого должно передаваться такое уведомление, зависит от протокола. Некоторые протоколы на базе алгоритмов DV (в частности, RIP) требуют передавать обновление с небольшой задержкой, чтобы избежать значительного роста сетевого трафика. Рассмотрим, как это правило взаимодействует с правилами расчета новой метрики. Предположим, что путь от маршрутизатора в сеть N проходит через маршрутизатор G. Если обновление приходит непосредственно от G, принявший его маршрутизатор должен доверять полученной информации независимо от знака изменения метрики. Если в результате метрика изменяется, принявший обновление маршрутизатор будет передавать в связи с этим событием обновления (triggered updates) всем хостам и маршрутизаторам, непосредственно подключенным к нему. Каждый из получивших обновление узлов может передать его своим соседям. В результате возникает каскад обновлений. Легко увидеть, какие хосту и маршрутизаторы будут вовлечены в этот каскад. Предположим, что маршрутизатор G фиксирует тайм-аут для доступа в сеть N. В результате этого события G будет передавать обновления всем своим соседям. Однако доверятся этому обновлению только те маршрутизаторы, чьи маршруты в сеть N проходят через G. Остальные маршрутизаторы и хосты увидят эту информацию о новом маршруте, который они уже используют, и просто проигнорируют обновление. Соседи, чьи маршруты проходят через G обновят свою метрику и отправят triggered update всем своим соседям. И снова эти обновления будут восприняты только теми маршрутизаторами, для которых путь в сеть N проходит через G. Таким образом, обновления по событию обратно по всем путям, полученным от маршрутизатора G, устанавливая для этого пути бесконечную метрику. Распространение обновлений прекратится как только они попадут в ту часть сети, откуда путь в N идет через другие маршрутизаторы.

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

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

В требованиях к маршрутизаторам [11] сказано, что все реализации RIP должны поддерживать обновления по событию для удаленных маршрутов и могут также поддерживать такие обновления для новых или измененных маршрутов. Реализации RIP должны также ограничивать скорость, с которой могут передаваться обновления по событиям (см. параграф 3.10.1).

3.5 Спецификация протокола

Протокол RIP предназначен для обмена информацией, позволяющей рассчитать маршруты через сети на базе IPv4. Предполагается, что любой маршрутизатор, использующий RIP, имеет интерфейсы в одну или несколько [внешних] сетей (в противном случае, это устройство не является маршрутизатором). Будем называть такие сети подключенными напрямую (directly-connected). Протокол основан на доступе к некоторой информации о каждой из таких сетей. Наиболее важной информацией является метрика. RIP-метрика сети выражается целыми числами от 1 до 15, включительно. Ограничения значений метрики не являются частью данной спецификации. Обычно для метрики используется значение 1. Разработчики должны давать администраторам возможность устанавливать метрику для каждой сети. В дополнение к метрике каждая сеть будет иметь связанный с ней адрес [получателя] IPv4 и маску подсети. Эти параметры устанавливаются администратором сети, независимо от данной спецификации.

Предполагается, что любой хост, использующий RIP, имеет интерфейс в одну или несколько сетей, которые называются подключенными напрямую (directly-connected). Протокол опирается на некую информацию о каждой из таких сетей. Наиболее важным параметром является метрика или «стоимость». Метрика сети выражается целым числом от 1 до 15, включительно. Ограничения значений метрики не являются частью данной спецификации. Многие существующие реализации хостов используют метрику 1. В новых разработках администратору должна предоставляться возможность установки метрики для каждой сети. В дополнение к стоимости с каждой сетью связан номер сети IPv4 и маска подсети. Эти значения устанавливаются администратором независимо от данной спецификации.

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

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

  • адрес IPv4 для получателя;
  • метрика, которая представляет общую стоимость доставки дейтаграммы от маршрутизатора к адресату (эта метрика представляет собой сумму стоимостей, связанных с каждой сетью на пути к адресату);
  • адрес IPv4 для следующего маршрутизатора на пути к адресату (next hop); если адресат находится в подключенной напрямую сети, этот параметр не требуется;
  • флаг, показывающий, что информация о маршруте была недавно изменена – его называют флагом изменения маршрута (route change flag);
  • различные таймеры, связанные с маршрутом (см. параграф 3.6).

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

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

Разработчики могут также предоставить администратору возможность ввода дополнительных маршрутов. Скорей всего, это будут маршруты к хостам или сетям за пределами видимости системы маршрутизации. Такие маршруты называют статическими (static route). Записи для адресатов сверх тех, которые указаны изначально, добавляются и удаляются с использованием описанных ниже алгоритмов.

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

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

Работа протокола RIP основана на транспортном протоколе UDP. Каждый маршрутизатор, использующий протокол RIP, включает в себя процесс маршрутизации, который передает и принимает дейтаграммы UDP через порт 520, выделенный для протоколов RIP-1/RIP-2. Весь обмен данными с процессами RIP на других маршрутизаторах осуществляется через порт RIP и через этот же порт передаются все обновления RIP. Незапрошенные анонсы обновления маршрутов передаются с использованием порта RIP у отправителя и получателя. Обновления, передаваемые по запросу, отправляются с использованием того же порта, в который был адресован запрос. Некоторые специфические запросы могут передаваться с использованием портов, отличных от RIP, но они должны быть направлены в порт RIP адресата.

Формат пакетов RIP показан на рисунке8:

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  command (1)  |  version (1)  |       должно быть 0 (2)       |
+---------------+---------------+-------------------------------+
|                                                               |
~                        Запись RIP (20)                        ~
|                                                               |
+---------------+---------------+---------------+---------------+

Количество записей RIP может меняться от 1 до 25 (включительно). Записи RIP-1 имеют формат:

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| address family identifier (2) |      должно быть 0 (2)        |
+-------------------------------+-------------------------------+
|                          адрес IPv4 (4)                       |
+---------------------------------------------------------------+
|                       должно быть 0 (4)                       |
+---------------------------------------------------------------+
|                       должно быть 0 (4)                       |
+---------------------------------------------------------------+
|                           metric (4)                          |
+---------------------------------------------------------------+

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

Каждое сообщение содержит заголовок RIP, включающий идентификатор команды и номер версии. В данном параграфе рассматриваются заголовки для первой версии протокола, а заголовки новой версии описаны в параграфе 4. Поле команды показывает цель данного сообщения и может принимать два значения:

1 – запрос (request) на получение таблицы маршрутизации или ее части;

2 – отклик (response), содержащий запрошенную таблицу маршрутизации или ее часть; это сообщение может передано в ответ на запрос или как незапрошенное (unsolicited) обновление таблицы маршрутизации.

Для каждого типа сообщений протокола версии 1 оставшаяся часть дейтаграммы содержит список маршрутных записей (Route Entry или RTE). Каждая RTE-запись в этом списке содержит идентификатор семейства адресов (Address Family Identifier или AFI), адрес получателя (IPv4) и стоимость доставки (метрику).

Поле AFI указывает тип адреса и для RIP-1 может принимать единственное значение AF_INET = 2.

Поле метрики может содержать значения от 1 до 15 (включительно), показывающие «стоимость» доставки информации адресату, или значение 16 (бесконечность), говорящее о недоступности адресата.

3.7 Адресация

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

В формате RIP-1 типы адресов не различаются и поле адреса может содержать:

адрес хоста, номер подсети, номер сети или 0 (принятый по умолчанию маршрут)

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

Когда узел оценивает информацию, полученную с помощью RIP-1, интерпретация адреса зависит от наличия информации о применимой маске подсети. Если маска известна, можно определить смысл адреса. Возьмем для примера сеть 128.6 и маску 255.255.255.0. В этом случае 128.6.0.0 будет номером сети, 128.6.4.0 – номером подсети, а 128.6.4.1 – адресом хоста. Однако при отсутствии маски оценка адреса может быть неоднозначной. Если связанная с узлом часть отлична от нуля, не существует способа отличить номер подсети от адреса хоста. Поскольку номер подсети без маски ценности не представляет, в таких ситуациях предполагается, что адрес относится к хосту. Чтобы избавиться от неоднозначностей такого сорта при использовании протокола версии 1, узлы не должны передавать маршруты в подсети тем узлам, про которые нельзя с уверенностью предположить, что им известна маска подсети. Следовательно, при отсутствии специальных мер маршруты в подсети не должны передаваться за пределы сети, частью которой является данная подсеть. Протокол RIP-2 (см. параграф 4) избавляет от неоднозначностей хост/подсеть путем включения маски подсети в маршрутную запись.

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

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

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

Специальный адрес 0.0.0.0 используется для обозначения принятого по умолчанию маршрута. Этот маршрут используется в тех случаях, когда неудобно включать каждую подходящую сеть в обновления RIP и когда один или несколько близко расположенных маршрутизаторов в системе подготовлены для обслуживания трафика в сети, которые не указаны явно. Эти маршрутизаторы должны создавать записи RIP для адреса 0.0.0.0, как будто это непосредственно подключенная сеть. Способ, который используется для создания таких записей, могут выбирать разработчики. В общем случае администратору сети предоставляется возможность указать, какой маршрутизатор должен создать запись для 0.0.0.0, однако возможны и другие механизмы. Например, разработчики могут решить, что любой маршрутизатор, использующий BGP, должен декларироваться как используемый по умолчанию. Такой подход может быть полезен, поскольку позволяет администратору выбрать метрику для использования в подобных записях. Если существует несколько принятых по умолчанию маршрутизаторов, можно задать для них предпочтения. Записи для 0.0.0.0 обрабатываются протоколом RIP точно так же, как это происходило бы для реальной сети с таким адресом. Администратор должен принять меры против распространения маршрутов в сеть 0.0.0.0 дальше, чем следует. В общем случае каждая автономная система имеет свой предпочтительный маршрут для использования по умолчанию. Таким образом, маршруты, включающие 0.0.0.0, в общем случае не должны пересекать границ автономной системы. Реализация этого требования не рассматривается в данном документе.

3.8 Таймеры

В этом параграфе рассматриваются все события, активизируемые по таймеру.

Каждые 30 секунд процесс RIP активизируется для передачи незапрашиваемых откликов (Response), содержащих полную таблицу маршрутизации (см. параграф 3.4.3, расщепление горизонта), каждому из соседних маршрутизаторов. При наличии в сети большого числа маршрутизаторов существует тенденция синхронизировать их между собой для одновременной передачи обновлений. Это может произойти в результате воздействия загрузки системы на отсчет 30-секундных интервалов для передачи периодических обновлений. Синхронизация обновлений нежелательна, поскольку она может приводить к многочисленным коллизиям в широковещательных сетях. Следовательно, разработчики должны принять меры предосторожности:

  • отсчет 30-секундных интервалов должен вестись по часам, на которые не влияет уровень загрузки системы и время обработки предыдущего обновления;
  • 30-секундный интервал изменяется на незначительную величину (+/- 0 — 5 сек) всякий раз при установке таймера9.

С каждым маршрутом связаны два таймера – timeout (тайм-аут) и garbage-collection (сборка мусора). По истечении тайм-аута маршрут считается недоступным, однако он сохраняется в таблице еще некоторое время, чтобы соседи могли быть уведомлены о недоступности маршрута. При наступлении времени сборки мусора маршрут удаляется из таблицы маршрутизации.

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

Удаление маршрута может произойти в двух случаях – по тайм-ауту и в результате установки для метрики значения 16 на основании обновлений, принятый от текущего маршрутизатора (см. обсуждение вопроса обработки обновлений от других маршрутизаторов в параграфе 3.7.2). В обоих случаях выполняются следующие действия:

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

Пока не наступит время сборки мусора (garbage-collection timer), маршрут продолжает включаться во все передаваемые маршрутизатором обновления. По истечении времени (120 сек.) маршрут окончательно удаляется из таблицы.

Если в процессе ожидания времени сбора мусора взамен утраченного организован новый маршрут в ту же сеть, таймер garbage-collection сбрасывается.

Для обновления по событиям используется отдельный таймер, описанный в параграфе 3.9.1.

3.9 Обработка входящей информации

В этом параграфе рассматривается обработка дейтаграмм, принимаемых портом RIP. Процесс обработки зависит от значения поля команды в дейтаграммах. Зависимость процесса обработки от номера версии описана в параграфах 4.6 и 5.1.

3.9.1 Запросы

Запросы (Request) используются для получения от маршрутизатора сообщений, содержащих таблицу маршрутизации или ее часть. Обычно запросы передаются в широковещательном режиме (групповая адресация RIP-2) через порт RIP маршрутизаторами, которые недавно инициализированы и хотят как можно быстрее заполнить свою таблицу маршрутизации. Однако могут возникать ситуации (например, мониторинг маршрутизатора) когда требуется получить таблицу от единственного маршрутизатора. В таких случаях запрос адресуется напрямую нужному маршрутизатору через порт UDP, отличный от порта RIP. При получении такого запроса маршрутизатор отправляет ответ с использованием адреса и номера порта из принятого запроса.

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

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

3.9.2 Отклики

Получение откликов (Response) может быть вызвано несколькими причинами:

  • переданный ранее запрос;
  • периодическое обновление (unsolicited response – незапрашиваемый отклик);
  • обновление по событию (в результате изменения маршрута).

Обработка откликов не зависит от вызвавшей их причины.

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

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

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

  • корректность адреса получателя;
  • корректность значения метрики (от 1 до 16, включительно)

Если запись не проходи какую-либо из проверок, она должна игнорироваться с переходом к проверке следующей записи. Хорошим тоном является запись в журнал фактов игнорирования записей.

После завершения проверки записи обновляется значение метрики путем добавления стоимости сети, из которой принято обновление. Если результирующая метрика превышает бесконечное значение, устанавливается метрика 16:

metric = MIN (metric + cost, infinity)

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

  • установку для адреса получателя одноименного значения из RTE;
  • установку в поле метрики полученного в результате расчета значения;
  • установку в поле next hop (следующий маршрутизатор) адреса маршрутизатора, от которого получено обновление;
  • инициализацию отсчета тайм-аута (если уже включен таймер сбора мусора, он останавливается, как описано в параграфе 3.6);
  • установку флага изменения маршрута;
  • активизацию процесса для инициирования обновления (см. параграф 3.8.1)

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

  • в таблицу вносятся изменения (т. е., корректируется метрика и при необходимости изменяется поле next hop);
  • Устанавливается флаг изменения маршрута и активизируется процесс инициирования обновления;
  • Если новая метрика бесконечна, активизируется процесс удаления записи, описанный выше, в остальных случаях сбрасывается отсчет тайм-аута.

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

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

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

3.10 Обработка исходящей информации

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

  • получение запроса (Request), как описано в параграфе 3.7.1;
  • регулярное обновление (рассылается с использованием групповых или широковещательных адресов каждые 30 секунд);
  • обновление по событию (рассылка изменений с использованием группового или широковещательного адреса).

Когда отклик (Response) посылается всем соседям (периодическое обновление или обновление по событию), сообщение адресуется удаленному маршрутизатору для каждого соединения «точка-точка» или передается в широковещательном режиме (групповая адресация в RIP-2) во все подключенные сети, поддерживающие широковещание. Таким образом, один отклик подготавливается для каждой подключенной напрямую сети и передается по соответствующему адресу (прямая адресация или широковещательный/групповой адрес). В большинстве случаев этого достаточно для доставки отклика всем соседним маршрутизаторам. Однако в некоторых ситуациях могут потребоваться дополнительные действия. В числе адресатов могут оказаться сети, не поддерживающие широковещания (например, the ARPANET) или «тупые» (dumb) маршрутизаторы. В таких случаях может потребоваться указание списка соседних маршрутизаторов и явная адресация дейтаграмм каждому из них. Разработчики должны сами определять необходимость использования такого механизма и способ указания списка соседних маршрутизаторов.

3.10.1 Обновления по событию — Triggered Updates

Обновления по событию (Triggered update) требуют специальной обработки по двум причинам. Во-первых, опыт показывает, что такие обновления могут приводить к перегрузке сетей с низкоскоростными каналами или большим числом маршрутизаторов. Следовательно, разработчики должны принимать меры по ограничению частоты обновлений по событию. После передачи такого обновления требуется установить таймер на случайный промежуток времени в диапазоне от 1 до 5 секунд. Если до истечения этого времени произойдут события, которые должны инициировать дополнительные обновления по событию, передается единственное обновление по истечении заданного времени и таймер снова устанавливается для отсчета случайного времени от 1 до 5 секунд. Обновления по событиям не должны передаваться, если наступило время генерации периодического обновления.

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

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

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

3.10.2 Генерация откликов

В этом параграфе описана генерация отклика для отдельной сети с прямым подключением:

  • установка номера версии 1 или 2 (механизм выбора номера версии зависит от конкретной реализации, однако в откликах на запрос номер версии должен совпадать с номером версии в запросе);
  • установка значения Response (отклик) в поле команды;
  • установка нулевого значения для следующего поля;
  • заполнение записей RTE (число записей в отклике не должно превышать 25 – если реально требуется передать большее число записей, следует генерировать несколько обновлений).

При заполнении полей RTE проверяется каждый маршрут в таблице. Если генерируется обновление по событию, следует включать только записи с установленным флагом изменения маршрута. Если после обработки Split Horizon маршрут не следует включать в обновление, опустите его. Если маршрут включается в обновление, значения метрики и адреса получателя должны быть скопированы в RTE. Маршруты с бесконечной метрикой также должны включаться в дейтаграммы.

4. Расширения протокола

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

В сообщениях RIP-1 и RIP-2 используются заголовки одного формата (см. параграф 3.4). Формат 20-октетных записей RTE для RIP-2 показан ниже:

    0                   1                   2                   3 3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Address Family Identifier (2) |        Route Tag (2)          |
   +-------------------------------+-------------------------------+
   |                         IP Address (4)                        |
   +---------------------------------------------------------------+
   |                         Subnet Mask (4)                       |
   +---------------------------------------------------------------+
   |                         Next Hop (4)                          |
   +---------------------------------------------------------------+
   |                         Metric (4)                            |
   +---------------------------------------------------------------+

Поля идентификатора семейства адресов (Address Family Identifier), IP-адреса и метрики описаны в параграфе 3.4. Поле версии должно содержать значение 2 для сообщений RIP, использующих аутентификацию или содержащих информацию в полях, которые не были определены для версии 1.

4.1 Аутентификация

Поскольку функции аутентификации должны выполняться на уровне каждого сообщения, а в заголовке сообщения имеется лишь два свободных октета, тогда как для любой схемы аутентификации требуется больший объем сведений, система аутентификации протокола RIP версии 2 использует для хранения информации записи RIP. Если идентификатор семейства адресов (Address Family Identifier) первого (и только первого) элемента в сообщении имеет значение 0xFFFF, оставшаяся часть сообщения содержит сведения для аутентификации. Это означает, что для аутентификации может использоваться до 24 записей 24 RIP в оставшейся части сообщения. Если аутентификация не используется, поле идентификатора семейства адресов не должно принимать значение 0xFFFF. Сообщения RIP с использованием аутентификации будут иметь следующий формат:

    0                   1                   2                   3 3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | Command (1)   | Version (1)   |            unused             |
   +---------------+---------------+-------------------------------+
   |             0xFFFF            |    Authentication Type (2)    |
   +-------------------------------+-------------------------------+
   ~                       Authentication (16)                     ~
   +---------------------------------------------------------------+

В настоящее время поддерживается только один тип аутентификации – простой пароль – и для его обозначения в поле типа устанавливается значение 2. Оставшиеся 16 октетов могут содержать пароль в виде строки текста (plain text password). Если пароль содержит менее 16 октетов, он должен дополняться соответствующим количеством нулей (0x00) справа.

4.2 Тег маршрута

Поле тега маршрута (Route Tag или RT) является атрибутом маршрута, который должен сохраняться и анонсироваться вместе с маршрутом. Поле RT позволяет отличать «внутренние» RIP-маршруты (маршруты для сетей внутри области RIP-маршрутизации) от «внешних», которые импортируются от EGP или других IGP.

Для маршрутизаторов, поддерживающих отличные от RIP протоколы, должна обеспечиваться возможность настройки RT для маршрутов, импортируемых из других источников. Например, маршруты, импортируемые от EGP или BGP, должны обеспечивать возможность установки для них произвольного значения тега маршрута RT или (по крайней мере) номера автономной системы (AS), из которой был получен маршрут.

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

4.3 Маска подсети

Поле Subnet Mask содержит маску подсети, которая применяется к IP-адресу для того, чтобы выделить из него номер сети (подсети). Если запись не включает маску подсети, поле должно иметь нулевое значение.

Для интерфейсов, где маршрутизатор RIP-1 может принимать и обрабатывать информацию RIP-2, действуют следующие правила:

  1. внутренняя информация одной сети никогда не должна анонсироваться в другие сети;
  2. информация о специфической подсети может не анонсироваться, если маршрутизаторы RIP-1 будут воспринимать это как путь к хосту;
  3. supernet-маршруты (маршруты, в которых маска подсети содержит меньше битов, нежели «естественная маска сети) не должны анонсироваться, если существует возможность их некорректной интерпретации маршрутизаторами RIP-1.

4.4 Следующий маршрутизатор

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

Поле Next Hop позволяет избавиться от лишней пересылки пакетов в системе. Особенно полезна такая возможность в тех случаях, когда протокол RIP поддерживается не всеми маршрутизаторами в сети. Простой пример приведен в Приложении A. Отметим, что поле Next Hop является «информационным» (advisory), т. е., его можно игнорировать (это может привести к снижению производительности, но маршрутизация будет работать нормально). Если адрес, казанный в поле Next Hop недоступен напрямую, значение поля должно трактоваться как 0.0.0.0.

4.5 Групповая адресация

Для снижения избыточной нагрузки на хосты, которые не слушают сообщений RIP-2, при передаче периодических обновлений может использоваться групповой адрес IP 224.0.0.9. Отметим, что IGMP не требуется, поскольку эти сообщения передаются между маршрутизаторами и не требуют дальнейшей пересылки.

В сетях NBMA должна использоваться конкретная (unicast) адресация. Однако отклики, переданные с использованием группового адреса RIP-2, должны восприниматься.

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

4.6 Запросы

Если маршрутизатор RIP-2 принимает запрос RIP-1, он должен возвращать отклик в формате RIP-1. Если передача откликов поддерживается только для формата RIP-2, запросы RIP-1 должны игнорироваться.

5. Совместимость

В первой версии протокола [1] предусмотрены некоторые возможности обработки номера версии. Спецификация говорит, что сообщения RIP с номером версии 0 должны отбрасываться, а сообщения версии 1 отбрасываются только при ненулевом значении любого из полей MBZ (Must Be Zero – должно быть нулевым). Для сообщений RIP с номером версии, превышающим не должны отбрасываться лишь потому, что имеют ненулевое значение в поле MBZ. Это означает, что новая версия RIP полностью совместима с существующими реализациями RIP, которые соответствуют этой части спецификации.

5.1 Ключ совместимости (Compatibility Switch)

Включение ключа совместимости обусловлено двумя причинами. Во-первых, существуют реализации протокола RIP-1, в которых поля сообщений отличаются от спецификации [1]. Во-вторых, использование групповой адресации будет предохранять системы RIP-1 от получения обновлений RIP-2 (это может быть весьма желательно для некоторых случаев). Ключ совместимости должен устанавливаться независимо для каждого интерфейса.

Ключ совместимости может принимать 4 значения:

  • RIP-1 – передаются только сообщения RIP-1;
  • RIP-1 compatibility – сообщения RIP-2 являются широковещательными;
  • RIP-2 – сообщения RIP-2 используют групповую адресацию;
  • None – запрет передачи сообщений RIP.

Рекомендуется использовать для ключа совместимости значения RIP-1 или RIP-2, но не RIP-1 compatibility, поскольку последнее значение может вызывать проблемы для некоторых вариантов топологии. Значение RIP-1 compatibility следует использовать только в тех случаях, когда все последствия такого применения осознаны сетевым администратором.

Для полноты маршрутизаторы также должны поддерживать ключ управления приемом, который будет определять, какие сообщения воспринимаются – только RIP-1, только RIP-2, оба типа или никакие. Это ключ также должен устанавливаться независимо для каждого интерфейса. Рекомендуется устанавливать используемые по умолчанию значения ключа совместимыми с используемым форматом передачи обновлений.

5.2 Аутентификация

Ниже описан алгоритм, который должен использоваться для аутентификации сообщений RIP. Если в маршрутизаторе отключена аутентификация сообщений RIP-2, должны восприниматься сообщения RIP-1 и сообщения RIP-2 без аутентификации, а сообщения RIP-2 с аутентификацией должны отбрасываться. Если аутентификация сообщений RIP-2 на маршрутизаторе включена, должны восприниматься сообщения RIP-1 и сообщения RIP-2 после проверки аутентификации. Сообщения RIP-2 без аутентификации или не прошедшие проверку должны отбрасываться. В целях обеспечения максимальной безопасности сообщения RIP-1 следует игнорировать при использовании аутентификации (см. параграф 4.1), поскольку в противном случае сообщения с аутентификацией (пароль) будут передаваться маршрутизаторами RIP-1 без аутентификации.

Поскольку сообщения с аутентификацией помечаются значением идентификатора семейства адресов 0xFFFF, системы RIP-1 будут игнорировать такие записи (в первой версии поддерживается только семейство адресов IP). Следует отметить, однако, что использование аутентификации не запрещает системам RIP-1 видеть сообщения RIP-2. Если нужно, такую недоступность можно организовать путем использования групповой адресации (см. параграфы 4.5 и 5.1).

5.3 Увеличение «бесконечности»

Говоря о совместимости, нельзя не упомянуть, что часто приходится слышать запросы увеличения «бесконечной метрики» (16). Основной причиной отказа от такого увеличения является необходимость обеспечения обратной совместимости. Большее значение бесконечной метрики будет приводить к неоднозначности трактовки поля метрики старыми системами RIP. В лучшем случае маршруты с метрикой больше 16 будут игнорироваться. Были также предложения сделать поле метрики 1-октетным, а три старших октета использовать для других целей – такой вариант будет несовместим с реализациями, трактующими поле метрики как 4-октетное значение.

5.4 Безадресные соединения

Как и RIP-1, протокол RIP-2 не поддерживает безадресные соединения.

6. Взаимодействие между версиями 1 и 2

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

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

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

7. Вопросы безопасности

Базовый вариант протокола RIP не обеспечивает безопасности. При переходе к RIP-2 и более современным протоколам маршрутизации обеспечиваются дополнительные возможности аутентификации, описанные в параграфах 4.1 и 5.2. Дополнительные меры безопасности описаны в работе [3].

Приложение A

Показанный на рисунке простой пример служит иллюстрацией использования поля next hop в маршрутной записи.

      -----   -----   -----           -----   -----   -----
      |IR1|   |IR2|   |IR3|           |XR1|   |XR2|   |XR3|
      --+--   --+--   --+--           --+--   --+--   --+--
        |       |       |               |       |       |
      --+-------+-------+---------------+-------+-------+--
        <-------------RIP-2------------->

 

Предположим, что маршрутизаторы IR1, IR2 и IR3 являются «внутренними» и для них обеспечивается единое администрирование (например, кампусная сеть) с использованием протокола RIP-2 в качестве IGP. Маршрутизаторы XR1, XR2 и XR3, с другой стороны, относятся к сфере другого администратора (например, региональная сеть, в которую входит кампус) и работают с другим протоколом маршрутизации (например, OSPF). XR1, XR2 и XR3 обмениваются маршрутной информацией между собой и знают, что лучшие маршруты в сети N1 и N2 проходят через XR1, в сети N3, N4, N5 – через XR2, а в сети N6 и N7 — через XR3. При корректной установке поля Next Hop (XR2 для сетей N3/N4/N5, XR3 для N6/N7) только маршрутизатору XR1 потребуется обмен сообщениями RIP-2 с IR1/IR2/IR3 для того, чтобы при маршрутизации не использовалось лишнего интервала через XR1. Если Next Hop не используется (например, при работе на базе RIP-1) маршрутизаторам XR2 и XR3 также потребуются сообщения RIP-2 для предотвращения избыточных пересылок.

Литература

[1] Hedrick, C., «Routing Information Protocol», STD 3410, RFC 1058, Rutgers University, June 1988.

[2] Malkin, G., F. Baker, «RIP Version 2 MIB Extension», RFC 138911, January 1993.

[3] Baker, F., R. Atkinson, «RIP-II MD5 Authentication», RFC 2082, January 1997.

[4] Bellman, R. E., «Dynamic Programming», Princeton University Press, Princeton, N.J., 1957.

[5] Bertsekas, D. P., Gallaher, R. G., «Data Networks», Prentice-Hall, Englewood Cliffs, N.J., 1987.

[6] Braden, R., Postel, J., «Requirements for Internet Gateways», STD 4, RFC 1009, June 1987.

[7] Boggs, D. R., Shoch, J. F., Taft, E. A., Metcalfe, R. M., «Pup: An Internetwork Architecture», IEEE Transactions on Communications, April 1980.

[8] Ford, L. R. Jr., Fulkerson, D. R., «Flows in Networks», Princeton University Press, Princeton, N.J., 1962.

[9] Xerox Corp., «Internet Transport Protocols», Xerox System Integration Standard XSIS 028112, December 1981.

[10] Floyd, S., V. Jacobson, «The synchronization of Periodic Routing Messages,» ACM Sigcom ’93 symposium, September 1993.

[11] Baker, F., «Requirements for IP Version 4 Routers.» RFC 1812, June 1995.

Адрес автора

Gary Scott Malkin

Bay Networks

8 Federal Street

Billerica, MA 01821

Phone: (978) 916-4237

E-mail: gmalkin@baynetworks.com


Перевод на русский язык

Николай Малых

nmalykh@gmail.com

Полное заявление авторских прав

Copyright (C) The Internet Society (1998). All Rights Reserved.

This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.

The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an «AS IS» basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

1 Прообраз сети Internet. Прим. перев.

2 Отметим, что в некоторых реализациях могут существовать различия между хостами и сетями (см. параграф 3.2).

3 Отметим, что стоимость d(i, i) имеет нулевое значение (в оригинале ошибочно сказано «бесконечное» — прим. перев.), т. е., мы не учитываем здесь прямую передачу узла самому себе.

4 Это можно строго доказать с использованием метода математической индукции.

5 Если несколько маршрутов имеют одинаковую стоимость, маршрутизатор будет относиться к одному из таких путей.

6 Отметим, что рассмотрение построено на предположении о статическом характере системы и не учитывает возможности «падения».

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

8 В скобках указано число октетов (байтов) в каждом поле. Прим. перев.

9 Недавние исследования [10] показали допустимость и больших вариаций периода рассылки обновлений.

10 В настоящее время этот документ не имеет статуса стандарта (см. STD 1). Прим. перев.

11 В настоящее время этот документ утратил силу и заменен RFC 1724. Прим. перев.




RFC 2410 The NULL Encryption Algorithm and Its Use With IPsec

Network Working Group                                       R. Glenn
Request for Comments: 2410                                      NIST
Category: Standards Track                                    S. Kent
                                                            BBN Corp
                                                       November 1998

Пустой алгоритм шифрования (NULL) и его использование в IPsec

The NULL Encryption Algorithm and Its Use With IPsec

PDF

Статус документа

В этом документе содержится проект стандарта Internet для сообщества Internet и запрос на обсуждение в целях развития и совершенствования. Текущее состояние стандартизации и статус протокола можно узнать из документа «Internet Official Protocol Standards» (STD 1). Документ может распространяться без ограничений.

Авторские права

Copyright (C) The Internet Society (1998). All Rights Reserved.

Тезисы

В данном документе определен пустой алгоритм шифрования NULL и его использование с IPsec ESP1. Алгоритм NULL никак не меняет полученных для «шифрования» данных. Фактически, NULL, как таковой, просто не делает ничего. NULL обеспечивает для ESP возможность реализации услуг идентификации и контроля целостности без шифрования данных.

Информация о других компонентах, требуемых для реализации ESP, приведена в документах [ESP] и [ROAD].

1. Введение

В этом документе определен алгоритм шифрования NULL и его использование с IPsec ESP [ESP] для обеспечения услуг идентификации и контроля целостности без сохранения конфиденциальности.

NULL является блочным механизмом шифрования, истоки которого теряются в античности. Несмотря на слухи о том, что NSA2 препятствует публикации этого алгоритма, неочевидно, что это дело их рук. Недавние археологические раскопки показывают, что алгоритм NULL был разработан во времена Римской империи в качестве экспортного варианта шифров Цезаря (Ceaser). Однако, по причине отсутствия 0 в римских цифрах документальные записи алгоритма были утеряны для истории на два тысячелетия.

[ESP] задает использование необязательного алгоритма шифрования для обеспечения конфиденциальности, а также необязательных алгоритмов для идентификации и проверки целостности. Алгоритм шифрования NULL является удобным способом реализации опции «без шифрования». В документе [DOI] такой вариант обозначен, как ESP_NULL.

Спецификация заголовка идентификации IPsec [AH] предоставляет похожий сервис, обеспечиваемый расчетом идентификационных данных, покрывающих поля данных пакета, а также не изменяемые при передаче поля заголовка IP. ESP_NULL не включает заголовок IP в расчет идентификационных данных. Это может быть полезно при организации услуг IPsec через сеть устройств, работающих не по протоколу IP. Обсуждение использования ESP_NULL в отличных от IP сетях выходит за пределы настоящего документа.

В данном документе алгоритм NULL используется в контексте ESP. Дополнительную информацию о совместном использовании компонент ESP для предоставления услуг по защите можно найти в работах [ESP] и [ROAD].

Ключевые слова необходимо (MUST), недопустимо (MUST NOT), требуется (REQUIRED), нужно (SHALL), не следует (SHALL NOT), следует (SHOULD), не нужно (SHOULD NOT), рекомендуется (RECOMMENDED), возможно (MAY), необязательно (OPTIONAL) в данном документе интерпретируются в соответствии с RFC 2119 [RFC 2119].

2. Определение алгоритма

Алгоритм NULL математически определяется функцией идентичности (I3) применяемой к блоку данных b:

NULL(b) = I(b) = b

2.1 Ключи

Подобно другим современным шифрам (например, RC5 [RFC-2040]), алгоритм шифрования NULL может использовать ключи различного размера. Однако повышения уровня защиты по мере увеличения длины ключа не происходит.

2.2 Криптографическая синхронизация

Поскольку природа алгоритма NULL не требует поддержки данных о состоянии, ему не требуется предавать IV4 или иные данные криптографической синхронизации в каждом пакете (или для каждой SA). Алгоритм шифрования NULL объединяет в себе лучшие характеристики блочных и потоковых шифров, не требуя передачи IV или аналогичных данных криптографической синхронизации.

2.3 Заполнение

NULL использует блоки размером 1 байт, позволяющие обойтись без заполнения.

2.4. Производительность

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

2.5 Тестовые векторы

Ниже приведен набор тестовых векторов для упрощения разработки интероперабельных реализаций алгоритма NULL.

test_case = 1
data = 0x123456789abcdef
data_len = 8
NULL_data = 0x123456789abcdef

test_case = 2
data = "Network Security People Have A Strange Sense Of Humor"6
data_len = 53
NULL_data = "Network Security People Have A Strange Sense Of Humor"

3. Операционные требования ESP_NULL

ESP_NULL определяется использованием алгоритма NULL в контексте ESP. В этом параграфе уточняется определение ESP_NULL путем указания требований к рабочим параметрам.

Для механизма обмена ключами IKE7 [IKE] размер ключа для этого алгоритма должен иметь нулевое (0) значение в целях обеспечения интероперабельности и предотвращения всех возможных проблем при экспортном контроле.

Для обеспечения интероперабельности размер IV для данного алгоритма должен быть равным 0 битов.

В исходящих пакетах может использоваться заполнение в соответствии со спецификацией [ESP].

4. Вопросы безопасности

Алгоритм шифрования NULL не обеспечивает конфиденциальности и не предоставляет никаких других услуг защиты. Он просто является удобным вариантом представления опционального использования шифрования в ESP. В таком случае ESP можно использовать для обеспечения идентификации и контроля целостности без конфиденциальности. В отличие от AH эти средства защиты не применяются ко всем частям заголовка IP. На момент подготовки этого документа не было очевидного понимания, что использование ESP_NULL в чем-либо менее безопасно по сравнению с AH при выборе одного алгоритма идентификации (т. е., пакет, защищенный с помощью ESP_NULL при использовании некого алгоритма идентификации криптографически защищен точно так же, как пакет с использованием AH и того же алгоритма идентификации).

Как указано в [ESP], использование алгоритмов шифрования и идентификации в ESP является необязательным, но для каждой ESP SA должно задаваться использование по крайней мере одного криптографически стойкого алгоритма шифрования или одного криптографически стойкого алгоритма идентификации (или по одному алгоритму каждого типа).

На момент подготовки этого документа не было известно законодательных ограничений на экспорт алгоритма NULL с ключами размером 0 битов.

5. Права интеллектуальной собственности

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

6. Благодарности

Steve Bellovin предложил и подготовил текст для параграфа о паравах интеллектуальной собственности.

Следует также отметить участников семинара по интероперабельности Cisco/ICSA IPsec & IKE в марте 1998, поскольку документ обязан им своим появлением на свет.

7. Литература

[ESP] Kent, S., and R. Atkinson, «IP Encapsulating Security Payload», RFC 24068, November 1998.

[AH] Kent, S., and R. Atkinson, «IP Authentication Header», RFC 24029, November 1998.

[ROAD] Thayer, R., Doraswamy, N., and R. Glenn, «IP Security Document Roadmap», RFC 2411, November 1998.

[DOI] Piper, D., «The Internet IP Security Domain of Interpretation for ISAKMP», RFC 2408, November 1998.

[IKE] Harkins, D., and D. Carrel, «The Internet Key Exchange (IKE)», RFC 2409, November 1998.

[RFC-2026] Bradner, S., «The Internet Standards Process — Revision 3», BCP 9, RFC 2026, October 1996.

[RFC-2040] Baldwin, R., and R. Rivest, «The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms», RFC 2040, October 1996

[RFC-2119] Bradner, S., «Key words for use in RFCs to Indicate Requirement Levels», BCP 14, RFC 2119, March 1997.

6. Адреса редакторов

Rob Glenn

NIST

EMail: rob.glenn@nist.gov
Stephen Kent

BBN Corporation

EMail: kent@bbn.com

 

С рабочей группой IPsec можно связаться через ее председателей:

Robert Moskowitz

ICSA

EMail: rgm@icsa.net

 

Ted T’so

Massachusetts Institute of Technology

EMail: tytso@mit.edu


Перевод на русский язык

Николай Малых

nmalykh@gmail.com

7. Полное заявление авторских прав

Copyright (C) The Internet Society (1998). All Rights Reserved.

This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.

The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an «AS IS» basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

1Encapsulating Security Payload — защищенные инкапсулированные данные.

2National Security Agency — Агентство национальной безопасности США.

3Identity — идентичность.

4Initialization Vector – вектор инициализации. Прим. перев.

5Операционной системы. Прим. перев.

6У специалистов по сетевой безопасности специфическое чувство юмора.

7Internet Key Exchange – обмен ключами в сети Internet. Прим. перев.

8Документ утратил силу и заменен RFC 4303 и RFC 4305, перевод которых имеется на сайте www.protocols.ru. Прим. перев.

9Документ утратил силу и заменен RFC 4301, перевод которого имеется на сайте www.protocols.ru. Прим. перев.




RFC 2439 BGP Route Flap Damping

Network Working Group                                       C. Villamizar
Request for Comments: 2439                                            ANS
Category: Standards Track                                      R. Chandra
                                                                    Cisco
                                                              R. Govindan
                                                                      ISI
                                                            November 1998

 

Демпфирование осцилляций маршрутов BGP

BGP Route Flap Damping

PDF

Статус документа

В этом документе содержится спецификация протокола, предложенного сообществу Internet. Документ служит приглашением к дискуссии в целях развития и совершенствования протокола. Текущее состояние стандартизации протокола вы можете узнать из документа Internet Official Protocol Standards (STD 1). Документ может распространяться без ограничений.

Авторские права

Copyright (C) The Internet Society (1998). All Rights Reserved.

Тезисы

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

Основными целями являются:

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

При этом должны приниматься во внимание другие задачи протокола BGP:

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

Избыточная скорость обновления анонсов доступности для подмножества префиксов Internet часто встречается в сети Internet. Это было отмечено еще в начале 1990 годов многими людьми, вовлеченными поддержку работы Internet. Для обозначения этого эффекта используется неформальный термин route flap. Описанный здесь метод в настоящее время широко распространен и обычно обозначается термином route flap damping1.

1 Обзор

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

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

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

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

2 Методы ограничения маршрутных анонсов

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

Возможно и желательно использовать комбинации обоих методов. На практике таймеры с фиксированным значением устанавливаются на очень короткое время и полезны для упаковки маршрутов в меньшее число обновлений для тех случаев. Когда маршруты приходят в виде отдельных обновлений. Протокол BGP называет это упаковкой NLRI2 [5].

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

2.1 Рекомендации по установке фиксированных значений для таймеров

BGP-3 не включает конкретных рекомендаций по этому вопросу [1]. Короткая глава Frequency of Route Selection3 просто рекомендует что-нибудь делать и содержит рассуждения общего плана о желательных и нежелательных свойствах.

BGP4 сохраняет главу Frequency of Route Advertisement4 и добавляет главу Frequency of Route Origination5. BGP-4 описывает метод ограничения частоты маршрутных анонсов, включающий таймеры с фиксированными значениями MinRouteAdvertisementInterval (задается в конфигурации) и MinASOriginationInterval [5]. Рекомендуемое значение для таймера MinRouteAdvertisementInterval составляет 30 секунд, для MinASOriginationInterval — 15 секунд.

2.2 Желаемые свойства алгоритмов демпфирования

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

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

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

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

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

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

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

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

2.3 Выбор алгоритма

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

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

f(f(figure-of-merit, t1), t2) = f(figure-of-merit, t1+t2)

Это свойство позволяет в один прием вычислить уменьшение значения за длительный период независимо от текущего значения уровня нестабильности (figure-of-merit). В целях оптимизации производительности уменьшение значений уровня нестабильности следует выполнять по истечении фиксированного интервала времени (периода). Зная время “полураспада”7, можно рассчитать с упреждением значение уровня нестабильности для следующего периода. Снижение уровня нестабильности за несколько периодов можно рассчитать по формуле:

f(figure-of-merit, n*t0) = f(figure-of-merit, t0)**n = K**n

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

3 Ограничение анонсирования маршрутов с использованием фиксированных таймеров

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

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

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

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

4 Демпфирование анонсов с учетом уровня стабильности

Этот метод ограничения маршрутных анонсов использует меру стабильности маршрутов независимо для каждого маршрута. Данный метод применяется в тех случаях, когда обновления приходят только от внешних партнеров (EBGP). Применение этого метода к маршрутам, полученным от IBGP, или к анонсам, передаваемым в IBGP или EBGP после выбора маршрута, может приводить к возникновению маршрутных петель.

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

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

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

4.1 Один или множество наборов параметров?

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

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

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

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

Хотя это и не играет важной роли, но может оказаться желательной возможность создания множества наборов конфигурационных параметров для маршрута. Желательной может быть и возможность настройки наборов параметров для некоторого множества маршрутов (определяемого AS path, партнером, адресатом или иными критериями). Опыт может определять требования к гибкости и способам выбора наилучшего набора параметров. Возможность использования различных наборов параметров демпфирования для разных маршрутов и поддержки множества значений уровня нестабильности (figure of merit) для маршрута определяется реализацией.

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

4.2 Параметры конфигурации

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

cutoff threshold (cut)

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

reuse threshold (reuse)

Нижний порог числа отзывов маршрута, используемый для восстановления анонсов демпфированного ранее маршрута (когда число отзывов станет ниже порогового уровня).

maximum hold down time (T-hold)

Максимальное время, на которое маршрут может быть демпфирован независимо от того, насколько он был нестабилен перед данным периодом стабильности.

decay half life while reachable (decay-ok)

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

decay half life while unreachable (decay-ng)

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

decay memory limit (Tmax-ok or Tmax-ng)

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

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

time granularity (delta-t)

Гранулярность времени (в секундах) при выполнении всех расчетов снижения уровня нестабильности.

reuse list time granularity (delta-reuse)

Интервал времени между оценками списков повторного использования (reuse list).

reuse list memory reuse-list-max

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

number of reuse lists (reuse-list-size)

Число списков повторного использования. Значение параметра может определяться на основе reuse-list-max или задаваться явно.

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

reuse index array size (reuse-index-array-size)

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

4.3 Рекомендации по установке параметров

Время снижения уровня нестабильности вдвое (decay half life) следует устанавливать существенно большим, чем период осцилляций, для которого используется этот параметр. Например, при установке для снижения уровня времени 10 минут для маршрута, который отзывается и заново анонсируется каждые 10 минут, осцилляции маршрута будут продолжаться, если для верхнего порога (cutoff) установлено значение 2 или выше.

  время    уровень нестабильности как функция времени (в минутах)
  0.00    0.000 .         0.000 .         0.000 .         0.000 .
  0.08    0.000 .         0.000 .         0.000 .         0.000 .
  0.16    0.000 .         0.000 .         0.000 .         0.973  .
  0.24    0.000 .         0.000 .         0.000 .         0.920  .
  0.32    0.000 .         0.000 .         0.946  .        1.817    .
  0.40    0.000 .         0.953  .        0.895  .        2.698     .
  0.48    0.000 .         0.901  .        0.847  .        2.552     .
  0.56    0.953  .        0.853  .        1.754    .      3.367      .
  0.64    0.901  .        0.807  .        1.659   .       4.172        .
  0.72    0.853  .        1.722    .      1.570   .       3.947        .
  0.80    0.807  .        1.629   .       2.444     .     4.317        .
  0.88    0.763  .        1.542   .       2.312     .     4.469        .
  0.96    0.722  .        1.458   .       2.188    .      4.228        .
  1.04    1.649   .       2.346     .     3.036      .    4.347        .
  1.12    1.560   .       2.219    .      2.872      .    4.112        .
  1.20    1.476   .       2.099    .      2.717     .     4.257        .
  1.28    1.396   .       1.986    .      3.543       .   4.377        .
  1.36    1.321   .       2.858      .    3.352      .    4.141        .
  1.44    1.250   .       2.704     .     3.171      .    4.287        .
  1.52    2.162    .      2.558     .     3.979        .  4.407        .
  1.60    2.045    .      2.420     .     3.765       .   4.170        .
  1.68    1.935    .      3.276      .    3.562       .   4.317        .
  1.76    1.830    .      3.099      .    4.356        .  4.438        .
  1.84    1.732    .      2.932      .    4.121        .  4.199        .
  1.92    1.638   .       2.774     .     3.899       .   3.972        .
  2.00    1.550   .       2.624     .     3.688       .   3.758       .
  2.08    1.466   .       2.483     .     3.489       .   3.555       .
  2.16    1.387   .       2.349     .     3.301      .    3.363      .
  2.24    1.312   .       2.222    .      3.123      .    3.182      .
  2.32    1.242   .       2.102    .      2.955      .    3.010      .
  2.40    1.175   .       1.989    .      2.795     .     2.848      .
  2.48    1.111  .        1.882    .      2.644     .     2.694     .
  2.56    1.051  .        1.780    .      2.502     .     2.549     .
  2.64    0.995  .        1.684   .       2.367     .     2.411     .
  2.72    0.941  .        1.593   .       2.239    .      2.281     .
  2.80    0.890  .        1.507   .       2.118    .      2.158    .
  2.88    0.842  .        1.426   .       2.004    .      2.042    .
  2.96    0.797  .        1.349   .       1.896    .      1.932    .
  3.04    0.754  .        1.276   .       1.794    .      1.828    .
  3.12    0.713  .        1.207   .       1.697    .      1.729    .
  3.20    0.675  .        1.142   .       1.605   .       1.636   .
  3.28    0.638  .        1.081  .        1.519   .       1.547   .
  3.36    0.604  .        1.022  .        1.437   .       1.464   .
  3.44    0.571  .        0.967  .        1.359   .       1.385   .

Рисунок 1: Нестабильность показателя качества при постоянной частоте осцилляций

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

Если базовый уровень пика зажат верхним ограничением, он просто будет достигать верхней границы быстрее при более высокой частоте осцилляций. Например, если переключение маршрута происходит 4 раза за период снижения уровня вдвое, наблюдается следующая последовательность значений. Когда маршрут становится недоступным первый раз, значение становится равным 1. При следующем переключении добавляется 1 к предыдущему значению, которое уменьшилось на корень четвертой степени из 2 (уменьшение уровня за ¼ периода “полураспада”, если снижение происходит по экспоненциальному закону). В результате будет получаться последовательность значений 1, 1.84, 2.55, 3.14, 3.64, 4.06, 4.42, 4.71, 4.96, 5.17, …, сходящаяся приблизительно к 6.285. Когда переключение происходит 4 раза за период снижения вдвое, уровень будет достигать 3 за 4 цикла, 4 – за 6, 5 – за 10 и сойдется к значению около 6.3. При двух переключениях за период снижения вдвое, уровень достигнет 3 за 7 циклов и сойдется при значении, меньшем 3.5.

На рисунке 1 показана стабильность показателя качества (уровня нестабильности) для постоянной скорости переключения маршрутов. По временной оси значения отложены в периодах снижения уровня нестабильности вдвое. Графики представляют переключение маршрутов с периодом 1/2, 1/3, ¼ и 1/8 от срока снижения уровня вдвое. Установлен верхний порог 4.5, который, как можно видеть на рисунке, оказывает влияние на три графика, эффективно ограничивая время, через которое произойдет реанонсирование маршрута независимо от предыстории. При пороговых уровнях cutoff и reuse 1,5 и 0,75, соответственно, маршруты будут подавляться после того, как будет декларирована из недоступность 2-3 раза и будут снова использоваться приблизительно через по истечении периода стабильности приблизительно в два срока снижения уровня нестабильности вдвое.

Эту функцию можно выразить формально. Доступность маршрута может быть представлена как переменная R с возможными значениями 0 (недоступен) и 1 (доступен). В любой момент времени R принимать только одно значение. Уровень нестабильности увеличивается на 1 при каждом переходе от R=1 к R=0 и зажат верхним ограничением (ceiling). Снижение уровня нестабильности может быть выражено через набор дискретных интервалов следующим образом:

figure-of-merit(t) = K * figure-of-merit(t - delta-t)
K = K1 для R=0, K=K2 для R=1
 время    уровень нестабильности как функция времени
                       (в минутах)
  0.00    0.000 .         0.000 .         0.000 .
  0.20    0.000 .         0.000 .         0.000 .
  0.40    0.000 .         0.000 .         0.000 .
  0.60    0.000 .         0.000 .         0.000 .
  0.80    0.000 .         0.000 .         0.000 .
  1.00    0.999  .        0.999  .        0.999  .
  1.20    0.971  .        0.971  .        0.929  .
  1.40    0.945  .        0.945  .        0.809  .
  1.60    0.919  .        0.865  .        0.704  .
  1.80    0.894  .        0.753  .        0.613  .
  2.00    1.812    .      1.657   .       1.535   .
  2.20    1.762    .      1.612   .       1.428   .
  2.40    1.714    .      1.568   .       1.244   .
  2.60    1.667   .       1.443   .       1.083  .
  2.80    1.622   .       1.256   .       0.942  .
  3.00    1.468   .       1.094  .        0.820  .
  3.20    2.400     .     2.036    .      1.694    .
  3.40    2.335     .     1.981    .      1.475   .
  3.60    2.271     .     1.823    .      1.284   .
  3.80    2.209    .      1.587   .       1.118  .
  4.00    1.999    .      1.381   .       0.973  .
  4.20    2.625     .     2.084    .      1.727    .
  4.40    2.285     .     1.815    .      1.503   .
  4.60    1.990    .      1.580   .       1.309   .
  4.80    1.732    .      1.375   .       1.139   .
  5.00    1.508   .       1.197   .       0.992  .
  5.20    1.313   .       1.042  .        0.864  .
  5.40    1.143   .       0.907  .        0.752  .
  5.60    0.995  .        0.790  .        0.654  .
  5.80    0.866  .        0.688  .        0.570  .
  6.00    0.754  .        0.599  .        0.496 .
  6.20    0.656  .        0.521 .         0.432 .
  6.40    0.571  .        0.454 .         0.376 .
  6.60    0.497 .         0.395 .         0.327 .
  6.80    0.433 .         0.344 .         0.285 .
  7.00    0.377 .         0.299 .         0.248 .
  7.20    0.328 .         0.261 .         0.216 .
  7.40    0.286 .         0.227 .         0.188 .
  7.60    0.249 .         0.197 .         0.164 .
  7.80    0.216 .         0.172 .         0.142 .
  8.00    0.188 .         0.150 .         0.124 .

Рисунок 2: Использование раздельных параметров снижения уровня нестабильности.

Четыре графика представлены вертикально. В силу ограниченного пространства показан ограниченный набор точек по временной оси. Значения уровня нестабильности показаны также в числовой форме. Разрешение по оси уровня нестабильности крайне низко по причине ограниченности изобразительных средств ASCII. График дает лишь грубое качественное представление роста и спада уровня нестабильности. Линии не показаны на графика в силу ограниченных возможностей текстового формата. По причине низкого разрешения на графиках пики и спады видны, но точные значения доступны лишь в виде чисел.

С момента максимального удержания (T-hold) может быть определено отношение значения reuse к верхнему порогу (ceiling). После этого может быть выбрано целое значение верхнего порога (ceiling) так, чтобы не возникало проблем переполнения и остальные значения могли быть подобающим образом масштабированы. Если заданы оба порога или установлено множество наборов параметров, будет использовано наибольшее значение верхнего порога.

На рисунке 2 показан эффект задания различных скоростей спада для периодов доступности и недоступности маршрута (в периоды недоступности скорость снижения устанавливалась в 5 раз меньше). На трех показанных графиках период осцилляций был равен времени снижения уровня нестабильности вдвое, а период доступности маршрута составлял 1/8, 1/2 и 7/8 от периода снижения уровня нестабильности вдвое. В последнем случае маршрут не подавлялся до того, как он стал недоступным в третий раз (когда уровень нестабильности превысил порог после того, как маршрут снова стал доступным).

Основным назначением рисунка 2 является демонстрация эффекта изменения рабочего цикла изменений переменной R при фиксированной частоте переключений. Если константы снижения уровня нестабильности выбраны так, что снижение происходит медленнее, когда R=0 (маршрут недоступен), уровень нестабильности растет более медленно (точнее, более медленно растет базовый уровень пиков), когда маршрут сохраняет доступность более долго. Эффект при восстановлении постоянной доступности маршрута может быть весьма незначительным, если величина пика зажата верхним порогом (ceiling), но он становится более значимым, если пик не достигает верхнего порога (ceiling). На рисунке 2, где нестабильность маршрута достаточно кратко-временна, верхний порог не достигается, следовательно, маршруты, которые доступны в течение большей части периода переключения маршрутов (route flap cycle) начинают снова использоваться (включаются в RIB и анонсируются партнерам) после восстановления стабильности (R становится равным 1, показывая, что маршрут стал доступным и сохраняет это состояние)быстрее, чем другие маршруты.

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

Целью демпфирования осцилляций маршрутов BGP является снижение нагрузки на процессоры промежуточного маршрутизатора и “нисходящих” (downstream) маршрутизаторов (BGP-партнеры и партнеры этих партнеров, которые будут видеть анонсы маршрутов от промежуточного маршрутизатора). Расчет уровня нестабильности для каждого дискретного интервала времени по формуле

figure-of-merit(t) = K * figure-of-merit(t - delta-t)

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

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

Списки повторного использования содержат маршруты, сгруппированные по времени ожидания возможности повторного использования. Периодически каждый список будет перемещаться на одну позицию вперед, а один список будет удаляться, как описано в параграфе 4.8.7. Все подавляемые маршруты из подлежащего удалению списка будут оцениваться заново и включаться в число используемых, либо помещаться в другой список в соответствии с дополнительным временем, которое должно пройти до того, как маршрут можно будет использовать снова. Последний список будет содержать все маршруты, которые не будут анонсироваться дольше, чем допустимо для остальных списков. Кода последний список будет перемещаться вперед, некоторые из содержащихся в нем маршрутов не будут готовые к повторному использованию и будут помещены в очередь снова. Временной интервал переоценки демпфированных маршрутов и число списков следует делать настраиваемыми. Разумными значениями для использования по умолчанию будут 30 секунд и 64 списка. Маршруты, остающиеся демпфированными более длительное время, следует оценивать заново каждые 32 минуты.

4.4 Рабочие (Run Time) структуры данных

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

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

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

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

4.4.1 Структуры данных для наборов конфигурационных параметров

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

    • Фактор масштабирования снижения уровня нестабильности (decay-array-scale-factor)
    • Значение порога cutoff (cut)
    • Значение параметра повторного использования (reuse)
    • Верхний порог уровня нестабильности (ceiling)

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

4.4.2 Структуры данных для массивов Decay и Reuse Index

Приведенные ниже значения также рассчитываются на основе конфигурационных параметров, но этот расчет не делается напрямую. Описание процедур расчета приведено в параграфе 4.5.

    • Скорость снижения уровня нестабильности (decay-delta-t)
    • Размер массива decay (decay-array-size)
    • Массив decay (decay[])
    • Размер массива индексов повторного использования (reuse-index-array-size)
    • Массив индексов повторного использования (reuse-index-array[])

Для каждой заданной скорости снижения уровня (decay rate) будет использоваться массив, в котором хранятся значения рассчитанных параметров, возводимых в степень, задаваемую индексом каждого элемента массива. Такой подход позволяет ускорить расчеты. Снижение уровня нестабильности за один период (decay rate per tick) является промежуточным значением, выражаемым действительным числом, и используется при расчете значений, хранящихся в массивах decay. Размер массива рассчитывается с учетом заданного в конфигурации предела распределения памяти для decay, заданного как размер массива или максимальное время удержания.

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

Массив индексов повторного использования (reuse index) используется с теми же целями, что и массивы decay. В BGP маршрут считается используемым, если он выбран как лучший (best route). В этом контексте используемые маршруты включают в RIB и выбирают для анонсирования партнерам BGP. Если маршрут отзывается (с помощью анонса BGP, показывающего недоступность данного маршрута), он больше не относится к числу используемых. После того, как доступность маршрута будет восстановлена, он может не сразу попасть в число используемых, если уровень нестабильности для него будет указывать на недавнюю нестабильность. После того, как маршрут достаточно долго будет сохранять стабильность и уровень нестабильности станет ниже порога повторного использования («reuse» threshhold), этот маршрут может начать использоваться снова (будет трактоваться как действительно доступный, помещен в RIB и передаваемые партнерам анонсы). Время, по истечение которого может начаться повторное использование маршрута, может определяться просмотром массива. Массив может создаваться на основе скорости снижения уровня нестабильности. Массив индексируется с использованием целочисленного коэффициента, пропорционального отношению уровня нестабильности к порогу начала повторного использования.

4.4.3 Состояние для каждого маршрута

Информация должна поддерживаться в форме некого «кортежа» (tuple), представляющего маршрут. В кортеже должна содержаться (как минимум) информация (префикс BGP и его размер). Возможно включение (исключение) различных атрибутов BGP в зависимости от ситуации. По умолчанию в кортеж следует включать также AS path. Опционально могут включаться и другие атрибуты BGP — такие, как MULTI_EXIT_DISCRIMINATOR (MED).

Представление маршрута в целях демпфирования осцилляций имеет вид:

Элемент По умолчанию Опционально
Префикс NLRI требуется
Размер NLRI требуется
AS path включен может быть исключен
Последний AS set в пути исключен может быть включен
next hop исключен может быть включен
MED исключен может быть включен (только для сравнения)

Атрибут AS path обычно включается для идентификации нестабильности в нисходящем направлении, которая не подавляется или ослабляется недостаточно и является чередованием стабильного и нестабильного пути. В редких случаях может оказаться желательным исключение AS path для всего или части набора префиксов. Если AS path заканчивается в AS set, на практике такой путь всегда является агрегируемым. Изменение «трейлерного» AS set следует игнорировать. В идеале сравнение AS должно давать по крайней мере одну AS, которая сохраняется в старом и новом AS set, но допускается и полное игнорирование содержимого «трейлерного» AS set.

Включение изменений hop и MED помогает подавить использование AS с внутренней нестабильностью и избежать интервалов next hop , которые ближе к нестабильному пути IGP в смежной AS. При использовании большого числа значений MED рост количества состояний может создать проблему. В силу этого обстоятельства MED не используется по умолчанию и включается лишь в качестве части сравнения «кортежей» с использованием одного элемента состояния независимо от значения MED. Включение MED будет подавлять использование смежной AS даже в тех случаях, когда изменения не распространяются дальше. Использование MED является единственно безопасной практикой для случаев, когда известно о существовании пути через другую AS или имеется достаточно партнерских со смежной AS сайтов и подавляться будут только маршруты для части партнеров.

4.4.4 Структуры данных для маршрута

Перечисленные ниже данные должны поддерживаться на уровне маршрутов. Маршрутом в данном случае считается кортеж, обычно содержащий NLRI, next hop и AS path, как определено в параграфе 4.4.3.

stability figure of merit (figure-of-merit) — стабильность добротности (добротность)

Каждый маршрут должен обеспечивать стабильность добротности для применимого набора параметров.

last time updated (time-update) — время последнего обновления (время обновления)

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

config block pointer — указатель конфигурационного блока

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

reuse list traversal pointers

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

4.5 Обработка конфигурационных параметров

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

Масштабирование обычно зависит от наибольшего значения, которого может достигнуть добротность (потолок). Реальное значение потолка обычно определяется приведенным ниже уравнением. Для потолка можно также указать конкретное значение, которое, в свою очередь, определяет T-hold.

ceiling = reuse * (exp(T-hold/decay-half-life) * log(2))

В этом уравнении параметр reuse указывает порог повторного использования, описанный в параграфе 4.2.

Методы масштабирования в целочисленной арифметике здесь не описываются детально. Приведены методы расчета действительных значений. Преобразование в целочисленные значения и детали масштабирования в целочисленной арифметике оставлены для отдельной работы.

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

penalty value and thresholds (как пропорционально масштабируемые целые числа)

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

decay rate per tick (decay[1])

Величина снижения за единицу приращения времени (определяется гранулярностью отсчета времен) должна быть определена (по крайней мере изначально как действительное число). Снижение за один «тик» будет числом слегка меньше 1. Это корень N-ой степени из половины, где N составляет половину времени жизни, поделенного на гранулярность отсчета времени.

decay[1] = exp ((1 / (decay-half-life/delta-t)) * log (1/2))

decay array size (decay-array-size)

Размера массива decay array size в памяти decay, поделенный на гранулярность отсчета времени. Если отсечка целой части делает значение элемента массива нулевым, массив можно уменьшить. Реализации следует также задавать максимальный приемлемый размер массива или разрешать более одного умножения.

decay-array-size = (Tmax/delta-t)

decay array (decay[])

Каждый i-й элемент массива decay является задержкой на «тик», возведенной в степень i. Лучшим способом выполнить это может оказаться последовательное умножение действительных чисел с дальнейшим целочисленным округлением или отсечкой. Сам массив требуется рассчитывать только при старте.

decay[i] = decay[1] ** i

4.6 Индексирование списков повторного использования

Списки повторного использования могут восприниматься дружественно, если число маршрутов для демпфирования осцилляций достаточно велико. Предложен метод ускорения выбора списка повторного использования, который может быть применен для данного маршрута. Метод описан в параграфе 4.2, его конфигурация — в параграфе 4.4.2, а алгоритмы в параграфах 4.8.6 — 4.8.7. В данном параграфе рассматривается индексирование списков повторного использования.

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

reuse array maximum ratio (max-ratio)

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

max-ratio = min(ceiling/reuse, exp((1 / (half-life/reuse-array-time)) * log(2)))

reuse array scale factor (scale-factor)

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

scale-factor = reuse-index-array-size / (max-ratio - 1)

reuse index array (reuse-index-array[])

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

reuse-index-array[j] = integer((decay-half-life / reuse-time-granularity) * log(1/(reuse * (1 + (j / scale-factor)))) / log(1/2))

Для определения очереди, куда следует поместить маршрут, который будет подавляться, используется описанная далее процедура. Значение текущей добротности делится на значение отсечки, к результату добавляется 1 и сумма умножается на коэффициент масштабирования. Полученное значение будет индексом для массива индексов повторного использования (reuse-index-array[]). Значение, полученное из массива индексов повторного использования (reuse-index-array[]) является индексом для массива списков повторного использования (reuse-array[]). Если этот индекс указывает на конец массива, используется последняя очередь. В остальных случаях массив просматривается и из него выбирается очередь с соответствующим номером. Этот механизм работает достаточно быстро, легко устанавливается и не расходует большого объема памяти.

4.7 Пример конфигурации

Ниже представлен простой пример, в котором оценивается перекрытие пространства для установки конфигурационных параметров. Предполагается, что:

  1. имеется один набор параметров для всех маршрутов,
  2. «распад» неиспользуемых маршрутов происходит медленней «распада» используемых,
  3. массив должен иметь полный размер вместо того, чтобы разрешать более одного умножения на одну операцию «распада» с целью снижения размера массива.

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

Наборы конфигурационных параметров и параметров реализации имеют вид:

  1. Конфигурационные параметры
    • cut = 1.25
    • reuse = 0.5
    • T-hold = 15 мин.
    • decay-ok = 5 мин.
    • decay-ng = 15 мин.
    • Tmax-ok, Tmax-ng = 15, 30 мин.
  1. Параметры реализации
    • delta-t = 1 сек.
    • delta-reuse = 15 сек.
    • reuse-list-size = 256
    • reuse-index-array-size = 1024

С помощью этих параметров конфигурации и реализации, а также уравнений из параграфа 4.5 можно рассчитать дополнительное пространство (space overhead). Это фиксированное пространство не будет зависеть от числа маршрутов. Указанные требования к пространству связаны со стабильным маршрутом. Для нестабильных маршрутов возникают дополнительные требования к пространству. Пространственные требования для приведенных выше параметров указаны в списке.

  1. Фиксированное пространство (с использованием параметров из предыдущего примера)
    • 900 * integer — массив «распада»
    • 1,800 * integer — массив «распада»
    • 120 * pointer — начала списков повторного использования
    • 2,048 * integer — массивы индексов повторного использования
  1. Дополнительное пространство для стабильного маршрута
    • pointer — содержит нулевой элемент
  1. Дополнительное пространство для нестабильного маршрута
    • pointer — указатель на структуру демпфирования, содержащую
    • integer — добротность + бит для состояния
    • integer — время последнего обновления
    • 2 * pointer — указатели на списки повторного использования (предыдущий, следующий)

Размер массивов «распада» определяется в соответствии с delta-t и Tmax-ok или Tmax-ng. Число заголовков списков повторного использования определяется значением delta-reuse и большим из Tmax-ok и Tmax-ng. Имеется два массива индексов повторного использования, размер которых задается конфигурационным параметром.

На рисунке 3 показано поведение алгоритма с указанными выше параметрами. Рассмотрены 4 случая, для каждого из которых присутствует 12-минутный интервал маршрутных осцилляций. Используется два периода осцилляций в 2 и 4 минуты продолжительностью. Используются два цикла загрузки, в одном из которых маршрут доступен в течение 20% продолжительности цикла, в другом — 80%. Во всех четырех случаях маршрут подавляется после того, как он во второй раз становится недоступным. Демпфирование маршрута сохраняется в течение некоторого времени после восстановления его стабильности. Маршруты, которые осциллируют с периодом 4 минуты перестанут подавляться в течение 9-11 после восстановления их стабильности. Маршруты с периодом осцилляций 2 минуты будут подавляться не более 15 минут после восстановления их стабильности.

4.8 Обработка операций протокола маршрутизации

 время    уровень нестабильности как функция времени (в минутах)
 0.00    0.000 .         0.000 .         0.000 .         0.000 .
 0.62    0.000 .         0.000 .         0.000 .         0.000 .
 1.25    0.000 .         0.000 .         0.000 .         0.000 .
 1.88    0.000 .         0.000 .         0.000 .         0.000 .
 2.50    0.977  .        0.968  .        0.000 .         0.000 .
 3.12    0.949  .        0.888  .        0.000 .         0.000 .
 3.75    0.910  .        0.814  .        0.000 .         0.000 .
 4.37    1.846    .      1.756    .      0.983  .        0.983  .
 5.00    1.794    .      1.614    .      0.955  .        0.935  .
 5.63    1.735    .      1.480   .       0.928  .        0.858  .
 6.25    2.619      .    2.379     .     0.901  .        0.786  .
 6.88    2.544      .    2.207     .     0.876  .        0.721  .
 7.50    2.472     .     2.024     .     0.825  .        0.661  .
 8.13    3.308       .   2.875      .    1.761    .      1.608    .
 8.75    3.213       .   2.698      .    1.711    .      1.562    .
 9.38    3.122       .   2.474     .     1.662    .      1.436   .
10.00    3.922        .  3.273       .   1.615    .      1.317   .
10.63    3.810        .  3.107       .   1.569    .      1.207   .
11.25    3.702        .  2.849      .    1.513    .      1.107   .
11.88    3.498       .   2.613      .    1.388   .       1.015   .
12.50    3.904        .  3.451       .   2.312     .     1.953    .
13.13    3.580        .  3.164       .   2.120     .     1.791    .
13.75    3.283       .   2.902      .    1.944    .      1.643    .
14.38    3.010       .   2.661      .    1.783    .      1.506    .
15.00    2.761      .    2.440     .     1.635    .      1.381   .
15.63    2.532      .    2.238     .     1.499   .       1.267   .
16.25    2.321     .     2.052     .     1.375   .       1.161   .
16.88    2.129     .     1.882    .      1.261   .       1.065   .
17.50    1.952    .      1.725    .      1.156   .       0.977  .
18.12    1.790    .      1.582    .      1.060   .       0.896  .
18.75    1.641    .      1.451   .       0.972  .        0.821  .
19.38    1.505    .      1.331   .       0.891  .        0.753  .
20.00    1.380   .       1.220   .       0.817  .        0.691  .
20.62    1.266   .       1.119   .       0.750  .        0.633  .
21.25    1.161   .       1.026   .       0.687  .        0.581  .
21.87    1.064   .       0.941  .        0.630  .        0.533  .
22.50    0.976  .        0.863  .        0.578  .        0.488 .
23.12    0.895  .        0.791  .        0.530  .        0.448 .
23.75    0.821  .        0.725  .        0.486 .         0.411 .
24.37    0.753  .        0.665  .        0.446 .         0.377 .
25.00    0.690  .        0.610  .        0.409 .         0.345 .

Рисунок 3: Несколько достаточно продолжительных циклов осцилляций (в течение 12 минут), за которыми следует стабильное состояние.

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

Маршрутные события включают:

  1. Первое появление (или восстановление после продолжительного отсутствия) нового партнера BGP или маршрута (параграф 4.8.1).
  2. Переход маршрута в недоступное состояние (параграф 4.8.2)
  3. Восстановление доступности маршрута (параграф 4.8.3)
  4. Изменения маршрутов (параграф 4.8.4)
  5. Потеря партнера (параграф 4.8.5)

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

  1. Вставка в список повторного использования (параграф 4.8.6).
  2. Обработка списка повторного использования каждые delta-t секунд (параграф 4.8.7).

4.8.1 Обработка новых партнеров или маршрутов

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

4.8.2 Обработка сообщений Unreachable

При отзыве или изменении маршрута (обработка изменений описана в параграфе 4.8.4) используется описанная ниже процедура.

Если истории стабильности нет (нулевой указатель на структуру демпфирования):

  1. выделяется структура демпфирования;
  2. устанавливается figure-of-merit = 1
  3. маршрут отзывается.

При наличии истории:

     1.  устанавливается t-diff = t-now - t-updated
     2.  если (t-diff указывает на конец массива) {
              setfigure-of-merit =1
          } иначе {
              setfigure-of-merit = figure-of-merit *decay-array-ok [t-diff ]+ 1
              если (figure-of-merit > ceiling) {
                        setfigure-of-merit = ceiling
              }
         }
     3.  маршрут удаляется из списка повторного использования, если он там присутствует
     4.  маршрут отзывается, если он уже не был демпфирован.

В любом случае:

  1.  устанавливается t-updated = t-now
  2.  маршрут помещается в список повторного использования (см. параграф 4.8.6).

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

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

4.8.3 Обработка маршрутных анонсов

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

  1. не создавать новую структуру демпфирования;
  2. использовать маршрут.

При наличии структуры демпфирования значение уровня добротности устраняется, поля figure-of-merit и t-updated обновляются. Далее принимается решение о незамедлительном использовании маршрута или сохранении демпфированного состояние в течение некоторого времени.

     1.  установить t-diff = t-now - t-updated
     2.  если (t-diff выходит за пределы массива) {
            установить figure-of-merit = 0
         } иначе {
            установить figure-of-merit = figure-of-merit * decay-array-ng[t-diff]
         }
     3.  если (нет демпфирования и figure-of-merit < cut) {
            использовать маршрут
         } иначе, если (имеется демпфирование и figure-of-merit < reuse) {
            установить состояние «не подавлять»
            удалить маршрут из списка повторного использования
            использовать маршрут
         } иначе {
            установить состояние «подавлять»
            не использовать маршрут
            поместить маршрут в список повторного использования (см. параграф 4.8.6)
         }
     4.  если (figure-of-merit > 0) {
           установить t-updated = t-now
         } иначе {
           восстановить память для структуры damping
           обнулить указатель на структуру damping
         }

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

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

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

4.8.4 Обработка изменений маршрутов

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

4.8.5 Обработка потери маршрутизатора-партнера

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

В будущем могут быть предложены уведомления BGP с использованием необязательных переходных атрибутов для снижения издержек, связанных со структурами демпфирования.

4.8.6 Вставка в список Reuse Timer List

  +-+    +-+    +-+          непустой связанный список 
  | |    | |    | |     <--  говорит о наличии маршрутов с 
  +-+    +-+    +-+          отложенными на N * delta-reuse 
   ^      ^      ^           секунд действиями.
   |      |      |
+------+------+------+------+------+      +------+
|голова|голова|голова|голова|голова|  ... |голова|
|списка|списка|списка|списка|списка|  ... |списка|
+------+------+------+------+------+      +------+
   ^      ^      ^      ^      ^             ^
  Nth    1st    2nd    3rd    4th           N-1
          |
   Смещение по отношению к первому списку
   (смещение инкрементируется каждые delta-reuse секунд)

Рисунок 4: Структура данных списка повторного использования.

Список повторного использования служит для обеспечения возможности быстрой оценки ранее демпфированных маршрутов, которые показали стабильность, достаточную для возобновления их применения. Структура данных включает заголовков списков (голова — list head). Каждый список включает набор маршрутов, для которых планируется переоценка примерно в одно время. Множество таких заголовков трактуется, как циклический массив (см. рисунок 4).

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

Основным требованием является возможность включения элемента в наиболее подходящую очередь с минимальными затратами на вычисления. Рассчитывается только текущее значение уровня добротности. Вместо расчетов с использованием логарифмов применяется массив повторного использования reuse-array[], описанный в параграфе 4.6. Массив, масштаб и границы рассчитываются заранее для отображения значений figure-of-merit на ближайший заголовок списка без расчета логарифмов (см. параграф 4.5).

Отметим, что в последующих параграфах записи вида modulo a b означают b % a в нотации языка C.

Например число 1023 по модулю 16 (modulo 16 1023) будет иметь значение 15.

     1.  масштабировать добротность для поиска в массиве индексов
     2.  проверить индекс на предмет выхода за границы массива
     3.  если (в границах массива) {
           установить index = reuse-array[index]
         } иначе {
           установить index = reuse-list-size-1
         }
     4.  поместить в список
           reuse-list[moduloreuse-list-size (index + offset)]

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

4.8.7 Обработка событий, связанных с таймерами

Гранулярность таймера повторного использования следует делать более грубой, чем для таймера распада (decay). В результате по завершении отсчета таймера повторного использования демпфированные маршруты следует дополнительно «разрушать» путем множественного инкрементирования времени распада. Части расчетов можно избежать за счет вставки в список повторного использования, соответствующий однократному инкрементированию прошлой желательности повторного использования. В тех случаях, когда списки повторного использования имеют более долгую «память», нежели «память распада» (см. выше), все маршруты из первой очереди могут применяться незамедлительно, если они доступны или запись истории для недоступного маршрута может быть устранена.

Когда наступает время продвижения списков, должна обрабатываться первая очередь с перемещением циклического списка. Используя массив и смещение в качестве циклического массива (см. параграф 4.8.6), приведенный ниже алгоритм повторяют каждые delta-reuse секунд.

     1.  установить указатель на текущую нулевую очередь и обнулить элемент списка заголовков
     2.  установить offset = modulo reuse-list-size (offset + 1), перемещая тем самым очередь в циклическом списке
     3.  если (сохраненный указатель на заголовок не пуст)
         для каждого элемента {
           sett-diff = t-now - t-updated
           set figure-of-merit = figure-of-merit * decay-array-ok[t-diff]
           sett-updated = t-now
           если ( figure-of-merit < reuse)
             снова использовать маршрут
           else
             поместить маршрут в другой список (см. параграф 4.8.6)
         }

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

5 Опыт реализации

Первыми реализациями демпфирования маршрутных осцилляций (route flap damping) были демон rsd10, разработанный Ramesh Govindan (ISI) и реализация Cisco IOS от Ravi Chandra. Обе реализации стали доступны в 1995 и широко использовались. Демон rsd применялся в серверах маршрутов финансируемых NSF точках доступа в сеть NAP11 и других основных узлах Internet. Версия Cisco IOS использовалась Internet-провайдерами по всему миру. Реализация rsd была встроена в демон gated (see http://www.gated.org) и доступна на коммерческих маршрутизаторах, использующих gated.

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

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

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

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

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

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

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

Благодарности

Этот документ и работа в целом не были бы завершены без советов, комментариев и поддержки Yakov Rekhter (Cisco). Dennis Ferguson (MCI) представил описания алгоритмов в реализации gated BGP, а также множество идей и комментариев. David Bolen (ANS) и Jordan Becker (ANS) внесли важные комментарии, особенно в части ранних моделей. Прошло четыре года между представлением изначального чернового варианта в BGP WG (октябрь 1993 г.) и выходом данного документа. За время работы был обретен значительный опыт применения двух реализаций, развернутых в 1995 г. Одна из них была предложена Ramesh Govindan (ISI) для проекта NSF Routing Arbiter, а вторая — Ravi Chandra (Cisco). Sean Doran (Sprintlink) и Serpil Bayraktar (ANS) были среди первых независимых тестировщиков предварительной реализации Cisco. Значимые комментарии и обратная связь были представлены многими членами рабочих групп IETF IDR WG и RIPE Routing, а также NANOG и IEPG.

Благодарим также Rob Coltun (Fore Systems), Sanjay Wadhwa (Fore), John Scudder (IENG), Eric Bennet (IENG) и Jayesh Bhatt (Bay Networks) за обнаружение ошибок в более свежих реализациях. Эти ошибки в деталях, внесенных после завершения двух ранних реализаций. Спасибо Vern Paxson за внимательное рассмотрение документа и множество внесенных уточнений.

Литература

[1] Gross, P., and Y. Rekhter, «Application of the border gateway protocol in the internet», RFC 1268, October 1991.

[2] ISO/IEC. ISO/IEC 10747 — information technology — telecommunications and information exchange between systems — protocol for exchange of inter-domain routeing information among intermediate systems to support forwarding of iso 8473 pdus. Technical report, International Organization for Standardization, August 1994. ftp://merit.edu/pub/iso/idrp.ps.gz12.

[3] Lougheed, K., and Y. Rekhter, «A border gateway protocol 3 (BGP-3)», RFC 1267, October 1991.

[4] Rekhter, Y., and P. Gross, «Application of the border gateway protocol in the internet», RFC 1772, March 1995.

[5] Rekhter, Y., and T. Li, «A border gateway protocol 4 (BGP-4)», RFC 1771, March 1995.

[6] Rekhter, Y., and C. Topolcic,»Exchanging routing information across provider boundaries in the CIDR environment», RFC 1520, September 1993.

[7] Traina, P., «BGP-4 protocol analysis», RFC 177413, March 1995.

[8] Traina, P., «Experience with the BGP-4 protocol», RFC 1773, March 1995.

Вопросы безопасности

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

Адреса авторов

Curtis Villamizar

ANS

EMail: curtis@ans.net

 

Ravi Chandra

Cisco Systems

EMail: rchandra@cisco.com

 

Ramesh Govindan

ISI

EMail: govindan@isi.edu

 

Перевод на русский язык

Николай Малых

nmalykh@gmail.com

Полное заявление авторских прав

Copyright (C) The Internet Society (1998). All Rights Reserved.

This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.

The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns.

This document and the information contained herein is provided on an «AS IS» basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

1Демпфирование осцилляций маршрутов.

2Network Layer Reachability Information – информация о доступности на сетевом уровне.

3Частота выбора маршрутов.

4Частота анонсирования маршрутов.

5Частота порождения маршрутов.

6По-русски будет лучше сказать уровень нестабильности и мы будет в дальнейшем использовать именно такой термин. Прим. перев.

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

8Routing Information Base

9Reuse index array.

10Route server daemon — демон сервера маршрутов.

11Network Access Point.

12Приведенная в оригинале ссылка устарела. На момент перевода документ был доступен по ссылке ftp://ftp.merit.edu/oldmerit/pub/iso/idpr-fnl.tar.gz. Прим. перев.

13Этот документ устарел и заменен RFC 4274. Прим. перев.




RFC 2409 The Internet Key Exchange (IKE)

Заменен RFC 4306.




RFC 2406 IP Encapsulating Security Payload (ESP)

Заменен RFC 4303 и RFC 4305.




RFC 2402 IP Authentication Header

Заменен RFC 4302 и RFC 4305.




RFC 2401 Security Architecture for the Internet Protocol

Заменен RFC 4301.