автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Разработка метода численного анализа характеристик узлов обработки трафика мультисервисной сети

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

¿А""

сС

Козырева Надежда Ивановна

РАЗРАБОТКА МЕТОДА ЧИСЛЕННОГО АНАЛИЗА ХАРАКТЕРИСТИК УЗЛОВ ОБРАБОТКИ ТРАФИКА МУЛЬТИСЕРВИСНОЙ СЕТИ

Специальность 05.12.13 — Системы, сети и устройства телекоммуникаций

5 ДЕК 2013

Автореферат диссертации на соискание ученой степени кандидата технических наук

Самара-2013

005542514

Работа выполнена в Федеральном государственном образовательном бюджетном учреждении высшего профессионального образования «Поволжский государственный университет телекоммуникаций и информатики» (ФГОБУ ВПО ПГУТИ)

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

Карташевский Вячеслав Григорьевич

Официальные оппоненты: Прохоров Сергей Антонович

Заслуженный работник высшей школы РФ, доктор технических наук, профессор ФГБОУ ВПО Самарский государственный аэрокосмический университет им. академика С.П. Королева (национальный исследовательский университет) заведующий кафедрой «Информационные системы и технологии»

Бахарева Надежда Федоровна

доктор технических наук, доцент ФГОБУ ВПО ПГУТИ Заведующая кафедрой «Информатика и вычислительная техника»

Ведущая организация: ФГБОУ ВПО «Самарский

государственный технический университет»

Защита состоится 26 декабря 2013 г. в 12 часов на заседании диссертационного совета Д219.003.02 при Поволжском государственном университете телекоммуникаций и информатики по адресу: 443010 г. Самара, ул. Льва Толстого, 23.

С диссертацией можно ознакомиться в библиотеке ФГОБУ ВПО ПГУТИ.

Автореферат разослан 26 ноября 2013 г.

Учёный секретарь

диссертационного совета Д219.003.02, доктор технических наук, профессор

Мишин Д.В.

Общая характеристика работы

Актуальность темы. На сегодняшний день состояние телекоммуникационных сетей операторов связи в России характеризуется высокой степенью динамики развития. Это связано, в том числе и с появлением новых сетевых технологий, новых мультимедиа сервисов, а так же переходом традиционных услуг на платформу IP. Стремительно растет количество пользователей новыми услугами, так по данным компании J'son & Partners Consulting на конец 2012 г. абонентская база услуги IPTV в России составила около 2,54 млн. пользователей, что соответствует 4,7% от общего числа домохозяйств России. По прогнозам этой же компании проникновение IPTV в 2017 г. может вырасти в 2 раза по сравнению с 2012 г. Если в 2011 г. в России насчитывалось 22 млн. пользователей IP-телефонии, то по итогам 2012 г. количество выросло до 27 млн., а к концу 2015 г. по прогнозам аналитиков число пользователей VoIP-сервисом достигнет 37 млн.

Продолжающаяся в последние десятилетия конвергенция сетей передачи голоса и данных привела к появлению понятия мультисервисные сети (МСС), то есть сети, готовые к предоставлению любых телекоммуникационных и информационных услуг. В условиях новой концепции построения сетей, становится актуальной проблема анализа качества предоставления услуг, а так же проблема выбора оптимальных параметров проектируемых телекоммуникационных систем. При рещении этих задач принято использовать аппарат теории массового обслуживания. Существуют фундаментальные работы, посвященные решению данных вопросов, следующих ученых: Хинчин А.Я.,Клейнрок Л., Саати Т.Л., Эрланг А.К., Башарин Г.П. и др. Однако описанные в них методы анализа СМО, как правило, разработаны в предположении о пуассоновских потоках поступления и обслуживания требований.

В 1993 были опубликованы результаты работы американских ученых W.E.Leland, M.S.Taqqu, W.Willinger, D.V.Wilson, которая в корне изменила существующие представления о процессах, происходящих в телекоммуникационных сетях с коммутацией пакетов. Так впервые было установлено, что трафик такой сети обладает свойством "самоподобия", т.е. выглядит качественно одинаково при почти любых масштабах временной оси, имеет память (последействие), а также характеризуется высокой пачечностью. В результате чего теоретический расчет параметров системы, предназначенной для обработки такого трафика, по классическим формулам дает некорректные и неоправданно оптимистические результаты. Более того, привычные алгоритмы обработки трафика, созданные для работы с простейшими потоками, оказываются недостаточно эффективными для потоков с самоподобием.

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

В связи с этим, в настоящее время существует актуальная научно-техническая задача анализа и разработки методов расчета параметров узла МСС, таких как среднее время ожидания пакетов в очереди, длина очереди.

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

Для достижения поставленной цели требуется решение следующих задач:

— анализ трафика в узле МСС с целью выявления его самоподобных свойств;

— анализ существующих методов оценки характеристик СМО произвольного типа;

— исследование методов решения интегрального уравнения (ИУ) Линдли, как уравнения Фредгольма второго рода;

— разработка и реализация алгоритма численного метода определения плотности вероятности времени ожидания пакетов в очереди и длины очереди в узле МСС, представленном в виде модели СМО типа 0/0/1.

Методы исследования. Основные теоретические и экспериментальные исследования диссертационной работы выполнены с применением методов теории вероятностей, математической статистики и вычислительных методов, реализованных в пакете МаЙаЬ.

Научная новизна работы. Научная новизна диссертационной работы заключается в следующем:

— предложен алгоритм численного решения интегрального уравнения Линдли с целью определения среднего времени ожидания пакета в очереди и длины очереди для СМО произвольного типа;

— получены аналитические выражения ядер ИУ Линдли для случая использования распределений с «тяжелым хвостом» (РТХ);

— выполнен анализ характеристик, полученных путем решения интегрального уравнения Линдли для СМО произвольного типа при использовании РТХ.

Основные положения, выносимые на защиту:

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

- определение плотности распределения времени ожидания пакета в очереди может быть осуществлено на основе метода Гаусса — Кристоффеля решения ИУ второго рода;

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

- анализ средней длины очереди и времени ожидания пакетов в устройстве обслуживания, показывает что для СМО с РТХ значения данных характеристик существенно превышают аналогичные значения для системы М/М/1.

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

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

Практическая ценность и реализация результатов работы.

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

Результаты диссертационной работы внедрены в ОАО «Концерн «Автоматика» (г. Москва), что подтверждено актом внедрения, представленным в приложении.

Результаты работы использованы в учебном процессе ФГОБУ ВПО «Поволжский государственный университет телекоммуникаций и информатики» (г. Самара) при изучении курса «Основы теории массового обслуживания», что подтверждено актом внедрения.

Апробация работы. Основное содержание работы докладывалось и обсуждалось на XIV, XV, XVI, XVII и XVIII Российской научно-технической конференции ПГУТИ (Самара, 2007г., 2008г., 2009г., 2010г. и 2011г.), на VIII, IX и X Международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» (Уфа, 2007г., Казань, 2008 г.,

Казань, 2009 г.), на X и XI Международной конференции «Цифровая обработка сигналов и ее применение» (Москва, 2008г. 2009г.), IX Международной конференции «Кибернетика и высокие технологии XXI века» (Воронеж, 2008г), VIII и XI Всероссийском Симпозиуме по Прикладной и Промышленной Математике (Сочи-Адлер, 2007 г., Кисловодск, 2010 г.), на 63 и 65 научных сессиях, посвященных Дню Радио (Москва, 2008 г. 2010 г.), на I Международной научно-практической конференции «Проблемы

инфокоммуникаций. Наука и технологии» (Харьков, 2013 г.).

Публикации. По теме диссертации опубликовано 18 работ, в том числе 3 работы из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных исследований, 7 тезисов, 8 публикаций трудов и докладов на международных научных конференциях.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка используемой литературы. Основная часть работы содержит 133 страницы машинописного текста и 18 рисунков. Список литературы содержит 115 наименований.

Краткое содержание работы

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

В первой главе рассмотрены особенности построения современных мультисервисных сетей. Рассмотрены основные положения концепции NGN, в том числе вопросы обеспечения качества обслуживания в сетях IP. Представлена структура перспективной сети доступа и основные ее компоненты, а так же описаны некоторые особенности трафика локальных (LAN) и глобальных (WAN) сетей.

Рассмотрены виды систем массового обслуживания. Для оценки вероятностных характеристик модели СМО используют следующие методы, описанные в первой главе: явное решение, алгоритмическое решение, имитационное моделирование, инженерные методики, эмпирические методы и измерение.

Методы управления очередями позволяют рационально использовать ресурсы сети. Эти методы можно разбить на три основные группы: специальные стратегии организации очередей, traffic shaping и ограничение скорости. В главе также рассмотрены дисциплины обслуживания: FIFO, WQF, RED, priority queueing, custom queueing.

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

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

Во второй главе рассмотрены аналитические методы исследования СМО, такие как:

- построение вложенной цепи Маркова по моментам обслуживания заявок;

- введение дополнительной переменной;

- интегральный метод Линдли.

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

Сравнение предложенных методов показало, что целесообразным является анализ СМО типа 0/0/1 путем решения ИУ Линдли.

где Т7- функция распределение времени ожидания требования в очереди;

К -функция распределения разности между длительностью обслуживания требования и интервалом времени между поступлениями соседних требований.

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

Кроме того, представляет интерес решение уравнения Линдли как ИУ Фредгольма второго рода.

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

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

Р{х) =

$К(х-у)с/Г(у),х> О

(1)

а

где Xj - узлы квадратурной формулы, Aj - известные коэффициенты, не зависящие от функции (р(х), п - это степень полинома ф(х;), используемого для интерполяции подынтегрального выражения, £„[<р]- ошибка замены

интеграла суммой, т. е остаточный член квадратурной формулы.

При решении ИУ часто прибегают к использованию квадратурных формул Ньютона — Котеса, которые являются интерполяционными. Однако они не могут успешно использоваться для получения формул высокой точности по причине неустойчивости интерполяционного процесса для многочленов высокого порядка. В главе 3 показано, что постоянные Лебега растут с увеличением количества узлов интерполяции для равномерной сетки. По этой причине обычно используются полиномы степени от нуля до трех. Вычисление с их помощью интегралов от функций, обладающих высокой степенью гладкости представляется нерациональным. В выражение для погрешности этих формул входят первая, вторая или четвертая производные. Погрешность определяется низким порядком производной при высокой степени гладкости интегрируемой функции. Этих недостатков лишены квадратуры Гаусса, обеспечивающие высокую точность уже при небольшом количестве узлов интерполяции. Квадратуры Гаусса лежат в основе численного метода Гаусса-Кристоффеля.

При решении ИУ Фредгольма второго рода

ь

у(х) - |л:(х, s)y(s)cls = f(x) , (a <x<b) (3)

а

суть метода Гаусса-Кристоффеля заключается в замене интеграла в (3) приближенно на квадратурную сумму по формуле (2) и дальнейшего решения нового уравнения относительно новой неизвестной функции :

/"(*) - =/(*) (4)

м

Для решения уравнения (3) х поочередно полагается равным х1,х1,...,ха.

Обозначим gt =yw(xj), тогда gt должны удовлетворять системе уравнений

=/(*,), / = 1.2.....ft , (5)

№

Или в матричной записи Dz= q, где

D= КМ,= V ^К(х„х^, q = (f(xl)/(x2),...f(x„))

г = (д1,д1,...,дп) - искомый вектор.

После вычисления решения системы (5), решение уравнения (4) может быть получено по формуле

м

Блок-схема алгоритма численного решения уравнения Линдли для СМО произвольного типа представлена на рис.1

Рис.1

В четвёртой главе разработанный алгоритм решения ИУ Линдли использован для анализа характеристик функционирования СМО общего вида. Проверка достоверности результатов работы предложенного метода, была осуществлена путем решения ИУ для СМО типа М/М/1, так как существует аналитически определенная функция плотности распределения времени ожидания для такой системы.

Дифференцируя обе части уравнения (1) по переменной х получим

/(*)= \K\(x-y)f(y)dy,x>Q

о"

С учетом того, что функция F(0) является вероятностью того что приходящая заявка застает систему пустой, интегрирование по dF(y) дает

оо

fix) = Kx(x)F{ 0) + ¡Kx(x-y)/(y)dy (6)

о

Для одноканальных систем F(0) = 1 - р, где р- коэффициент использования системы. Разделим обе части уравнения на F(0) и обозначим fix)

ф(х) =-, тогда

Fi 0)'

оо

ф(х) = <(х)+|<(х-;у)фООф (7)

о

Для дальнейшего решения уравнения (7) необходимо определить функцию Kxiu), т.е. ядро интегрального уравнения. Можно показать, что для всех и , К iu) определяется выражением

ос

К'iu) = ]б(и +t)a(t)ch,

о

где ait) - плотность распределения интервалов времени между поступлениями требований на обслуживание, bix) - плотность распределения длительности обслуживания. Для системы М/М/1 эти распределения имеют вид

a(t) = ke-7J ,b(x) = [ie-ÍLX.

Вычисляя интегралы и полагая Ki0) = 1--, находим

А. + Ц

Kiu) =

1--—е~т,и> 0

+ ц

(8)

Х + (1

Известно, что для одноканальных СМО коэффициент использования системы определяется как р = Х/ц, тогда с учетом (8) окончательно получаем зависимость для ПРВ случайной величины и

К\и) =

цр

1+р

—еи,и<0 1+р

Следующим этапом реализации алгоритма является определение узлов и весов квадратуры Гаусса. Узлы квадратуры Гаусса располагаются в корнях полинома Лежандра степени N. Так если Ры(х) - полином Лежандра, тохА. -корни полинома, определенные на отрезке [-1,1], т. е. табличные узлы

квадратуры Гаусса, а с, =---- - табличные веса квадратуры

Гаусса. Существуют таблицы узлов и весов квадратуры Гаусса для N от 1 до 512. Приведенные в таблицах справочной литературы данные рассчитаны для отрезка [-1,1]. При этом предполагается, что интегрирование производится по табличному отрезку. При реализации вычислений нужно искать интеграл на отрезке [0,6]. В таком случае при использовании табличных значений узлов и весов, с помощью замены переменной осуществляется переход от переменной

х е [-1,1] к переменной хк е [0,6]:

Ь+а Ь-а

х. =--1--х,

А 2 2

Затем определяются А. - веса полинома Лежандра в узлах хк . Следующим этапом реализации алгоритма является определение К( значений ядра К (х-у) в узлах хк_ и х^ , при / = [1: /V], у =[1: /V]. На рис. 2 представлен график изменения значений функции К'(},/)

Рис.2

Далее вычисляя значения г функции ф в узлах хк , решение уравнения (7) получается в виде

Ь — а "

Ф(х) = Кх{х) + ——^А/Х(хк ,хк

1 м

Для функции плотности распределения времени ожидания в очереди получаем

/М = (Кх(х)+~^А;К(хк1 »(1 - р)

1 7=1

Аналитически в работе Л.Клейнрока данное распределение было записано в виде

>фс) = ¡л(1 — р)е~и0~р)1 Результаты аналитических и численных расчетов представлены на рис.3.

0.25

0.2

0.15 0.1 0.05 0

О 10 20 30 40 50 60

х

Рис. 3

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

Так среднее время в очереди при выбранных параметрах )J. = 0,25 [1/t] и

р = 0,67 составила 8,12. По формуле Литтла была рассчитана средняя длина очереди

Q = Xx = 0,17-8.12 = 1,38 Переходя к решению ИУ Л индии для СМО типа G/G/1, в качестве распределения интервалов между требованиями и распределения времени обслуживания этих требований примем распределение Парето. Т.е.

cfiff function

.................

--- analytical curve

\ р = 0,1

................ V \

р = 0,67

о,/<р

аЬ" ^ О ,КЪ

Так, например для а = а = 2 , р = 3 и 6 = 2, выражения для ядра примут

вид

К\и) =

аЬ1 ар:

и + р2

аЬгар2 1

,и =0

а62сф2 -

и+ В2

1 2 9 12

2 • 2<Р и р и3 ы4

2 9 12

- + -Г- + —+

6 , и + р

--т1п--

и* Р

,и> О

(9),

2-иВ и'В и3 и4

6 , и +В + — 1п-

,и< 0;

где /? = шахЬ-и,В .

Вид ядра представлен на рис. 4.

Рис.4

Следуя описанному выше алгоритму, были получены значения функции плотности распределения времени ожидания требования в очереди СМО типа 0/0/1, представленные на рис. 5 .

■в __»

(М (ипс.юл

§ 0.1

- 3/13/1 М/М/1

-_-

600 650 700 750

Рис.5

Оценка точности алгоритма была произведена методом Рунге-Ромберга. Погрешность вычислений согласно анализу точности составляет менее 1%.

По результатам расчета плотности f(x) оценены средние значения времени пребывания пакета в очереди и длины очереди соответственно.

х = 14,18, ß = ^ = 0,1714,18 = 2,4 Рис. 5 подчеркивает факт того, что при работе с РТХ результаты расчетов среднего времени пребывания пакета в очереди и размера очереди зависят от интервала представления аргумента исходных плотностей распределения времени обслуживания и поступления пакетов.

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

— Непосредственными измерениями подтвержден самоподобный характер трафика на узле доступа МСС;

— проведен анализ существующих методов оценки характеристик СМО произвольного типа, в результате чего принято решение произвести анализ СМО типа G/G/1 путем решения ИУ Линдли;

— проведено исследование методов решения ИУ Линдли, как уравнения Фредгольма второго рода;

— разработан алгоритм численного метода определения плотности вероятности времени ожидания пакетов в очереди и длины очереди в узле МСС, на основе метода Гаусса-Кристоффеля. Реализация разработанного алгоритма произведена для моделей СМО типа М/М/1, G/G/1. Показано, что при соответствующих коэффициентах загрузки среднее время ожидания и средняя длина очереди для системы G/G/1 больше, чем для системы М/М/1, а так же сохраняется тенденция увеличения значений данных характеристик с увеличением интервала анализа.

Основные публикации по теме диссертации: Публикации в изданиях рекомендованных ВАК

1. Козырева, Н.И. Самоподобные процессы в оценке телетрафика [Текст]/ Карташевский И. В., Козырева H.A.// Обозрение прикладной и промышленной математики. - 2007. -Т. 15,№ 2. - С. 372-373.

2. Козырева, Н.И. Численный анализ характеристик сетевого узла типа G/G/1. [Текст]/ Козырева Н.И.// Обозрение прикладной и промышленной математики. -2010.-Т. 17,№ 5.-С. 732-733.

3. Козырева, Н.И. Метод численного решения уравнения Линдли при анализе систем массового обслуживания [Текст]/ Блатов И.А, Карташевский В.Г. Козырева Н.И.// Электросвязь. - 2013. - № 3. - С.48-50.

Публикации в других изданиях

4. Фадеева,* Н.И. Самоподобные процессы в оценке трафика [Текст]/ Фадеева Н.И.// Труды XIV Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов. - Самара: ПГАТИ, 2007.-С.54.

5. Козырева, Н.И. Имитационное моделирование систем массового обслуживания в среде GPSS [Текст]/ Козырева Н.И.// Труды XV Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов. — Самара:ПГАТИ, 2008. - С. 90-91.

6. Козырева, Н.И. Анализ системы массового обслуживания типа G/G/1 при распределении времени обслуживания с «тяжелым хвостом» [Текст]/ Меркулова И.А., Козырева Н.И.// Труды Российского научно-технического общества радиотехники, электроники и связи им. A.C. Попова. Серия «Цифровая обработка сигналов и ее применение». — Вып. X— М., 2008. — С. 282-284.

7. Козырева, Н.И. Моделирование распределения с тяжелым хвостом с использованием системы M/G/1 [Текст]/ Карташевский И. В., Козырева Н.И.// Проблемы техники и технологии телекоммуникаций: матер. VIII Междунар. Науч.-техн. конф.- Уфа, 2007. - С. 110-113.

8. Козырева, Н.И. Моделирование характеристик узла мультисервисной сети [Текст]/ Карташевский И. В., Козырева Н.И.// Труды Российского научно-технического общества радиотехники, электроники и связи им. A.C. Попова. Серия «Научная сессия, посвященная Дню Радио». - Вып. LXIII-M., 2008. - С. 225-226.

9. Козырева, Н.И. Метод решения уравнения Линдли при анализе СМО типа G/M/1 [Текст]/ Карташевский И. В., Козырева Н.И.// Проблемы техники и технологии телекоммуникаций: матер. IX Междунар. Науч.-техн. конф — Казань, 2008.-С. 123-124.

10. Козырева, Н.И. Исследование поведения длины очереди в системе массового обслуживания G/G/1 при распределении времени обслуживания с «тяжелым хвостом» [Текст]/ Меркулова И.А., Козырева Н.И. // Доклады IX Международной конференции «Кибернетика и высокие технологии XXI века». - Воронеж, 2008 - № 1. - С. 503-506.

П.Козырева, Н.И. Применение теоремы о среднем при анализе систем G/M/1 [Текст]/ Карташевский В. Г., Козырева Н.И.// Труды XVI Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов. - Самара, 2008. -С. 90-91.

12. Козырева, Н.И. Метод вычисления обратного преобразования Лапласа при решении уравнения Линдли [Текст]/ Шатилов С. В., Козырева Н.И.// Труды Российского научно-технического общества радиотехники, электроники и связи им. A.C. Попова. Серия «Цифровая обработка сигналов и ее применение». - Вып. XI - М., 2009. - С. 282-284.

13. Козырева, Н.И. Разработка метода вычисления преобразования Лапласа при решении уравнения Линдли [Текст]/ Шатилов С. В., Козырева Н.И.// Проблемы техники и технологии телекоммуникаций: матер. X Междунар. науч.-техн. конф.— Казань, 2009. - С. 7-8.

14. Козырева, Н.И. Применение Вейвлет-преобразования при анализе систем G/G/1 [Текст]/ Козырева Н.И.// Труды XVII Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов. — Самара, 2010. — С. 57-58.

15. Козырева, Н.И. Применение Вейвлет-преобразования при решении интегрального уравнения Линдли [Текст]/ Козырева Н.И.// Труды Российского научно-технического общества радиотехники, электроники и связи им. A.C. Попова. Серия «Научная сессия, посвященная Дню Радио». — Вып. LXV— М.,

2010.-С. 231-233.

16. Козырева, Н.И. Преобразование Лапласа методом Гаусса-Лагерра/ Козырева Н.И.// Труды XVIII Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов. — Самара,

2011.-С. 64-65.

П.Козырева, Н.И. Применение численного метода при решении интегрального уравнения Линдли. [Текст]/Козырева Н.И.// Проблемы инфокоммуникаций. Наука и технологии: матер. I Междунар. Науч.-техн. конф - Харьков, 2013. С. 51-52.

18. Козырева, Н.И. Алгоритм работы метода Гаусса-Кристоффеля для решения ИУ Линдли [Текст]/ Козырева Н.И.// Труды XX Российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов. — Самара, 2013. —С. 81.

♦-Фадеева Н.И. сменила фамилию на Козырева Н.И. 31.08.2007 г.

Федеральное государственное образовательное бюджетное учреждение высшего

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

_443010, г. Самара, ул. Льва Толстого, 23_

Подписано в печать 25.11.2013. Формат 60x84Хо Бумага офсетная.

_Гарнитура Times. Заказ 1651. Усл. печ. л.0,93. Тираж 100 экз._

Отпечатано в Издательстве учебной и научной литературы Поволжского государственного университета телекоммуникаций и информатики 443090, г. Самара, Московское шоссе 77, т. (846)228-00-44

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

Федеральное государственное образовательное бюджетное учреждение высшего

профессионального образования

ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ

042014531 53 (/

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

Козырева Надежда Ивановна

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

Специальность: 05.12.13 - Системы, сети и устройства телекоммуникаций Диссертация на соискание степени кандидата технических наук

Научный руководитель:

доктор технических наук, профессор

Карташевский Вячеслав Григорьевич

Самара - 2013

оглавление

перечень сокращений............................................................4

введение............................................................................................5

1. мультисервисные телекоммункационные сети.....................................................................................................10

1.1 Структура современных мультисервисных сетей.................................10

1.1.1 Качество обслуживания в сетях IP...............................................14

1.1.2 Алгоритмы управление очередями в сетях IP.............................18

1.2 Особенности построения мультисервисных сетей. Трафик мультисервисных сетей.......................................................................................23

1.2.1 Сети доступа. Трафик LAN...........................................................23

1.2.2. Транспортные сети NGN. Трафик WAN.....................................29

1.3. Виды систем массового обслуживания. Методы теории телетрафика...........................................................................................................33

1.4. Выводы......................................................................................................44

2. методы исследования смо типа g/g/1 46

2.1. Самоподобные модели телекоммуникационного трафика..................46

2.2. Экспериментальное исследование свойств мультимедийного трафика..................................................................................................................51

2.3. Методы анализа СМО произвольного типа..........................................57

2.3.1. Метод вложенных марковских цепей Кендалла........................58

2.3.2. Введение дополнительной переменной......................................60

2.3.3. Интегральный метод Линдли.......................................................62

2.3.4. Метод диффузионной аппроксимации........................................73

2.3.5. Метод полиномиальной аппроксимации....................................76

2.4. Выводы......................................................................................................78

3. численные методы решения интегральных уравнений..................................................................................................81

3.1. Понятие и классификация интегральных уравнений...........................81

3.2. Метод вырожденных ядер.......................................................................82

3.3. Метод квадратур.......................................................................................84

3.3.1 Простейшие квадратурные формулы............................................87

3.3.2 Метод Гаусса-Кристоффеля...........................................................94

3.3.3 Правило Рунге практической оценки погрешности квадратурных формул..........................................................................................96

3.4. Проекционные методы............................................................................99

3.5. Алгоритм решения ИУ Линдли для СМО произвольного типа........102

3.6. Выводы....................................................................................................103

4. определение числовых характеристик смо

типа аа!....................................................................................................ю4

4.1. Реализация алгоритма решения ИУ Линдли для СМО типа М/М/1...................................................................................................................106

4.2. Реализация алгоритма решения ИУ Линдли для СМО типа 0/0/1....................................................................................................................110

4.3. Выводы....................................................................................................114

заключение............................................................................................115

литература..............................................................................................116

приложение 1........................................................................................127

приложение 2........................................................................................130

приложение 3........................................................................................131

приложение 4........................................................................................132

приложение 5........................................................................................133

перечень сокращений

АСШС - ассимптотическое самоподобие в широком смысле

ИУ - интегральное уравнение

МУЗ - медленно убывающая зависимость

ПРВ - плотность распределения вероятности

РТХ - распределение с «тяжелыми хвостами»

ССШС - строгое самоподобие в широком смысле

CIR (Committed Information Rate) - согласованная скорость передачи информации

FIFO (first-in, first-out) - алгоритм обработки очередей - «первый пришёл -первый вышел»

iVoD (Internet Video on Demand) - Internet видео по запросу

LAN (Local Area Network) - локальная вычислительная сеть

NGN (Next Generation Network) - концепция построения сетей связи

следующего поколения

QoS (Quality of Service) - качество обслуживания

RED (Random Early Detect) - алгоритм случайного раннего обнаружения

TCP/IP (Transmission Control Protocol/Internet Protocol) - эталонная модель,

служащая для обмена данными между узлами

WAN (Wide Area Network) - глобальная вычислительная сеть

WFQ (Weighted Fair Queuing) - взвешенный механизм равномерного

обслуживания очередей

Введение

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

На сегодняшний день состояние телекоммуникационных сетей операторов связи в России характеризуется высокой степенью динамики развития. Это связано, в том числе и с появлением новых сетевых технологий, новых мультимедиа сервисов, а так же переходом традиционных услуг на платформу IP. Стремительно растет количество пользователей новыми услугами, так по данным компании J'son & Partners Consulting на конец 2012 г. абонентская база услуги IPTV в России составила около 2,54 млн. пользователей, что соответствует 4,7% от общего числа домохозяйств России. По прогнозам этой же компании проникновение IPTV в 2017 г. может вырасти в 2 раза по сравнению с 2012 г. Если в 2011 г. в России насчитывалось 22 млн. пользователей IP-телефонии, то по итогам 2012 г. количество выросло до 27 млн., а к концу 2015 г. по прогнозам аналитиков число пользователей Уо1Р-сервисом достигнет 37 млн.

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

В условиях новой концепции построения сетей, становится актуальной проблема анализа качества представления услуг, а так же проблема выбора оптимальных параметров проектируемых телекоммуникационных систем. При решении этих задач принято использовать аппарат теории массового обслуживания. Существуют фундаментальные работы, посвященные решению данных вопросов, следующих ученых: Клейнрок JL, Саати T.JL, Эрланг А.К., Кокс Д., Вентцель Е.С. и др. [35, 42]Однако описанные в них

методы анализа СМО, как правило, разработаны в предположении о пуассоновских потоках поступления и обслуживания требований.

В 1993 были опубликованы результаты работы американских ученых W.E.Leland, M.S.Taqqu, W.Willinger, D.V.Wilson [107], которая в корне изменила существующие представления о процессах, происходящих в телекоммуникационных сетях с коммутацией пакетов. Было обнаружено, что потоки в ней нельзя аппроксимировать простейшими и, как следствие, они уже имеют совершенно иную структуру, чем принято в классической теории телетрафика. В частности, было установлено, что трафик такой сети обладает так называемым свойством "самоподобия", т.е. выглядит качественно одинаково при почти любых масштабах временной оси, имеет память (последействие), а также характеризуется высокой пачечностью. В результате теоретический расчет параметров системы распределения информации, предназначенной для обработки такого трафика, по классическим формулам дает некорректные и неоправданно оптимистические результаты. Более того, привычные алгоритмы обработки трафика, созданные для работы с простейшими потоками, оказываются недостаточно эффективными для потоков с самоподобием.

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

В связи с этим, в настоящее время существует актуальная научно-техническая задача анализа и разработки методов расчета параметров узла

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

Цель работы

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

Для достижения поставленной цели требуется решение следующих

задач:

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

- анализ существующих методов оценки характеристик СМО произвольного типа;

- исследование методов решения интегрального уравнения (ИУ) Линдли, как уравнения Фредгольма второго рода;

- разработка и реализация алгоритма численного метода определения плотности вероятности времени ожидания пакетов в очереди и длины очереди в узле МСС, представленном в виде модели СМО типа САЗЛ.

Методы исследования

Основные теоретические и экспериментальные исследования диссертационной работы выполнены с применением методов теории вероятностей, математической статистики и вычислительных методов, реализованных в пакете Ма1:1аЬ [28, 94]. Научная новизна работы

Научная новизна диссертационной работы заключается в следующем:

- предложен алгоритм численного решения интегрального уравнения Линдли с целью определения среднего времени ожидания пакета в очереди и длины очереди для СМО произвольного типа;

- получены аналитические выражения ядер ИУ Линдли для случая использования распределений с «тяжелым хвостом» (РТХ);

выполнен анализ характеристик, полученных путем решения интегрального уравнения Линдли для СМО произвольного типа при использовании РТХ.

Основные положения, выносимые на защиту

наличие самоподобных свойств трафика требует разработки новых алгоритмов анализа характеристик сетевых устройств МСС; определение плотности распределения времени ожидания пакета в очереди может быть осуществлено на основе метода Гаусса -Кристоффеля решения ИУ второго рода;

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

- анализ средней длины очереди и времени ожидания пакетов в устройстве обслуживания, показывает что для СМО с РТХ значения данных характеристик существенно превышают аналогичные значения для системы М/М/1.

Практическая ценность и реализация результатов работы

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

Результаты диссертационной работы внедрены в ОАО «Концерн «Автоматика» (г. Москва), что подтверждено актом внедрения, представленным в приложении.

Результаты работы использованы в учебном процессе ФГОБУ ВПО «Поволжский государственный университет телекоммуникаций и

информатики» (г. Самара) при изучении курса «Основы теории массового обслуживания», что подтверждено актом внедрения.

Апробация работы

Основное содержание работы докладывалось и обсуждалось на XIV, XV, XVI, XVII и XVIII Российской научно-технической конференции ПГУТИ (Самара, 2007г., 2008г., 2009г., 2010г. и 2011г.), на VIII, IX и X Международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» (Уфа, 2007г., Казань, 2008 г., Казань, 2009 г.), на X и XI Международной конференции «Цифровая обработка сигналов и ее применение» (Москва, 2008г. 2009г.), IX Международной конференции «Кибернетика и высокие технологии XXI века» (Воронеж, 2008г), VIII и XI Всероссийском Симпозиуме по Прикладной и Промышленной Математике (Сочи-Адлер, 2007 г., Кисловодск, 2010 г.), на 63 и 65 научных сессиях, посвященных Дню Радио (Москва, 2008 г. 2010 г.), на I Международной научно-практической конференции «Проблемы инфокоммуникаций. Наука и технологии» (Харьков, 2013 г.).

Публикации

По теме диссертации опубликовано 18 работ, в том числе 3 работы из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных исследований, 7 тезисов, 8 публикаций трудов и докладов на международных научных конференциях.

Структура и объем работы

Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложений. Основная часть работы содержит 133 страницы машинописного текста и 18 рисунков. Список литературы включает 115 наименований.

1. Мультисервисные телекоммуникационные сети

1.1 Структура современных мультисервисных сетей

С каждым годом усиливается тенденция сближения компьютерных и телекоммуникационных сетей разных видов. Предпринимаются попытки создания универсальной, так называемой мультисервисной сети, способной предоставлять услуги как компьютерных, так и телекоммуникационных сетей [70, 83].

К телекоммуникационным сетям относятся телефонные сети, радиосети и телевизионные сети. Главное что объединяет их с компьютерными сетями, то, что в качестве ресурса, предоставляемого клиентам, выступает информация. Однако, эти сети, как правило, представляют информацию в разном виде. Так, изначально компьютерные сети разрабатывались для передачи алфавитно-цифровой информации, которую часто называют просто данными, в результате у компьютерных сетей имеется и другое название - сети передачи данных, в то время как телефонные сети и радиосети были созданы для передачи только голосовой информации, а телевизионные сети передают и голос, и изображение [52].

Конвергенция телекоммуникационных и компьютерных сетей идет по нескольким направлениям. Прежде всего, наблюдается сближение видов услуг, предоставляемых клиентам [21]. Первая попытка создания мультисервисной сети, способной оказывать различные услуги, в том числе услуги телефонии и передачи данных привела к появлению технологии цифровых сетей с интегрированным обслуживанием (Integrated Services Digital Network, ISDN) [29]. Сегодня на роль глобальной мультисервисной сети нового поколения, часто называемой в англоязычной литературе Next Generation Network (NGN), или New Public Network (NPN) [80].

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

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

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

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

- Трансформация понятия услуги. Названия отдельных технологий и услуг обезличиваются - пользователю необходим один вид сервиса, под названием «соединение с сетью», подразумевающий возможность получения мультимедийной информации в разнообразных сочетаниях, определяемых абонентом в соответствии со своими индивидуальными запросами по качеству и скорости. Оператор должен предложить пользователю дружественный интерфейс и возможность оптимизации затрат, а пользователю остается лишь запросить у сети нужную услугу;

- Доминирующая роль протокола IP. Дешевизна решений на базе IP пр�