×
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 751-760 of 1,427 items.
25.08.2017
№217.015.cc40

Способ для балансировки конструктивного элемента

Группа изобретений относится к балансировке ротора электрической машины. Способ балансировки конструктивного элемента (1), в частности ротора электрической машины, заключатся в том, что штифты (11, 11') вводят в предварительно изготовленные отверстия (5, 7, 9) в роторе (1). Причем ротор (1)...
Тип: Изобретение
Номер охранного документа: 0002620459
Дата охранного документа: 25.05.2017
25.08.2017
№217.015.ccb2

Лопатка ротора газовой турбины, ротор газовой турбины и способ сборки ротора

Лопатка ротора газовой турбины, включающая в себя корневую часть, платформу и перьевую часть. Платформа содержит входную и выходную стороны, боковые стороны, проходящие от входной к выходной стороне, а также осевую и радиальную канавки в каждой боковой стороне платформы. Радиальная канавка...
Тип: Изобретение
Номер охранного документа: 0002620472
Дата охранного документа: 25.05.2017
25.08.2017
№217.015.ccca

Композиционный материал для термического накопителя энергии и способ получения композиционного материала для термического накопителя энергии

Изобретение относится к композиционному материалу для термического накопителя энергии с термопластичным материалом, а также к способу получения такого композиционного материала. Композиционный материал содержит термопластичный материал с изменяемым фазовым состоянием, в который с заданным...
Тип: Изобретение
Номер охранного документа: 0002620843
Дата охранного документа: 30.05.2017
25.08.2017
№217.015.cd39

Выдвижная рама для электрического выдвижного коммутационного аппарата, а также блок из выдвижной рамы и электрического выдвижного коммутационного аппарата

Изобретение относится к электротехнике, к электрическим коммутационным аппаратам. Технический результат состоит в упрощении блокирования выдвижной рамы. Выдвижная рама для электрического выдвижного коммутационного аппарата, в частности выдвижного силового выключателя, имеет переходной цоколь...
Тип: Изобретение
Номер охранного документа: 0002619763
Дата охранного документа: 18.05.2017
25.08.2017
№217.015.cd6c

Охлаждаемые составные листы для газовой турбины

Слоистый лист для детали газовой турбины содержит первый и второй покрывающие слои и первый промежуточный слой. Первый покрывающий слой, второй покрывающий слой и первый промежуточный слой сложены вместе один на другой. Первый промежуточный слой расположен между первым покрывающим слоем и...
Тип: Изобретение
Номер охранного документа: 0002619664
Дата охранного документа: 17.05.2017
25.08.2017
№217.015.cda6

Светофор

Оптическая система светофора содержит линзу (13) Френеля с френелевскими структурами (15) на внутренней поверхности входа света, при этом наружная поверхность выхода света (16) выполнена таким образом, что каждая касательная (17) к наружной поверхности выхода света (16) образует угол ≥ 105° по...
Тип: Изобретение
Номер охранного документа: 0002619678
Дата охранного документа: 17.05.2017
25.08.2017
№217.015.d024

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

Изобретение относится к энергетике. Энергетическая установка (100) содержит кожух (108) с первой секцией (I) кожуха и второй секцией (II) кожуха, причём генератор (110) переменного тока расположен в пределах первой секции (I) кожуха, а газовая турбина (120) расположена в пределах второй секции...
Тип: Изобретение
Номер охранного документа: 0002620878
Дата охранного документа: 30.05.2017
25.08.2017
№217.015.d1c6

Уплотнительная втулка для паровой турбины и паровая турбина

Настоящее изобретение относится к уплотнительной втулке (1) для паровой турбины (40). Паровая турбина (40) содержит по меньшей мере ротор (41) турбины и корпус (43) турбины, при этом уплотнительная втулка (1) размещена между валом (42) ротора (41) и корпусом (43) и содержит по меньшей мере два...
Тип: Изобретение
Номер охранного документа: 0002621447
Дата охранного документа: 06.06.2017
25.08.2017
№217.015.d1e3

Отделитель для диоксида углерода, способ его эксплуатации и отделительный узел

Изобретение относится к отделителю для диоксида углерода. Описан отделитель диоксида углерода, содержащегося, в частности, в дымовом газе электростанции на ископаемом топливе, включающий в себя абсорбционный узел, приданный ему десорбционный узел и отделительный узел для отделения солей из...
Тип: Изобретение
Номер охранного документа: 0002621809
Дата охранного документа: 07.06.2017
26.08.2017
№217.015.d412

Система с газовым уплотнением

Изобретение относится к системе с газовым уплотнением (GS), статором (S) и проходящим вдоль оси (X) ротором (R) для уплотнения уплотнительного зазора (SGP) между ротором (R) и статором (S), включающее в себя вращающееся уплотнительное кольцо (RSR) ротора и неподвижное уплотнительное кольцо...
Тип: Изобретение
Номер охранного документа: 0002622445
Дата охранного документа: 15.06.2017
+ добавить свой РИД