Адаптивная система управления потоком для транспортного протокола в сетях с коммутацией пакетов

Однако применение алгоритма RED в маршрутизаторах усложняет их и увеличивает их стоимость.

1.9.3. Альтернативные схемы управления потоком

1.9.3.1. TCP VEGAS

Vegas представляет собой улучшенную реализацию протокола TCP по сравнению с распространенными реализациями Tahoe и Reno. Улучшения, предложенные в системе Vegas

[14, 15], затрагивают в основном механизм быстрой ретрансляции. В алгоритме Vegas используется более точный способ определения необходимости быстрой ретрансляции потерянных сегментов. Этот алгоритм использует значения временной метки в заголовке сегментов.

Таким образом, Vegas лучше, чем TCP, реагирует на ситуации в которых происходит потеря более чем одного сегмента в пределах окна, и с которыми не может эффективно бороться стандартный механизм ускоренной ретрансляции [19, 20, 21]. Также в рамках этого механизма Vegas более точно управляет размером окна в процессе ретрансляции. Для реализации контроля перегрузки алгоритм Vegas сохраняет значение минимального RTT в переменной BaseRTT=min(BaseRTT, RTT). Ожидаемое значение пропускной способности определяется по формуле Expected=размер_окна/BaseRTT. Далее, реальная пропускная способность периодически вычисляется как количество байт переданных с момента отправки определенного сегмента и до прихода его подтверждения. Разность реальной и ожидаемой пропускной способности определяет выбор режима линейного увеличения или уменьшения окна.

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

1.9.3.2. TRUMP

Данный механизм разработан в докторской диссертации В.К. Тумей [22] и в него входит не только спецификация транспортного протокола, но и целая система управления потоком на сетевом уровне. Эта система включает в себя механизм измерения загрузки узлов с явной реверсивной обратной связью и собственный формат данных. Интересным аспектом системы TRUMP является то, что скорость отправки данных в сеть регулируется не скользящим окном, а значением разрешенной скорости, задаваемым сетевыми устройствами. К недостаткам системы нужно отнести тот факт, что системы с явной передачей контрольной информации существовали и ранее [23, 24, 25]. Попытки реально внедрить такие системы для сети Интернет не имели успеха, поскольку это потребовало бы введение дополнительных функций маршрутизаторов, в то время как TRUMP предусматривает не только существенное изменение сетевых устройств, но и полное отсутствие совместимости с архитектурой TCP/IP.

1.9.3.3. PP (Packet Pair Flow Control)

Управление потоком по методу Packet Pair Flow Control [26] представляет собой оригинальную идею измерения доступной пропускной способности сети. Схема предназначена для сетей с виртуальными каналами, которые изолируют транспортные потоки при помощи диспетчера квотированного обслуживания (ДКО) очередей [27, 28, 29]. Мотивация для создания такой схемы управления потоками в том, что предоставление интегрированных сервисов становится доминирующим направлением в современной сетевой парадигме. Согласно ей сети должны одновременно обслуживать стабильные потоки с постоянной скоростью передачи данных одновременно с потоками, работа которых характеризуется всплесками и неравномерностью. Первый тип обменов должен получать обслуживание от сети с гарантированным качеством, а второй тип трафика использовать оставшиеся ресурсы. Это основная концепция построения сетей с интеграцией сервисов [30]. Для ее реализации, межсетевые устройства должны применять один из алгоритмов равноправного обслуживания очередей. Как правило это алгоритм взвешенной равноправной диспетчеризации WFQ [28].

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

Алгоритм PP не подходит для использования в сетях TCP/IP, поскольку в таких сетях отсутствует логическая изоляция потоков на сетевом уровне. Однако PP вполне может найти применение в сетях ATM, при наличии раздельной буферизации каждого из виртуальных каналов.

1.9.3.4. NETBLT

Протокол NETBLT [33, 34] разработан с цель предоставления пользователю сервиса аналогичного сервису протокола TCP, а именно надежной передачи большого объема информации с подтверждениями и контролем скорости потока. В протоколе NETBLT представлено несколько принципиально новых идей.

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

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

Таким образом, протокол NETBLT способен обеспечить хорошие результаты при работе по каналам, характеризующимся большим значением RTT*BW. Однако NETBLT не свободен и от недостатков присущих TCP, например оба протокола интерпретируют потерю пакета как признак перегрузки, что неверно в общем случае.

1.9.3.5. Tri-S

Алгоритм Slow Start and Search (Tri-S) [35] основан на механизме замедленного старта протокола TCP. Авторы проанализировали недостатки замедленного старта и попытались устранить неприемлемо высокую амплитуду осцилляций размера окна, которая приводит к большому числу потерь и значительному увеличению компонента задержки.

По результатам моделирования схема Tri-S позволяет улучшить показатель справедливости деления ПС по сравнению с TCP. Однако выбор предельных значений оказывает сильнейшее влияние на стабильность системы. Кроме того, как и стандартный TCP, схема Tri-S интерпретирует потерю пакета как признак перегрузки.

1.9.3.6. DUAL

Данный метод был предложен как способ устранения проблем с осцилляцией окна, наблюдаемых с алгоритмом замедленного старта [36]. DUAL использует изменение измеряемого RTT вместе с отслеживанием потерь пакетов для определения перегрузки.

1.9.3.7. Выводы

Каждый из этих методов обладает определенными недостатками и не применяется в стандартных протоколах. Главный недостаток Vegas, Tri-S, DUAL в том, что в них используется протокол TCP, который реагирует на потерю сегмента снижением скорости, а в отсутствии потерь линейно увеличивает нагрузку на сеть, приводя к переполнению буферов. Схема TRUMP предполагает расширение функциональности маршрутизаторов механизмом, уведомляющим источники о перегрузке в явном виде, что означает отход от парадигмы сетей с пакетной коммутацией. PP предлагает эффективный способ измерения загрузки сети, однако неприменимый для TCP/IP, поскольку предполагает работу в сети с виртуальными каналами на сетевом уровне.

1.9.4. Принципы AIMD и STA

Большинство алгоритмов управления потоками различаются способом определения наступления состояния перегрузки и реагируют на изменения состояния сети путем аддитивного (линейного) увеличения нагрузки и мультипликативного сброса, в случае определения наступления перегрузки. В литературе такой подход получил название Addititve Increase and Multiplicative Decrease (AIMD). Обоснование применения принципа AIMD изложены в работе [2].

В случае отсутствия перегрузки, сеть никак не сообщает соединениям о наличии дополнительных ресурсов, в связи с этим, в отсутствие сигналов о перегрузке, соединения должны увеличивать нагрузку, до тех пор, пока потеря пакет не сообщит о начале перегрузки. Экспоненциальный рост всегда приводит к новой перегрузке, поэтому автор [2,44, 45] рекомендует линейный рост или аддитивное увеличение.

Глава 1. Постановка задачи

1.1. Недостатки протокола TCP

К наиболее существенным недостаткам протокола TCP в области управления потоками относится следующее:

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

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

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

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

Поскольку недостатки TCP широко известны, то множество работ было посвящено созданию отдельного транспортного протокола для асимметричных инфраструктур [51] или беспроводных сетей [47, 48, 49, 50]. Большинство предлагаемых протоколов не являются совместимыми с TCP и требуют наличия агентов-посредников транспортного уровня. Тем самым нарушается основной постулат Интернет заключающийся в том, что сеть должна обеспечивать беспрепятственную связь на транспортном уровне между непосредственными участниками обмена. Также излишне усложняется вся структура сети.

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

1.2. Цель работы

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

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

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

1.3. Формальная модель системы

Формализуем модель на которой будем изучать протокол ARTCP. Имеется сеть, в топологическую схему которой входят несколько узлов, два маршрутизатора и набор каналов соединяющих узлы (рис. 16). На каждом узле исполняется объект протокола ARTCP. Узлы объединены в две локальные вычислительные сети (ЛВС), каждая из которых подключена к одному маршрутизатору. Маршрутизаторы связывают локальные сети, передавая трафик по каналу с малой ПС и большим значением задержки.

Каждый из узлов в одной из ЛВС отправляет сегменты с заданным межсегментным интервалом, который и определяет скорость передачи. Эта скорость задается алгоритмом управления потоком ARTCP. Предполагается, что источники потоков всегда имеют информацию для отправки. Источники и приемники трафика находятся в разных ЛВС. Приемники трафика ARTCP отправляют подтверждения в противоположном направлении в виде сегментов, не содержащих данных.

Задача маршрутизатора в том, чтобы осуществлять передачу сегмента по адресу получателя в его заголовке. В буфере маршрутизатора R1 организуется FIFO очередь сегментов, которые отправляются далее к маршрутизатору R2. Очередь имеет конечную длину. Сегмент, поступающий на выходной интерфейс, помещается в очередь, если она может вместить этот сегмент, иначе сегмент теряется. Очередь маршрутизатора R1 обслуживается со скоростью канала, соединяющего маршрутизаторы.

Рис. 16. Формальная модель исследуемой сети. Стрелками указано направление передачи данных.

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

1.4. Основные характеристики протокола

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

1. Относительное число потерь сегментов (отношение числа потерянных к общему числу отправленных сегментов)

2. Коэффициент использования пропускной способности каналов

U ? число _ принятых _ битов (скорость _ канала ) ? время

возможному их числу).

(отношение числа успешно принятых битов к максимально

3. Коэффициент равноправия разделения ресурсов

n

F ? (?b )2

?1

4. Средняя длина очереди Q в маршрутизаторе R1.

Сравнение ARTCP и TCP производится по этим основным характеристикам.

Приведенные выше характеристики протокола являются стандартными и используются во многих исследованиях протоколов [73].

1.5. Сеть как самоорганизующаяся система

Определение самоорганизующейся системы в смысле Г. Хакена следующее: система с большим числом степеней свободы, под воздействием сложных внутренних сил, переходящая в состояние с существенно меньшим числом степеней свободы: несколькими параметрами порядка, называется самоорганизующейся [101]. Хаотическое поведение системы на уровне отдельных компонентов приводит к детерминированному поведению ее средних величин.

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

Глава 2. Алгоритм ARTCP

Предлагаемый в данной работе новый протокол Adaptive Rate Transmission Control Protocol (ARTCP) заимствует некоторые механизмы от протокола TCP. В ARTCP полностью пересмотрен алгоритм управления потоком, который и отличает его от TCP. Вместе с тем, предлагаемый протокол может обеспечивать совместимость с TCP.

2.1. Аспекты новизны протокола ARTCP

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

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

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

2.2. Эвристика в основе алгоритма ARTCP

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

Поэтому в этой работе было решено создать новый алгоритм транспортного протокола, остающийся, однако, полностью совместимым с архитектурой TCP/IP.

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

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

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

2.4. Формат сообщения

Формат сообщений используемых ARTCP может в точности совпадать с форматом пакета TCP (рис. 8). Стандарт TCP [4] предусматривает наличие дополнительных полей в заголовке сегмента между стандартным заголовком и полем данных. ARTCP может передавать дополнительную информацию в этих полях, что будет гарантировать совместимость с TCP. Всего протокол ARTCP требует использования лишь двух новых полей: значения предыдущего порядкового номера “PS” в направлении от отправителя к получателю и значения скважности “TI” в направлении от получателя к отправителю. Значение “TI” можно передавать в виде опции временной метки [6], а значение “TI” требует поля, позволяющего поместить порядковый номер сегмента.

2.5. Структурная схема ARTCP

В протоколе ARTCP полностью переработаны все механизмы управления потоком. Механизм коррекции ошибок передачи в ARTCP не влияет на скорость передачи. От TCP сохранены оконный механизм для управления загрузкой получателя, алгоритмы определения RTT и установки таймера ТПП. Признаком потери сегмента служит срабатывание ТПП или приход двух последовательных подтверждений одного сегмента. Алгоритм управленияскоростью включает в себя: функции диспетчеризации сегментов, измерения скорости и адаптации скорости (рис. 17). Далее рассмотрим эти функции подробно.

Рис. 17. Функциональная схема механизма управления потоком ARTCP. Жирная стрелка вверху обозначает направление передачи данных. Более тонкие стрелки: направление передачи управляющей информации.

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

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

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

2.5.1. Диспетчеризация сегментов

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

Рис. 18. Диспетчеризация сегментов и измерение скорости потока алгоритмом ARTCP.

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

2.5.2. Измерение скорости

Очевидно, что скорость приема потока получателем не может быть выше скорости обслуживания потока на участке с наименьшей ПС, через который проходит соединение. Таким образом, зная скорость прибытия потока к получателю, можно определить доступную пропускную способность сети. Для корректного измерения скорости необходимо не учитывать выпавшие из потока, т.е. потерянные сегменты, а также сегменты, доставляемые сетью в измененном порядке. Для выполнения этого условия в поле “PS” каждого отправляемого сегмента записывается порядковый номер (или смещение) от предыдущего сегмента.

2.5.3. Функция адаптации

Описание алгоритма работы функции адаптации, непосредственно осуществляющего управление потоком ARTCP, было дано в работах [52, 53, 54, 76].

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

Рис. 19. Диаграмма режимов алгоритма адаптации протокола ARTCP. Штрихованные линии обозначают возможные переходы в состояние остановки системы.

Работа ARTCP начинается с режима быстрого увеличения скорости, аналогичной механизму замедленного старта стандартного TCP, для максимально быстрого достижения соединением верхнего предела доступной пропускной способности. После того, как верхний предел достигнут, алгоритм ARTCP переходит в режим точной настройки, в течение которой удерживает скорость на уровне доступной ПС. В случае определения уменьшения доступной ПС, ARTCP совершает мультипликативное снижение скорости, которое в случае продолжительного состояния перегрузки продолжается экспоненциально. Итак, адаптация скорости передачи потока протоколом ARTCP происходит в пяти режимах (рис. 19).

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

Режим восстановления (REC) имеет целью, линейно увеличивая скорость, довести ее до уже известного значения ПС канала: Re (t) , компенсируя возникшую в режиме SS перегрузку.

Режим тонкой настройки (FT) следует за режимом REC, в режиме FT скорость отправки данных медленно подстраивается под ПС канала. Отношение коэффициентов speedup и slowdown в состоянии FT определяет вероятность снижения или повышения скорости на каждом шаге. Коэффициент speedup, отвечающий за повышение скорости обратно пропорционален скорости данного соединения. Коэффициент slowdown, отвечающий за снижение скорости, пропорционален отношению измеряемого RTT к минимальному значению RTT. Значение speedup больше при меньших значениях Rs (t) , что дает медленным соединениям преимущество для получения доступа к большей относительной доле ПС. Значение slowdown одинаково для всех соединений и растет при росте RTT. Таким образом, вероятность повышения скорости для медленных соединений больше, а вероятность снижения скорости одинакова для всех соединений. Выход из режима FT происходит в случае скачкообразного изменения измеряемого RTT.

Отношение speedup/slowdown определяет знак отклонения мгновенного значения скорости от среднего. Если speedup>slowdown то отклонение от среднего значения для мгновенного значения скорости будет положительным, т.е. скорость потока будет увеличиваться. В случае speedup<slowdown скорость потока будет снижаться. Также, в состоянии FT максимальное отклонение мгновенного значения скорости отправки пакетов от среднего за предыдущий период, согласно формуле (27), пропорционально среднему значению скорости. В связи с этим поток, совершая переход 4 в состоянии FT при большем значении оценки доступной ПС, приспосабливается к небольшим изменениям ПС более интенсивно.

Условием перехода из FT в режим мультипликативного сброса MD2 (переход 6) является:

ERTT ? K ? (FT max RTT ? min ERTT ) (28)

Режим мультипликативного сброса (MD2) необходим для быстрого снижения скорости при условии резкого роста RTT:

midpoint i ? midpoint i ?1 ? MDFACTOR (29)

После этого протокол переходит в состояние FT, реализуя переход 7. В том случае, если условие (28) продолжает оставаться истинным, то мультипликативное уменьшение продолжается, поскольку последовательность переходов 6 - 7 реализуется неоднократно, выражаясь в экспоненциальном уменьшении скорости передачи данных.

Завершение работы протокола может произойти из любого состояния {SS, REC, FT} - переходы (8, 9, 10).

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

Рис. 21. Ожидаемое поведение алгоритма управления скоростью потока (зависимость скорости от времени). Значения t в точках A,B,C обозначают моменты перехода в новый режим.

2.6. Совместимость с TCP

Система, поддерживающая ARTCP, может быть также совместима с TCP. Для этого, инициатор соединения, поддерживающий ARTCP, помещает в заголовке синхронизирующего пакета опцию “PS”.

Наличие поля “PS” в заголовке SYN пакета должно включать механизм ARTCP получателя. Если такая возможность имеется, то получатель включает в сегмент SYN-ACK поле “TI”, если нет, то отсутствие опции “TI” в ответе получателя отключает механизм ARTCP у инициатора и дальнейший обмен происходит по протоколу TCP. Если же опция “TI” присутствует в ответе, то инициатор уверен, что и получатель задействовал механизм ARTCP.

2.7. Сравнение ARTCP и TCP на основе анализа алгоритма

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

Теорема 2: Протокол ARTCP не создает потерь сегментов, если

Qmax

R

е , где

Qmax - максимальная длина очереди, е - предельное значение, используемое алгоритмом ARTCP, а R - скорость канала.

Доказательство:

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

Если D сумма задержек передачи в каналах на пути от отправителя к получателю, то в предположении, что каналы в системе симметричны и трафик передается лишь в одном направлении, минимальное время minRTT определяется как 2D. В случае если средняя скорость отправки потока RS превышает скорость R канала, обслуживающего очередь, возникает очередь сегментов в маршрутизаторе. Появление очереди длины Q приведет к увеличению времени RTT на величину Q/R. Однако для ARTCP, если разность RTT-minRTT превышает некоторое предельное значение е , вероятность снижения скорости отправки потока RS станет отличной от нуля и скорость потока будет снижаться, пока значение разрешенного превышения RTT над minRTT не станет ниже предельного значения. Таким образом, выполняется неравенство: Q < е ? R . Выбирая достаточно малое значение е , алгоритм ARTCP гарантирует, что длина очереди не превысит определенного значения, меньшего, чем максимальная длина очереди Q ? Qmax . Для выполнения этого, необходимо выбрать е , так, чтобы е ? Qmax . Следовательно, при таком выборе предельного значения, R отсутствие потерь сегментов при работе ARTCP гарантировано.

Следствие из теоремы 2: при числе потоков большем 1, протокол ARTCP в отличие от TCP, может быть настроен так, чтобы вообще не создавать потерь сегментов.

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

Протокол ARTCP в отличие от TCP не снижает скорость передачи потока при возникновении потери сегмента. Потерянные данные ретранслируются, не оказывая влияния на скорость передачи. Вследствие этого, потери сегментов не оказывают влияния на скорость потока ARTCP.

Сказанное выше можно сформулировать в следующем виде:

Свойство: В отличие от TCP, протокол ARTCP не чувствителен к потерям сегментов.

2.8. Направления дальнейшего развития ARTCP

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

2.8.1. Асимметричные системы

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

Для использования ARTCP в таких системах необходимо уменьшить частоту подтверждений. Поскольку искусственная задержка подтверждений вызовет увеличение задержки в петле обратной связи, то, измерение задержки передачи сегментов нужно также связать с получателем. Поскольку трудно добиться хорошей синхронизации системных часов получателя и отправителя, то получатель может лишь замечать изменение времени передачи сегментов, если отправитель использует стандартное поле временной метки [6]. Если разность значений метки в потоке и системных часов получателя изменяется, значит изменяется и абсолютное значение задержки. В этом случае получатель должен увеличить частоту подтверждений, чтобы отправитель мог среагировать на изменение нагрузки в сети. Когда значения скорости прибытия потока и задержки передачи не меняются, частота подтверждений может быть снова уменьшена.

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

2.8.2. Соединения с различными RTT

Для соединений, обладающих различным временем RTT, из-за различий длин их маршрутов, среднее значение коэффициента F ограничивается некоторым числом, меньшим

1, как показано в работах [80, 81, 82, 83]. Это верно как для ARTCP, так и для TCP. Чтобы достичь равноправия разделения ПС между ARTCP потоками с разной длиной маршрута, необходимо устранить зависимость коэффициента speedup от минимального времени RTT. Этого результата можно достичь путем модификации алгоритма адаптации таким образом, чтобы в режиме FT полностью отказаться от использования измеренного RTT как индикатора перегрузки, используя лишь значения межсегментных интервалов потока.

Глава 3. Имитационная модель

Для исследования возможностей протокола и отработки его механизмов была разработана программная имитационная модель самого протокола и сетевых компонентов, в среде которых должен функционировать протокол ARTCP. Модель представляет собой набор компонентов имитирующих реальные объекты в составе сети и объекты протоколов ARTCP и CBR (Constant Bit Rate). Изучаемая сеть может иметь топологическую схему достаточно большой сложности, которая строится из необходимого числа экземпляров имеющихся классов.

Основными способами позволяющими исследовать и верифицировать сложные сетевые протоколы являются стенды для тестирования (экспериментальные сети), программные эмуляторы и системы автоматизированной верификации. Верификацию набора процедурных правил протокола можно осуществлять с помощью программного перебора состояний конечного автомата представляющего протокол [56, 57, 58], например, в интерпретаторе языка PROMELA, таком как SPIN [3]. Однако верификация набора процедурных правил, и изучение эффективности протокола преследуют различные цели и, соответственно, для них применяются различные инструменты. Верификация протокола означает применение к его набору процедурных правил формального метода, который позволяет доказать, что этот набор или моделирующая его система конечных автоматов (с обменом данными) полна, не содержит недостижимых состояний, свободна от статических и динамических блокировок. Верификация протокола не ставит задачей даже определение количественных характеристик его эффективности, с точки зрения верификации важно лишь то, что прогрессивный обмен данными вообще происходит. Вследствие этого методы верификации построены на полном или частичном анализе доступных состояний КА, представляющего протокол. Для систем с большим числом состояний ( ? 105 ) верификация основанная на полном анализе затруднена на практике.

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

Одним из наиболее мощных эмуляторов протоколов по своим функциональным возможностям является программный комплекс NS (Network Simulator) входящий в состав системы VINT (Virtual Internetwork Testbed) [59, 60, 61]. Однако эта система вследствие крайней обширности области применения является также очень требовательной к вычислительным ресурсам и не дает возможности эффективно работать с диспетчеризацией на уровне сегментов, поэтому для моделирования протокола ARTCP использовалось программное обеспечение собственной разработки. Для построения данной программной модели (ПМ) были использованы методы объектной разработки и реализация на языке C++ [62, 63] в среде Digital UNIX. Далее мы рассматриваем формат сообщения, используемый в модели, иерархию и реализацию ее основных классов.

3.1. Формат сообщения

Сегменты протоколов моделируется следующей структурой данных.

struct artcp_segment_s {

int src, dst, port;

// адрес отправителя, получателя, порт назначения

long int seq, psn;

// порядковый номер сегмента, смещение от предыдущего (поле PS)

double psk;

// скорость потока, при получении этого сегмента (поле TI)

long int rcv_wnd;

// окно объявленное получателем

long int ack_trig, ack;

// порядковый номер сегмента вызвавшего это подтверждение, номер

// подтверждения

long int syn_ack;

// подтверждаемый порядковый номер SYN-сегмента

unsigned char flags;

// управляющие флаги

long int id;

// уникальный в модели номер сегмента

};

Новые сегменты создаются внутри объектов протоколов ARTCP или CBR. Все объекты топологии передают друг другу указатель на область памяти, содержащую соответствующий сегмент, вместо копирования реальных данных. Кроме того, размеры заголовка сегмента и поля полезной нагрузки задаются в самой структуре данных, и все объекты определяют размер сегмента, интерпретируя значения этих полей. Поскольку ссылка на объект может одновременно содержаться во всех объектах, где реализована буферизация: ARTCP, link, interface, то во избежание конфликтов счетчик ссылок хранит количество объектов, в буферах которых находится ссылка на данный сегмент. Освобождение области памяти, содержащей сегмент, разрешено только в случае обнуления счетчика. За исключением полей “TI” и “PS” и служебных полей link, id, все остальные поля сегмента соответствуют полям стандартного TCP заголовка.

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

3.2. Объектная структура ПМ

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

? Объект протокола ARTCP

? Объект протокола CBR

? Конечная система (host)

? Симплексный канал (link)

? Маршрутизатор (router)

? Интерфейс (interface)



Рис. 22. Иерархия объектов модели сети в ПМ. Буквами A, G, P обозначены основные компоненты интерфейсов объектов. Штриховые линии указывают отношение наследования. Сплошные линии - направления вызовов методов для передачи сегментов.

Все классы, описывающие топологические элементы сети: конечная система (host), канал (link), маршрутизатор (router), интерфейс (interface), являются наследниками базового класса element. Интерфейс каждого из этих классов определяется тремя важнейшими компонентами: прием сегмента - accept_packet(), запрос сервиса - get_service(), обработка прерывания - proc_int(). Эти методы являются переопределением виртуальных функций базового класса. Кроме того, каждый производный класс расширен дополнительными специфическими для него методами. Посредством этих элементов интерфейса моделируется передача данных в системе (рис. 22). Каждый из наследников класса element ссылается на элемент, с которым он связан топологически, по указателю на базовый класс.

Экземпляр каждого из приведенных классов использует вызов accept_packet() топологически привязанного к нему объекта для передачи ему сегмента. В зависимости от наличия ресурсов метод вызываемого объекта может принять или не принять сегмент на обслуживание. Метод proc_int() каждого экземпляра вызывается из основной программы для обработки очереди и принятия решения об обслуживании очередного сегмента.

Рис. 23. Пример простейшей топологической схемы 1, состоящей из двух узлов и двух маршртутизаторов.

Объединение элементов сети в топологическую схему осуществляется с помощью вызова специального метода attach_next() для каждого экземпляра всех классов. Например, для организации модели сети по простейшей схеме (рис. 23) требуется набор из 14 объектов (рис. 24).

Рис. 24. Набор взаимодействующих объектов для топологической схемы 1. Закрашенная область обозначает топологические элементы сети (каналы и маршрутизаторы)

3.2.1. Класс link: аспекты реализации

Класс, моделирующий канал, получает значения пропускной способности и задержки передачи при инициализации. Структура данных класса реализуется односвязной динамической очередью, в которую помещаются сегменты, принятые на обслуживание. После начала обслуживания сегмента канал блокирует последующие запросы в течение времени t=S/R, где S - размер сегмента, а R - скорость канала, т.е. времени приема сегмента размера S в канал. В очереди канала сегмент задерживается в течение установленного времени задержки передачи. По истечении этого времени, объект канала вызывает метод accept_packet() следующего объекта в топологической схеме сети. Если следующий объект отказывает в обслуживании сегмента, то этот сегмент отбрасывается. Для моделирования дуплексной связи применяются 2 экземпляра канала. Параметры каналов могут быть различными для моделирования асимметричных систем.

Метод proc_int() всех экземпляров класса link вызывается из главного цикла. Обработка прерывания переводит внутренний счетчик времени и вызывает передачу готового сегмента из канала следующему объекту топологии.

Для моделирования ошибок среды передачи экземпляр класса link может быть инициализирован перегружаемым инициализатором, который помимо параметров скорости и задержки канала получает также параметр соответствующий резидентному15 значению ошибки передачи BER. С вероятностью 1 ? (1 ? BER) S сегмент отбрасывается вместо передачи следующему элементу топологии. Таким образом, можно моделировать спутниковые, радио, сотовые каналы.

3.2.2. Класс router: аспекты реализации

Структура класса router является сложной. В его состав входят несколько экземпляров класса interface. При инициализации класса router ему передаются два параметра: количество интерфейсов и объем буферного пространства (максимальная длина очереди), одинаковый для всех интерфейсов. Объект маршрутизатора создает заданное количество экземпляров класса interface. Указатели на каждый интерфейс располагаются в специальном массиве, проиндексированном по порядку создания интерфейсов. После этого на конкретный интерфейс можно ссылаться как router.interface(Х), где Х - номер нужного интерфейса. Каждый интерфейс при инициализации получает указатель на создавший его объект класса router, по которому он может ссылаться на методы класса router для передачи сегментов в матрицу коммутации (обозначена в схемах как "поле коммутации").

После этого сопоставление адреса назначения сегмента со вторым полем таблицы маршрутизации дает номер выходного интерфейса для данного сегмента. При отсутствии совпадения с записями таблицы маршрутизации, сегмент передается для рассылки всем интерфейсам маршрутизатора, кроме того, с которого он был получен. Полученный от коммутирующей матрицы, сегмент помещается в выходную очередь интерфейса, если свободное пространство в ней Qmax ? Q ? S , в противном случае сегмент отбрасывается. Очередь моделируется списком двойной связности, динамически выстраиваемом в памяти [63].

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

Метод обработки прерывания каждого из интерфейсов вызывается методом обработки прерывания объекта маршрутизатора. Также объекты маршрутизатора и интерфейса снабжены методами для выдачи отчета по текущим параметрам трафика: средняя скорость, счетчики пропущенных/отброшенных сегментов, таблица маршрутизации, средняя длина очереди. Таким образом, объект маршрутизатора моделирует современное межсетевое устройство с не блокирующей коммутационной матрицей и буферизацией на выходе [67]. Возможно также расширение класса маршрутизатора алгоритмами RED и WFQ или CBQ [65, 66].

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

3.2.3. Класс host: аспекты реализации

Класс host имеет в своем составе экземпляр класса ARTCP, моделирующего сам протокол и экземпляр класса CBR, моделирующий протокол передачи данных без подтверждений и управления потоком с постоянной битовой скорости. В каждый момент времени только один из протоколов может быть в активном состоянии.

При отправке сегмента метод get_service() экземпляра класса host вызывается одним из протоколов.

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

В случае отсутствия возможности передать сегмент на канальном уровне, метод get_service() объекта host возвращает отрицательное подтверждение. При инициализации экземпляра класса host он получает сетевой адрес. Отдельно устанавливается сетевой адрес назначения.

В случае приема сегмента от объекта канала, метод accept_packet() передает указатель протоколу определяемому по значению поля port заголовка сегмента. Сегменты, чей адрес назначения не совпадает с адресом данного экземпляра узла, отбрасываются. Метод proc_int() класса host используется для передачи запроса на обработку прерывания объекту активного протокола.

3.2.4. Объект протокола CBR

Протокол постоянной скорости передачи напрямую соответствует реальному режиму передачи данных с постоянной битовой скоростью, например CBR в ATM [68] или (Circuit emulation services) CES [69] в IP сетях. Корректное взаимодействие с таким режимом передачи данных является актуальной задачей любого адаптивного транспортного протокола в современных сетях с интеграцией сервисов [30]. Именно поэтому протокол CBR включен в модель среды исполнения ARTCP. Протокол CBR генерирует сегменты и отправляет их в сеть с предустановленной скоростью R , т.е. временные промежутки между моментами начала последовательных трансляций составляют ф ? S / R . Подтверждения и, следовательно, ретрансляция сегментов и контроль скорости не реализуется протоколом CBR.

3.2.5. Объект протокола ARTCP

Модель ARTCP реализует управление скоростью отправки сегментов посредством механизма скользящего окна и собственно алгоритма ARTCP, коррекцию ошибок передачи не связанную с управлением передачи, быструю ретрансляцию сегментов и стандартную ретрансляцию по срабатыванию ТПП. Основные методы класса ARTCP таковы: Establish() - применяется для начальной синхронизации соединения, getarea() - вычисляет значение области компенсации, accept_packet(), proc_int(), status() - запрашивает результат отправки сегмента узлом. Из них три последние являются открытыми и составляют интерфейс класса. В состав класса ARTCP входят два экземпляра класса Queue, которые реализуют приемный и передающий буфер и методы для манипуляции с ними.

3.2.5.1. Класс Queue

Данный класс реализует схему стандартного управления потоком по методу скользящего окна. Класс содержит динамический список двойной связности, в который записываются указатели на сегменты, поставленные в очередь вместе с экземпляром класса таймера, реализующего ТПП. Методы класса Queue позволяют осуществлять вставку сегмента с сортировкой, сканирование списка, нахождение очередного сегмента готового к передаче. Ретрансляция реализована посредством изменения очередности готовых к отправке сегментов. Взаимодействие очередей с объектом протокола и схема обработки сегментов приведены на рис. 25.