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

Сивов Анатолий Александрович

РАЗРАБОТКА, РЕАЛИЗАЦИЯ И АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ

МОДИФИЦИРОВАННОГО ТРАНСПОРТНОГО ПРОТОКОЛА

Специальность 05.13.11 –

математическое и программное обеспечение

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Ярославль 2013

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Ярославский государственный университет им. П.Г. Демидова»

Научный руководитель: доктор физико-математических наук, Профессор Соколов Валерий Анатольевич

Официальные оппоненты: Смелянскоий Руслан Леонидович, доктор физико-математических наук, членкорреспондент Российской академии наук, заведующий лабораторией факультета вычислительной математики и кибернетики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный университет имени М.В. Ломоносова»

Пакулин Николай Витальевич, кандидат физико-математических наук, старший научный сотрудник Федерального государственного бюджетного учреждения науки Института системного программирования Российской академии наук

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт проблем информатики Российской академии наук

Защита диссертации состоится 23 мая 2013 г. в 15.00 на заседании диссертационного совета Д.002.087.01 при Федеральном государственном бюджетном учреждении науки Институте системного программирования Российской академии наук по адресу: 109004, Москва, ул. Александра Солженицына, д.25.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Института системного программирования Российской академии наук.

Автореферат разослан «_» 2013 г.

Ученый секретарь /Прохоров С.П./ диссертационного совета, кандидат физ.-мат. наук

Общая характеристика работы

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

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

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

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

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

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

Так как TCP реагирует на любую потерю сегмента уменьшением порогового значения в два раза, а рост размеров окна перегрузки после достижения порогового значения производится линейно, TCP неэффективен при работе в высокоскоростных сетях с большими значениями RTT (Round Trip Time, интервал времени между отправкой сегмента и получением подтверждения о его доставке), потому что даже незначительное количество ошибок в сети приводит к существенному недоиспользованию доступных ресурсов.

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

алгоритмы, использующие потерю в качестве индикатора перегрузки (в англоязычной литературе они обозначаются loss-based), и алгоритмы, использующие для контроля перегрузки темпоральные характеристики потока (например, RTT) (в англоязычной литературе они обозначаются delayТакже проводятся исследования, направленные на создание based).

гибридных алгоритмов, сочетающих в себе черты алгоритмов обоих типов.

Ярким примером подобного алгоритма является разработанный в Microsoft Research алгоритм Compound TCP.

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

В исследованиях, направленных на улучшение работы TCP в беспроводных сетях (см. работы Casetti, Ferorelli, Fu, Liew, Grieco, Mascolo и др.), применяются способы определения доступной пропускной способности сети для более быстрого восстановления после мультипликативного сброса путем более гибкого манипулирования пороговым значением медленного старта.

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

измерении задержек при доставке данных. Классическим примером проактивного алгоритма является TCP Vegas. Такие алгоритмы в своем большинстве измеряют задержки с помощью RTT. Использование данного индикатора может привести к некорректным выводам, так как в составлении значений RTT участвует время передачи данных по прямому каналу, а также время передачи подтверждения по обратному каналу. Алгоритм, использующий RTT, вынужден иметь дело с такими явлениями как отложенная отправка подтверждений. Также он не в состоянии отличить задержки, произошедшие из-за пребывания сегмента с данными в очередях маршрутизаторов в прямом направлении передачи данных, от задержек, вызванных пребыванием сегмента с подтверждением в очередях маршрутизаторов в обратном направлении передачи данных. Таким образом, эти алгоритмы могут неверно интерпретировать перегрузку в обратном направлении передачи данных, вызываемую действиями других соединений, как собственную перегрузку, борьба с которой приведет к неэффективному использованию доступной пропускной способности сети.

Другим слабым местом многих проактивных алгоритмов избежания перегрузки, а также алгоритмов, направленных на оценку доступной пропускной способности, является использование пороговых значений задержки (таких как BaseRTT (базовое значение RTT)). Как показано в работах Hayes, La, Warland, Tan и др., неправильный выбор порогового значения может существенно повлиять на работу таких алгоритмов.

высокоскоростных сетях (например, Highspeed TCP, CUBIC, Scalable TCP, HTCP), модифицируют характер изменения размеров окна, делая его в определенных ситуациях более агрессивным. Для достижения пропускной способности сети они используют способ, схожий с применяемым в стандартном TCP, и не контролируют рост задержек. В надежных сетях с чрезмерной буферизацией это может вылиться в значительное увеличение RTT и неэффективное использование канала.

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

Цели работы. Цель диссертационной работы — предложить комплексное решение для преодоления недостатков TCP, разработав совместимый с TCP протокол TCP TIPS (TIPS является конкатенацией названий дополнительных полей, используемых протоколом, TI (Time Interval) и PS (Packet Sequence)), не имеющий проблем, присущих существующим модификациям. Совместимость с TCP в данном случае подразумевает возможность прозрачной замены TCP на разрабатываемый протокол для приложений, использующих TCP, без необходимости какойлибо модернизации этих приложений и возможность возврата к использованию TCP на этапе установки соединения в случае, если один из участников соединения не поддерживает новый протокол.

Создание нового протокола предусматривает разработку алгоритма управления потоком данных, предлагающего проактивную схему избежания перегрузки и разделяющего логику управления скоростью передачи и логику коррекции ошибок. Перед разрабатываемым алгоритмом поставлены следующие требования: высокий коэффициент использования пропускной способности сети, минимизация задержек при передаче данных (посредством минимизации роста длин очередей маршрутизаторов), высокая эффективность работы в ненадежных сетях и в сетях с частой сменой маршрута передачи данных, отсутствие проблем, характерных алгоритмам, основанным на использовании RTT (невозможность отложенной отправки подтверждений, неверная индикация перегрузки при наличии перегрузки в направлении, обратном направлению передачи данных). Также при использовании в сетях, содержащих потоки данных постоянной скорости, TCP TIPS должен уступать этим потокам необходимую долю пропускной способности сети при их появлении и занимать ее при их завершении, при этом не вызывая роста задержек передачи данных. Это требование накладывается на TCP TIPS для возможности его применения в сетях, передающих потоки данных, чувствительные к задержке (например, IPтелефония, IP-телевидение и др.). Такие потоки должны считаться высокоприоритетными, поэтому TCP TIPS должен уступать им требуемую долю пропускной способности сети, обеспечивая одновременно сервис надежной передачи данных, обладающий меньшим приоритетом, но эффективно использующий доступную долю пропускной способности.

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

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

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

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

TCP TIPS

симулятора ns-2, что позволило моделировать поведение протокола в сетях с различными характеристиками. Также наличие реализации в ns-2 позволило провести наряду с исследованиями поведения TCP TIPS в рамках единой программной модели эксперименты с участием ряда модификаций TCP и получить результат сравнительного анализа свойств этих протоколов и TCP TIPS.

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

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

докладывались на коллоквиумах Spring/Summer Young Researcher’s Colloquium on Software Engineering (SYRCoSE) (Екатеринбург, 2011 и Пермь, 2012), VIII международной научно-практической конференции «Современное состояние естественных и технических наук» (Москва, 2012), III международной научно-практической конференции «Научная дискуссия:

вопросы физики, математики, информатики» (Москва, 2012), международной научно-практической конференции «Тенденции развития прикладной информатики» (Ярославль, 2012), семинаре по теоретической информатике Ярославского государственного университета (Ярославль, 2012), семинаре отдела «Технологий программирования» Института Системного Программирования РАН (Москва, 2012). Разработка поддержана грантом РФФИ 12-07-31173-мол_а («Разработка, моделирование и анализ коммуникационных протоколов транспортного уровня с управлением потоком передачи данных, минимизирующим задержку»), грантом Федеральной Целевой Программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, соглашение 14.132.21. («Разработка, моделирование и анализ производительности транспортных протоколов в коммуникационных сетях»).

Результаты диссертации опубликованы в 8 работах, в том числе в работах – в изданиях из списка ВАК. Получено свидетельство о государственной регистрации программы для ЭВМ №2013611466 «Модуль протокола TCP TIPS для среды ns-2».

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

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

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

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

Параграф 1.2.1 затрагивает вопросы активного управления очередями (AQM). В нем рассмотрен ряд алгоритмов AQM (RED, BLUE, CoDel).

Параграф 1.2.2 посвящен алгоритмам борьбы с перегрузкой на транспортном уровне. В нем рассматриваются реактивные, проактивные и гибридные методы борьбы с перегрузкой, приведено описание и анализ ряда модификаций TCP (Highspeed TCP, TCP BIC, TCP CUBIC, TCP Vegas, FAST TCP, Compound TCP, TCP-Illinois, TCP Westwood+, TCP Veno). В конце первой главы следуют выводы по имеющимся модификациям TCP.

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

В начале главы следует краткое описание разработанного протокола TCP TIPS, сравнение с его предшественником ARTCP. Указаны ключевые особенности протокола TCP TIPS: отправка данных через определенные интервалы времени, называемые межсегментными интервалами, вместо отправки всплесками в пределах доступного окна, отказ от использования таких понятий как «пороговое значение медленного старта» и «окно перегрузки».

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

Для обеспечения возможности анализа значений межсегментных интервалов, измеренных получателем, на стороне отправителя необходимо предоставить получателю возможность корректно вычислять эти значения и реализовать способ их доставки отправителю. Для решения этих задач TCP TIPS использует два параметра — TI и PS, – давших название протоколу (TIPS является конкатенацией имен параметров). Параметр TI (Time Interval, промежуток времени) используется для передачи измеренного получателем значения межсегментного интервала от получателя отправителю вместе с подтверждениями о доставке сегментов. Чтобы получатель имел возможность определить, что принятые им сегменты являются соседними (то есть отправитель, например, не передавал между ними сегмент с данными, не доставленный по причине потери), отправитель последовательно нумерует все посылаемые им сегменты. Номер сегмента передается с помощью параметра PS (Packet Sequence, последовательность пакета). Значение этого параметра не имеет ничего общего с номером последовательности TCP, так как PS означает номер сегмента в передаче. Он увеличивается при каждой отправке сегмента (в том числе при повторной отправке) и никак не связан с передаваемыми в сегменте данными.

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

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

где B – пропускная способность сети, N – размер отправляемых сегментов в байтах, P – значение межсегментного интервала, наблюдаемого получателем (интервала времени между прибытием последнего бита пакета k и последнего бита пакета k + 1).

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

где I – значение межсегментного интервала, устанавливаемого отправителем, a – скорость передачи данных, устанавливаемая отправителем, T – минимальное возможное значение межсегментного интервала для данной сети (определяется пропускной способностью сети при фиксированном размере передающихся по ней сегментов), x – пропускная способность сети, P – значение межсегментного интервала, наблюдаемого получателем, b – суммарная скорость передачи данных сторонних соединений в сети.

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

где B – доступная пропускная способность сети, P' – значение межсегментного интервала, наблюдаемого получателем при скорости передачи данных a', P – значение межсегментного интервала, наблюдаемого получателем при скорости передачи данных a, I – значение межсегментного интервала, используемого отправителем для достижения скорости передачи данных a.

В разделе 2 второй главы описан алгоритм управления потоком данных в протоколе TCP TIPS. Этот алгоритм состоит из 4 состояний:

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

Рисунок 1. Взаимодействие режимов работы TCP TIPS После установки соединения методом тройного рукопожатия TCP TIPS работает в режиме медленного старта. Он устанавливает значение межсегментного интервала равным RTT, вычисленному во время установки соединения. В качестве интервала времени, в течение которого проводится усреднение значений межсегментных интервалов, измеренных получателем, также используется RTT. Пока производится усреднение значений, отправитель не изменяет скорость передачи данных. Когда усреднение завершено и имеется значение межсегментного интервала, наблюдаемое получателем, TCP TIPS проверяет наличие перегрузки. Считается, что перегрузка имеется, если где I – значение межсегментного интервала, использованного отправителем для сегментов, усреднение по которым дало значение P для межсегментного интервала, наблюдаемого отправителем, — параметр, означающий «зону нечувствительности».

Если неравенство (5) не выполняется, то считается, что перегрузки нет, и TCP TIPS уменьшает значение межсегментного интервала, деля его текущее значение на параметр SSGR > 1. В имитационной модели мы устанавливаем SSGR равным двум. В противном случае TCP TIPS проводит подготовительные действия для получения оценки доступной пропускной способности сети, определяемой с помощью алгоритма, описанного в разделе 1 второй главы. С помощью этого алгоритма TCP TIPS вычисляет отношение ak скорости передачи данных к пропускной способности сети и отношение bk суммарной скорости передачи данных сторонних соединений к пропускной способности сети:

После вычисления этих отношений TCP TIPS при наличии возможности избежать перегрузки устанавливает оценочное значение межсегментного интервала Ie:

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

компенсации перегрузки, задается формулой:

где MDF – множитель мультипликативного сброса, 0 < MDF < 1. В имитационной модели мы устанавливаем MDF = 1 / 2.

площадей прямоугольников длиной RTT и высотой, равной разности скорости передачи данных и оценки доступной пропускной способности. Для вычисления указанной площади можно воспользоваться формулой где PRTT – среднее значение RTT, вычисленное в момент обнаружения перегрузки. Первое слагаемое используется в формуле (10), только если выполняется условие Ie > P. Остальные слагаемые подставляются в формулу (10), если выполняется условие SSGRn / I' 1 / Ie.

Длительность работы в режиме компенсации перегрузки вычисляется по формуле:

где S – величина, определяемая формулой (10).

Выход из режима компенсации происходит в двух случаях: по истечении интервала времени, определенного формулой (11), или при обнаружении перегрузки согласно формуле (5). Перегрузка в режиме компенсации может возникнуть из-за действий других соединений или уменьшения пропускной способности сети по каким-либо причинам (например, смена маршрута для соединения). При выходе из режима компенсации соединение переходит в режим пробы/отмены ускорения.

Однако если причиной выхода является перегрузка, TCP TIPS сохраняет эту информацию в состоянии соединения. После выхода из режима компенсации значение межсегментного интервала устанавливается равным Ie, если причиной выхода стало окончание промежутка времени t, или равным P, полученным при вычислении среднего арифметического значений поля TI, если причиной выхода является перегрузка.

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

где SRTT – сглаженное значение RTT.

пробы/отмены ускорения площадь компенсации также будет определяться формулой (12), но вместо Ir и P будут использоваться действовавшие на стороне отправителя значения межсегментных интервалов.

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

Ускорение и отмена ускорения задаются формулами (13) и (14) соответственно.

где In – устанавливаемое значение межсегментного интервала, I' – текущее значение межсегментного интервала, I – значение межсегментного интервала, для которого установлено наблюдаемое получателем значение межсегментного интервала P, (I) — функция ускорения, Io – значение межсегментного интервала, соответствующего отсутствию перегрузки в сети.

Функция ускорения определяется формулой (15).

где C – коэффициент, соответствующий максимальному допустимому приросту скорости. Этот коэффициент можно установить равным оценке пропускной способности сети. Чтобы C соответствовало максимальному приросту скорости, для I > 1 следует установить (I) = C. Для значений I < функция (I), выраженная формулой (15), делает прирост скорости передачи данных обратно пропорциональным квадратному корню скорости, что позволяет уменьшать разность скоростей при совершении двумя каналами ускорения, иметь возможность достаточно быстрого ускорения при появлении доступной пропускной способности и поддержания скорости передачи данных, близкой к оптимальной при незначительной заполненности очереди маршрутизатора.

В разделе 3 второй главы рассмотрены вопросы совместимости TCP TIPS с TCP, приведены варианты представления полей TI и PS в заголовке протокола. Описан алгоритм, позволяющий на этапе установки соединения определить наличие поддержки TCP TIPS у другой стороны соединения и в случае ее отсутствия переключиться к использованию произвольного варианта TCP, не прерывая установку соединения. Раздел 4 второй главы рассматривает направления дальнейших исследований, которые могут быть проведены для улучшения алгоритма, применяемого в TCP TIPS.

В главе 3 описана реализация протокола для среды сетевого моделирования ns-2, рассмотрены вопросы его реализации в сетевой подсистеме ОС Linux. В разделе 1 главы 3 рассмотрена реализация TCP TIPS, представленная в виде расширения портированной ранее Дэвидом Веем в ns-2 части сетевой подсистемы ОС Linux. Благодаря такой реализации, имеется возможность провести модельные испытания TCP TIPS и ряда модификаций TCP в рамках единой надежной среды моделирования.

К тому же реализацию TCP TIPS для ns-2 в силу ее специфики можно рассматривать как базу реализации данного протокола для ОС Linux. Более подробно вопросы реализации для ОС Linux рассмотрены в разделе 2 главы 3. В частности, рассматриваются вопросы вычисления интервалов времени, диспетчеризации сегментов, реализации программно-аппаратных оптимизаций, схожих с применяемыми в LRO, TSO, возможность использования NAPI.

В главе 4 приведены результаты модельных экспериментов, их анализ и сравнение характеристик, показанных TCP TIPS, TCP и рядом модификаций TCP.

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

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

В разделе 1 четвертой главы приведены результаты первой группы экспериментов, которые показывают, что поведение TCP TIPS в точности соответствует ожидаемому, протокол использует более 90% пропускной способности сети (в среднем 97-98% при размере буферов, не меньших BDP), увеличение размеров буферов не приводит к росту задержек при передаче данных (наблюдаемых с помощью измерения RTT). По значению полезной

TCP TIPS

рассмотренных модификаций TCP (показывает, в частности, результаты, в среднем на 10-20% превышающие продемонстрированные TCP NewReno).

TCP TIPS показывает неплохое значение коэффициента справедливости разделения ресурсов (0,875 — 0,97 для 10 потоков), определяемого по предложенной Lain и др.1 формуле где xi – доля пропускной способности i-го соединения, n — число соединений. Этот коэффициент определяет, насколько различаются доли пропускной способности сети, полученные каждым соединением. Для n соединений он принимает непрерывные значения в диапазоне от 1/n до 1, где 1/n достигается, если вся пропускная способность была получена одним соединением, а 1 достигается, если все соединения получили равную долю пропускной способности.

В разделе 2 четвертой главы приведены результаты экспериментов в Lain R., Chiu D. M., Hawe W., A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems, Technical Report, Digital Equipment Corporation, DEC-TR-301, ненадежной сети. Эксперименты показали, что TCP TIPS достигает лучших показателей использования пропускной способности сети, чем TCP NewReno, при вероятности ошибки больше, чем 10-6, чем TCP Veno, при вероятности ошибки больше, чем 10-6-10-5, чем TCP Westwood+, при вероятности ошибки больше 0,0001.

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

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

Вторая группа экспериментов демонстрирует превосходство проактивного алгоритма борьбы с перегрузкой, примененного в TCP TIPS, по сравнению с алгоритмом, использующим RTT (на примере TCP Vegas).

В разделе 5 четвертой главы приведены эксперименты по передаче данных в сети, периодически изменяющей маршрут следования пакетов. В первом эксперименте при изменении маршрута менялась пропускная способность сети, во втором — задержка передачи данных. Эксперименты показали, что TCP TIPS хорошо адаптируется к подобным изменениям.

Заключение В данной работе приведено описание нового транспортного протокола TCP TIPS, основанного на TCP, но отличающегося от него в ряде ключевых аспектов. Как и ARTCP, TCP TIPS осуществляет отправку данных сегментами, разделенными промежутками времени. TCP TIPS использует значения межсегментных интервалов времени, наблюдаемые получателем, для определения перегрузки. Построенная на анализе результатов данных измерений проактивная схема борьбы с перегрузкой позволяет добиться низких показателей средней длины очередей маршрутизаторов, что приводит в случае чрезмерно больших размеров очередей к существенному снижению задержек при передаче данных. Также такая схема дает возможность избежать проблем, характерных для проактивных алгоритмов борьбы с перегрузкой, использующих такие показатели как RTT, как то: неверная индикация перегрузки при наличии перегрузки в обратном направлении передачи данных и неэффективное использование пропускной способности сети в сетях с динамической маршрутизацией, приводящей к периодическим изменениям RTT. Разделение логики управления потоком данных и коррекции ошибок позволяет добиться высокой эффективности работы протокола в сетях с большим количеством потерь.

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

Помимо подробного описания алгоритма протокола и формата его заголовка, описана реализация TCP TIPS на C++ для среды моделирования сетей ns-2. Эта реализация приведена как расширение класса LinuxTcpAgent, представляющего собой портирование части сетевого стека Linux в ns-2, поэтому может рассматриваться как основа для реализации поддержки протокола в ОС Linux. Также в работе рассмотрены аспекты практической реализации протокола, возможность аппаратной реализации его частей высокоскоростных сетях.

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

Результаты модельных экспериментов показывают превосходство TCP TIPS над рядом модификаций TCP в условиях изолированного использования, особенно в ненадежных сетях и сетях с динамически меняющимися характеристиками. Также TCP TIPS показал себя как протокол, способный быстро и эффективно уступать требующуюся долю пропускной способности сети протоколам, использующим фиксированную скорость передачи данных, а также быстро продолжать использовать эту долю пропускной способности после ее освобождения. Данная особенность TCP TIPS является одним из ключевых требований, выдвинутых автором работы к разрабатываемому протоколу. Ее наличие позволяет широко применять TCP TIPS в сетях, использующихся для передачи данных реального времени, чувствительных к росту задержек (например, VoIP), в качестве эффективного средства для передачи данных, использующего доступную часть канала и не приводящего к деградации качества работы высокоприоритетных потоков.

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

1. Алексеев И.В., Меркулов С.А., Сивов А.А. Аспекты практической реализации протокола ARTCP на ядре Linux 2.6 // Моделирование и анализ информационных систем. Том 17, № 2, с. 144-149, Ярославль:

Яросл. гос. ун-т, 2010.

2. Сивов А.А. Формат пакета ARTCP. Особенности формирования и обработки заголовков ARTCP в сетевой подсистеме ОС Linux 2.6 // Моделирование и анализ информационных систем. Том 18, № 2, с. 129Ярославль: Яросл. гос. ун-т, 2011.

3. Сивов А.А. TCP TIPS: транспортный протокол для ненадежных сетей, передающих чувствительные к задержкам данные // Моделирование и анализ информационных систем. Том 19, №5, с. 142-151, Ярославль:

Яросл. гос. ун-т, 2012.

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

4. Сивов А.А. О росте задержек при передаче данных в коммуникационных сетях // Всероссийский конкурс научно-исследовательских работ студентов и аспирантов в области информатики и информационных технологий, сб. науч. работ в 3 т., том 2, с. 292-295, Белгород: ИД «Белгород», 2012.

5. Сивов А. А. Проактивная схема борьбы с перегрузкой в сети для транспортного протокола // материалы III Международной заочной научно-практической конференции «Научная дискуссия: вопросы физики, математики, информатики», с. 116-128, Москва: Изд. «Международный центр науки и образования», 2012.

6. Сивов А. А. Проактивная схема борьбы с перегрузкой в транспортном протоколе на основе оценки доступной пропускной способности сети // материалы VIII Международной научно-практической конференции «Современное состояние естественных и технических наук», с. 108-118, Москва: Спутник+, 2012.

7. Sivov A., The Bufferbloat Problem and TCP: Fighting with Congestion and Latency // Proceedings of the 6th Spring/Summer Young Researchers’ Colloquium on Software Engineering SYRCoSE 2012, pp. 109-114, Perm, 2012.

8. Sivov A., Sokolov V., The ARTCP Header Structure, Computation and Processing in the Network Subsystem of Linux Kernel // Proceedings of the 5th Spring/Summer Young Researchers’ Colloquium on Software Engineering SYRCoSE 2011, pp. 31-35, Yekaterinburg, 2011.

9. Сивов А. А. Свидетельство о государственной регистрации программы для ЭВМ №2013611466 «Модуль протокола TCP TIPS для среды ns-2» от 21 января 2013 г.