ВЕРОЯТНОСТНЫЙ ВЫБОР ЛИНИИ СВЯЗИ В АЛГОРИТМЕ МАРШРУТИЗАЦИИ Российский патент 2008 года по МПК H04L12/56 

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

Общеизвестный важный метод для маршрутизации соединений в сети определяется как маршрутизация от узла-источника (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, представлен NC²-алгоритм (на EREW PRAM) для вычисления равноценности для ряда таких согласованных значений и RNC²-алгоритм для нахождения одного. В случае, когда ограничение по функции стоимости является монотонным, т.е. для каждой пары элементов 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 сети генерирует случайные числа самостоятельно, независимо от других узлов и выбирает наилучший путь для маршрутизации данных вызова. Кроме того, каждый запрос маршрута использует различные случайные числа, независимо от случайных чисел в предыдущих запросах.

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

1. Способ нахождения пути для маршрутизации вызова от узла-источника (SN) до узла-получателя (DN) через коммуникационную сеть, отличающийся тем, что узел-источник (SN) генерирует случайное число, и в зависимости от генерированного случайного числа, по меньшей мере, один путь между узлом-источником (SN) и узлом-получателем (DN) будет выбираться из узла-источника (SN).2. Способ по п.1, отличающийся тем, что случайное число является дисперсией расстояния линии связи, зависимой от емкости линии связи и/или свободной ширины полосы.3. Способ по п.1 или 2, отличающийся тем, что сигнализация к другим узлам через сеть выполняется посредством сообщений уведомлений о состоянии линии связи LSA протокола OSPF.4. Способ по п.1, отличающийся тем, что узел-источник (SN) генерирует для каждого выбранного пути отдельное случайное число.5. Способ по п.1, отличающийся тем, что случайное число является суммой случайных переменных, вычисленных в каждой линии связи рассматриваемого пути.6. Способ по п.1, отличающийся тем, что способ использует алгоритм маршрутизации на основе качества обслуживания для выбранного пути.7. Способ по п.6, отличающийся тем, что в качестве алгоритма маршрутизации на основе качества обслуживания используется Dijkstra- и/или Bellman-Ford-алгоритм.8. Способ по п.1, отличающийся тем, что узел-получатель (DN) представляет собой оконечное устройство, оконечное устройство мобильной сети, компьютер, мобильный компьютер и/или персональный цифровой помощник (PDA).9. Способ по п.1, отличающийся тем, что коммуникационная сеть представляет собой сеть мобильной связи и/или сеть передачи данных.10. Устройство для нахождения пути для маршрутизации вызова от узла-источника (SN) до узла-получателя (DN) через коммуникационную сеть, содержащее узел-источник (SN) для генерации случайного числа в зависимости от емкости линии связи и свободной ширины полосы, причем узел-источник (SN) обеспечивает выбор, по меньшей мере, одного пути между узлом-источником (SN) и узлом-получателем (DN) в зависимости от генерированного случайного числа, при этом узел-источник (SN) обеспечивает генерацию для каждого выбранного пути отдельного случайного числа.11. Устройство по п.10, отличающееся тем, что упомянутое устройство для сигнализации использует сообщения уведомления о состоянии линии связи (LSA) протокола OSPF.