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

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

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

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

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

Формально метод маршрутизации в режиме “от одного ко многим” можно отнести к так называемой маршрутизации потоков данных в режиме “маршрутизации от источника” (Source Routing - SR).

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

Важно отметить, что в новой версии IP-протокола IPv6 в глобальной сети Internet наряду с распределенной маршрутизацией предусмотрена и SR-“маршрутизация от источника”.

Предельными случаями маршрутизации в режиме “от одного ко многим” (в частности, “от одного к одному”) является лавинная (“от одного ко всем”) маршрутизация.

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

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

- военные (оборонные) ТКС, в которых значительная часть узлов и каналов связи может быть уничтожена;

- одновременное обновление распределённых БД и БЗ в КС, обслуживаемых глобальной ТКС;

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

Модификация алгоритма Дейкстры для много-адресной маршрутизации в режиме «от одного ко многим»

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

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

Введём исходные данные и необходимые обозначения:

- множество соседних a_i узлов;

- множество узлов, обработанных алгоритмом;

()- множество узлов, обрабатываемых алгоритмом;

-остальные узлы ТКС;

- стоимость ребра ; w(i,i)=0; , если узлы a_i и a_j не соединены каналом связи непосредственно; , если эти два узла непосредственно соединены;

L(j) если , - оценка алгоритмом стоимости маршрута от узла-источника s₀ до узла n;

L(j) если, - стоимость кратчайшего маршрута от s₀ до n. (Для остальных j это значение L(j) не определено).

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

Алгоритм решения этой задач заключается в следующем:

Инициализация.

T₁ - пусто, T₁={s₀}, т.е. вначале множество обработанных узлов ТКС состоит только из узла-источника. Узлу-источнику сопоставляется пустой маршрут.

L(n)=w(s₀,n) для , т.е. начальные стоимости маршрутов к соседним узлам - это веса соответствующих ребер графа G, L(s₀)=0.

Все пусты.

Шаг алгоритма.

Выберем из T₁ узел ТКС с минимальной оценкой стоимости маршрута и поместим его в T_{0 ,} обозначая соответствующий ему маршрут как кратчайший. Иными словами, находим

:.(2)

При этом рассматриваем все рёбра графа ТКС с начальным узлом x.

Для каждого ребра (x, j) выполняется одно из трех действий:

А) если , то никаких действий не производится;

В) если , то j переводится из множества T₂ в T₁, причём j-ому узлу сопоставляется значение

, (3)

а также маршрут, состоящий из кратчайшего маршрута до x и ребра (x,j).

С) если , то производится новая оценка

,(4)

и j-ому узлу сопоставляется соответствующий оценке маршрут (либо прежний, либо согласно в В)).

Для каждого узла a_i, составляющего полученный кратчайший маршрут, кроме узла x, и всех групп узлов-получателей F, содержащих x, добавляем в узел a_j, такой, что ребро (a_i,a_j) входит в кратчайший до x маршрут.

Итерации алгоритма повторяются до тех пор, пока T₀ не станет равно s.

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

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис.2.1. Архитектура нейронной сети Хопфилда

Метод построения нейросетевой модели маршрутизатора

Для построения нейронной сети Хопфилда необходимо последовательно выполнить следующие шаги (этапы синтеза):

1) определить функцию активации для нейронов;

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

3) на объединении пространства входных данных и пространства решений задать энергетическую функцию нейронной сети вида

,(6)

обладающую следующими свойствами:

а) функция E является положительно определённой квадратичной формой,

b) глобальный минимум функции E соответствует решению поставленной задачи.

4) в соответствии с энергетической функцией (2.6) построить модель нейронной сети;

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

В качестве функции активации i-го нейрона выберем нелинейную функцию вида

, (7)

где z - суммарный входной сигнал i-го нейрона, а л_i - некоторый положительный коэффициент - параметр i-го нейрона .

Такая функция активации позволяет рассматривать динамику нейронной сети , т.е. описать её поведение во времени.

Пусть узлы графа ТКС проиндексированы, т.е. A={a_i}, i=1, .., N, где N - число узлов в ТКС. В качестве пространства решений сети Хопфилда Y будем рассматривать следующее множество:

(8)

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

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

1) Выходное значение нейронов должно быть либо 1, либо 0;

2) От узла-источника до каждого узла-получателя существует только один маршрут

(т.е. в каждой матрице должен быть только один маршрут);

3) В каждый маршрут в решении могут входить только существующие ребра графа ТКС.