автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Разработка методов оценки средней скорости передачи данных по протоколу ТСР

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

ДУНАЙЦЕВ Роман Альбертович

РАЗРАБОТКА МЕТОДОВ ОЦЕНКИ СРЕДНЕЙ СКОРОСТИ ПЕРЕДАЧИ ДАННЫХ ПО ПРОТОКОЛУ TCP

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

Автореферат

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

Санкт-Петербург

2005

Работа выполнена в Санкт-Петербургском государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича.

Научный руководитель:

доктор технических наук, профессор Кучерявый А.Е.

Официальные оппоненты:

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

доктор технических наук, профессор

Степанов С.Н.

кандидат технических наук

Парамонов А.И.

ОАО «ГИПРОСВЯЗЬ СПб»

Защита состоится «30 » //&/ 2005 г. в часов на заседании

диссертационного совета К.219.004.01 при государственном университете телекоммуникаций им. проф. М.А. Бонч-Бруевича по адресу: 191186 Санкт-Петербург, наб. р. Мойки, 61, ауд.413.

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

Автореферат разослан « 2005 г.

Ученый секретарь совета, к.т.н., доц.

Л*?

В.Х. Харитонов

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

Актуальность проблемы. Согласно последним исследованиям, протокол управления передачей (Transmission Control Protocol, TCP) является доминирующим протоколом транспортного уровня в Интернет. Такие востребованные пользователями службы как World Wide Web (WWW), служба передачи файлов, электронная почта (E-mail) и многие другие используют для надежной передачи данных протокол TCP. Столь широкое применение протокола TCP в Интернет определило пристальное внимание к нему со стороны специалистов, занимающихся проблемами обеспечения качества обслуживания (Quality of Service, QoS) в Интернет. Помимо традиционных измерений и имитационного моделирования, в последнее десятилетие значительное число исследовательских работ было адресовано разработке математических моделей функционирования протокола TCP. Вопросы математического моделирования функционирования протокола TCP рассматривались в работах К.Авраченкова, М Mathis, J.Padhye, N.Cardwell, B.Sikdar и ряда других авторов.

В настоящее время предполагается, что одну из основных составляющих трафика Интернет в ближайшем будущем будут создавать услуги передачи мультимедийной информации: потоковое видео, аудио-трансляции и т.п. В ряде работ было доказано, что для большинства мультимедийных услуг приоритетными параметрами, влияющими на качество предоставляемой услуги, являются задержка доставки пакета и дисперсия этой задержки (джиттер), в то время как трафик, создаваемый услугами потокового типа, является (в определенных пределах) устойчивым к потерям. В основном это объясняется тем, что услуги потокового типа ориентированы на передачу аудио/видеоинформации и ее незамедлительное воспроизведение, в результате чего оконечный пользователь и является той системой, которая оценивает качество предоставляемсй услуги. В связи с этим применение протокола передачи пользовательских дейтаграмм (User Datagram Protocol, UDP) для потокового мультимедийного трафика предпочтительнее, чем протокола TCP, так как реализованная в протоколе TCP функция управления перегрузкой с резким уменьшением скорости передачи при обнаружении потери может существенно ухудшить качество предоставляемой услуги за счет увеличения задержки доставки данных и дисперсии этой задержки. Однако отсутствие каких-либо алгоритмов управления перегрузкой в протоколе UDP может привести к ухудшению условий функционирования параллельных соединений TCP (т.е. соединений TCP, использующих общий канальный ресурс совместно с потоками UDP), а также к перегрузке сети.

В последние годы был предложен ряд механизмов, позволяющих осуществлять адаптивное управление трафиком, создаваемым, в том числе, и потоками UDP. Протокол дружественного TCP управления скоростью передачи данных (TCP Friendly Rate Control, TFRC), определенный в документе RFC 3448, является одним из наиболее проработанных и перспективных механизмов для адаптивного управления скоростью передачи данных и реализации функции управления перегрузкой при использовании протокола UDP для передачи потокового мультимедийного трафика. Протокол TFRC позволяет прикладному процессу передавать данные примерно с той же скоростью, что и протокол TCP в аналогичных условиях, но при этом избегая резкого уменьшения скорости передачи данных в случае потери пакетов. При использовании указанного протокола приемник TFRC сообщает передатчику информацию о потерях, а передатчик TFRC рассчитывает скорость передачи данных на основе полученной информации, времени обращения пакета и формулы, определяющей среднюю скорость передачи

данных по протоколу TCP в аналогичных услови

Данная формула была получена в работе J.Padhye, V Firoiu, D.Towsley и J.Kurose (и широко известна как PFTK-модель) на основе математического моделирования передачи данных по протоколу TCP Reno в длительном соединении в условиях пачечного процесса потерь, возникающим три использовании в маршрутизаторах алгоритма усечения хвоста очереди (Tail-Drop) с дисциплиной обслуживания FIFO (First In, First Out). В то же время детальный анализ показывает, что используемое в PFTK-модели упрощенное представление таких алгоритмов, как быстрая повторная передача и быстрое восстановление, а также отсутствие рассмотрения фазы медленного запуска после таймаута может приводить к существенно завышенной оценке средней скорости передачи данных по протоколу TCP Reno в условиях пачечного процесса потерь.

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

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

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

Цель и задачи исследований. Целью диссертационной работы является разработка методов оценки средней скорости передачи данных по протоколу TCP. С учетом вышесказанного, в качестве рассматриваемых реализаций протокола TCP были выбраны следующие реализации: TCP Reno и TCP NewReno (вариант Slow-but-Steady). При этом поставленная цель достигается путем решения следующих основных задач:

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

2. Анализ существующих методов оценки средней скорости передачи данных по протоколу TCP. Определение возможных подходов к разработке метода оценки средней скорости передачи данных по протоколу TCP и недостатков существующих методов.

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

4. Разработка метода оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady) в длительном соединении в условиях пачечного процесса потерь.

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

Методы исследования. Проведенные в диссертационной работе исследования основываются на теории вероятностей, теории восстановления, математической статистике и высшей алгебре.

Для проведения численных расчетов и статистического анализа в диссертационной работе использовался пакет программ Mathcad 2000 Professional. Для проверки адекватности разработанных методов оценки средней скорости передачи данных по протоколу TCP использовался программный продукт моделирования сетей связи ns-2. Для анализа и обработки данных, полученных в результате имитационного моделирования, использовались утилиты awk и Windows Grep.

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

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

- метод оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady) в длительном соединении в условиях пачечного процесса потерь.

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

Использование результатов работы в протоколе TFRC для адаптивного управления скоростью передачи потокового мультимедийного трафика по протоколу UDP позволит обеспечить совместимость с соединениями TCP, где, согласно документу RFC 2309, TCP-совместимым потоком является поток, реагирующий на сообщения о перегрузке и средняя скорость передачи которого в установившемся состоянии не превышает среднюю скорость передачи данных в соединении TCP в аналогичных условиях.

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

1. 56-я научно-техническая конференция профессорско-преподавательского состава, научных сотрудников и аспирантов ГУТ им. проф. М.А. Бонч-Бруевича, Санкт-Петербург, 26-30 января, 2004 г.

2. 57-я научно-техническая конференция профессорско-преподавательского состава, научных сотрудников и аспирантов ГУТ им. проф. М.А. Бонч-Бруевича, Санкт-Петербург, 24-28 января, 2005 г.

3. 8-я международная конференция «Internet, Multimedia Systems and Applications», Кауаи (США), 16-18 августа, 2004 г.

4. 3-й международный семинар «Internet Performance, Simulation, Monitoring and Measurements», Варшава (Польша), Технологический Университет Варшавы, 14-15 марта, 2005 г.

5. 3-я международная конференция «Wired/Wireless Internet Communications», Ксанти (Греция), 11-13 мая, 2005 г.

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

- новые аналитические результаты функционирования протокола TCP в условиях пачечного процесса потерь;

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

- метод оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady) в длительном соединении в условиях пачечного процесса потерь;

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

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

Публикации. Основные результаты диссертационной работы представлены в 9 печатных работах.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и трех приложений. Работа содержит 155 страниц машинописного текста, включая 37 рисунков, список литературы из 125 наименований и приложения.

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

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

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

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

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

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

В данной главе были рассмотрены математическая модель, представленная в работе M.Mathis и др., а также математическая модель, представленная в работе J.Padhye, V.Firoiu, D.Towsley и J.Kurose (PFTK-модель).

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

где В - средняя скорость передачи данных по протоколу TCP;

Ai\Y\ - математическое ожидание числа сегментов данных, переданных в течение цикла;

При этом метод оценки средней скорости передачи данных по протоколу TCP основан на использовании следующей функциональной зависимости:

где р - вероятность потери сегмента данных;

RTT - среднее время обращения сегмента (Round Trip Time, RTT);

RTO - средняя длительность таймаута повторной передачи (Retransmission TimeOut, RTO);

b - число сйгментов данных, подтверждаемых одним сегментом подтверждения;

И/щах - максимальное значение окна приемника.

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

Проведенный анализ показал, что если при передаче окна, состоящего из W сегментов данных и потере последовательности сегментов данных, вероятность того, что будет потеряно 5 сегментов, имеет равномерное распределение от 1 до W, то при использовании реализации TCP Reno и обнаружении потери первого сегмента данных (из числа потерянных) в результате получения трех повторных подтверждений, будет иметь место следующая последовательность действий:

B=M[Y]/M[A\,

О)

А/[л] - математическое ожидание длительности цикла.

(2)

- получение трех повторных подтверждений;

- инициирование алгоритмов быстрой повторной передачи и быстрого

восстановления, повторная передача первого потерянного сегмента данных;

- ожидание истечения таймера повторной передачи, установленного после

подтверждения приема повторно переданного сегмента данных;

- инициирование алгоритма медленного запуска.

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

В третьей главе разработаны методы оценки средней скорости передачи данных по протоколам TCP Reno и TCP NewReno (вариант Slow-but-Steady) в условиях пачечного процесса потерь.

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

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

Предполагается, что в течение всего соединения размер передаваемых сегментов данных является постоянным и равным максимально разрешенному (Maximum Segment Size, MSS), который определяется на этапе установления соединения TCP Значение размера окна приемника также предполагается постоянным. Предполагается, что время, необходимое для передачи всех сегментов данных в скользящем окне, значительно меньше RTT, а величина RTT и вероятность потери сегмента данных не зависят величины скользящего окна. Процесс потерь сегментов предполагается пачечным, т.е. предполагается, что потери в различных раундах независимы, в то же время вероятность потери сегментов данных коррелированна в пределах одного раунда. При этом потери происходят только в направлении от передатчика к приемнику.

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

величины скользящего окна (и, соответственно, скорости передачи данных) со стороны приемника.

Для случая передачи данных по протоколу TCP Reno получены следующие результаты.

На основе анализа, проведенного во второй главе, в качестве цикла определен процесс передачи сегментов данных в интервале времени между двумя таймаутами, при этом цикл состоит из следующих фаз: медленного запуска (slow start, SS), предотвращения перегрузки (congestion avoidance, СА), быстрой повторной передачи и быстрого восстановления (fast retransmit/fast recovery, FR) и одного таймаута (рис. 1).

w,

сели.

Б± 2

□ подтвержденный оегменг

■ni потерянный I&I сегмент

SS,

СА,

FR, RTO,

SS,.

№ раунда

Рис. 1. Процесс передачи сегментов данных в течение 1-го цикла (/ = 1,2,...).

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

W, сет. »i г,

i Н Гг Ц г г* у> L, Н ,

J t¿

цикл 3

цикл 1 цикл 2

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

Следовательно, согласно (1) и (2), средняя скорость передачи данных может быть определена как

1

■M[W]

В = -

RTT

max(log2M[W],2) + ¿>+ 1 | + 2

(3)

+ RTO

где р - вероятность потери сегмента данных при условии, что он является либо первым в раунде, либо предыдущий сегмент в данном раунде был успешно передан;

А/[>г] - математическое ожидание значения окна ((У) в конце фазы предотвращения перегрузки:

2+3-¿>У ¡8 + 4 р Г2+3-М2

уз ь-р+{ з ъ )-

з ь з ь-р Ч з-

(4)

На втором этапе, учитывая, что обнаружение потери первого из числа потерянных в одном раунде сегментов данных может происходить как в результате получения трех повторных подтверждений, так и в результате истечения таймаута повторной передачи, аналогично РРТК-модели, рассмотрим процесс передачи сегментов данных как последовательность сверхциклов, где г'-й сверхцикл (г = 1,2,.. ) состоит из j циклов (У = 1,...,л,) с обнаружением потери первого потерянного сегмента данных в результате получения трех повторных подтверждений в первых (л,-1) циклах и цикла с обнаружением потери первого потерянного сегмента данных в результате истечения таймаута повторной передачи, сопровождающегося последовательностью таймаутов (рис. 3).

Тогда средняя скорость передачи может быть определена как

в = м[м)1мЩ, (5)

где А/[М] - математическое ожидание числа сегментов данных, переданных в течение сверхцикла;

М [5] - математическое ожидание длительности сверхцикла.

"V цикл /1 V цикл /2 V последовательность таймаута

5.

сверхцикл/

Рис. 3. Процесс передачи сегментов данных в течение г-го сверхцикла, где Л, - число сегментов данных, переданных в течение последовательности таймаутов.

Тогда, согласно (5), средняя скорость передачи данных может быть определена как

иищ+сЛнЩ^е-

в=

птт

тах (йф, М [IV], 2) + +11 + 2 | +

где Л/[РГ] определяется согласно (4);

/(р) определяется как

/(р) = 2- р+2-р2 +4-р3 +8-р4 + 16-р5 + 32-р6; (7)

- значение вероятности обнаружения потери первого сегмента данных из числа потерянных в одном раунде в результате истечениятаймаута повторной передачи Согласно РРТК-модели б(А/[И']) определяется как

Г (1-(1-РГ)-(1+(1-Р)3-(1-0-рГиУ 11 1-(1 -р)4""1

Q{M[W^ = min

(8)

На заключительном этапе определим среднюю скорость передачи данных для случая с ограничением величины скользящего окна IV со стороны приемника (рис. 4), где Щпн - значение окна приемника, выраженное в сегментах данных.

V цикл >1 V цикл/2 последовательность таймаугов

Ь- S, 1

сверхцикл(

Рис. 4. Процесс передачи сегментов данных в течение г-го сверхцикла с ограничением величины скользящего окна со стороны приемника.

При ТГвд > А/[(Р] влияние величины окна приемника на скорость передачи данных в длительном соединении предполагается минимальным и, следовательно, средняя скорость передачи данных может быть определена согласно (6). Для случая ^ <А/[>Г] используем приближение М а У/^. Тогда средняя скорость передачи данных может быть определена как

я=

р \-р

m[™*(iog2 + +-rtt]' <9>

где QiW^ ) определяется согласно (8) с заменой М [w] на Wmax.

Объединяя (6) и (9), запишем результирующее выражение, определяющее среднюю скорость передачи данных по протоколу TCP Reno:

д=

>M{W\,

р 1 - р

RTT rnax(log2»'m„>2)+~-f" + И"

4PK

(Ю)

^ + + RTO + )| RTO ^ - Шj <M[fT],

где определяется согласно (4);

/(/>) определяется согласно (7);

и определяются согласно (8).

Для случая передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady) получены следующие результаты.

На основе проведенного анализа, в качестве цикла определен процесс передачи сегментов данных в интервале времени между двумя обнаружениями потери сегмента данных в результате получения трех повторных подтверждений, при этом цикл состоит из фазы быстрой повторной передачи и быстрого восстановления (fast retransmifTast recovery, FR) и фазы предотвращения перегрузки (congestion avoidance, СА) (рис. 5).

W, сегм

W,-

Eti 2

□

FR,

подтвержденный сетент

потерянный сепмнт

СА,

FR,.

№ раунда

ЦИКЛ I

Рис. 5. Процесс передачи сегментов данных в течение 1-го цикла (/ = 1,2,...).

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

Тогда, согласно (1) и (2), средняя скорость передачи данных может быть определена

1 -р

в=-

ятт

2 { 2 )

(П)

где р - вероятность потери сегмента данных при условии, что он является либо первым в раунде, либо предыдущий сегмент в данном раунде был успешно передан;

- математическое ожидание значения окна (IV) в конце фазы предотвращения перегрузки:

1 1 1>а+и \ъ ь-р+р и-6+и п

(12)

IV, сели.

г. (Г, "з -Г1*. —I

А1 С-- > 1 с

цикл 1

цикл 2

цикл 3

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

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

Отсюда, согласно (5), средняя скорость передачи данных может быть определена как

("МГ-О

1 -р

в=

1 -р

+м[иг]~ 2-

где Л/[>Р] определяется согласно (12); /(р) определяется как

/(/>) = 1 + р + 2- р2 +4-рг +8-р* + 16-рг + 32-р6; определяется согласно (8).

цикл /1 V цикл /2 V последовательность таймаутов

—г

сверхцикл I

Рис. 7. Процесс передачи сегментов данных в течение /-го сверхцикла, где Л, - число сегментов данных, переданных в течение последовательности таймаутов.

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

сверхцикл I

Рис. 8. Процесс передачи сегментов данных в течение 1-го сверхцикла с ограничением величины скользящего окна со стороны приемника.

При И^ >М\№\ влияние величины окна приемника на скорость передачи данных в длительном соединении предполагается минималшым и, следовательно, средняя скорость передачи данных может быть определена согласно (13). Для случая <М[Ж] используем приближение М^]*)?^. Тогда средняя скорость передачи данных может быть определена как

1-/7

+ »'_ -2-

1-р

8

ктт

((3+6)

8-11р + 26рИ' > ., У/?ГО/Ы ■—( , . Ж,+пУ (15)

где определяется согласно (8) с заменой A/[fF] на .

Объединяя (13) и (15), запишем результирующее выражение, определяющее среднюю скорость передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady):

в =

р 1 г , W]-2 У 1 " 1 -р 8

р RTOfíp) — Í . ... Л/М+ЛУ -т-^ + Я7г1 max(logIA/[»'],2)--U- II >M[W\, I1"' 8 J

(16)

где Л/[ff] определяется согласно (12);

f(p) определяется согласно (14);

£?(A/[w]) и Q(Wm) определяются согласно (8).

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

Имитационное моделирование проводилось с использованием программного продукта имитационного моделирования сетей связи ns-2. В качестве конкурирующего трафика использовался трафик, создаваемый ON/OFF источниками UDP. Для изменения условий функционирования рассматриваемого соединения TCP число источников UDP варьировалось с шагом в 10 источников. На каждом шаге было проведено 20 испытаний (запусков имитационного моделирования), каждое из которых имело дительность равную одному часу по внутреннему времени ns-2.

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

-Л

Пя1"" - вг*\"

в«жр

(17)

где п - число испытаний.

На рис. 10 представлено сравнение значений средней скорости передачи данных по протоколу TCP Reno, определяемых согласно результатам имитационного моделирования, PFTK-модели и разработанному методу оценки, а также сравнение погрешности оценки средней скорости передачи данных по протоколу TCP Reno PFTK-модели и разработанного метода.

Анализ показывает, что разработанный метод оценки средней скорости передачи данных по протоколу TCP Reno хорошо согласуется с результатами имитационного моделирования в диапазоне значений р от 0,001 до 0,1, в то время как PFTK-модель существенно переоценивает значение средней скорости передачи данных по протоколу TCP Reno во всем диапазоне значений параметра р, за исключением случая, когда р-> 0. При этом погрешность оценки средней скорости передачи данных согласно разработанному методу составляет в среднем менее 5% в диапазоне значений р от 0,002 до 0,095, тогда как погрешность PFTK-модели в указанном диапазоне составляет в среднем 50% и уменьшается лишь при р 0.

.Г

i ^гГ rt--

4 -

и< ч»лчи им é (TCP Rfc)

pFVUM/m

а) б)

Рис. 10. Сравнение а) измеренных и расчетных значений средней скорости передачи данных по протоколу TCP Reno и б) погрешности оценки.

На рис. 11 представлено сравнение значений средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady), определяемых согласно результатам имитационного моделирования, формуле, используемой в протоколе TFRC, и разработанному методу оценки, а также сравнение погрешности оценки средней скорости передачи данных по протоколу TCP NewReno указанной формулы и разработанного метода.

i

У I

..-г1 1

3

1

1

—L —г ж

- ж-2

Приложенный ЮТЗДОЦМЯИ (TCP формула Гфопмоло TFRC

оо1 ata оде о» ооб аов и(ТСР

а) б)

Рис. 11. Сравнение а) измеренных и расчетных значений средней скорости передачи данных по протоколу TCP NewReno и б) погрешности оценки.

Анализ показывает, что разработанный метод оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady) хорошо согласуется с результатами имитационного моделирования в диапазоне значений р от 0,008 до 0,09, в то время как формула, используемая в протоколе TFRC, существенно переоценивает значение средней скорости передачи данных по протоколу TCP NewReno во всем диапазоне значений параметра р. При этом погрешность оценки разработанного метода составляет в среднем 5% в диапазоне значений р от 0,008 до 0,075, тогда как погрешность оценки указанной формулы в данном диапазоне составляет в среднем 40%.

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Проведен анализ функционирования протокола TCP NewReno (вариант Slow-but-Steady) в условиях пачечного процесса потерь, на основе которого сделан вывод о необходимости учета алгоритмов быстрой повторной передачи, быстрого восстановления и медленного запуска при разработке метода оценки средней скорости передачи данных по протоколу TCPNewReno (вариант Slow-but-Steady)

5. Разработан метод оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady) в длительном соединении в условиях пачечного процесса потерь.

6. Проведено имитационное моделирование передачи данных по протоколамТСР Reno и TCP NewReno в присутствии конкурирующего трафика, создаваемого ON/OFF источниками UDP.

7. Проведенные исследования доказывают, что разработанные методы оценки средней скорости передачи данных по протоколу TCP имеют погрешность в среднем 5% в большом диапазоне значений вероятности потери сегмента данных, в то время как PFTK-модель и формула, используемая в протоколе TFRC, существенно переоценивают значение средней скорости передачи данных по протоколам TCP Reno и TCP NewReno (погрешность указанных методов оценки составляет в среднем 50% и 40% соответственно). Использование разработанных методов в протоколе TFRC для адаптивного управления скоростью передачи потокового мультимедийного трафика по протоколу UDP позволит обеспечить совместимость

данных потоков с соединениями TCP в соответствии с требованиями документа RFC 2309.

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Дунайцев, Р.А. Улучшенная и дополненная PFTK-модель для протокола TCP Reno / Р.А.Дунайцев, Е.А.Кучерявый // Электросвязь.- 2005,- № 3- С. 27-31.

2. Дунайцев, Р.А. Анализ WWW-трафика различных типов пользователей / Р.А.Дунайцев // 56 научн.-техн. конф. профессорско-преподавательского состава, научных сотрудников и аспирантов, СПб. 2004: Тез. докл.- ГУТ, СПб., 2004 - С. 20.

3. Дунайцев, Р.А. Анализ основных подходов к математическому моделированию протокола TCP / Р.А.Дунайцев, Е.А.Кучерявый // 57 научн.-техн. конф. профессорско-преподавательского состава, научных сотрудников и аспирантов, СПб. 2005: Тез. докл.- ГУТ, СПб., 2005.- С. 15-16.

4. Дунайцев, Р.А. Влияние сетевой асимметрии на характеристики протокола TCP / Р.А.Дунайцев, Е.А.Кучерявый // Телемультимедиа.- 2004- № 1 -С. 19-23.

5. Дунайцев, Р.А. Методы ускорения для коротких передач данных / РА.Дунайцев, Е.А.Кучерявый // Телемультимедиа.- 2004.- № 2.- С. 14-18.

6. Дунайцев, Р.А. Оценка объема Web-трафика создаваемого пользователями домашней сети / Р.А.Дунайцев, Е.А.Кучерявый // Телемультимедиа- 2004,- № 4.-С. 10-14.

7. Dunaytsev, R. Estimation of WWW-traffic generated by users in home networks / R.Dunaytsev, Y.Koucheiyavy, J.Haiju // LASTED IMSA. 2004: Proceedings - 2004 - pp. 120-125.

8. Dunaytsev, R. The impact of RTT and delayed ACK timeout ratio on the initial slow start phase / R.Dunaytsev, Y.Koucheryavy, J.Haiju // IPS MoMe. 2005: Proceedings.- 2005.-pp. 171-176.

9. Dunaytsev, R. Refined PFTK-model of TCP Reno throughput in the presence of correlated losses / R.Dunaytsev, Y.Koucheiyavy, J.Haiju // WWIC. 2005" Proceedings - 2005 - pp. 42-53.

Подписано к печати 25 04 2005 Объем I печ л Тир. 80 зйсз

Тип СПбГУТ. 191186 СПб, наб. р Мойки, 61 16

I

1

i (

г

РНБ Русский фонд

2006-4 9577

СОДЕРЖАНИЕ.

СПИСОК СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1 АНАЛИЗ ОСНОВНЫХ АЛГОРИТМОВ ПРОТОКОЛА TCP.

1.1 Введение и постановка задачи.

1.2 Архитектура протокола TCP.

1.2.1 Стек протоколов TCP/IP.

1.2.2 Формат TCP-сегмента.

1.3 Основные функции и алгоритмы протокола TCP.

1.3.1 Назначение протокола TCP. Общие положения.

1.3.2 Базовая передача данных.

1.3.3 Процедура мультиплексирования/демультиплексирования.

1.3.4 Обеспечение достоверности.

1.3.5 Управление соединением.

1.3.6 Управление потоком.

1.3.7 Управление перегрузкой и особенности различных реализаций протокола TCP.

1.4 Анализ использования различных реализаций протокола TCP.

Выводы.

ГЛАВА 2 АНАЛИЗ ОСНОВНЫХ МЕТОДОВ ОЦЕНКИ СРЕДНЕЙ СКОРОСТИ ПЕРЕДАЧИ ДАННЫХ ПО ПРОТОКОЛУ TCP.

2.1 Введение и постановка задачи.

2.2 Математическая модель общей реализации протокола TCP

TCP Reno/NewReno/S АСК).

2.2.1 Используемые предположения.

2.2.2 Построение модели.

2.2.3 Анализ модели.

2.3 Математическая модель TCP Reno (PFTK-модель).

2.3.1 Используемые предположения.

2.3.2 Построение модели.

2.3.3 Анализ модели.

Выводы.

ГЛАВА 3 РАЗРАБОТКА МЕТОДОВ ОЦЕНКИ СРЕДНЕЙ СКОРОСТИ ПЕРЕДАЧИ ДАННЫХ ПО ПРОТОКОЛУ TCP.

3.1 Введение и постановка задачи.

3.2 Используемые предположения.

3.3 Метод оценки средней скорости передачи данных по протоколу TCP Reno.

3.3.1 Обнаружение потери в результате получения трех повторных АСК.

3.3.2 Обнаружение потери в результате получения трех повторных АСК или истечения RTO.

3.3.3 Ограничение скорости передачи данных со стороны приемника.

3.3.4 Результирующая формула средней скорости передачи данных по протоколу TCP Reno.

3.4 Метод оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady).

3.4.1 Обнаружение потери в результате получения трех повторных АСК.

3.4.2 Обнаружение потери в результате получения трех повторных АСК или истечения RTO.

3.4.3 Ограничение скорости передачи данных со стороны приемника.

3.4.4 Результирующая формула средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady).

Выводы.

ГЛАВА 4 АНАЛИЗ ТОЧНОСТИ РАЗРАБОТАННЫХ

МЕТОДОВ ОЦЕНКИ СРЕДНЕЙ СКОРОСТИ ПЕРЕДАЧИ ДАННЫХ

ПО ПРОТОКОЛУ TCP.

4.1 Введение и постановка задачи.

4.2 Сценарий имитационного моделирования.

4.2.1 Конкурирующий трафик.

4.2.2 Топология сети и параметры конфигурации.

4.3 Анализ точности разработанного метода оценки средней скорости передачи данных по протоколу TCP Reno.

4.4 Анализ точности разработанного метода оценки средней скорости передачи данных по протоколу TCP NewReno.

Выводы.

RTT Round Trip Time, время обращения сегмента rwnd receiver window, окно приемника

SACK Selective Acknowledgement, выборочное подтверждение

SMSS Sender Maximum Segment Size, максимальный размер сегмента данных передатчика

SN Sequence Number, порядковый номер ssthresh slow start threshold, порог медленного запуска

TCP Transmission Control Protocol, протокол управления передачей

TFRC TCP Friendly Rate Control, протокол дружественного TCP управления скоростью передачи данных

UDP User Datagram Protocol, протокол передачи пользовательских дейтаграмм

WWW World Wide Web, гипермедийная служба в Интернет

ВВЕДЕНИЕ

Актуальность проблемы. Протокол управления передачей (Transmission Control Protocol, TCP) является доминирующим протоколом транспортного уровня в Интернет. Согласно исследованиям [70], от 60% до 90% всего трафика в Интернет, включая трафик службы World Wide Web, передачи файлов (FTP), электронной почты (E-mail) и т.д., передается с помощью протокола TCP. Столь широкое применение протокола TCP определило пристальное внимание к нему со стороны специалистов, занимающихся проблемами обеспечения качества обслуживания (Quality of Service, QoS) в Интернет. Помимо традиционных измерений и имитационного моделирования, в последнее десятилетие значительное число исследовательских работ [21,23,27

29,31,32,34,35,50,55,56,62,63,66,71,75,78,80-82,89,96,112,121] было адресовано разработке математических моделей функционирования протокола TCP. В числе авторов, получивших важные результаты в этой области, можно отметить К.Авраченкова, M.Mathis, J.Padhye, N.Cardwell, B.Sikdar и ряд других авторов.

В то же время предполагается [13,15,36,57,65,74,76], что одну из основных составляющих трафика Интернет в ближайшем будущем будут создавать услуги передачи мультимедийной информации: потоковое видео, Интернет-радио и т.п. Согласно принятой классификации [18], создаваемый данными услугами трафик характеризуется как изохронный и устойчивый к потерям. Изохронность трафика предполагает, что имеется некоторый порог чувствительности к задержкам, при превышении которого резко снижается качество предоставляемой услуги (например, превышение порога задержки в 100-150 мс при передаче голоса резко снижается качество воспроизводимого голоса). Устойчивость данного трафика к потерям объясняется тем, что небольшое количество отсутствующих данных может быть заменено аппроксимацией на основе принятых данных, а также тем, что услуги потокового типа ориентированы на передачу аудио/видео информации и ее незамедлительное воспроизведение, в результате чего оконечный пользователь и является той системой, которая оценивает качество предоставляемой услуги. Устойчивость к потерям также имеет свои границы, поэтому процент потерянных пакетов не должен превышать некоторый предел (например, не более 1 %).

В связи с отмеченными особенностями, применение протокола передачи пользовательских дейтаграмм (User Datagram Protocol, UDP) для потокового мультимедийного трафика предпочтительнее, чем протокола TCP, так как реализованная в протоколе TCP функция управления перегрузкой с резким уменьшением скорости передачи при обнаружении потери может существенно ухудшить качество предоставляемой услуги за счет увеличения задержки доставки данных и дисперсии этой задержки [15,44,61,76,81,107]. Однако отсутствие каких-либо алгоритмов управления перегрузкой в протоколе UDP может привести к ухудшению условий функционирования параллельных соединений TCP (т.е. соединений TCP, использующих общий канальный ресурс совместно с потоками UDP), а также к перегрузке сети [25,51,52,57,72,74,90].

В последние годы был предложен ряд механизмов [22,25,33,4546,77,81,91,101,103,106,115-117], позволяющих осуществлять адаптивное управление трафиком, создаваемым, в том числе, и потоками UDP. Протокол дружественного TCP управления скоростью передачи данных (TCP Friendly Rate Control, TFRC), определенный в документе RFC 3448 [103], является одним из наиболее проработанных и перспективных механизмов для адаптивного управления скоростью передачи данных и реализации функции управления перегрузкой при использовании протокола UDP для передачи потокового мультимедийного трафика. Протокол TFRC позволяет прикладному процессу передавать данные примерно с той же скоростью, что и протокол TCP в аналогичных условиях, но при этом избегая резкого уменьшения скорости передачи данных в случае потери пакетов. При использовании данного протокола приемник TFRC сообщает передатчику информацию о потерях, а передатчик TFRC рассчитывает скорость передачи данных на основе полученной информации, времени обращения пакета и формулы, определяющей среднюю скорость передачи данных по протоколу TCP в аналогичных условиях.

Данная формула была получена в работе J.Padhye, V.Firoiu, D.Towsley и J.Kurose (и широко известна как PFTK-модель) на основе математического моделирования передачи данных по протоколу TCP Reno [82] в длительном соединении в условиях пачечного процесса потерь, возникающим при использовании в маршрутизаторах алгоритма усечения хвоста очереди (Tail-Drop) с дисциплиной обслуживания FIFO (First In, First Out). В то же время анализ показывает, что используемое в PFTK-модели упрощенное представление таких алгоритмов, как быстрая повторная передача и быстрое восстановление, а также отсутствие рассмотрения фазы медленного запуска после таймаута может приводить к существенно завышенной оценке средней скорости передачи данных по протоколу TCP Reno в условиях пачечного процесса потерь.

Необходимо отметить, что указанная модель является одной из важнейших в области математического моделирования функционирования протокола TCP. Результирующая формула, полученная в данной работе, часто применяется для проверки адекватности новых математических моделей [21,31,55,96], а также используется в различных исследовательских работах [34,56,75,112] и книгах [14,95]. Как следствие, неточность данной формулы может приводить к неверным результатам или некорректным выводам. Следовательно, представляется необходимой разработка метода оценки средней скорости передачи данных по протоколу TCP Reno с более полным учетом алгоритмов, используемых в протоколе TCP.

Более того, согласно исследованиям [73,83], наиболее распространенной на сегодняшний день реализацией протокола TCP является TCP NewReno [109]. Анализ опубликованных исследований показывает, что недостаточное внимание было уделено математическому моделированию передачи данных по протоколу TCP NewReno. Соответственно, важной задачей является разработка метода оценки средней скорости передачи данных по протоколу TCP NewReno для последующего использования полученной формулы в протоколе TFRC.

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

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

TCP были выбраны следующие реализации: TCP Reno и TCP NewReno (вариант Slow-but-Steady). При этом поставленная цель достигается путем решения следующих основных задач:

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

2. Анализ существующих методов оценки средней скорости передачи данных по протоколу TCP. Определение возможных подходов к разработке метода оценки средней скорости передачи данных по протоколу TCP и недостатков существующих методов.

3. Разработка метода оценки средней скорости передачи данных по протоколу TCP Reno.

4. Разработка метода оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady).

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

Для проведения численных расчетов и статистического анализа в диссертационной работе использовался пакет программ Mathcad 2000 Professional. Для проверки адекватности разработанных методов оценки средней скорости передачи данных по протоколу TCP использовался программный продукт моделирования сетей связи ns-2 [124]. Для анализа и обработки данных, полученных в результате имитационного моделирования, использовались утилиты awk [123] и Windows Grep [125].

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

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

- метод оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady) в длительном соединении в условиях пачечного процесса потерь.

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

Использование результатов работы в протоколе TFRC для адаптивного управления скоростью передачи потокового мультимедийного трафика по протоколу UDP позволит обеспечить совместимость с соединениями TCP, где, согласно документу RFC 2309 [90], TCP-совместимым потоком является поток, реагирующий на сообщения о перегрузке и средняя скорость передачи данных которого в установившемся состоянии не превышает среднюю скорость передачи данных в соединении TCP в аналогичных условиях.

Апробация работы и публикации. Результаты диссертационной работы были представлены в форме докладов [6-11,41-43] на следующих научно-технических конференциях:

1) 56-я научно-техническая конференция профессорско-преподавательского состава, научных сотрудников и аспирантов ГУТ им. проф. М.А. Бонч-Бруевича, Санкт-Петербург, 26-30 января, 2004 г.

2) 57-я научно-техническая конференция профессорско-преподавательского состава, научных сотрудников и аспирантов ГУТ им. проф. М.А. Бонч-Бруевича, Санкт-Петербург, 24-28 января, 2005 г.

3) 8-я международная конференция «Internet, Multimedia Systems and Applications», Кауаи (США), 16-18 августа, 2004 г.

4) 3-й международный семинар «Internet Performance, Simulation, Monitoring and Measurements», Варшава (Польша), Технологический Университет Варшавы, 14-15 марта, 2005 г.

5) 3-я международная конференция «Wired/Wireless Internet Communications», Ксанти (Греция), 11-13 мая, 2005 г.

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

- новые аналитические результаты функционирования протокола TCP в условиях пачечного процесса потерь;

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

- метод оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady) в длительном соединении в условиях пачечного процесса потерь;

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

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

Публикации. Основные результаты диссертационной работы представлены в 9 печатных работах.

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

Выводы

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

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

2. На точность оценки средней скорости передачи данных по протоколам TCP Reno и TCP NewReno (вариант Slow-but-Steady) согласно разработанным методам влияет характер процесса потерь сегментов данных. Если при передаче окна, состоящего из W сегментов данных и потере последовательности сегментов данных, вероятность того, что будет потеряно 5 сегментов, имеет равномерное распределение от 1 до W, то погрешность оценки средней скорости передачи данных по протоколам TCP Reno и TCP NewReno (вариант Slow-but-Steady) согласно разработанным методам составляет в среднем 1%.

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

4. Доказано, что используемая в протоколе TFRC формула, полученная на основе PFTK-модели, дает существенно завышенную оценку средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady). Учитывая, что, согласно исследованиям, реализация TCP NewReno является доминирующей в Интернет, подобная завышенная оценка может приводить к более «агрессивному» поведению соединений, использующих протокол TFRC, по сравнению с соединениями TCP.

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Проведен анализ функционирования протокола TCP NewReno (вариант Slow-but-Steady) в условиях пачечного процесса потерь, на основе которого сделан вывод о необходимости учета алгоритмов быстрой повторной передачи, быстрого восстановления и медленного запуска при разработке метода оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady).

5. Разработан метод оценки средней скорости передачи данных по протоколу TCP NewReno (вариант Slow-but-Steady) в длительном соединении в условиях пачечного процесса потерь.

6. Проведено имитационное моделирование передачи данных по протоколам TCP Reno и TCP NewReno в присутствии конкурирующего трафика, создаваемого ON/OFF источниками UDP.

7. Проведенные исследования доказывают, что разработанные методы оценки средней скорости передачи данных по протоколу TCP имеют погрешность в среднем менее 5% в большом диапазоне значений вероятности потери первого сегмента данных, в то время как PFTK-модель и формула, используемая в протоколе TFRC, существенно переоценивают значение средней скорости передачи данных по протоколам TCP Reno и TCP NewReno (погрешность указанных методов оценки составляет в среднем 50% и 40% соответственно). Использование разработанных методов в протоколе TFRC для адаптивного управления скоростью передачи потокового мультимедийного трафика по протоколу UDP позволит обеспечить совместимость данных потоков с соединениями TCP в соответствии с требованиями документа RFC 2309.

1. Вентцель, Е.С. Теория вероятностей / Е.С.Вентцель- М.: Наука, 1969 576 с.

2. Вентцель, Е.С. Теория вероятностей и ее инженерные приложения / Е.С.Вентцель, Л.А.Овчаров- М.: Высшая школа, 2000.- 320 с.

3. Выгодский, М.Я. Справочник по высшей математике / МЯ.Выгодский- М.: Физматгиз, 1963 870 с.

4. Гмурман, В.Е. Теория вероятностей и математическая статистика / В.Е.Гмурман.-М.: Высшая школа, 1977.-479 с.

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

6. Дунайцев, Р.А. Влияние сетевой асимметрии на характеристики протокола TCP / Р.А.Дунайцев, Е.А.Кучерявый // Телемультимедиа.- 2004- № 1С. 19-23.

7. Дунайцев, Р.А. Методы ускорения для коротких передач данных / Р.А.Дунайцев, Е.А.Кучерявый // Телемультимедиа.- 2004- № 2 С. 14-18.

8. Дунайцев, Р.А. Оценка объема Web-трафика создаваемого пользователями домашней сети / Р.А.Дунайцев, Е.А.Кучерявый // Телемультимедиа.- 2004-№4.-С. 10-14.

9. Дунайцев, Р.А. Анализ WWW-трафика различных типов пользователей / Р.А.Дунайцев // 56 научн.-техн. конф. профессорско-преподавательского состава, научных сотрудников и аспирантов, СПб. 2004: Тез. докл.- ГУТ, СПб., 2004.- С. 20.

10. Дунайцев, Р.А. Улучшенная и дополненная PFTK-модель для протокола TCP Reno / Р.А.Дунайцев, Е.А.Кучерявый // Электросвязь 2005- № 3 - С. 27-31.

11. Камер, Д.Э. Сети TCP/IP, том 1. Принципы, протоколы и структура, 4-е изд. / Д.Э.Камер-М.: Издательский дом «Вильяме», 2003 880 с.

12. Кох, Р. Эволюция и конвергенция в электросвязи / Р.Кох, Г.Г.Яновский.- М.: Радио и Связь, 2001.- 280 с.

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

14. Кучерявый, Е.А. Управление трафиком и качество обслуживания в сети Интернет / Е.А.Кучерявый СПб.: Наука и Техника, 2004- 336 с.

15. Кучерявый, Е.А. NS-2 как универсальное средство имитационного моделирования сетей связи: http://www.cs.tut.fi/~yk/ns2ru/ns2.pdf

16. Мамаев, М.А. Телекоммуникационные технологии. Сети TCP/IP. Учебное пособие / М.А.Мамаев- Владивосток: Изд-во ВГУЭиС, 1999.

17. Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы, 2-е изд. / В.Г.Олифер, Н.А.Олифер СПб.: Питер, 2005.- 864 с.

18. Прудников, А.П. Интегралы и ряды. Элементарные функции / А.П.Прудников, Ю.А.Брычков, О.И.Маричев.-М.: Наука, 1981.- 800 с.

19. Пустовалов, Г.Е. Погрешности измерений. Методическая разработка по общему физическому практикуму / Г.Е.Пустовалов М.: Изд-во МГУ, 2001.

20. A Markovian model for the stationary behavior of TCP / S.Fortin, B.Sericola; Technical Report. IRISA-INRIA, France.- 2001, RR 4240.-31 p.

21. A model based TCP-friendly rate control protocol / J.Padhye, J.Kurose, D.Towsley et al.; Technical Report. Department of Computer Science, University of Massachusetts, USA.- 1998, TR 98-04.- 18 p.

22. Ajmone, M. Performance analysis of TCP connections sharing a congested Internet link / M.Ajmone, C.Casetti, R.Gaeta et al. // Performance Evaluation 2000 - vol. 42(2-3).-pp. 109-127.

23. Akimaru, H. Teletrafflc. Theory and applications / H.Akimaru, K.Kawashima.-Berlin: Springer-Verlag, 1993.

24. Albuquerque, C. Network border patrol: preventing congestion collapse and promoting fairness in the Internet / C.Albuquerque, T.Suda, B.Vickers // IEEE/ACM Transactions on Networking.-2004.-vol. 12(1).-pp. 173-186.

25. Allman, M. Estimating loss rates with TCP / M.Allman, W.Eddy, S.Ostermann // ACM SIGMETRICS Performance Evaluation Review.- 2003.- vol. 31(3).-pp. 12-24.

26. Altman, E. A stochastic model of ТСРЯР with stationary random losses / E.Altman, K.Avrachenkov, C.Barakat // ACM SIGCOMM Computer Communication Review.- 2000.- vol. 30(4).- pp. 231-242.

27. Altman, E. Impact of bursty losses on TCP performance / E.Altman, K.Avrachenkov, C.Barakat // ACM SIGMETRICS Performance Evaluation Review.- 2000.- vol. 42(2-3).- pp. 129-147.

28. Altman, E. TCP in presence of bursty losses / E.Altman, K.Avrachenkov, C.Barakat //ACM SIGMETRICS. 2000: Proceedings.-2000.-pp. 124-133.

29. Altman, E. NS simulator course for beginners. Lecture notes: http://www-sop.inria.fr/mistral/personnel/Eitan.Altman/ns.htm

30. Analytical Markovian model of TCP congestion avoidance algorithm performance / O.Bogoiavlenskaia, M.Kojo, M.Mutka et al.; Technical Report. Department of Computer Science, University of Helsinki, Finland.- 2002, C-2002-13 39 p.

31. Barakat, С. ТСРЯР modeling and validation / C.Barakat // IEEE Network.- 2001.-vol. 15.-pp. 38-47.

32. Bolot, J. Control mechanisms for packet audio in the Internet / J.Bolot, A.Vega-Garcia // IEEE INFOCOM. 1996: Proceedings 1996.- pp. 232-239.

33. Cardwell, N. Modeling TCP latency / N.Cardwell, S.Savage, T.Anderson // IEEE INFOCOM. 2000: Proceedings.- 2000.- pp. 1742-1751.

34. Casetti, С. A new approach to model the stationary behavior of TCP connections / C.Casetti, M.Meo // IEEE INFOCOM. 2000: Proceedings.- 2000.- pp. 367-375.

35. Chesire, M. Measurement and analysis of a streaming-media workload / M.Chesire, A.Wolman, G Voelker et al. // USITS. 2001: Proceedings.- 2001.- pp. 534-543.

36. Computing TCP's retransmission timer: RFC 2988 / V.Paxson, M.Allman 2000.

37. Congestion control in IP/TCP internetworks: RFC 896 / J.Nagle 1984.

38. Congestion control principles: RFC 2914 / S.Floyd 2000.

39. Crovella, M. Self-similarity in World Wide Web traffic: evidence and possible causes / M.Crovella, A.Bestavros // IEEE/ACM Transactions on Networking1997.- vol. 5(6).-pp. 835-846.

40. Dunaytsev, R. Estimation of WWW-traffic generated by users in home networks / R.Dunaytsev, Y.Koucheryavy, J.Harju // IASTED IMSA. 2004: Proceedings.-2004.-pp. 120-125.

41. Dunaytsev, R. The impact of RTT and delayed ACK timeout ratio on the initial slow start phase / R.Dunaytsev, Y.Koucheryavy, J.Harju // IPS MoMe. 2005: Proceedings-2005.-pp. 171-176.

42. Dunaytsev, R. Refined PFTK-model of TCP Reno throughput in the presence of correlated losses / R.Dunaytsev, Y.Koucheryavy, J.Harju // WWIC. 2005: Proceedings 2005 - pp. 42-53.

43. End-to-end quality in multimedia applications / M.Claypool, J.Riedl; Technical Report. Department of Computer Science, University of Massachusetts, USA1998.TR 98-18.-17 p.

44. Equation-based congestion control for unicast applications / S.Floyd, M.Handley, J.Padhye; Technical Report. International computer science institute, Berkeley, USA.- 2000, TR 00-003.- 22 p.

45. Experiments with a layered transmission scheme over the Internet / T.Turletti, S.Parisis, J.Bolot; Technical Report. INRIA, France.- 1997, RR 3297.- 26 p.

46. Explaining World Wide Web traffic self-similarity / M.Crovella, A.Bestavros; Technical Report. Computer Science Department, Boston University, USA.- 1995, TR 95-015.- 19 p.

47. Fall, K. Simulation-based comparisons of Tahoe, Reno, and SACK TCP / K.Fall, S.Floyd // ACM SIGCOMM Computer Communication Review- 1996.-vol. 26(3).- pp. 5-21.

48. Fall, K. The ns manual: http://www.isi.edu/nsnam/ns/ns-documentation.html

49. Floyd, S. Connections with multiple congested gateways in packet-switched networks, part 1: one-way traffic / S.Floyd // ACM SIGCOMM Computer Communication Review.- 1991.- vol. 21(5).- pp. 30-47.

50. Floyd, S. Random early detection gateways for congestion avoidance / S.Floyd, V.Jacobson // IEEE/ACM Transactions on Networking.- 1993- vol. 1(4).-pp. 397-413.

51. Floyd, S. Promoting the use of end-to-end congestion control in the Internet / S.Floyd, K.Fall // IEEE/ACM Transactions on Networking.- 1999.- vol. 7(4).- pp. 458-472.

52. Floyd, S. Internet research needs better models / S.Floyd, E.Kohler // ACM SIGCOMM Computer Communication Review 2003.- vol. 33(1).- pp. 29-34.

53. Floyd, S. Difficulties in simulating the Internet / S.Floyd, V.Paxson // IEEE/ACM Transactions on Networking.- 2001.- vol. 9(4).- pp. 392-403.

54. Fortin, S. Refined TCP performance evaluation with simple modeling / S.Fortin, B.Sericola// ASMTA. 2003: Proceedings.-2003-pp. 193-198.

55. Fu, S. Modelling TCP Reno with spurious timeouts in wireless mobile environment / S.Fu, M.Atiquzzaman // ICCCN. 2003: Proceedings.- 2003.- pp. 155-165.

56. Hong, D. Evaluating the impact of emerging streaming media applications on TCP/IP performance / D.Hong, C.Albuquerque, C.Oliveira et al. // IEEE Communications Magazine 2001- vol. 39(4).- pp. 76-82.

57. Improving simulation for network research / S.Bajaj, L.Breslau, D.Estrin et al.; Technical Report. USC Computer Science Department, USA.- 1999, TR 99-702b-11 p.

58. Increasing TCP's initial window: RFC 3390 / M.Allman, S.Floyd, C.Partridge -2002.

59. Internet protocol: RFC 791 / J.Postel 1981.

60. Jacobs, S. Providing video services over networks without quality of service guarantees / S.Jacobs, A.Eleftheriadis // RTMW. 1996: Proceedings.- 1996- pp. 120-123.

61. Khalifa, I. An overview and comparison of analytical TCP models / I.Khalifa, L.Trajkovic // IEEE ISCAS. 2004: Proceedings.- 2004. pp. 469-472.

62. Kim, B. Loss recovery modeling of TCP Reno over wireless links / B.Kim, D.Kim, J.Han et al. // ECUMN. 2004: Proceedings.- 2004. pp. 165-174.

63. Known TCP implementation problems: RFC 2525 / V.Paxson, M.Allman, S.Dawson et al. 1999.

64. Koucheryavy, Y. Multimedia traffic delivery over next-generation telecommunications networks / PhD thesis. Institute of Communications Engineering, Tampere University of Technology, Finland, 2004.- 147 p.

65. Lakshman, T. The performance of TCP/IP for networks with high bandwidth-delay products and random loss / T.Lakshman, U.Madhow // IEEE/ACM Transactions on Networking.- 1997.- vol. 5(3).- pp. 336-350.

66. Lang, T. Evaluation of different TCP versions in non-wireline environments / PhD thesis. Institute of Telecommunications Research, University of South Australia, 2002.- 199 p.

67. Law, A. Simulation modeling and analysis / A.Law, D.Kelton.- New York: McGraw-Hill, Inc., 1991.

68. Leon-Garcia, A. Communications networks. Fundamental concepts and key architectures / A.Leon-Garcia, I.Widjaja Singapore: McGraw-Hill, Inc., 2000.

69. Longitudinal study of Internet traffic in 1998-2003 / M.Fomenkov, K.Keys, D.Moore et al.; Technical Report. Cooperative Association for Internet Data Analysis (CAIDA).- 2003.- 6 p.

70. Mathis, M. The macroscopic behavior of the TCP congestion avoidance algorithm / M.Mathis, J.Semke, J.Mahdavi // ACM SIGCOMM Computer Communication Review.- 1997.- vol. 27(3).- pp. 67-82.

71. Measurements of the congestion responsiveness of Windows streaming media / J.Nichols, M.Claypool, R.Kinicki et al.; Technical Report. Worcester Polytechnic Institute, USA.- 2004, TR 04-075.- 6 p.

72. Mediano, A. Measuring the evolution of transport protocols in the Internet: the extended version / A.Mediano, M.Allman, S.Floyd // ACM SIGCOMM Computer Communication Review.- 2005- vol. 21(5).- pp. 30-47.

73. Merwe, J. Streaming video traffic: characterization and network impact / J.Merwe, S.Sen, C.Kalmanek // IWCW. 2002: Proceedings.- 2002.- pp. 114-130.

74. Modeling the performance of short TCP connections / N.Cardwell, S.Savage, T.Anderson; Technical Report. Department of Computer Science and Engineering, University of Washington, USA.- 1998- 27 p.

75. Multimedia streaming via TCP: an analytic performance study / B.Wang, J.Kurose, P.Shenoy et al.;. Technical Report. Department of Computer Science, University of Massachusetts, USA.- 2004, TR 04-21.- 18 p.

76. Mustafa, A. End-to-end IP rate control / A.Mustafa, M.Hassan // IASTED ADCOM. 2000: Proceedings.- 2000. pp. 279-282.

77. Olsen, J. Stochastic modeling and simulation of the TCP protocol / PhD thesis. Department of Mathematics, Uppsala University, Sweden, 2003.- 94 p.

78. On the performance of TCP loss recovery mechanisms / M.Lima, N.Fonseca, J.Rezende; Technical Report. Federal University of Rio de Janeiro, Brasilia.-2003.-5 p.

79. Ott, Т. The stationary behavior of ideal TCP congestion avoidance: http://citeseer.ist.psu.edu/ott96stationary.html

80. Padhye, J. Towards a comprehensive congestion control framework for continuous media flows in best effort networks / PhD thesis. Department of Computer Science, University of Massachusetts, USA, 2000.- 127 p.

81. Padhye, J. Modeling TCP Reno performance: a simple model and its empirical validation / J.Padhye, V.Firoiu, D.Towsley et al. // IEEE/ACM Transactions on Networking.-2000.- vol. 8(2).- pp. 133-145.

82. Padhye, J. On inferring TCP behavior / J.Padhye, S.Floyd // ACM SIGCOMM. 2001: Proceedings.- 2001.- pp. 287-298.

83. Park, K. On the relation between file sizes, transport protocols, and self-similar network traffic / K.Park, G.Kim, M.Crovella // ICNP. 1996: Proceedings.- 1996.-pp. 171-180.

84. Park, K. Self-similar network traffic and performance evaluation / K.Park, W.Willinger.- NY: Wiley, 2000.

85. Paxson, V. Measurements and analysis of end-to-end Internet dynamics / PhD thesis. Computer Science Division, University of California, USA, 1998.- 389 p.

86. Paxson, V. Automated packet trace analysis of TCP implementations / V.Paxson // ACM SIGCOMM Computer Communication Review.- 1997.- vol. 27(4).-pp. 167-179.

87. Practical analysis of TCP implementations: Tahoe, Reno, NewReno / B.Moraru, F.Copaciu, G.Lazar et al.; Technical Report. Technical University of Cluj-Napoca, Romania.- 2004.- 6 p.

88. Predicting TCP throughput from non-invasive data / M.Goyal, R.Guerin, R.Rajan; Technical Report. University of Pennsylvania, USA 2001- 40 p.

89. Recommendations on queue management and congestion avoidance in the Internet: RFC 2309 / R.Braden, D.Clark, J.Crowcroft et.al. 1998.

90. Rejaie, R. RAP: an end-to-end rate-based congestion control mechanism for realtime streams in the Internet / R.Rejaie, M.Handley, D.Estrin // IEEE INFOCOM. 1999: Proceedings.- 1999.-pp. 1337-1345.

91. Requirements for Internet hosts communications layers: RFC 1122 / R.Braden -1989.

92. Ross, S. Applied probability models with optimization applications / S.Ross.-Dover: Springer-Verlag, 1970.

93. RTP: a transport protocol for real-time applications: RFC 1889 / H.Schulzrinne, S.Casner, R.Frederick et al. 1996.

94. Schiller, J. Mobile communications, 2nd edition / J.Schiller.- Kent: Addison-Wesley, 2000.

95. Sikdar, B. Analytic models for the latency and steady-state throughput of TCP Tahoe, Reno, and SACK / B.Sikdar, S.Kalyanaraman, K.Vastola // IEEE/ACM Transactions on Networking.- 2003 vol. 11(6).- pp. 959-971.

96. Sisalem, D. The loss-delay based adjustment algorithm: a TCP-friendly adaptation scheme/ D.Sisalem, H.Schulzrinne // NOSSDAV. 1998: Proceedings- 1998-pp. 215-226.

97. Sizing router buffers / G.Appenzeller, I.Keslassy, N.McKeown; Technical Report. Stanford University, USA.- 2004, TR 04-HPNG-06-08-00.- 12 p.

98. SPAND: shared passive network performance discovery / S.Seshan, M.Stemm, R.Katz; Technical Report. University of California, USA.- 1997, CSD 97-96713 p.

99. Supporting differentiated service classes: TCP congestion control mechanisms / C.Semeria; Technical Report. Juniper Networks, Inc., Sunnyvale, USA.- 2002.

100. Tan, D. Real-time Internet video using error resilient scalable compression and TCP-friendly transport protocol / D.Tan, A.Zakhor // IEEE Transactions on Multimedia.- 1999.-vol. 1(2).-pp. 172-186.

101. TCP congestion control: RFC 2581 / M.Allman, V.Paxson, W.Stevens 1999.

102. TCP friendly rate control (TFRC): protocol specification: RFC 3448 / M.Handley, S.Floyd, J.Padhye et al. 2003.

103. TCP selective acknowledgment options: RFC 2018 / M.Mathis, J.Mahdavi, S.Floyd et al. 1996.

104. TCP slow start, congestion avoidance, fast retransmit, and fast recovery algorithms: RFC 2001 / W.Stevens 1997.

105. TEAR: TCP emulation at the receivers flow control for multimedia streaming / I.Rhee, V.Ozdermir, Y.Yi; Technical Report. Department of Computer Science, North Carolina State University, US A - 2000 - 24 p.

106. The effects of jitter on the perceptual quality of video / M.Claypool, J.Tanner; Technical Report. Department of Computer Science, University of Massachusetts, USA.- 1999, TR 99-02.- 13 p.

107. The NewReno modification to TCP's recovery algorithm: RFC 2582 / S.Floyd, T.Henderson-1999.

108. The NewReno modification to TCP's recovery algorithm: RFC 3782 / S.Floyd, T.Henderson, A.Gurtov 2004.

109. The stationarity of Internet path properties: routing, loss, and throughput / Y.Zhang, V.Paxson, S.Shenker; Technical Report. AT&T Center for Internet Research, USA.-2000.- 14 p.

110. Tijms, H. Stochastic modeling and analysis: a computational approach / H.Tijms London: John Wiley & Sons Ltd., 1988.

111. Tokuda, K. TCP throughput analysis with variable packet loss probability for improving fairness among long/short-lived TCP connections / K.Tokuda, G.Hasegawa, M.Murata // IEEE CQR. 2002: Proceedings.- 2002.- pp. 145-149.

112. Transmission control protocol: RFC 793 / J.Postel 1981.

113. User datagram protocol: RFC 768 / J.Postel 1980.

114. Vicisano, L. TCP-like congestion control for layered multicast data transfer / L.Vicisano, L.Rizzo, J.Crowcroft//IEEE INFOCOM. 1998: Proceedings.- 1998.-pp. 996-1003.

115. Vickers, V. Source-adaptive multi-layered multicast algorithms for real-time video distribution / V.Vickers, C.Albuquerque, T.Suda // IEEE/ACM Transactions on Networking.- 2000 vol. 8(6).- pp. 720-733

116. Wang, Q. TCP-friendly congestion control schemes in the Internet / Q.Wang, K.Long, S.Cheng et al. // ICII. 2001: Proceedings.- 2001.- pp. 205-210.

117. Willinger, W. Self-similarity through high-variability: statistical analysis of Ethernet LAN traffic at the source level / W.Willinger, M.Taqqu, R.Sherman et al. // IEEE/ACM Transactions on Networking.- 1997- vol. 5 pp. 100-113.

118. Zhang, Y. Characterizing end-to-end Internet performance / PhD thesis. Graduate school of Cornell University, USA, 2001- 142 p.

119. Zhang, Y. On the constancy of Internet path properties / Y.Zhang, N.Duffield, V.Paxson et al. // ACM SIGCOMM IMW. 2001: Proceedings.- 2001.- pp. 197-211.

120. Zheng, D. A comprehensive TCP stochastic model / D.Zheng, G.Lazarou, H.Rose // IASTED CUT. 2003: Proceedings.- 2003.- pp. 291-296.

121. Windows Grep-http://www.wingrep.com/