Что такое протокол внутридоменной маршрутизации

Обновлено: 08.05.2024

Среди принципов маршрутизации трафика группового вещания можно отметить:

§ маршрутизацию на основе доменов;

§ учет плотности получателей группового трафика;

§ два подхода к построению маршрутного дерева;

§ концепцию продвижения по реверсивному пути.

Маршрутизация на основе доменов. Значительный объем хранимой и передаваемой по сети служебной информации, используемой для поддержания группового вещания, стал факто­ром, ограничивающим масштабируемость данной технологии. Для улучшения масштаби­руемости разработчики технологии группового вещания предложили традиционный для Интернета иерархический подход, основанный на доменах. Подобно автономным системам (доменам маршрутизации) и DNS-доменам, вводятся домены группового вещания. Для доставки информации в пределах домена предлагаются одни методы и протоколы маршру­тизации группового вещания, называемые внутридоменными, а в пределах многодоменной структуры — другие, называемые междоменными. Мы ограничимся в этом учебнике опи­санием средств продвижения пакетов группового вещания в пределах отдельного домена. Учет плотности получателей группового трафика. Внутридоменные протоколы маршру­тизации разделяются на два принципиально отличных класса:

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

ПРИМЕЧАНИЕ

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

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

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

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

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

Напротив, все пакету с групповым адресом маршрутизаторы тиражируют и передают ко­пии во все стороны — на все интерфейсы, кроме того, с которого этот пакет поступил. При этом в сложных сетях возможно образование петель — замкнутых маршрутов. Для пра­вильной работы сети зациклившиеся пакеты необходимо распознавать и отбрасывать. Петля не может возникнуть, если ли пакет прибыл от источника по ожидаемому пути, про­ложенному в соответствии с обычным алгоритмом маршрутизации, основанном на анализе таблиц маршрутизации. А именно, маршрутизатор проверяет, является ли входной интер­фейс, получивший групповой пакет, интерфейсом, через который пролегает кратчайший путь к источнику. Он делает это с помощью обычной таблицы маршрутизации, которая, как известно, содержит указания о рациональных путях ко всем сетям составной интерсети. Проверка факта выполнения данного условия называется продвижением по реверсивному пути(Reverse Path Forwarding, RPF). Такое название объясняется тем, что эта процедура связана не столько с путями, ведущими вперед от текущего места нахождения пакета к пункту назначения, сколько с обратным (реверсивным) путем, который уже пройден пакетом от того места, где он находится сейчас, до источника. Только пакеты, которые прошли RPF-проверку, являются кандидатами для дальнейшего продвижения вдоль путей, ведущих к потенциальным получателям трафика группового вещания.

Концепция продвижения по реверсивному пути является главной при маршрутизации груп­пового трафика независимо от того, какой протокол при этом использован. Механизм RPF применятся и в других вариантах организации группового вещания. Например, когда марш­рутизатор пытается продвигать пакеты к точке встречи в сети, работающей в разряженном режиме, он выбирает интерфейс, от которого проходит кратчайший путь к точке встречи. На этом этапе мы не предъявляли специфических требований к таблицам маршрутиза­ции, на основании которых выполняется RPF-проверка. Некоторые протоколы, такие как DVMRP, строят собственную таблицу маршрутизации, в то время как, например, протокол PIM работает с таблицами маршрутизации, построенными другими протоколами.

Протокол DVMRP

Дистанционно-векторный протокол маршрутизации группового вещания(Distance Vector Multicast Routing Protocol, DVMRP), описанный в спецификации RFC 1075, может быть характеризован с самых общих позиций следующим образом:

§ как следует из его названия, он основан на дистанционно-векторном алгоритме и, сле­довательно, обладает всеми особенностями, свойственными данному алгоритму;

§ относится к классу протоколов плотного режима, использующих проверку продвижения по реверсивному пути;

§ продвигает пакеты на основе деревьев с вершинами в источниках;

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

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

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

Рис. 18.15. Управляемое широковещание

Чтобы модернизировать протокол DVMPR, понадобилось несколько лет дополнительных усилий.

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

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

Для построения деревьев с вершиной в источнике пригодны различные алгоритмы, в частности один из таких алгоритмов, разработанный и стандартизованный IEEE для мостов локальных сетей под названием STA, мы рассмотрели ранее в главе 14.

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

1. Источник отправляет пакет по своей локальной сети с групповым адресом. Присоеди­ненный к локальной сети маршрутизатор получает пакеты и отправляет их на все вы­ходные интерфейсы.

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

Протокол MOSPF

Протокол PIM-SM

Протокол PIM-SM является одной из двух версий протокола PIM(Protocol Independent Multicast — независимое от протокола групповое вещание), описываемого в спецификации RFC 2362:

§ версии плотного режима PIM-DM (Protocol Independent Multicast — Dense Mode);

§ версии разряженного режима PIM-SM (Protocol Independent Multicast — Sparse Mode).

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

Главной особенностью протокола PIM-SM является то, что он рассчитан на работу в раз­ряженном режиме, то есть он посылает групповые пакеты только по явному запросу по­лучателя. Для доставки данных каждой конкретной группе получателей протокол PIM-SM строит одно разделяемое дерево, общее для всех источников этой группы (рис. 18.16).

Рис. 18.16. Разделяемое дерево протокола PIM-SM

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

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

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

1. Построение разделяемого дерева с вершиной в точке встречи, которое описывает пути доставки групповых пакетов между точкой встречи и членами данной группы. Это де­рево называют также деревом точки встречи (Rendezvous Point Tree, RPT).

2. Построение дерева кратчайшего пути (Shortest Path Tree, SPT), которое будет достав­лять пакеты между источником данной группы и точкой встречи.

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

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

Рассмотрим работу протокола PIM-SM на простом примере. На рис. 18.17 показана одно­доменная сеть, в которой протокол PIM-SM устанавливает связь между одним получате­лем А и одним источником S. Будем считать, что работа сети соответствует модели ASM (групповое вещание из любого источника), на всех узлах сети развернут протокол IGMP и все маршрутизаторы поддерживают протокол PIM-SM. Будем считать также, что точка встречи сконфигурирована статически: и источники, и получатели знают индивидуальный адрес точки встречи, роль которой в этой сети играет маршрутизатор D. Для оповещения узлов сети об адресе точке встречи имеется стандартный протокол автоматического опо­вещения, называемый протоколом загрузки.

Рис. 18.17. Этап 1 — построение разделяемого дерева

Этап 1 — построение разделяемого RPT-дерева от получателя к точке встречи. Когда раз­деляемое дерево уже построено, трафик группового вещания передается от точки встречи в направлении заинтересованных получателей. Однако процесс построения разделяемого дерева движется в обратном направлении — от получателей к точке встречи на основе по­шагового (hop-by-hop) подхода.

В нашем примере на данном этапе нет активных источников, поэтому данные группового вещания еще не поступают к точке встречи (см. рис 18.17).


Рис. 18.18. Этап 2 — регистрация источника с построением дерева кратчайшего пути

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


Рис. 18.19. Этап 3 – построение дерева кратчайшего пути от источника к получателю.

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

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

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

  1. к какой сети он должен его передать;
  2. по какому пути.

Последнее решение основано на выборе оптимального пути. Какой доступный путь является оптимальным путем? Это обычно определяется метрикой. Метрика – это условная стоимость передачи по сети. Полное измерение конкретного маршрута равно сумме метрик сетей, которые включают в себя маршрут . Маршрутизатор выбирает маршрут с наименьшей метрикой. Метрика назначается для интерфейса сети в зависимости от типа протокола. Некоторые простые протоколы, подобно протоколу маршрутной информации ( RIP – Routing Information Protocol ), рассматривают все сети как одинаковые. Тогда стоимость прохождения через каждую сеть — одна и та же, и для определения метрики подсчитываются участки. Так, если пакет, чтобы достигнуть конечного пункта, проходит через 10 сетей, полная стоимость составляет 10 участков.

Другие протоколы, такие как "первоочередное открытие наикратчайших путей" ( OSPF — Open Shortest Path First ), позволяют администратору назначить стоимость для передачи через сеть , основанную на типе требуемого обслуживания. Маршрут через сеть может иметь различную стоимость (метрику). Например, если для типа сервиса желательна максимальная производительность , спутниковый канал имеет меньшую метрику, чем оптическая линия. С другой стороны, если типу сервера желательна минимальная задержка, оптическая линия имеет меньшую метрику, чем спутниковый канал. OSPF позволяет каждому маршрутизатору иметь таблицу последовательностей маршрутов, основанную на требуемом типе сервиса.

Другие протоколы определяют метрику различно. В протоколе пограничной маршрутизации ( BGP — Border Gateway Protocol ) критерий — это политика, которую может устанавливать администратор . Политика — это принцип, по которому определяется путь .

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

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

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

Внутренняя и внешняя маршрутизация

Сегодня Интернет — громадная сеть , так что один протокол маршрутизации не может обрабатывать задачу обновления таблиц всех маршрутизаторов. По этой причине Интернет разделяется на автономные системы. Автономная система (Autonomous System – AS) — группа сетей и маршрутизаторов под управлением одного администратора. Маршрутизация внутри автономной системы отнесена к внутренней маршрутизации. Маршрутизация между автономными системами отнесена к внешней маршрутизации. Каждая автономная система может выбрать протокол внутренней маршрутизации для того, чтобы обрабатывать маршрутизацию внутри автономной системы. Однако для обработки маршрутизации между автономными системами выбирается только один протокол маршрутизации .

Разработано несколько внутренних и внешних протоколов. В этой лекции мы коснемся только наиболее популярных из них — внутренних протоколов RIP и OSPF и одного внешнего протокола BGP . RIP и OSPF используются для обновления таблиц маршрутизации внутри автономной системы. Протокол BGP применяется в обновлении таблиц маршрутизации для маршрутизаторов, которые объединяют вместе автономные системы.

Протокол маршрутной информации (RIP)

Протокол маршрутной информации ( RIP – Routing Information Protocol ) — внутренний протокол маршрутизации , используется внутри автономной системы. Это очень простой протокол, основанный на применении дистанционного вектора маршрутизации. В этом разделе сначала рассмотрим принцип дистанционного вектора маршрутизации, так как он применяется в RIP , а затем обсудим сам протокол RIP .

Вектор расстояния маршрутизации

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

  1. Распределение информации о входе в автономную систему. Каждый маршрутизатор распределяет информацию о входе соседним автономным системам. Вначале эта информация может быть не подробной. Однако объем и качество информации не играют роли. Маршрутизатор посылает, во всяком случае, все что имеет.
  2. Распределение только соседям. Каждый маршрутизатор посылает свою информацию только к соседям. Он посылает информацию, которую получает через все интерфейсы.
  3. Распределение через регулярные интервалы. Каждый маршрутизатор посылает свою информацию соседней автономной системе через фиксированные интервалы, например, каждые 30 с.

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

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

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

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

· обмен информации о локально подключенных хостах и сетях;

· сравнение альтернативных путей;

· согласование топологии сети.

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

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

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

· в повышении надежности сети;

· эффективном расходовании ресурсов;

· возможности применения для диагностики и временного разрешения проблем в сети;

· обеспечении безопасности сети.

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

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

Недостатки дистанционно-векторной маршрутизации следующие:

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

· маршрутизатор ничего не знает о фактической топологии сети и других маршрутизаторах;

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

Основным достоинством дистанционно-векторных протоколов является их простота. Эти протоколы эффективны в очень мелких сетях с минимальным количеством альтернативных путей и отсутствием жестких требований к производительности. Типичным представителем таким протоколов является протокол RIP (описан в документе RFC1058).

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


менений в сети. Топологическая маршрутизация обладает двумя существенными недостатками:

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

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

Решаются эти проблемы посредством планирования и технического оснащения сети.

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

· шлюз (gateway) – компьютер, выполняющий преобразование протоколов. Шлюзы работают на уровнях модели OSI с 4 по 7 (например, шлюз электронной почты). Шлюзы очень часто выполняют преобразование нескольких протоколов в зависимости от сетевых подключений, например, также они могут выполнять шифрование/дешиф-рование данных;

· мост (bridge) – компьютер, соединяющий две сети и более, использующий один протокол. Мост работает на уровне 2 модели OSI и использует адреса канального уровня (а не адреса IP);

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

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

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

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

Существует и прямо противоположный, многошаговый подход — маршрутизация от источника (Source Routing). В соответствии с ним узел-источник указывает в отправляемом в сеть пакете полный маршрут его следования через все промежуточные маршрутизаторы. Такой способ не требует построения и анализа таблиц маршрутизации. Это ускоряет прохождение пакета по сети и разгружает маршрутизаторы, но при этом большая нагрузка ложится на конечные узлы. Данная схема применяется гораздо реже, чем схема распределенной одношаговой маршрутизации.

Статические алгоритмы и простая маршрутизация

В зависимости от способа формирования таблиц маршрутизации одношаговые алгоритмы делятся на три класса:

  • алгоритмы фиксированной (или статической) маршрутизации;
  • алгоритмы простой маршрутизации;
  • алгоритмы адаптивной (или динамической) маршрутизации.

В первом случае все записи в таблице маршрутизации статические. Администратор сети сам решает, на какие маршрутизаторы надо передавать пакеты с теми или иными адресами, и заносит соответствующие записи в таблицу маршрутизации вручную (например, с помощью утилиты route ОС UNIX или Windows NT).

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

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

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

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

  • случайная маршрутизация, когда прибывший пакет посылается в первом попавшемся направлении, кроме исходного;
  • лавинная маршрутизация, когда пакет широковещательно посылается по всем возможным направлениям, кроме исходного (аналогично тому, как мосты обрабатывают кадры с неизвестным адресом);
  • маршрутизация с учетом накопленного опыта, когда выбор маршрута осуществляется по таблице, но таблица строится так же, как и в случае моста путем анализа адресных полей поступающих пакетов.
АДАПТИВНАЯ МАРШРУТИЗАЦИЯ

Наибольшее распространение получили алгоритмы адаптивной (или динамической) маршрутизации. Они обеспечивают автоматическое обновление таблиц маршрутизации после изменения конфигурации сети. Используя протоколы адаптивных алгоритмов, маршрутизаторы могут собирать информацию о топологии связей в сети и оперативно реагировать на все изменения конфигурации связей. В таблицы маршрутизации обычно заносится информация об интервале времени, в течение которого данный маршрут будет оставаться действительным. Это время называют временем жизни маршрута (Time To Live, TTL).

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

В последнее время наметилась тенденция использовать так называемые серверы маршрутов: они собирают маршрутную информацию, а затем по запросам раздают ее маршрутизаторам. В этом случае последние либо освобождаются от функции создания таблицы маршрутизации, либо создают только часть таблицы. Взаимодействие маршрутизаторов с серверами маршрутов осуществляется по специальным протоколам, например Next Hop Resolution Protocol (NHRP).

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

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

  • дистанционно-векторные алгоритмы (Distance Vector Algorithm, DVA);
  • алгоритмы состояния каналов (Link State Algorithm, LSA).

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

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

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

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

Примерами протоколов на базе алгоритма состояния связей могут служить IS-IS (Intermediate System to Intermediate System) стека OSI, OSPF (Open Shortest Path First) стека TCP/IP и протокол NLSP стека Novell.

СТРУКТУРА INTERNET

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

Internet изначально строился как сеть, объединяющая большое количество независимых систем. С самого начала в его структуре выделяли магистральную сеть (core backbone network), а подключенные к магистрали сети рассматривались как автономные системы (autonomous system). Магистраль и каждая из автономных систем имели свои собственные административное управление и протоколы маршрутизации. Необходимо подчеркнуть, что деление на автономные системы не связано прямо с делением Internet на сети и домены имен. Автономная система объединяет сети, где маршрутизация осуществляется под общим административным руководством одной организации, а домен имен — единый для компьютеров (возможно, принадлежащих разным сетям), в которых назначение уникальных символьных имен происходит под таким же руководством. Естественно, область действия автономной системы и домена имен могут в частном случае совпадать, если одна организация выполняет обе указанные функции.

Маршрутизаторы, применяемые для формирования сетей и подсетей внутри автономной системы, называются внутренними шлюзами (interior gateway), а те, с помощью которых автономные системы подключаются к магистрали сети, — внешними шлюзами (exterior gateway). Магистраль сети также является автономной системой. Все автономные системы имеют уникальный 16-разрядный номер, который присваивается централизованно соответствующим административным органом Internet.

Используемые внутри автономных систем протоколы маршрутизации называются протоколами внутренних шлюзов (Interior Gateway Protocol, IGP), а протоколы обмена маршрутной информацией между внешними шлюзами и шлюзами магистральной сети — протоколами внешних шлюзов (Exterior Gateway Protocol, EGP). Внутри магистральной сети также может функционировать любой собственный внутренний протокол IGP.

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

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

Техника бесклассовой маршрутизации CIDR может значительно сократить объемы маршрутной информации, передаваемой между автономными системами. Так, если все сети внутри некоторой автономной системы начинаются с общего префикса, скажем 194.27.0.0/16, то внешний шлюз автономной системы должен делать объявления только об этом адресе, не сообщая отдельно о существовании внутри данной автономной системы, например сети 194.27.32.0/19 или 194.27.40.0/21, так как эти адреса агрегируются в адресе 194.27.0.0/16.

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

RIP и OSPF

Протокол RIP (Routing Information Protocol) — внутренний протокол маршрутизации дистанционно-векторного типа. Это один из наиболее ранних протоколов обмена маршрутной информацией, до сих пор чрезвычайно распространенный ввиду простоты реализации. Кроме варианта RIP для сетей TCP/IP версия RIP имеется и для сетей IPX/SPX компании Novell. Протокол RIP для IP представлен двумя версиями: первой и второй. RIP v.1 не поддерживает маски, т. е. он распространяет между маршрутизаторами только информацию о номерах сетей и расстояниях до них, а информацию о масках этих сетей не рассылает, считая, что все адреса принадлежат к стандартным классам A, B или С. Протокол RIP v.2 передает информацию о масках сетей, поэтому он в большей степени соответствует требованиям сегодняшнего дня.

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

Читайте также: