3444 МАРШРУТИЗАЦИЯ В СЕТЯХ

  1. Маршрутизация пакетов в глобальной
    сети связи

 

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

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

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

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

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

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

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

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

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

2. Адаптивная распределенная маршрутизация

 

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

Рис. 1

 

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

Состояние таблиц маршрутизации до первого обмена служебной информацией представлено в таб. 1.

В таблицах применены обозначения: S – номер узла назначения, Р – номер порта, N – количество промежуточных узлов до узла, к которому подключен абонент.