Методы статической и много-адресной маршрутизации информационных потоков

6.1. Классификация методов маршрутизации и управления потоками данных

Задачи маршрутизации потоков данных по существу возникают во всех глобальных ТКС. Методы решения этих задач для IP-сетей и АТС-сетей могут значительно различаться. Одни из этих методов сводятся к геометрическому планированию оптимальных маршрутов (например, кратчайших маршрутов – Shortest Path), другие – к потоковой маршрутизации (Multicommodity Flow) с учётом текущей загрузки каналов связи [1–9, 20, 69].

Описание и классификация традиционных методов и средств маршрутизации потоков данных в ТКС приводятся в ряде монографий и статей (см., например, [1–9, 20, 69]).Однако модели и методы адаптивной много-адресной и многопотоковой маршрутизации, ориентированные на глобальные ТКС нового поколения, остаются мало изученными и недостаточно обоснованными. Этот же вывод можно сделать по отношению к нейросетевым и мульти-агентным технологиям оптимальной маршрутизации и адаптивного управления потоками данных в реальном времени в сложных современных и перспективных глобальных ТКС [29, 30].

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

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

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

Статические методы формируют оптимальные маршруты в статических ТКС с фиксированной структурой (топологией связей) и постоянными параметрами (весами) каналов связи [1–3].

Ряд статических задач маршрутизации базируется на моделях потокового типа [1, 6, 20]. Для решения этих задач используются методы нелинейного программирования и градиентные алгоритмы поиска оптимальных маршрутов. Эти методы позволяют вычислять оптимальные маршруты сразу для нескольких пар узлов “источник-получатель”.

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

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

По признаку априорного или апостериорного вычисления маршрутов при практической реализации процессов маршрутизации принято различать методы, основанные на заранее (априори) вычисленных маршрутах (Pre-Computed) и методы, основанные на вычислении маршрутов по запросу (требованию) пользователя (On-Demand) [1, 6, 20].

Априорное вычисление маршрутов удобно для статических ТКС [1, 20]. Такие методы относятся к классу “квази-статических алгоритмов”. Важно отметить, что маршруты могут быть некорректными или нереализуемыми из-за возможных изменений топологии ТКС.

При апостериорной маршрутизации по запросу пользователя вычисление маршрутов производится в реальном времени, начиная с момента запроса. При этом возникает задержка установки соединения между узлом-источником и узлом-получателем, равная времени вычисления маршрута. Кроме того, при маршрутизации “по запросу” может использоваться устаревшая (ещё не обновлённая) информация о ТКС. Поэтому методы апостериорной маршрутизации относятся к классу “квази-динамических алгоритмов”. К ним можно отнести и метод “вычисления маршрутов с задержкой”, когда процесс маршрутизации для нескольких запросов начинается только после получения (естественно, с некоторой задержкой) обновлённой информации о текущем состоянии динамической ТКС [20, 69].

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

В свою очередь методы априорного вычисления маршрутов подразделяются на методы вычисления маршрутов в узле-источнике (Source Routing), т.е. до начала установки соединения, и методы типа “прыжок-за-прыжком” (Hop-by-Hop), вычисляющие маршрут в процессе установки соединения.

По признаку учёта (или неучёта) моментов появления запросов на установку или разъединение линии связи методы маршрутизации классифицируются на временно-зависимые и временно-независимые (инвариантные).

По признаку разветвлённости (множественности) маршрутов между узлом-источником и узлом-получателем данных методы маршрутизации подразделяются на однопотоковые и многопотоковые.

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

Каждому из указанных методов маршрутизации присущи определённые достоинства и недостатки. Например, в рамках статической однопотоковой маршрутизации можно использовать сравнительно простые известные алгоритмы (алгоритм Дейкстры и др. [1–3]) планирования оптимального маршрута.

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

В общем случае многопотоковая (альтернативная) динамическая маршрутизация более предпочтительна, чем статическая однопотоковая (неразветвлённая) маршрутизация, поскольку она более полно использует сетевые ресурсы ТКС. Однако многопотоковая динамическая или адаптивная маршрутизация значительно сложнее, чем однопотоковая статическая маршрутизация.

Важным для практики частным случаем многопотоковой маршрутизации является маршрутизация с априори фиксированным ограничением на число К (например, К =3) каналов связи, исходящих из каждого узла ТКС. Назовём такую разновидность альтернативной маршрутизации К –потоковой [29, 69].

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

С точки зрения теории и архитектуры сетевых систем управления (ССУ) глобальных ТКС важное значение имеет классификация методов маршрутизации на централизованные, децентрализованные и мульти-агентные [29, 69].

Централизованная маршрутизация основана на сетевом менджменте и вычислении маршрутов в центральном узле-маршрутизаторе ТКС.

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

Мульти-агентная маршрутизация сочетает в себе достоинства централизованной и децентрализованной маршрутизации и основывается на теории мульти-агентных систем и технологий [29, –31, 57, 69, 95].

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

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

- использование средств математического и компьютерного моделирования не требует привлечения значительных сетевых и вычислительных ресурсов и позволяет провести всесторонний анализ и обоснованный выбор перспективных алгоритмов маршрутизации в процессе концептуального проектирования ССУ глобальных ТКС;

- математическое моделирование (в отличие от имитационного и полунатурного моделирования) не требует значительных финансовых и временных затрат для обоснованного выбора наиболее эффективных алгоритмов и протоколов маршрутизации потоков данных в глобальных ТКС нового поколения.

Однако окончательная отладка перспективных алгоритмов и протоколов маршрутизации для ССУ нового поколения должна осуществляться на стендах имитационного и натурного моделирования управляемых потоков данных в глобальных ТКС в реальном времени.

Анализ научно-технической литературы в области управления потоками данных в глобальных ТКС свидетельствует о том парадоксальном факте, что в само понятие “маршрутизация” (Routing) различные авторы вкладывают разный смысл [1, 20].

Чаще всего под термином “маршрутизация” понимается либо “вычисление (планирование) маршрута“ (Route Calculation), либо “протокол маршрутизации“ (Routing Protocol), либо “подсистема маршрутизации”, т.е. “маршрутизатор” (Routing Sub-System). Очевидно, что эти краткие семантические интерпретации термина “маршрутизация” отнюдь не эквивалентны и порождают значительную путаницу и противоречия в восприятии опубликованных результатов исследований задач, методов и средств маршрутизации потоков данных в ТКС.

Несмотря на многозначность понятия “маршрутизация”, важнейшим его аспектом является именно “вычисление (планирование) маршрутов”. Другие аспекты этого понятия связаны с передачей информации о “вычисленном” маршруте и его практической (программной или аппаратной) реализацией в ТКС.

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

Таким образом, под термином “маршрутизация” следует понимать прежде всего планирование (вычисление) одного или нескольких маршрутов передачи данных от узла-источника к узлу-получателю по запросу (заявке) пользователей глобальной ТКС, которые удовлетворяют следующим естественным требованиям [29, 69]:

- являются допустимыми, т.е. связывают узел-источник с узлом-получателем данных с учётом конкретной топологии ТКС;

- оптимизируют локальный или глобальный функционал качества сетевой маршрутизации;

- удовлетворяют ограничениям по качеству обслуживания (QoS) пользователей, обратившихся с запросами в ТКС.

В зависимости от используемых принципов управления и архитектур ССУ вычисление (планирование) оптимальных маршрутов и установка соответствующих соединений узлов и каналов связи ТКС может производиться по-разному. Так, например, в АТМ-сетях при централизованном управлении под контролем администратора или оператора ТКС устанавливается постоянное (фиксированное) виртуальное соединение (Permanent Virtual Circuit), при децентрализованном управлении устанавливается коммутируемое виртуальное соединение (Switched Virtual Circuit), а при комбинированном (в частности, мульти-агентном) управлении устанавливается гибкое виртуальное соединение (Soft-Permanent Virtual Connection).

Важно отметить, что при установке соединений указанных типов в АТМ-сетях используется алгоритм управления (контроля) доступом соединения (Connection Admission Control – CAC), который в каждом узле спланированного маршрута проверяет наличие необходимых ресурсов (загруженность входных и выходных буферов, пропускная способность каналов связи и т.п.) с точки зрения заданных требований по качеству (QoS) обслуживания запросов (заявок) пользователей глобальной ТКС.

Общая задача управления потоками данных в глобальных ТКС с пакетной коммутацией и маршрутизацией передаваемой информации распадается на две взаимосвязанные задачи [29, 69]:

1) планирование (вычисление), оптимизация и адаптация маршрутов передачи потоков данных узла-источника (отправителя) запроса или данных к узлу-получателю (адресату);

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

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

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

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

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

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

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

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

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

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

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

Необходимость в динамической и адаптивной маршрутизации потоков данных в ТКС возникает в следующих случаях:

1. Изменение стоимости каналов связи ТКС (например, при их замене);
2. Отказ (выход из строя) в ТКС одного или нескольких каналов связи;
3. Добавление (ввод в строй) в ТКС новых каналов связи;
4. Отказ (выход из строя) одного или нескольких узлов ТКС;
5. Добавление (ввод в строй) в ТКС новых узлов;
6. Перегрузка каналов связи ТКС;
7. Перегрузка (переполнение) буферов узлов ТКС.

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

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

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

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

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

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