Содержание к диссертации
Введение
Глава 1. Принципы функционирования сетей WDM 12
1.1 Оптические технологии передачи данных 12
1.2 Мультиплексирование с разделением длин волн 12
1.3. Архитектуры оптических сетей WDM. 13
1.3.1 Широковещательные сети 14
1.3.2 Сети с маршрутизацией подлине волны 16
1.4 Конверсия длин волн 18
1.5 Задача маршрутизации и назначения длин волн 21
1.6 Одноадресные и многоадресные соединения 24
1.7 Задачи теории телетрафика в сетях WDM с маршрутизацией по длине волны28
1.7.1 Построение математической модели сети 28
1.7.2 Анализ вероятностей блокировок линейного фрагмента сети с одноадресными соединениями 29
1.7.3 Анализ вероятностей блокировок линейного фрагмента сети с одно- и многоадресными соединениями 30
Глава 2. Математичекая модель линейного фрагмента с одно- и многоадресными соединениями 32
2.1 Предположения и обозначения 32
2.2 Пространство состояний и равновесное распределение 36
2.3 Численные результаты 42
Глава 3. Приближенный анализ линейного фрагмента с одно- и многоадресными соединениями 51
3.1 Метод модификации интенсивностей переходов 51
3.2 Вычисление нормирующей константы 56
3.3 Расчет вероятностей блокировок 58
3.4 Метод декомпозиции 62
3.5 Численные результаты 66
Заключение 71
Литература 72
- Мультиплексирование с разделением длин волн
- Построение математической модели сети
- Пространство состояний и равновесное распределение
- Вычисление нормирующей константы
Введение к работе
Первые задачи теории телетрафика состояли в изучении телефонных и телеграфных сетей. Начало теории телетрафика восходит к работам датского математика А. К. Эрланга, исследовавшего статистические характеристики работы телефонных сетей и опубликовавшего в 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., Mukherjee В., Sivarajan K.N., Somani А. и др., причем в последние годы число подобных публикаций быстро растет. В российской научной литературе пока очень мало публикаций на эту тему.
Построение и анализ математических моделей как отдельных фрагментов оптических сетей, так и сетей в целом, необходим не только производителям оборудования, но даже в большей степени операторам сетей, для эффективного управления ресурсами и обеспечения качества услуг.
Таким образом, математический анализ оптических сетей является весьма актуальной задачей современной индустрии связи. Целью данной диссертационной работы является разработка математической модели оптической сети, разработка подходов к её анализу и создание эффективных алгоритмов вычисления её ВВХ.
Работа имеет следующую структуру. В главе I изложены основные принципы функционирования оптических сетей в объеме, достаточном для постановки задачи и физического обоснования предложенной математической модели. В главе 2 предложена математическая модель линейного фрагмента сети WDM (Wavelength Division Multiplexing) с маршрутизацией по длине волны без волновых конвертеров с одно- и многоадресными соединениями. В первом разделе приводятся основные предположения и вводятся необходимые обозначения. Во втором разделе производится построение пространства состояний модели и случайного процесса, описывающего функционирование линейного фрагмента сети WDM с одно- и многоадресными соединениями. Глава 3 посвящена приближенному анализу предложенной модели. В первом разделе рассмотрен и применен метод модификации интенсивностей переходов. С помощью данного метода получен приближенный обратимый марковский процесс (ОМП), имеющий мультипликативное равновесное распределение. Во втором разделе разработан эффективный рекурсивный алгоритм для расчета нормирующей константы равновесного распределения. В третьем разделе предлагается метод для расчета вероятностей блокировок заявок на установление одно- и многоадресных соединений рассматриваемой модели линейного фрагмента сети WDM. В четвертом разделе приведен метод декомпозиции, позволяющий оценивать вероятности блокировок линейных фрагментов с большим числом звеньев.
Мультиплексирование с разделением длин волн
Возможности оптических волокон по передаче данных ограничиваются быстродействием электронного оборудования (несколько гигабит в секунду). Поэтому в настоящее время широкое развитие получила технология мультиплексирования с разделением длин волн (wavelength division multiplexing - WDM). При использовании технологии WDM оптический диапазон, использующийся для передачи (обычно это диапазон длин волн вблизи 1500 нм, где затухание минимально), разбивается на некоторое число неперекрывающихся каналов (или длин волн), каждый из которых функционирует на пиковой электронной скорости. Поступающие сигналы на разных длинах волн мультиплексируются, передаются по оптическому волокну и демультиплексируются на выходе (см. Рис. 1 [74]). Существенным преимуществом WDM является возможность значительно увеличить доступную ширину полосы пропускания каналов без необходимости прокладывания дополнительных кабелей и связанных с этим финансовых затрат.
В зависимости от используемой технологии передачи данных можно выделить три «поколения» сетей [49, 61, 71, 82]. Сети первого поколения используют медный кабель или радио. И передача данных, и коммутация выполняются в таких сетях с использованием «электронных» технологий, без использования оптики. Примером такой сети может служить Ethernet. Сети второго поколения используют оптические волокна в качестве каналов передачи данных, а в узлах сети установлено электронное оборудование. Развертывание таких сетей позволило получить качественный выигрыш за счет более высокой пропускной способности, более низкого уровня ошибок, лучшей надежности и других свойств оптоволокна. Примером такой сети может служить FDDI (Fiber Distributed Data Interface - распределенный интерфейс передачи данных по волоконно-оптическим каналам, стандарт ANSI, США). Узким местом таких сетей становится коммутационное электронное оборудование, установленное в узлах сети. Сети третьего поколения используют технологию WDM, а также технологии оптической коммутации в узлах сети. Это позволяет более эффективно использовать ширину полосы пропускания (ШГШ) оптического волокна и исключить оптоэлектронные преобразования в узлах сети соответственно. Использование оптических технологий не только в качестве каналов передачи данных, но и в узлах коммутации позволяет перейти к построению и использованию так называемых «полностью оптических сетей» (all-optical network - AON). Такие сети характеризуются тем, что информация в них проходит по оптической среде на протяжении всего пути за исключением оконечных пунктов.
Можно выделить следующие классы оптических сетей, использующих технологию WDM: широковещательные сети (broadcast-and-select networks) и сети с маршрутизацией по длине волны (wavelength routing networks).
Центральным звеном широковещательных сетей [68, 74, 82] является пассивный ответвитель (passive star coupler), основная функция которого состоит в «упаковке» световых каналов в оптическое волокно и их «извлечении» из него. Все узлы сети подключены к ответвителю посредством оптических волокон. Каждый узел сети оборудован одним или несколькими передающими устройствами (transmitter) и одним или несколькими принимающими устройствами (receivers), которые в свою очередь могут оперировать либо только на одной фиксированной длине волны (fixeduned transmitter / receiver), либо может настраиваться на несколько длин волн (tunable transmitter I receiver). Различные узлы сети передают информацию узлам на разных длинах волн одновременно. Ответвитель «упаковывает» все эти сообщение в одно и передает его всем узлам сети. Для получения сообщения от конкретного узла-отправителя узел - получатель настраивает свои принимающие устройства на необходимую длину волны. В зависимости от возможностей принимающих и передающих устройств по настройке на работу с одной или несколькими длинами волн может быть получены различные логические топологии сети. Например, если каждый узел сети оборудован одним передающим и одним приемным устройством, которые настроены только на одну длину волны, то логическая топология такой сети будет иметь структуру кольца (см. Рис. 2). При этом каждый узел в один переприем в оптической форме может осуществлять передачу только одному из узлов.
Построение математической модели сети
Ограничения, накладываемые технологией WDM в отсутствие волновых конвертеров, приводят к тому, что традиционные в теории телетрафика модели и методы их анализа [1, 2, 9, 10, 18, 20, 51, 56, 63] не могут быть применены. В частности, состояние сети не может быть полностью описано числом установленных соединений каждого класса, т.к. важно не только сколько установлено соединений, но и какие каналы (длины волн) оно использует. Учет данного факта приводит к существенному усложнению пространства состояний и матрицы интенсивностей переходов процесса, описывающего функционирование сети WDM с маршрутизацией подлине волны. Основными параметрами математической модели сети с маршрутизацией по длине волны являются способ выбора маршрута (в основном используются фиксированная или фиксированная альтернативная маршрутизация), способ назначения длин волн (в основном используется схема случайного выбора), наличие, количество и степень конверсии волновых конвертеров, а также наличие оптических разделителей, если учитывается многоадресный трафик.
Математическая модель сети WDM с маршрутизацией по длине волны с фиксированной маршрутизацией, случайным выбором длин волн и без волновой конверсии была предметом исследований многих авторов [40, 46, 60, 80, 84, 85, 87]. У всех авторов делается предположение о пуассоновском характере поступления заявок на установление соединений, а также об экспоненциальном распределении длительности их удержания. Однако сложность исследуемого явления привела к необходимости дополнительных упрощающих предположений. Так в [46] при построении модели линейного фрагмента сети предполагалось, что интенсивности поступления потоков заявок на установление соединения по маршрутам, включающим в себя больше одного звена, много меньше интенсивности поступления заявок на маршруты, состоящие из одного звена. В этой работе был разработан приближенный алгоритм для расчета вероятностей блокировок, который, однако, из-за высокой трудоемкости может быть применен только для анализа линейных фрагментов из двух-трех звеньев. В [59] при построении математической модели и анализе линейного фрагмента сети сделано предположение о том, что нагрузка на звено j зависит только от нагрузки, поступающей на звено. В данной работе предложен рекурсивный алгоритм вычисления вероятностей блокировок заявок на установление соединений. В работах [84, 85, 87] построена математическая модель сети и разработан приближенный метод расчета вероятностей блокировок. Метод основывается на идее аппроксимации процесса, описывающего функционирование модели, марковским процессом, построенным над тем же пространством состояний, с почти теми же интенсивностями переходов, но у которого некоторые интенсивности переходов были изменены таким образом, чтобы приближенный марковский процесс был обратимым.
При моделировании многоадресной передачи данных могут использоваться различные подходы.
Один подход в построении модели сети с многоадресными соединениями состоит в том, что в сеть поступают заявки на установление всего дерева многоадресной передачи сразу. При этом принимается, что пользователи не могут подключаться к уже существующему многоадресному соединению2. В случае если существует осуществить передачу тех же данных дополнительному множеству получателей, то должно быть установлено еще одно многоадресное соединение (не оказывая влияния на уже существующее соединение). Таким образом, структура многоадресных соединений в такой модели статична. Подобный подход использовался для построения модели с многоадресными соединениями в [67, 73]. В этих работах предполагается, что существует 3 Рассмотрим сеть, предоставляющую услуги кабельного телевидения. Пусть пользователи сети имеют 9 возможность подписаться на просмотр телепередачи или телефильма по расписанию. Таким образом, к началу трансляции известен набор подписчиков и, следовательно, необходимо установить многоадресное соединение от сервера услуг ко всем подписчикам. В рассматриваемой модели число подписчиков не может измениться после установления соединения. фиксированное количество возможных классов соединений, каждый из которых характеризуется световым путем, если это одноадресное соединение, или световым деревом, если речь идет о многоадресном соединении, а также интенсивностью поступления и обслуживания. Состояние сети характеризуется информацией обо всех установленных соединениях всех классов. В [67] предлагается приближенный метод, позволяющий аппроксимировать потоки заявок на установление многоадресных соединений потоками одноадресных заявок со специально подобранными интенсивностями поступлений. При моделировании многоадресных соединений предполагается, что в один момент времени в сети может быть установлено два и более одинаковых многоадресных соединений.
Другой подход в построении модели сети с многоадресными соединениями состоит в том, что поступающие в сеть заявки могут подключаться к существующему дереву многоадресной передачи [25, 26, 29, 30, 31, 32, 54, 55, 70, 72]. В работах [27, 29, 31, 32, 48, 72] для моделирования сети с многоадресными соединениями вводится новое понятие - «логический путь», который характеризуется маршрутом от узла подключения пользователя и предоставляемой услугой. Состояние модели, таким образом, описывается состоянием всех логических путей. Структура многоадресных соединений в рассматриваемой модели динамична: сделавший запрос на предоставление услуги будет подключен к логическому дереву многоадресной передачи, если эта услуга уже предоставляется другим пользователям, или инициализирует новое многоадресное соединение, если эта услуга никому не предоставлялась.
Пространство состояний и равновесное распределение
Пусть л (/)є{0,і} - случайное число световых путей установленных для к - соединения на длине волны w в сети в момент времени г 0. Заметим, что здесь необходимо различать вероятность того, что нельзя установить иоеое к - соединение и вероятность того, что нельзя принять к - заявку, т.к. в рассматриваемой модели многоадресные соединения могут быть заблокированы только тогда, когда ни на одной длине волны маршрута не установлено соединения этого же класса. В противном случае, вне зависимости от состояния других каналов звеньев заявка не блокируется, а «присоединяется» к существующему соединению. Таким образом, если рассмотреть одноадресную и многоадресную заявки, использующих один и тот же маршрут, то вероятность отказа в установлении нового соединения для обоих классов будет одинаковая, а вероятность отказа в приеме заявок для многоадресного соединения будет ниже, чем для одноадресного. W и числа классов К и быстро растет с их увеличением. Поэтому в данном разделе мы приводим результаты численного решения СУР только для простого линейного фрагмента, заданного на Рис. 9. На графиках мы сравниваем результаты, полученные решением СУР, с результатами, полученными с помощью имитационного моделирования. Для более сложного линейного фрагмента, который будет рассмотрен ниже, приводятся только результаты моделирования. 4 = = 0.0(0.05)0.25, Дз = 0.03, Л, - 0-03, ц1 -„.-/ -% W = Рис. 12 График изменения вероятностей блокировок всех классов заявок, полученных решением СУР и моделированием, при увеличении интенсивности поступления 1 и 2 - заявок
Рассмотрим пример четырехзвеньевого линейного фрагмента, заданного на Рис. 15. В примере в системе может быть установлено шесть классов соединений, 1,...,5 из которых являются одноадресными, а соединение 6 - многоадресным. На рисунке поступающие потоки заявок на установление соединений схематично изображены стрелками.
Построение и решение СУР для такой системы уже является чрезвычайно трудоемким делом, поэтому её анализ мы будем производить с помощью имитационного моделирования. 1 Можно видеть, что с ростом числа длин волн вероятности блокировок всех классов соединений быстро падают. Данный тип графиков позволяет оценить минимальное число длин волн в звеньях, необходимое для обеспечения нужного уровня качества передачи данных.
Далее сравним рассматриваемую модель с маршрутизацией по длине волны с сетями, функционирующие по принципу коммутации каналов. В сетях с коммутацией каналов заявка принимается и соединение устанавливается тогда, когда в каждом звене нужного маршрута есть хотя бы один свободный канал. В противном случае заявка на установление соединения блокируется. В сетях с маршрутизацией по длине волны из-за дополнительных ограничений (ограничение постоянства длины волны и ограничение используемости длин волн) заявка на установление соединения прнинимается только в том случае, если существует хотя бы одна длина волны свободная на всех звеньях маршрута. Очевидно, что вероятности блокировок в сетях с маршрутизацией по длине волны выше, чем в сетях с коммутацией каналов.
Вычисление нормирующей константы
Приведенный в предыдущем разделе метод расчета распределения линейного фрагмента сети WDM с маршрутизацией по длине волны связан с достаточно интенсивными вычислениями. Из формул (9), (11) видно, что основной задачей при вычислении равновесного распределения линейного фрагмента является расчет нормирующей константы. Это связано с тем, что мощность множества (5) растет экспоненциально с ростом количества классов соединений. В данном разделе предлагается эффективный рекурсивный алгоритм расчета нормирующей константы.
Полученные результаты определяют метод расчета нормирующей константы: по формулам (19), (20) могут быть рекуррентно вычислены значения функций g(k,w)r а по формуле (21) вычисляется искомое значение нормирующей константы (11).
Построение данного множества и вычисление блокировок по формуле (22) исключительно неэффективно ввиду быстрого роста мощности пространства состояний Q. Ниже предлагается более эффективный метод вычисления вероятностей блокировок заявок на установление соединений.
Доказательство. По условию теоремы, шар т -го цвета нельзя разместить в некоторую урну в том случае, если либо эта урна уже занята другим шаром этого же цвета, либо если в урну с эти же номером из своего набора урн помещен шар другого цвета, например, цвета /, который влияет на размещение т - шаров, т.е. sjm = 1. Поэтому искомое число вариантов - это число вариантов размещения всех шаров такое, что ни в одну урну из набора урн для т -шаров нельзя разместить еще один шар.
Рассмотрим случай 1ИУ =0.В данном случае удовлетворяющие условию задачи варианты существуют только тогда, когда число шаров влияющих на размещение т - шаров превосходит число урн, которые необходимо занять, т.е. mWJV.-v.). Этим рассуждением оправдывается множитель u(smn-mm(Nj -v,)+l) в верхней части формулы (25).
В предыдущем разделе были получены приближенные аналитические выражения для равновесного распределения процессов, описывающих функционирование линейного фрагмента сети с маршрутизацией по длине волны. Время работы алгоритма модификации растет экспоненциально при увеличении числа классов соединений. Поэтому, в случае если число классов таково, что вычисления с помощью приближенного метода модификации интенсивностей переходов невозможны, то может быть применен метод декомпозиции [84].
Мы будем анализировать функционирование четырехзвеньевого линейного фрагмента, представленного на рисунке 5 (а) (для которого определено К = б классов) путем его декомпозиции на два сегмента как это показано на рисунке 5 (Ь) (для каждого из которых определено Kin = К(2) = 4 классов соединений). Пусть марковский процесс X(s)(t),t 0, определенный над множеством состояний П , описывает функционирование сегмента s = 1,2. Если бы на четырехзвеньевой фрагмент поступали заявки на установление соединений только на звеньях первого или второго сегментов (не было бы заявок на установление соединения по звеньям и первого и второго сегмента), то введенные процессы Х (() были бы независимыми. В этом случае, можно было бы рассмотреть два сегмента независимо друг от друга с помощью приближенного алгоритма из предыдущего раздела. ti
Вероятности блокировок заявок исходного четырехзвеньевого фрагмента равнялись бы вероятностям блокировок соответствующих заявок двухзвеньевых сегментов. В общем случае, когда помимо заявок на установления соединений только по звеньям одного из сегментов могут поступать заявки на установление соединений по звеньям обоих сегментов, данные марковские процессы будут зависимыми. Таким образом, для того, чтобы состояние каналов этих сегментов, рассмотренных независимо друг от друга, приближенно соответствовало состоянию исследуемого линейного фрагмента в любой момент времени, необходимо специальным образом подобрать нагрузку, предложенную на рассматриваемые сегменты.
В данном разделе мы сравним результаты вычисления вероятностей блокировок для примеров, заданных на Рис. 9 и Рис. 15. Для двухзвеньевого линейного фрагмента (см. Рис. 9) мы построим и сравним кривые, полученные численным решением СУР, и алгоритма «модификации интенсивностей переходов» предложенного в разделе 3.1. Время работы данного алгоритма растет экспоненциальным образом при увеличении числа классов соединений, тем не менее, он позволяет существенно расширить диапазон применения аналитических методов. В качестве примера его работы на более «длинном» линейном фрагмента будет рассмотрен четырехзвеньевой линейный фрагмент (см. Рис. 15), где результаты алгоритма «модификации интенсивностей переходов» будут сравнены результатами имитационного моделирования.
График изменения вероятностей блокировок всех классов заявок, полученных с помощью имитационного моделирогвания и алгоритмом «модификации», при увеличении числа длин волн в звеньях, W. На Рис. 23 отображены кривые изменения вероятностей блокировок при увеличении числа длин волн в звеньях. Очевидно, что с ростом числа длин волн все вероятности быстро уменьшаются. Данный тип графиков позволяет оценить минимальное число длин волн в звеньях, необходимое для обеспечения нужного уровня качества передачи данных.
В диссертационной работе разработана математические модель сети WDM с маршрутизацией по длине волны и предложены эффективные алгоритмы вычисления их вероятностно-временных характеристик. Ниже приводится список основных результатов, полученных в работе:
1. В главе 2 предложена математическая модель линейного фрагмента сети WDM с маршрутизацией по длине волны без волновых конвертеров с фиксированной схемой маршрутизации и схемой случайного выбора длин волн;
2. В разделе 3.1 впервые метод модификации интенсивностей переходов применен для анализа линейного фрагмента сети WDM с маршрутизацией по длине волны, поддерживающей одноадресные и многоадресные соединения;
3. В разделе 3.2 предложен рекурсивный алгоритм для вычисления нормирующей константы равновесного распределения;
4. В разделе 3.3 предложен алгоритм для расчета вероятностей блокировок линейного фрагмента сети WDM с маршрутизацией по длине волны с одноадресными и многоадресными соединениями.
