Маршрутизация пакетов в сетях

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

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

Выбор маршрутов в узлах связи ТКС производится в соответствии с реализуемым алгоритмом (методом) маршрутизации.

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

Основные цели маршрутизации заключаются в обеспечении:

• минимальной задержки пакета при его передаче от отправителя к получателю;

• максимальной пропускной способности сети, что достигается, в частности, нивелировкой загрузки линий связи ТКС;

• максимальной защиты пакета от угроз безопасности содержащей­ся в нем информации;

• надежности доставки пакета адресату;

• минимальной стоимости передачи пакета адресату.

Различают следующие способы маршрутизации.

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

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

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

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

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

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

Эффективность алгоритмов маршрутизации оценивается следу­ющими показателями:

• временем доставки пакетов адресату;

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

• затратами ресурсов в узлах связи (временем работы коммуника­ционной ЭВМ, емкостью памяти). Факторы, снижающие эффективность алгоритмов маршрутизации:

• передача пакета в узел связи, находящийся под высокой нагрузкой;

• передача пакета в направлении, не приводящем к минимальному времени его доставки;

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

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

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

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

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

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

Локальная адаптивная маршрутизация основана на использова­нии информации, имеющейся в данном узле и включающей: таблицу маршрутов, которая определяет все направления передачи пакетов из этого узла; данные о состоянии выходных линий связи (работают или не работают); длину очереди пакетов, ожидающих передачи. Ин­формация о состоянии других узлов связи не используется. Таблица маршрутов определяет кратчайшие маршруты, обеспечивающие до­ставку пакета адресату за минимальное время. Преимущество тако­го метода состоит в том, что принятие решения о выборе маршрута производится с использованием самых последних данных о состоянии узла. Недостаток метода заключается в его «близорукости», посколь­ку выбор маршрута осуществляется без учета глобального состояния всей сети. Следовательно, всегда есть опасность передачи пакета по перегруженному маршруту.

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

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

Гибридная адаптивная маршрутизация основана на использова­нии таблиц маршрутов, рассылаемых ЦМ узлам сети, в сочетании с анализом длины очередей в узлах. Следовательно, здесь реализуются принципы централизованной и локальной маршрутизации. Гибридная маршрутизация компенсирует недостатки централизованной (марш­руты, формируемые центром, являются несколько устаревшими) и локальной («близорукость» метода) маршрутизации и воспринимает их преимущества: маршруты центра соответствуют глобальному со­стоянию сети, а учет текущего состояния узла обеспечивает своевре­менность решения задачи.