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

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

ПЕТРОВ Виталий Валерьевич

СТРУКТУРА ТЕЛЕТРАФИКА И АЛГОРИТМ ОБЕСПЕЧЕНИЯ КАЧЕСТВА ОБСЛУЖИВАНИЯ ПРИ ВЛИЯНИИ ЭФФЕКТА САМОПОДОБИЯ

05.12.13 - "Системы, сети и устройства телекоммуникаций"

АВТОРЕФЕРАТ

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

Москва, 2005

Работа выполнена на кафедре Радиоприемных устройств Московского энергетического института (Технического университета)

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

БОГАТЫРЕВ Евгений Алексеевич.

Официальные оппоненты - заслуженный деятель науки Российской Федера-

Защита состоится " 10 " февраля 2005 года в " 15 " часов " 30 " минут на заседании диссертационного совета Д 212.157.05 при Московском энергетическом институте (Техническом университете) по адресу: 111250, г. Москва, Красноказарменная ул., д. 17, аудитория А-402.

С диссертацией можно ознакомиться в библиотеке МЭИ (ТУ).

Отзывы в двух экземплярах, заверенные печатью, просим направлять по адресу: 111250, г. Москва, Красноказарменная ул., д. 14, Учёный совет МЭИ

ции, доктор технических наук, профессор ШЕЛУХИН Олег Иванович,

кандидат технических наук, доцент ТОМАШЕВСКИЙ Алексей Иосифович.

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

Научно-исследовательский институт вычислительных комплексов им. Карцева М.А. (НИИВК), г. Москва.

(ТУ).

Автореферат разослан

Учёный секретарь диссертационного со] кандидат технических наук, доцент

гачкина Т. И.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

намических систем, в том числе, хаотических (раздела реконструкции динамической системы по ее реализации), регрессионного анализа временных рядов, а также имитационное моделирование и расчеты на ПЭВМ.

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

1. Количественные и качественные характеристики самоподобного сетевого трафика.

2. Результаты анализа трафика в беспроводной сети стандарта ШЕЕ 802.11Ь.

3. Теоретические предпосылки возможности прогнозирования сетевого трафика.

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

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

принципы и схема организации.

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

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

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

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

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

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

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

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

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

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

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

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

Объем и структура работы. Настоящая диссертация содержит 197 страниц и состоит из введения, четырех глав, заключения и 2 приложений, включая 86 иллюстраций. Список литературы содержит 84 наименования.

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

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

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

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

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

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

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

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

• шейпинг

время, с время, с

• полисинг

время, с время, с

Рис. 2. Принципы функционирования принятых механизмов управления интенсивностью

трафика

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

На рис. 3 иллюстрируется идея функционирования данного алгоритма. Очевидно, чем ближе прогнозируемая пропускная способность С к профилю трафика, тем меньше потерь при пропускании такого трафика через канал с прогнозируемой пропускной способностью, тем меньше вносимые задержки пакетов, возникающие из-за буферизации и тем выше утилизация (использование) канала. Иначе говоря, пропускная способность канала теперь меняется динамически, отслеживая профиль трафика. Это основное отличие предложенной нами схемы от статического способа задания пропускной способности с помощью полисинга и шейпинга. Разработка алгоритма обеспечения качества об-

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

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

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

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

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

Произведено измерение показателя Хэрста (Н) семью методами: анализа дисперсии, нормированного размаха (R/S), периодограмм, абсолютных моментов, дисперсии остатков, Эбри-Вейча и Виттла. Подтверждено, что для всех

реализаций сетевого трафика коэффициент трафик относится к

классу персистентных процессов. Использование нами разнообразных методов оценки показателя Хэрста преследовало цель получить более достоверные результаты.

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

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

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

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

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

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

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

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

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

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

Далее в работе изучается и сравнивается эффективность применения следующих вариантов управления пропускной способности канала на реализациях трафика, изученных ранее в главе 2 диссертации: статическое задание пропускной способности, динамическое распределение пропускной способности с простым предсказателем (по последнему известному значению), динамическое распределение пропускной способности с авторегрессионным предсказателем первого и второго порядка, динамическое распределение пропускной способности с ЛЯМА-предсказателем, динамическое распределение пропускной способности с РЛЫМА-предсказателем.

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

соотношение сигнал/шум (8№1'), разрабатываются и вводятся специальные статистики - коэффициент недооценки Б+, выражающий отношение количества потерянной информации к общему количеству информации, которое нужно было обработать (пропустить через канал), и коэффициент переоценки О", отражающий отношение количества неиспользованной пропускной способности канала к общему количеству информации, которое нужно было пропустить через канал. Чем ближе прогностические оценки С(к) к действительным значениям трафика тем ближе к нулю коэффициенты и тем меньше потери и тем выше эффективность системы динамического управления пропускной способностью.

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

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

2 Выигрыши в ошибках недооценки и* и переоценки 0" для используемых предсказателей равны.

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

ActvDphi3_BMi/s

A âvDpbu _arl AâvDplus_u2 A dvOpliH^amta AâvDpliis_fannie

1 1 ! 1 1 ]

FARIMA >фецс ! [- ! 1

1 , 1 i 1

ЛВ<1}- >ф «Ж *ва 1 гЧ 1 1

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

Например, в работе показано, что применение простого предсказателя (для случая реально допустимых значений потерь) позволяет уменьшить потери пакетов и, соответственно, увеличить коэффициент использования канала на ~10 %, а показатель SNR*1, связанный с величиной джиттера, улучшить на 5459 % по сравнению с методом статического распределения пропускной способности. Исходя из критериев минимизации ресурсов процессора на реализацию предсказаний, а также получения наилучших характеристик для даль-

нейшего использования выбирается простой предсказатель.

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

синга, в которые внедряется модуль (на рис. 5 выделен) прогнозирования сетевого трафика и управления скоростью поступления маркеров3 в корзину.

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

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

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

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

щего отсчета агрегированного ряда х на время вперед. Исходя из

требований к величине возможных потерь, оценивается пропускная способность системы В результате размер буфера маркеров устанавливается равным Вс = С(п + 1) ■ Тс на время Д вперед. Таким образом, значение Вс (а вместе с ним и пропускная способность системы) будет меняться каждый интервал Д, отслеживая динамику изменения интенсивности трафика. Как было показано выше, при той же самой (в среднем) пропускной способности системы в режиме динамического управления пропускной способностью с прогнозированием удается достичь лучших показателей потерь и степени использования канала, нежели в случае реализации обычного полисинга.

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

Источником самоподобного трафика в данном эксперименте являлась одна из реализаций реального сетевого трафика, изученная в главах 2 и 3 настоящей диссертации, которая подавалась на узел N5. Посредством узла N5 полученный таким образом самоподобный поток упаковывался в иБР-пакеты и передавался в сторону получателя N4.

Кроме того, на схеме также имеется еще один (вспомогательный) источник трафика N0, генерирующий и транслирующий поток иБР-пакетов в направлении получателя N4. В целях данного эксперимента для оценки потенциальных возможностей алгоритма был выбран источник с постоянной интенсивностью (8 бит/с) генерирования пакетов (так называемый, СБИ-источник).

Трафики обоих источников (самоподобного и СБЯ) имеют в составе своего пути к получателю N4 один общий участок, одновременно являющийся "узким" местом сети - канал №-N4 с пропускной способностью 8 бит/с. В дан-

ном случае возникает задача эффективного разделения ресурсов канала №-N4 (его пропускной способности) между трафиками обоих источников N5 и N0.

Рис. 6. Схема эксперимента по моделированию статического и динамического режимов управления пропускной способностью канала

В процессе проведения эксперимента система рис. 9 изучалась в двух режимах:

в режиме статического разделения пропускной способности канала №-N4 между самоподобным и СБЯ трафиками. При этом некоторый ресурс этой пропускной способности С < 8 (бит/с) закрепляется постоянно за самоподобным трафиком, а оставшаяся пропускная способность 8 - С (бит/с) выделяется под трафик СБЯ. Однако, как уже отмечалось выше, такой способ малоэффективен вследствие высокой пачечности трафика источника N5;

в режиме динамического перераспределения пропускной способности канала №-N4 между самоподобным и СБЯ трафиками при помощи прогнозирования. В этом случае на основе информации, полученной в процессе мониторинга интенсивности самоподобного трафика в канале №-N2 в момент времени 1, делается прогноз потребностей потока источника N5 в пропускной способности С (бит/с) на участке №-N4 в последующий интервал времени 1 + А. На основании такой прогностической оценки самоподобному трафику в ка-

нале №-N4 выделяется требуемый ресурс С (бит/с), а СВЯ-трафику, соответственно оставшийся ресурс пропускной способности на время А.

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

Полученные результаты подтверждают выводы, сделанные ранее в главе 3 диссертации, о безусловном повышении эффективности системы вследствие применения метода динамического распределения пропускной способности с помощью прогнозирования: при том же самом объеме информации, полученной узлом N4 от источника N0, потерь в самоподобном трафике заметно (на 810%) меньше, а соотношение ЗИП"1 улучшается примерно на 54% при использовании алгоритма динамического распределения пропускной способности с прогнозированием.

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

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

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

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

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

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

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

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

8. Разработан алгоритм обеспечения качества обслуживания в условиях самоподобного трафика, использующий динамическое распределение пропускной способности канала и прогнозирование. Алгоритм основывается на базе известного принципа "корзина маркеров", в который внедрен предсказывающий модуль. Экспериментально показано, что предлагаемый механизм даже в случае простого предсказателя дает ощутимый выигрыш (8-10%) в уменьшении потерь и увеличении использовании канала, а также в величине показателя характеризующего джиггер, при самоподобном трафике по сравнению со статическим способом распределения пропускной способности.

9. С помощью имитационного моделирования исследовано функционирование и подтверждена эффективность предлагаемого алгоритма.

В Приложения вынесены распечатки листингов разработанных программ (пакеты

Список публикации по теме диссертации

1. Петров В.В., Платов В.В. Исследование самоподобной структуры телетрафика беспроводной сети // Радиотехнические тетради. - 2004. - № 30. -С. 58-62.

2. Петров В.В. Самоподобный сетевой трафик: от хаоса и фракталов к прогнозированию и качеству обслуживания // Конф. NEW2AN: Сборник трудов. - СПб., 2004. - С. 110-118. (На английском языке).

3. Петров В.В., Богатырев Е.А. Статистический анализ сетевого трафика // РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА: Тез. докл. Десятой Междунар. научно-техн. конференции студентов и аспирантов. Том 1. - М: Издательство МЭИ, 2-3 марта 2004.

4. Петров В.В. Самоподобие в сетевом трафике // 58-я Научная сессия РНТОРЭС им. А.С. Попова: Сборник трудов. Том 2 - М., 14-15 мая 2003. - С. 126.

5. Петров В.В., Богатырев Е.А. О самоподобном сетевом трафике // РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА: Тез. докл. Девятой Междунар. научно-техн. конференции студентов и аспирантов. Том 1. - М: Издательство МЭИ, 4-5 марта 2003. - С. 53 - 54.

Печ.л. 1,25 Тираж 100 Заказ 443 Типография МЭИ (ТУ), Красноказарменная ул., д. 13

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

Введение.

Глава 1. Современное состояние и основные понятия теории самоподобного телетрафика.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.6.3 Особенности технологии IEEE 802.1 lb.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на IX и X международных научно-технических конференциях студентов и аспирантов "Радиоэлектроника, электротехника, энергетика" в 2003 и 2004 годах, научно-техническом семинаре кафедры РПУ МЭИ в 2003 году, 58-й научной сессии РНТОРЭС им. А.С. Попова в 2003 году и Международной конференции "Next Generation Teletraffic 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 (Англия), и др. за плодотворные дискуссии, поддержку и понимание.

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

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

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

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

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

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

6. Экспериментально с помощью моделирования показано, что предлагаемый механизм в случае простого предсказателя дает заметный выигрыш (~ 8-10 %) в уменьшении потерь и увеличении эффективности использования канала при самоподобном трафике по сравнению со статическим способом распределения пропускной способности. При этом параметр SNR"1, характеризующий джиттер, улучшается на 58%. Повышение общей эффективности системы обусловлено более эффективным распределением ее ресурсов.

Заключение

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

Основным результатом проведенных в диссертационной работе теоретических и экспериментальных исследований является разработанный метод обеспечения качества обслуживания, основанный на прогнозировании и предназначенный для работы с самоподобным трафиком. Метод реализует принципы предоставления ресурсов "по-требованию" и динамического распределения пропускной способности каналов телекоммуникационных сетей. При этом достигается выигрыш 58%) в статистике SNR"1, характеризующей джиттер, а также в уменьшении потерь и увеличении использования ресурсов системы 10%) за счет более эффективного их распределения.

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

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

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

3. Подготовлен и выполнен оригинальный эксперимент по сбору и исследованию трафика беспроводной сети, подтверждающий наличие самоподобных свойств в трафике современных телекоммуникационных сетей, использующих технологии беспроводного доступа IEEE 802.11b в том числе. Полученные реализации трафика беспроводной сети представлены для публичного пользования в Интернет по адресу www.teletraffic.ru.

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

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

- произведено измерение показателя Хэрста (Н) семью методами: анализа дисперсии, нормированного размаха (R/S), периодограмм, абсолютных моментов, дисперсии остатков, Эбри-Вейча и Виттла. Обнаружено, что для всех реализаций сетевого трафика Н>0.5, то есть трафик относится к классу персистентных процессов. Использование разнообразных методов оценки показателя Херста преследовало цель получить более достоверные результаты. Усредненное значение Н для сетевого трафика Н-0.8. Зависимости коэффициента Н от уровня агрегирования (для рассматриваемых уровней) не выявлено;

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

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

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

6. Поставлена задача прогнозирования сетевого трафика в составе задачи динамического (адаптивного) распределения пропускной способности канала. Определен алгоритм проверки прогнозируемости и оценки качества прогноза. Наряду с классической оценкой сигнал/шум разрабатываются другие оценки: коэффициент потерь и коэффициент недоиспользования.

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

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

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

Ю.Экспериментально с помощью моделирования показано, что предлагаемый механизм даже в случае простого предсказателя дает заметный выигрыш (~ 8-10 %) в уменьшении потерь и увеличении эффективности использования канала при самоподобном трафике по сравнению со статическим способом распределения пропускной способности. При этом параметр SNR'1, характеризующий джиттер, улучшается на 58%. Повышение общей эффективности системы обусловлено более эффективным распределением ее ресурсов.

1. Значит, нужные книги ты в детстве читал.

2. В. Высоцкий "Баллада о борьбе"

3. Leland W.E., Taqqu M.S., Willinger W., and Wilson D.V. On the self-similar nature of ethernet traffic // IEEE/ACM Transactions of Networking, 2(1), 1994. -P. 1-15.

4. Цыбаков Б.С. Модель телетрафика на основе самоподобного случайного процесса // Радиотехника. 1999. - № 5. - С. 24-31.

5. В.И. Нейман. Новое направление в теории телетрафика // Электросвязь. -1998.-№7. -С. 27-30.

6. Tsybakov B.S., Georganas N.D. Self-similar processes in communications networks // IEEE Trans. Inform. Theory, vol. 44. Sep.1998. - P. 1713-1725.

7. Tsybakov B.S., Georganas N.D. Self-similar traffic: upper bounds to buffer-overflow probability in an ATM queue // Proceedings of CCBR'97, the Canadian Conference on Broadband Research, Ottawa. 1997.-P. 137-148.

8. Gneiting Т., Schlather M. Stochastic models which separate fractal dimension and Hurst effect // NRCSE-TRS. Sep. 20, 2001. - № 069.

9. Кендел M. Временные ряды: Пер. с англ. и предисл. Ю.П. Лукашина. — М: Финансы и статистика, 1981. 199с.

10. Feng W., Tinnakornsrisuphap P. The Failure of TCP in High-Performance Computational Grids // SC2000: High-Performance Network and Computing Conference, Dallas, TX. November, 2000.

11. Заборовский B.C. Методы и средства исследования процессов в высокоскоростных компьютерных сетях: Диссертация на соискание ученой степени доктора технических наук СПб., 1999 г.

12. Городецкий А.Я., Заборовский B.C., Информатика. Фрактальные процессы в компьютерных сетях / Учебное пособие. — СПб.: СПбГТУ, 2000.

13. Grabbe О. Chaos and Fractals in Financial Markets, www.aci.net/kalliste/.

14. Найденов В.И., Кожевникова И.А. Эффект Харста в геофизике // Природа. — 2000.-№1.

15. Шелухин О.И., Тенякшев A.M., Осин А.В. Фрактальные процессы в телекоммуникациях. Монография: Под ред. О.И. Шелухина. — М.: Радиотехника, 2003. 480 с.

16. Криштофович А.Ю. Самоподобие трафика сети ОКС №7 // МКИССиТ, Санкт- Петербург, 2002 г.

17. Бершадский А.В. Статистическая модель рыночных событий. Электронный журнал "Исследовано в России", 1476-1488, 2002 г. http://zhurnal.ape.relarn.ru/articles/2002/132.pdf.

18. Veres A., Boda М. The Chaotic Nature of TCP Congestion Control // Proceedings of IEEE INFOCOM'2000, March 2000.

19. Veres A., Kenesi Zs., Molnar S., Vattay G. On the Propagation of Long-Range Dependence in the Internet // Proc. ACM SIGCOMM 2000. Stockholm, Sweden, Sep. 2000.

20. Kugiumtzis D., Boudourides M. Chaotic Analysis of Internet Ping Data: Just a Random Generator? // SOEIS meeting at Bielefeld, March 27-28, 1998.

21. Петров B.B. Самоподобие в сетевом трафике // 58-я Научная сессия РНГОРЭС им. А.С. Попова: Сборник трудов. Том 2. М., 14-15 мая 2003. -С. 126.

22. Петров В.В., Платов В.В. Исследование самоподобной структуры телетрафика беспроводной сети // Радиотехнические тетради. — 2004. — № 30.-С. 58-62.

23. Петров В.В., Богатырев Е.А. О самоподобном сетевом трафике // РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА: Тез. докл. Девятой Междунар. научно-техн. конференции студентов и аспирантов. Том 1. М: Издательство МЭИ, 4-5 марта 2003. - С. 53 — 54.

24. Петров В.В., Богатырев Е.А. Статистический анализ сетевого трафика // РАДИОЭЛЕКТРОНИКА, ЭЛЕКТРОТЕХНИКА И ЭНЕРГЕТИКА: Тез.докл. Десятой Междунар. научно-техн. конференции студентов и аспирантов. Том 1. М: Издательство МЭИ, 2-3 марта 2004.

25. Park К., Willinger W. Self-Similar Network Traffic and Performance Evaluation. John Wiley & Sons, 2000.

26. Вегешна Ш. Качество обслуживания в сетях IP.: Пер. с англ. М.: Изд. дом "Вильяме", 2003. -368 с.

27. Policing and Shaping Overview, QC: Cisco IOS Release 12.0 Quality of Service Solutions Configuration Guide, http://www.cisco.com.

28. Ostring S., Sirisena H. The Influence the Long-Range Dependence on Traffic Prediction // Proceedings of ICC'Ol. Helsinki, June 2001.

29. Miloucheva I., Muller E., Anzaloni A. A practical appoach to forecast Quality of Service parameters considering outliers, 2003. http://www.ist-intermon.org/workshop/papers/06 03 end arima corrected.pdf.

30. Beran J. Statistical Methods for Data with Long-Range Dependence // Statistical Science, Volume 7, Issue 4. -1992. P. 404-416.

31. Foag J., Wild T. Traffic Prediction Algorithm for a Speculative Network Processor // 17th Intl. Symposium for High Performance Computing Systems and Applications HPCS 2003. Sherbrooke, May 2003.

32. Trajkovic L., Neidhardt A. Internet traffic prediction // Centre for Systems Science, Simon Fraser University, Vol. 12, Issue 1. Mar. 2000.

33. Koucheryavy Y., Harju J. A novel approach for self-similar traffic prediction. / Proceedings of the St. Petersburg Regional International Teletraffic Seminar, St. Petersburg, Russia, January 29 February 1. - 2002. - P. 172 - 179.

34. Анищенко B.C. Знакомство с нелинейной динамикой // Лекции соросовского профессора. Саратов, 2000.

35. Шредер М. Фракталы, хаос, степенные законы. Миниатюры из бесконечного рая. Москва-Ижевск, 2001.

36. Уайндер С. Справочник по технологиям и средствам связи. М.: "Мир", 2000.

37. Gripenberg G., Norros I. On the prediction of fractal Brownian motion // Journal of Applied Probability, vol.33. -1996. P. 400-410.

38. Fowler H. J., Leland W. E. Local Area Network Traffic Characteristics, with Implications for Broadband Network Congestion Management // IEEE JSAC, 9(7) . September 1991. - P. 1139-1149.

39. Paxson V., Floyd S. Wide-Area Traffic: The Failure of Poisson Modeling // IEEE/ACM Transactions on Networking, 1995.

40. Кузнецов С.П. Динамический хаос (курс лекций). М.: Изд-во Физико-математической литературы, 2001. - 296 с.

41. Малинецкий Г.Г., Потапов А.Б. Современные проблемы нелинейной динамики. М.: Едиториал УРСС, 2002. 360с.

42. Theiler J. Some comments on the correlation dimension of 1/f noise // Phys. Lett. A. 155.-1991.-P. 480-493.

43. Olowoyeye G., Kim В., Chandra K. Modelling Spectral Features in TCP Traffic. Submitted to ITC'99, October 1998.

44. Chandra K., You C., Olowoyeye G. and Thompson C. Non-linear Time-Series Models of Ethernet Traffic // Submitted to INFOCOM'99, July 1998.

45. Erramilli A., Singh R.P., Pruthi P. An Application of Deterministic Chaotic Maps to Model Packet Traffic // Queueing Systems, 20(3) . -1995. P. 171-206.

46. Potapov A., Kurths J. Correlation integral as a tool for distinguishing between dynamics and statistics in time series data // Physics D. 120. -1998. P.369-385.

47. Brock W. A., Dechert W. D., Scheinkman J.A. and LeBaron B. A test for independence based on correlation dimension // Econometric Reviews 15. 1996. -P. 197-235.

48. Kennel M. В., Brown R. and Abarbanel H. D. I. Determining embedding dimension for phase-spase reconstruction using a geometrical construction // Phys. Rev. A 45. 1992. - P. 3403.

49. Gao J.B., Cao Y., Lee J-M. Principal component analysys of l/f noise // Physics Letters A, 314. 2003. - P. 392-400.

50. Hegger R., Kantz H., Schreiber T. Practical implementation of nonlinear time series methods: The TISEAN package, 1998.

51. Eckmann J.P., Kamphorst S. and Ruelle D. Recurrence plots of dynamical systams // Europhys. Lett. 4. 1987. - P. 973-977.

52. Голяндина Н.Э., Некруткин B.B., Браулов K.A. Метод "Гусеница''-SSA: анализ временных рядов, 2002. http ://www. gistatgroup.com/gusZssaan.pdf.

53. Ghaderi М. On the Relevance of Self-Similarity in Network Traffic Prediction, 2003. http://www.cs.uwaterloo.ca/cs-archive/CS-2003/28/TR-CS-2003-28.pdf.

54. Sadec N., Khotanzad A., Chen T. ATM Dynamic Bandwidth Allocation Using F-Arima Prediction Model, http://snoopy.seas.smu.edu/papers/icccn03 .pdf.

55. Айвазян С.А. Прикладная статистика. Основы эконометрики: Учебник для вузов: В 2 т. 2-е изд. испр. Т.2.: Айвазян С.А. Основы эконометрики. — М.: ЮНИТИ-ДАНА, 2001. - 432 с.

56. Dang Т. D., Sonkoly В., Molnar S. Fractal Analysis and Modelling of VoIP Traffic // NETWORKS2004, Vienna, Austria, June 13-16, 2004.

57. Пономарев Д.Ю. Вероятностно-временные характеристики асинхронных систем обработки интегральной информации с учетом влияния свойства самоподобия. Диссертация на соискание ученой степени кандидата технических наук Красноярск, 2002.

58. Chong S., Li S., Grosh J. Predictive Dynamic Bandwidth Allocation for Efficient Transport of Real-Time VBR Video over ATM // IEEE Journal on Selected Areas in Communications, Vol.13, No 1. January 1995. - P. 12-23.

59. Кучерявый E.A. Управление трафиком и качество обслуживания в сети Интернет. — СПб.: Наука и Техника, 2004. 336 с.

60. Petroff V. Self-Similar Network Traffic: From chaos and Fractals to Forecasting and QoS // NEW2AN. St.Petersburg, 2004. - P. 110-118.

61. Traffic Modeling Based on FARIMA Models. Xue F., Liu J., Shu Y., Zhang L., Yang O.W.W // CCECE99 Proceed. May 1999. - P. 162-167.

62. A High Speed Implementation of Adaptive Shaping for Dynamic Bandwidth Allocation. Brown C., Sirkay V., Uriona H., Seetharam S., Yousefi E., Petr D., Niehaus D., Frost V., Evans J., Minden G. // IEEE Communications Magazine, 1997.

63. Chiruvolu G., Sankar R., Ranganathan N. Adaptive VBR Video Traffic Management for Higher Utilization of ATM Networks // ACM SIGCOMM, Vol. 28, Issue 3. July 1998. - P. 27-40.

64. Park K., Kim G., Crovella M. On the relationship between file sizes, transport protocols, and self-similar network traffic // Proceedings of the Fourth International Conference on Network Protocols (ICNP'96) . -1996. P.l71-180.

65. Заборовский B.C., Рязанов М.Г. Управление в компьютерных сетях: концепция сетевых процессоров // Демиург. 1998. - №1, — С. 47-81.

66. Paxson V., Floyd S. Wide-Area Traffic: The Failure of Poisson Modeling // IEEE/ACM Transactions on Networking. 3(3) . - 1995. - P. 226-244.

67. Fowler H.J., Leland W.E. Local area network traffic characteristic, with implications for broadband network congestion management // IEEE Journal on Selected Areas in Communications, vol. 9. 1991. - P. 1139-1149.

68. Zhao H., Ansari N., Shi Y.Q. A Fast Non-linear Algorithm for Video Traffic Prediction // ITCC, 2002.

69. Chen В., Peng S., Wang K. Traffic Modeling, Prediction, and Congestion Control for High-Speed Networks: A Fuzzy AR Approach // IEEE Trans. On Fuzzy Systems Vol. 8. 2000. - №5.

70. Лившиц B.C., Пшеничников А.П., Харкевич А.Д. Теория телетрафика // М.: "СВЯЗЬ", Учебник для вузов.2-е изд., перераб. и доп., 1979. 224 с.

71. Столлингс В. Современные компьютерные сети: Питер, 2-е изд. (пер. с англ. Леонтьева А.), 2003 г. 784 с.

72. Brenner P. A Technical Tutorial on the IEEE 802.11 Protocol // Breezecom, 1997.

73. Grassberger P., Procaccia I. Characterization of strange attractors I I Phys. Rev. Lett. 58. 1983. - P. 2387-2389.

74. Уолрэнд Дж. Телекоммуникационные и компьютерные сети. Вводный курс. Москва: Постмаркет, 2001.- 480 с.

75. Ершов М.А., Кузнецов Н.А. Теоретические основы построения сети с интеграцией служб. М.: ИППИ РАН, 1995.

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

77. Гмурман В.Е. Теория вероятностей и математическая статистика. Учеб. пособие для вузов. 8-е изд., стер. - М.: Высш. шк., 2002. - 479 с.

78. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения. Учеб. пособие для втузов. - 2-е изд., стер. - М.: Высш. шк. , 2002. - 383с.

79. Баскаков С.И. Радиотехнические цепи и сигналы.: Учеб. для вызов по спец. "Радиотехника". 2-е изд. перераб. и доп. - М.: Высш. шк., 1998 - 448 с.

80. Кирьянов Д.В. Самоучитель MathCad 2001. СПб.: БХВ-Петербург, 2002. -544с.

81. Документация и программное обеспечение сетевого симулятора ns-2: http ://www-mash.C S .Berkeley .EDU/ns.

82. Архив трафика: http://ita.ee.lbl.gov.

83. Пакет программ для анализа временных реализаций методами нелинейной динамики TISEAN v2.1 :http://lists.mpipksdresden.mpg.de/~tisean/TISEAN2.1.

84. Программа FRACTAN v4.4, предназначенная для фрактального анализа временных реализаций: http://impb.psn.ru/~svchyov/soft.shtml.

85. Selfis vO.lb программа для анализа экспоненты Хэрста разработки Thomas Karagiannis: http://www.cs.ucr.edu/~tkarag.

86. Официальный сайт проекта VINT: http://www.isi.edu/nsnam/vint/index.html.