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

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

□0306440Б

ПЛАТОВ Виктор Вячеславович

СПЕЦИАЛЬНОЕ МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПРОЦЕССОВ УПРАВЛЕНИЯ ИНТЕНСИВНОСТЬЮ ПЕРЕДАЧИ ДАННЫХ

Специальность 05 13 11 - Математическое и программное обеспечение

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

АВТОРЕФЕРАТ

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

Воронеж - 2007

0 2 АВГ 2007

003064406

Работа выполнена в Воронежском государственном техническом университете

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

Кравец Олег Яковлевич

Официальные оппоненты доктор технических наук, профессор

Титов Виталий Семенович, Курский государственный технический университет,

кандидат технических наук, доцент Свиридов Андрей Станиславович, Воронежская государственная технологическая академии

Ведущая организация Воронежский государственный универ-

ситет (г Воронеж)

Защита состоится 27 сентября 2007 г в 10ос часов в конференц-зале на заседании диссертационного совета Д 212 037 01 Воронежского государственного технического университета по адресу 394026 Воронеж, Московский просп, 14

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

Автореферат разослан 27 августа 2007 г.

Ученый секретарь диссертационного совета ' Питолин В М

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

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

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

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

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

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

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

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

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

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 научных работах, в том числе 2 - в изданиях, рекомендованных ВАК РФ

В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю принадлежит в [1] - алгоритм управления интенсивностью потока данных с использованием прогнозирования доступной полосы пропускания, в [3] — способ оценки влияния параметров TCP на степень самоподобия трафика, в [4, 5, 6] - алгоритм «сглаживания» интенсивности отправки сегментов данных, в [7, 8] - математическая модель процесса управления потоком TCP Reno, учитывающая фазы медленного старта и экспоненциального отката, в [4, 9] — алгоритм управления очередями активных сетевых устройств с выборочным отбрасыванием пакетов, в [10] — подготовка и проведение эксперимента по сбору трафика беспроводной сети, его анализ

Структура и объем работы. Работа состоит из введения, четырех глав, заключения, списка литературы, включающего в себя 131 наименование^ при-

ложения Основная часть работы изложена на 121 странице, содержит 1 таблицу и 47 рисунков

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы диссертационной работы, изложено состояние проблемы, сформулированы цели и задачи исследований, показаны научная новизна и практическая значимость полученных результатов, описан объект исследования Приведены основные положения, выносимые автором на защиту, сведения об апробации и внедрении работы

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

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

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

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

- начальные значения скользящего окна перегрузки W = 1 и граница фазы медленного старта IV1'1 = wf = 65535 байт TCP соединение стартует с фазы медленного старта, которая продолжается при IV < IV,'/' и отсутствии потерь На фазе медленного старта размер скользящего окна увеличивается на 1 каждый раз при получении АСК, те Wc = W" +1 При достижении размером окна перегрузки порогового значения w* TCP переходит в фазу предотвращения перегрузки,

- при обнаружении ТД ошибки Wrt = max(

W

,2), Wc = max(

Wc

,1), TCP

переходит в фазу предотвращения перегрузки, в течение которой размер скользящего окна возрастает на сегментов при получении каждого АСК,

— при обнаружении ТА ошибки WА = тах(

W

2), Wc = 1, TCP переходит

2

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

рянный сегмент, удваивая таймер повторной передачи Т„ каждый раз в случае неудачи,

- при окончании фазы экспоненциального отката (подтверждении получения потерянного сегмента) TCP входит в фазу медленного старта, а при достижении W° порога Wk и в фазу предотвращения перегрузки

Определение потери сегмента по Определение потери сегмента по

таима уту повторной передачи (ТА) трем последовательным АСК (ТД)

Рис 1 Определение ошибок передачи

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

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

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

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

1

0,9

х

§08 íií

So-7

»0,6

— Tahoe

- T»K»«ED <■ tö'no

» «прогчео

1 e

m 1 6

8.14

Ф

X|2

Q,

¡D 1 5

£oe rS

С 4

02

10 20 30 40 50 Число одновременных соединении

60 о 6)

- Talit»

- hfie REO Reno Koro,RED

St. Л Л1 •«. «0 Число одновременных соединении

Рис 2 Зависимость параметров мультиплексированного трафика от числа одновременных соединений (мультиплексируемых потоков) для различных версий протокола TCP а) коэффициент вариации, б) параметр Хэрста

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

Предложенная модель учитывает так называемый параметризованный процесс управления потоком ТСР(а,р,5) Параметры а, р, 5 определены следующим образом окно перегрузки Wc возрастает при получении каждого АСК на а сегментов во время медленного старта, на p/W сегментов во время этапа предотвращения перегрузок и, наконец, умножается на 5 < 1 в случае потери пакета (кроме случаев, когда факт потери определяется по истечении тайм-аута повторной передачи) Таким образом, классический алгоритм TCP Reno определяется как TCP (1,1,1/2)

Моделирование осуществляется с помощью однородной Марковской цепи ^ = (^„)„г1, каждое состояние которой описывается двумя параметрами

Хп = (IV^, W*), где W„r равен размеру окна перегрузки на n-ом раунде, или W< =0, если алгоритм находится в фазе экспоненциального отката, параметр W,'* определяет пороговое значение фазы медленного старта на n-ом раунде

Раунд — это период времени между отправлением последнего сегмента текущего окна и получением АСК на него

Механизм алгоритма управления потоком TCP(a,ß,5) может быть описан следующим образом

- медленный старт (MC) увеличение перегрузочного окна на а сегмен-

~wc~

тов при получении каждого АСК W^ = \УЦ +

при условии, что

и

1 < fV,' < W*, и отсутствии потерь,

- предотвращение перегрузки (ПП) увеличение размера окна на —

сегментов при получении АСК при условии, что W* <W¡ <¡VmM, и отсутствии потерь (когда IV,' достигает максимальной вместимости буфера активного устройства lVm„, оно остается постоянным),

- обнаружение потери сегмента по тройному дублированию АСК (ТД) три последовательных подтверждения доставки сегмента т-1 говорит о том, что сегмент m был потерян = ma\([<5If„' Jl), tv*, = ma\(|_<5W„'J2), после чего запускается новая стадия ПП,

- обнаружение потери сегмента по тайм-ауту (ТА) если отправитель не получает подтверждение за время истечения тайм-аута Г0 , то = О и W.'J, - maxd/JF; J2), после чего запускается новая стадия экспоненциального отката,

- экспоненциальный откат (ЭО) при обнаружении ТА утерянный сегмент будет передаваться повторно, пока не придет АСК (значение таймера удваивается в случае каждой неуспешной попытки Г0, 2Т0, ..,64Г0) , после чего стартует фаза МС с и^, = 1

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

Каждый цикл в алгоритме управления потоком TCP Reno состоит из фаз медленного старта и предотвращения перегрузки То есть в пределах каждого цикла возможно появление нескольких ТД ошибок и одной ТА ошибки (рис 3)

Сделаем предположение о том, что в течение текущего раунда потеря одного из сегментов ведет к потере всех последующих сегментов (коррелированные потери) Такое предположение соответствует реальной ситуации высокоскоростных сетей и узлов коммутации с политикой очередей tail-drop Более того, если в течение данного раунда к сегментов были переданы до того, как про-

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

Используя предположения о том, что потери сегментов происходят только от отправителя к получателю, т е АСК не теряются, и постоянстве величины р вероятности этой потери, были получены выражения для величин вероятностей переходов между состояниями алгоритма управления потоком TCP Reno, вероятностей ТА и ТД потерь пакетов, средних чисел E[d1A], E[dmm] и E[dor]

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

наклон = {i

и;

a Wc ТД потеря

| ТД потеря I ТА потеря

,s »

1 Aá

í !

:n¡

< !

i I i i i

..ulÍÜ.

í i r 1

If 1 •. П

:ms

i i ■

IVth

■^ír

Y'f h

' t /1

J

l 1 i

■o <¿-¿0

á

A í!'

MC ПП ПП ПП ЭО MC rn Рис 3 Пример изменения размера окна ТСР(1,2,3/4)

A-1I hi

Г:

Рис. 4 Остаточный раунд

Используя эти выражения, можно найти скорость отсылки данных отправителем и скорость приема данных получателем-

Р £[ГП ] + £[7](Ш ] + ~1)Рог' ( )

Р" КТтЛ + ЩТ^Л + НГПЫ,,^, -1 )рОР • ( '

где £[<<„,„] и ЩОР] - среднее число сегментов, отосланных в течение фа-

зы экспоненциального отката, каждого цикла и каждого остаточного раунда,

Е[4°„.,] и Е№оР] - среднее число успешно переданных сегментов в течение цикла и остаточного раунда соответственно,

Е[Тта] и - средняя продолжительность этапа экспоненциального

отката и каждого цикла,

N...

- среднее число потерь за время цикла,

р0Р - вероятность того, что во время остаточного раунда будет передан хотя бы один пакет, т е успешная доставка как минимум одного сегмента была подтверждена,

ЯТТ - среднее время оборота пакета в сети

Анализируя полученные результаты, можно заметить, что, во-первых, характеристики алгоритма управления потоком TCP Reno практически не зависят от выбора параметра фазы медленного старта а

Рис 5 Скорость отправки пакетов р и эффективность е = —

Р

для различного выбора параметров а ,р,5

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

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

Основное предположение, которое было сделано при разработке данной модели, заключается в характеристиках сети передачи данных, через которую осуществляется работа TCP соединения Данная сеть предполагается высокоскоростной и географически распределенной Действительно, описанная модель предполагает, что время, необходимое для отсылки всех сегментов внутри текущего перегрузочного окна, а также временные интервалы между соседними АСК должны быть малы по сравнению с RTT (время оборота пакета в сети) для выделения всплесков трафика, названных раундами Предложенная модель также использует предположение о том, что вероятность потери пакета не зависит от размера окна В высокопроизводительных сетях одно TCP соединение не может вызвать перегрузку всей сети Если говорить о связи потерь пакетов (при потери одного из сегментов внутри раунда все остальные сегменты также теряются), сделанные предположения соответствуют высокопроизводительным

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

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

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

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

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

На рис. 6 по вертикальной оси отложена интенсивность передачи р, достигаемая рассматриваемым TCP соединением, а по горизонтальной оси - ин-

С

О

Рис 6 Фазовая плоскость TCP соединения

тенсивность передачи р„ остального трафика Пусть одновременно N TCP соединений разделяют канал пропускной способности С Тогда оптимальная рабочая точка будет находиться на пересечении прямых р + р„=С (прямая емкости) и — = —-— (прямая справедливого разделения ресурсов) Без предсказания Ро W-1

трафика TCP соединение достигает оптимальную рабочую точку спустя несколько фаз алгоритма управления потоком То есть TCP протокол экспериментально подбирает интенсивность своей передачи в зависимости от внешних условий

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

В качестве предсказателя величины доступной полосы пропускания для предлагаемого алгоритма управления потоком МТСР (Modified TCP) был выбран фильтр низких частот с экспоненциально взвешенным скользящим средним (ЛМСКО)

Рассмотрим механизм прогнозирования трафика подробнее Имея информацию о временном ряде величин доступной полосы пропускания /(/),/eZ + , МТСР отправитель вычисляет агрегированные последовательности f'"'(k-n + X),f{"'){k-п + 2), ,fim\k), отсчеты которых соответствуют п предыдущим интервалам измерений Базируясь на этих отсчетах агрегированных рядов, отправитель предсказывает доступную полосу пропускания /'"''(A + l) на следующем интервале измерения Агрегированные временные ряды использовались по следующим причинам во-первых, долгосрочная зависимость, присутствующая в самоподобном трафике, означает, что автокорреляционная функция агрегированного ряда подчиняется тому же закону, что и исходного Следовательно, данные агрегированные ряды могут представлять исходные последовательности Во-вторых, операции усреднения могут быть рассмотрены как операции считывания и выравнивания Известно, что выравненные отсчеты трафика проявляют более предсказуемую природу, тем самым обеспечивая более точную оценку

Пусть временной ряд fimy(k),k = 1, ,и,/0"'(л + 1), может быть выражен в виде взвешенной суммы последних п отсчетов То есть такая оценка может быть записана как

/""'(« +1) = [а

/<т>(1) /с"'(2)

(3)

где а,,«,,., ал - ЛМСКО коэффициенты, которые могут быть записаны в виде

Л(0) й(1) Л(и -1)"

Я(1) Д(0) Д(я - 2)

[а, а, о„]=[й(и) fi(n-l) «(!)]>

(4)

Д(и-1) Л(и - 2) Я(0)

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

Я(0 £ Л('"Ч0 = ~ Z/'W^O-О,

(5)

для 0 < i < л -1, где п - число хранимых отсчетов агрегированного ряда, подстраиваемый параметр (как в опытах, так и в аналитических выкладках использовалось значение я = 20)

Обратимся к рис 6 для того, чтобы пояснить, как результат предсказания

- «»о

/ (и + 1) может быть использован для подстройки алгоритма управления потоком TCP Оптимальная рабочая точка N TCP соединений, разделяющих канал связи пропускной способности С, лежит на пересечении прямых / + В ~С и f 1

= ——- Предположим, что изначально рабочая точка находится в точке «х»

Без информации о числе N TCP соединение использует алгоритм управления потоком TCP Reno и следует пунктирной линии для достижения оптимальной рабочей точки за несколько RTT В ходе достижения оптимальной точки пунктирная линия несколько раз пересечет прямую емкости, отображая события потерь пакетов Если же TCP соединение сможет сделать предположение о числе N, оно будет способно напрямую подстроить свое перегрузочное окно таким образом, чтобы сразу работать в оптимальной точке (сплошная линия рис 6) В наилучшем случае оптимальная рабочая точка может быть достигнута за один RTT без пересечения прямой емкости, т е избежав потерь пакетов Главная проблема заключается в оценке числа соединений N Пусть W,(n) и Щ(п +1) означают соответственно текущий размер перегрузочного окна и размер окна перегрузки в течение следующего RTT для i-го соединения Используя выражение

для оценки достижимой пропускной способности / (и +1) на следующем RTT и предположение о синхронизации всех TCP соединений (т е. все TCP соединения имеют одинаковое значение RTT), МТСР сможет вычислить N по формуле

Алгоритм управления потоком МТСР, аналогично TCP Reno, состоит из трех фаз медленного старта, предотвращения перегрузки и экспоненциального отката, причем поведение МТСР на фазах медленного старта и экспоненциального отката полностью аналогично поведению алгоритма TCP Reno Также останется неизменным механизм уменьшения размера окна управления потоком алгоритма TCP Reno Главным отличием МТСР от TCP Reno является механизм увеличения размера окна на фазе предотвращения перегрузки МТСР рассчитывает размер окна предотвращения перегрузки по формуле

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

Рис 7 Фазовые траектории, иллюстрирующие случаи пересечения рабочей точкой прямой емкости а) ошибки предсказания, б) различные RTT

(7)

В случае возникновения ошибки предсказания или если TCP соединения не синхронизированы (имеют разное RTT), рабочая точка может уйти за прямую емкости с последующей потерей сегмента данных (рис. 7) Например, как показано на рис 7,6, если рассматриваемое МТСР соединение реагирует на внешние факторы быстрее фонового трафика, то МТСР следует пунктирной линии для достижения оптимальной рабочей точки Если же фоновый трафик реагирует быстрее, то МТСР следует жирной линии, может пересечь прямую емкости и потерять данные Так как механизм уменьшения размера окна остался неизменным, при потере сегмента размер окна перегрузки уменьшается наполовину, а рабочая точка перемещается обратно под прямую емкости, после чего модифицированный алгоритм пытается переместить рабочую точку к оптимальному значению на следующем RTT Неизменность механизма уменьшения размера окна обусловлена соображениями устойчивости TCP Оставляя данный механизм неизменным, можно бьгсь уверенными, что стабильность TCP не нарушится из-за изменений механизма увеличения размера окна

В случае постоянных ошибок предсказания МТСР соединение может никогда не достичь оптимальной рабочей точки, все время находясь поблизости от нее Хотя стабильность протокола гарантируется неизменным механизмом уменьшения размера окна перегрузки, долгосрочное справедливое разделение полосы пропускания может быть нарушено

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

Разработанный в настоящей диссертации алгоритм управления потоком данных МТСР реализован как в среде сетевого эмулятора ns-2, так и в ядре операционной системы FreeBSD 5 0 Причем путем создания интерфейса взаимодействия исходного кода FreeBSD и ns-2 удалось достичь использования FreeBSD реализации алгоритма МТСР в эмуляторе ns-2 Схема данного интерфейса приведена на рис 8

Для сравнения характеристик предложенного алгоритма управления потоком МТСР с характеристиками алгоритма TCP Reno была проведена серия экспериментов по имитационному моделированию в среде ns-2 для различных топологий компьютерных сетей и параметров каналов связи В качестве математической модели потока данных использовалась модель on/off, генерирующая самоподобный трафик с параметром Н=0,8 Как видно на рис 9, МТСР практически не уменьшает степени самоподобия трафика, причины которого лежат на вышележащих уровнях модели OSI (Open System Interconnection модель взаимодействия открытых систем, англ)

Рис 8 Структура программного кода реализации алгоритма МТСР

для ns-2

tj-,-,-,-,-,-,-,-,-

- t t l-l < - - | T . .

I i

£ & » 1 I I < | I

««■i 4 .....

£

& 46

t>55 - t - -Í ~ - - ~t ( - - *

4Í -----!-----.---1-

10 44 Л 4Л >1 <o ТО «•) « 100 Число соединении

Рис 9 Зависимость параметра Херста Н от числа одновременных МТСР

соединений

Вместе с тем, как видно из рисунков 10,а и 10,6, такие характеристики МТСР, как полезная пропускная способность и доля потерянных пакетов, оказываются значительно (до 70 %) лучшими, чем характеристики алгоритма TCP Reno в случае самоподобного трафика

m

e

w

с § «

go ote

a>

с £ erf

a)

.«...МГСР TCP Rent

'шср

* TCPRWK

gj-IB

О

5 4J»

g- 4?

^ I'J iTU V.t O'J V»' IV №J Ifl

Число соединении Б) Число соединений

Рис 10 Сравнение МТСР с TCP Reno-а) доля потерянных пакетов, б) достигаемая пропускная способность

При анализе характеристик реализации алгоритма МТСР для операционной системы FreeBSD 5 0 в реальных сетях передачи данных была выбрана глобальная сеть Интернет, объединяющая региональные офисы компании D-Lmk Эксперименты по передаче файлов осуществлялись через сеть Интернет, причем приемники данных находились в московском офисе компании D-Link (dservmsk dlinkru), а также в Ростовском, Новосибирском и Екатеринбургском филиалах D-Link, тогда как источник данных находился в Воронежском офисе D-lmk Описываемые эксперименты осуществлялись в течение трех различных временных интервалов (утро, полдень, вечер) на протяжении 2-х недель Во время опытов были измерены средняя пропускная способность каждого соединения и общее число тайм-аутов повторной передачи На рис 11 отображены результаты экспериментов, проведенных между Воронежским и Московским офисами D-Link в полуденные часы Анализируя эти результаты, можно заметить, что МТСР показывает лучшие характеристики в плане средней пропускной способности и количества тайм-аутов повторной передачи

л!

Размер файла (байт)

б)

10* 10" Размер файла (байт)

Рис 11 Результаты использования алгоритма МТСР в реальных сетях (Интернет) а) пропускная способность; б) количество повторных передач

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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-ЗСогп Technologies и используется для оптимизации обмена маршрутной информацией

Основные результаты диссертации опубликованы в следующих работах: Публикации в изданиях, рекомендованных ВАК РФ

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

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

Статьи и материалы конференций

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

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

5 Кравец О Я , Платов В В Анализ TCP-сглаживания на стороне источника данных // Системные проблемы надежности, качества информационных технологий материалы X междунар конф и Российской науч школы - М Радио и связь, 2005 Ч 5 - С 38-41

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

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

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

9 Кравец О Я , Платов В В Анализ существующих и перспективных политик очередей с точки зрения минимизации степени самоподобия трафика пакетных сетей передачи данных // Информационные технологии моделирования и управления научно-технический журнал Воронеж Научная книга, 2006 №3(28) - С 377-383

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

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

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

Подписано в печать 04 07 2007 Формат 60x84/16 Бумага для множительных аппаратов Уел печ л 1,0 Тираж 90 экз. Заказ № 35"£

ГОУВПО «Воронежский государственный технический университет» 394026 Воронеж, Московский просп , 14

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

Введение.

Глава 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 и используется для оптимизации обмена маршрутной информацией.

Заключение

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