Способ поиска защищенного пути в ячеистых сетях

Способ поиска защищенного пути в ячеистых сетях

Иллюстрации

Показать все

Реферат

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

Настоящее изобретение относится к области построения сетей передачи данных, более конкретно к поиску защищенного пути в ячеистой сети передачи данных, и в конкретном случае к способам расчета многопротокольных коммутируемых на основе признаков путей 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 можно использов