СПОСОБ МНОГОМЕРНОЙ ДИНАМИЧЕСКОЙ МАРШРУТИЗАЦИИ В СЕТИ СВЯЗИ С ПАКЕТНОЙ ПЕРЕДАЧЕЙ СООБЩЕНИЙ Российский патент 2017 года по МПК H04L12/64 

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

Известен способ многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений, в соответствии с которым в каждом из узлов связи осуществляют контроль качества входящих в узел связи каналов связи. Результаты контроля качества каналов связи передают на узлы связи сети связи. В зависимости от качества каналов связи оценивают пропускную способность каналов связи, затем определяют пропускную способность одномерных маршрутов в зависимости от пропускной способности входящих в этот одномерный маршрут каналов связи. Далее формируют многомерный маршрут передачи сообщения, причем вначале в многомерный маршрут включают одномерные маршруты передачи с наибольшей пропускной способностью, затем - одномерные маршруты передачи с меньшей, но следующей по величине пропускной способностью и так далее, до тех пор, пока пропускная способность многомерного маршрута передачи не обеспечит передачу сообщения в заданное время, и далее передают сообщение по этому многомерному маршруту передачи (Квашенников В.В., Шабанов А.К. Способ адаптивной маршрутизации в сети связи с многомерными маршрутами передачи сообщений. Патент РФ №2431945. Опубл. 20.10.2011. Бюл. №29).

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

Известен также способ многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений, заключающийся в том, что в узлах связи осуществляют контроль качества входящих каналов связи. Результаты контроля качества каналов связи передают на другие узлы связи и в зависимости от качества каналов связи формируют одномерные маршруты передачи. Далее из одномерных маршрутов передачи формируют многомерный маршрут передачи сообщения, включая в него сначала одномерные маршруты передачи с каналами связи лучшего качества, затем - одномерные маршруты передачи с меньшим, но следующим по величине качеством каналов связи, и так до тех пор, пока качество многомерного маршрута передачи не обеспечит передачу всего сообщения. Затем оценивают вероятность доведения сообщения по многомерному маршруту передачи, и при величине вероятности доведения сообщения по многомерному маршруту передачи менее заданного значения перераспределяют пакеты по одномерным маршрутам передачи и далее передают сообщение по многомерному маршруту передачи (Квашенников В.В., Солдатенко Э.Н. Способ динамической маршрутизации в сети связи с многомерными маршрутами и пакетной передачей сообщений. Патент РФ №2457628. Приор. 14.06.2011, опубл. 27.07.2012, Бюл. №21).

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

Наиболее близким к предлагаемому способу (прототип) является способ многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений, заключающийся в том, что по результатам контроля качества входящих в узлы связи каналов связи вычисляют целевые функции каналов связи, которые учитывают вероятность и время доведения сообщения, затем на основании целевых функций каналов связи формируют одномерные маршруты и многомерный маршрут передачи и вычисляют их целевые функции, при формировании одномерных маршрутов передачи выполняют оптимизацию целевой функции этих маршрутов передачи, при формировании многомерных маршрутов передачи выполняют оптимизацию целевой функции этого маршрута передачи, выбирая сначала одномерный маршрут передачи с наибольшим значением целевой функцией, затем одномерный маршрут передачи с меньшим, но следующим по величине значением целевой функции и так до тех пор, пока многомерный маршрут передачи не обеспечит передачу всех пакетов сообщения в заданное время и с заданной вероятностью доведения сообщения, при этом значения целевых функций входящих в узлы связи каналов связи передают на смежные узлы связи, которые далее передают значения целевой функции на другие смежные узлы связи, исключая узлы, от которых были получены значения целевой функции (Квашенников В.В. Способ многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений. Патент РФ №2526755. Приор. 08.04.2013, опубл. 27.08.2014, Бюл. №24).

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

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

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

Рассмотрим осуществление предлагаемого способа многомерной динамической маршрутизации в сети связи с пакетной передачей сообщений.

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

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

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

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

Анализ вероятностей целесообразно проводить через промежутки времени, длительность которых привязана к длительности квазистационарных состояний каналов связи, которая определяется параметрами сигнально-помеховой обстановки. Излишне частый анализ вероятностей доставки пакетов до узлов связи может приводить к ее некорректной оценке. С другой стороны, недостаточная частота анализа вероятности доставки пакетов до узлов связи приведет к тому, что не будет оперативно отслеживаться состояние сети связи и вероятностные характеристики доставки сообщений могут уменьшиться. Если по истечении некоторого времени (обычно 3-5 минут) вероятностные характеристики каналов связи выйдут за пределы установленных ограничений, целесообразно изменить скорости передачи информации по каналам связи. Пороговое значение для вероятности доставки Р_зад зависит от важности сообщений, требований качества обслуживания, и может составлять, например, величину 0.99. Это позволяет сократить объем служебной маршрутной информации и число вычислений при выборе маршрутов передачи.

Далее формируют одномерные маршруты передачи, из одномерных маршрутов формируют многомерные маршруты передачи, причем при формировании одномерных и многомерных маршрутов формируют все их возможные варианты.

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

Если вероятность доставки пакетов по каналу связи удовлетворяет условию

то считается, что скорость выбрана правильно и коррекция скорости передачи информации в канале связи не производится. Если Р_зад>Р, то принимается решение о необходимости снижения скорости передачи информации в канале связи. Если Р=1, то принимается решение о необходимости повышении скорости передачи информации в канале связи.

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

Пусть для доставки всех сообщений до каждого из узлов , являющихся получателями сообщений, необходимо доставить Np_k пакетов длиной L.

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

где C_kb – коэффициенты, равные 1, если пакеты доставляются до k-го узла по многомерному маршруту b и 0 в противном случае.

Время доставки пакета T_kb по одномерному маршруту, осуществляющему доставку информации до k-го узла в многомерном маршруте b, равно сумме времен доставки пакета по всем каналам связи, входящим в этот одномерный маршрут, каждое из которых определяется как отношение длины пакета сообщения L к скорости передачи информации V_rkb в r-ом канале связи:

где R_kb - количество каналов связи, входящих в указанный одномерный маршрут.

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

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

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

1) адреса узлов связи - получателей пакетов сообщений;

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

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

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

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

При вводе сети в эксплуатацию проводят анализ сети, в результате которого определяют количество многомерных маршрутов, все их варианты, коэффициенты C_kb. На основе полученной информации, согласно приведенному алгоритму, формируется матрица А (фиг. 2). Далее при анализе сети связи оценивают скорости передачи информации каналов связи для каждого из многомерных маршрутов с учетом их взаимного влияния и время доставки пакетов. На основе полученных результатов формируют начальные значения целевых функций F, которые вводятся в алгоритм работы вычислителя маршрутизатора.

Далее по результатам контроля качества каналов связи корректируют скорости передачи информации в каналах связи с учетом взаимного влияния всех каналов связи, задействованных в каждом многомерном маршруте, определяют целевые функции многомерных маршрутов (фиг. 3). Для этого в алгоритме осуществляется ввод вероятностей доставки Р по всем узлам - получателям и номерам многомерных маршрутов b. Если для некоторого r-го канала связи Р_зад>P_rkb, то принимается решение о необходимости снижения скорости передачи информации по этому каналу связи, а если P_rkb=1, то о необходимости повышении скорости передачи информации по нему. Далее определяют времена доставки пакетов и целевые функции многомерных маршрутов передачи, на основе которых корректируется матрица А.

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

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

Далее осуществляют оптимальный выбор многомерных маршрутов и кратности их использования по критерию минимизации времени доставки (6) согласно алгоритму процедуры нахождения оптимальных многомерных маршрутов, приведенному в приложении. Алгоритм является реализацией задачи целочисленного линейного программирования в виде полностью целочисленного алгоритма Гомори (Шевченко В.Н., Золотых Н.Ю. Линейное и целочисленное программирование. Нижний Новгород, Издательство Нижегородского госуниверситета им. Н.И. Лобачевского, 2004, 154 с.).

Приведенный алгоритм может быть реализован на стандартных программных и программно-аппаратных маршрутизаторах, базирующихся на операционной системе Linux или IOS (для маршрутизаторов фирмы CISCO).

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

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

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