Семейство протоколов TCP/IP. Протоколы маршрутизации. Алгоритм RIP.

Протоколы маршрутизации. Алгоритм RIP

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

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

Рис. 2.6.1.

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

На ранней стадии развития сети Internet наибольшее распространение имела логическая схема построения сети, которая имела название core architecture (централизованная архитектура).

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

В качестве узла (Node) сети core architecture может выступать как отдельный узел, так и совокупность узлов или сетей, которые объединены по принципу единой территориальной или функциональной принадлежности. Информационное взаимодействие в данном случае может быть организовано только через центральную структуру – (Core). В качестве центральной структуры сетей использовалась небольшая сеть взаимодействующих узлов – маршрутизаторов. Каждый из центральных узлов был связан с одним или несколькими периферийными узлами, и с несколькими маршрутизирующими узлами, которые образуют центральную структуру. Для обеспечения решения задачи маршрутизации центральные узлы должны были обмениваться информацией о структуре сети.

Маршрутизация в сетях core architecture выполнялась по двум различным схемам – одна из этих схем применялась для определения маршрута передачи дейтаграмм в периферийных узлах, другая применялась в центральных узлах.

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

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

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

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

Концепция автономных систем предполагает разбиение сети на отдельные области, в пределах которых управление процессами определения маршрута производится автономно. На рисунке приведена структурная схема организации информационного взаимодействия в соответствии с концепцией автономных систем. В данном случае каждая из автономных систем AS N может объединять в себе несколько локальных сетей. Взаимодействие между этими локальными сетями в пределах автономной системы производится в соответствии с правилами определения маршрута, которые приняты в данной автономной системе. Внутри каждой автономной системы могут быть использованы различные правила определения маршрута и протоколы маршрутизации. Информационное взаимодействие между компонентами различных автономных систем может быть выполнено только через специальную область, которая предназначена для интеграции всей системы в целом. Такая область, в соответствии с терминологией, которая принята в данной концепцией, называется Backbone Area.

Рис. 2.6.2.

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

•  определение маршрута внутри автономной системы;

•  определение маршрута между автономными системами.

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

Функции коммуникационных узлов в реальных системах выполняют специальные пограничные маршрутизаторы , которые называются exterior/edge router. Пограничные маршрутизаторы всех автономных систем совместно с маршрутизаторами центральной области участвуют в выполнении специальных алгоритмов маршрутизации, которые используются для определения маршрута передачи данных между автономными системами. Такие алгоритмы маршрутизации относятся к классу EGP (exterior gateway protocol).

Алгоритмы маршрутизации, которые используются для определения маршрута за пределами автономной системы, относятся к классу exterior gateway protocol – EGP .

Алгоритмы маршрутизации, которые используются для определения маршрута внутри автономной системы, относятся к классу interior gateway protocol – IGP .

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

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

•  Протоколы distant vector;

•  Протоколы link state.

Протоколы типа distant vector предусматривают передачу информации о маршрутах периодически через установленные интервалы времени.

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

Протокол маршрутизации RIP (Routing Information Protocol) относится к алгоритмам класса "distance vector". Этот алгоритм является одним из первых алгоритмов маршрутизации, которые были использованы в информационно – вычислительных сетях вообще и в сети Internet – в частности.

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

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

Использование протокола RIP может в ряде случаев привести к появлению "зацикленных маршрутов". Для предотвращения возникновения подобных ситуаций должны быть использованы специальные меры (poison reverse, split horizon).

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

Описание алгоритма distant vector. Пусть D (i, j) представляет показатель оптимального маршрута из объекта i в объект j, а D (k, j) обозначает показатель маршрута из узла k в сеть j. Показатель оптимального маршрута может быть вычислен следующим образом: объект i запрашивает у соседей k, оценки их расстояний до сети j. Когда i получает оценки из k, он добавляет оценку своего маршрута до данного соседа d (i, k) к каждому из чисел. Затем i сравнивает величины от всех соседей и выбирает наименьшую из них. Таким образом,

D ( i , i ) = 0, для всех i

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

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

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

Рис. 2.6.3.

В исходном состоянии все каналы передачи данных функционируют нормально и, поэтому, маршруты из узлов D и C к сети N лежат через маршрутизатор B и имеют метрику 2. предположим, что в некоторый момент времени канал, который связывает маршрутизаторы A и В, выходит из строя. Маршрутизатор B в этом случае перестает принимать update для сети N от маршрутизатора A и по истечении установленного интервала времени маршрутизатор B определяет сеть N в качестве недостижимой и исключает её из своих массивов update. Однако из-за того, что эти массивы передаются в сети асинхронно вполне возможно, что вскоре после этого маршрутизатор C получит массивов update от маршрутизатора D, который пока ещё считает, что маршрут из B до сети N существует. Получив такую информацию, маршрутизатор C включит в свою таблицу маршрутизации новый маршрут до сети N - через маршрутизатор D с метрикой 3. После того, как истечет время существования исходного маршрута в маршрутизаторе D, эта ситуация повторится совершенно аналогичным образом. В результате маршрутизатор D скорректирует свою таблицу маршрутизации и внесет в неё маршрут до сети N через шлюз C с метрикой 4. Подобная ситуация будет таким образом возобновляться снова и снова с периодом, который соответствует времени существования маршрута (3TUpdate). Этот цикл, который называется «счет до бесконечности», будет продолжаться до тех пор, пока метрика циклического маршрута не достигнет значения 15, после чего он разорвется автоматически.

Алгоритм split horizon является неотъемлемой частью протокола маршрутизации RIP и предназначен для предотвращения появления циклических маршрутов в сети. Для предотвращения возникновения подобных ситуаций достаточно использовать следующее правило: Маршрутизатор не должен направлять update для маршрутов в адрес их источника .

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

Правило split horizon может быть использовано с незначительной модификацией. Правило split horizon with poisoned reverse «расщепленный горизонт с отравленным обратным путем» – разрешает передачу update для потенциально опасных, с точки зрения возникновения циклов, маршрутов. В данном случае для таких маршрутов устанавливается метрика, которая соответствует бесконечности – 15.

Процедура triggered update (Управляемые модификации). Использование процедуры Split horizon позволяет избежать появления зацикленного маршрута у двух шлюзов. Однако возможно возникновение ситуации, когда в циклическом маршруте участвуют три шлюза. На рисунке приведен пример возникновения подобной ситуации. В приведенной сети при выходе из строя канала, который связывает узел А с сетью N, маршрутизатор B может принять от маршрутизатора С несуществующий маршрут до сети N, который якобы проходит через узел C. К тому моменту, когда маршрутизатор C определит, что он не имеет собственного маршрута до сети N, маршрутизатор B уже успеет передать информацию о наличии у него маршрута до этой сети марщрутизатору D. Использование процедуры Split horizon не сможет предотвратить появление такой петли, поскольку сообщения о маршруте поступают не от того маршрутизатора, которому передаются сообщения update. Следовательно, эта петля будет разорвана только тогда, когда метрика циклического маршрута достигает бесконечности. Для того, чтобы уменьшить время переходных процессов в сети можно использовать процедуру управляемых модификаций.

Рис. 2.6.4.

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

Возможно возникновение ситуации, когда периодическое обновление будет просто потеряно в сети из за возникновения краткосрочной перегрузки или временной неработоспособности канала передачи данных. Для того, чтобы в этой ситуации маршруты не были ошибочно удалены из таблицы маршрутизации, каждому маршруту ставится в соответствие специальный счетчик времени, который называется timeout – timer . В тот момент времени, когда данный маршрут включается в таблицу маршрутизации, или когда для него приходит очередное обновление значение счетчика timeout – timer устанавливается равным Ttimeout max. = 180 секунд и этот счетчик начинает обратный отсчет времени. В том случае, если счетчик timeout – timer какого либо маршрута достигнет значения 0, этот маршрут должен быть исключен из числа активных маршрутов.

К основным недостаткам, которые присущи алгоритму RIP-1, помимо возможности возникновения циклических маршрутов, относятся:

•  Невозможность использования внеклассовых сеток;

•  Невозможность использования независимых областей маршрутизации.

Эти недостатки были устранены при формировании современной версии данного протокола, которой было присвоено наименование RIP-2.

Новая версия протокола, RIP-2 , обеспечивает устранение некоторых недостатков первой версии и является совместимой с ней. Общие принципы организации протокола маршрутизации RIP-2 изложены в RFC 1388.

Для передачи сообщений протокола RIP используются дейтаграммы, которые адресуются в порт №520 UDP. Формат сообщения протокола маршрутизации RIP приведен в таблице:

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

Таблица 2.6.1.

В поле COMMAND дейтаграммы RIP размещается код сообщения:

•  Значение 1 соответствует сообщению типа request (запрос);

•  Значение 2 соответствует сообщению типа response (ответ).

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

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

Поле IP ADDRESS занимает 4 байта в заголовке дейтаграммы протокола RIP. В сообщении типа RIP request в данном поле содержится адрес сети, для которой необходимо определить маршрут. В сообщениях типа RIP response в данное поле помещается адрес сети, которая является достижимой для источника данного сообщения.

Поле SUBNET MASK занимает 4 байта в заголовке дейтаграммы протокола RIP. В этом поле сообщений протокола RIP–2 размещается маска сети, адрес которой расположен в соответствующем поле IP ADDRESS. У сообщений, которые сформированы протоколом RIP-1, содержимое данного поля должно быть равно 0.

В поле NEXT HOP сообщений протокола RIP-2 размещается адрес маршрутизатора, который является непосредственно достижимым для источника данного сообщения и может быть использован в качестве next hop для передачи данных в сеть, адрес которой указан в поле IP ADDRESS.

Поле METRIC также занимает 4 байта в заголовке дейтаграммы протокола RIP, однако в данном поле может быть размещена только характеристика маршрута, который определен полями IP ADDRESS, SUBNET MASK, NEXT HOP – метрика, которая может принимать значение от 0 до 15.