Результат интеллектуальной деятельности: СПОСОБ МНОГОПУТЕВОЙ МАРШРУТИЗАЦИИ С ИСПОЛЬЗОВАНИЕМ РАСЩЕПЛЕНИЯ ПОТОКА ТРАФИКА ДАННЫХ

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

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

Известен способ междоменной многопутевой маршрутизации (патент US 20060274718 А1 от 07.12.2006), включающий в себя этапы, на которых распределяют трафик данных по множеству междоменных линий связи от первого узла первой пакетно-ориентированной сети к узлу назначения второй пакетно-ориентированной сети, вычисляют альтернативный путь между первой пакетно-ориентированной сетью и второй пакетно-ориентированной сетью через первый узел первой пакетно-ориентированной сети, при этом вычисление производится первым узлом и пограничным узлом второй пакетно-ориентированной сети, которая доступна по нескольким междоменным линиям связи, данные междоменные линии связи соединяют первую пакетно-ориентированную сеть с сетью, в которую пересылается трафик данных для узла назначения, распределяют пакеты по множеству линий связи, каждая из которых соединяет первую сеть с одной из дополнительных сетей через дополнительный узел соответствующей дополнительной сети, вычисляют пути маршрутизации к месту назначения за пределами первой пакетно-ориентированной сети путем объединения дополнительных узлов, способных осуществлять маршрутизацию к месту назначения, с целью сформировать единый виртуальный узел, вычисляют распределение метрик путей для маршрутизации до места назначения с помощью одного виртуального узла.

Известен способ ограниченной многопутевой маршрутизации (патент US 20030099194 А1 от 29.12.2003), включающий в себя этапы, на которых устанавливают состояние сети MPLS и требования к трафику по каждой линии связи, рассчитывают количество распределений для каждого требования, предъявляемого к трафику для каждой линии связи, и минимальное значение пропускной способности каждой линии связи а, вычисляют скорость передачи трафика, в котором степень использования сетевого ресурса минимизирована к минимальному значению пропускной способности линии связи а, используя рассчитанное количество распределений для каждого требования, предъявляемого к трафику для каждой линии связи, вычисляют множество путей, соответствующих требованиям входного трафика и коэффициентов разделения трафика на множество путей с учетом рассчитанной скорости трафика.

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

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

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

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

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

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

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

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

Заявленные объекты изобретения поясняются чертежами, на которых:

на фиг. 1 - блок-схема способа многопутевой маршрутизации с использованием расщепления потока трафика данных;

на фиг. 2 - структурная схема сети связи;

на фиг. 3 – КМУФ, найденный на третьем шаге;

на фиг. 4 – КМУФ, найденный на четвертом шаге.

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

Оконечные и промежуточные системы представляют собой абстрактное представление технических средств, удовлетворяющих тем требованиям стандартов ВОС, которые необходимы для функционирования открытой системы (ГОСТ Р ИСО 8648-98).

Расщепление логических соединений, расщепление (Splitting) - функция, выполняемая логическим объектом-отправителем уровня и использующая несколько соединений смежного нижнего уровня для обеспечения одного соединения данного уровня (см. ГОСТ 24402-88).

Рекомбинация логических соединений, рекомбинация (Recombining) - функция, выполняемая логическим объектом-получателем уровня и использующая несколько соединений смежного нижнего уровня для обеспечения одного соединения данного уровня (см. ГОСТ 24402-88).

Маршрутизация данных (Routing) - функция уровня взаимосвязи открытых систем, преобразующая наименование или адрес логического объекта уровня в маршрут для достижения этого объекта уровня (см. ГОСТ 24402-88).

Протокольный блок данных - блок данных, передаваемый между логическими объектами одного и того же уровня (см. ГОСТ 24402-88).

Реализация заявленного способа заключается в следующем (фиг. 1).

101. Принимают промежуточной системой потоки трафика данных от оконечной системы отправителя, каждый поток трафика данных представлен в виде протокольных блоков данных или байтов.

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

В качестве примера рассмотрим сеть связи, представленную на фиг. 2, информация о которой записана с помощью двух матриц смежности, выражения (1)-(2). Определим требования по надежности направления связи из узла сети 1 в узел сети 6 на уровне 0,9. Найдем минимально необходимое число маршрутов между 1-ми 6-м узлом сети связи в порядке уменьшения их надежности (в формировании маршрута участвуют только ребра графа), обеспечивающих требования по надежности направления связи.

Матрица смежности, в которой хранятся номера вершин и ребер их соединяющих (если элемента нет, тогда его номер равен нулю) имеет вид

Матрица смежности, в которой хранятся вероятности работоспособного состояния узлов сети и линий их соединяющих (если элемента нет или он находится в неработоспособном состоянии, тогда его вероятность работоспособного состояния равна нулю)

Задачу нахождения k надежных маршрутов от x_1,s к х_1,t можно свести к задаче нахождения k кратчайших маршрутов от x_l,s к х_1,t взяв в качестве эквивалентного веса ребра (х_1,i x_1,t) величину

где pr_i,j - это вероятность работоспособного состояния ребра (х_1,i x_1,j).

В этом случае k кратчайших маршрутов от х_1,s к x_l,t с матрицей эквивалентных весов будут в то же время и наиболее надежными маршрутами с матрицей вероятностей При этом надежность соответствующих маршрутов определяется по формуле

где prm_s,t,r - это вероятность работоспособного состояния r-го надежного маршрута от х_1,s к х_1,t;

mcm_s,t,r - эквивалентный вес r-го надежного маршрута от x_l,s к x_l,t.

Взяв в качестве эквивалентного веса ребра (x_1,i x_1,j) - величину, рассчитанную по формуле (3), получим матрицу смежности, в которой хранятся эквивалентные веса узлов сети и линий их соединяющих.

Матрица смежности, в которой хранится метрика вершин и ребер их соединяющих (если элемента нет, тогда его длина равна бесконечности), рассчитанные по формуле (3), имеет вид

Кратчайший маршрут успешного функционирования (КМУФ) между вершиной x_1,s и x_1,t - это такая последовательность элементов графа (вершин или ребер или вершин и ребер), когда нельзя ни один элемент изъять, не нарушив связности между вершинами х_1,s и х_1,t.

Ветвь дерева состояний - это последовательность элементов сети (узлов и/или соединительных линий), которая описывает группу состояний сети связи (последний элемент ветви это длина минимального КМУФ для этой группы состояний, если такового КМУФ не существует, тогда длина равна бесконечности).

Пример ветви дерева состояний

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

Пример формирования ответвления от ветви дерева состояний (см. выражение (6))

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

Исходная ветвь дерева состояний

Список возможных ответвлений от исходной ветви

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

Ниже представлены новые ветви дерева состояний для списка ответвлений (см. выражения (9-11))

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

Шаг 1. Список конкурирующих ветвей на первом шаге

Список ответвлений на первом шаге не содержит элементов

Список конкурирующих маршрутов на первом шаге

Список КМУФ на первом шаге

Шаг 2. Список конкурирующих ветвей на втором шаге

Список ответвлений на втором шаге

Список конкурирующих маршрутов на втором шаге

Список КМУФ на втором шаге

Шаг 3. Список конкурирующих ветвей на третьем шаге

Список ответвлений на третьем шаге

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

Список КМУФ на третьем шаге

На третьем шаге получаем первый КМУФ (фиг. 3). В списке конкурирующих ветвей находим строку с наименьшей длиной. На ее основе формируем список ответвлений и удаляем эту ветвь из списка конкурирующих ветвей дерева состояний. Соответствующий ей кратчайший маршрут из списка конкурирующих маршрутов необходимо сравнить с уже имеющимися маршрутами в списке КМУФ и, если такового маршрута нет, тогда записать его в список КМУФ, а из списка конкурирующих маршрутов соответствующую строку удалить. Если же такой маршрут уже есть, тогда нужно просто удалить соответствующую строку из списка конкурирующих путей.

Используя метод объединения простых цепей с учетом эффекта поглощения (ГОСТ Р 53111-2008) воспользуемся следующим выражением

где Е - называют поглощением;

- вероятность исправного состояния k -го КМУФ.

Согласно формуле (36) надежность направления связи из 1 узла сети в 6 узел сети будет р₁₆ = 0,806. Так как требование по надежности направления связи из 1 узла сети в 6 узел сети определено на уровне 0,9, а найденное значение меньше требуемого 0,9 ≥ 0,806, следовательно, продолжаем дальнейший поиск КМУФ.

Шаг 4. Список конкурирующих ветвей на четвертом шаге

Список ответвлений на четвертом шаге

Список конкурирующих маршрутов на четвертом шаге

Список КМУФ на четвертом шаге

На четвертом шаге получаем два КМУФ (фиг. 3, фиг. 4), выражение (46-47) можем записать в следующем виде

Рассчитаем надежность направления связи из 1 узла сети в 6 узел сети с учетом двух КПУФ по формуле (36), получим p₁₆ = 0,935. Так как мы задали надежность направления связи из 1 узла сети в 6 узел сети не хуже 0,9, а 0,9 ≤ 0,935, значит, на этом шаге останавливаем поиск КПУФ. Два КПУФ достаточно, чтобы выполнить требование по надежности направления связи из 1 узла сети в 6 узел сети. Найденные два надежных маршрута отображаются в таблице маршрутизации.

103. Заполняют таблицы маршрутизации для двух и более надежных маршрутов сети связи в порядке уменьшения их надежности.

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

Рассмотрим пример формирования вектора величин расщепления потока трафика данных на два и более субпотоков трафика данных.Пусть на вход i-го направления связи поступает нагрузка d_i, которая распределяется последовательно по k_i надежным маршрутам, которые были найдены ранее. Если величина потока трафика данных, обслуживаемого маршрутом 1-го выбора, составляет то величина характеризует остаточный необслуженный поток трафика данных, который передается для обслуживания маршрутом 2-го выбора, и так далее. В результате, распределение i-го направления связи поток трафика данных по маршрутам определяется следующими соотношениями:

где Δ_ji - величина потока трафика данных, оставшегося после его обслуживания маршрутом j-го выбора, - величина необслуженного потока трафика данных i-го направления связи, а Δ_0i= d_i. Величина обслуженного потока трафика данных направления связи определяется из следующего соотношения:

где g_ji - поток по маршруту (маршруту j-го выбора для i-го направления связи).

При известном распределении загруженность ребра r_k потоком трафика данных i-го направления связи определяется следующим соотношением:

где

Полная загруженность каждого ребра составит:

Величины g_ji определяются исходя из условия суперконкурентного (справедливого) распределения потоков трафика данных по маршрутам, в соответствии с которым субпотоки трафика данных различных потоков трафика данных имеют равные "права" на использование ресурса сети (при условии равенства приоритетов всех субпотоков трафика данных) [Малашенко Ю.Е., Новикова Н.М. Модели неопределенности в многопользовательских сетях. - М.: Эдиториал УРСС, 1999. - 160 с]. При возникновении дефицита пропускной способности ребра (канала связи), обслуживающего потоки трафика данных несколькими маршрутами его ресурс с_k делится пропорционально поступающей нагрузке Δ_ji в соответствии с выражением:

где

Поиск величин g_ji осуществляется методом последовательного приближения к оптимальному решению. На каждом последующем шаге поток трафика данных g_ji маршрута R_j(i) может быть увеличен на величину ν_ji.

Очевидно, что величина ν_ji не может превосходить величину оставшегося необслуженного потока трафика данных Δ_ji. Кроме того, она не может превосходить и остаточную пропускную способность сети на маршруте R_j(i), определяемую выражением (56):

где h_k - загруженность ребра (канала связи) r_k, обслуживающего маршрутом R_j(i) - вычисляется в соответствии с (53). Более того, если ребро (канал связи)

обслуживает несколько маршрутов, то на долю маршрута R_j(i) приходится только часть остаточной пропускной способности η_ji, определяемой в соответствии с выражением (54) после замены в нем с_k на η_ji. Таким образом, увеличение ν_ji потока трафика данных g_ji составит:

где

и

Приращение (55) повторяется последовательно для каждого маршрута (порядок следования маршрутов не имеет значения). Затем весь цикл расчета повторяется для того, чтобы еще увеличить потоки трафика данных по маршрутам на величину :

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

Число итераций зависит от задаваемого значения точности вычислений ε. Для практического использования величину ε достаточно брать на отрезке [0.1; 0.01]. Экспериментально было установлено, что при этом число итераций не превосходит 100.

На основе полученных в результате расчетов значений g_ji вычисляются величины обслуженных субпотоков трафика данных для направления связи по формуле (51) и загруженности каналов связи по (52, 53).

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

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

107. Рекомбинируют в промежуточной системе каждый поток трафика данных, состоящий из двух или более субпотоков трафика данных

108. Передают от промежуточной системы потоки трафика данных в оконечную систему получателя.

Правомерность теоретических предпосылок проверялась с помощью программы для оптимизации ресурса телекоммуникационных сетей (Parallel Pro Net) [Свидетельство о государственной регистрации программы для ЭВМ №2007612374 от 7 июня 2007 г.] при следующих исходных данных:

- число узлов в сети связи промежуточной системы N=6;

- пропускная способность, метрика, надежность каналов связи представлены в таблице 1;

- информационная скорость направления связи из 1 узла сети в 6 узел сети составляет V_1-6 = 3000 кбит/с;

- информационная скорость направления связи из 3 узла сети в 2 узел сети составляет V_1-4 = 3000 кбит/с;

- узлы сети будем считать абсолютно надежными.

Зададим два направления связи p₁₆ из 1 узла сети в 6 узел сети и р₃₂ из 3 узла сети в 2 узел сети. Согласно данному изобретению найдем количество маршрутов в сети связи, чтобы выполнялось требование по надежности направления связи на уровне 0,9. Для направления связи из 1 узла сети в 6 узел сети это маршруты μ₁ = [8 13 14 15] и μ₂ = [7 10 15], а для направления связи из 3 узла сети в 2 узел сети μ₁ = [8 7] и μ₂ = [l 1 12 9]. Рассчитаем по формуле (36) надежность направления связи, соответственно получим р₁₆ = 0,935, р₃₂ = 0,975. Произведем расщепление потоков трафика данных по найденным маршрутам согласно данному изобретению, при этом, используя метод полного перебора состояний заданной промежуточной системы, получим средневзвешенное значение величины обслуженного трафика для направления связи из 1 узла сети в 6 узел сети 1768 кбит/с, а для направления связи из 3 узла сети в 2 узел сети 1755 кбит/с.

В прототипе поиск маршрутов в сети связи осуществляется по критерию наименьшего количества «хопов» (Нор) между двумя узлами сети связи. Для направления связи из 1 узла сети в 6 узел сети это маршруты μ₁ = [7 9 13] и μ₂ = [8 11 14], а для направления связи из 3 узла сети в 2 узел сети μ₁ = [8 7] и μ₂ = [11 10]. Произведем расщепление потоков трафика данных по найденным маршрутам согласно прототипу, при этом, используя метод полного перебора состояний заданной промежуточной системы, получим средневзвешенное значение величины обслуженного трафика для направления связи из 1 узла сети в 6 узел сети 1464 кбит/с, а для направления связи из 3 узла сети в 2 узел сети 1585 кбит/с.

В таблице 2 представлено сравнение надежности направления связи и средневзвешенного значения величины обслуженного трафика прототипа и изобретения.

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

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