Специальное математическое и программное обеспечение процессов управления интенсивностью передачи данных тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Платов, Виктор Вячеславович

• Платов, Виктор Вячеславович
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Платов, Виктор Вячеславович

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

Введение.

Глава 1. Управление потоком данных в компьютерных сетях с самоподобным трафиком.

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

1.2 Алгоритм управления интенсивностью потока данных TCP Reno.

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

1.4 Самоподобный (фрактальный) трафик компьютерных сетей с коммутацией пакетов.

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

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

1.5 Основные свойства самоподобных процессов.

1.5.1 Долгосрочная и краткосрочная зависимости, продолжительная память.

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

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

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

Глава 2. Математическая модель параметризованного процесса управления потоком TCP Reno.

2.1 Описание модели.

2.2 Переходы между фазами алгоритма управления потоком.

2.3 Вероятности потери пакетов.

2.4 Пропускная способность.

2.5 Анализ выбора параметров (Х,р,8.

2.6 Другие характеристики производительности.

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

Глава 3. Алгоритмизация управления потоком данных с использованием самоподобия сетевого трафика.^

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

3.2 Использование долгосрочной зависимости в алгоритме управления потоком данных.

3.3 Прогнозирование доступной полосы пропускания.

3.3.1 Предсказатель JIMCKO.

3.3.2 «Элементарный» предсказатель.

3.4 Управление перегрузкой с использованием результатов прогнозирования.

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

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

Глава 4. Оценка функционирования программной реализации алгоритма управления потоком МТСР.

4.1 Реализация алгоритма МТСР.

4.1.1 Реализация МТСР в среде ns-2.

Реализация МТСР в ядре операционной системы

FreeBSD 5.0.

4.2 Результаты имитационного моделирования МТСР в среде ns-2. юз

4.2.1 Топология с одним буфером «узкого» места.ЮЗ

4 2 2 Сравнение характеристик JIMCKO и «элементарного» предсказателей.

4.2.3 Топология с несколькими буферами «узкого» места.

4.3 Анализ функционирования алгоритма МТСР при передаче данных в сети Интернет.

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

Введение диссертации (часть автореферата) на тему «Специальное математическое и программное обеспечение процессов управления интенсивностью передачи данных»

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

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

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

Работа выполнена в рамках научного направления Воронежского государственного технического университета - «Вычислительные системы и программно-аппаратные комплексы».

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

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

1. Анализ современных подходов к управлению интенсивностью передачи данных.

2. Математическое моделирование процесса управления интенсивностью передачей данных TCP.

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

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

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

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

Научная новизна. К результатам работы, отличающимся научной новизной, относятся:

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

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

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

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

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

Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы реализованы в виде модуля МТСР ядра операционной системы FreeBSD 5.0, полученного в виде программной реализации алгоритма управления интенсивностью передачи данных и предназначенного для использования в составе транспортного протокола TCP. Данный программный модуль также используется в операционной системе коммутаторов и маршрутизаторов компаний D-Link International PTE Ltd. и H3C Technologies Ltd., о чем свидетельствуют соответствующие Акты внедрения.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на X-XI Международных открытых научных конференциях «Современные проблемы информатизации» (Воронеж, 2005-2006); Всероссийской научно-технической конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2005); Международной научно-практической конференции «Составляющие научно-технического прогресса» (Тамбов, 2005); Международной научно-технической конференции «Информационные технологии» (Воронеж, 2005); X Международной конференции «Системные проблемы надежности, качества информационных технологий» (Москва, 2005); IV Всероссийской научно-исследовательской конференции «Вузовская наука - региону» (Вологда, 2006); Всероссийской конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2006); Всероссийской научно-практической конференции «Новые технологии в современном здравоохранении» (Москва, 2007).

Публикации. Основные результаты диссертации опубликованы в 12 научных работах, в том числе, 3 без соавторов; 2 в изданиях, рекомендованных ВАК РФ [7, 20]. В работах, опубликованных в соавторстве и приведенных в списке литературы, лично соискателю принадлежит: в [7] - алгоритм управления интенсивностью потока данных с использованием прогнозирования доступной полосы пропускания; в [8] - способ оценки влияния параметров TCP на степень самоподобия трафика; в [9, 10, 11] - алгоритм «сглаживания» интенсивности отправки сегментов данных; в [12, 13] - математическая модель процесса управления потоком TCP Reno, учитывающая фазы медленного старта и экспоненциального отката; в [9, 14] - алгоритм управления очередями активных сетевых устройств с выборочным отбрасыванием пакетов; в [19] - подготовка и проведение эксперимента по сбору трафика беспроводной сети, его анализ.

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, списка литературы, включающего в себя 131 наименование и одного приложения. Основная часть работы изложена на 121 странице, содержит 1 таблицу и 47 рисунков.

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработанный в настоящей диссертации алгоритм управления потоком данных реализован как в среде сетевого эмулятора ns-2, так и в ядре операционной системы FreeBSD 5.0.

По результатам имитационного моделирования в ns-2 и экспериментальных исследований по передаче трафика через сеть Интернет можно сделать заключение о значительном выигрыше разработанного в диссертационной работе алгоритма управления интенсивностью потока данных по сравнению с наиболее распространенным на сегодня алгоритмом протокола TCP Reno. Например, превосходство нового алгоритма над TCP Reno с точки зрения доли потерянных пакетов или справедливости распределения полосы пропускания составило 75% и выше.

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Платов, Виктор Вячеславович

Основные результаты работы:

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

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

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

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

5. Предложен алгоритм управления интенсивностью передачи данных МТСР, основанный на прогнозировании доступной полосы пропускания.

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

7. Разработаны программные компоненты МТСР для системы имитационного моделирования ns-2, обеспечивающие сбор и статистическую обработку параметров функционирования МТСР.

8. Исследованы характеристики алгоритма МТСР для различных условий. Установлено, что данный алгоритм обладает в среднем на 4% большей пропускной способностью, обеспечивает уменьшение количества потерянных пакетов до 75%, а также имеет лучшие на 70% и более характеристики справедливости распределения доступной полосы пропускания по сравнению с современным алгоритмом управления интенсивностью потока данных TCP Reno.

9. Представленная практическая реализация алгоритма управления интенсивностью потоков данных с прогнозированием доступной полосы пропускания МТСР внедрена в программное обеспечение коммутаторов и маршрутизаторов компаний D-Link International PTE LTD и Huawei-3Com Technologies и используется для оптимизации обмена маршрутной информацией.

Заключение

Список литературы диссертационного исследования кандидат технических наук Платов, Виктор Вячеславович, 2007 год

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

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

3. Бершадский А.В. Статистическая модель рыночных событий. Электронный журнал "Исследовано в России", 1476-1488, 2002.

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

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

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

7. Кравец О.Я., Платов В.В., Поваляев А.Д. Использование самоподобия сетевого трафика в алгоритме управления потоком TCP. // Системы управления и информационные технологии, 2007, N1.1(27). С. 165-170.

8. Кравец О.Я., Платов В.В. Влияние параметров существующих алгоритмов управления потоком TCP на степень самоподобия трафика. // Современные проблемы информатизации в технике и технологиях: Сб. трудов. Вып. 10. Воронеж, 2005. - С. 145-147.

9. Кравец О.Я., Платов В.В. Об уменьшении степени самоподобия трафика пакетных сетей передачи данных. // Составляющие научно-технического прогресса: сборник материалов международной научно-практической конференции.- Тамбов: Першина, 2005. С. 203-205.

10. Кравец О.Я., Платов В.В. Уменьшение степени самоподобия трафика путем реализации TCP-сглаживания. // Новые технологии в научных исследованиях, проектировании, управлении, производстве: Труды Всерос. конф.- Воронеж: ВГТУ, 2005. С. 9-11.

11. Кравец О.Я., Платов В.В. Анализ причин самоподобия трафика в переполненном буфере активного сетевого устройства. // Современные проблемы информатизации в технике и технологиях. Сб. трудов. Вып. 11.-Воронеж, 2005.

12. Кравец О.Я., Платов В.В. Переполненный буфер активного сетевого устройства и причины самоподобия трафика. // Новые технологии в научных исследованиях, проектировании, управлении, производстве: труды Всерос. конф.- Воронеж: ВГТУ, 2006. С. 17-20.

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

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

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

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

17. Петров В.В., Платов В.В. Исследование самоподобной структуры телетрафика беспроводной сети. // Радиотехнические тетради, №3, М.: ОКБ МЭИ, 2004.- С.58-62.

18. Платов В.В. Математическая модель параметризованного протокола TCP. // Системы управления и информационные технологии, 2007, N1.1(27). -С. 183-187

19. Платов В.В. Использование TCP-сглаживания для уменьшения степени самоподобия трафика. // Информационные технологии: материалы Всероссийской научно-технической конференции. Воронеж: Научная книга, 2005.- С. 111-114.

20. Платов В.В. Обработка самоподобного трафика активными сетевыми устройствами: новый алгоритм управления очередями и его программная реализация. //Вузовская наука региону: сб. трудов. - Вологда, 2006.-С.124-128.

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

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

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

24. Abouzeid A., Roy S. and Azizoglu М. Stochastic Modeling of TCP over Lossy Links. // INFOCOM'OO, Tel-Aviv, Israel, March 2000.

25. Adas A. Using adaptive linear prediction to support real-time VBR video under RCBR network service model. // IEEE/ACM Transactions on Networking 6 635-644 c.

26. Anjum F., Tassiulas L. Fair Bandwidth Sharing Among Adaptive and Non-Adaptive Flows in the Internet. // IEEE INFOCOM'99, March 1999.

27. Allman M. et al. TCP Congestion Control. RFC-2581 IETF, April 1999.

28. Allman M. A Web Server's View of the Transport Layer. // ACM Computer Communication Review, October 2000.

29. Altman E., Avrachenkov K. and Barakat C. A stochastic model of TCP/IP with stationary ergodic random losses. // Tech. Rep. RR-3824, INRIA, Nov. 1999.

30. Altman E., Avrachenkov K., Barakat C. TCP modeling in the presence of nonlinear window growth. // ITC-17, Brazil, Sept. 2001.

31. Altman E., Jimenez T. NS simulator for beginners, Lecture notes, France, 2003.

32. Apisdorf J., Claffy K., Thompson K. and Wilder R. OC3MON: Flexible, Affordable, High-Performance Statistics Collection. August 1996.

33. Arlitt M. and Jin T. Workload Characterization of the 1998 World Cup Web Site. HP Technical Report http://www.hpl.hp.com/techreports/1999/HPL-1999-35Rl.html, September 1999.

34. Athuraliya S., Low S., Li V. and Yin Q. REM: Active Queue Management. // IEEE Network Magazine, 15(3), May/June 2001.

35. Baccelli F., Hong D. TCP is Max-Plus Linear. Tech. Rep. RR-3986, INRIA, 2000.

36. Baccelli F., Hong D. A.I.M.D., Fairness and Fractal Scaling of TCP Traffic. Tech. Rep. RR-4155, INRIA, April 2001.

37. Balakrishnan H., Padmanabhan V., Seshan S., Stemm M. and Katz R. TCP Behavior of a Busy Web Server: Analysis and Improvements. // IEEE INFO-COM'98, March 1998.

38. Balakrishnan H., Rahul H. and Seshan S. An Integrated Congestion Manage-mentArchitecture for Internet Hosts. // ACM SIGCOMM'99, August 1999.

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

40. Berners-Lee T. et al. The World Wide Web. Communications of the ACM, August 1994.

41. Berners-Lee T. et al. Hypertext Transfer Protocol HTTP/1.0. RFC-1945, IETF, May 1996.

42. Braden R. Extending TCP for Transaction Concepts. RFC-1379, IETF, November 1992.

43. Braden R. T/TCP TCP Extensions for Transactions. Functional Specifica-tion.RFC-1644, IETF, July 1994.

44. Braden B. et al. Management and Congestion Avoidance in the Internet. RFC-2309, IETF, April 1998.

45. Box G.E.P., Jenkins G.M. Time Series Analysis: Forecasting and Control. Holden Day, San Francisco, 1970.

46. Cardwell N., Savage S. and Anderson T. Modeling TCP latency. // INFO-COM'OO, Tel-Aviv, Israel, March 2000.

47. Chiu D., Jain R. Analysis of the increase/decrease algorithms for congestion avoidance in computer networks. // Computer Networks and ISDN 17. P. 114.

48. Claffy K., Miller G., Thompson K. The nature of the beast: recent traffic measurements from an Internet backbone. // INET'98.

49. Comer D. Internetworking with TCP/IP, Volume 1: Principles, Protocols, and Architecture, 3rd edition. Prentice-Hall, 1995.

50. Cormen Т., Leiserson C., Rivest R. Introduction to Algorithms. The MIT Press/McGraw-Hill, Cambridge, MA/New York, 1998.

51. Crovella M., Bestavros A. Self-similarity in world wide web traffic: evidence and possible causes. // IEEE/ACM Transactions on Networking 5 (6) (1997) 835-846.

52. Cunha C. R., Bestavros A. and Crovella M. E. Characteristics of WWW Cli-entbased Traces. Technical Report Boston University CS Department, April 1995.

53. Dumas V., Guillemin F. and Robert P. A Markovian Analysis of AIMD Algorithms, Adv. in App. Prob., vol. 34, no. 1.

54. Eggert L., Heidemann J. and Touch J. Effects of Ensemble-TCP. // ACM Computer Communication Review, January 2000.57