СПОСОБ ПОИСКА ЗАЩИЩЕННОГО ПУТИ В ЯЧЕИСТЫХ СЕТЯХ Российский патент 2011 года по МПК H04L12/56 

Область техники, к которой относится изобретение

Настоящее изобретение относится к области построения сетей передачи данных, более конкретно к поиску защищенного пути в ячеистой сети передачи данных, и в конкретном случае к способам расчета многопротокольных коммутируемых на основе признаков путей MPLS (МПКП, многопротокольная коммутация на основе признаков) с гарантированной зашитой с быстрым изменением маршрута (FRR, БИМ).

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

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

МПКП представляет собой развивающуюся технологию, которая улучшает масштабируемость и рабочие характеристики IP (ПИ, протокол Интернет) сетей, вместе с предоставлением новых услуг, ранее недоступных при использовании традиционного ПИ. В частности, МПКП обеспечивает возможность для провайдеров услуги управлять трафиком в своих сетях и предлагать услуги на основе качества обслуживания (QoS, KaO), включающие в себя гарантированную пропускную способность (полосу пропускания, BW (ПП)). При использовании МПКП коммутатор-маршрутизатор (LSR, КММ) многопротокольной коммутации на основе признаков вставляет метки в пакеты, поступающие из системы-источника (например, компьютера); все эти пакеты с метками затем следуют по одному и тому же пути коммутации по метке (LSP, ПКМ) в направлении КММ назначения, который извлекает метку из пакета и передает его в систему назначения.

На фиг.1 иллюстрируется путь ПКМ, который начинается в узле-источнике КММ А, проходит через транзитный узел КММ В и заканчивается в узле назначения КММ С. Таким образом, все пакеты, которые отображаются КММ на ПКМ, следуют пути А→В→С. Кроме того, показано, что пакеты компонуют с меткой МПКП в источнике КММ А и освобождают от метки МПКП в месте назначения КММ С.

Основное свойство МПКП представляет собой механизм, называемый быстрым изменением маршрута (БИМ). БИМ позволяет быстро изменять маршрут ПКМ на заранее сконфигурированный резервный ПКМ вокруг сетевого соединения сети или узла, в которых произошел отказ, где первый случай называется защитой соединения БИМ, в то время как последний называется защитой узла БИМ. Когда происходит отказ в защищенном соединении или в узле, трафик первичных ПКМ переключают на резервный ПКМ в направлении следующего сегмента (NH, СС) КММ или следующего за ним сегмента (NNH, ССС) КММ соответственно. Резервный ПКМ повторно соединяется с первоначальным путем первичных ПКМ в СС или ССС, который перенаправляет трафик в первичный ПКМ. Следует отметить, что такое приложение предполагает, что защищающий узел резервный ПКМ соединяется с первичным путем ПКМ в ССС, а не далее вдоль пути ПКМ (например, не в СССС). Резервный ПКМ может совместно использоваться множеством ПКМ. При использовании БИМ прерванный поток трафика может быть перенаправлен вокруг отказавшего узла/соединения в течение короткого интервала времени, меньше 50 миллисекунд, сводя таким образом к минимуму влияние на трафик.

На фиг.2 иллюстрируется защита соединения БИМ. ПКМ 1 (толстая линия) и ПКМ 2 (тонкая линия) обычно следуют пути А→В. Когда происходит отказ соединения между КММ А - КММ В, КММ А перенаправляет оба ПКМ 1 и ПКМ 2 в резервный ПКМ (пунктирная линия), который следует в КММ В (СС) через КММ С (резервный ПКМ совместно используется ПКМ 1 и ПКМ 2, это возможно, как отмечено выше). Путь резервного ПКМ повторно соединяется с исходным путем ПКМ 1 и ПКМ 2 в СС (следующий сегмент) КММ В, который перенаправляет трафик обратно в ПКМ 1 и ПКМ 2 соответственно.

На фиг.3. иллюстрируется защита узла БИМ. Пусть ПКМ 1 (толстая линия) и ПКМ 2 (тонкая линия) нормально проходят вдоль пути А→В→С. Когда происходит отказ КММ В, КММ А перенаправляет оба ПКМ 1 и ПКМ 2 в резервный ПКМ (пунктирная линия), который протекает в КММ С (ССС) через КММ D. Путь резервного ПКМ повторно соединяется с исходным путем ПКМ 1 и ПКМ 2 в ССС (следующий после следующего сегмента) КММ С, который перенаправляет трафик обратно в ПКМ 1 и ПКМ 2 соответственно. Для того чтобы сделать защиту действительной, первичный ПКМ и его резервные ПКМ должны быть проложены по различным маршрутам (разъединены), в противном случае в резервном ПКМ произойдет отказ, как только произойдет отказ в защищенном соединении или узле. Используя примеры по фиг.2 и фиг.3, путь резервного ПКМ, защищающего соединение (например, пунктирный путь, показанный на фиг.2), не должен использовать защищенное соединение (соединение АВ на фиг.2), и путь резервного ПКМ, защищающего узел (например, пунктирная линия на фиг.3), не должен использовать ни защищенный узел (узел В на фиг.3), ни любое из его соединений.

Детектирование отказа соединения может быть основано на сигналах тревоги физического уровня связи (например, SONET/SDH, СОСЕТЬ/СЦИ синхронная оптическая сеть/синхронная цифровая иерархия), детектируемого в этом соединении (соединение АВ на фиг.2). Детектирование отказа узла может быть основано на сигналах тревога либо уровня сети или уровня передачи данных (например, OSPF ППКП, протокол предпочтения кратчайшего пути или РРР, ПТТ, протокол канала связи с соединением точка-точка соответственно). Иногда и предпочтительно, учитывая механизм быстрого детектирования, отказ узла можно детектировать, используя сигналы тревоги физического уровня передачи данных соединения, расположенного перед отказавшим узлом (соединением АВ на фиг.3). В этом последнем случае для ПКМ может быть назначен защищающий соединение резервный ПКМ или защищающий узел резервный ПКМ для каждого сегмента, но не для обоих этих случаев, поскольку невозможно сделать различие между отказом соединения и отказом узла. Для обеспечения возможности применения всех этих сценариев детектирования отказа в данной заявке также предполагается, что ПКМ может быть назначена либо защита соединения или защита узла на каждый-сегмент, но не оба эти элемента.

Защита БИМ может быть определена как схема сегментированного резервирования, поскольку она основана на предоставлении резервного ПКМ для защиты от отказа отдельного сегмента (узла или соединения) вдоль пути первичного ПКМ. Таким образом, для полной защиты ПКМ требуется множество резервных ПКМ, по одному резервному ПКМ на защищаемый сегмент. Хотя один путь резервного ПКМ для каждого защищаемого сегмента должен быть отсоединен от пути первичного ПКМ по этому сегменту, разрешено использовать соединения и узлы с первичными ПКМ по другим сегментам и совместно использовать соединения, узлы и возможно также совместно использовать полосу пропускания с резервными ПКМ, защищающими другие сегменты первичного ПКМ. Такое совместное использование может чрезвычайно увеличить шансы того, что набор резервных ПКМ, который может полностью защитить ПКМ, фактически существует. Например, путь резервного ПКМ на фиг.2 не должен использовать защищенное соединение АВ, но может использовать любое другое соединение вдоль пути первичных ПКМ 1 и 2, например соединение, по которому ПКМ 1 и ПКМ 2 соединяются с КММ А.

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

Требования к ПКМ включают в себя КММ-источник, КММ назначения и дополнительные атрибуты, такие как полоса пропускания ПКМ (пропускная способность) и требования к защите БИМ; дополнительные требования могут представлять собой класс обслуживания (CoS, КлО), ограничение сегмента, двунаправленность и т.д.

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

Информация о резервном ПКМ может содержаться в сервере расчета пути (PCS, СРП), которая может представлять собой КММ любого рода или систему управления сетью. КММ-источник затем может запрашивать информацию о резервных ПКМ из СРП, когда он (КММ-источник) должен рассчитывать путь для ПКМ, защищенного БИМ. В качестве альтернативы, КММ-источник может запрашивать СРП самостоятельно рассчитать путь ПКМ, защищенного БИМ.

Результаты алгоритма поиска пути представляют собой оптимальный, реально осуществимый путь, который удовлетворяет требованиям ПКМ, без нарушения ограничений топологии РТ. Существуют различные критерии оптимизации, наиболее популярный из которых представляет собой самый короткий путь, в котором требуется найти реально осуществимый путь с наименьшей суммарной метрикой. Поиск пути ПКМ на основе критерия самого короткого пути обычно называется "ограниченный самый короткий путь первым" (CSPF, ОСКП). ОСКП имеет две эвристические фазы: (1) На первой фазе удаляют все практически неосуществимые соединения ("направления соединения"). Что касается доступности полосы пропускания, это означает, что любое направление соединения, которое не удовлетворяет требованиям ПП для ПКМ, должно быть исключено из топологии РТ. (2) На второй фазе самый короткий путь между КММ-источником и КММ назначения рассчитывают, используя стандартный алгоритм, такой как алгоритм Дейкстра (Dijkstra).

На фиг.4 иллюстрируется топология РТ, содержащая четыре КММ (А, В, С, D), взаимно соединенные соединениями, где каждое из направлений соединения (стрелка) имеет заранее сконфигурированную метрику и доступную полосу пропускания ПП. Например, существует направление соединения от КММ В к КММ D, имеющее метрику = 5 и доступную ПП=100; метрика и ПП (в скобках) показаны в прямоугольной метке, показанной рядом с направлением соединения. КММ А и С источника/назначения представлены как темные прямоугольники, в то время как транзитные КММ представлены как белые прямоугольники.

Предположим, что требуется рассчитать путь ПКМ с ПП=200 от КММ А до КММ С.

Фаза 1: все невыполнимые на практике соединения отбрасывают, в результате чего получают топологию, показанную на фиг.5. Например, направление соединения от В до D отбрасывают, поскольку оно имеет ПП=100<200.

Фаза 2: рассчитывают самый короткий путь. В этом случае, остались только два возможных пути от КММ А до КММ С:

(1) Путь А→С, с метрикой, равной 2

(2) Путь А→D→С, с метрикой, равной 6+3=9.

Следует отметить, что путь, который пересекает КММ более чем один раз (например, А→D→А→С), формируя таким образом "петлю трафика", запрещен и таким образом не учитывается. Путь А→С представляет собой самый короткий путь, и таким образом его выбирают, как показано на фиг.6. В этом примере расчет самого короткого пути очень прост; и в общем случае используют систематический способ, такой как алгоритм Дейкстра или алгоритм Беллмана-Форда.

Расчет пути становится более сложным, когда ПКМ, который требуется установить, имеет требования защиты БИМ. Такие требования могут устанавливать: (1) защиту соединения; (2) защиту узла (за исключением последнего направления соединения по пути, который должен иметь защиту соединения); (3) защиту узла-соединения, в котором требуется либо защита узла или защита соединения и в котором защита узла (везде, где это доступно) должна быть предпочтительной по сравнению с защитой соединения.

Проблема возникает, когда защиту БИМ требуется гарантировать вдоль пути ПКМ. Таким образом, первичный ПКМ должен быть защищен от любого одиночного отказа сегмента (соединения или узла) вдоль их пути. Такой ПКМ рассматривают как полностью защищенный БИМ первичный ПКМ. Любой путь, который не удовлетворяет этому требованию, должен быть отброшен.

Если требуемое гарантированное БИМ представляет собой защиту соединения, простое отбрасывание направлений соединения, в которых не предусмотрена защита соединения (Фаза 1), может работать. Например, если только направление соединения от А до С на фиг.4 имеет защиту соединения (то есть существует резервный ПКМ от А до С, который защищает от отказа направления соединения А→С), топология после отбрасывания должна выглядеть так, как показано на фиг.6. В этом случае, существует только один реально выполнимый путь для требуемого ПКМ: А→С. Проблема состоит в том, что простое правило отбрасывания в соответствии с Фазой 1 иногда не помогает, когда для пользователя сети требуют обеспечить гарантированную защиту узла БИМ или гарантированную защиту БИМ узла-соединения. Это случается из-за того, что путь ПКМ, представляющий интерес, не известен во время Фазы 1 процедуры поиска пути. Например, в топологии, показанной на фиг.7, имеется резервный (показанный пунктиром) ПКМ, предназначенный для защиты от отказа узла В, если путь ПКМ представляет собой А→В→С.Однако не существует резервный ПКМ для защиты от отказа узла В, если путь ПКМ представляет собой А→В→Е; поэтому направление соединения А→В является практически осуществимым, если путь ПКМ представляет собой А→В→С, но практически неосуществимым, если путь ПКМ представляет собой А→В→Е. Поскольку путь ПКМ не известен на фазе 1, отбрасывание направления соединения А→В на фазе 1 было бы неправильным действием, поскольку путь ПКМ, представляющий интерес, возможно, будет выбран с использованием пути А→В→С на фазе 2.

Двухэтапный подход к сегментированной резервной схеме используется в публикации "A Scalable and Decentralized Fast-Rerouting Scheme with Efficient Bandwidth Sharing" by Simon Balon et al., Dec - 13, 2005: в этом подходе вначале рассчитывают первичный путь ПКМ, используя один из доступных алгоритмов, таких как двухфазный ОСКП, описанный выше. Для полученного пути-кандидата алгоритм затем пытается назначить резервные ПКМ. Недостаток такого подхода состоит в том, что он не позволяет гарантировать полностью защищенный БИМ первичный ПКМ, даже если такой действительно существует. Как отмечено в статье, "Когда первичный путь известен, мы рассчитываем набор резервных ПКМ, требуемых для предотвращения любого возможного отказа узла вдоль этого пути. Если резервный путь не может быть найден для конкретного предположения отказа узла, мы предполагаем, что будет происходить только отказ соединения, и рассчитываем новый резервный путь. Если такой расчет снова окажется неудачным, запрос отбрасывают".

Другой двухэтапный подход для сегментированной схемы резервирования используется в публикации "A Distributed Primary-Segmented Backup Scheme for Dependable Real-Time Communication in Multihop Networks" by Ranjith и др., 2002: здесь распознают преимущества сегментированной схемы резервирования (которые представляют собой защиту БИМ) над несегментированным резервированием, но предполагают, что первичный путь уже выбран и остается только рассчитать оптимальные резервные пути для него. Однако если первичный путь уже выбран, он может проходить через соединения и узлы без доступных резервных ПКМ, и таким образом защита не может быть гарантирована. Как упомянуто в статье, "распределенный алгоритм необходимо выполнять дважды, то есть в первый раз для поиска первичного пути с минимальной стоимостью между источником и назначением и во второй раз для поиска набора сегментированных резервных путей с минимальным общим весом для этого первичного пути".

В публикации 2003/0229807 А1 патента США описана технология защиты сегмента для сети, содержащая два этапа: рассчитывают оптимальный (самый короткий) активный путь (АР, АП), делят его на несколько активных сегментов (AS, AC) и затем защищают каждый АС обходным путем, называемым резервным сегментом или BS (PC). Фактически, в публикации 2003/0229807 США описывается еще одна версии известного принципа "активный путь первый (APF, АПП).

Аналогичный подход описан авторами Yu Liu и David Tipper в их статье "Successive Survivable Routing for Node Failures", где рабочие пути задают до того, как предварительно планируемые резервные пути будут проложены и зарезервированы.

Другой известный подход называется способом К Самых Коротких Путей (KSP, КСКП), в котором алгоритм находит К самых коротких активных путей (АП) и затем проверяет их один за другим в порядке увеличения их стоимости до тех пор, пока не будет найден резервный путь для всех путей, прошедших проверку. Поскольку способ КСКП основан на ограниченном количестве априори выбранных АП, он может не найти защищенный путь, даже если такой существует.

На основе описанного выше можно видеть, что задача поиска гарантированного пути защищенным сегментом в ячеистой сети (например, в полностью защищенной БИМ в первичном ПКМ в сети МПКП) не может быть эффективно решена, используя ни один из упомянутых выше 2-фазных алгоритмов поиска пути.

Одновременно с этим гарантированная защита БИМ имеет первостепенную важность для провайдеров услуги. Сущность множества приложений Интернет, таких как электронный бизнес и электронная коммерция, представляет собой возможность предложить клиентам круглосуточный, без перерыва, доступ к сети Интернет. Отказ или поломка оптоволоконного кабеля или узла маршрутизации/коммутации, которые составляет Интернет, может сделать недоступным жизненно важное соединение провайдера услуг Интернет для их клиентов. Когда пакеты передают со скоростью 10 Гбит в секунду или больше, одна секунда неактивности означает, что миллионы байтов ценных данных клиента будут отброшены, и гарантии КаО не будут выполнены таким образом; не говоря уже о приложениях критически важных задач, где такие отказы могли бы иметь катастрофические последствия.

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

Таким образом, цель настоящего изобретения состоит в том, чтобы разработать способ выбора пути, который позволяет находить оптимальный путь передачи данных в ячеистой сети, которые мог бы иметь полностью гарантированную защиту сегментированного узла или защиту узла-соединения. В конкретном практическом случае конкретная цель состоит в том, чтобы найти первичный ПКМ в ячеистой сети МПКП с полностью гарантированной защитой БИМ узла или узла-соединения.

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

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

определяют требуемый тип защиты, который представляет собой либо защиту узла или защиту узла-соединения,

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

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

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

- b1) в случае защиты узла, если узел, к которому ведет данный специфичный сегмент L пути соединения, представляет собой назначение первичного пути (то есть представляет собой так называемый "последний сегмент");

- b2) в случае требования защиты узла-соединения, если сегмент N пути узла, к которому ведет данный специфичный сегмент L пути соединения, не может быть защищен в соответствии с правилом (а).

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

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

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

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

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

(1) упомянутый узел источника (КММ); (2) упомянутый узел назначения (КММ); (3) Требования к качеству обслуживания (КаО), содержащие, по меньшей мере, значение требуемой полосы пропускания/пропускной способности пути передачи данных (ПКМ), который включает в себя так называемый случай "максимальных усилий", когда полоса пропускания может быть равна нулю; (4) один из упомянутых типов требуемой защиты (БИМ), либо гарантированной (полной) защиты узла или гарантированной (полной) защиты соединения. Дополнительные (используемые в случае необходимости) требования могут содержать, например, максимальную метрику (длина, стоимость и т.д), разрешенную вдоль пути, класс обслуживания (КлО), двунаправленность пути, явные ограничения пути, ограничения отсутствия петель (то есть путь передачи данных не может пересекать один узел более чем один раз) и т.д.

Способ содержит: используют информацию топологии сети. Информация топологии может быть представлена как взвешенный ориентированный граф узлов и взаимно соединяющих их соединений, где каждый узел и соединение ассоциированы с ресурсами и/или ограничениями топологии, включающими в себя информацию, относящуюся к доступным резервным путям узла и резервным путям соединения. В частности, каждое соединение, соединяющее исходящий порт одного узла (КММ) с входящим портом другого узла (КММ), ассоциировано с весом, известным также как метрика или стоимость, доступной ПП (например, рассчитываемой как коэффициент нагрузки линии минус полоса пропускания, зарезервированная для существующих ПКМ в сети), и доступные резервные пути (ПКМ) для защиты соединения и для защиты узла; дополнительные ресурсы могут представлять собой доступную ПП для класса обслуживания (КлО), совместно используемых групп соединения риска (SRLG, СГСР) и т.д. Пример ресурсов узла представляет собой внутренняя память узла, доступная для сохранения параметров трафика для ПКМ.

Предпочтительно и в соответствии с пояснениями, приведенными в разделе "Уровень техники":

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

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

С этой целью автор заявки предлагает следующую версию способа:

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

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

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

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

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

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

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

Изобретение будет дополнительно подробно описано со ссылкой на следующие неограничительные чертежи.

На фиг.1 (предшествующий уровень техники) схематично иллюстрируется путь ПКМ в сети МПКП.

На фиг.2 (предшествующий уровень техники) схематично иллюстрируется защита сегмента соединения (БИМ соединение).

На фиг.3 (предшествующий уровень техники) схематично иллюстрируется защита сегмента узла (БИМ узла).

На фиг.4 (предшествующий уровень техники) представлен пример топологии сети.

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

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

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

На фиг.8 иллюстрируется пример предложенного преобразования топологии сети для выбора гарантированного пути передачи данных защищенного узла.

На фиг.9 иллюстрируется пример предложенного преобразования топологии сети для выбора гарантированного пути передачи защищенного узла-соединения.

На фиг.10 представлена упрощенная блок-схема последовательности операций предложенного алгоритма поиска пути.

На фиг.11 более подробно показана блок-схема последовательности операций вновь предложенного этапа преобразования топологии сети.

На фиг.12 иллюстрируется другой пример графа топологии сети перед вводом фиктивных соединений внутри узла.

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

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

На фиг.15 показана еще одна возможность графа исходной топологии сети перед вводом фиктивных соединений внутри узла.

На фиг.16 иллюстрируется преобразованный граф топологии сети после ввода соответствующего соединения внутри узла в граф по фиг.15.

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

На фиг.18 иллюстрируется применение ограниченного алгоритма Дейкстра для получения пути передачи данных БИМ без петель.

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

При описании уровня техники была сделана ссылка на фиг.1-7. В следующем подробном описании изобретения общие термины полная/гарантированная защита узла или узла-соединения могут взаимозаменяемо использоваться с терминами защита сегмента БИМ, защита узла БИМ или защита узла-соединения БИМ, которые, в частности, подходят для сетей МПКП. То же относится к общим терминам узел, путь и к конкретным терминам КММ, ПКМ соответственно.

На фиг.8 отображается ввод операции соединения внутри узла (то есть ввод фиктивных соединений внутри узла) в графе топологии сети для получения гарантированной защиты узла БИМ для направления соединения от узла (КММ) А к узлу В. В данном направлении узел А имеет соединение с портом 1 узла В, который, в свою очередь, имеет соединение из порта 2 с портом 1 узла С и другое соединение из порта 3 с портом 1 узла D. На этих и на других чертежах порты узлов показаны как пронумерованные кружки, в то время как значения метрик соединений показаны в небольших квадратах на соответствующих соединениях. Под метриками можно понимать как весовые значения, которые могут отображать длину, стоимость, качество соединения и т.д. Граф топологии также имеет резервный сегмент защиты узла (ПКМ, показанный прямой пунктирной линией), начинающийся от узла А и заканчивающийся в узле С, который обеспечивает защиту от отказа узла В. Во время этапа формирования соединения внутри узла (показан как стрелка INC (ввод) между исходным и преобразованным графом) соединение внутри узла с нулевой метрикой назначают в узле В, в направлении от порта 1 к порту 2, поскольку существует резервный ПКМ для защиты прежде всего пути от А к В до С ПКМ, защищающий от отказа узла В. Фиктивные соединения внутри узла с нулевой метрикой ("бесплатные") помечены "0". Следует отметить, что соединение внутри узла с ненулевой метрикой назначают для узла В от порта 1 до порта 3, поскольку отсутствует резервный ПКМ для защиты первичного пути от А до В и до D ПКМ, защищающий от отказа узла В. В результате при выборе требуемого пути передачи данных по полученному преобразованному графу первичный защищенный путь ПКМ может проходить от А до В и до С, но не может проходить из А в В и в D.

Резервный ПКМ защиты узла А→С (показанный прямой пунктирной линией) представлен на чертеже только схематично; в действительности он может проходить через множество промежуточных КММ, за исключением узла В и его соединения (в соответствии с так называемым "правилом резервирования узла"), поскольку в этих соединениях также произойдет отказ, при отказе их узла В.

На фиг.9 отображается ввод соединения внутри узла в топологии сети для получения гарантированной защиты узел-соединение БИМ для направления соединения из узла (КММ) А в узел (КММ) В. Эта топология аналогична представленной на фиг.8, но в ней допускается, что направление соединения от узла А до В также имеет соединение, защищающее соединение резервной ПКМ от А до В (показано изогнутой пунктирной линией). Во время этапа ввода соединения внутри узла (INC) назначают соединение внутри узла с нулевой метрикой в узле В из порта 1 в порт 2 (как на фиг.8), поскольку существует резервный ПКМ для защиты первичного пути ПКМ от А до В и до С против отказа узла В. Однако, кроме того, соединение внутри узла с ненулевой метрикой, помеченное как "Р" (метрика ухудшения), назначают для узла В из порта 1 в порт 3, поскольку в случае потенциального выбора пути А→В→D ПКМ все еще остается резервный ПКМ для защиты потенциального ПКМ, по меньшей мере, от отказа направления соединения от А в В. В результате, когда выбирают защищенный первичный путь ПКМ, он наиболее вероятно пройдет от А до В и до С, но, в качестве альтернативы, с меньшими шансами (из-за метрики Р ухудшения), пройдет от А до В и до D. Предпочтительно разработчик сети устанавливает Р>0 для назначения предпочтения, для защиты сегмента узла.

Однако установку Р=0 можно использовать для назначения защите соединения БИМ того же предпочтения, что и для защиты узла БИМ.

Резервный путь ПКМ А→В, защищающий соединение (изогнутая пунктирная лиши), показан схематично. В действительности, он может пересекать множество промежуточных КММ, но он не должен использовать те же порты в качестве защищенного соединения (порт 1 узла А и порт 1 узла В), поскольку в них также произойдет отказ, как только произойдет отказ основного направления соединения из А в В ("правило резервирования соединения").

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

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

Этап 14 представляет собой этап ввода фиктивного соединения внутри узла в обрезанный граф. Способ ввода этих фиктивных соединений внутри узла зависит от присутствия в обрезанном графе резервных путей для узлов и их соединений. Это более подробно поясняется на фиг.11 и в разделе "Подробное описание изобретения". Этап 14 приводит к получению графа с преобразованной топологией.

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

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

На фиг.11 подробно иллюстрируется этап 14 предложенного способа.

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

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

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

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

Однако иногда "защита только узла" не может быть достигнута в сети. Если обеспечивается смешанная защита соединения - узла в соответствии с требованиями пользователя (этап 14.4), на этапе 14.5 обеспечивается ввод дополнительных фиктивных соединений в узлы сети. Ожидается, что эти соединения будут "более дорогими" (ненулевые метрики) с тем, чтобы предоставить предпочтение для соединений с нулевыми метриками. Такие фиктивные соединения внутри узла с ненулевыми метриками вставляют в узлы, когда входящее соединение узла имеет резервный путь соединения, но при этом не существует резервный путь узла из этого соединения в следующий после следующего сегмента (ССС) ССС. Ненулевое соединение внутри узла вставляют между двумя портами, один из которых соединен с защищенным входящим соединением и другой с исходящим соединением, которое ведет к ССС. Другими словами, если защита узла не доступна из соединения в ССС, но защита соединения доступна и разрешена, такое соединение все еще можно использовать, хотя и с другим предпочтением.

На фиг.12 представлен образец графа топологии сети, содержащего узлы (КММ) А, В, С и Z, взаимно соединенные следующим образом и формирующие следующие резервные пути друг для друга:

(1) двунаправленное соединение АВ (метрика 1 из А в В и 9 из В в A), BZ, ВС, АС, CZ

(2) резервный ПКМ, защищающий узлы (пунктирные линии): А→В (помечен как N1 и защищающий от отказа С), А→С (N2, В), В→Z (N3, С), С→Z (N4, В)

(3) резервный ПКМ, защищающий соединение С→Z (помечен как пунктирная линия L1 и защищающий от отказа направление соединения из С в Z).

Если требуется найти первичный путь ПКМ из А в Z, требуемый ПКМ может иметь гарантированную защиту узла БИМ (защита сегмента полного узла). Требуется учитывать, что:

a) Поскольку последний сегмент первичного ПКМ никогда не будет защищен как узел (поскольку, если произойдет отказ узла Z, также произойдет отказ ПКМ), в данной заявке всегда можно предположить, что последний сегмент должен иметь гарантированную защиту соединения.

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

c) Источник (назначение) КММ содержит точку источника (назначения) ПКМ, помеченную как "S" ("D"), каждая из которых представляет собой виртуальный порт, который помечает происхождение (конец) первичного ПКМ соответственно.

d) Предполагается, что все резервные ПКМ выполняют правило резервирования узла и правило резервирования соединения, которые были определены выше.

В таком простом примере можно видеть, что существует четыре возможных пути ПКМ (при этом каждый узел появляется только однажды на пути, чтобы исключить бесконечные петли): А→В→С→Z, А→В→Z, А→С→В→Z, А→С→Z, из которых только первый путь может быть осуществлен на практике благодаря тому, что он имеет защиту узла по всем сегментам (N2 для случая отказа В, N3 для случая отказа С) и защиту соединения для последнего сегмента (L1 для случая отказа направления соединения С-Z).

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

На фиг.13 показана обрезанная топология после окончания этапа соединения внутри узла остались только следующие соединения внутри узла:

(1) Фиктивные соединения с нулевой метрикой из "S" (источник) во все направления исходящих соединений (выходные порты 1 и 2, помеченные как 01, 02)

(2) Фиктивное соединение с нулевой метрикой из любого направления входящего соединения (которое имеет резервный ПКМ, защищающий соединение) в назначение "D". Например, оно представляет собой входной порт 2 (12) узла Z в "D" (благодаря" резервному ПКМ для L1 по фиг.12).

(3) Фиктивное соединение с нулевой метрикой в узле, если узел имеет защищающий резервный путь в обрезанном графе. Оно включает в себя порт из 3 в 2 узла В (ввиду резервирования ПКМ для N2), порт из 2 в 1 (N4) для узла В, порт из 3 в 2 (N1) для узла С, порт из 2 в 1 (N3) для узла С - см. фиг.12.

На фиг.14 показан выбранный первичный путь ПКМ после выполнения стандартного алгоритма самого короткого пути, такого как алгоритм Дейкстра, по обрезанной топологии. Выбранный путь представлен как толстая линия А→В→С→Z с метрикой 1+1+4=6 и имеет защиту узла в случае отказа В или С и защиту соединения, в случае отказа последнего сегмента С-Z. В таком простом примере можно видеть, что отсутствует какой-либо другой реально осуществимый путь из А в Z. Например, здесь отсутствуют фиктивные соединения внутри узла из порта 1 узла Z в "D", и таким образом ПКМ не может быть разрешено проходить через направление В-Z соединения.

На фиг.15 представлен образец топологии сети, содержащий узлы (КММ) А, В, С и Z, взаимно соединенные следующим образом: (1) двунаправленные соединения, как на фиг.12 (2), резервные ПКМ, защищающие узел: С→Z (помечен как N1, и защищающий от отказа В), А→С (N2, В), В→Z (N3, С) (3) резервный ПКМ, защищающий соединение С→Z (помечен как L1 и защищает от отказа направления соединения из С в Z), А→В (L2), В→Z (L3). Требуется найти первичный путь ПКМ из А в Z, на котором этот первичный ПКМ должен иметь гарантированную защиту соединения - узла БИМ. В этом простом примере можно видеть, что существуют четыре возможных пути ПКМ, как на фиг.12 (А→В→С→Z; А→В→Z; А→С→В→Z; А→С→Z), из которых только два осуществимы на практике: (1) А→В→С→Z из-за того, что он имеет защиту узла или соединения по всем сегментам (N2 в случае отказа В, N3 в случае отказа С, L1 в случае отказа С-Z) (2) А→В→Z из-за того, что он имеет защиту узла или соединения по всем сегментам (L2 в случае отказа А-В, L3 в случае отказа В-Z).

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

На фиг.16 показана обрезанная топология после выполнения этапа соединения внутри узла. Остались только следующие соединения внутри узла: (1) направление соединения с нулевой метрикой из "S" во все направления исходящих соединений (всегда выполняются для узла-источника); (2) направление соединения с нулевой метрикой из любого направления входящего соединения, которое имеет защищающее резервное соединение ПКМ для "D" (узел назначения). Это включает в себя Z порт 2 для "D" (благодаря наличию резервного ПКМ L1) и Z порт 1 для "D" (L3); (3) направление " соединения с нулевой метрикой из любого направления входящего соединения, которое имеет резервный ПКМ, защищающий узел, в направлении исходящего соединения, который проходит в ССС резервного ПКМ. Он включает в себя узел В порт из 3 в 2 (благодаря наличию резервного ПКМ N2), узел В порт из 2 в 1 (N1), узел С порт из 2 в 1 (N3); (4) Направление соединения с заданным ухудшением Р ненулевой метрики (Р=99 используется в данном примере) из любого направления входящего соединения, которое имеет резервный ПКМ, защищающий соединение, в любое направление несогласованного исходящего соединения. Это включает в себя узел В порт из 3 в 1 (благодаря наличию резервного ПКМ L2).

На фиг.17 показан выбранный первичный путь ПКМ после выполнения стандартного алгоритма поиска самого короткого пути, такого как алгоритм Дейкстра по обрезанной топологии. В таком простом примере можно просто видеть, что на практике могут быть найдены два выполнимых пути: (1) А→В→С→Z с метрикой 1+1+4=6; (2) А→В→Z с метрикой 1+99+1=101. Путь А→В→С→Z является "более коротким", и таким образом его выбирают. Этот путь имеет защиту от отказа В или С и защиту соединения от отказа для последнего сегмента С-Z. Следует отметить: что, хотя путь А→В→Z короче по метрике соединений (1+1=2), ухудшение метрики внутри узла, равное 99 в узле В, значительно увеличивает общую метрику, и в конечном итоге его не выбирают. Ухудшение внутри узла поэтому определяет заданное предпочтение для защиты узла, если доступный (А→В→С→Z имеет полную защиту узла), через защиту соединения (А→В→Z полностью защищен по соединению).

Фиг.18 помогает пояснить пример определения гарантированного пути БИМ без петель в иллюстрируемой сети.

Пусть показанная сеть фактически представляет ее преобразованный граф. Здесь применяют ограниченный алгоритм Дейкстра для преобразованного графа. Ограниченный алгоритм Дейкстра описан, например, авторами Timothy Y. Chow, Fabian Chudak and Anthony Ffrench в их публикации "Fast Optical Layer Mesh Protection Using Pre-Cross-Connected Trails", Section 7. Ограниченный алгоритм Дейкстра работает с ориентированным графом, с узлом (А)-источником, где каждое из соединений имеет неотрицательный вес.

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

Основной подход ограниченного алгоритма Дейкстра состоит в следующем: выполняют пробу "перехода вперед" из текущего активного узла. Предположим, что С представляет собой активный узел и что ABC представляет собой активный частичный путь. Рассматривают каждое соединение, исходящее из узла С. Соединение запрещено, если оно проходит в узел, который уже содержится в активном частичном пути. Запрещенные соединения игнорируют и выполняют следующий переход для учета других исходящих соединений.

Найдем самый короткий гарантированный путь БИМ без петель из А в D в иллюстрируемом преобразованном графе.

Следует отметить, что в случае игнорирования ограничения отсутствия петель самый короткий путь от А до D должен быть определен как А→В→С→В→D. Однако, если ограничение отсутствия петель действительно, этот путь является недопустимым, поскольку он дважды содержит узел В, то есть формирует петлю.

Первоначально А представляет собой активный узел. Если выполнить (с помощью ограниченного алгоритма Дейкстра) пробный переход вперед, существует один возможный путь А→В→С. Этот путь становится текущим активным частичным путем, и узел С становится текущим активным узлом.

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

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

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

Изобретение относится к области сетей передачи данных. Технический результат заключается в обеспечении защиты сегментированного узла. Сущность изобретения заключается в том, что способ содержит этапы, на которых: определяют требуемый тип защиты и дополнительно выбирают каждый конкретный сегмент пути требуемого пути передачи данных на основе исходных требований пользователя и информации о топологии сети. Каждый конкретный сегмент N пути узла для пути передачи данных выбирают, обеспечивая то, что он может быть защищен в сети резервным путем узла, удовлетворяющим исходным требованиям пользователя. Каждый конкретный сегмент L пути соединения для пути передачи данных выбирают, если он может быть защищен в сети резервным путем соединения, удовлетворяющим исходным требованиям пользователя и, если сегмент N пути узла, к которому ведет сегмент L, не может быть защищен соответствующим резервным путем узла. 13 з.п. ф-лы, 18 ил.

1. Способ выбора полностью защищенного пути передачи данных между источником и узлом назначения в ячеистой сети, причем упомянутый путь передачи данных собран из сегментов пути, каждый из которых представляет либо сегмент N пути узла или сегмент L пути соединения, и каждый из них защищен резервным путем в упомянутой сети, в котором каждый сегмент N узла пути содержит узел, соединение, входящее в упомянутый узел, и соединение, исходящее из упомянутого узла, в то время как каждый сегмент L пути соединения содержит одиночное соединение, исходящее из одного ассоциированного узла и входящее в другой ассоциированный узел, способ содержит этап, на котором определяют требуемый тип защиты для упомянутого пути передачи данных, который представляет собой либо защиту узла, или защиту узла - соединения, отличающийся тем, что при определении первичного пути, который представляет собой упомянутый полностью защищенный путь передачи данных, в результате выбора каждого конкретного сегмента пути для упомянутого первичного пути в соответствии с исходными требованиями пользователей и информацией о топологии сети, и с использованием следующих правил:
а) для любого из упомянутых типов защиты выбирают конкретный сегмент N пути узла для первичного пути после обеспечения того, что упомянутый конкретный сегмент N пути узла может быть защищен в сети резервным путем узла, удовлетворяющим упомянутым исходным требованиям пользователя,
b) если определена защита узла, выбирают для первичного пути только одиночный конкретный сегмент L пути соединения, содержащий соединения, входящие в упомянутый узел назначения, и после обеспечения того, что упомянутый одиночный конкретный сегмент L пути соединения может быть защищен в сети резервным путем соединения, удовлетворяющим упомянутым исходным требованиям пользователя,
c) если определена защита узел - соединение, выбирают для первичного пути конкретный сегмент L пути соединения, только если вместо этого невозможно выбрать сегмент N пути узла, и после обеспечения того, что упомянутый конкретный сегмент L пути соединения может быть защищен в сети резервным путем соединения, удовлетворяющим упомянутым исходным требованиям пользователя.

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

3. Способ по п.1 или 2, в котором путь передачи данных представляет собой путь коммутации по метке (ПКМ), ячеистая сеть представляет собой сеть с многопротокольной коммутацией на основе признаков (МПКП), и упомянутая защита сегмента гарантируется защитой с быстрым изменением маршрута (БИМ).

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

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

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

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

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

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

10. Способ по п.9, в котором алгоритм расчета представляет собой ограниченный алгоритм Дейкстра для поиска упомянутого оптимального пути без петель.

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

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

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

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