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

РЕФЕРАТ

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

по курсу: «Сети передачи данных»

 

 

ОГЛАВЛЕНИЕ

 

 

ВВЕДЕНИЕ

Основная задача сетей - транспортировка информации от ЭВМ-отправителя  к ЭВМ-получателю. В большинстве  случаев для этого нужно совершить  несколько пересылок. Проблему выбора пути решают алгоритмы маршрутизации. Если транспортировка данных осуществляется дейтограммами, для каждой из них эта задача решается независимо. При использовании виртуальных каналов выбор пути выполняется на этапе формирования этого канала. В Интернет с его IP-дейтограммами реализуется первый вариант (если не рассматривать виртуальные сети), а в ISDN и ATM - второй. Для решения проблемы маршрутизации используются специальные устройства, называемые маршрутизаторами.

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

 

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

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

Предположим, что поток  данных между ЭВМ B и D, соединенных  через концентратор (К) весьма высок, что окажет ощутимое влияние на скорость обмена между ЭВМ А и С. Но этот факт довольно трудно выявить, находясь в ЭВМ А или С. Внешне это проявится лишь как повышенная задержка и пониженная пропускная способность участка А-С.

 

 

Рис. 1.1. Сеть, объединяющая 4 компьютера

1.1. Параметры оптимизации маршрута

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

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

1.2. Принцип оптимальности

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

Чтобы убедиться в  этом обозначим маршрут I-M R1, а M-J - R2. Если существует маршрут оптимальнее, чем R2, то он должен быть объединен с R1, чтобы образовать более оптимальный путь I-J, что противоречит исходному утверждению об оптимальности пути J-J. Следствием принципа оптимальности является утверждение, что оптимальные маршруты от всех отправителей к общему месту назначения образуют дерево, лишенное циклов

Такое дерево (называется sink tree) может быть не единственным, могут существовать другие деревья с теми же длинами пути. А это, в свою очередь означает, что любой пакет будет доставлен за строго ограниченное время, пройдя однократно определенное число маршрутизаторов. Маршрутизатор всегда является корнем этого дерева. В реальных условиях отдельные узлы могут выходить из строя или отключаться, что вызывает существенные видоизменения дерева. Разные маршрутизаторы могут иметь свои представления о том, какое из возможных деревьев выбрать. Это является причиной того, что путь из точки А в точку Б может не совпадать с путем из точки Б в точку А.

Главным параметром при  маршрутизации пакета в Интернет является IP-адрес его места назначения. Проблема оптимальной маршрутизации в современном Интернет, насчитывающем уже более миллиарда узлов, весьма сложна. Полная таблица маршрутов может содержать 109! записей, что не по плечу не только сегодняшним ЭВМ. Внешние маршрутизаторы обычно ищут оптимальный путь между сетями, а не отдельными ЭВМ. Тем не менее, размеры маршрутных таблиц растут экспоненциально и традиционные схемы и решения рано или поздно станут неэффективны. В общем случае для формирования оптимального маршрута нужно владеть исчерпывающей информацией обо всех сетевых сегментах. Это реально только для локальных сетей малого или среднего размеров. Следует также учитывать, что ситуация в сети постоянно меняется и маршрутизаторы для решения их задач имеют ограниченные ресурсы времени. На практике оптимизация осуществляется для ограниченной области сегментов, тогда и объем данных, подлежащих обработке, сокращается на многие порядки. Понятно, что компромиссы здесь неизбежны и результирующий маршрут в этом случае отнюдь не всегда будет оптимальным. Сбор данных о сетевых сегментах и маршрутах выполняется путем обмена этой информацией между маршрутизаторами. Переадресация же дейтограммы должна осуществляться за время 1-20 миллисекунд, которое зависит от длины очереди в буфере.

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

При географическом принципе каждая из стран получит равные по численности блоки IP-адресов (США  и Андорра получат равное число  адресов). Именно по этой причине при 32-битах адреса такая схема была неосуществима.

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

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

IP делит все ЭВМ  на маршрутизаторы и обычные  ЭВМ (host), последние, как правило,  не рассылают свои маршрутные  таблицы. Предполагается, что маршрутизатор  владеет исчерпывающей информацией  о правильных маршрутах (хотя  это и не совсем так). Обычная ЭВМ имеет минимальную маршрутную информацию (например, адрес маршрутизатора локальной сети и сервера имен). Автономная система может содержать множество маршрутизаторов, но взаимодействие с другими AS она осуществляет только через один маршрутизатор, называемый пограничным (border gateway, именно он дал название протоколу BGP). Пограничный маршрутизатор нужен лишь тогда, когда автономная система имеет более одного внешнего канала, в противном случае его функции выполняет порт внешнего подключения (gateway; поддержка внешнего протокола маршрутизации в этом случае не требуется). Здесь и далее используется достаточно простые на первый взгляд понятия внешних и внутренних каналов, внешних и внутренних протоколов или маршрутизаторов. Но такое разделение часто весьма условно. Поясню это на примере, представленном на рисунке 1.2.

Может показаться, что  проблема надумана, моя локальная  сеть является внутренней, а все, что  за ее пределами - внешнее. На рисунке  показаны семь маршрутизаторов (R1-R7), один из них связывает эту систему с Интернет. К каждому маршрутизатору подключена одна или несколько субсетей (иначе бы маршрутизаторы были просто не нужны). Следует помнить, что вся эта система маршрутизаторов после подключения становится равноправной частью Интернет. С топологической точки зрения задача маршрутизации сводится к построению оптимального пути от ЭВМ отправителя к ЭВМ-получателю.

 

 

Рис. 1.2. Локальная сеть

 

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

1.3. Метрики маршрутов

Если адресат достижим более чем одним путем, маршрутизатор  должен сделать выбор, этот выбор  осуществляется на основании оценки маршрутов-кандидатов. Обычно каждому  сегменту, составляющему маршрут, присваивается некоторая величина - оценка этого сегмента. Каждый протокол маршрутизации использует свою систему оценки маршрутов. Оценка сегмента маршрута называется метрикой. Здесь следует обратить внимание на то, что при выборе маршрута всем сегментам пути должны быть даны сопоставимые значения метрики. Недопустимо, чтобы одни сегменты оценивались числом шагов, а другие - по величине задержки в миллисекундах. В пределах автономной системы это обычно не создает проблем, ведь это зона ответственности одного администратора. Но в региональных сетях, где работает много администраторов, проблема выбора метрики может стать реальной трудностью. Именно по этой причине в таких сетях часто используется вектор расстояния, исключающий субъективность оценок метрики.

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

1.4. Широковещательный алгоритм оптимизации маршрута

Существуют и другие схемы, например, использующие широковещательные  методы адресации (flooding), где каждый приходящий пакет посылается по всем имеющимся исходящим каналам, за исключением того, по которому он получен. С тем чтобы исключить беспредельное размножение пакетов в заголовок вводится поле-счетчик числа шагов. В каждом узле содержимое поля уменьшается на единицу. Когда значение поля становится равным нулю, пакет ликвидируется. Исходное значение счетчика определяется размером субсети. Предпринимаются специальные меры против возможного зацикливания пакетов. Существует усовершенствованная версия широковещательной маршрутизации, называемая селективной широковещательной рассылкой. В этом алгоритме рассылка производится не по всем возможным направлениям, а только по тем, которые предположительно ведут в правильную сторону. Широковещательные методы не относятся к широко применимым. Но они используются там, где нужна предельно возможная надежность, например в военных приложениях, когда весьма вероятно повреждение тех или иных каналов. Данные методы могут использоваться лишь при формировании виртуального канала, ведь они всегда обеспечивают наикратчайший путь, так как перебираются все возможности. Если путь записывается в пакете, получатель может выбрать оптимальный проход и уведомить об этом отправителя.

Большинство алгоритмов учитывают топологию связей, а не их качество (пропускную способность, загрузку и пр.). Но существуют подходы к решению проблемы статической маршрутизации, учитывающие как топологию, так и загрузку (flow-based routing). В некоторых сетях потоки между узлами относительно стабильны и предсказуемы. В этом случае появляется возможность вычислить оптимальную схему маршрутов заранее. Здесь на основе теории массового обслуживания производится оценка средней задержки доставки для каждой связи. Топология маршрутов оптимизируется по значению задержки доставки пакета. Исходными данными при расчете считается описание топологии связей, матрица трафика для всех узлов T_i,j (в пакетах в секунду) и матрица пропускных способностей каналов B_i,j в битах в секунду. Задержка t для каждой из связей оценивается по формуле 1.1.

 

ti,j = 1/(p*Bi,j - Ti,j)	(1.1)

где i и j - номера узлов.

1/Р - среднее значение  ширины пакета в битах, произведение p*B_i,j выражается в пакетах в секунду, а t измеряется в мсек. Сформировав матрицу t_i,j, можно получить граф кратчайших связей. Так как вычисления производятся не в реальном масштабе времени, особых трудностей здесь не возникает.

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

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

Рассмотрим для примера  сеть, изображенную на рис. 1.3.

 

 

Рис. 1.3. Схема для иллюстрации  методики составления маршрутных таблиц, G1, G2, G3 – Маршрутизаторы

 

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

Примитивная таблица  маршрутизации для приведенного примера может иметь вид (для маршрутизатора g2):

Таблица 1.1

Таблица маршрутизации  для маршрутизатора G2

Сеть-адресат	Маршрут к этой сети
193.0.0.0	Прямая доставка
193.148.0.0	Прямая доставка
192.0.0.0	Через адрес 193.0.0.1
192.166.0.0	Через адрес 193.148.0.7