4-1маршрутизация (Лекции по Сетевым технологиям)

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

Протоколы маршрутизации предназначены для автоматического построения таблиц маршрутизации, на основе которых происходит продвижение пакетов сетевого уровня. Протоколы маршрутизации, в отличие от сетевых протоколов, таких как 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). Для того чтобы адаптироваться к изменениям состояния сети, маршрутизаторы продолжают периодически сообщать друг другу информацию о наилучших маршрутах ко всем известным сетям. Если информация о какой-ни­будь сети перестала поступать в маршрутизатор в течение определенного време­ни, то соответствующая запись из таблицы маршрутизации удаляется.

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