Нейросетевая маршрутизация информационных потоков

Нейронные сети (НС) представляют собой эффективную вычислительную модель, позволяющую распознавать образы или аппроксимировать функции любой сложности, основываясь на неполной информации [25, 35–40, 69].

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

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

Для решения задач маршрутизации используются в основном два вида нейронных сетей: сети перцептронного типа и сети Хопфилда. Однако решения, вычисляемые сетями перцептронного типа, как правило, неустойчивы. Поэтому в данной работе рассматриваются нейронные сети Хопфилда (НСХ) [25, 26, 69, 77–80].

Построим нейронную сеть для мульти-агентной модели, предложенной в 7.3.

Рассмотрим оптимизационную задачу (7.9)-(7.10). Данная задача при выполнении условий I-IV п.7.3.2 имеет, по крайней мере, одно решение. При этом для всех решений значение вектора распределения нагрузок ρ будут одними и теми же.

Достаточным условием решения оптимизационной задачи (7.9)-(7.10) с линейными ограничениями при помощи НСХ, является строгое монотонное возрастание минимизируемой функции ([76]).

Рассмотрим систему (7.7). Так как для конкретного множества значением функции Φ _D является положительная константа, то её можно перенести в левую часть, не меняя условий задачи, т.е.:

. (7.17)

Введём матрицу Δ вида

, (7.18)

где δ _ij – доля интенсивности информационного потока x_j, которая приходится на дугу i.

Так как ρ _l = ρ _l (x), то задачу (7.9)-(7.10) можно переформулировать следующим образом:

(FΦ _D) → min (7.19)

при ограничениях

. (7.20)

В качестве возможных решений задачи (7.19), (7.20) будем искать векторы (ρ, x). Без потери общности можно считать, что и .

Построим энергетическую функцию E = E(ρ, x) для НСХ, решающей оптимизационную задачу (7.19)-(7.20). Потребуем, чтобы функция E была квадратичной формой от (ρ, x).

Сначала рассмотрим функцию E₀:

, (7.21)

где α _ij - некоторые положительные константы, причём α ₁₁ – достаточно малое число [76]. Однако E₀ не является квадратичной формой, так как в первой сумме присутствуют нелинейные элементы T _l (ρ _l). Заменим первую сумму в (7.21) на квадрат линейной комбинации ρ. Тогда получим следующую энергетическую функцию для НСХ:

(7.22)

где и достаточно малы.

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

Замена (7.21) на (7.22) допустима, поскольку для двух строго возрастающих функций с одинаковыми областями определения (задаваемыми системой (7.20)) экстремумы достигаются в одинаковых точках.

Таким образом, синтезирована модель НСХ, состоящая из |E|+|Π | нейронов, где Π - упорядоченное множество всех маршрутов для всех пар узлов, а E – множество дуг графа, соответствующего ТКС. Эта модель НСХ адаптирована к условиям централизованной схемы мульти-агентной маршрутизации.

Теперь рассмотрим задачу локальной оптимизации (7.11). При выполнении условий I-IV параграфа 7.3.2 эта задача имеет, по крайней мере, одно решение. Рассмотрим первое уравнение системы (7.11). В силу второго и четвёртого неравенств системы получим, что для любого x справедливо неравенство вида

(7.23)

Отсюда следует, что неотрицательная функция (T(x)-Γ y)x принимает нулевые значения (с учётом остальных ограничений) в точках возможных решений неравенств (7.23). Это означает, что точки минимумов данной функции совпадают с решениями оптимизационной задачи (7.11). С учётом (7.23) и того, что

(7.24)

переформулируем задачу (7.11) следующим образом:

(7.25)

Задачу (7.25) можно свести к следующей задаче [76]:

(7.26)

Заметим, что z_p=0, если T_p(x) = (Γ A(x))_p. Поэтому с учётом неравенств x_p≥ 0 и z_p> 0 получим, что

T_p(x)> (Γ A(x))_p и x_p=0. (7.27)

Построим НСХ, решающую оптимизационную задачу (7.26). В качестве возможных решений будем искать векторы (x, z). Так же, как и в предыдущей задаче, будем полагать, что и . Из первого равенства в системе ограничений следует, что

(7.28)

Таким образом, энергетическая функция E для НСХ будет иметь следующий вид:

(7.29)

Соответствующая (7.29) модель НСХ состоит из 2|Π | нейронов [69], где Π - упорядоченное множество всех маршрутов для всех пар узлов, и адаптирована к условиям задачи локальной оптимизации для распределённой схемы мульти-агентной маршрутизации.

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

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

7.5. Многопотоковая маршрутизация

7.5.1 Цели и задачи многопотоковой маршрутизации

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

В простейших случаях, когда изменения параметров или структуры ТКС незначительны, для этого достаточно сетевых решений, предоставляемых существующими протоколами IP­-маршрутизации [1-5]. Однако при этом не гарантируется своевременность ответов на запросы пользователей ТКС вследствие больших запаздываний.

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

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

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

Будем называть многопотоковой такую модель маршрутизации, которая для пересылки потоков данных использует К (К ³ 2)маршрутов.

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

7.5.2 Особенности многопотоковой маршрутизации в сетях с переменной структурой

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

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

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

1) существует возможность (вероятность) выхода из строя каналов связи и узлов ТКС или возникновения новых узлов и каналов связи, изменяющих структуру и параметры ТКС;

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

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

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

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

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

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

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

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

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

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

Однако распределённая К-потоковая маршрутизация имеет два существенных отличия:

- на каждом шаге алгоритма выбираются оптимальные или близкие к оптимальным (субоптимальные) маршруты;

- существует и используется механизм предотвращения образования циклических маршрутов.

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

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

7.5.3. Классификация методов многопотоковой маршрутизации

По способу передачи пакетов данных алгоритмы многопотоковой маршрутизации можно разбить на четыре типа [1, 69]:

- резервирующие алгоритмы;

- избыточные алгоритмы;

- распределяющие алгоритмы;

- гибридные (комбинированные) алгоритмы.

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

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

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

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

При решении задачи К-потоковой маршрутизации можно выделить два типа задач:

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

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

7.5.4 Постановка задачи К-потоковой маршрутизации

Рассмотрим графовую модель ТКС

G = G(A, R, W), (7.30)

где A – множество вершин графа G, соответствующих узлам ТКС, R – множество однонаправленных дуг G, соответствующие каналам связи, а W – множество весов дуг, соответствующих некоторым числовым характеристикам-весам каналов связи ТКС, определяющим их «стоимость».

Стоимость маршрута определяется как суммарная стоимость составляющих его дуг.

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

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

Введем следующие обозначения. Пусть все несамопересекающиеся маршруты из s в f проиндексированы. Тогда обозначим i -й маршрут из s в f через i_sd, а его стоимость через w(i_sf). Если i -й и j -й маршруты не пересекаются, то будем обозначать это следующим образом: .

Определим всевозможные множества из К непересекающихся маршрутов из s в d. Пусть все маршруты из узла s в узел f проиндексированы. Обозначим i-й маршрут из s в f как i_sf. Тогда любое множество K непересекающихся маршрутов выглядит следующим образом:

. (7.31)

Зададим над этими множествами аддитивный функционал качества Q вида

. (7.32)

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

(7.33)

Будем называть оптимизационную задачу (3.4) с заданными ограничениями К-потоковой задачей прокладки маршрутов. Решение этой задачи достаточно для синтеза избыточных и резервирующих алгоритмов многопотоковой маршрутизации.

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

Пусть задан граф G вида (7.30) и на нём определены узел-источник s и узел-получатель f. Назовём пару узлов (s, d) l -связной, если на графе ТКС G существует l непересекающихся маршрутов от s к d.

Пусть из узла-источника s в узел-получатель f проложено несколько (возможно, пересекающихся друг с другом) маршрутов. Обозначим его через Р.

Надёжностью передачи данных от узла-источника s к узлу-получателю f на множестве маршрутов Р будем называть максимально возможное значение связности пары (s, f) на подграфе графа G, заданном множеством проложенных маршрутов. Например, если для выделенного множества маршрутов пара (s, f) l -связна, но не (l +1)-связна, то надёжность передачи данных от s к f на множестве Р равна m.

Обозначим надёжность передачи данных из s в f на множестве Р через T( Р )_sf.

Оптимизационное решение К-потоковой задачи передачи данных сводится к следующему.

Требуется построить множество несамопересекающихся маршрутов из s в d таких, что выполняются следующие условия:

a) суммарная стоимость несамопересекающихся маршрутов минимальна;

b) надёжность передачи данных по этим маршрутам из любого содержащегося в них узла к узлу d не меньше К (на практике К, как правило, равно 2 или 3);

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

(7.34)

7.5.5. Критерии существования решений задачи К-потоковой маршрутизации

Прежде всего введём определения двух понятий, необходимых для формулировки критериев существования решений задачи К-потоковой маршрутизации [29–31].

Пусть на графе ТКС G = G(A, R, W) заданы узел-источник s и узел-получатель f.

Определение 7.1. Минимальным разрезом графа ТКС G для пары узлов (s, f) называется минимальное число однонаправленных рёбер, при исключении которых из графа G, не останется ни одного маршрута из s в f.