защита от p-цикла

Схема защиты p-цикла — это метод защиты ячеистой сети от сбоя канала, обладающий преимуществами скорости восстановления кольца и эффективности емкости ячеистой сети, аналогичной защите общего резервного пути (SBPP). Защита p-цикла была изобретена в конце 1990-х годов, исследования и разработки проводились в основном Уэйном Д. Гровером и Д. Стамателакисом.

Обзор p-цикла

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

Рис. 1. p-цикл в ячеистой сети, создающий кольцевую структуру.

Рис. 2. Сбой в p-цикле, показывающий два узла, участвующих в восстановлении.

Рис. 3. Отказ межсетевого пролета и восстановление этого звена с помощью p-цикла.

Рис. 4. Гамильтонов p-цикл, путь защиты проходит через все узлы сети только один раз

Рис. 5. Непростой p-цикл, путь защиты проходит через синий узел более одного раза.

Одним из ключевых отличий между схемой на основе кольца и схемой с p-циклом является способность p-цикла защищать каналы, которые не находятся в кольце p-цикла, как показано на рисунке 3. Возможность защиты двух каналов для каждый резервный канал, назначенный p-циклу, позволяет достичь эффективности пропускной способности, подобной ячеистой. Эта особенность придает p-циклу дополнительную эффективность по сравнению с кольцевыми схемами. «Еще одна упущенная из виду особенность p-цикла заключается в том, что рабочие пути могут свободно маршрутизироваться по сетевому графу и не ограничиваться маршрутами, ограниченными кольцом» .

Типы P-циклов

P-циклы бывают нескольких вариаций в зависимости от того, как они защищают данную сеть и лежащую в ее основе архитектуру. Доступны следующие типы p-циклов: Гамильтониан , Простой , Непростой , Промежуточный , Окружающий узел , Путь и Поток . Гамильтониан . , простой и непростой названы в честь их базовой архитектуры (по отношению к сети) P-циклы Span, Node, Path и Flow названы в честь типа защиты, предлагаемой сети.

• Гамильтониан — p-цикл, в котором путь защиты проходит через все узлы сети только один раз. Этот p-цикл показан на рисунке 4.

• Простой — p-цикл, в котором путь защиты не обязан проходить через все узлы сети. P-циклу разрешено проходить через любой узел только один раз, как показано на рисунке 1.

• Непростой — p-цикл, в котором пути защиты разрешено проходить через любой заданный узел более одного раза. Это показано на рисунке 5.

• Span p-цикл - p-цикл, основная задача которого заключается в защите участков или связей, находящихся за пределами самого p-цикла. Этот тип p-цикла показан на рисунке 3.

• Окружение узла — p-цикл, защищающий в случае выхода узла из строя. В этом типе трафик, который проходил через этот узел до сбоя, перенаправляется на соседние узлы, окружающие вышедший из строя узел, но не через вышедший из строя узел.

• P-цикл защиты пути — p-цикл, который защищает весь путь от источника до места назначения, пока все узлы находятся в p-цикле.

• P-цикл потока - p-цикл, который обеспечивает защиту каналов, находящихся в p-цикле, в отличие от схемы защиты Span p-цикла.

Проектирование и формирование p-циклов

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

Централизованный

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

Модели целочисленного линейного программирования

В этой модели есть несколько методов, которые используются для создания приемлемых p-циклов для защиты сети, некоторые из них включают:

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

• Совместная оптимизация мощности . В этом методе оптимизация распространяется не только на резервную мощность сети, но и на общую мощность сети. Сюда входят резервная мощность и рабочая мощность сети. Еще одним отличием является то, что маршрутизация по рабочей емкости не производится до формирования p-цикла. Сначала для каждой пары источник/назначение рассчитывается вариант рабочего маршрута, затем из всех найденных возможных решений выбирается пара с добавлением резервной мощности, учитываемой для оптимизации общей пропускной способности сети. Модель этого метода можно найти в [1].
• Оптимизация защищенной рабочей емкости . Эта модель отличается от двух других моделей тем, что в ней первыми обнаруживаются p-циклы. Существуют некоторые соображения при создании р-циклов, основанные на идее оптимизации общего объема рабочих каналов, которые необходимо защитить. После того, как p-циклы найдены, рабочий запрос направляется в сеть в пределах домена защиты p-циклов. Эта концепция известна как защищенный диапазон работоспособности (PWCE).

Эвристический метод

Первый метод создания p-циклов требует больших вычислительных ресурсов, когда количество узлов велико. Представленный эвристический метод под названием unity-p-цикл на основе ER показывает привлекательное решение проблемы создания p-циклов без использования ILP. Этот метод также имеет решение, близкое к оптимальному, но без необходимости дополнительного вычислительного времени. Общая идея алгоритма заключается в выявлении единичных p-циклов, способных защитить как можно больше работающих звеньев, что существенно уменьшает количество необходимых для защиты запасных блоков. « Единичный p-цикл способен защитить одно рабочее звено в противоположном направлении на каждый отрезок цикла и два рабочих звена на каждый разнесенный отрезок. Количество запасных звеньев единичного p-цикла равно числу отрезков на цикле». Отношение, называемое ER, определяется как количество рабочих звеньев, защищенных единичным p-циклом, к количеству резервных модулей. Чем выше соотношение, тем выше эффективность защитных p-циклов, и, следовательно, именно на это и нацелен алгоритм.

Этот метод можно объяснить следующим образом, как показано в [6] и показано здесь:

1. На основе алгоритма из [7] Найдите возможные циклы и определите работоспособность каждого на основе одного из алгоритмов кратчайшего пути .
2. Рассчитайте соотношение ER единичных циклов для циклов, вычисленных на шаге 1.
3. На основе расчета ER выберите цикл с самым высоким ER.
4. Удалите рабочие звенья, которые можно защитить выбранным циклом сверху, и обновите работоспособность.
5. Повторяйте вышеуказанные шаги до тех пор, пока рабочая мощность на каждом пролете не станет равна 0.

Алгоритм трансграничной связи

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

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

Распределенный

Распределенный метод создания p-циклов отличается от централизованного подхода по ряду причин. Основное различие заключается в предположениях, сделанных в централизованных методах. Это предположение основано на том, что p-циклы всегда гарантированно защищают 100% работоспособности. Другими словами, предполагается, что всегда можно создать p-циклы, способные полностью защитить работоспособность. Распределенный метод занимается логической конфигурацией и назначением уже имеющихся физических мощностей. это означает, что распределенный метод нацелен на реальные операции, где физические связи фиксированы, но можно провести логическое различие в том, как можно использовать и/или определять резервную и рабочую мощность. Этот метод не всегда позволяет защитить 100% рабочих мощностей, поскольку резервной мощности может не хватить для создания необходимых p-циклов для защиты всех рабочих каналов сети. Распределенный метод можно реализовать одним из двух способов:

Предварительная конфигурация распределенного цикла

Этот метод основан на правилах и концепциях, заимствованных из протокола Selfhealing Network. Идея (DCPC) заключается в следующем: каждому запасному каналу соответствует связанное с ним состояние, называемое состояниелетом , с несколькими состояниями. Узел видит каждое логическое соединение с входящим и исходящим состоянием. Входящее состояние от ссылки на узел исходит от соседнего узла, который соединен этой ссылкой. Кроме того, каждое исходящее состояние канала имеет входящее состояние, которое образует его предшественник. На основе этой идеи некоторое количество состояний рассылается по сети (широковещательно) и формирует дерево состояний. «Каждый узел в дереве имеет корни в порте-предшественнике, из которого распространяются исходящие состояния». Это называется государственным маршрутом. В алгоритме есть два варианта узлов, а именно Cycler и Tandem , каждый из которых имеет свою конкретную роль. Cycler . — это роль отправителя/выборщика. В этом режиме Cycler отправляет и получает части состояния, которое он инициировал Все узлы принимают такое поведение, и это достигается по циклической схеме. Другая роль – это «Тандем» , который выступает посредником в конкуренции государственных вещателей с использованием новых правил и критериев, которых нет в сетях самовосстановления. Проще говоря, каждому узлу разрешено исследовать сеть и обнаруживать возможные p-циклы. Роль Tandem также определяет разрешенное обнаружение p-циклов типом узла Cycler . На основе DCPC p-циклы самоорганизуются в резервной мощности сети и находятся распределенным образом. Алгоритм можно запускать повторно каждый раз при изменении сети, чтобы обеспечить оптимальное использование резервной мощности. Для получения дополнительной информации читателю рекомендуется прочитать [9].

Система роевого интеллекта

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

Эффективность p-циклов

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

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

$1/({\bar {d}}-1)$

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

Приложения

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

• ИП
• ВДМ
• АСТН
• АСОН
• СДХ
• МПЛС
• СОНЕТ
• Защита сегмента
• Оптические Mesh-сети
• Оптический многоадресный медиа-трафик