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

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

САВОЧКИН ЕГОР АЛЕКСАНДРОВИЧ

ВЕРОЯТНОСТНЫЙ АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ ОПТИЧЕСКИХ СЕТЕЙ С МАРШРУТИЗАЦИЕЙ ПО ДЛИНЕ ВОЛНЫ

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

Автореферат

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

Москва-2005

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

Научный руководитель -заслуженный деятель науки РФ, академик РАЕН, доктор технических наук, профессор Г.П. Башарин

Официальные оппоненты:

доктор физико-математических наук, профессор С.Я. Шоргин кандидат физико-математических наук, доцент В. А. Ефимушкин

Ведущая организация:

Институт проблем передачи информации РАН

Защита диссертации состоится «21» октября 2005 г. в 15 час. 30 мин. на заседании диссертационного совета К 212.203.08 при Российском университете дружбы народов по адресу 117923, г. Москва, ул. Орджоникидзе, 3

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

Автореферат разослан «_» сентября 2005 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук доцент

М. Б. Фомин

/3£>¿1

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

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

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

A.Н., Хинчин А.Я., Гнеденко Б.В., Башарин Г.П., Боровков A.A., Бочаров П.П., Вишневский В.М., Климов Г.П., Коваленко И.Н., Наумов В.А., Нейман

B.И., Печинкин A.B., Рыков В.В., Севастьянов Б.А., Степанов С.Н., Харкевич А.Д., Шнепс-Шнеппе М.А., Яновский Г.Г. и др. - и зарубежными учеными -Feller W., Beneä V.E., Cooper R.B., Iversen V.B., Kelly F.P., Kleinrock L., Neuts M.F., Perros H.G., Riordan J., Ross K.W. и др. - разработано большое количество математических моделей и численных методов их анализа, которые широко применяются при создании различных телекоммуникационных сетей. Однако, специфические особенности оптических технологий, например, технологии мультиплексирования с разделением длин волн (Wavelength Division Multiplexing - WDM), ставят перед теорией телетрафика ряд задач, которые не возникали ранее. В частности, в отличие от традиционных сетей с коммутацией каналов, в которых в каждом звене соединение может использовать любой свободный канал, соединение в сетях WDM с маршрутизацией по длине волны может быть установлено только на одной и той же длине волны на всех звеньях маршрута. Таким образом, процессы установления и обслуживания соединений разных классов зависимы, особенно в сетях с многоадресными соединениями. Данные обстоятельства приводят, к тому, что состояние

НАЦИОНАЛЬНА*

системы нельзя полностью описать числ >м уWMfHflfHW соединении

*>с нацнуилльи

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

Известные сегодня модели ТМО и теории телетрафика, применяемые для анализа производительности и качества обслуживания оптических сетей, разработаны зарубежными специалистами, такими как Birman A., Rouskas G.N., Perros H.G., Mukheijee В., Sivarajan K.N., Somani А. и др., причем в последние годы число подобных публикаций быстро растет. В российской научной литературе пока очень мало публикаций на эту тему.

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

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

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

Методы исследования. В работе использованы методы теории вероятностей, ТМО, теории телетрафика, теории матриц.

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

- Разработана новая математическая модель линейного фрагмента

оптической,,, сети,- WDM с маршрутизацией по длине волны,

• t,. ¿j* - ' "

* 4

учитывающая как одноадресные, так и многоадресные соединения с динамической структурой;

- Метод модификации интенсивностей переходов обобщен для анализа линейного фрагмента сети WDM с одноадресными и многоадресными соединениями с динамической структурой;

- Доказана теорема о мультипликативном виде равновесного распределения и макрораспределения модифицированного процесса;

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

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

Практическая ценность работы. Аналитические методы и вычислительные алгоритмы, полученные в диссертации, предназначены для анализа характеристик качества обслуживания в оптических сетях, использующих технологии мультиплексирования с разделением длин волн (WDM) и маршрутизации по длине волны. Результаты могут быть использованы при анализе фрагментов оптических сетей или могут быть обобщены для изучения оптических сетей WDM с произвольной топологией. Результаты исследований используются в учебном процессе на кафедре систем телекоммуникаций РУДН для студентов, обучающихся по направлению «Прикладная математика и информатика», а также в курсовых и дипломных работах.

Реализация результатов работы. Работа проводилась в рамках НИР 020602-1-173 (2003-2005) "Разработка математических моделей и анализ

информационно-телекоммуникационных сетей и интеллектуальных систем", выполняемой в соответствии с планами РУДН, а также при частичной поддержке программы «Университеты России» (НИР «Разработка математических моделей и методов анализа систем сложной структуры в цифровых сетях», шифр УР.03.01.022 (2004) и УР.03.01.252 (2005)).

Апробация работы. Результаты, полученные в ходе выполнения диссертационной работы, докладывались на

- XXXVIII-XL научных конференциях факультета физико-

математических наук РУДО! (Москва 2002 - 2004);

- LVII, LIX, LX научных сессиях РНТОРЭС им. A.C. Попова (Москва,

2002-2005);

- 8-й международной конференции ConTEL'2005 (Загреб, 2005);

- 19-ом международном конгрессе по телетрафику ГГС-19 (Пекин, 2005);

- Семинарах кафедры систем телекоммуникаций РУДН (Москва 20022005).

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

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

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

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

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

В разделах 1.1 - 1.4 приводится краткое описание технологии мультиплексирования с разделением длин волн (WDM), структурных компонентов сети, применяемых при построении оптических сетей, а также приводится описание широковещательной архитектуры оптической сети WDM и архитектуры сети с маршрутизацией по длине волны. Вводятся и характеризуются такие понятия как «световой путь», «оптический кросс-коммутатор», «степень конверсии узла», «ограничение постоянства длины волны», «ограничение использования различных длин волн».

В разделе 1.5 формулируется задача установления световых путей известная как задача «маршрутизации и назначения длин волн» (Routing and Wavelength Assignment - RWA). Приводится описание основных эвристические подходов, применяемых при выборе маршрута и длины волны для установления светового пути.

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

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

Глава 2 посвящена построению математической модели линейного фрагмента сети WDM с маршрутизацией по длине волны с одно- и многоадресными соединениями, услуги в которой предоставляются в виде передачи данных по принципу коммутации каналов по световым путям.

В разделе 2.1 формулируются основные предположения и вводятся необходимые обозначения.

Сделаем следующие предположения: (1) топология сети представляет собой линейный путь, / = {l,...,J) - множество звеньев; (2) узлы сети не оборудованы волновыми конвертерами; (3) каждое звено сети поддерживает W каналов WDM (длин волн), W - множество длин волн; (4)

имеется К классов заявок; каждая к - заявка (ке Ж = ЛГ}) представляет собой одно- или многоадресное соединение по некоторому маршруту (последовательности звеньев) из множества маршрутов Я = {1,...,Я}; пусть •К> х* ' множества одноадресных и многоадресных классов заявок соответственно, Ж - Жи и Жт,Жиг\Хт = Я\ (5) в систему поступает пуассоновский поток к - заявок с интенсивностью Хк, к € Ж; (б) при поступлении заявки на установление одноадресного соединения по некоторому маршруту, новое соединение устанавливается только в том случае, если есть длины волн свободные на всем маршруте; длина волны выбирается случайным образом среди всех доступных длин волн; (7) при поступлении заявки на установление многоадресного соединения, новое соединение устанавливается только в том случае, если соединение данного класса не установлено ни на одной длине волны; длина волны выбирается случайным образом среди всех доступных длин волн; если соединение данного класса уже установлено на какой-либо длине волны, то заявка «присоединяется» к существующей передаче не влияя на параметры обслуживания данного соединения;' (8) заявки, которые не могут быть обслужены из-за недостатка ресурсов сети, блокируются и теряются, не оказывая влияния на рассматриваемый фрагмент сети. (9) время

обслуживания соединения распределено по экспоненциальному закону со средним $, кеЛС;

Введем матрицы: О := » гДе Я ¡г индикатор того, что маршрут

г включает в себя звено , где Л^ индикатор того, что к -

класс использует звено в где этой матрицы являются

индикаторами того, что маршруты к и / пересекаются.

I I * I *

= { 1,..., Ж } - мишсспо

1 ; [ : '! © я""(1 ->кптк»иршруго«;

" ^ Я - {1,2,3,4} - икотстю классов

^ t t '*nS"r""W,:

_1_I г • (1.2A3) - «П(>шр)гш шссм

I К.».

Рис. 1 Пример 2-звеньевого линейного фрагмента сети WDM На Рис. 1 схематично изображен двухзвеньевой линейный фрагмент, состоящий из трех узлов, соединенных между собой двумя звеньями, каждое из которых поддерживает две длины волны. В примере на фрагмент поступает четыре класса заявок на установление трех одноадресных и одного многоадресного соединения.

В разделе 2.2 производится построение пространства состояний модели и марковского процесса, описывающего её функционирование.

Состояние J - звеньевого линейного фрагмента описывается матрицей где xwt - индикатор того, что установлено к - соединение на

длине волны w. Заметим, что х,к := - число к - соединений, которые

»-цк

установлены в системе в состоянии х. Пространство состояний линейного фрагмента имеет вид

О = [х е {0,1}™ : Шт е {0,1}""" е {0,1},У к е Хт], (1)

Обозначим !%(х) и /4(х)?=|.^;(х)|е{1,...,^} - множество и число свободных длин волн для установления к - соединения в состоянии % соответственно. Пусть *ж4(0е{0,1} - случайное число световых путей установленных для к -соединения на длине волны и* в сети в момент времени Динамика функционирования в равновесном1 режиме описывается марковским процессом Х(0 = (х„4(0)^Мх. '£0 с равновесным распределением р(х),

хе£1 и матрицей интенсивностей переходов А:= (а(*»У))„еП• Из

сделанных предположений следует, что равновесное распределение удовлетворяет СУГБ:

/»00

Ш

».* I-«., сП Jh. W+1

Лемма 1. Если W>\ и существуют классы соединений такие, что

выполняется Д п/^й^с/Д cjftj) где ^ > {у е$:hJk = l} -множество звеньев, используемых к - соединением, то процесс X(f) не является обратимым.

В разделе 2.3 приводятся результаты численного анализа двухзвеньевого линейного фрагмента. Сравниваются результаты численного решения СУР и результаты, полученные с помощью имитационного моделирования.

Глава 3 посвящена приближенному анализу линейного фрагмента сети WDM с маршрутизацией по длине волны.

В разделе 3.1 приводится метод модификации интенсивностей переходов для приближенного анализа линейного фрагмента сети WDM.

Функционирование линейного фрагмента в равновесном режиме может быть аппроксимировано обратимым марковским процессом X(t) = (xri(t))^ ujr, определенным над пространством состояний Q, с

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

матрицей интенсивиостей переходов А:=(а(х,у))1^п, которая получается модификацией некоторых интенсивиостей переходов исходного процесса. Обозначим О(й)хеО: п = 1гх = },я еЛ - макросостояние,

включающее в себя такие состояния двухзвеньевого линейного фрагмента, в которых установлено пк соединений к - класса. Здесь - множество возможных векторов Я. Заметим, что введенные множества попарно не пересекаются так, что и £2(й) = О.

Будем аппроксимировать процесс Х(г) марковским процессом Х(/). Обозначимся)" ]Г р(х), ]Г$(й) = 1.

Теорема 1. Марковский процесс Х(*), определенный над пространством состояний П, с инфинитезимальной матрицей А:= (<5(х>У)),,^еП > полученной модификацией интенсивиостей переходов процесса Х(1)

У) = \а(Х'^Х)' = Х + (2)

[ а(Х, у), в прот. случае

К

<РМ= }кГ п -^-. <3>

V ~ IV« V - £ -

¡-к Ыя* I

имеет мультипликативное равновесное распределение

йж) = <Г'П7-, ,хеО, (4)

Ы+1 ),

а также

где

* о"»

?(я) = С?-'П^. пвлг (5)

м V

(б)

нормирующая константа.

Вероятность блокировки запросов на установление соединения по

маршрутам приближенно равна Вк * := ^ р(х), де Щ - множество

иЛ

состояний блокировок к - заявок.

Теорема 1 определяет приближенный метод расчета равновесного распределения линейного фрагмента сети. Использованный метод мы будем называть методом «модификации интенсивностей переходов».

В разделе 3.2 рассматривается задача расчета нормирующей константы равновесного распределения. Без ограничения общности будет предполагать, что классы заявок упорядочены по неубыванию длин используемых физических маршрутов, т.е. выполняется А., <... < к.к. Обозначим

(щ.^УЛй пк £ п„51т,1 = Щ

т=М )

(7)

*(*,*>:= Е Г1~- (8)

¡м.Цк,ж) М я, ■

Теорема 2. Функция g(k,w) вычисляется по формуле

/=о

(9)

с начальным условием §(0,0) = 1 (10)

Следствие 1. Нормирующая константа (6) распределения (4) вычисляется по формуле

С = е(Х,Ю,где Г = (11)

Полученные результаты определяют метод расчета нормирующей константы: по формулам (9), (10) могут быть рекурсивно вычислены значения функций а по формуле (11) вычисляется искомое значение

нормирующей константы (б)

В разделе 3.3 рассматривается задача вычисления вероятностей блокировок заявок на установление соединений.

Вероятности блокировок заявок можно разложить следующим образом: Ва = £/?т(п)ч(п), где Дт(п)~р{х.е&т\хеП(й) | - доля состояний х с п

ЯЛ-Г

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

Введем функцию /т(к,Й,\>,п) такую, что

дг Ч

* Г„(*-1,АГ-54я4,у + »4,й)и(»11я-1пт(АГ(-^)+1), V, =0,

9

г.-» \У*У

при А:> 1 или А = 1 и у,>0,атакже ^(1,^,0,«,) = -

С'}

при к = 1 и V, =0, где Ик(а,Ь) = 1ка-ек{Ь-а), = ^(Т — ^ хЗдесь

и(х) = - функция Хевисайда, 8Ц = ' * - символ Кронекера.

1, '= У 0, I*)

Теорема 3. Величина /0„(л) может быть вычислена по формуле

М-^.т-йк.

(12)

^е |П(Й)| = П *»1

Ык* I П.

- мощность множества состоянии, в которых

установлено п соединений, Уа(п) = \30т глС1(п)\ - число состояний из множества П(й), в которых нельзя установить новое т - соединение.

Причем, /т(п) = ут(К,К,0,п), где N = (М,\~, ' •

I ' 6 Лт

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

Д, I л,

7~1 ,

1 ,1

4,1 1> * 1-

4.1

(Ь)

1 | <Ч" [Л 1 чг

, * 2 1

'' оЦо (=4 о ;оЕ ЗОЁ 5о

? т

1 т т т т

Л'"

/-(1.2.3.4) -» = { I, Л

{1.2.3,4.5,6) -М, X. »{1,2,3.4,5} -«,

> юпесюсмд

Н- 2

5

12 3 4 5«

0 0 11 0 0 11 10 11 0 111

Л"1

Л = « = 1,

-(1,2)-«

= { I, . № } 'Инвснстмпннюлниатн ■ {1,2,3,4} - мномстаоклассовсосдмммиИ

= {1,2,3) - множество оджмир классов сосд -{4} •■«юястюиппир шсюксспншД

2

1.*»П4 2

Рис. 2 (а) четырехзвеньевой линейный фрагмент (Ь) его декомпозиция на два двухзвеньевых сегмента

Мы будем анализировать функционирование четырехзвеньевого линейного фрагмента, представленного на Рис. 2 (а) путем его декомпозиции на два сегмента как это показано на Рис. 2 (Ь). Пусть марковский процесс Хг,>(г)Д>0, определенный над множеством состояний С1(1>, описывает функционирование сегмента 5 = 1,2.

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

Мы будем рассматривать сегменты независимо друг от друга при следующей предложенной нагрузке:

Л<'>=^(1-д») (13)

==я,л<3)=ло - г/'и2)=ло - 4г)) (н)

на первый и второй сегменты соответственно. Мы будем считать, что

вероятности блокировок 5,, к = 1,К исходного четырехзвеньевого

линейного фрагмента приближенно равны следующим значениям:

«В?\В, «Д. (15)

Здесь, « и Ьк ы Вк - приближенные оценки вероятностей Д" и соответственно.

В разделе 3.5 приводятся результаты численного анализа примеров двухзвеньевых и четырехзвеньевых фрагментов, рассмотренных в диссертации. Для двухзвеньевого фрагмента на графиках сравниваются результаты полученные методом численного решения СУР и метода модификации интенсивностей переходов. На рисунке 3 можно видеть, что кривые блокировок, полученных этими методами очень близки, т.е. метод имеет малую погрешность.

\ - Л, - О 05,* - О 03. Д, . <ХР 03» 15, ц - я, . л - 1 - 2

блпвирочи

Рис. 3 График изменения вероятностей блокировок всех классов заявок, полученных решением СУР и алгоритмом «модификации», при увеличении интенсивности поступления 4 - заявок

• Мцдоте t I—ill

Рис. 4 График изменения вероятностей блокировок всех классов заявок, полученных с помощью имитационного моделирования и алгоритмом «декомпозиции», при увеличении интенсивности числа длин волн, ¡V.

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

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

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

- Метод модификации интенсивностей обобщен для анализа линейного фрагмента сети WDM с одноадресными и многоадресными соединениями с динамической структурой;

- Доказана теорема о мультипликативном виде равновесного и макрораспределения модифицированного процесса.

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

Основные результаты работы отражены в следующих публикациях:

1. Башарин Г.П., Савочкин Е.А. Анализ многозвеньевого маршрута

оптической сети с маршрутизацией по длине волны // Тр. 59 конф. РНТОРЭС. - 2004. - Т.1. - С. 8-10.

2. Башарин Г.П., Савочкин Е.А. Анализ пропускной способности

линейного фрагмента оптической сети с маршрутизацией по длине волны // Электросвязь. - 2005. - №5. - С.48-52.

3. Савочкин Е.А. Мультипликативное решение для одного класса

полностью оптических сетей без волновой конверсии // Труды 59 конф. РНТОРЭС. - 2004. - Т.2. - С.171-173.

4. Самуилов К. Е., Савочкин Е. А. Модель сети мультивещания с

несколькими уровнями качества предоставляемых услуг // Сб. научн. трудов «Системы телекоммуникаций и моделирование сложных систем». - М.: ПАИМС, 2001. - С. 70-76.

5. Самуилов К. Е., Савочкин Е. А. Алгоритм свертки для расчета

вероятностных характеристик сети с многоадресными соединениями и несколькими источниками информации // Сб. научн. трудов «Системы телекоммуникаций и моделирование сложных систем». -М.: ПАИМС, 2002. - С. 29-37,

6. Самуйлов К.Е., Савочкин Е.А. Модель сети мультивещания с потерями

// Труды 57 конф. РНТОРЭС. - 2002. - Т.2. - С. 183-184.

7. Basharin G.P., Savochkin ЕЛ. An Approach to Approximately Calculate

the Blocking Probabilities for a Special Case of Network with Fixed Routing and No Wavelength Conversion II Вестник РУДН (Прикладная и компьютерная математика). - 2002. - Т. 1, №1. - С. 25-34.

8. Basharin G.P., Savochkin ЕЛ. Flow Modification and Decomposition

Approach for Analyzing Wavelength Routed All-Optical Networks II Вестник РУДН (Прикладная и компьютерная математика). - 2004. -Т. 3, №1. -С.5-18.

9. Basharin G.P., Savochkin ЕЛ. Calculating Blocking Probabilities in

Wavelength Routed Networks with Multiclass Unicast and Multicast Calls // Proc. ConTEL conf. - Zagreb, 2005. - Vol. 2. - Pp. 501-506.

10. Basharin G.P., Savochkin ЕЛ. Decomposition Analysis of Linear

Fragments of Wavelength Routed WDM Networks with Multicast Calls // Proc. ITC-19. - Beijing, 2005. - Vol. 6a. - Pp. 1059-1069.

11. Basharin G.P., Savochkin E.A., GroubnikA. V. A Product-form Solution for

a Class of Wavelength Routed All-Optical Networks without Wavelength Conversion // Вестник РУДН (Прикладная и компьютерная математика). - 2003. - Т. 2, №1. - С.13-23.

Савочкин Егор Александрович (Россия)

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

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

Savochkin Egor Alexandrovich

Probabilistic performance analysis of wavelength-routed optical networks

A mathematical model of a linear fragment of WDM wavelength-routed optical network with unicast and multicast calls is developed in the thesis. It was assumed that the network is not equipped with wavelength converters and that lightpath set up process consists of two steps - the predefined fixed route between source and destination is selected, a wavelength is selected among all available wavelengths on the route. Effective analytical and algorithmic approaches for approximately evaluating equilibrium distribution and blocking probabilities of calls are presented.

Подписано в печать Ов ¿1Г Формат 60x84/16. Тираж4£>0 экз. Усл. печ. л. V . Заказ 2 &V

Типография Издательства РУДН 117923, ГСП-1, г. Москва, ул. Орджоникидзе, д. 3

1 59 49

РНБ Русский фонд

2006-4 13022

ВВЕДЕНИЕ.

ГЛАВА 1. ПРИНЦИПЫ ФУНКЦИОНИРОВАНИЯ СЕТЕЙ WDM.

1.1 Оптические технологии передачи данных.

1.2 Мультиплексирование с разделением длин волн.

1.3 Архитектуры оптических сетей WDM.

1.3.1 Широковещательные сети.

1.3.2 Сети с маршрутизацией по длине волны.

1.4 Конверсия длин волн.

1.5 Задача маршрутизации и назначения длин волн.

1.6 Одноадресные и многоадресные соединения.

1.7 Задачи теории телетрафика в сетях WDMс маршрутизацией по длине волны

1.7.1 Построение математической модели сети.

1.7.2 Анализ вероятностей блокировок линейного фрагмента сети с одноадресными соединениями.

1.7.3 Анализ вероятностей блокировок линейного фрагмента сети с одно-и многоадресными соединениями.

ГЛАВА 2. МАТЕМАТИЧЕКАЯ МОДЕЛЬ ЛИНЕЙНОГО ФРАГМЕНТА С ОДНО- H МНОГОАДРЕСНЫМИ СОЕДИНЕНИЯМИ

2.1 Предположения и обозначения.

2.2 Пространство состояний и равновесное распределение.

2.3 Численные результаты.

ГЛАВА 3. ПРИБЛИЖЕННЫЙ АНАЛИЗ ЛИНЕЙНОГО ФРАГМЕНТА С ОДНО- И МНОГОАДРЕСНЫМИ СОЕДИНЕНИЯМИ.

3.1 Метод модификации интенсивностей переходов.

3.2 Вычисление нормирующей константы.

3.3 Расчет вероятностей блокировок.

3.4 Метод декомпозиции.

3.5 Численные результаты.

Первые задачи теории телетрафика состояли в изучении телефонных и телеграфных сетей. Начало теории телетрафика восходит к работам датского математика А. К. Эрланга, исследовавшего статистические характеристики работы телефонных сетей и опубликовавшего в 1909 году свою основополагающую работу "Теория вероятностей и телефония"1. Простые модели, разработанные в первую четверть XX века А.К. Эрлангом и Т.О. Энгсетом [1, 2,18,20], позволили достаточно точно описать функционирование телефонных сетей связи и коммутационного оборудования. В течение XX века в развитие этого направления большой вклад внесли математики ряда стран, включая А.Н. Колмогорова и А.Я. Хинчина. К середине XX века окончательно сложилась новая прикладная математическая дисциплина - теория массового обслуживания (англ. термин - theory of queues), отвечающая на запросы различных областей техники.

Связь - одна из самых динамично развивающихся отраслей. Достижения в областях электроники, разработки новых материалов, радио, вычислительной техники ставили перед учеными новые задачи [2, 8, 9, 10, 12, 13, 15, 16, 17, 18, 20, 21, 23, 34, 36, 38]. Многими известными российскими - Гнеденко Б.В., Башарин Г.П., Боровков А.А., Бочаров П.П., Вишневский В.М., Климов Г.П., Коваленко И.Н., Наумов В.А., Нейман В.И., Печинкин А.В., Пшеничников А.П., Рыков В.В., Севастьянов Б.А., Степанов С.Н., Харкевич А.Д., Шнепс-Шнеппе М.А., Яновский Г.Г. и др. - и зарубежными учеными - Feller W., Benes V.E., Cooper R.B., Iversen V.B., Kelly F.P., Kleinrock L., Neuts M.F., Perros H.G., Riordan J., Ross K.W. и др. - разработано большое количество математических моделей и численных методов их анализа, которые широко применяются при

1 Erlang А.К. «The Theory of Probabilities and Telephone Conversations», Nyt Tidsskrit for Matematik B, Vol. 20 (1909). создании различных телекоммуникационных сетей [1, 2, 9,

10,11,14,16,17,18,20, 21, 33, 38, 51, 56, 63].

С момента развертывания первых телефонных и телеграфных сетей потребность пользователей в пропускной способности сетей растет экспоненциальным образом. Традиционные телекоммуникационные сети связи, использующие медный кабель, достигли своего предела и уже не могут обеспечить нужную производительность телекоммуникационных сетей [15, 49, 62, 74, 82]. Поэтому в последнее время большое внимание уделяется сетям, при построении которых используются оптические компоненты - оптические волокна, оптические коммутаторы и т.д. В настоящее время технологии, позволяющие осуществлять пачечную (burst) или пакетную коммутацию в оптических сетях, находятся на стадии НИР и ОКР и еще не поступили на телекоммуникационный рынок, поэтому наибольший практический интерес сейчас представляет анализ производительности оптических сетей с коммутацией каналов. Известно, что в сетях с пачечной пакетной коммутацией трафик имеет самоподобных характер. При изучении таких сетей применяется теория самоподобных процессов [21, 24, 37, 59, 81]. Однако, при построении математических моделей для сетей, в основу которых заложен принцип коммутации каналов, применим и широко используется аппарат марковских процессов, хорошо изученный в рамках ТМО и теории телетрафика. Однако, специфические особенности оптических технологий, например, технологии мультиплексирования с разделением длин волн (Wavelength Division Multiplexing - WDM), ставят перед теорией телетрафика ряд задач, которые не возникали ранее. В частности, в отличие от традиционных сетей с коммутацией каналов, в которых в каждом звене соединение может использовать любой свободный канал, соединение в сетях WDM с маршрутизацией по длине волны может быть установлено только на одной и той же длине волны на всех звеньях маршрута. Таким образом, процессы установления и обслуживания соединений разных классов зависимы, особенно в сетях с многоадресными соединениями. Данные обстоятельства приводят к тому, что состояние системы нельзя полностью описать числом установленных соединений разных классов [84, 85, 86, 87]. Поэтому, при построении математической модели для такой сети необходимо существенно расширять количество параметров, описывающих её детальное состояние. Большая размерность пространства состояний и отсутствие обратимости приводят к необходимости разработки приближенных методов анализа сетей рассматриваемого типа.

Известные сегодня модели ТМО и теории телетрафика, применяемые для анализа производительности и качества обслуживания оптических сетей, разработаны зарубежными специалистами, такими как Birman A., Rouskas G.N., Perros H.G., Mukheijee В., Sivarajan K.N., Somani А. и др., причем в последние годы число подобных публикаций быстро растет. В российской научной литературе пока очень мало публикаций на эту тему.

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

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

Работа имеет следующую структуру. В главе 1 изложены основные принципы функционирования оптических сетей в объеме, достаточном для постановки задачи и физического обоснования предложенной математической модели. В главе 2 предложена математическая модель линейного фрагмента сети WDM (Wavelength Division Multiplexing) с маршрутизацией по длине волны без волновых конвертеров с одно- и многоадресными соединениями. В первом разделе приводятся основные предположения и вводятся необходимые обозначения. Во втором разделе производится построение пространства состояний модели и случайного процесса, описывающего функционирование линейного фрагмента сети WDM с одно- и многоадресными соединениями. Глава 3 посвящена приближенному анализу предложенной модели. В первом разделе рассмотрен и применен метод модификации интенсивностей переходов. С помощью данного метода получен приближенный обратимый марковский процесс (ОМП), имеющий мультипликативное равновесное распределение. Во втором разделе разработан эффективный рекурсивный алгоритм для расчета нормирующей константы равновесного распределения. В третьем разделе предлагается метод для расчета вероятностей блокировок заявок на установление одно- и многоадресных соединений рассматриваемой модели линейного фрагмента сети WDM. В четвертом разделе приведен метод декомпозиции, позволяющий оценивать вероятности блокировок линейных фрагментов с большим числом звеньев.

ЗАКЛЮЧЕНИЕ

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

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

2. В разделе 3.1 впервые метод модификации интенсивностей переходов применен для анализа линейного фрагмента сети WDM с маршрутизацией по длине волны, поддерживающей одноадресные и многоадресные соединения;

3. В разделе 3.2 предложен рекурсивный алгоритм для вычисления нормирующей константы равновесного распределения;

4. В разделе 3.3 предложен алгоритм для расчета вероятностей блокировок линейного фрагмента сети WDM с маршрутизацией по длине волны с одноадресными и многоадресными соединениями.

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

2. Башарин Г. П., Гайдамака Ю. В., Саму шов К Е. Модель функционирования сети с многоадресными соединениями и несколькими источниками информации // Труды межд. конф. по телеком. ИСС-2001. -2001. -С. 90-98.

3. Башарин Г.П., Савочкин Е.А. Анализ пропускной способности линейного фрагмента оптической сети с маршрутизацией по длине волны // Электросвязь. -2005. №5. -С. 48-52.

4. Башарин Г.П., Савочкин Е.А. Анализ многозвеньевого маршрута оптической сети с маршрутизацией по длине волны // Труды 59 Конф. РНТОРЭС. -2004. -Т.1. -С.8-10.

5. Башарин Г.П., Савочкин Е.А., Ефимушкин А.В. Анализ блокировок двухзвеньевого линейного фрагмента оптической сети с одно- и многоадресными соединениями // Труды 60 научной сессии РНТОРЭС. -2005. -Т.1.-С. 3-6.

6. Башарин Г. П., Самуилов К. Е. Обратимые марковские процессы и их применение к анализу сетевых моделей с мультипликативным решением // Труды 55 научной сессии РНТОРЭС. -2000. -Т.1. -С.267.

7. Башарин Г.П., Самуилов К.Е. Современный этап развитиятелетрафика // Информационная математика. -2001. -№1. -С. 153166.

8. Бочаров ПЛ., Печинкин А.В. Теория массового обслуживания:

9. Учебник. -М.: Изд-во РУДН, 1995. -529 с.

10. Башарин Г.П., Харкевич А.Д., Шнепс М.А. Массовое обслуживание втелефонии. -М.: Наука, 1968.

11. Боровков А.А. Ассимптотические методы в ТМО. -М.: Наука, 1980.

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

13. Вербовицкий А.А. Основы проектирования цифровыхоптоэлектронных систем связи. -М.: Радио и связь, 2000.

14. Гнеденко Б.В., Коваленко КН. Введение в теорию массовогообслуживания. -2-е изд. -М.: Наука, ГРФМЛ, 1987.

15. ГринфилдД. Оптические сети. Пер. с англ. -С-П.: ДиаСофтЮП, 2002.

16. ДымарскийЯ.С., КрутиковаН.П., Яновский Г.Т. Управление сетямисвязи: принципы, протоколы, прикладные задачи. -М.: ИТЦ «Мобильные коммуникации», 2003. -384 с.

17. Ершов В.А. Кузнецов Н.А. Мультисервисные телекоммуникационныесети. -М.: Изд-во МГТУ им Н.Э. Баумана, 2003.

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

19. Кох Р., Яновский Г.Г. Эволюция и конвергенция в электросвязи. -М.:1. Радио и связь, 2001.

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

21. Нейман В.И. Структура систем распределения информации. -М.:1. Радио и связь, 1983.

22. Нейман В.И. Самоподобные процессы и их применение в теориителетрафика // Тр. межд. акад. связи. -1999. -Т.9, №1. -С. 11-15.

23. Нейман В.И. Тенденции развития телетрафика (к итогам MKT -18)//1. Электросвязь. -2004. -№9.

24. Ромашкова О.Н. Обработка пакетной нагрузки информационныхсетей. -М.: МИИТ, 2001.-196 с.

25. Рыков В.В. Сети обслуживания прозрачных требований // Автоматикаи телемеханика. -2001. -№5.

26. Рыков В.В., Самуилов К.Е. К анализу вероятностей блокировокресурсов сети с динамическими многоадресными соединениями // Электросвязь. -2000. -№10. -С. 27-30.

27. Савочкин Е.А. Мультипликативное решение для одного классаполностью оптических сетей без волновой конверсии // Труды 59 онф. РНТОРЭС. -2004. -Т.2. -€. 171-173.

28. Самуйлов К. Е. Метод расчета вероятностных характеристик моделисети с многоадресными соединениями // Вестник РУДН (Прикладная и компьютерная математика). -2003. -С. 45-51.

29. Самуйлов К. Е., Савочкин Е. А. Модель сети мультивещания снесколькими уровнями качества предоставляемых услуг // Сб. научн. трудов «Системы телекоммуникаций и моделирование сложных систем». М.: ПАИМС. -2001. -С. 70-76.

30. Самуйлов К Е., Савочкин Е. А. Алгоритм свертки для расчетавероятностных характеристик сети с многоадресными соединениями и несколькими источниками информации // Сб. научн. трудов

31. Системы телекоммуникаций и моделирование сложных систем». -М.: ПАИМС. -2002. -€. 29-37.

32. Самуилов К.Е., Савочкин Е.А. Модель сети мультивещания с потерями

33. Труды 57 Конф. РНТОРЭС. -2002. Т.2. -С. 183-184.

34. Самуилов К. Е., Яркина Н. В. Модель звена мультисервисной сети содноадресными и многоадресными соединениями // Вестник РУДН (Прикладная и компьютерная математика). -2003. -Т.2, №1. -С. 3244.

35. Севастьянов Б. А. Эргодическая теорема для Марковских процессов и