Электронная библиотека российских диссертаций Электронная библиотека российских диссертаций Электронная библиотека российских диссертаций Электронная библиотека российских диссертаций Электронная библиотека российских диссертаций Электронная библиотека российских диссертаций
Каталог

Обратная связь

Я ищу:

Содержимое электронного каталога российских диссертаций

Диссертационная работа:

Петров Виталий Валерьевич. Структура телетрафика и алгоритм обеспечения качества обслуживания при влиянии эффекта самоподобия : Дис. ... канд. техн. наук : 05.12.13 : Москва, 2004 199 c. РГБ ОД, 61:05-5/1891


Для получения доступа к работе, заполните представленную ниже форму:


*Имя Отчество:
*email



Содержание диссертации:

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

Введение 7

Глава 1. Современное состояние и основные понятия теории

самоподобного телетрафика 16

  1. Понятие фрактальности 16

  2. Самоподобный (фрактальный) телетрафик 18

  1. Проблема самоподобного телетрафика 18

  2. Определения самоподобного процесса 19

1.3 Основные свойства самоподобного трафика 22

  1. Медленно, быстро убывающие зависимости, продолжительная память 25

  2. Понятие коэффициента Херста 27

  3. Понятие фрактальной размерности и ее связь с коэффициентом Хэрста 30

  4. Распределения с "тяжелыми хвостами" 35

  5. Аспекты теории нелинейной динамики 38

1.4 Постановка задачи обеспечения качества обслуживания (QoS) в
условиях влияния эффекта самоподобия 43

1.5 Выводы по главе 1 51

Глава 2. Статистический анализ реализаций сетевого трафика 53

2.1 Описание реализаций сетевого трафика 53

  1. Реализация сетевого трафика BC-Oct89Ext.TL 53

  2. Реализация сетевого трафика LBL-PKT-5.TCP 56

  3. Реализация сетевого трафика LBL-TCP-3 57

2.2 Формирование временных рядов 59

  1. Процедура агрегирования 59

  2. Тестовые реализации (хаос и белый шум) 67

  3. Логарифмированные реализации 68

2.3 Классический анализ 70

  1. Плотности распределения 71

  2. Автокорреляционные функции 73

  3. Энергетические спектры 78

  1. Исследование показателя Хэрста реализаций 80

  2. Исследование сетевого трафика методами нелинейной динамики... 82

  1. Концепция суррогатных данных 84

  2. Идея реконструкции аттрактора 86

  3. Ложные ближайшие соседи 86

  4. Вычисление корреляционного интеграла 88

  5. Проверка гипотезы о статистической независимости (BDS-тест) 94

2.6 Эксперимент по сбору трафика в беспроводной сети 95

  1. Постановка эксперимента по сбору трафика беспроводной сети 95

  2. Характеристика реализаций 97

2.6.3 Особенности технологии IEEE 802.lib 98

2.6.2 Анализ результатов обработки трафика беспроводной сети. 101

2.7 Выводы по главе 2 106

Глава 3. Исследование возможностей прогнозирования

самоподобного телетрафика .-.„

  1. Предпосылки к прогнозированию самоподобного трафика ПО

  2. Задача динамического управления пропускной способностью канала с помощью прогнозирования. Оценки выигрыша 113

  3. Анализ алгоритмов управления пропускной способностью канала. 118

  1. Статическое задание пропускной способности 119

  2. Динамическое распределение пропускной способности с простым предсказателем 121

  3. Динамическое распределение пропускной способности с авторегрессионным предсказателем первого порядка 123

  4. Динамическое распределение пропускной способности с авторегрессионным предсказателем второго порядка 125

  1. Динамическое распределение пропускной способности с ARMA- предсказателем 126

  2. Динамическое распределение пропускной способности с

F ARIMA-предсказателем 128

3.4 Сравнение алгоритмов динамического распределения пропускной
способности и выбор метода прогнозирования 130

3.5 Выводы по главе 3 135

Глава 4. Метод обеспечения качества обслуживания в условиях
самоподобного телетрафика
137

  1. Принцип динамического управления пропускной способность 137

  2. Алгоритмы контроля и управления трафиком 141

Алгоритм полисинга на основе механизма "корзина

маркеров" 141

Алгоритм шейпинга на основе механизма "корзина

маркеров" 144

  1. Разработка метода управления трафиком для работы в условиях влияния эффекта самоподобия 146

  2. Моделирование механизма динамического управления пропускной способностью канала с использованием прогнозирования в среде ns-2 148

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

4.6 Выводы по главе 4 163

Заключение 165

Список литературы 169

Приложение 1 176

Приложение 2 180

Акты о внедрении 198

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

АСШС

ско ссшс

СУС ФБД

ASCII

ARMA

ARIMA

Автокорреляционная функция Асимптотическое самоподобие в широком смысле Быстро убывающая зависимость Медленно убывающая зависимость

Броуновское движение Программное обеспечение Распределение с "легкими хвостами" Распределение с "тяжелыми хвостами" Среднеквадратическое отклонение

Строгое самоподобие в широком смысле Самоподобие в узком смысле Фрактальное броуновское движение

Фрактальный гауссовский шум

Центральная предельная теорема

American standard code for information

(американский стандартный код обмена информацией)

Asynchronous transfer mode

(асинхронный режим передачи)

Autoregressive

(авторегрессия)

Autoregressive moving average

(авторегрессионное скользящее среднее)

Autoregressive integrated moving average

(авторегрессионное проинтегрированное скользящее

среднее)

Constant bit rate

(постоянная скорость передачи)

CIR - Committed information rate

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

CRC - Cyclical redundancy check

(контроль с помощью циклического избыточного кода)

CSMA/CA - Carrier Sense Multiple Access with Collision Avoidance

(множественный доступ с контролем несущей и

предотвращением конфликтов)

DSSS - Direct-Sequence Spread Spectrum

(расширение спектра с помощью прямой

последовательности)

FARIMA - Fractionally differenced autoregressive integrated moving average (Фрактальное авторегрессионное проинтегрированное

скользящее среднее) FNN - False Nearest Neighbors

(ложные ближайшие соседи)
OSI - Open system interconnection

(взаимодействие открытых систем)
QoS - Quality of Service

(качество обслуживания) VBR - Variable bit rate

(непостоянная скорость передачи)
VC - Virtual channel

(виртуальный канал)



Введение диссертации:

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

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

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

Однако, в 1993 году группа американских исследователей W.Leland, M.Taqqu, W.Willinger и D.Wilson опубликовали результаты своей новой работы, которая в корне изменила существующие представления о процессах, происходящих в телекоммуникационных сетях с коммутацией пакетов. Эти исследователи изучили трафик в информационной сети корпорации Bellcore и обнаружили, что потоки в ней нельзя аппроксимировать простейшими и, как следствие, они уже имеют совершенно иную структуру, чем принято в классической теории телетрафика. В частности, было установлено, что трафик

такой сети обладает так называемым свойством "самоподобия", т.е. выглядит качественно одинаково при почти любых масштабах временной оси, имеет память (последействие), а также характеризуется высокой пачечностью1.

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

Таким образом, образовалась "проблема самоподобия телетрафика", которой за последние 11 лет посвящено более тысячи работ и которая до сих пор не утратила своей актуальности. Среди зарубежных ученых, активно занимающихся этой проблемой, необходимо выделить уже упоминавшихся авторов, которым принадлежат наиболее фундаментальные труды в этом направлении, а также К. Park, В. Ryu, V. Paxson, R. Mondragon и др. Среди отечественных исследователей необходимо отметить работы В.И. Неймана, Б.С. Цыбакова, Н.Б. Лиханова, О.И. Шелухина, B.C. Заборовского, А.Я. Городецкого и др.

Несмотря на значительную популярность этой тематики и продолжительный (11 лет) период ее активного изучения, приходится констатировать, что до сих пор остается множество вопросов и нерешенных задач. Перечислим, на наш взгляд, основные из них:

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

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

1 Коэффициент пачечности (пачечность) для заданного потока соответствует отношению пиковой интенсивности процесса поступления заявок на обслуживание к его среднему значению.

параметров и показателей качества систем распределения информации при влиянии эффекта самоподобия;

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

Настоящая диссертация посвящена решению последней из перечисленных, но далеко не последней по степени важности задаче.

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

Формирование основных идей и принципа функционирования алгоритма обеспечения качества обслуживания в условиях самоподобного трафика;

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

Анализ прогнозируемости сетевого трафика как базовой концепции разрабатываемого алгоритма;

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

Проведение испытаний (имитационное моделирование) и оценка эффективности разработанного алгоритма.

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

Научная новизна. В диссертации получены следующие новые научные и практические результаты:

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

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

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

  2. Обнаружены регулярные периодические составляющие в агрегированном сетевом трафике.

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

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

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

используется в демонстрационной лабораторной работе по дисциплине "Методы и устройства цифровой обработки сигналов" на кафедре РПУ МЭИ (ТУ). Имеется соответствующий Акт об использовании.

Материалы данной работы вошли в НИОКР по теме: «Сопряжение периферийных земных станций спутниковой связи с абонентскими пунктами информационно-коммуникационной системы», целью которой являлось сокращение затрат на аренду частотно-энергетического ресурса спутника-ретранслятора "Ямал-200" при проектировании и построении Ведомственной Технологической Сети Спутниковой Связи для Министерства Российской Федерации по атомной энергии, о чем свидетельствует соответствующий Акт внедрения.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на IX и X международных научно-технических конференциях студентов и аспирантов "Радиоэлектроника, электротехника, энергетика" в 2003 и 2004 годах, научно-техническом семинаре кафедры РПУ МЭИ в 2003 году, 58-й научной сессии РНТОРЭС им. А.С. Попова в 2003 году и Международной конференции "Next Generation Teletrafflc and Wired/Wireless Advanced Networking (NEW2AN)" 2004 r.

По теме диссертации автором опубликовано 5 печатных работ.

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

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

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

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

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

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

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

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

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

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

В рамках данной диссертационной работы проведено оригинальное исследование особенностей структуры трафика современной беспроводной сети стандарта IEEE 802.1 lb.

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

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

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

Изучается и сравнивается эффективность применения различных вариантов управления (алгоритмов прогнозирования) пропускной способности канала на реализациях трафика.

Для вычисления выигрыша, получаемого от применения алгоритма динамического управления с прогнозированием, основные характеристики

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

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

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

Для проверки полученных в настоящей диссертационной работе результатов с помощью имитационного моделирования на ПЭВМ был поставлен эксперимент по анализу эффективности алгоритма динамического управления пропускной способностью с прогнозированием в условиях самоподобного телетрафика. Моделирование производилось в среде популярного сетевого эмулятора ns-2. Источником самоподобного трафика в данном эксперименте является одна из реализаций реального сетевого трафика, изучаемая в главах 2 и 3 настоящей диссертации.

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

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

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

Хочу выразить искреннюю благодарность своему научному руководителю к.т.н., проф. Е.А. Богатыреву (МЭИ, Россия) за координирование, помощь в написании и подготовке к защите настоящей диссертации, д.т.н., проф. СМ. Смольскому (МЭИ, Россия) за ценные рекомендации и внимание, проявленное к данной работе. Отдельное спасибо хочется высказать моим коллегам: Виктору Платову, в сотрудничестве с которым была выполнена работа по сбору и анализу трафика беспроводной сети, а также Дмитрию Соколову, который сделал ряд замечаний к первоначальному варианту работы.

Также выражаю особую признательность Н.Б. Лиханову (ИППИ РАН, Россия), М.В. Капранову (МЭИ, Россия), А.С. Дмитриеву (ИРЭ РАН, Россия), Е.А. Кучерявому (TUT, Финляндия), А. Осину (МГУ С, Россия), А. Саенко (Финляндия), В.И. Найденову (ИНВП РАН, Россия), I. Kaplan (США), D. Wischik (Англия), и др. за плодотворные дискуссии, поддержку и понимание.

Реклама


2006-20011 © Каталог российских диссертаций