автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Методы анализа вероятностных характеристик модели разделения ресурсов мультисервисной телекоммуникационной сети

904613383 На правах рукописи

Лузгачев Михаил Васильевич

Методы анализа вероятностных характеристик модели разделения ресурсов мультисервисной телекоммуникационной сети

05.13.17 - теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

1 8 НОЯ 2010

Москва - 2010

004613383

Работа выполнена на кафедре систем телекоммуникаций Российского университета дружбы народов

Научный руководитель доктор технических наук, профессор

Самуйлов Константин Евгеньевич

Официальные оппоненты доктор технических наук, профессор

Степанов Сергей Николаевич

кандидат физико-математических наук Павлова Наталья Геннадьевна

Ведущая организация Институт проблем информатики

Российской академии наук (ИЛИ РАН)

Защита диссертации состоится 26 ноября 2010 г. в 15 час. 30 мин. на заседании диссертационного совета Д 212.203.28 при Российском университете дружбы народов по адресу: г. Москва, ул. Орджоникидзе, д. 3, ауд. 110.

С диссертацией можно ознакомиться в Научной библиотеке Российского университета дружбы народов по адресу: 117198, г. Москва, ул. Миклухо-Маклая, д. 6. (Отзывы на автореферат просьба направлять по указанному адресу.)

Автореферат разослан « Я-Ь» октября 2010 г.

Ученый секретарь диссертационного совета

Д Г.м^7

М.Б. Фомин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

Современное состояние телекоммуникаций характеризуется предоставлением множества различных услуг на базе единой сетевой инфраструктуры. Например, по единому широкополосному каналу пользователю могут одновременно предоставляться услуги передачи данных (Интернет), телефонии и вещательного телевидения. Этим услугам в мультисервисных телекоммуникационных сетях соответствуют различные типы трафика: потоковый одноадресный трафик (англ., unicast), потоковый многоадресный трафик (англ., multicast), эластичный трафик (англ., elastic). Для анализа характеристик обслуживания трафика, таких как вероятность блокировки, интенсивность обслуженной нагрузки, среднее время передачи и др., применяются модели мультисервисных сетей с потерями. При построении и анализе таких моделей используется аппарат теории вероятностей, теории массового обслуживания и теории телетрафика. К российским ученым, внесшим большой вклад в этих областях, относятся Г.П. Башарин, В.М. Вишневский, A.B. Печинкин, А.П. Пшеничников, К.Е. Самуйлов, Б.А. Севастьянов,

С.Н. Степанов, А.Д. Харкевич, С.А. Шоргин, Г.Г. Яновский и др., а к зарубежным - Й. Виртамо, В. Иверсен, Дж. Кауфман, Ф. Келли, JI. Клейнрок, Дж. Роберте, К. Росс и др.

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

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

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

Методы исследования. В работе использованы методы теории вероятностей, теории случайных процессов, теории массового обслуживания, теории телетрафика, математического программирования.

Научная новизна и результаты, выносимые на защиту, состоят в следующем:

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

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

- построена модель и разработан метод анализа величины чувствительности дохода к изменению пропускной способности VPN с одноадресными и многоадресными соединениями;

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

Практическая ценность работы. Приближенные методы и алгоритмы, полученные в диссертации, предназначены для расчета характеристик показателей эффективности мультисервисных сетей с одноадресными и многоадресными соединениями и могут быть применены проектными организациями и операторами сетей для планирования виртуальных частных сетей. Результаты диссертации использованы в исследованиях по гранту РФФИ №10-07-00487-а «Задача управления доступом в широкополосной сети и анализ марковской модели с мультипликативным распределением вероятностей состояний», а также в учебном процессе на кафедре систем телекоммуникаций РУДН для студентов, обучающихся по направлению «Прикладная математика и информатика», в выпускных работах бакалавров и магистерских диссертациях.

Апробация работы. Основные результаты, изложенные в диссертации, докладывались на:

- XLV и XLVI Всероссийской конференции по проблемам математики, информатики, физики и химии РУДН (Москва, 2009 и 2010);

- LXIV научной сессии, посвященной дню радио Российского научно-технического общества радиотехники, электроники и связи им. А.С.Попова (Москва, 2009);

- Международных конференциях «International Conference on Ultra Modern Telecommunications» (Санкт-Петербург, 2009; Москва, 2010);

- VI Отраслевой научной конференции-форуме «Технологии информационного общества» (Москва, 2010);

- Научном межвузовском семинаре «Современные телекоммуникации и математическая теория телетрафика» (РУД11, МГУСИ, ОАО «Интеллект Телеком»; Москва, 2010). Публикации. По теме диссертации опубликовано 6 работ, из них

2 - в ведущих рецензируемых научных журналах, 4 - в трудах всероссийских и международных конференций.

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

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и библиографии из 102 наименований. Диссертация содержит 124 страницы текста, 23 рисунка и 23 таблицы.

СОДЕРЖАНИЕ РАБОТЫ

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

Глава 1 посвящена исследованию проблем эффективного разделения ресурсов мультисервисных телекоммуникационных

сетей, в том числе задач планирования VPN. В разделе 1.1 исследована многокритериальная задача маршрутизации трафика на графе сети MPLS (Multiprotocol Label Switching), которую необходимо решать при анализе вероятностных характеристик модели мультисервисной сети, в том числе при маршрутизации в VPN. Раздел 1.2 посвящен краткому обзору используемых в работе методов расчета вероятностных характеристик - вероятностей блокировок соединений и среднего времени передачи эластичного трафика. В разделе 1.3 представлена задача маршрутизации и разделения ресурсов мультисервисной сети между VPN с одноадресными соединениями. Дан краткий анализ метода решения задачи нелинейного программирования с ограничениями типа лилейных равенств, метода возможных направлений Зойтендейка, а также метода отсечений в целочисленном линейном программировании. Для случая с одноадресными соединениями рассмотрено понятие упущенной выгоды, на котором осповап метод анализа величины чувствительности дохода к пропускной способности VPN.

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

В разделе 2.1 разработана модель разделения пропускной способности отдельного звена сети между виртуальными частными сетями. Рассмотрим мультисервисную сеть с множеством звеньев

й' = {1.....L]. В сети построены VPN„ из множества .•f" = {l,...,jV + l}.

Звено I сети имеет пропускную способность с' е Z+, при этом VPN„ использует 0 < С'„ й С' условных единиц канального ресурса (ЕКР).

В VPNi,...,VPNw устанавливаются одноадресные соединения различных классов из множества X, причем соединение к -класса требует dk ЕКР на каждом звене соответствующего маршрута из

множества . Считаем заданной величину ак предложенной нагрузки на соединение ¿-класса, и пусть Е11к - интенсивность поступления дохода от к -соединения (ед. дохода/ед. времени). Заметим, что соединение устанавливается, если во время поступления запроса пользователя на каждом звене маршрута 9!к имеется <1к ЕКР, иначе соединение блокируется. Обозначим С,=(С',...,Свектор пропускных способностей УРН, на звеньях сети и Жп с Л множество соединений УРН- Если вероятность блокировки соединения кеЖп равна Вк(Сп), то интенсивность поступления дохода от \ФЫ„ вычисляется по формуле

Рассмотрим теперь в которой на базе многоадресных

соединений предоставляются услуги мультивещания из множества Л(={1 ,...,М}, причем для предоставления т-услуги требуется Ьт ЕКР. Считаем, что в сети имеется один источник услуг мультивещания. Пусть р - путь (маршрут) от источника к группе пользователей, и пусть У - множество всех путей (дерево мультивещания), г£рс,'1- звенья пути. Пару (т, р) будем называть логическим путем, и считаем, что по каждому пути ре¡У устанавливаются соединения всех услуг из множества М. Обозначим р предложенную нагрузку на (/л, р)-путь, ЕМт -интенсивность поступления дохода от т -услуги. Считаем заданными дерево г? и значения нагрузок ртр, те Ж, ре ¡Р. Запрос на установление многоадресного соединения блокируется, если услуга еще не предоставляется, и на соответствующем пути не хватает пропускной способности для ее предоставления. Обозначим

(1)

П„,ДСЛЧ1) вероятность блокировки (т,р)-пути, и тогда интенсивность ЕЛ,+1 (Cw+1) поступления дохода от VPNW+1 имеет вид

S EMmY,P„,P(l-nJCNJ), (2)

I) »6. Л рсУ

а общая интенсивность дохода от всех VPN вычисляется по формуле £(С)=ХЕ„(Сп). (ЗУ

пе.1

Введем обозначения для отдельного I -звена сети: пусть а[ -интенсивность предложенной нагрузки А:-соединений; р'т -интенсивность предложенной нагрузки т -услуги; Jini - множество соединений VPN,,; В[(С[} - вероятность блокировки соединений к-класса в VPN„; ПЦс^+1) - вероятность блокировки т -услуги в VPN/y+i; - интенсивность дохода от соединений через /-

звено. Далее исследуется задача разделения ресурсов отдельного /'звена сети (т.е. предполагается, что С' <°°, и С'=°°, если /£Й?\{Г}), которая состоит в поиске вектора С' ,...,C'NHj,

максимизирующего суммарный доход El (С j = ^ ^ EUka't х

x(l-<(cf)) + от всех VPN сети:

max Е''(сг), (4)

5Х=С'',С''6(Ги{0})"+1. (5)

Задача (4)-(5) является задачей целочисленного нелинейного программирования с ограничениями типа линейных равенств. Особенность состоит в том, что целевая функция определена только для целочисленного аргумента, а при вычислении вероятностей блокировок, от которых она зависит, применяются точные

рекуррентные алгоритмы Кауфмана-Робертса (одноадресные соединения) и Гайдамака-Самуйлова (многоадресные соединения).

В разделе 2.2 разработан метод решения задачи (4)—(5), на каждой итерации Cj.fl) = С^ + <5j'fl) которого необходимо найти

вектор <5j'i+1j е ZN+I изменения пропускных способностей VPN„ на /* -

звене. Для решения этой задачи применяется модифицированный метод возможных направлений Зойтендейка в предположении дифференцируемости функций В[ (■) и П^(-) в точках С[ , при этом

значения

dc'

dC'

определяются с помощью конечно-

разностной аппроксимации. Предлагаемый метод позволяет найти локальный максимум целевой функции задачи.

Утверждение 1. Вектор 6' е изменения пропускных способностей является решением задачи целочисленного линейного программирования

«Г ж=.|ЯСц

2Х=0,

K.t

Si^tf ¿Ж,пел,

(6)

(7)

(8)

где Sn =

ё'„ =

min С

Г1' -С:',max^Jcf))

ф - заданная константа.

В разделе 2.2 также разработан пример численного анализа, в котором иллюстрируется решение задачи и оценивается точность приближенного метода, относительная погрешность которого в рассматриваемом диапазоне значений параметров сети не превосходит 1%.

В разделе 2.3 исследуется модель разделения пропускной способности отдельного звена сети между VPN, по которому передается эластичный трафик, когда блоки данных получают максимальную на момент передачи пропускную способность, т.е. обслуживаются по принципу «best effort». В рассматриваемой модели блокировки отсутствуют, а вероятностной характеристикой, которая подлежит оптимизации, является среднее время передачи блока данных, т.е. решается задача минимизации суммы средних времен передачи

nun£5X(C„), (9)

пел ке.К

£с„=С,Се(Ги{0})", (10)

пеЛ

где среднее время передачи блока данных длиной вк по VPN„ определяется по формуле

(Ц)

/ V «г л )

Утверждение 2. Решение задачи (9)-(Ю) имеет вид

( \ 1 с[ = C + N^XJ-YLW А' (12)

\ *еЛ jej ieX Jj

В диссертации показано, что решение (12) является также решением задачи минимизации максимального времени передачи, т.е. когда целевая функция имеет вид шах т^ (С„).

тл, kzJt

Глава 3 посвящена разработке методов анализа вероятностных характеристик модели разделения ресурсов мультисервисной телекоммуникационной сети. В разделе 3.1 получены результаты, необходимые для вычисления упущенных выгод и чувствительностей дохода к изменению пропускных способностей VPN - величин, используемых при решении задачи разделения пропускной способности сети.

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

Введем обозначения, используемые в методах расчета упущенных выгод и чувствительностей дохода: а'к(С„) -предложенная нагрузка А:-соединений на /-звено, р'тр(Cw+,) -предложенная нагрузка т-услуги по р-пути на /-звено, -

упущенная выгода от установления к -соединения на /-звене в VPN„, п е .А', <П(СЛЧ1) - упущенная выгода от установления соединения т -услуги на / -звене в VPNW+1.

Утверждение 3. Величины упущенных выгод (С„) от одноадресных соединений VPN„, пе Л'\{/У + 1}, являются решением системы линейных уравнений

iejr.fc*

EU,- I #(0

■МЧ'}

(13)

,кеХж,1

Л

а величины упущенных выгод ¿¡'т (СЛ/+]) от многоадресных соединений \ФМЛ>+1 являются решением системы линейных уравнений

1 + Рт\У1ы)*-Л

X Z ЕМ - £ <Г/(С„+|)

V **гЧ!)

psflzSt,

,те.И,1& У,

(14)

J J

где е1 -(0.....0,1,0,...,0), р\=

реУ

Далее вводится понятие чувствительности дохода Э Еп Э Е„(С„)

—j:=— ; к изменению пропускной способности, которая ЭС„ оС„

показывает, как меняется интенсивность дохода от VPN„ при увеличении ее пропускной способности на / -звене.

Утверждение 4. Величины чувствительностей интенсивностей дохода от VPN к изменению пропускных способностей звеньев сети вычисляются по формулам де- дя' (

S = - I I i/(C„) + (15)

I p'JcJem^ X ^(c,+l)]. (i6)

В разделе 3.2 сформулирована следующая задача разделения ресурсов сети между VPN с одноадресными и многоадресными соединениями:

тахЕ(С), (17)

£ Ci= С', Iе С = (С„...,С„+|)£ (Z+u{0})i("+1'. (18)

m.t

Для решения задачи (17)—(18) в диссертационной работе разработаны приближенный метод и вычислительный алгоритм. Эта задача является задачей целочисленного нелинейного программирования с ограничениями типа линейных равенств, причем для вычисления значений целевой функции требуется применение разработанного в работах Ф. Келли, К. Росса и К.Е. Самуйлова приближенного метода просеянной нагрузки. Как и в задаче (4)-(5), на каждой итерации С^ = С^ + требуется

найти вектор <5jw) изменения пропускных способностей VPN на всех

звеньях сети, dim^l+)) = (// + l)L. Проблема нахождения вектора

решается аналогично задаче (6)-(8) из утверждения 1, причем

на каждой итерации решаются системы уравнений (13), (14), и вычисляются по формулам (15) и (16) величины чувствительностей дохода.

Раздел 3.3 посвящен организации вычислительного эксперимента и анализу эффективности разделения ресурсов мультисервисной сети между VPN с одноадресными и многоадресными соединениями. Рассматривается базовая сеть (рис. 1), состоящая из 8 узлов и 20 звеньев Gigabit Ethernet, в узле 2 сети расположен источник услуг мультивещания. Ресурсы сети необходимо разделить между VPN„, пе Л ={1,...,5}, за ЕКР принята величина а = 64 кбит/с.

Требования двух одноадресных услуг, предоставляемых в VPNi,...,VPN4, к пропускной способности сети равны 64 и 128 кбит/с соответствешю, а трафик услуг передается в каждой VPN по заданному множеству маршрутов. В рассматриваемой конфигурации сети число классов одноадресных соединений |ji| = 1792, причем Х = |ji^| = |jlT2|; dk= 1, k&J(i\dl=2,keJl1.

Рис. 1. Структура сети с одноадресными и многоадресными соединениями

Источник мультивещания расположен в узле 2 сети и предоставляет М =50 услуг в УР^ по путям, показанным на рис. 1 пунктирной линией. Предполагается, что этим услугам

Пользователи Щ^У одноадресных соединений

Ш Источник услуг мультивещания

^ Дерево

мультивещания

Пользователи услуг мультивещания

Звено Gigabit Ethernet

соответствуют 50 каналов цифрового ТВ, 5 из которых являются популярными (р^=6б,б), а 45 - непопулярными (/7^=1,0).

Требования к пропускной способности для каждой из услуг равны 4 Мбит/с, т.е. Ът = 64 ЕКР, т е Л.

Начальное значение вектора С определено исходя из того, что для VPN5 на всех физических путях выделено ^ Ът ЕКР, т.е.

л|е.й

200 Мбит/с, чего достаточно для передачи трафика услуг ТВ без блокировок соединений. Оставшаяся пропускная способность сети равномерно разделена между VPNi,...,VPN4 с одноадресными соединениями.

На рис. 2 показан график изменения значений целевой функции дохода, полученный при решении задачи (17)—(18) методом, разработанным в диссертации. Максимальное значение £(С) = 166,56 условных единиц дохода достигается за 11 итераций. В таблице 1 приведен фрагмент значений вектора С пропускных способностей VPN на звеньях сети, соответствующего найденному решению задачи. Характеристики найденного решения показаны ниже в таблице 2. В таблице 3 приведены значения вероятностей блокировок соединений.

166,6 J -

Рис. 2. Значения целевой функции при поиске решения задачи (17Н18)

Таблица 1. Разделение пропускной способности сети между УРЫ

Звено сети С' С' ч С' 1 с' 2 | Ч> С' 4 с'5

(3;4) 9600 1686 1570 1596 1822 2926

(3;8) 9600 2142 2142 2646 2670 0

(4;3) 9600 2142 2142 2646 2670 0

(4;5) 9600 1466 1466 | 1686 1782 3200

(8;3) 9600 2142 2142 2646 2670 0

(8;7) 9600 1623 1712 1543 1822 2900

Таблица 2. Характеристики решения задачи (17)—(18)

Доля Интенсивность Интенсивность

УРК пропускной обслуженной поступления

способности нагрузки дохода

УРЫ, 20,393% 4871,88 43,85

УРЫ2 19,932% 4548,96 40,94

УРИз 23,674% 4146,12 37,32

УР^ 24,633% 4876,63 43,89

УРЫ5 11,368% 2629,89 0,56

Таблица 3. Вероятности блокировок соединений

УРЫ Услуга Среднее значение Максимальное значение

УРН, 1 2,02-10"" 2,74-10"8

2 4,23-10"" 5.73-10"8

УРИ2 1 2,70 -КГ" 7,13 -ИГ8

2 5,64- Ю-11 8,61-Ю"9

УРИ3 1 1,77-10"" 5,23-10"9

2 3.72-10"" 1.10-10"8

УРЫ4 1 1,98-10"'° 2.24- КГ4

2 4.10-10-'° 4.62-Ю"6

УРЫ5 1...5 6,32-Ю-7 1,47-ИГ*

6...50 4,04-10"3 9.43-ИГ5

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

3. Построена математическая модель для оценки эффективности разделения пропускной способности отдельного звена мультисервисной сети между VPN. В отличие от известных работ модель учитывает не только одноадресные, но и многоадресные соединения. Предложен приближенный метод решения задачи максимизации дохода от соединений, и показано, что в исследуемой в работе сети его относительная погрешность не превосходит 1%.

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

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

Основные публикации по теме диссертации:

1. Лузгачев М.В., Самуилов К.Е. Задача маршрутизации трафика на графе сети MPLS с одноадресными соединениями // Вестник РУДН. Серия «Математика. Информатика. Физика». - 2009. -№1.-С. 23-33.

2. Лузгачев М.В., Самушов К.Е. Метод решения задачи разделения ресурсов мультисервисной сети между виртуальными частными сетями с одноадресными и многоадресными соединениями // Вестник РУДН. Серия «Математика. Информатика. Физика». -2010. -№2(1). -С. 42-53.

3. Лузгачев MB. Методы решения задач разделения ресурсов мультисервисных сетей между VPN с потоковым или эластичным трафиком // XLVI Всероссийская конференция по проблемам математики, информатики, физики и химии: Тезисы докладов. Секции математики и информатики. - М.: РУДН, 2010.-С. 84-85.

4. Лузгачев М.В., Самуилов К.Е. Об одной задаче оптимизации ресурсов мультисервисной сети с одноадресными и многоадресными соединениями // Труды РНТОРЭС им. А.С. Попова. Серия: Научная сессия, посвященная Дню радио. -Вып. LXIV. - 2009. - С. 20-22.

5. Luzgachev М., Samouylov К. On the Resource Allocation Problem for a Multiservice Network Link with Unicast and Multicast Connections // Proc. of the IEEE International Conference on Ultra Modern Telecommunications ICUMT 2009. - St.-Petersburg, Russia: 2009.-Pp. 1-3.

6. Luzgachev M., Samouylov K. The Resource Allocation Problem in the Design of Virtual Private Networks with Unicast and Multicast Connections II Proc. Of the IEEE International Conference on Ultra Modern Telecommunications ICUMT 2010. - Moscow, Russia: 2010.-Pp. 1-6.

Лузгачев Михаил Васильевич (Россия) Методы анализа вероятностных характеристик модели разделения ресурсов мультисервисной телекоммуникационной сети

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

Mikhail Luzgachev (Russia) Methods for analyzing the probabilistic characteristics of the multiservice network resource allocation model

In this thesis we analyze a multicritera routing problem and the conditions of the efficient resource allocation for a stand-alone link of a multiservice network with elastic traffic. We introduce the resource allocation model for a stand-alone link with unicast and multicast connections and develop an approximate method to solve the revenue maximization problem. We also introduce an analytical model and a method to analyze revenue sensitivities. To solve the resource allocation problem for a multiservice network we develop an approximate method and an algorithm. The results are illustrated on a case study.

Подписано в печать: 19.10.2010

Заказ № 4338 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ra

СПИСОК ОСНОВНЫХ ОБ ОЗНАЧЕНИИ

ВВЕДЕНИЕ

ГЛАВА 1. Анализ задач разделения ресурсов мультисервисных сетей

1.1. Задачи планирования виртуальных частных сетей

1.2. Методы анализа вероятностно-временных характеристик мультисервисных сетей

1.3. Анализ задачи разделения ресурсов между виртуальными частными сетями с одноадресными соединениями

1.4. Постановка задачи исследований

ГЛАВА 2. Методы анализа моделей разделения ресурсов отдельного звена мультисервисной сети между виртуальными частными сетями

2.1. Построение модели мультисервисной сети с потоковым трафиком

2.2. Приближенный метод анализа модели отдельного звена сети с потоковым трафиком

2.3. Аналитическое решение задачи разделения ресурсов звена сети с эластичным трафиком

ГЛАВА 3. Анализ модели разделения ресурсов сети между виртуальными частными сетями

3.1. Вероятностные характеристики модели и методы их расчета

3.2. Приближенный метод решения задачи разделения ресурсов сети

3.3. Численный анализ вероятностных характеристик модели

Современное состояние телекоммуникаций характеризуется предоставлением множества различных услуг на базе единой сетевой инфраструктуры. Стремительно развиваются сети следующего поколения (Next Generation Network, NGN) [13,38], в том числе на основе реализации концепции IMS (IP1 Multimedia Subsystem) [39,101], а также сотовые сети третьего (3rd Generation, 3G) [16,101] и уже четвертого поколения (4rd Generation, 4G) [8], активно внедряются беспроводные технологии WiMAX (Worldwide Interoperability for Microwave Access) и LTE (Long Term Evolution) [8,37]. Такие сети характеризуются возможностью предоставлять множество услуг на базе широкополосного доступа (ШПД). Например, по единому широкополосному каналу пользователю могут одновременно предоставляться услуги передачи данных (Интернет), телефонии и вещательного телевидения, реализуя принцип «Triple Play» (тройная услуга) [4,33]. Этим услугам в мультисервисных телекоммуникационных сетях соответствуют различные типы трафика:

- потоковый одноадресный трафик (англ., unicast),

- потоковый многоадресный трафик (англ., multicast),

- эластичный трафик (англ., elastic).

Потоковый трафик характеризуется наличием требования к пропускной способности сети и непрерывной передачей информации. Одноадресные соединения [2,4,27,71,92] используются такими услугами как телефония или видео по запросу, и обладают особенностью - каждое новое соединение занимает пропускную способность сети. Многоадресные соединения устанавливаются при предоставлении услуг, использующих технологию мультивещания, таких как вещательное телевидение [4,27,59]. Их особенностью является то, что при предоставлении одной и той же услуги различным пользователям данные не дублируются, таким образом, осуществляется экономия ресурсов сети, что особенно важно, учитывая потенциальное число пользователей услуги цифрового ТВ.

1 Internet Protocol

Эластичный трафик обслуживается по принципу «best effort», что означает передачу данных с максимально возможной скоростью, которая, в свою очередь, определяется объемом одновременно передаваемых данных [40]. Трафик этого типа генерируется, например, при передаче сообщений электронной почты, пересылке файлов, просмотре web-страниц и др. Исследованию и анализу моделей одноадресных соединений посвящены работы [7,71,92], модели мультисервисных сетей с многоадресными соединениями исследуются в [4,27,59,93,94]. В работах [40,45,99] исследуются модели с эластичным трафиком.

Трафик перечисленных типов передается на базе единой сетевой инфраструктуры. Одним из решений для построения транспортного уровня мультисервисных сетей является технология многопротокольной коммутации по меткам (MPLS, Multiprotocol Label Switching) [12], которая обеспечивает коммутацию пакетов на магистральных каналах, позволяя осуществлять безопасную и эффективную передачу данных. Эта технология может использоваться для сокращения задержек передачи по сети и обеспечения управления маршрутизацией трафика, а также позволяет использовать заданную маршрутизацию, классификацию и приоритезацию трафика. Одним из существенных преимуществ MPLS является возможность применения инжиниринга трафика (Traffic Engineering, ТЕ) [41,88], предлагающего гибкие механизмы по управлению трафиком в сети и позволяющего избежать сложностей, возникающих, например, при использовании стандартных протоколов маршрутизации, таким образом, обеспечивая возможность повысить эффективность использования сетевых ресурсов.

Для анализа характеристик обслуживания трафика, таких как вероятность блокировки, интенсивность обслуженной нагрузки, среднее время передачи и др., применяются модели мультисервисных сетей с потерями. При построении и анализе таких моделей используется аппарат теории вероятностей и случайных процессов [34,72], теории массового обслуживания [3,7,11,43] и теории телетрафика [2,4,18,20,33,35,68,92]. К российским ученым, внесшим большой вклад в этих областях, относятся Т.П. Башарин, В.М. Вишневский, A.B. Печинкин, А.П. Пшеничников,

К.Е. Самуйлов, Б.А. Севастьянов, С.Н. Степанов, А.Д. Харкевич, С.А. Шоргин, Г.Г. Яновский и др., а к зарубежным - Й. Виртамо, В. Иверсен, Дж. Кауфман, Ф. Келли, JI. Клейнрок, Дж. Роберте, К. Росс и др.

В современных сетях одной из важнейших задач операторов является эффективное использование сетевых ресурсов. В связи с этим существует широкий класс задач оптимального планирования сетей [17,52,58,61,63, 64,65,74,91,96]. Множество публикуемых работ посвящено задачам маршрутизации [54,55,58,82,95,98], планированию ресурсов [46,57,76, 97,100]. Отдельно выделим исследования, связанные с планированием именно виртуальных частных сетей [44,49,53,62,65,66,67,73,77,87,89,90, 102]. Решение задач такого класса требует применения основополагающих результатов в области методов решения задач оптимизации [1,5,6], задач линейного [14,21,36,42,78], нелинейного [9,15,21,75] и целочисленного программирования [10], а также многокритериальных задач оптимизации [28,51,55] и др. Заметим, что многие известные алгоритмы математического программирования реализованы. Например, для решения широкого круга задач могут применяться такие средства, как система моделирования GAMS (The General Algebraic Modeling System) [60].

В современных телекоммуникациях востребованной услугой является виртуальная частная сеть (Virtual Private Network, VPN) - технология доступа, позволяющая сформировать защищенные каналы обмена информацией между локальными сетями или пользователями [8]. Одной из важнейших задач эффективного использования базовой телекоммуникационной сети является разделение пропускной способности ее звеньев между VPN с учетом неоднородности передаваемого трафика. В рассматриваемых в [29,84,85] постановках задач необходимо разделить ресурсы базовой сети (пропускные способности) между VPN с целью максимизации величины суммарной интенсивности поступления дохода, которая может уменьшаться при возникновении блокировок запросов на установление соединений из-за нехватки пропускной способности сети. При этом в сети передается трафик только одноадресных соединений. Доход здесь служит интерпретацией взвешенной величины обслуженной нагрузки соединений. Для решения задачи в [84] предложен приближенный метод, основанный на анализе чувствительности целевой функции (дохода) к изменению пропускных способностей VPN. При этом чувствительности рассчитываются с помощью упущенной выгоды - дохода, который не получит оператор вследствие дополнительных блокировок в будущем, вызванных установлением нового соединения. Понятие упущенной выгоды введено в работе [71] и подробно исследуется в [92]. Оно также используется при решении задач маршрутизации [48,81,83,86].

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

Работа имеет следующую структуру. Глава 1 посвящена исследованию проблем эффективного разделения ресурсов мультисервисных телекоммуникационных сетей, в том числе задач планирования VPN. В разделе 1.1 исследована многокритериальная задача маршрутизации трафика на графе сети MPLS, которую необходимо решать при анализе вероятностных характеристик модели мультисервисной сети, в том числе при маршрутизации в VPN. Раздел 1.2 посвящен краткому обзору используемых в работе методов расчета вероятностных характеристик - вероятностей блокировок соединений и среднего времени передачи эластичного трафика. В разделе 1.3 представлена задача маршрутизации и разделения ресурсов мультисервисной сети между VPN с одноадресными соединениями. Дан краткий анализ метода решения задачи нелинейного программирования с ограничениями типа линейных равенств, метода возможных направлений Зойтендейка, а также метода отсечений в целочисленном линейном программировании. Для случая с одноадресными соединениями рассмотрено понятие упущенной выгоды, на котором основан метод анализа величины чувствительности дохода к пропускной способности VPN. Раздел 1.1 написан на основе публикации с участием автора [24].

Глава 2 посвящена разработке методов анализа характеристик моделей разделения ресурсов отдельного звена мультисервисной сети как с потоковым, так и с эластичным трафиком. В разделе 2.1 разработана модель разделения пропускной способности сети с одноадресными и многоадресными соединениями между VPN, а также предложена постановка задачи максимизации суммарной интенсивности дохода, определяемого величиной обслуженной нагрузки одноадресных и многоадресных соединений, для отдельного звена. Особенностью является то, что целевая функция определена только для целочисленного аргумента, а при вычислении входящих в нее вероятностей блокировок применяются точные рекуррентные алгоритмы Кауфмана-Робертса (одноадресные соединения) и Гайдамака-Самуйлова (многоадресные соединения).

В разделе 2.2 разработан приближенный метод и алгоритм решения задачи разделения ресурсов звена мультисервисной сети с одноадресными и многоадресными соединениями. Разработанный метод является итерационным, он основан на анализе производных функций вероятностей блокировок в предположении об их дифференцируемости. На каждой итерации новые пропускные способности определяются с помощью вектора их изменения, который ищется путем решения задачи целочисленного линейного программирования. Данный метод основан на результатах, представленных в [84], где, в свою очередь, был модифицирован метод возможных направлений Зойтендейка [15]. При расчете величин производных функции вероятности блокировки используется конечно-разностная аппроксимация. Разработанный метод позволяет найти локальный максимум целевой функции. На основе проведенных численных экспериментов предложен набор критериев останова алгоритма решения задачи. Получена формула числа итераций при решении задачи перебором всех допустимых точек, которая демонстрирует актуальность разработки приближенных методов для решения задачи.

В разделе 2.3 исследуется модель разделения пропускной способности отдельного звена сети между VPN, по которому передается эластичный трафик, когда блоки данных получают максимальную на момент передачи пропускную способность, т.е. обслуживаются по принципу «best effort». В рассматриваемой модели блокировки отсутствуют, а вероятностной характеристикой, которая подлежит оптимизации, является среднее время передачи блока данных. Анализируются две стратегии разделения ресурсов: согласно первой из них минимизируется сумма средних времен передачи блоков данных во всех VPN, согласно второй - максимальное из средних времен. Для первой стратегии получено единственное решение в аналитической форме, показано, что при эффективном разделении ресурсов средние времена передачи блоков данных в различных VPN совпадают. Доказано, что решение для второй стратегии совпадает с решением для первой. Организован и проведен вычислительный эксперимент. Разделы 2.1.-2.3 написаны на основе публикаций с участием автора [23,79].

Глава 3 посвящена разработке методов анализа вероятностных характеристик модели разделения ресурсов мультисервисной телекоммуникационной сети. В разделе 3.1 получены результаты, необходимые для вычисления упущенных выгод и чувствительностей дохода к изменению пропускных способностей VPN - величин, используемых при решении задачи разделения пропускной способности сети. Предложены формулы расчета упущенных выгод, однако в связи с высокой вычислительной сложностью разработан приближенный метод расчета упущенных выгод для многоадресных соединений, основанный на предположении о независимости функционирования звеньев сети. Помимо доказательства для метода расчета упущенных выгод от установления многоадресных соединений, разработано доказательство для случая одноадресных соединений, в [84] этот метод предложен без доказательства. Аналогичное доказательство предложено в [92]. Получены формулы для расчета приращения интенсивности дохода от одноадресных и многоадресных соединений при изменении пропускных способностей звеньев, на их основании предложены формулы расчета чувствительностей дохода для обоих типов соединений.

В разделе 3.2 сформулирована задача разделения ресурсов сети между VPN с одноадресными и многоадресными соединениями, разработаны приближенный метод и соответствующий вычислительный алгоритм. Эта задача является задачей целочисленного нелинейного программирования с ограничениями, заданными набором линейных равенств, причем для вычисления значений целевой функции требуется применение разработанного в работах Ф. Келли, К. Росса и К.Е. Самуйлова приближенного метода просеянной нагрузки. Данный метод основан на результатах, полученных во второй главе, а также в разделе 3.1. На каждой итерации метода необходимо вычислять упущенные выгоды и чувствительности интенсивности дохода к изменению пропускных способностей, а также решать задачу перераспределения пропускной способности. Как и в случае отдельного звена, предложенный метод ищет локальный максимум целевой функции. По аналогии с задачей разделения ресурсов отдельного звена предложены критерии останова алгоритма расчета пропускных способностей. Раздел 3.3 посвящен организации вычислительного эксперимента и анализу эффективности разделения ресурсов мультисервисной сети между VPN с одноадресными и многоадресными соединениями. Разделы 3.1-3.3 написаны на основе публикаций с участием автора [25,26,80].

Помимо исследований при написании диссертации, автором ранее проводились сопутствующие исследования, в частности, была разработана вероятностная модель протокола инициирования сеансов связи SIP (Session Initiation Protocol) для анализа среднего времени установления соединения в сети следующего поколения [31], а также разработаны методы расчета параметров трафика интеллектуальной сети связи (ИСС) [32,50].

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

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

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

3. Разработка модели и метода анализа величины чувствительности дохода к изменению пропускной способности VPN с одноадресными и многоадресными соединениями;

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

В заключение сформулируем основные результаты и выводы работы.

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

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

3. Построена математическая модель для оценки эффективности разделения пропускной способности отдельного звена мультисервисной сети между VPN. В отличие от известных работ модель учитывает не только одноадресные, но и многоадресные соединения. Предложен приближенный метод решения задачи максимизации дохода от соединений, и показано, что в исследуемой в работе сети его относительная погрешность не превосходит 1%.

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

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

1. Арутюнов A.B. Условия экстремума. Анормальные и вырожденные задачи. - М.: Изд-во «Факториал», 1997. - 256 с.

2. Башарин Г.П. Лекции по математической теории телетрафика: Учеб. пособие. Изд. 3-е, испр. и доп. М.: Изд-во РУДН, 2009. - 342 с.

3. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. М.: Наука, Гл. ред. физ.-мат. лит., 1989. - 336 с.

4. Башарин Г.П., Самуилов К.Е., Яркина Н.В., Гудкова И.А. Новый этап развития математической теории телетрафика // Автоматика и телемеханика. М.: Академиздатцентр «Наука» РАН. - 2009. -№ 12.-С. 16-28.

5. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002. -824 с.

6. Васильев Ф.П. Численные методы решения экстремальных задач. -М.: Наука, 1988.-552 с.

7. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. -М.: Техносфера, 2003. 512 с.

8. Вишневский В., Портной С., Шахнович И. Энциклопедия WiMAX. Путь к 4G. М.: Техносфера, 2009. - 472 с.

9. Гwin Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с анг. -М.: Мир, 1985.-509 с.

10. Глебов Н.И., Кочетов Ю.А., Плясунов A.B. Методы оптимизации: Учебное пособие. Новосиб. ун-т. Новосибирск, 2000. - 105 с.

11. Гнеденко Б.В., Коваленко H.H. Введение в теорию массового обслуживания. М.: КомКнига, 2005. - 397 с.

12. Гольдштейн А.Б., Голъдштейн Б.С. Технология и протоколы MPLS. СПб.: БХВ-Санкт-Петербург, 2005. - 304 с.

13. Гольдштейн Б.С., Соколов H.A., Яновский Г.Г. Сети связи: Учебник для вузов. СПб.: БХВ-Петербург, 2010.-400 с.

14. Грешилов A.A. Математические методы принятия решений. Уч. пособие для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2006. -584 с.

15. Зойтендейк Г. Методы возможных направлений. Пер. с анг. С.М. Мовшовича. под. ред. Д.Б. Юдина. М.: Издательство иностранной литературы, 1963. - 176 с.

16. Кааранен X., Ахтиайнен А., Лаитинен Л., Найян С., Ниеми В. Сети UMTS. Архитектура, мобильность, сервисы. М.: Техносфера, 2007.-464 с.

17. Клейнрок Л. Коммуникационные сети. Стохастические потоки и задержки сообщений. М.: Наука, 1970. - 256 с.

18. Корнышев Ю.Н., Пшеничников А.П., Харкевич А.Д. Теория телетрафика. Учебник для вузов. М.: Радио и связь, 1996. - 272 с.

19. Кудрявцев Л.Д. Краткий курс математического анализа. Т. 2. Дифференциальное и интегральное исчисления функций многих переменных. Гармонический анализ: Учебник. 3-е изд., перераб. -М.: ФИЗМАТЛИТ, 2005. - 424 с.

20. Лагутин B.C., Степанов С.Н. Телетрафик мультисервисных сетей связи. М.: Радио и связь, 2000. - 320 с.

21. Ларин P.M., Пяткин A.B., Плясунов A.B. Методы оптимизации. Примеры и задачи: Учеб. Пособие. Новосиб. ун-т. Новосибирск, 2003.- 115 с.

22. Летников А.И., Пшеничников А.П., Гайдамака Ю.В., Чукарин A.B. Системы сигнализации в сетях с коммутацией каналов и пакетов. -М.: МТУ СИ, 2008.- 195 с.

23. Лузгачев М.В., Самуилов К.Е. Задача маршрутизации трафика на графе сети MPLS с одноадресными соединениями // Вестник РУДН. Серия «Математика. Информатика. Физика». 2009. - №1. - С. 2333.

24. Лузгачев М.В., Самуйлов К.Е. Метод решения задачи разделения ресурсов мультисервисной сети между виртуальными частнымисетями с одноадресными и многоадресными соединениями // Вестник РУДН. Серия «Математика. Информатика. Физика». -2010.-№2(1).-С. 42-53.

25. Лузгачев М.В., Самуйлов К.Е. Об одной задаче оптимизации ресурсов мультисервисной сети с одноадресными и многоадресными соединениями // Труды РНТОРЭС им.

26. A.C. Попова. Серия: Научная сессия, посвященная Дню радио. -Вып. LXIV. 2009. - С. 20-22.

27. Наумов В.А., Самуйлов К.Е., Яркина Н.В. Теория телетрафика мультисервисных сетей: Монография. М.: Изд-во РУДН, 2007. -191 с.

28. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход. 2-е изд., испр. и доп. - М.: ФИЗМАТЛИТ, 2005. - 176 с.

29. Росляков A.B. Виртуальные частные сети. Основы построения и применения. -М.: Эко-Трендз, 2006. 304 с.

30. Самуйлов К.Е. Методы анализа и расчета сетей ОКС-7: Монография. М.: Изд-во РУДН, 2002. - 291 с.

31. Самуйлов К.Е., Чукарин A.B., Бобриков Н.В., Лузгачев М.В. К расчету параметров трафика в интеллектуальной сети связи // Вестник РУДН. Серия Прикладная и компьютерная математика. Т.4. №1.2005.-31-39 с.

32. B.А. Трапезникова РАН. 2009. - С. 1722-1730.

33. Севастьянов Б. А. Эргодическая теорема для марковских процессов и ее приложение к телефонным линиям с отказами // Теория вероятностей и ее приложения. 1957. - Т. 2, вып. 1. - С. 106-116.

34. Степанов С.Н. Основы телетрафика мультисервисных сетей. М.: Эко-Трендз, 2010.-392 с.

35. ТахаХ.А. Введение в исследование операций / Пер. с англ. Изд. 6-е.- М.: Издательский дом «Вильяме», 2001. 912 с.

36. Тихвинский В. О., Терентъев С.В., Юрчук А.Б. Сети мобильной связи LTE. Технология и архитектура. М.: Эко-Трендз, 2010. - 283 с.

37. Шнепс-Шнеппе М.А. Лекции по сетям связи следующего поколения NGN. М.: МАКС Пресс, 2005. - 232 с.

38. Яновский Г.Г. IP Multimedia Subsystem: принципы, стандарты и архитектура // Вестник Связи. №3. - 2006. - С. 71—76.

39. Яшков С.Ф., Яшкова А. С. Разделение процессора: обзор математической теории // Информационные процессы. 2007. - Т.7. -№3. - С. 248-322.

40. Awduche D., Chiu A., Elwalid A., Widjaja I., XiaoX. Overview and Principles of Internet Traffic Engineering / RFC 3272. IETF, 2002.

41. Bazaraa M.S., Jarvis J.J., Sherali H.D. Linear Programming and Network Flows, fourth edition. John Wiley & Sons, Inc., New York, NY, 2010.-748 p.

42. Bocharov P.P., D'Apice C., Pechinkin A. V., Salerno S. Queueing Theory.- Utrecht Boston: VSP, 2004. - 735 p.

43. Cerav S.K., Mathar R. An Off-line Traffic Engineering Model for MPLS Networks // Proceedings of the 27th Annual IEEE Conference on Local Computer Networks, IEEE Computer Society, Washington, DC, USA, 2002.-Pp. 166-174.

44. Chatzaki M., Sartzetakis S., Papadakis N., Courcoubetis C. Resource Allocation in Multiservice MPLS // In Proc. of the 7th IEEE/IFIP IWQoS'99 International Workshop on Quality of Service, UCL, London, UK, May 31 June 4, 1999. - Pp. 197-206.

45. Chou. C.T. Traffic engineering for MPLS-based virtual private networks // Computer Networks, vol.44, no.3, 2004. Pp.319-333.

46. Chukarin A., Bobrikov N., Luzgachev M. Signaling and Intelligent Large-scale Network Dimensioning and Planning // Proc. of the 13th IEEE Mediterranean Electrotechnical Conference, Melecon 2006, Benalmadena, May 2006. Pp. 725-728.

47. Coello Coello C., Lamont G., Van Veldhuizen D. Evolutionary algorithms for solving multi-objective problems. Second Edition. -Springer, 2007. 800 p.

48. Corne D. W., Oates M.J., Smith G.D. Telecommunications Optimization: Heuristic and Adaptive Techniques // John Wiley & Sons, Ltd.; 2000. -416 p.

49. Cotter R., Medhi D. Survivable design of reconfigurable MPLS VPN networks // 7th International Workshop on Design of Reliable Communication Networks, 2009, DRCN 2009. Pp. 78-85.

50. Craveirinha J., Girao-Silva R., Climaco J. A Meta-Model for Multiobjective Routing in MPLS // Central European Journal of Operations Research, Volume 16, Number 1, March 2008. Pp. 79-105.

51. Donoso Y, Fabregat R. Multi-Objective Optimization in Computer Networks Using Metaheuristics. Auerbach Publications, 2007. - 472 p.

52. Elias J., Martigno F., Capone A. An Efficient Dynamic Bandwidth Allocation Algorithm for Quality of Service Networks // in Proc. of First International IFIP TC6 Conference, AN 2006, Paris, France, September 27-29, 2006.-Pp. 132-145.

53. Figueira J., Greco S., Ehrgott M. Multiple Criteria Decision Analysis: State of the Art Surveys // Springer; 1 edition, 2004. 245 p.

54. Gaidamaka Y., Samouylov K. Analytical model of multicast network and single link performance analysis // Proc. of the 6-th International Conf. on Telecommunications, Zagreb, Croatia, 2001. Pp. 169-175.

55. GAMS Solver manual. GAMS Development Corporation, 2001.

56. Gao D.Y., Sherali H.D. Advances in Applied Mathematics and Global Optimization: In Honor of Gilbert Strang (Advances in Mechanics and Mathematics). Springer; 1 edition, 2009. - 520 p.

57. Garg R., Saran H. Fair bandwidth sharing among virtual networks: A capacity resizing approach // Proc. of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2000, March 2000. Pp. 255-264.

58. Gen M., Cheng R., Lin L. Network Models and Optimization. -Springer; 1 edition, 2008. 692 p.

59. Gibbens R.J., Kelly F.P., Network programming methods for loss networks // IEEE J. Sel. Areas Commun., vol. 13, no. 7, Sep. 1995. -Pp. 1189-1198.

60. Girará A., Sansó B., Vázquez-Abad F. Performance Evaluation and Planning Methods for the Next Generation Internet. Springer; 1 edition, 2005.-365 p.

61. Ishibashi K., Ishizuka M., Aida M., Ishii H. Capacity dimensioning of VPN access links for elastic traffic // Proc. of the IEEE International Conference on Communications ICC'03, vol.3, 2003. Pp. 1547-1551.

62. Iversen KB. Teletraffic Engineering Handbook. ITU-D SG 2/16 & ITC 2002/09/06, 2002. - 324 p.

63. Kelly F.P. Fixed point models of loss networks // J. Austr. Math. Soc., Ser. B, Vol. 31. - Pp. 204-218.

64. Kelly F.P. Reversibility and Stochastic Networks. New York: J. Wiley & Sons, 1979.-630 p.

65. Kumar P., Dhanakoti N., Gopalan S., Sridhar V. CoS Based Resource Allocation (CBRA) in VPNs over MPLS // Proc. IEEE Workshop on IP Operations and Management, 2004. Pp. 140-145.

66. Kumar R. Multicriteria Network Design Using Distributed Evolutionary Algorithm // Proc. of the 2003 international conference on Genetic and evolutionary computation: Partll. Chicago, IL, USA, 2003. Pp. 21792190.

67. Lagariasy J.C., Reedsz J.A., Wrightx M.H., Wright P.E. Convergence properties of the NELDER-MEAD Simplex method in low dimensions. // Society for Industrial and Applied Mathematics Vol. 9, No. 1, 1998.-Pp. 112-147.

68. Lam N., Dziong Z., Mason L.G. Network capacity allocation in service overlay networks // in Proc. of the 20th international teletraffic conference on Managing traffic performance in converged networks, Ottawa, Canad, 2007. Pp. 224-235.

69. Liu Y.L., Sun Y.S., Chen M.C. MTRA: An on-line hose-model VPN provisioning algorithm // Telecommunication Systems, Volume 31, Number 4, April 2006. Pp. 379-398.

70. Luenberger D.G., Ye Y. Linear and Nonlinear Programming. Third Edition. Springer, 2008. - 560 p.

71. Martins L., Craveirinha J., Climaco J. A New Multiobjective Dynamic Routing Method for Multiservice Networks Modelling and Performance // Comput. Manag. Sci. 3, No. 3, 2006. Pp. 225-244.

72. Mitra D., Morrison J.A., Ramakrishnan K.G. Optimization and Design of Network Routing Using Refined Asymptotic Approximations // Perform. Eval. 36-37(1-4), 1999. Pp. 267-288.

73. Mitra D., Morrison J.A., Ramakrishnan K.G. Virtual private networks: joint resource allocation and routing design // in Proc. Eighteenth Annual

74. Joint Conference of the IEEE Computer and Communications Societies. INFOCOM'99, vol. 1, New York, NY, 1999. Pp. 480^190.

75. Mitra D„ Morrison J.A., Ramakrishnan K.G. VPN DESIGNER: A tool for design of multiservice virtual private networks // Bell Labs Tech. J. Volume 3, Issue 4, October/December 1998. Pp. 15-31.

76. Montgomery M.; de Veciana G. Hierarchical Source Routing Using Implied Costs // Computer Networks, Volume 34, Number 3, September 2000.-Pp. 379-397.

77. Oki E., Iwaki A. Performance Comparisons of Optimal Routing by Pipe, Hose, and Intermediate models // IEEE Sarnoff Symposium, 2009. -Pp. 1-5.

78. Osborne E., Simha A. Traffic Engineering with MPLS. Cisco Press, 2002.-608 p.

79. Qu S., Lindqvist J. Scalable IPTV Delivery to Home via VPN // Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, Volume 40, Part 10, 2010. Pp. 237246.

80. Quanshi Xia. Provisioning VPN over Shared Network Infrastructure // P. Lorenz and P. Dini (Editors): ICN 2005, LNCS 3420, Springer-Verlag

81. Berlin Heidelberg, 2005. Pp. 500-507.

82. Resende M., Pardalos P. Handbook of Optimization in Telecommunications. 1 edition, Springer, 2006. - 1174 p.

83. Ross K. W. Multiservice loss models for broadband telecommunication networks. London: Springer-Verlag, 1995. - 343 p.

84. Samouylov K.E., Plaksina O.N. Approximating blocking probabilities for multiservice network link with unicast and multicast connections // Proc. of the International IEEE Conference EUROCON 2009. Russia, Saint Petersburg. Pp. 1814-1817.

85. Samouylov K., Yarkina N. Blocking probabilities in multiservice networks with unicast and multicast connections // Proc. of the 8th International Conference on Telecommunications, 2005. ConTEL 2005. Volume 2, June 15-17, 2005. Pp. 423-429.

86. Sousa P., Rocha M, Cortez P., Rio M. Multiconstrained optimization of networks with multicast and unicast traffic // G. Pavlou, T. Ahmed, T. Dagiuklas (editors): MMNS 2008, LNCS 5274, 2008. Pp. 139-150.

87. Srivastava S., Medhi D. Traffic engineering of tunnel-based networks with class specific diversity requirements // Journal of Combinatorial Optimization. vl2, 2006. Pp. 97-125.

88. Tong H., Brown T.X. Reinforcement Learning for Call Admission Control and Routing under Quality of Service Constraints in Multimedia Networks // Machine Learning, Volume 49, Issue 2-3, 2002. Pp. 111139.

89. Vassilakis V., Moscholios I., Logothetis M. Call-Level performance modelling of elastic and adaptive service-classes with finite population // IEICE Transactions on Communications. Vol. 91-B, No. 1, 2008. -Pp. 151-163.

90. Wu J., Yue W., and Wang S. Optimization of Bandwidth Allocation in Communication Networks with Penalty Cost // V.S. Sunderam et al. (Editors): ICCS 2005, LNCS 3516, 2005. Pp. 539-547.

91. Wuthnow M., Shih J., Stafford M. IMS: A New Model for Blending Applications. Auerbach Publications, 2009. - 368 p.

92. Zhang D., Ionescu D. Online Packet Loss Measurement and Estimation for VPN-Based Services // IEEE Transactions on Instrumentation and Measurement, Aug. 2010. Pp. 2154-2166.