СПОСОБ МАРШРУТИЗАЦИИ ДЛЯ ОПТИМИЗАЦИИ РАБОТЫ СЕТИ SDH В МУЛЬТИСЕРВИСНОМ РЕЖИМЕ Российский патент 2006 года по МПК H04L12/28 H04M3/36 

Область техники

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

Уровень техники

На качественном уровне проблема распределения маршрутов для оптимизации работы сети с синхронной цифровой иерархией (SDH - Synchronous Digital Hierarchy) в мультисервисном режиме может быть описана следующим образом. Исходя из условия, что заданы топология сети, т.е. структурная схема узлов и каналов связи между ними, а также матрица сервисов, требуется распределить маршруты для всех сервисов таким образом, чтобы ресурс сервисов, использующих каждый канал связи, не превышал общего объема ресурсов сети, чтобы объем используемых ресурсов сети был минимальным, и чтобы нагрузка в сети была сбалансирована. До настоящего времени способов решения этой проблемы не существовало. Ближе всего к решению указанной проблемы находится технология плотного волнового уплотнения для оптоволоконной сети (DWDM - Dense Wavelength Division Multiplexing). Согласно этой технологии при маршрутизации часто используют эвристический алгоритм. Эвристический алгоритм основан на следующем принципе: по определенному критерию маршрутизации, например, по методу кратчайшего пути, рассчитывают первоначальный маршрут данного сервиса. Далее в зависимости от текущего состояния использования ресурсов сети, например, в зависимости от используемой полосы пропускания, производят перерасчет маршрутов частичных сервисов до тех пор, пока индикатор сервиса не достигнет ожидаемого значения или не будет достигнута сходимость результатов расчета или после определенного числа циклов расчета не будет получен удовлетворительный результат.

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

Сущность изобретения

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

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

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

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

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

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

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

Указанная проверка на этапе Е может включать в себя:

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

Е2. проверку, меньше ли рассчитанный суммарный показатель рассчитанного ранее целевого оптимального значения; если да, то условие сходимости признают выполненным, в противном случае - невыполненным.

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

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

Указанные начальные маршруты для каждого запроса на сервис на этапе А рассчитывают по алгоритму кратчайшего маршрута.

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

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

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

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

Указанный показатель баланса нагрузки на этапе D представляет собой дисперсию коэффициента использования ресурсов канала связи кольцевой подсети.

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

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

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

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

Краткое описание чертежей

Фиг.1 изображает схему корректировки маршрутов.

Фиг.2 изображает схему разделения сети на центральную и периферийную подсети.

Фиг.3 изображает общую блок-схему реализации предложенного способа.

Подробное описание изобретения

Далее приводится подробное описание изобретения со ссылкой на приложенные чертежи.

Настоящее изобретение, основанное на использовании общего эвристического алгоритма, предлагает оптимальное решение задачи маршрутизации для оптимизации работы в мультисервисном режиме на основе детального анализа топологии и морфологии сети SDH. Под оптимизацией в данном случае понимается минимизация используемых сетевых ресурсов и выравнивание нагрузки в сети. Пусть R обозначает коэффициент использования сетевых ресурсов, s - показатель баланса нагрузки, равный дисперсии всех коэффициентов использования ресурсов каналов связи в сети; тогда целевой показатель оптимизации может быть представлен как Min(aR+bs), где а и b - весовые коэффициенты, которые могут быть найдены эмпирическим путем по результатам тестирования.

Сеть состоит, главным образом, из разного рода колец, таких как кольцо защиты мультиплексной секции (MSP - Multiplex Section Protection), кольцо защиты маршрута (РР - Path Protection), кольцо с двойной межузловой связью (DNI - Dual Node Interconnection ) и т.д. Кольцо MSP относится к числу колец защиты маршрута и обеспечивает защитную коммутацию посредством взаимодействия бит-ориентированных протоколов, определенных для байтов, однонаправленных или двунаправленных, на двух- или четырехволоконном кабеле, при этом различают кольца MSP следующих типов: двухволоконное однонаправленное кольцо защиты мультиплексной секции, двухволоконное двунаправленное кольцо защиты мультиплексной секции и четырехволоконное двунаправленное кольцо защиты мультиплексной секции; кольцо РР является частным случаем кольца защиты соединения подсети, выполняющего функцию защитной коммутации через функцию соединения, обычно работающее в однонаправленном двухволоконном режиме, а именно - в режиме двухволоконного однонаправленного кольца защиты маршрута; кольцо DNI включает кроссовер-узлы двух подсетей, причем эти кроссовер-узлы должны быть сконфигурированы в зависимости от вида конкретной сети.

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

1) Если маршрут проходит только через одну подсеть, то в его перерасчете нет необходимости. Как показано на фиг.1, маршрут сервиса S1 проходит от узла А кольцевой подсети R1 к узлу В, т.е. маршрут S1 представлен кривой 101. Поскольку узлы А и В принадлежат к одной и той же кольцевой подсети R1, нет необходимости корректировать маршруты данного сервиса, и маршрут S1 по-прежнему представляется кривой 101. Применение принципа 1) позволяет избежать громоздкой и малоэффективной процедуры корректировки маршрутов.

2) Что касается сквозного сервиса, то здесь предусмотрено разделение маршрутов сервиса по кольцам; часть маршрута, проходящая внутри одной из кольцевых подсетей, может переключаться между двумя разными направлениями кольца, что не влияет на другие части маршрута. Как показано на фиг.1, маршрут сервиса S2 пролегает от узла С к узлу D кольцевой подсети R1 и проходит через канал L1 к узлу Е кольцевой подсети R2, т.е. маршрут S2 представлен кривой 102, дополненной L1 каналом связи. Если имеет место перегрузка по сервису S2 на участке между узлами С и D, то маршрут сервиса S2 в кольцевой подсети R1 меняется, переходя от кривой 102 к кривой 103, т.е. путь от узла С к узлу D будет проходить через узлы А и В. Как видно из фиг.1, эта корректировка не влияет на маршрутизацию других частей данного сервиса. Применение принципа 2) обеспечивает возможность корректировки маршрутов в соответствии с топологическими характеристиками сети SDH. Разделение корректировки баланса нагрузки всей сети упрощает местную корректировку на части маршрута, сводя ее к выбору одного из двух направлений, при этом обеспечивается достижение баланса нагрузки - как местного, так и общего по всей сети. Подобное разделение позволяет сократить число корректировок маршрутов по всей сети, тем самым резко повышая эффективность вычисления маршрутов; одновременно при этом удается избежать издержек, связанных с прямой корректировкой маршрутов вслепую, что повышает точность выравнивания нагрузки.

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

Разделение сети на центральную и периферийную подсети проиллюстрировано на фиг.2. Топология сетевой структуры 200 организована таким образом, что после разделения сети на кольцевые подсети ее дополнительно делят на периферийные и центральные подсети. На фиг.2 символом R обозначены кольцевые подсети, а символом L - каналы связи, причем элементы R4, R5, R6, R7, L5 и L6 образуют периферийные подсети, а R1, R2, R3, L1, L2, L3 и L4 - центральные подсети. При расчете показателя баланса нагрузки сети, т.е. дисперсии всех коэффициентов использования ресурсов каналов связи в сети, учитываются только центральные подсети. Неравенство объемов сервиса между кольцами R7 и R4 ведет к неравенству объемов сервиса в сети, и этот дисбаланс не может быть устранен корректировкой баланса нагрузки. Оптимизация путем перерасчета маршрутов сервисов периферийных подсетей не может дать удовлетворительных результатов.

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

На фиг.3 показана общая блок-схема предложенного способа. Поэтапное описание этой схемы, приведенное ниже, дается со ссылкой на фиг.1.

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

Этап 302 проверки ресурсов каналов связи между кольцевыми подсетями: проверка ресурсов каналов связи между кольцевыми подсетями, таких как каналы L1, L2, L3, L4, L5 и L6, на наличие перегрузки; если таковая отсутствует - переход к этапу 304 проверки ресурсов внутри кольцевых подсетей.

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

Этап 304 проверки ресурсов каналов связи внутри кольцевых подсетей: проверка ресурсов каналов связи внутри кольцевых подсетей R1, R2, R3, R4, R5, R6 и R7 на перегрузку. При наличии таковой - переход к этапу 306 для корректировки маршрутов внутри кольцевых подсетей, в противном случае - переход к этапу 305.

Этап 305 проверки баланса нагрузки внутри кольцевых подсетей: проверка, удовлетворяет ли показатель баланса нагрузки каждой из кольцевых подсетей R1, R2, R3, R4, R5, R6 и R7 заданному значению. Если да, то переход к этапу 307 для выявления существования центральной подсети во всей сети, в противном случае - переход к этапу 306. Под показателем баланса нагрузки подсети здесь понимается дисперсия коэффициентов использования ресурсов каналов связи в данной кольцевой подсети.

Этап 306 корректировки маршрутизации внутри кольцевой подсети: если показатель баланса нагрузки кольцевой подсети, например R1, не удовлетворяет заданному значению, или если ресурсы каналов связи внутри кольцевой подсети перегружены, то выполняют корректировку маршрутов в двух направлениях кольца для всех сервисов внутри подсети, переключение маршрута между двумя различными направлениями кольца для обеспечения баланса нагрузки данной подсети, а затем переход к этапу 304 проверки ресурсов каналов связи внутри кольцевых подсетей.

Этап 307 проверки существования центральной подсети во всей сети; при отсутствии таковой - завершение данного процесса оптимизации.

Этап 308 проверки баланса нагрузки по центральным подсетям: если установлено существование центральных подсетей, например, R1, R2, R3, L1, L2, L3 и L4, то выполняют проверку того, удовлетворяет ли общий показатель баланса нагрузки центральных подсетей заданному значению, если да - то завершение текущего процесса оптимизации, в противном случае - переход к этапу 309. Под общим показателем баланса нагрузки понимается дисперсия всех коэффициентов использования ресурсов каналов связи в данных центральных подсетях.

Этап 309 проверки условия завершения: если общий показатель баланса нагрузки центральных подсетей не удовлетворяет заданному значению, то выполняют проверку сходимости текущего суммарного показателя по всем центральным подсетям, причем суммарный показатель вычисляют по коэффициенту использования ресурсов и общему показателю баланса нагрузки. Указанный суммарный показатель вычисляют как сумму коэффициента использования ресурсов канала связи данной центральной подсети R, помноженного на соответствующий весовой коэффициент а, и общего показателя баланса нагрузки центральной подсети S, помноженного на соответствующий весовой коэффициент b. Если суммарный показатель удовлетворяет условию сходимости, т.е. не превышает значения оптимального целевого показателя Min(aR+bS), заранее вычисляемого в зависимости от состояния сети и результатов практического тестирования, то выполняют завершение текущего процесса оптимизации, в противном случае - проверяют количество циклов расчета маршрутов; если текущее количество циклов расчета превышает заданный лимит, то выполняют завершение процесса оптимизации, в противном случае - переходят к этапу 303 с перерасчетом маршрутов для всех сервисов, проходящих через этот канал связи.

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

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

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

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

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

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

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

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

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

Е2. проверку, меньше ли рассчитанный суммарный показатель рассчитанного ранее целевого оптимального значения; если да, то условие сходимости признают выполненным, в противном случае - невыполненным.