Адаптивная маршрутизация в сетях передачи данных с учетом самоподобия трафика тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат технических наук Комиссаров, Аркадий Михайлович

• Комиссаров, Аркадий Михайлович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Комиссаров, Аркадий Михайлович

Используемые сокращения

Введение

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

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

1.2. Особенности работы протокола маршрутизации 08РБ

1.3. Анализ особенностей самоподобного трафика

1.4. Постановка задачи исследований 30 Выводы по главе

2. Статистический анализ реализаций трафика на самоподобие

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

2.1.1. Реализация трафика УГАТУ

2.1.2. Реализация трафика сети провайдера Уфанет

2.1.3. Реализация трафика Уфимского государственного колледжа радиоэлектроники.

2.1.4. Трафик беспроводного Интернет-провайдера

2.1.5. Тестовые реализации.

2.2. Расчет показателей Херста исследуемых реализаций

2.2.1. График Я/З-статистики

2.2.2. График изменения дисперсии

2.2.3. График структурной функции

2.3. Анализ статистических показателей исследуемых рядов

2.3.1. Плотность распределения вероятностей исследуемых рядов

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

2.3.3. Энергетические спектры исследуемых рядов 56 Выводы по главе

3. Математическая модель процесса маршрутизации в пакетных сетях с учетом приоритета пакетов

3.1. Анализ современных подходов к задаче маршрутизации в сетях с коммутацией пакетов

3.1.1. Постановка задачи оптимального распределения потоков

3.1.2. Задача о динамической маршрутизации пакетов

3.2. Задача сравнения алгоритма распределения потоков с адаптивным алгоритмом маршрутизации для модели обслуживания трафика М/М/

3.2.1. Решение задачи при одинаковых потоках в сети

3.2.2. Решение задачи при разных потоках в сети

3.3. Задача сравнения алгоритма распределения потоков с адаптивным алгоритмом маршрутизации для модели обслуживания трафика fbm/D/

3.3.1. Решение задачи при одинаковых потоках в сети

3.3.2. Решение задачи при разных потоках в сети 83 Выводы по главе х

4. Моделирование работы адаптивного протокола маршрутизации с использованием фрактального фильтра предсказателя

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

4.1.1. Постановка задачи прогнозирования интенсивности трафика в сетях передачи данных

4.1.2. Синтез оптимального фильтра

4.1.3. Имитационная модель фрактального фильтра

4.1.4. Оценка эффективности фильтра предсказателя

4.2. Моделирование процессов маршрутизации и передачи пакетов в сети

4.2.1. Моделирование работы сети с трафиком М/М/

4.2.2. Моделирование работы сети с трафиком fbm/D/1 110 Выводы по главе

Введение диссертации (часть автореферата) на тему «Адаптивная маршрутизация в сетях передачи данных с учетом самоподобия трафика»

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

IP-TV, высокоскоростного доступа в Интернет с обеспечением высоких требований к качеству обслуживания - Quality of Service (QoS),4to требует увеличения пропускной способности сети, использования высококачественного оборудования функционирующего на основе протоколов стека TCP/IP. Для обеспечения QoS может использоваться дифференциальное или интегральное обслуживание, в основе которых лежат разделение трафика на классы приоритетного обслуживания и резервирование пропускной способности каналов. В связи с этим возникает задача более эффективного использования ресурсов сети.

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

До недавнего времени теоретическую базу для проектирования и моделирования систем распределения информационных потоков обеспечивала теория телетрафика, которая является одной из ветвей теории массового обслуживания, получившая свое развитие в работах ряда авторов: А. К. Эрланг, Л. Клейн-рок, Г. П. Башарин, А. Д. Харкевич, В. М. Вишневский и др. Наиболее распространенной моделью потока вызовов в теории телетрафика является стационарный пуассоновский поток, подходящий для сетей с коммутацией каналов. В работах зарубежных (W. Leland, D. Wilson, I. Noros) и российских исследователей (В. И. Нейман, Б. С. Цыбаков, О. И. Шелухин, В. С. Заборовский, А. Я. Городецкий) утверждается, что трафик в сетях с коммутацией пакетов обладает так называемым свойством «самоподобия». В результате теоретические расчеты характеристик современных систем распределения информации по классическим формулам дают некорректные результаты относительно длин очередей и времени задержек пакетов.

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

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

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

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

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

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

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

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

Практическая ценность

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

Основные научные результаты, выносимые на защиту:

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

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

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

4. Методика расчета пороговых значений для метода адаптивной маршрутизации с учетом двух приоритетов передаваемых пакетов для моделей трафика М/М/1 и fbm/D/l.

5. Имитационная модель сети передачи данных для моделей трафика fbm/D/1 и М/М/1, позволяющая оценивать эффективность предлагаемого метода маршрутизации.

Основные результаты работы обсуждались на следующих конференциях и семинарах: IV-VIII, X, XI Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций» (г. Уфа, г. Самара,

2003-2007, 2009, 2010); на VII Международном семинаре «Вычислительная техника и информационные технологии» CSIT (г. Уфа, 2005).

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

Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Комиссаров, Аркадий Михайлович

Основные выводы и результаты

1. Установлено на основе исследования рядов, описывающих интенсивности и межкадровые интервалы трафика сетей уровня распределения, по статистическим характеристикам и коэффициенту Херста, что трафик обладает свойствами стохастического самоподобия. Исследование рядов показало, что приемлемой моделью трафика сетей передачи данных уровня распределения является - 1ЪтЮ/1, которая, в отличие от традиционной для сетей связи модели трафика - М/М/1, позволяет адекватно оценивать задержки в сетях передачи данных.

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

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

4. Разработана методика расчета пороговых значений для предлагаемого метода адаптивной маршрутизации, на основе теории очередей с учетом двух приоритетов передаваемых пакетов для моделей трафика М/М/1 и fbm/D/1, позволяющая уменьшить среднюю задержку пакетов в сети в 2 - 5 раз для трафика fbm/D/1.

5. Разработана имитационная модель сети передачи данных в пакете matlab, включающая разработанный метод адаптивной двухпутевой маршрутизации с использованием фрактального фильтра-предсказателя, позволяющая моделировать работу сети с различными алгоритмами маршрутизации и моделями трафика fbm/D/1, М/М/1. Это позволило оценить эффективность работы предлагаемого метода маршрутизации. Средняя задержка пакетов в сети уменьшается 2-3 раза для трафика модели fbm/D/1.

ЗАКЛЮЧЕНИЕ

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

Список литературы диссертационного исследования кандидат технических наук Комиссаров, Аркадий Михайлович, 2011 год

1. Столингс В. Современные компьютерные сети. СПб.: Питер, 2003. -783с.

2. Олифер В. Г., Олифер Н. А. Компьютерные сети. Принципы, технологии, протоколы: учебник для вузов. 3-е изд. СПб.: Питер, 2009. -958с.

3. Мизин И. А., Кулешов А. П., Богатырев В. А. Сети коммутации пакетов. М.: Радио и связь, 1986. - 408с.

4. Куроуз Дж., Росс К. Компьютерные сети. 4-е изд. СПб.: Питер, 2004.- 765с.

5. Коммутаторы локальных сетей D-Link: учебное пособие. 4-е изд. М., 2006. - 162с.

6. Вегешна, Шринивас. Качество обслуживания в сетях 1Р.:Пер. с англ. -М. :Издательский дом «Виьямс», 2003. 368 с.

7. IP-телефония в компьютерных сетях: учебное пособие / И. В. Баскаков, А.В. Пролетарский. М.: Интернет - Университет информационных технологий; Бином. Лаборатория знаний, 2008. - 184с.

8. Network routing: algorithms, protocols, and architectures/ Deepankar Medhi, Karthikeyan Ramasamy. Morgan Kaufmann Publishers, 2007.

9. Стивене У. P. Протоколы TCP/IP. Практическое руководство / Пер. с англ. А. Ю. Глебовского. СПб.: «Невский Диалект» - «БХВ-Петербург», 2003. - 672с.

10. Березко М. П., Вишневский В. М., Е.В. Левнер Е. В., Федотов Е. В. Математические модели исследования алгоритмов маршрутизации в сетях передачи данных // Информационные процессы, том 1,№ 2, 2001,С. 103- 125 N

11. Бертсекас Д. Сети передачи данных / Перевод с англ. Н. Б. Лиханова; под ред. Б. С. Цибакова. М. : Мир, 1989. - 544с.

12. Вишневский В. M. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003. - 512с.

13. Руководство по технологиям объединенных сетей. 4-е изд.: Пер .с англ.- М.: Издательский дом «Виьямс», 2005. 1040 с.

14. Построение сетей интегрального обслуживания / Б. Я. Советов, С. А. Яковлев. JL: Машиностроение, 1990. - 331с.

15. Manual. DES 3800. - : D-Link, 2006.

16. Leland W. E., Taqqu M. S., Willinger W., Wilson D. V. On the self similar nature of Ethernet traffic // IEEE Transaction on networking. - Vol. 12. -1994. -№i.-P.2-15

17. Фрактальные процессы в телекоммуникациях / под ред. О. И. Шелухи-на. М.: Радиотехника, 2003. - 480 с.

18. Городецкий А. Я., Заборовский В. С. Информатика. Фрактальные процессы в компьютерных сетях: учебное пособие / СПб.: Изд-во СПбГТУ, 2000. 102с.

19. Анализ пропускной способности в пакетных сетях с приоритетами / А. М. Комиссаров // Проблемы техники и технологии телекоммуникаций: Сб. докл. IV Междунар. научн.-техн. конф. Уфа: УГАТУ, 2003. С. 106-107.

20. Методы оценки пропускной способности в пакетных сетях с различными типами нагрузки / А. М. Комиссаров // Проблемы техники и технологии телекоммуникаций: Сб. докл. V Междунар. научн.-техн. конф.- Самара, ПГАТИ, 2004. С. 54-55.

21. Постановка задачи для построения квазистатических адаптивных алгоритмов маршрутизации / А. М. Комиссаров // Проблемы техники и технологии телекоммуникаций: Сб. докл. VIII Междунар. научн.-техн. конф. Уфа, УГАТУ, 2007. С. 116-119.

22. Прогнозирование телетрафика на основе фрактальных фильтров сети / А. X. Султанов, В. X. Багманов, А. М. Комиссаров // Вестник УГАТУ: науч. журн. Уфимск. гос. авиац. техн. ун-та. 2007. Т.9, № 6(24). С. 217221.

23. Реализация трафика беспроводной сети IEEE 802.11b http://www.teletraffic.ru /traffic.

24. Дьяконов В. П. 8тиИпк 5/6/7: Самоучитель. М.: ДМК -Пресс, 2008. -784с.

25. Дьяконов В.П. Энциклопедия МаЛсаё 2001 \ и МаЛсас! 11. СОЛОН-Пресс, 2004. - 832с.

26. Федер Е. Фракталы: Пер. с англ. М.: Мир, 1991. - 254 с.

27. Тихонов В. И. Статистическая радиотехника. -2-е изд., перераб.и доп.-М.: Сов.радио, 1982.-624с.

28. Бронштейн И. Н., Семендяев К. А. Справочник по математике для инженеров и учащихся втузов.- 13-е изд. М.: Наука, Гл. ред. физ.-мат. лит., 1986.-544с.

29. Сергиенко А.Б. Цифровая обработка сигналов. СПб.: Питер, 2006. -751с.

30. Клейнрок Л. Вычислительные системы с очередями; пер. с англ. под ред Б. С. Цыбакова. М.: Мир ,1979.

31. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979.

32. Богуславский Л. Б. Основы построения вычислительных сетей для автоматизированных систем / Л. Б. Богуславский, В. И. Дрожников М.: Энергоатомиздат^ 1990. - 256с.

33. Методы повышения эффективности использования пропускной способности каналов связи в пакетных сетях с дифференциальным обслуживанием / А. М. Комиссаров // Электронные устройства и системы: межвузовский научный сборник. Уфа, УГАТУ, 2010. С. 172-178.

34. Теория телетрафика / Б. С. Лившиц, А. П. Пшеничников, А. Д. Харке-вич, учебник для вузов. М.: Связь, 1979. - 224 с.

35. Крылов В. В., Самохвалова С. С. Теория телетрафика и ее приложения. СПб.: БХВ-Петербург, 2005. - 288 с.

36. Конвей Р. В. Теория расписаний. М.: Наука, 1975 - 360с.

37. Балыбердин В. А. Оценка и оптимизация характеристик систем обработки данных. М.: Радио и связь, 1987. - 176с.

38. Расчет пропускной способности каналов низкоприоритетного трафика в сетях с дифференциальным обслуживанием / А. М. Комиссаров // Проблемы техники и технологии телекоммуникаций: Сб. докл. X Меж-дунар. науч.-техн. конф. Самара, ПГУТИ, 2009. С. 139-140.

39. A storage model with self-similar input Ilkka Noross. Queueing Systems, 16, 1994, 387-396

40. Задача сравнения потоковых и адаптивных алгоритмов маршрутизации для модели трафика fbm/D/1 / А. М. Комиссаров // Проблемы техники и технологии телекоммуникаций: Сб. докл. XI Междунар. научн.-техн. конф. -Уфа: УГАТУ, 2010. С. 74-78.

41. Андре Арго. Математика для электро- и радио инженеров. М.: Наука, 1967.-779с.

42. Градштейн И. С. Рыжик И. М. Таблицы интегралов, сумм, рядов и произведений. -5-е изд., перераб. -М.: Наука, 1971. 1108с.

43. Лаврентьев М.А., Шабат Б. В. Методы теории функций комплексного переменного. М.: Наука, 1973. - 736с.

44. Алексеев Е. Р., Чесноков О. В. MATLAB 7. М.: НТ Пресс, 2006. -464с.

45. Цифровая обработка сигналов: Справочник/ Л. М. Гольденберг, Б. Д. Матюшин, М. Н. Поляк. М.: Радио и связь, 1985. 312 с.

46. Адаптивные фильтры: Пер с англ ./под ред. К.Ф.Н. Коуэна и П.М. Гранта.-М.: Мир, 1988.- 392

47. Степанов С. Н. рсновы телетрафика мультисервисных сетей. М.: Эко-Трендз, 2010. - 392 с.

48. Моделирование самоподобного трафика пакетных сетей передачи данных в среде GPSS / А. М. Комиссаров // Проблемы техники и технологии телекоммуникаций: Сб. докл. VII Междунар. научн.-техн. конф. -Самара, ПГАТИ, 2006. С. 104-105.

49. Ряд Длинна ряда Среднее значение Макс, значение Мин. значение Средне квадр. откл. Коэфф. Херста / коэфф. детермин. ФРВ

50. Гр. измен. R/S Гр.изм. диспер. Гр.изм. структ. ф.

51. КиТ (УГАТУ) 288 420 кбайт/с 773 кбайт/с 4 кбайт/с 201 кбайт/с 0,94/0,99 0,99/ 0,5 0,92/ 0,98

52. Уфанет1 входящ. 510 45,83 Мбит/с 118 Мбит/с 5 Мбит/с 20,8 Мбит/с 0,97/0,99 0,98/ 0,68 0,85/ 0,99 Гаусса

53. Межкадр. интервал Уфимск. колледж радиоэл. 1070007 0,94 мс 64 мс 0,6*10"'с 1,97 мс

54. Шаг агр 500 2140 0,94 мс 3 мс 0,23 мс 0,45 мс 0,89/0,99 0,92/ 0,98 0,18/ 0,94

55. Шаг 1000 1070 0,94 мс 2,56 мс 0,28 мс 0,42 мс 0,9/0,99 0,93/ 0,98 0,23/ 0,92 Вейбула

56. Шаг 2000 535 0,94 мс 2,36 мс 0,35 мс 0,39 мс 0,9/0,99 0,93/ 0,96 0,28/ 0,88 Вейбула1. Беспров. сеть WiFi 0,5 с 44888 25,5 кбайт/с 1,3 Мбайт/с 0 38,5 кбайт/с 0,65 0,23 0,85/ 0,96 0,06/ 0,55 Парето

57. Юс 2244 25,5 кбайт/с 0,6 Мбайт/с 0 24,6 кбайт/с 0,52 0,15 0,67/ 0,96 0,03/0,32 Парето1с 22444 25,5 кбайт/с 1,2 Мбайт/с 0 35 кбайт/с 0,6 0,2 0,815/0,94 0,06/ 0,6 Парето5 с 4488 25,5 кбайт/с 0,87 Мбайт/с 0 27,3 кбайт/с 0,55 0,17 0,73/ 0,97 0,04/0,5 Парето

58. Межкадр, интервал беспров. сети 4 млн. 5,6 мс 0,302с 2 мкс 8,3 мс

59. Шаг 500 8000 5,6 мс 14 мс 0,46 мс 1,7 мс 0,78 0,1 0,9/ 0,99 0,13/ 0,86 Гаусса

60. Шаг 1000 4000 5,6 мс 12 мс 0,6 мс 1,5 мс 0,76 0,1 0,9/ 0,99 0,12/0,83 Гаусса

61. Шаг 5000 800 5,6 мс 9,9 мс 0,6 мс 1,3 мс 0,87/0,99 0,87 0,94 0,17/0,66 Гаусса

62. Fbm (Я =0,7) 1002 52,14 92 13,6 17,13 0,95/0,99 0,98/ 0,7 0,98/ 0,98 Гаусса

63. Fbm (шаг агрег. 3 ) 333 52,1 91 14 17 0,94/0,99 0,98 /0,73 0,98 /0,98 Гаусса

64. БГШ 1000 50 111 -18 20 0,62/0,99 0,56/ 0,98 0,007/ 0,1 Гаусса

65. БГШ (шаг агрег. 3 ) 333 48 85,1 15 11,2 0,63/0,99 0,53/0,98 0,008/0,08 Гаусса

66. Рисунок П.Б Модель трехузловой сети в пакете 8іти1іпк/Ма1;1аЬ7ю