Методы расчета надежности и оптимизации загрузки кольцевых SDH-сетей

Шполянский

Источник: http://www.infocosmo.ru/content/statji/2004-3/wpolanski.pdf

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

Вопросы оптимизации надёжности SDH сетей


Преимущества кольцевой топологии

Для оптимизации затрат на создание SDH-сетей, обеспечивающих высокий коэффициент готовности, необходимо использовать разнесение трасс. Разнесение трасс может быть достигнуто без использования большого количества дополнительных связей. Во многих случаях введение всего одного дополнительного звена позволяет значительно повысить сетевую надежность. Так, если минимальная связность сети из n узлов обеспечивается n1 звеном, то, соединив эти узлы в кольцо, мы задействуем всего одно дополнительное звено. При этом с точки зрения надежности вклад будет весьма существенным, так как между любой парой узлов в кольце будет существовать, по крайней мере, два непересекающихся пути.
Математические выражения, позволяющие определить диаметр кольца, обеспечивающий требуемый общесетевой коэффициент готовности.
Если перед разработчиком ставится задача оптимизации размеров сети при заданных показателях надежности, весьма актуально иметь математические выражения, позволяющие быстро определить требуемые величины.
Учитывая тот факт, что в случае оптических сетей (SONET/SDH) любая 2х связная структура может рассматриваться как состоящая из колец, произведем анализ только кольцевых сетей.
Пусть все звенья сети имеют коэффициент готовности ,тогда получим выражение для двухточечной надежности одного кольца:

где: - двухточечная надежность одного кольца, n - количество узлов в кольце.
Выразим n из полученного уравнения:

Используя аппроксимацию, можно получить приближенное выражение для расчета n:

Пример:пусть = 99,5 % , необходимо определить: при каком количестве звеньев может быть достигнута двухточечная надежность одного кольца = 99,99 %. Подставив параметры в расчетную формулу, получаем: n = 4.
Данное выражение можно использовать для определения размеров сети, у которой все узлы соединены в одно кольцо, и ставится задача обеспечить требуемую надежность сети при заданных коэффициентах готовности звеньев.
Определим теперь двухточечную надежность крупной сети, состоящей из нескольких колец. В случае последовательной кольцевой структуры (сцепка колец) получим:

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

Теперь получим выражение для определения числа узлов в каждом кольце составной кольцевой сети:


Пример составной сети приведен на рис. 1.
Оценка надёжности существующей сети
Не менее актуальным является вопрос оценки надежности уже существующей сети. Если повышаются требования к отказоустойчивости рассматриваемой структуры, не исключено, что потребуется вводить дополнительные резервные маршруты (для чего, естественно, должна выделяться дополнительная резервная емкость).
Предполагая, что во всех звеньях определим двухточечную надежность между двумя наиболее удаленными точками A и B. С точки зрения двухточечной надежности между выбранными узлами данная сеть эквивалентна сети, приведенной на рис. 2.
В эквивалентной структуре цифры над сегментами обозначают коэффициенты неготовности эквивалентных звеньев. Произведем анализ, рассматривая два случая:


1 – звено CD в работе (вероятность данного события 0,995);
2 – звено CD не работает (вероятность данного события 0,005).
Выражение для определения 2х точечной надежности примет вид:

где x и y – коэффициенты готовности для случаев 2 и 1 соответственно. Далее, используя параллельно– последовательный метод упрощения, нетрудно получить величины x и y. В результате имеем:

Проблема загрузки колец

В крупной сети SDH пропускная способность колец может быть разной (в зависимости от распределения трафика между узлами), но в пределах одного кольца она одинакова для каждого звена. Очевидно, что стоимость кольца является возрастающей функцией от его емкости. При этом на стоимость оказывают влияние не оптические волокна, имеющие огромную полосу пропускания, а мультиплексоры ввода/вывода, имеющие градацию скоростей передачи в соответствии со стандартами SDH. Поэтому для каждого кольца существует такая предельная емкость C, что ни одно из его звеньев не может пропустить больше, чем C единиц трафика.
Кольцевые SDH структуры
Возможности мультиплексоров ввода–вывода (МВВ) позволяют организовывать кольцевые самозалечивающиеся сети. Существуют два варианта их построения: однонаправленное и двунаправленное кольцо [1].
В однонаправленных кольцевых структурах весь трафик передается в одном направлении (до момента возникновения отказа), рис. 3. Пропускная способность однонаправленных колец выбирается таким образом, чтобы обеспечить передачу всех требований «точка–точка» между узлами и, следовательно, равна их сумме.
В двунаправленных кольцах маршрутизация запросов производится независимо для каждой пары узлов и весь трафик между этими узлами (в обоих направлениях) передается по выбранному маршруту, рис. 4.
Очевидно, что двунаправленные кольцевые структуры являются более экономичными с точки зрения требуемой пропускной способности. Например, в случае равномерного распределения трафика между узлами двунаправленное кольцо может пропустить нагрузку в четыре раза большую, чем однонаправленное кольцо при одинаковой пропускной способности [2]. Учитывая указанное преимущество двунаправленных колец, которые за счет своей структуры позволяют производить оптимизацию пропускной способности, последующее изложение будет посвящено только им.
Постановка задачи
Для заданного двунаправленного кольца C, проходящего через множество M из m узлов, где между каждой парой узлов существует требование d >= 0 единиц, проблема загрузки формулируется следующим образом [3]:

с учетом ограничений:

где:

D – общее количество требований.
Выражение (1) совместно с условием целостности (3) определяет маршрутизацию требований:
i соответствует передаче в направлении по часовой стрелке, а j – против часовой стрелки.
Выражение (2) ограничивает оптимальную емкость кольца z, которая должна быть не меньше чем загрузка любого звена в кольце. Так для звена (l, l+1) загрузка равна сумме всех dk между узлами i и j для требований, передаваемых в направлении по часовой стрелке и против часовой стрелки. При этом для требований, передаваемых по часовой стрелке:

Другими словами, в данной задаче необходимо найти такой план маршрутизации требований (), чтобы минимизировать общий максимальный трафик на звене, называемый загрузкой кольца.
Как известно из литературы [2, 4, 5], проблема загрузки кольца, математически сформулированная выше, с учетом ограничений (3) относится к классу задач с нелинейной полиномиальной оценкой. Приведение выражения (3) к виду значительно упрощает решение (ослабление ограничений линейной программы). Такое предложение эквивалентно случаю разбиения требования по двум направлениям в кольце.

Литература

  1. Soriano P. at al. Design and dimensioning of survivable SDH/SONET networks // Chapter 9 in Telecommunications Network Planning. – Kluwer Academic Publishers, Netherlands, 1998.
  2. Schrijver A., Seymour P. and Winkler P. The Ring Loading Problem. – in SIAM J. Discrete Math, 1998.
  3. Cosares S. et al. SONET Toolkit: A Decision Support System for Designing Robust and Cost$Effective Fiber–Optic Networks // Interfaces. – Vol. 25. – ? 1. – 1995.
  4. Karp R. M. Reducibility among combinatorial problems / in R. E. Miller and J. W. Thatcher editors // Numerical Solution of Markov Chains: Plenum Press. – New York, 1972.
  5. Shah Rahul. Optimization Problems in SONET/WDM Ring Architecture // Master’s essay under Vasek Chvatal. – 1998.