Вероятностный анализ характеристик оптических сетей с маршрутизацией по длине волны
На правах рукописи
Ефимушкин Александр Владимирович ВЕРОЯТНОСТНЫЙ АНАЛИЗ ХАРАКТЕРИСТИК ОПТИЧЕСКИХ СЕТЕЙ С МАРШРУТИЗАЦИЕЙ ПО ДЛИНЕ ВОЛНЫ 05.13.17 – Теоретические основы информатики
Автореферат диссертации на соискание ученой степени кандидата физико-математических наук
Москва – 2011
Работа выполнена на кафедре систем телекоммуникаций Российского университета дружбы народов
Научный консультант:
Заслуженный деятель науки РФ, доктор технических наук, профессор Гелий Павлович Башарин
Официальные оппоненты:
доктор технических наук, профессор Степанов Сергей Николаевич кандидат физико-математических наук Ледовских Татьяна Владимировна
Ведущая организация:
Институт проблем информатики Российской академии наук (ИПИ РАН)
Защита диссертации состоится « 21 » октября 2011 г.
в 16 час. 30 мин. на заседании диссертационного совета Д 212.203.28 в Российском университете дружбы народов по адресу: г. Москва, ул.
Орджоникидзе д. 3, ауд. 110.
С диссертацией можно ознакомиться в Научной библиотеке Российского университета дружбы народов по адресу:
117198, Москва, ул. Миклухо-Маклая, 6. (Отзывы на автореферат просьба направлять по указанному адресу.) Автореферат разослан « » сентября 2011 г.
Ученый секретарь диссертационного совета М.Б. Фомин
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность проблемы Развитие сетей идет со значительным ускорением;
прогнозируется дальнейший рост числа пользователей, повышение требований к качеству услуг и ширине полосы пропускания (ШПП) мультисервисных систем и сетей.
Применение в сетях оптического волокна для передачи информации ставит перед разработчиками множество задач, решение которых невозможно без специальных исследований, разработки математических моделей и численных методов анализа при расчетах показателей эффективности телекоммуникационных сетей. Значительный вклад в развитие данной области внесли российские и зарубежные ученые: Башарин Г.П., Вишневский В.М., Наумов В.А., Нейман В.И., Печинкин А.В., Пшеничников А.П., Самуйлов К.Е., Севастьянов Б.А., Степанов С.Н., Харкевич А.Д., Шоргин С.Я., Яновский Г.Г., Feller W., Bene V.E., Cooper R.B., Iversen V.B., Kelly F.P., Kleinrock L., Neuts M.F., Perros H.G., Ross K.W., Rouskas G.N. и др.
Требования к ШПП быстро растут из-за развития сети Интернет, появления новых приложений и услуг. Сегодня сети, использующие медный кабель, уже не могут удовлетворять возросшим требованиям, поэтому большое внимание уделяется исследованиям в области оптических сетей. Использование оптических компонентов на базе технологии спектрального уплотнения каналов (Wavelength Division Multiplexing, WDM) обеспечивает большую ШПП, малое число ошибок и потерь.
Для современного этапа развития волоконно-оптических систем характерен поиск путей повышения эффективности систем передачи. Технологии пакетной коммутации и групповой (англ. burst) коммутации пакетов в оптических сетях продолжают разрабатываться ведущими исследовательскими центрами и производителями оборудования. Таким образом, практический интерес для оптических сетей представляют задачи анализа производительности, как с коммутацией каналов, так и исследования пакетной и групповой коммутации.
При построении математических моделей для оптических сетей применим и широко используется аппарат марковских процессов, теории массового обслуживания (ТМО) и теории телетрафика. Специфические особенности применения WDM в оптических сетях ставят ряд задач, требующих решения, а именно: разработка методов анализа вероятностно-временных характеристик (ВВХ) функционирования оптических сетей с ограниченной и полной конверсией длин волн в узлах коммутации, моделей коммутатора оптической сети. Таким образом, задача разработки и развития моделей оптических сетей и методов их исследования является актуальной.
Целью диссертационной работы является модификация известных и разработка новых методов для анализа вероятностных характеристик функционирования оптических сетей с маршрутизацией по длине волны и их элементов, включая исследование аналитических моделей и проведение вычислительных экспериментов.
Методы исследования. В работе использованы методы теории вероятностей, теории случайных процессов, ТМО, теории телетрафика.
Научная новизна работы состоит в разработке методов вычисления вероятностных характеристик в оптических сетях. Отличие разработанных моделей и методов расчета их характеристик от известных моделей и методов состоит в следующем:
1) Для оптических сетей, использующих ограниченную конверсию длин волн, проведен математический анализ линейного фрагмента оптической сети с учетом того, что преобразование длины волны в узлах сети не является изменением круговой симметрии. В отличие от известных результатов получено доказательство применимости данного метода для расчета вероятностей блокировок маршрута оптической сети.
2) Разработана модель для анализа вероятностей блокировок звеньев сети, в которой в отличие от известных моделей учитывается оптический буферный накопитель (БН) в устройстве передачи. Разработан рекуррентный алгоритм вычисления стационарных вероятностей для системы (W + 1)( r + 1) + уравнений глобального баланса, что дает возможность более эффективно проводить расчеты характеристик модели.
3) Проведен анализ показателей эффективности маршрутов и сети с произвольной топологией как без возможности преобразования длин волн в узле, так и с преобразованием длин волн на основе разработанной модели звена сети с БН. Получены рекуррентные выражения для вероятности блокировки маршрута сети.
4) Разработана мультисервисная модель коммутатора оптической сети с учетом времени выгрузки информации. Получена формула для вероятности блокировки коммутатора оптической сети. Отличие разработанной модели и методов расчета ее характеристик заключается в учете сценария поведения источников трафика в оптической сети и требований к качеству обслуживания.
Практическая ценность работы. Аналитические методы и вычислительные алгоритмы, полученные в диссертации, предназначены для анализа характеристик качества обслуживания в оптических сетях, использующих технологию мультиплексирования с разделением длин волн и маршрутизацией по длине волны. Результаты могут использоваться при анализе фрагментов оптических сетей и могут быть обобщены для изучения оптических сетей WDM с произвольной топологией. Результаты исследований могут использоваться в учебном процессе на кафедре систем телекоммуникаций РУДН для студентов, обучающихся по направлениям «Прикладная математика и информатика».
Результаты работы использованы в рамках НИР № 16/06-22 от 27.04.2006 г.
«Методика расчета качественных показателей и коэффициента готовности отказоустойчивых структур ВОЛС ОАО «Ростелеком»» ФГУП ЦНИИС и НИР № 128/10-22 от 19.03.2010 г. «Разработка методик эксплуатационного контроля показателей и параметров качества функционирования сетей ОАО «Ростелеком»» ФГУП ЦНИИС.
Достоверность научных результатов диссертационной работы обоснована строгими математическими доказательствами. Достоверность подтверждается вычислительными экспериментами, проведенными с использованием близких к реальным исходных данных.
Апробация работы. Основные результаты, изложенные в диссертации, докладывались на:
XXXVII и XXXVIII научных конференциях факультета физико математических и естественных наук Российского университета дружбы народов (Москва, 2001, 2002);
Научных семинарах секции «Моделирование сетей связи, информационных систем и процессов» РНТОРЭС им. А.С. Попова (Москва, 2003, 2004, 2005);
Семинарах кафедры систем телекоммуникаций Российского университета дружбы народов (Москва, 2004-2007).
Отраслевых научно-технических конференциях «Технологии информационного общества» (Москва, 2007, 2008, 2010, 2011).
Публикации. По теме диссертации опубликовано 9 работ, из них работы [6,8,9] опубликованы в ведущих рецензируемых научных журналах, и содержат выносимые на защиту результаты.
В работах, выполненных в соавторстве, соискателю принадлежит: в [1] – приближенный метод и рекуррентный алгоритм для расчета вероятностей блокировок на маршруте волоконно-оптической сети;
в [2] – приближенный метод расчета вероятностей блокировок маршрутов в многоволоконных оптических сетях;
в [3] – модель расчета вероятностей блокировок функционирования оптоволоконной сети;
в [4] – численный анализ блокировок двухзвеньевого линейного фрагмента сети с одно- и многоадресными соединениями;
в [6] – модифицированная модель Энгсета коммутатора оптической сети с учетом времени освобождения каналов от информации, численные примеры;
в [9] – модель коммутатора оптической сети при предоставлении услуг различного качества с учетом времени освобождения каналов. Все результаты, выносимые на защиту, получены автором лично.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы из 115 наименований, приложения.
Диссертация содержит 115 страниц текста, 33 рисунка.
СОДЕРЖАНИЕ РАБОТЫ
Введение посвящено обоснованию актуальности темы диссертации, приведен обзор публикаций по теме, сформулирована цель исследований, кратко изложены содержание и основные результаты диссертации по главам, охарактеризованы их научная новизна и практическая значимость.
В первой главе исследована вероятностная модель блокировок волоконно оптической сети с ограниченной конверсией длин волн в узлах коммутации.
Приняты следующие допущения: в каждый узел сети поступает пуассоновский поток запросов (заявок) с интенсивностью a на установление соединений передачи данных;
время удержания заявки распределено экспоненциально с параметром µ = 1 ;
заявка, которая не может быть маршрутизирована в сети, блокируется и теряется, не оказывая влияния на функционирование сети;
число длин волн любого звена сети равно W ;
длины волн назначаются случайно поступающим в узел сети заявкам из всех доступных длин волн;
рассматриваются соединения «точка-точка».
Предположим также, что преобразование длины волны в узле сети не является изменением круговой симметрии. В известных работах данное допущение определяло круговую замкнутость диапазона длин волн и возможность ограниченной конверсии длин волн без учета границ диапазона.
Входящая длина волна i может быть преобразована в следующие выходящие длины волн: 1,..., i,..., i + d, при i d ;
i d,..., i,..., i + d, при d i W d и i d,..., i,..., W при i W d, где d показатель конверсии (рис.1).
Пусть R = (1,2,..., N ) - маршрут, состоящий из N звеньев множества звеньев J = {,2,..., J } сети, последовательно соединяющих узлы сети, и X i, где i = 1,..., N, случайная величина (СВ), определяющая число свободных длин волн на i -м звене, а X R – СВ, определяющая число вариантов выбора свободных длин волн на всем маршруте. Пусть p m ( x1, x2,..., x N ) вероятность того, что существует m вариантов выбора свободных длин волн на маршруте R, если x1, x2,..., x N – числа свободных длин волн на звеньях 1,2,..., N соответственно.
U V 1 2...
...
W- W W Звено i Звено j Рис.1. Возможное преобразование длин волн в узле при d = Обозначая w := ( x1, x2,..., x N ), получим pm ( w) = P (X R = m X 1 = x1, X 2 = x2,..., X N = x N ). (1) Для R = (i, j ) вероятность p m ( x, y ) = P ( X R = m X i = x, X j = y ). (2) Пусть Xi U, X j V – множества свободных из U и V длин волн на звеньях i и j соответственно, когда Xi = x, X j = y и U = V = W. Пусть Г( z ) – множество доступных по конверсии для z U длин волн из V, будем называть Г( z ) множеством соседей для z. Для Г( Xi ) := U Г( z ) доказано следующее zXi утверждение.
Лемма. Для любого множества Xi U справедливо неравенство min(W, Xi + d ) Г( Xi ) min(W, (2d + 1) Xi ). (3) В разделе 1.3 доказывается основное утверждение 1 и выводится рекуррентный алгоритм вычисления pm (w). Для двухзвеньевого маршрута R = (i, j ) справедливо следующее Утверждение 1. Вероятность наличия m свободных длин волн на маршруте R = (i, j ), при условии наличия свободных длин волн вычисляется по формуле l W l m y m pm ( x, y ) = P Г( Xi ) = l Xi = x, X j = y, l ( ) (4) W l = l y где l1 = min Г( Xi ), l2 = max Г( Xi ).
Xi U Xi U Рассмотрим теперь общий случай маршрута из N 3 звеньев. Он сводится к анализу уже рассмотренного случая N = 2.
В соответствии с формулой полной вероятности имеет место следующее рекуррентное соотношение, где p m (k, x N ) определяется из утверждения 1:
x N p m ( x1,..., x N 1, x N ) = p k ( x1,..., x N 1 ) p m (k, x N ). (5) k =m В разделе 1.4 рассматривается фиксированная маршрутизация по длине волны для сети с произвольной топологией, множеством звеньев J и количеством W возможных длин волн на каждом звене, приводится алгоритм вычисления вероятности блокировки сети.
На маршрут R поступает пуассоновский поток вызовов с интенсивностью a R. Время обслуживания вызова принимается экспоненциальным с параметром µ = 1. Пусть q j (w ) := P (X j = w ), w = 0, W. (6) Введем следующее предположение. Пусть СВ взаимно X 1,..., X J J независимы, так что q(w ) = q j (w j ), w = (w1, w2,..., wJ ).
j = При существовании w свободных длин волн на звене j, время до поступления нового вызова на звено j, распределено экспоненциально с параметром j (w), т.е. это суммарная интенсивность поступления нового вызова на звено j со всех маршрутов, содержащих звено j :
0, w = 0, j (w ) = ( ) a R P X R 0 X j = w ;
w = 1,W. (7) R: jR При рассмотрении одного звена, переходы из состояния в состояние можно рассматривать как процесс размножения и гибели. Запишем систему уравнений локального баланса (СУЛБ):
j (w )q j (w ) = q j (w 1)(W w + 1)µ, w = 1,W. (8) Для R = (i, j ) условная вероятность наличия свободных длин волн равна ( ) ( )( ) W P X R 0 X j = w = P X i = l X j = w P X R 0 X j = w, X i = l = l =. (9) W = qi (l )(1 p0 (w, l )) l = Справедливо следующее Утверждение 2. Вероятность блокировки маршрута R вычисляется по формуле qi (0 ), R = (i ), если R = P( X R = 0) = (10) WW l0w0 qi (l )q j (w ) p0 (w, l ), если R = (i, j ).
= = В сделанных предположениях и с учетом утверждения 2 получен алгоритм для расчета вероятности блокировки сети.
Во второй главе разрабатывается приближенный метод вычисления вероятностей блокировок оптоволоконной сети.
Предлагается аналитическая модель для нахождения вероятности блокировки маршрута сети, как без возможности преобразования длин волн в узле, так и с полным преобразованием длин волн. В устройстве передачи перед звеном имеется оптический БН, обеспечивающий задержку вызова в течение фиксированного времени. В модели, в целях упрощения анализа предполагается не детерминированное, а экспоненциально распределенное время пребывания в буфере со средним, равным указанному фиксированному значению. Таким образом, БН моделируется дополнительной группой приборов, называемой БН для упрощения. Предполагается также, что нагрузки на звенья сети независимы.
Интенсивность поступающего пуассоновского потока на звено i есть Li, а время обслуживания распределено по экспоненциальному закону с параметром µ, тогда нагрузка на звено i равна i = Li / µ, i = 1,J. В случае занятости всех длин волн звена вызов буферизуется в БН конечной емкости r, причем время пребывания вызова в БН распределено экспоненциально с параметром µ 0. По окончании этого периода вызов занимает свободную длину волны, при ее наличии, либо блокируется и теряется не оказывая влияния на поступающий поток вызовов (рис. 2).
Li (1 pWi ), • ) ( } r...
µ0 1 qpWi ),q ( Li pW), • (i q =...
r µ0 qpWi ),q ( Li pWi ),r ( q = Рис.2. СМО Пусть X (i ) – СВ, определяющая число занятых длин волн на i-м звене, а Y (i ) – СВ числа вызовов в БН. Функционирование звена описывается двумерным марковским процессом (МП) ( X (i ) (t ),Y ( i ) (t )), t 0 с пространством состояний { } X = (k, q) : k = 0,W, q = 0, r. Стационарное распределение вероятностей введенного МП p k( i, )q := P { X (i) (i) = k,Y = q }, k = 0, W, q = 0, r, существует и находится из следующей системы уравнений глобального баланса (СУГБ):
p k i, )q (u ( r q ) L i + u (W k ) u ( q r + 1) L i + k µ + q µ 0 ) = u ( k ) p k i)1, q L i + ( ( + u (W k ) p k i+)1, q ( k + 1) µ + u ( k ) u ( r q ) p k i)1, q + 1 ( q + 1) µ 0 + ( ( (11) + u ( k + 1 W ) u ( r q ) p k i, )q + 1 ( q + 1) µ 0 + u ( k + 1 W ) u ( q ) p k i, )q 1 L i, ( ( 0, x 0, k = 0,W, q = 0, r, u( x ) = Здесь и далее в моделях для нахождения 1, x 0.
единственного решения СУГБ используется условие нормировки.
Данная система содержит (W + 1 )( r + 1 ) + 1 уравнений, для которой в диссертационной работе разработан рекуррентный алгоритм вычисления вероятностей p k i, )q, (k, q) X.
( Алгоритм вычисления стационарных вероятностей для системы.
(1, q) X, q = 0, r Шаг 1. Вероятности состояний выражаются в виде (L i + q µ 0 ) p 0 i, q.
() () p 1,iq = µ Шаг 2. Для всех состояний (k, r ) X, k = 0,W p k i, )r выражаются через p 0 i, r.
( () p k i, )r 1, k = 0, W ( (k, r 1) X, k = 0,W Шаг 3. Для всех состояний () () выражаются через p 0 i, r 1 и p 0 i, r.
Шаг 4. Для граничного состояния (W, r 1) p Wi ), r 1 выражается через p 0 i, r.
( () Шаг 5. Для всех состояний (k, r 1) X, k = 0,W подставляем в уравнения () () выражение p 0 i, r 1 через p 0 i, r.
Шаг 6. Для всех состояний (k, q) X, k = 0,W при q = r 2, q = r 3, …, q = повторяем шаги 3-5.
() p 0 i, r.
Шаг 7. Из нормировочного условия находится вероятность Вероятности остальных состояний находятся из полученных выражений на шагах 1-6.
Введем следующие показатели эффективности системы: вероятность занятости всех длин волн звена i равна p Wi ), • ;
вероятность буферизации вызова ( r p (i ) вычисляется по формуле ;
вероятность потери вызова вследствие W,q q = занятости всех длин волн звена и БН равна p Wi ), r.
( Интенсивность потери вызова после пребывания в БН вычисляется по r формуле µ0 qpWi ),q. Совокупная интенсивность потери вызова на звене ( i ) ( q = r равна ( i ) = Li pWi ), r + µ0 qpWi ), q.
( ( q = Вероятность потери вызова на звене i совпадает с долей совокупной интенсивности потери вызова от интенсивности поступающего потока вызовов:
(i ) = (i ) / Li.
pki,)q, k = 0,W, q = 0, r, ( Распределение позволяет найти маргинальные вероятности занятости k длин волн на звене pki ) := pki,), k = 0,W.
( ( • Пусть маршрут RJ. Интенсивность определяется объединением Li вкладов от всех предложенных потоков на маршруты, содержащие звено i.
Проведем анализ для маршрута из большего числа звеньев. Пусть qk1,...,n ) ( вероятность наличия k занятых длин волн на первых n звеньях маршрута.
Для маршрута R = {a, b} из двух звеньев a и b обозначим через na и nb количество соответствующих свободных длин волн. Вероятность P ( f | na, nb ) того, что f длин волн свободны на звеньях a и b, эквивалентна вероятности наличия одних и тех же свободных длин волн, как на звене a, так и на звене b, и имеет вид:
na W na f n f b, n + n W f min( n, n ), a b a b W P ( f | na, nb ) = (12) n b в остальных случаях.
0, Здесь na + nb f W, 0 na, nb W.
По формуле условной вероятности распределение занятых длин волн на маршруте из двух звеньев имеет вид WW qW, )f = P ( f | i, j ) pi(1) p (j2 ).
(1 (13) i =0 j = Пусть (n,W ) и (n,W ) обозначают соответственно вероятности блокировки маршрута R, состоящего из | R |=n звеньев, содержащих по W длин волн без конверсии длин волн и с полной конверсией длин волн в узлах.
Вероятность блокировки маршрута из двух звеньев без конверсии длин волн в узлах определяется как ( 2, W ) = qW,2 ).
( Можно распространить описанный выше анализ на нахождение вероятности блокировки вызова, поступающего на маршрут из n звеньев, n 1.
Будем использовать рекуррентную формулу, определяющую распределение занятых длин волн на маршруте из n звеньев через распределение занятых длин волн на маршруте из n 1 звена. Для n WW qW,...,n ) = P (W f | i, j )qi(1,...,n 1) p (jn ), ( (14) f i =0 j = и ( n, W ) = qW,...,n ).
( (15) W Если в сети возможно преобразование длин волн, то ограничение на использование одной и той же длины волны для установления соединения отпадает. Блокировка вызова происходит при данных условиях только в отсутствии свободных длин волн на каком-либо из звеньев маршрута.
Вероятность блокировки для запросов соединений, поступающих на маршрут из n звеньев равна n (n,W ) = 1 (1 pWi ) ).
( (16) i = Если средняя загрузка звеньев одинакова, то pWi ) =: pW и вероятность ( блокировки может быть выражена в виде (n,W ) = 1 (1 pW ) n. (17) В разделе 2.5 проводится оценка вероятности блокировки сети. Пусть AR интенсивность предложенной нагрузки на маршрут R, R (n,W ) - вероятность блокировки маршрута R длины n звеньев.
Хорошей аппроксимацией интенсивности предложенной нагрузки, на звене i с возможностью преобразования длин волн в сети, является следующая функция:
1 R ( n,W ) Li = I i ( R ) AR, (18) 1i R 0, i R, где I i ( R) =.
1, i R.
Результатом разработанного приближенного метода и модели, учитывающей оптический БН, является возможность производить приближенный расчет вероятностей блокировок оптических сетей в сделанных выше предположениях по следующей формуле:
R ( n,W )AR RR = (19).
AR RR Для того, чтобы осуществить анализ сети без конверсии длин волн, сделаем допущение о пуассоновском потоке поступления вызовов. Из формулы (18) можно получить интенсивность предложенной нагрузки для сети без преобразования длин волн в узлах сети. При этом используем формулу (16) для получения R (n,W ), если конверсия длин волн в сети возможна, и формулы (14) и (17) для R ( n,W ), если не возможна.
Вероятности блокировки звеньев сети могут быть получены из решения СУГБ (12). Можно показать, что эта система уравнений с нормировочным условием имеет единственное решение. Для решения системы нелинейных уравнений и нахождения вероятности блокировки, используется итерационная процедура.
В третьей главе исследованы модели работы коммутатора оптической сети с коммутацией пакетов.
В разделе 3.1 описываются алгоритмы функционирования коммутатора оптической сети с коммутацией пакетов.
В разделе 3.2. исследуется система массового обслуживания (СМО) для коммутатора оптической сети в виде модификации модели Энгсета, осуществляется вывод и решение системы уравнений равновесия, проводится численный сравнительный анализ ВВХ.
В модели будем называть пакет заявкой, входную длину волны коммутатора – источником заявок, а выходную – линией. Предложенная нагрузка – независимый пуассоновский поток заявок с параметром от каждого из N источников. Будем учитывать время освобождения входных каналов передачи данных от информации при работе коммутатора оптической сети.
Пакет данных, поступивший с входной длины волны в коммутатор в момент занятости требуемой выходной длины волны, будет выгружаться из входного канала передачи данных, а входная длина волны будет находиться в состоянии "2" выгрузки и только после ее окончания перейдет в состояние "0".
Каждый из N независимых источников в свободном состоянии "0" может с интенсивностью сгенерировать заявку, которая мгновенно займет одну из свободных линий, если они имеются, а источник перейдет в состояние "1" - занят, либо с вероятностью pV занятости всех V линий предложенная источником и заблокированная заявка будет выгружаться из него, а сам источник перейдет в состояние "2". Примем, что длительности пребывания источника в состоянии "1" и "2" не зависят от состояния СМО и описываются экспоненциальным распределением с параметрами µ1 и µ 2, соответственно.
Функционирование СМО описывается двумерным марковским процессом { } X (t ) = (xij (t ) ) : i, j J (1), t 0 с двумя структурными параметрами ( N,V ) и тремя нагрузочными параметрами (, µ1, µ 2 ).
J (1) Здесь пространство состояний рассматриваемого марковского процесса:
{ } J (1) = (i, j ) : i = 0,V ;
j = 0, N V, (20) где i - число источников в состоянии "1", j - число источников в состоянии выгрузки "2". Количество состояний равно J (1) = (V + 1)( N V + 1).
Поскольку исследуемая СМО – система с явными потерями, то при любых структурных и нагрузочных параметрах существует равновесное распределение {p, i, j J (1) }. Обозначая функцию индикатор i, j 1, если событие А произошло 1( А) =, СУГБ можно записать в виде:
0, в противном случае [iµ1 + jµ2 + ( N i j ) ]pi, j = ( N i j + 1)pi 1, j u(i ) + + ( N V j + 1)pV, j 11(i = V )u( j ) + (i + 1) µ1 pi +1, j u(V i ) + (21) ( j + 1) µ2 pi, j +1u( N V j ), (i, j ) J (1).
Аналогично модели Энгсета вероятность блокировки по времени в данной модели есть:
N V = pV, j =: pV,•. (22) j = Вероятность блокировки по вызовам равна отношению среднего числа заблокированных заявок к среднему числу поступивших заявок за некоторый интервал времени T :
N V pi, j (N V j )T j = В =. (23) V N V pi, j (N i j )T i =0 j = В разделе 3.3. исследуется модель коммутатора оптической сети при предоставлении услуг различного качества с учетом времени освобождения каналов от информации. В введенных предположениях для раздела 3.2 выделим два класса услуг: класс 1: высший приоритет, соответствующий передаче данных в реальном времени;
класс 2: низший приоритет, не требующий передачи данных в реальном времени.
Пусть для услуг классов 1 и 2 выделен пул длин волн V1, а для услуг класса 1 выделен пул V2, причем V1 + V2 = V.
Предлагаемая мультисервисная модель с N источниками, V выходными длинами волн, N V виртуальными местами (заблокированные источники) для выгрузки получивших отказ заявок и выделенным общедоступным пулом длин волн V1 является СМО, которую, будем обозначать M M ;
M V,V1 0. Диаграмма N, 1, 2 µ1 ;
µ интенсивностей переходов для СМО изображена на рис. 3. В случае занятости V приборов, и при N V выгружающих источниках процесс поступления заявок с низшим приоритетом прекращается, поскольку они могут помешать поступлению приоритетных заявок.
Рис.3. Диаграмма интенсивностей переходов между состояниями источника Функционирование СМО описывается двумерным ступенчатым { } марковским процессом X(t ) = (xij (t ) ) : i, j J ( 2), t 0, с тремя структурными (N,V,V1 ) и четырьмя нагрузочными – ( 1, 2, µ1, µ2 ). Здесь, параметрами { } J ( 2) = (i, j ) : i = 0,V ;
j = 0, N V - пространство состояний рассматриваемого J ( 2 ) = (V + 1)( N V + 1) марковского процесса, содержащее состояний.
Соответствующий граф интенсивностей переходов представлен на рис.4, где. = 1 + 2. Отметим, что поскольку не все переходы являются парными, то ( 2) распределение марковского процесса X(t ) в пространстве J не является мультипликативным.
Рис.4. Граф интенсивностей переходов Используя граф интенсивностей переходов на рис.4, СУГБ можно записать следующим образом:
pi, j [iµ1 + jµ 2 + ( N i j ).u(V1 i ) + ( N i j ) 1 (1 u(V1 i )) + + ( N i j ) 2 (1 u(V1 i ))u(( N V ) j )] = pi 1, j [( N i j + 1) 1 (1 u(V1 + 1 i )) + (24) + ( N i j + 1).u(V1 + 1 i )]u(i ) + pi +1, j (i + 1) µ1u(V i ) + + pi, j 1 [( N i j + 1) 2 (1 u(V1 i )) + ( N i j + 1) 1 (1 u(V i ))]u( j ) + + pi, j +1 ( j + 1) µ 2 u( N V j ).
Основными показателями эффективности, исследуемыми в главе 3, являются вероятности блокировок приоритетного и неприоритетного классов заявок в модели коммутатора оптической сети с учетом времени освобождения входных каналов передачи данных от информации.
Эти вероятности соответствуют блокировкам запросов передачи трафика данных, требовательного к ресурсам сети, и трафика, некритичного к задержкам и потерям пакетов (англ. best-effort).
Вероятность блокировки по времени для заявок класса 1 вычисляется по N V p формуле 1 = E1 (V, N ) = а для заявок класса 2 – по формуле := pV, V, j j = V N V 2= E2 (V, N ) = pi, j.
i =V1 j = В разделе 3.5 проведен численный анализ для коммутатора оптической сети с характеристиками, соответствующими современным коммутаторам WDM. В качестве примера на рис.5 представлен график зависимости вероятностей 1 и 2 от N ( V = 88, V1 = 30, µ1 = 1, µ 2 = 0,5, 1 = 0,3, 2 = 0,2 ).
Рис.5. Вероятности блокировок заявок класса 1 и класса 2 от N В данном случае 2 быстро возрастает, а 1 практически не растет.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ 1. Построена модель блокировок для оптических сетей, использующих ограниченную конверсию длин волн в узле, с учетом того, что преобразование длины волны в узле сети не является изменением круговой симметрии.
Получено доказательство применимости данного метода для расчета вероятностей блокировок маршрута оптической сети.
2. Разработана модель для нахождения вероятностей блокировок звеньев сети, в которой в отличие от известных моделей учитывается оптический буферный накопитель в устройстве передачи. Разработан рекуррентный алгоритм вычисления стационарных вероятностей для системы (W + 1)( r + 1) + уравнений глобального баланса, что дает возможность более эффективно проводить расчеты характеристик модели.
3. Проведен анализ показателей эффективности маршрутов и сети с произвольной топологией как без возможности преобразования длин волн в узле, так и с преобразованием длин волн на основе разработанной модели звена сети с БН. Получены рекуррентные выражения для расчета вероятности блокировки маршрута сети и проведен численный эксперимент, который подтвердил незначительные отличия значений вероятности блокировки сети при числе длин волн более 16 для рассматриваемых нагрузочных параметров.
4. Разработана модель для анализа вероятностей блокировок коммутатора оптической сети при предоставлении услуг различного качества с учетом времени выгрузки информации. Получена формула для вероятности блокировки коммутатора оптической сети, и проведен численный эксперимент, который показал значительное повышение вероятности блокировки заявок класса 2 и незначительное повышение вероятности блокировки заявок класса 1 при увеличении числа источников нагрузки.
Основные результаты диссертационной работы отражены в следующих опубликованных работах:
1. Башарин Г.П., Ефимушкин А.В. Вероятностная модель блокировок в волоконно-оптических сетях с ограниченной конверсией в узлах коммутации // В сб.: Труды XXXVII Всероссийской научной конференции по проблемам математики и информатики. – М.: РУДН, 2001. – С.5–14.
2. Башарин Г.П., Ефимушкин А.В. Вероятностный анализ пропускной способности в многоволоконных оптических сетях // Труды XXXVIII Всероссийской научной конференции по проблемам математики и информатики.
– М.: РУДН, 2002. – С.13–20.
3. Башарин Г. П., Савочкин Е. А., Ефимушкин А. В. Приближенный метод вычисления вероятностей блокировок оптоволоконной сети // Труды XXXIX Всероссийской научной конференции по проблемам математики и информатики.
– М.: РУДН, 2003. – С.45.
4. Башарин Г.П., Савочкин Е.А., Ефимушкин А.В. // Анализ блокировок двухзвеньевого линейного фрагмента оптической сети с одно-многоадресными соединениями // В сб.: Труды 60-й Конференции РНТОРЭС, – М.: РНТОРЭС. – 2005. – С.3–6.
5. Ефимушкин А.В. Анализ вероятностей блокировок коммутатора оптической сети при предоставлении различного качества услуг связи // Технологии информационного общества: Тезисы докладов московской отраслевой научно-технической конференции, 23–25 апреля 2007 г. – М.:
Инсвязьиздат. – 2007. – С.10.
6. Башарин Г.П., Ефимушкин А.В. Анализ блокировок коммутатора оптической сети с коммутацией пакетов // М.: Электросвязь, – 2007. – № 8. – C.8–11.
7. Ефимушкин А.В. Подходы к анализу вероятностно-временных характеристик коммутатора оптической сети с коммутацией пакетов // Труды Московского технического университета связи и информатики Т.1. – М.: ИД Медиа Паблишер, – 2008. – С.118–124.
8. Ефимушкин А. В. Численный анализ блокировок оптической сети с маршрутизацией по длине волны // М.: T-Comm, – 2010. – № 7. – С.119–122.
9. Башарин Г.П., Ефимушкин А.В. Анализ вероятностей блокировок коммутатора оптической сети для услуг различного качества с механизмом освобождения каналов от информации // М.: Электросвязь. – 2011. – № 2. – С.48–51.
Ефимушкин Александр Владимирович (Россия) Вероятностный анализ характеристик оптических сетей с маршрутизацией по длине волны В диссертационной работе исследуются математические модели оптических сетей WDM с маршрутизацией по длине волны. Получены основные ВВХ функционирования оптических сетей и оптического коммутатора.
Разработана математическая модель узла сети с ограниченной конверсией длин волн с одноадресными соединениями с учетом того, что преобразование длины волны в узлах сети не является изменением круговой симметрии, в виде системы массового обслуживания с явными потерями.
Предложен эффективный рекуррентный алгоритм для расчета вероятностных характеристик модели оптической сети с полной конверсией длин волн и без конверсии длин волн, снижающий вычислительную сложность расчета вероятностей блокировок соединений.
Разработана математическая модель оптического коммутатора с учетом времени выгрузки информации в виде мультисервисной системы массового обслуживания с явными потерями. Выполнен сравнительный численный анализ поведения некоторых ВВХ.
Для приближенного вычисления вероятностей блокировок заявок моделей предложены эффективные аналитические и алгоритмические методы анализа.
Alexander Efimushkin (Russia) Probabilistic analysis of characteristics of wavelength-routed optical networks In this paper, the mathematical model of WDM wavelength-routed optical network is introduced. Main probability-time characteristics of optical network and optical switch operation are obtained.
The network node model with limited wavelength conversion is developed with not round symmetric wavelength conversion as a queuing system with point to point calls.
The effective recurrent algorithm to compute the optical network probabilistic characteristics with and without wavelength conversion of the model is developed.
The model of an optical switch with time of discharge information is constructed as a multiservice loss queuing system. The comparative numerical analysis of behavior of some probability-time characteristics is made.
Effective analytical and algorithmic approaches for approximately evaluating blocking probabilities of calls are presented.
Подписано в печать 16.09.2011г.
Заказ № Тираж: 100экз.
Копицентр «ЧЕРТЕЖ.ру» ИНН 107023, Москва, ул.Б.Семеновская 11, стр. (495) 542- www.chertez.ru