|
|
|
|
|||||||
|
|
|||||||||
|
|
|||||||||
|
Network Working Group G. Malkin
Request for Comments: 2453 Bay Networks
Obsoletes: 1723, 1388 November 1998
STD: 56 Category: Standards Track
RIP Version 2 Статус документа
Этот документ содержит спецификации протокола для сообщества 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).
Оглавление
|
|||||||||
|
4.
|
|||||||||
|
|
|||||||||
|
|
3.10 Обработка исходящей информации ................... 12
|
|
|||||||
|
5.
|
|
||||||||
|
Полное заявление авторских прав .................................... 16
|
|||||||||
|
|
|||||||||
|
1. Обоснование
После появления протоколов OSPF и IS-IS некоторые специалисты полагали, что протокол RIP должен уйти со сцены.
Понятно, что новые протоколы маршрутизации IGP существенно превосходят RIP, но и протокол RIP имеет
некоторые преимущества. Прежде всего, в небольших сетях RIP обеспечивает существенно меньший расход полосы, а
также снижение затрат времени на обслуживание и настройку. Протокол RIP очень прост в реализации, особенно в
сравнении с новейшими протоколами IGP.
Кроме того, в существующих сетях протокол RIP распространен во много раз шире, нежели OSPF и IS-IS. Очевидно,
что такая ситуация будет сохраняться еще достаточно долго.
Исходя из широкого распространения протокола RIP, представляется разумным расширение возможностей RIP. С
учетом затрат на такое изменение и получаемых результатов такая работа представляется очень перспективной.
|
|||||||||
|
|
|||||||||
|
2. Текущий вариант RIP
Сообщения RIP-1 содержат минимальное количество информации, требуемой маршрутизаторам сообщений через сеть. Кроме того, в сообщениях содержится много пустого места.
|
для направления
|
||||||||
|
|
|||||||||
|
|
||||
|
|
Перевод RFC 2453
|
|||
|
|
||||
|
В протоколе 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) для разрешения нештатных ситуаций (эта особенность будет рассмотрена ниже). Если в систему входит несколько сотен сетей и в маршрутизации имеются петли, «разрешение» этих петель потребует дополнительного времени (если ограничена частота обновления маршрутов) или полосы (если обновления передаются по факту их обнаружения). Пока такие петли не будут обнаружены и устранены, они будут поглощать значительную часть полосы сети. Будем надеяться, что в реальных сетях это не создаст дополнительных сложностей (за исключением случаев использования низкоскоростных каналов). Более того, эта проблема возникает достаточно редко, поскольку для ее предотвращения приняты специальные меры.
|
||||
|
|
||||
|
Прообраз сети Internet. Прим. перев.
|
||||
|
|
||||
|
2
|
||||
|
|
||||
| |
|||
| Перевод
RFC 2453
|
|||
| |
|||
| •
Протокол использует «фиксированную» метрику
для сравнения альтернативных маршрутов. Такое решение не подходит для
систем, где выбор маршрута должен основываться на параметрах, измеряемых
в реальном масштабе времени (задержка, надежность доставки, степень
загрузки). Простое добавление учета таких параметров приводит к нестабильности,
с которой протокол не может работать.
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-адрес
хоста или сети;
•
маршрутизатор: первый маршрутизатор на пути к получателю;
•
интерфейс: физический интерфейс, используемый для
связи с первым маршрутизатором;
•
метрика: число, показывающее «удаленность»
получателя;
•
таймер: время, прошедшее с момента последнего обновления
записи.
|
|||
| |
|||
| 2
Отметим, что в некоторых реализациях могут существовать различия
между хостами и сетями (см. параграф 3.2).
|
|||
| |
|||
|
|
|||
|
|
Перевод RFC 2453
|
||
|
|
|||
|
В дополнение к перечисленному могут включаться различные флаги и другая внутренняя информация. Эта база
данных инициализируется с описанием объектов, непосредственно подключенных к системе. База данных потом
обновляется в соответствии с информацией, получаемой в сообщениях от ближайших соседей.
Наиболее важная информация между маршрутизаторами и хостами передается в обновлениях (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 должна трактоваться как «квинтэссенция» записей для всех
|
|||
|
|
|||
|
3 Отметим, что стоимость d(i, i) имеет нулевое значение (в оригинале ошибочно сказано «бесконечное» - прим. перев.), т. е., мы не учитываем здесь прямую передачу узла самому себе.
4 Это можно строго доказать с использованием метода математической индукции.
|
|||
|
|
|||
|
|
||||
|
Перевод RFC 2453
|
|
|||
|
|
||||
|
узлов сети А. Единственная информация, которая не может быть включена в суммарную запись для сети А, это сведения о самом объекте G, поскольку стоимость доставки из G в G равна 0, а не С. Но, поскольку такие записи с нулевой стоимостью реально не используются, можно обойтись одной записью для всей сети А. В виду того, что записи с нулевой стоимостью реально не используются, хосты, не выполняющие функций маршрутизации, не должны передавать никаких обновлений таблиц. Очевидно, что хосты, не выполняющие функций маршрутизации (т.е., подключенные к единственной сети) не имеют какой-либо полезной информации для передачи другим хостам, за исключением тривиальной записи D(i,i) = 0. Поскольку такие хосты используют единственный сетевой интерфейс, легко видеть, что маршрут в любую другую сеть через такой хост будет приводить на тот же интерфейс (т. е., назад). В результате стоимость такого маршрута не может быть меньше минимальной стоимости С. Поскольку нет нужды в сохранении записей с нулевой стоимостью, хосты, не являющиеся маршрутизаторами, просто не должны участвовать в работе протокола маршрутизации.
Резюмируем сказанное выше о работе узла 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 секунд. Это сделано для того, чтобы избавиться
|
||||
|
|
||||
|
5 Если несколько маршрутов имеют одинаковую стоимость, маршрутизатор будет относиться к одному из таких путей.
6 Отметим, что рассмотрение построено на предположении о статическом характере системы и не учитывает возможности «падения».
7 К таким объектам относятся все маршрутизаторы; хосты, на поддерживающие маршрутизации, также могут выполнять эти процедуры
|
||||
|
|
||||
|
5
|
||||
|
|
||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Перевод RFC 2453
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
от ложных тайм-аутов в результате потери пакетов при констатации тайм-аута в результате отсутствия одного сообщения.
Как было показано выше, полезно иметь способ уведомления соседей об отсутствии маршрута в ту или иную сеть. 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
|<=== сеть получателя
Каждый маршрутизатор будет иметь таблицу, показывающую маршрут в каждую сеть, однако для упрощения рисунка показаны только пути от каждого маршрутизатора в сеть получателя (в нижней части рисунка).
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
подключение с метрикой 1
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
прямое
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
маршрут через D, метрика 2
маршрут через B, метрика 3
маршрут через B, метрика 3 Предположим, что рвется канал связи между B и D. Маршруты в этом случае должны быть на использование канала между C и D. К несчастью, на такое переключение потребуется время. Изменение маршрутизации начнется после того, как маршрутизатор B обнаружит невозможность использования D. Для простоты будем предполагать, что все маршрутизаторы передают обновления одновременно. Ниже показана метрика для сети получателя с точки зрения каждого маршрутизатора. время ------ >
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
dir = прямое соединение
unreach = сеть недоступна Здесь возникает проблема – маршрутизатор B может получить информацию о «падении» маршрута с использованием тайм-аута, но достаточно еще долго будет предполагать наличие маршрута в системе. Изначально, маршрутизаторы A и C продолжают думать, что они могут связаться с D по пути через B. Поэтому они будут передавать обновления, содержащие метрику 3. На следующем этапе B будет заявлять, что возможен доступ к D через A или C (естественно, это не так). Маршруты, заявляемые A и C, уже не существуют, но узнать об этом невозможно. И даже после обнаружения недоступности маршрутов через B каждый из маршрутизаторов A и C будет думать о доступности пути через другой маршрутизатор. В конце концов, будут найдены правильные маршруты, но это займет некоторое время.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||
|
Перевод RFC 2453
|
|
||
|
|
|||
|
Самая плохая ситуация возникает в тех случаях, когда сеть становится полностью недоступной из какой-то части системы. В таких случаях метрика медленно увеличивается, пока не будет вычислена недоступность. Такие ситуации называются «вычислением бесконечности» (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) будет предотвращать возникновение петель между парой маршрутизаторов. Однако возможны ситуации, когда в процесс
|
|||
|
|
|||
|
|
|||
|
|
|||
|
|
Перевод RFC 2453
|
||
|
|
|||
|
«взаимообмана» вовлечены три маршрутизатора. Например, маршрутизатор A может предполагать наличие маршрута через B, B через C, а C через A. Расщепление горизонта не может предотвратить возникновение таких петель. Для разрешения этой проблемы метрика должна сойтись к бесконечности и соответствующая сеть должна быть объявлена недоступной. Обновления по событию (triggered update) являются попыткой ускорить процесс схождения метрики. Для использования triggered update просто добавляется правило, по которому маршрутизатор, меняя метрику для пути, должен передать уведомление об этом, не дожидаясь времени штатной передачи обновления. Промежуток времени, по истечении которого должно передаваться такое уведомление, зависит от протокола. Некоторые протоколы на базе алгоритмов DV (в частности, RIP) требуют передавать обновление с небольшой задержкой, чтобы избежать значительного роста сетевого трафика. Рассмотрим, как это правило взаимодействует с правилами расчета новой метрики. Предположим, что путь от маршрутизатора в сеть N проходит через маршрутизатор G. Если обновление приходит непосредственно от G, принявший его маршрутизатор должен доверять полученной информации независимо от знака изменения метрики. Если в результате метрика изменяется, принявший обновление маршрутизатор будет передавать в связи с этим событием обновления (triggered updates) всем хостам и маршрутизаторам, непосредственно п | |||