РАЗДЕЛ 2. МЕТОД СТРУКТУРНЫЙ СИНТЕЗ СЕТЕЙ С ТЕХНОЛОГИЕЙ MPLS
2.1 Введение
Одной из важных задач, которые стоят перед проектировщиками сетей с технологией
MPLS есть задача структурного, или топологического синтеза сети, под заданную
входную нагрузку, в результате которой определяется общая структура сети, типы
каналов связи, их пропускные способности, распределение потоков при
ограничениях на заданный уровень QоS для потоков разных классов обслуживания
(Class of Service) по критерию стоимости. При этом как дополнительные
ограничения могут выступать показатели надежности и живучести сети.
В рамках решения задачи построения сети, кроме задачи выбора топологии, стоит
задача выбора оптимальных пропускных способностей будущей сети при априори
неизвестных, то есть нераспределенных потоках, базируясь лишь на требованиях к
объему данных, которые должны передаваться между узлами сети. Решение этой
задачи является необходимым для оценки стоимости построенной структуры,
следовательно, и для выбора оптимальной.
Ранее задачи структурного синтеза сети с перспективными технологиями
рассматривались для сетей с технологией ATM (Asynchronous Transfer Mode) и был
разработан и исследован достаточно эффективный алгоритм оптимизации
структурного синтеза, который учитывает специфику технологии ATM в частности
наличие нескольких категорий сервиса CBR, VBR и ABR [29,37].
Целью этого раздела является постановка и формализация задачи синтеза структуры
сетей с технологией MPLS и разработка соответствующего метода ее решения.
2.2 Математическая модель задачи структурного синтеза сетей
Задано множество узлов сети - маршрутизаторов MPLS (так называемых LRS – Label
Switching Routers), их размещение по территории региона, набор пропускных
способностей каналов связи из которых ведется синтез их удельных стоимостей на
длины , определены классы обслуживания CoS (Class of Service), известны матрицы
входящих требований для k-го класса ; , где – интенсивность k-го класса,
который необходимо передавать из узла i в узел j за единицу времени (Кбит/с).
Кроме того, введены ограничения на показатели качества QoS для каждого класса k
в виде ограничения на среднюю задержку ,
Требуется найти структуру сети в виде набора каналов связи (КС) , выбрать
пропускные способности (ПС) каналов связи и найти распределение потоков всех
классов , таким образом, чтобы обеспечить передачу требований всех классов в
полном объеме и с задержками , не превышающими заданные ,к и при этом бы
выполнялись ограничения на долю потерянных пакетов CLPk , а стоимость сети была
бы минимальной [56,57].
Составим математическую модель данной задачи синтеза.
Требуется найти такую структуру сети E, дла которой:
(2.1)
при условиях
(2.2)
для всех (2.3)
(2.4)
(2.5)
где - доля потерянных пакетов для потока к –го класса (приоритета), - заданное
ограничение на эту величину.
В работе [46 ] для потока k-го класса, при условии что обслуживание в классах
происходит с относительными приоритетами в порядке убывания номера класса (т.е.
) при заданном наборе ПС каналов и распределении потоков (РП) – было получено
(в работах Ю.П.Зайченко, Ахмед А.М. Шарадка [46,47]) следующее выражение для
средней задержки :
(2.6)
при условии, что
где - величина потока класса в КС ().
В работах [28,29] получено следующее выражение для величины доли потерянных
пакетов в каналах ():
(2.7)
где (2.8) - нормирующий множитель.
- число цифровых каналов базовой пропускной способности (1.544 Mбит/с) в линии
связи (); - размер буфера коммутатора MPLS, выделенного для потока к-го
класса.
Тогда вероятность отсутствия потерь пакетов в сети из Е - каналов равна , а
средняя вероятность, (доля) потерянных пакетов К-го класса в целом по сети
равна (2.9)
Данная задача синтеза структуры относится к классу комбинаторных задач
дискретного программирования и является NP - полной задачей. По этому для ее
решения предлагается генетический метод структурного синтеза.
2.3 Описание метода структурного синтеза
Дадим описание метода структурного синтеза сетей с технологией MPLS.
Метод состоит из двух этапов: предварительного и основного.
Цель предварительного этапа: синтезировать начальную структуру сети,
удовлетворяющую условиям заданной связности.
На основном этапе состоящем из однотипных итерации осуществляем оптимизацию
структуры текущей сети по стоимости при ограничениях на заданные значения
показателей качества QoS.
На предварительном этапе сначала строим кратчайшего связывающее дерево из
исходных узлов, а затем дополняем его до заданной связности 2.
Предварительный этап.
Синтез кратчайшего связывающего дерево (КСД) [121].
1. Находим суммарный объем информации в каждом узле .
2. Определяем корень дерева , как узел из условия . Для удобства изложения
алгоритма допустим, что .
3. Пусть стоимость канала связи между и , где - расстояние между и , а
пропускные способности КС ограничены величиной . Нужно найти такую структуру
сети в классе деревовидных структур с корнем в пункте , которая бы обеспечила
передачу заданного объема информации от всех узлов к при ограничении на ПС КС ,
и стоимость которой была бы минимальной.
- а итерация
Пусть уже проведено итераций, в результате которых построено изолированы
подграфы и есть корневой сегмент .
1. Выбираем произвольный изолированный подграф .
2. Выбираем некоторый соседний к нему подграф (изолированный) .
3. Проверяем возможность их объединения: . Если да, то на шаг 4, иначе выбор
другого .
4. Вычисляем экономию от введения КС : .
5. Ищем такую пару , для которой . Если , то вводим КС и объ
- Киев+380960830922