7.5.10 Маршрутизация запасных соединений

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

Восстановление (Restoration) разрушенного маршрута может производится двумя способами:

— на основе выбора запасного (backup или rerouted) маршрута в момент установки соединения (pre-planned restoration / protection);

— на основе выбора запасного маршрута непосредственно после отказа (on-demand restoration).

В аспекте этих вопросов возникают три типа проблем:

— учет в процессе выбора основного маршрута потенциальной эффективности его восстановления в момент выхода из строя (в аспекте таких критериев, как «время восстановления», «вероятность получения отказа при восстановлении» и т.д.);

— учет в процессе выбора основного маршрута потенциальной эффективности непосредственно запасного маршрута;

— разработка специфических алгоритмов выбора запасных маршрутов.

Последние два требования относятся, понятно, только к первому способу восстановления.

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

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

— во-вторых, моделирование процесса восстановления производится совсем на другом временном уровне (микросек-миллисек) по сравнению с моделированием алгоритмов маршрутизации (минуты-часы).

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

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

— средний разброс в количестве соединений, проходящих по различным линиям (среднее количество этих соединений определяется лишь средней длиной маршрута); очевидно, что чем меньше этот разброс, тем меньше и разброс в времени доставки сообщения с места отказа в источник маршрута.

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

Рассмотрим теперь оставшиеся две проблемы, относящиеся исключительно к алгоритмам предварительной маршрутизации (preplanned) запасных маршрутов. Первую из них проиллюстрируем на примере алгоритмов «1+1 protection», подразумевающих выбор запасного маршрута без всякого разделения ресурсов с другими маршрутами, т.е. в режиме «горячего резерва» (1:1 и 1:N Protection предполагает функционирование запасных маршрутов в режиме холодного резерва). Простейшим решением является последовательный выбор - сначала определяем основной маршрут, а потом для того же соединения - запасной маршрут, не разрешая использовать для него узлы, входящие в основной маршрут (за исключением, конечно, источника и адресата). Недостаток такого подхода очевиден - мы можем выбрать наилучший (по критерию суммы текущих стоимостей линий) основной маршрут, но тем самым заблокировать выбор многих возможных (или даже всех) запасных маршрутов, что в итоге приведет к достаточно неудачному выбору этих двух маршрутов в совокупности. На основе алгоритмов Беллмана-Форда или Дийкстра можно предложить несколько подходов к одновременному построению основного и запасного маршрутов (подробный анализ различных подходов к построению раздельных путей содержится, например, в [272]). Основная идея состоит в том, что на каждом шаге алгоритма имеется не одно (как в стандартных алгоритмов кратчайшего пути) множество ближайших узлов к источнику, а два непересекаю-щихся, по каждому из этих множеств ищутся ближайшие к ним узлы, не входящие в оба из них, и далее по одному из этих узлов присоединяются к ранее образованным множествам.

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

Protection-алгоритмы (см. [178]), как »1+1» так и «1:N», производят и поиск запасного маршрута, и установку запасного соединения (включая работу алгоритма САС в каждом из узлов выбранного маршрута) практически одновременно с выбором и установкой основного маршрута-соединения, т.е. задолго до возникновения возможного отказа. Такой подход обеспечивает высокие значения показателей эффективности сети в аспекте восстановления разрушенных соединений, но резко снижает эффективность использования ресурсов сети. С другой стороны, алгоритмы «on-demand restoration» [135,136] производят и поиск запасного маршрута, и установку запасного соединения только после возникновения отказа, что приводит к низкой эффективности сети в аспекте восстановления. Промежуточным вариантом являются алгоритмы «pre-planned restoration» [234,250,301], обеспечивающие выбор запасных маршрутов и предварительное резервирование необходимых ресурсов сети в момент установки основного соединения, но непосредственно установка запасного соединения и фактическое выделение ресурсов под него (работа алгоритма САС) производится только после возникновения отказа и разрушения основного соединения.

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

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

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

• MaxSp (Maximum Spare Bandwidth) - максимальная пропускная способность, выделенная всем запасным соединениям, планируемым к установке по данной линии в случае выхода из строя некоторых основных маршрутов.

Отметим, что в отличие от параметров линий MCR и AvCR, относящихся к каждой отдельной категории обслуживания, параметр MaxSp относится ко всем категориям обслуживания сразу. Жесткое разделение значений параметров по категориям обслуживания существенно снижает эффективность использования ресурсов сети, но в случае основных соединений оно обусловлено спецификой работы алгоритма САС, призванного обеспечить при установке соединения выполнение требований по QoS параметрам. В случае маршрутизации запасных соединений непосредственно установка соединений не производится (ресурсы только предварительно резервируются с высокой степенью совмещения между отдельными запасными соединениями), в связи с чем жесткое разделение ресурсов нецелесообразно.

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

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

Подчеркнем еще раз, что установка и, соответственно, работа алгоритма САС, запасного соединения производится только после разрушения основного маршрута. В связи с этим используемые в неравенстве значения EBW являются не итогом выполнения алгоритма САС (как в случае маршрутизации основных соединений при вычислении значения AvCR), а лишь результатом предварительного анализа типа алгоритма GCAC. В случае централизованной маршрутизации для определения значений EBW целесообразно применять комбинированный подход, используя как результаты приближенных прямых вычислений эквивалентной пропускной способности в зависимости от параметров соединения и линии (см., например, формулы в [180,217]), так и статистику в части фактических значений EBW по основным соединениям (результаты работы САС), ранее установленных по данной линии. Очевидно, что маршрутизация запасных соединений, выполняемая в рамках выделенной пропускной способности не должна оказывать никакого влияния на значения параметров линии MCR, AvCR и в целом на маршрутизацию основных соединений. С другой стороны, при выборе запасных маршрутов целесообразно учитывать текущее состояние в части основных маршрутов по отдельным категориям обслуживания. Таким образом, следует произвести следующую модификацию алгоритмов маршрутизации применительно к запасным соединениям:

• В части GCAC: для поступившей заявки производится вычисление эквивалентной пропускной способности запасного соединения - - для каждой из возможных линий j, исходя из параметров соединения и линии, а также статистики ранее установленных по этой линии соединений данной категории обслуживания; для каждой линии проверяется неравенство (7.57) для всех узлов i, входящих в основной маршрут данного соединения, с учетом вновь вычисленного значения .

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

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