Курс лекций "Сетевым технологиям"

Протоколы маршрутизации 

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

Классификация протоколов маршрутизации

Назначение  протоколов маршрутизации

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

Нетрудно  заметить, что задача продвижения  пакета от сети источника до сети назначения в каждом маршрутизаторе естественно распадается на две задачи:

• обработка пакета с помощью имеющейся таблицы маршрутизации;
• построение таблицы маршрутизации.

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

Маршрутизация без таблиц

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

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

Другой  вариант маршрутизации без таблицы  — это маршрутизация, управляемая событиями (Event Dependent Routing), когда пакет к определенной сети назначения посылается по маршруту, который уже приводил ранее к успеху (для данного адреса назначения). Это достаточно эффективный метод маршрутизации, но он требует наличия обратной связи, чтобы маршрутизатор-отправитель мог фиксировать факт успеха доставки пакета. Подобный метод маршрутизации использовался на этапе становления Интернета, когда перед отправкой пакета данных предварительно всем или нескольким соседям посылались эхо-запросы по протоколу IСМР, а затем на основании времени прихода эхо-ответов выбирался сосед, у которого это время минимально. Данный способ хорошо зарекомендовал себя в сетях, работающих по протоколам с предварительным установлением соединения. Запрос на установление соединения может посылаться нескольким соседям, а подтверждение установления соединения посылается тому соседу, который первым пришлет ответ.

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

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

Адаптивная  маршрутизация

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

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

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

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

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

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

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

Дистанционно-векторные  алгоритмы

В дистанционно-векторных алгоритмах (Distance Vector Algorithms, DVA) каждый маршрутизатор периодически и широковещательно рассылает по сети вектор, компонентами которого являются расстояния от данного маршрутизатора до всех известных ему сетей. Пакеты протоколов маршрутизации обычно называют объявлениями (advertisements), так как с их помощью маршрутизатор объявляет остальным маршрутизаторам известные ему сведения о сети. Под расстоянием обычно понимается число хопов. Возможна и другая метрика, учитывающая не только число промежуточных маршрутизаторов, но и время прохождения пакетов по сети между соседними маршрутизаторами. При получении вектора от соседа маршрутизатор наращивает указанные в векторе расстояния до сетей на величину расстояния до данного соседа, добавляет к нему информацию об известных ему других сетях, о которых он узнал непосредственно (если они подключены к его портам) или из аналогичных объявлений других маршрутизаторов, а затем снова рассылает новое значение вектора по сети. В конце концов, каждый маршрутизатор узнает информацию обо всех имеющихся в интерсети сетях и о расстоянии до них через соседние маршрутизаторы. Затем он выбирает из нескольких альтернативных маршрутов к каждой сети тот маршрут, который обладает наименьшей метрикой. Маршрутизатор, передавший информацию о данном маршруте, отмечается в таблице маршрутизации как следующий маршрутизатор (next hop). Для того чтобы адаптироваться к изменениям состояния сети, маршрутизаторы продолжают периодически сообщать друг другу информацию о наилучших маршрутах ко всем известным сетям. Если информация о какой-нибудь сети перестала поступать в маршрутизатор в течение определенного времени, то соответствующая запись из таблицы маршрутизации удаляется.

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

Наиболее  распространенным протоколом, основанным на дистанционно-векторном алгоритме, является протокол RIP, который распространен в двух версиях — RIP IP, работающий с протоколом IP, и RIP IPX, работающий с протоколом IPX.

Алгоритмы состояния связей

Алгоритмы, состояния связей (Link State Algorithms, LSA) обеспечивают каждый маршрутизатор информацией, достаточной для построения точного графа связей сети. Все маршрутизаторы работают на основании одинаковых графов, что делает процесс маршрутизации более устойчивым к изменениям конфигурации. «Широковещательная» рассылка (то есть передача пакета всем непосредственным соседям маршрутизатора) имеет место только при изменениях состояния связей, что происходит в надежных сетях не так часто. Вершинами графа являются как маршрутизаторы, так и объединяемые ими сети. Распространяемая по сети информация состоит из описания связей различных типов: маршрутизатор-маршрутизатор, маршрутизатор—сеть.

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

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

Применение  нескольких протоколов маршрутизации

В одной  и той же сети могут одновременно работать несколько разных протоколов маршрутизации (рис. 1). Это означает, что на некоторых (не обязательно всех) маршрутизаторах сети установлено и функционирует несколько протоколов маршрутизации, но при этом, естественно, по сети взаимодействуют только одноименные протоколы. То есть если маршрутизатор 1 поддерживает, например, протоколы RIP и OSPF, маршрутизатор 2 — только RIP, а маршрутизатор 3 — только OSPF, то маршрутизатор 1 будет взаимодействовать с маршрутизатором 2 по протоколу RIP, с маршрутизатором 2 — по OSPF, а маршрутизаторы 2 и 3 вообще непосредственно друг с другом взаимодействовать не смогут.