Помощь в написании студенческих работ
Антистрессовый сервис

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

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

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

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

Содержание

  • Перечень сокращений
  • Глава 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. Анализ выбора параметров (Х, р,
    • 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
  • Реализация МТСР в ядре операционной системы
  • FreeBSD
    • 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.

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

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

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

Разрабатывается алгоритм управления потоком, использующий предсказатель 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 и используется для оптимизации обмена маршрутной информацией.

Заключение

.

Показать весь текст

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

  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. В.В., Платов В. В. Исследование самоподобной структуры телетрафика беспроводной сети. // Радиотехнические тетради, № 3, М.: ОКБ МЭИ, 2004.- С.58−62.
  17. В.В. Математическая модель параметризованного протокола TCP. // Системы управления и информационные технологии, 2007, N1.1(27). -С. 183−187
  18. В.В. Обработка самоподобного трафика активными сетевыми устройствами: новый алгоритм управления очередями и его программная реализация. //Вузовская наука региону: сб. трудов. — Вологда, 2006.-С.124−128.
  19. .С. Модель телетрафика на основе самоподобного случайного процесса. // Радиотехника. 1999. — № 5. — С. 24−31.
  20. О.И., Тенякшев A.M., Осин А. В. Фрактальные процессы в телекоммуникациях. Монография: Под ред. О. И. Шелухина. М.: Радиотехника, 2003. — 480 с.
  21. С. Справочник по технологиям и средствам связи. М.: Мир, 2000.
  22. Abouzeid A., Roy S. and Azizoglu М. Stochastic Modeling of TCP over Lossy Links. // INFOCOM’OO, Tel-Aviv, Israel, March 2000.
  23. 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.
  24. Anjum F., Tassiulas L. Fair Bandwidth Sharing Among Adaptive and Non-Adaptive Flows in the Internet. // IEEE INFOCOM'99, March 1999.
  25. Allman M. et al. TCP Congestion Control. RFC-2581 IETF, April 1999.
  26. Allman M. A Web Server’s View of the Transport Layer. // ACM Computer Communication Review, October 2000.
  27. 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.
  28. Altman E., Avrachenkov K., Barakat C. TCP modeling in the presence of nonlinear window growth. // ITC-17, Brazil, Sept. 2001.
  29. Altman E., Jimenez T. NS simulator for beginners, Lecture notes, France, 2003.
  30. Apisdorf J., Claffy K., Thompson K. and Wilder R. OC3MON: Flexible, Affordable, High-Performance Statistics Collection. August 1996.
  31. 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.
  32. Athuraliya S., Low S., Li V. and Yin Q. REM: Active Queue Management. // IEEE Network Magazine, 15(3), May/June 2001.
  33. Baccelli F., Hong D. TCP is Max-Plus Linear. Tech. Rep. RR-3986, INRIA, 2000.
  34. Baccelli F., Hong D. A.I.M.D., Fairness and Fractal Scaling of TCP Traffic. Tech. Rep. RR-4155, INRIA, April 2001.
  35. 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.
  36. Balakrishnan H., Rahul H. and Seshan S. An Integrated Congestion Manage-mentArchitecture for Internet Hosts. // ACM SIGCOMM'99, August 1999.
  37. Beran J. Statistical Methods for Data with Long-Range Dependence. // Statistical Science, Volume 7, Issue 4. -1992. P. 404−416.
  38. Berners-Lee T. et al. The World Wide Web. Communications of the ACM, August 1994.
  39. Berners-Lee T. et al. Hypertext Transfer Protocol HTTP/1.0. RFC-1945, IETF, May 1996.
  40. Braden R. Extending TCP for Transaction Concepts. RFC-1379, IETF, November 1992.
  41. Braden R. T/TCP TCP Extensions for Transactions. Functional Specifica-tion.RFC-1644, IETF, July 1994.
  42. Braden B. et al. Management and Congestion Avoidance in the Internet. RFC-2309, IETF, April 1998.
  43. Box G.E.P., Jenkins G.M. Time Series Analysis: Forecasting and Control. Holden Day, San Francisco, 1970.
  44. Cardwell N., Savage S. and Anderson T. Modeling TCP latency. // INFO-COM'OO, Tel-Aviv, Israel, March 2000.
  45. Chiu D., Jain R. Analysis of the increase/decrease algorithms for congestion avoidance in computer networks. // Computer Networks and ISDN 17. P. 114.
  46. Claffy K., Miller G., Thompson K. The nature of the beast: recent traffic measurements from an Internet backbone. // INET'98.
  47. Comer D. Internetworking with TCP/IP, Volume 1: Principles, Protocols, and Architecture, 3rd edition. Prentice-Hall, 1995.
  48. Cormen Т., Leiserson C., Rivest R. Introduction to Algorithms. The MIT Press/McGraw-Hill, Cambridge, MA/New York, 1998.
  49. 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.
  50. Cunha C. R., Bestavros A. and Crovella M. E. Characteristics of WWW Cli-entbased Traces. Technical Report Boston University CS Department, April 1995.
  51. Dumas V., Guillemin F. and Robert P. A Markovian Analysis of AIMD Algorithms, Adv. in App. Prob., vol. 34, no. 1.
  52. Eggert L., Heidemann J. and Touch J. Effects of Ensemble-TCP. // ACM Computer Communication Review, January 2000.57
Заполнить форму текущей работой

Сессия? Спокойно!