×
01.03.2019
219.016.cd8c

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

Вид РИД

Изобретение

№ охранного документа
0002323533
Дата охранного документа
27.04.2008
Аннотация: Изобретение относится к способам и устройствам для нахождения пути для маршрутизации вызова от узла-источника (SN) до узла-получателя (DN) через коммуникационную сеть. Техническим результатом является обеспечение поиска кратчайшего пути через сеть от узла-источника (SN) до узла-получателя (DN) через коммуникационную сеть с учетом определенных ограничений, например, по минимальной ширине полосы, максимальной задержке. Технический результат достигается тем, что узел-источник (SN) генерирует случайное число, и в зависимости от генерированного случайного числа, по меньшей мере, один путь между узлом-источником (SN) и узлом-получателем (DN) будет выбираться из узла-источника (SN). 2 н. и 9 з. ф-лы, 2 ил.

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

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

В работе R.Ghosh, G.Varghese: "Symmetrical Routes and Reverse Path Congestion Control" [Online] 11 September 1997 (1997-09-11), pages 0-17, XP002301045 описаны новые механизмы учета при обработке асимметрии, которая возникает в протоколах маршрутизации. Показано, как избежать асимметрии маршрута (из-за неуникальных кратчайших путей) за счет добавления стоимостей линий связи, определяемых случайными числами. Документ показывает, каким образом может быть модифицирован RIP для того, чтобы избежать асимметрии маршрута с высокой вероятностью, без оказания воздействия на его метрики эффективности или рабочих характеристик, таких как время сходимости. Симметричная внутридоменная маршрутизация также обеспечивает возможность новой формы контроля перегрузки, которая определена как Контроль Перегрузки Обратного Канала (RPCC). Настоящий документ показывает, с использованием математического моделирования, что RPCC может улучшить существующие механизмы контроля перегрузки TCP для улучшения поведения при запуске или для исключения потерь на границах между доменами и основной сетью.

В статье K.A.Berman: "Cost-Constrained Matchings and Disjoint Paths" Internet Article, [Online] 31 December 2003 (1003-12-31), pages 1-15 XP002301046 описан график (G=(V,E)), где краевые области взвешены элементами из коммутативной полугруппы (S, +), и рассматривается задача нахождения согласующегося значения M, которое перекрывает заданное множество U вершин, для которых функция стоимости c(M) (где c(M) есть сумма весов на краях М) удовлетворяет заданному ограничению, т.е. для заданной функции ограничения Ф, отображающей S на {0,1}, Ф(c(M))=1. Эта задача является NP-неполной для полугрупп экспоненциального размера. В этом документе, для малых полугрупп S, т.е. размер S ограничен сверху уникальным элементом x/2 ∈ S, так что 2(x/2)=x, представлен NC2-алгоритм (на EREW PRAM) для вычисления равноценности для ряда таких согласованных значений и RNC2-алгоритм для нахождения одного. В случае, когда ограничение по функции стоимости является монотонным, т.е. для каждой пары элементов x, y ∈ S, x+y удовлетворяет ограничению, что x также принадлежит ему, это дает решение задачи выбора множества ограниченных путей и, в более общем виде, задачи ограниченных функцией стоимости дизъюнктивных путей. Наконец, представлены обобщения полученных результатов для бинарных матроидов.

В WO 00/69210 описано оценивание маршрутов R в коммуникационной сети, состоящей из коммутирующих узлов и каналов передачи. С этой целью модифицированные стоимости линий связи устанавливаются из стоимостей линий связи, назначенных каналам передачи, предпочтительно с использованием случайных чисел, и маршруты оцениваются в соответствии с модифицированными стоимостями линий связи. Если модифицированные стоимости линий связи устанавливаются на каждый запрос вызова, то соединения, которые могут устанавливаться по ряду маршрутов с идентичными минимальными стоимостями маршрута, равномерно распределяются по этим маршрутам при сохранении существующих алгоритмов маршрутизации.

Для нахождения маршрута из узла-источника к узлу-получателю по сети, хорошо известным алгоритмом является алгоритм Dijkstra, который вычисляет кратчайший путь. Один вариант этого алгоритма, иногда называемый открытым первым алгоритмом кратчайшего пути - OSPF, поскольку он используется в протоколе маршрутизации в Интернете под тем же самым именем, специфицирован в RFC 2328 и других связанных документах (J.Moy, "OSPF Version 2", RFC 2328, April 1998). Использование маршрутизации на основе QoS (параметр "качество обслуживания") в мобильных базовых сетях стало необходимым для того, чтобы удовлетворять потребностям мультимедийных приложений и повышать эффективность сети. Для маршрутизации на основе QoS алгоритмы маршрутизации должны быть спроектированы для того, чтобы удовлетворять ограничениям по QoS. Один такой алгоритм называется алгоритмом CSPF (Первый ограниченный кратчайший путь). Это алгоритм, который обеспечивает поиск кратчайшего пути через сеть, который подчиняется определенным ограничениям, например, по минимальной ширине полосы, максимальной задержке. Он основан на алгоритме Dijkstra для вычисления кратчайшего пути. Алгоритм CSPF может использоваться в узле, выполняющем протокол OSPF.

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

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

Настоящее изобретение нацелено на решение проблемы блокировки вызовов.

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

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

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

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

Фиг.1 - иллюстративный способ выбора случайного расстояния для линии связи,

Фиг.2 - иллюстрация выбора, по меньшей мере, одного пути между узлом-источником SN и узлом-получателем DN.

Фиг.1 показывает приведенный для примера способ выбора случайного расстояния для линии связи. Предположим, что базовое расстояние D установлено для линии связи путем конфигурирования или иным способом. Случайное число между 0 и числом, определяемым емкостью линии связи, генерируется, и расстояние определяется из графика. Расстояние, таким образом, является результирующим случайным числом. Можно видеть, что если линия связи имеет большую долю свободной ширины полосы, то ее расстояние будет находиться в диапазоне 0-D с большей вероятностью, чем в диапазоне D-2D. Чем меньше расстояние, тем более вероятен выбор линии связи. Этот тип функции имеет дополнительное преимущество, заключающееся в том, что весьма маловероятно, что будут иметь место связи, увеличивающие эффективность совместного использования нагрузки.

Фиг.2 иллюстрирует выбор, по меньшей мере, одного пути между узлом-источником SN и узлом-получателем DN. Узел-источник SN поддерживает базу данных состояний линий связи. Одной из возможностей передачи/сигнализации информации о состоянии от некоторого узла к соседним узлам является использование протокола OSPF. Сообщение уведомления о состоянии линии связи (LSA) протокола OSPF служит, главным образом, этой цели. Обычно база данных состояний линий связи будет устаревать вследствие изменения конфигурации соединений в сети и задержек распространения по протоколу OSPF. Если узлу-источнику SN желательно вычислить маршрут/путь от самого себя до узла-получателя DN, то он (узел SN) вычисляет маршрут/путь для данных вызова через сеть. Для нахождения маршрута/пути от узла-источника SN до узла-получателя DN (то есть мобильного оконечного устройства, мобильного компьютера, компьютера, персонального цифрового помощника (PDA) и т.д.) через сеть, узел-источник (SN) использует алгоритм, такой как алгоритм Dijkstra, Bellman-Ford или любой подобный алгоритм маршрутизации на основе качества обслуживания для выбора/вычисления кратчайшего пути через сеть. При рассмотрении маршрута/пути, используется кратчайший путь от узла-источника SN до узла-получателя DN. Это путь с минимальным полным суммарным расстоянием или стоимостью линий связи, которые он содержит. В данном изобретении полное расстояние или стоимость является случайным числом, представляя собой сумму расстояний/стоимостей соответствующих линий связи, часть из которых рандомизирована. Для такой линии связи случайное число для его расстояния/стоимости генерируется с использованием способа, подобного представленному на фиг.1. Специальным случаем является рандомизация расстояний/стоимостей всех используемых линий связи. Отдельное случайное число обычно генерируется для каждой рандомизированной линии связи каждого рассматриваемого пути. Согласно настоящему изобретению, каждый узел-источник SN сети генерирует случайные числа самостоятельно, независимо от других узлов и выбирает наилучший путь для маршрутизации данных вызова. Кроме того, каждый запрос маршрута использует различные случайные числа, независимо от случайных чисел в предыдущих запросах.

1.Способнахожденияпутидлямаршрутизациивызоваотузла-источника(SN)доузла-получателя(DN)черезкоммуникационнуюсеть,отличающийсятем,чтоузел-источник(SN)генерируетслучайноечисло,ивзависимостиотгенерированногослучайногочисла,поменьшеймере,одинпутьмеждуузлом-источником(SN)иузлом-получателем(DN)будетвыбиратьсяизузла-источника(SN).12.Способпоп.1,отличающийсятем,чтослучайноечислоявляетсядисперсиейрасстояниялиниисвязи,зависимойотемкостилиниисвязии/илисвободнойшириныполосы.23.Способпоп.1или2,отличающийсятем,чтосигнализациякдругимузламчерезсетьвыполняетсяпосредствомсообщенийуведомленийосостояниилиниисвязиLSAпротоколаOSPF.34.Способпоп.1,отличающийсятем,чтоузел-источник(SN)генерируетдлякаждоговыбранногопутиотдельноеслучайноечисло.45.Способпоп.1,отличающийсятем,чтослучайноечислоявляетсясуммойслучайныхпеременных,вычисленныхвкаждойлиниисвязирассматриваемогопути.56.Способпоп.1,отличающийсятем,чтоспособиспользуеталгоритммаршрутизациинаосновекачестваобслуживаниядлявыбранногопути.67.Способпоп.6,отличающийсятем,чтовкачествеалгоритмамаршрутизациинаосновекачестваобслуживанияиспользуетсяDijkstra-и/илиBellman-Ford-алгоритм.78.Способпоп.1,отличающийсятем,чтоузел-получатель(DN)представляетсобойоконечноеустройство,оконечноеустройствомобильнойсети,компьютер,мобильныйкомпьютери/илиперсональныйцифровойпомощник(PDA).89.Способпоп.1,отличающийсятем,чтокоммуникационнаясетьпредставляетсобойсетьмобильнойсвязии/илисетьпередачиданных.910.Устройстводлянахожденияпутидлямаршрутизациивызоваотузла-источника(SN)доузла-получателя(DN)черезкоммуникационнуюсеть,содержащееузел-источник(SN)длягенерациислучайногочиславзависимостиотемкостилиниисвязиисвободнойшириныполосы,причемузел-источник(SN)обеспечиваетвыбор,поменьшеймере,одногопутимеждуузлом-источником(SN)иузлом-получателем(DN)взависимостиотгенерированногослучайногочисла,приэтомузел-источник(SN)обеспечиваетгенерациюдлякаждоговыбранногопутиотдельногослучайногочисла.1011.Устройствопоп.10,отличающеесятем,чтоупомянутоеустройстводлясигнализациииспользуетсообщенияуведомленияосостояниилиниисвязи(LSA)протоколаOSPF.11
Источник поступления информации: Роспатент

Showing 31-40 of 1,427 items.
27.04.2013
№216.012.3ab6

Способ функционирования термодинамического контура и термодинамический контур

Термодинамический контур содержит три теплообменника (W1, W2, W3), сепаратор (4), турбину (2), объединитель (5) и обводной трубопровод (31). Первый теплообменник (W1) для выработки первого нагретого или частично испаренного потока (15) рабочей среды путем теплопередачи от разреженного потока...
Тип: Изобретение
Номер охранного документа: 0002480591
Дата охранного документа: 27.04.2013
27.04.2013
№216.012.3b8d

Способ анализа функционирования газовой турбины

Изобретение относится к способу анализа функционирования газовой турбины, а также к способу контроля функционирования газовой турбины. Технический результат - увеличение точности диагностики износа и повреждений турбины. Изобретение описывает способ, при котором, по меньшей мере, один...
Тип: Изобретение
Номер охранного документа: 0002480806
Дата охранного документа: 27.04.2013
27.04.2013
№216.012.3bc0

Система прерывателя с подвижной переключательной трубой

Система (1) прерывателя имеет переключательную трубу (3) с выходным отверстием (5) для переключательных газов. Переключательная труба (3) в зоне выходного отверстия (5) для переключательных газов соединена с соединительным участком (9) приводной штанги (10). Соединительный участок (9) защищен с...
Тип: Изобретение
Номер охранного документа: 0002480857
Дата охранного документа: 27.04.2013
10.05.2013
№216.012.3cef

Способ прокатки полосы на прокатном стане с распознаванием кривизны

Изобретение предназначено для улучшения качества прокатываемых полос. В многоклетевом прокатном стане полоса (2) проходит последовательно через прокатные клети (1). Полоса (2) относительно средней линии (7) прокатки в каждую из прокатных клетей (1) вводится с известным соответствующим сдвигом...
Тип: Изобретение
Номер охранного документа: 0002481166
Дата охранного документа: 10.05.2013
10.05.2013
№216.012.3d20

Способ ограничения угла между продольными осями соединенных друг с другом вагонных кузовов

Каждый вагонный кузов опирают лишь на одну поворотную тележку. На угол между продольными осями соединенных друг с другом через шарнир вагонных кузовов оказывают активное влияние с помощью соединенного с шарниром регулируемого электрического исполнительного элемента, пока он не примет заданное...
Тип: Изобретение
Номер охранного документа: 0002481215
Дата охранного документа: 10.05.2013
10.05.2013
№216.012.3e26

Паросиловая установка для генерирования электрической энергии

Изобретение относится к энергетике. Паросиловая установка содержит обводной трубопровод, который соединяет с возможностью прохождения потока трубопровод свежего пара с трубопроводом отработавшего пара, при этом в обводном трубопроводе расположен обводной пароохладитель, который при аварийной...
Тип: Изобретение
Номер охранного документа: 0002481477
Дата охранного документа: 10.05.2013
20.05.2013
№216.012.401a

Приводное устройство для рельсового транспортного средства

Изобретение относится к области рельсового транспорта. Приводное устройство (12), согласно изобретению, обеспечивает возможность создания имеющего особенно простую конструкцию и небольшую массу приводного устройства для рельсового транспортного средства большой мощности для диапазона скоростей...
Тип: Изобретение
Номер охранного документа: 0002481980
Дата охранного документа: 20.05.2013
20.05.2013
№216.012.417e

Ротор для гидравлической машины

Изобретение касается ротора (2) для гидравлической машины, включающего в себя вал (6) и установленное на нем осевое упорное кольцо (8) в качестве элемента осевого подшипника, служащего для осевого опирания вала (6). Предлагается, чтобы осевое упорное кольцо (8) включало в себя первую...
Тип: Изобретение
Номер охранного документа: 0002482336
Дата охранного документа: 20.05.2013
20.05.2013
№216.012.4276

Фронтальный узел, прибородержатель с таким фронтальным узлом и распределительный шкаф с большим числом таких прибородержателей

Изобретение относится к электротехнике и может быть использовано в системах распределения энергии. Технический результат состоит в упрощении конструкции при сохранении безопасности. Фронтальный узел (3) для прибородержателя (1) содержит расположенную на передней панели управления фронтального...
Тип: Изобретение
Номер охранного документа: 0002482584
Дата охранного документа: 20.05.2013
20.05.2013
№216.012.4279

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

Использование: в области электротехники. Технический результат заключается в повышении чувствительности. В способе с помощью по меньшей мере одного измеренного значения тока и по меньшей мере одного измеренного значения напряжения формируется измеренное значение запуска, которое сравнивается с...
Тип: Изобретение
Номер охранного документа: 0002482587
Дата охранного документа: 20.05.2013
+ добавить свой РИД