Разработка методики оценки доступной полосы пропускания для организации высокоскоростной передачи данных в телекоммуникационных сетях тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Качан Дмитрий Сергеевич

• Качан Дмитрий Сергеевич
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Качан Дмитрий Сергеевич

Перечень иллюстраций

Перечень таблиц

Введение

1 Альтернативные способы передачи данных с гарантированной доставкой

1.1 Традиционная передача данных с гарантированной доставкой

1.2 Сравнение современных приложений для высокоскоростной передачи данных по сети типа WAN с пропускной способностью в 10 Гбит/с

1.2.1 Топология экспериментальной сети

1.2.2 Исследуемые приложения

2 Сравнение коммерческих приложений для скоростной передачи данных

2.1.1 Выводы к разделу

2.2 Сравнение протоколов для высокоскоростной передачи данных

2.2.1 Результаты экспериментов и сравнение протоколов

2.3 Выводы к главе

3 Активные измерения доступной полосы пропускания

3.1 Основные положения

3.2 Измерения доступной полосы пропускания, основанные на оценке дисперсии пар пакетов

3.3 Измерение доступной полосы пропускания периодической посылкой потоков с постоянной скоростью передачи (PRM) — модель периодических потоков проб

3.3.1 Общие положения

3.3.2 Алгоритм Pathload

3.3.3 Алгоритм Claibrated Pathload

3.4 Выводы к главе

4 Алгоритм Kite и сопутствующие алгоритмы

4.1 Изменение количества тестовых пакетов в зависимости от скорости передачи в ходе итерации

4.2 Коэффициент понижения шага

4.3 Алгоритм измерения Kite

4.4 Алгоритм установки начальной скорости (Adjustment of Initial Rate - AIR)

4.5 Алгоритм возрастающей фазы

4.6 Алгоритм убывающей фазы

4.7 Алгоритм обнаружения малого размера буфера (SBD — small buffer betection)

4.8 Алгоритм анализа состава

4.9 Алгоритм «Отрезания головы»

4.10 Определение прерывания при посылке проб

4.11 Алгоритм «своевременной» посылки данных

4.12 Размер проб

4.13 Замеры времени

4.14 Объединение прерываний при получении проб

4.14.1 Описание явления

4.14.2 Математические модели приёма данных с включённой техникой Interrupt coalescence

4.14.3 Определение использования объединений прерываний на принимающей стороне

4.14.4 Противодействие объединению прерываний при оценке доступной полосы пропускания

4.15 Выводы к главе

5 Программная библиотека ABC (Available Bandwidth Control) для высокоскоростных транспортных протоколов

5.1 Интерфейс

5.2 Необходимые расширения протокола

5.3 Выводы к главе

6 Экспериментальное подтверждение эффективности работы алгоритмов

6.1 Измерения доступной полосы пропускания инструментом Kite в лабораторных условиях

6.1.1 Измерения в сети с джиттером

6.1.2 Оценка доступной полосы пропускания с чередующимися, «узким» и «плотным», каналами

6.1.3 Оценка без искусственно введённого джиттера

6.1.3.1 Эксперименты с сетевыми адаптерами Chelsio

6.1.3.2 Эксперименты с сетевыми адаптерами Intel

6.2 Измерения доступной полосы пропускания в реальной сети инструментом Kite

6.3 Измерения производительности протокола RWTP со встроенной библиотекой ABC

6.4 Выводы к главе

Заключение

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

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

ПРИЛОЖЕНИЕ А

Перечень иллюстраций

Рисунок 1 - Скорость передачи данных FTP via TCP (CUBIC)

Рисунок 2 - Статистика потерь пакетов. 0 - Африка, 1 - Азия, 2 - Европа, 3 - С. Америка,

Океания, 5 - Ю. Америка [24]

Рисунок 3 - Логический вид топологии экспериментальной сети

Рисунок 4 - Физическая топология экспериментальной сети

Рисунок 5 - A) сравнение скоростей передачи данных на сети без потерь

Рисунок 6 - Сравнение скорости передачи данных и загрузки процессора при уровне потерь 0%

Рисунок 7 - Сравнение скорости передачи данных и загрузки процессора при уровне потерь 1%

Рисунок 8 - Сравнение скорости передачи данных и загрузки процессора при уровне потерь 2%

Рисунок 9 - Топология для иллюстрации дисперсии пар пакетов

Рисунок 10 - Дисперсия пакетов при прохождении через сеть с «узким» каналом

Рисунок 11 - Топология для иллюстрации дисперсии пакетов кросс-трафиком

Рисунок 12 - Дисперсия пакетов при прохождении через сеть с «плотным» каналом

Рисунок 13 - Задержки в составе OWD

Рисунок 14 - Дисперсия покетов, иллюстрирующая эффект сжатия

Рисунок 15 - Ошибка измерения при постоянном размере состава

Рисунок 16 - Количество проб в зависимости от скорости передачи данных

Рисунок 17 - Коэффициент понижения шага

Рисунок 18 - Ошибка и время оценки для предложенных схем (22)

Рисунок 19 - Общий алгоритм измерения Kite

Рисунок 20 - UML-диаграмма структуры MeasurementResult

Рисунок 21 - Диаграмма алгоритма установки начальной скорости

Рисунок 22 - Характеристика работы алгоритма AIR в зависимости от размера состава

Рисунок 23 - Диаграмма алгоритма возрастающая фаза

Рисунок 24 - Диаграмма алгоритма убывающей фазы

Рисунок 25 - Задержка в один конец для состава

Рисунок 26 - Алгоритм анализа состава

Рисунок 27 - UML диаграмма структуры MeasurementDetails

Рисунок 28 - Нехарактерное поведение первой группы проб

Рисунок 29 - Межпакетный интервал при посылке

Рисунок 30 - Алгоритм посылки проб с постоянной скоростью

Рисунок 31 - Стиль посылки данных сетевых карт от различных производителей

Рисунок 32 - Случай превышения межпакетного интервала

Рисунок 33 - Характеристика параметров состава при приёме пакетов с объединением

прерываний

Рисунок 34 - Характеристика задержек в один конец в случае

Рисунок 35 - Процесс передачи пакетов при использовании объединения прерываний

Рисунок 36 - Влияние задержек при посылке пакетов на характеристику OWD с объединением

прерываний на принимающем интерфейсе

Рисунок 37 - Топология сети для сбора статистических данных для определения приёма данных

с объединением прерываний

Рисунок 38 - Плотность вероятности MPCT при различных условиях

Рисунок 39 - UML диаграмма интерфейса класса abcSender

Рисунок 40 - Диаграмма статусов библиотеки ABC

Рисунок 41 - UML диаграмма интерфейса ABC на стороне получателя

Рисунок 42 - UML диаграмма структуры Report

Рисунок 43 - Схема взаимодействия ABC и RWTP

Рисунок 44 - Топология экспериментальной сети с обозначением потоков данных

Рисунок 45 - Результаты измерения инструментом Yaz в сети с вариацией задержки

Рисунок 46 - Результаты измерения инструментом Kite в сети с вариацией задержки

Рисунок 47 - Результаты экспериментов для схем:

Рисунок 48 - Измерения Yaz на картах Chelsio, с использованием Jumbo Frames; MTU 9000 байт

Рисунок 49 - Оценки Yaz на картах Chelsio, без использования Jumbo Frames; MTU 1500 байт

Рисунок 50 - Оценки Kite на картах Chelsio, с использованием Jumbo Frames; MTU 9000 байт128 Рисунок 51 - Оценки Kite на картах Chelsio, без использования Jumbo Frames; MTU 1500 байт

Рисунок 52 - Оценки Yaz на картах Intel, с использованием Jumbo Frames; MTU 9000 байт

Рисунок 53 - Измерения Yaz на картах Intel, без использования Jumbo Frames; MTU 1500 байт

Рисунок 54 - Измерения Kite на картах Intel, с использованием Jumbo Frames; MTU 9000 байт

Рисунок 55 - Измерения Kite на картах Intel, без использования Jumbo Frames; MTU 1500 байт

Рисунок 56 - Время передачи данных для RWTP с использованием библиотеки ABC с весами 0.1 и 0.3 и без неё

Перечень таблиц

Таблица 1: Схема эксперимента «узкий» канал перед «плотным»

Таблица 2: Схема эксперимента «плотный» канал перед «узким»

Таблица 3: Ошибки оценок Pathload при объединении прерываний

Таблица 4: Параметры реальных соединений

Таблица 5: Результаты измерения в реальных сетях

Введение

Введение диссертации (часть автореферата) на тему «Разработка методики оценки доступной полосы пропускания для организации высокоскоростной передачи данных в телекоммуникационных сетях»

Актуальность темы

Высокоскоростная или высокоэффективная передача данных

Задача передачи данных между сетевыми узлами возникла почти одновременно с появлением первых ЭВМ. Но представления о быстрой передаче данных по IP-сетям в разное время отличались друг от друга. Это связано преимущественно с тем, что и отношение к объёмам данных претерпевало изменения. На заре компьютерной эры данные измерялись байтами и килобайтами, а мегабайтами — совокупный объем цифровых данных на Земле. К появлению первых IP-сетей эти объёмы увеличились, и их задачей стало обеспечение передачи данных на скоростях, соизмеримых с объёмом передаваемых данных — килобитами и мегабитами в секунду. Одна из первых версий TCP [1] в 1981 году была запущена поверх протокола NCP [2],[3] через технологию IMS [4], где максимальная скорость передачи данных составляла всего 230.4 Кбит\с. Только в 1984 году был представлен экспериментальный Ethernet [5], с помощью которого передача данных достигала 3 Мбит/с. К этому времени уже был анонсирован протокол IP [6]. C этого момента начинается эра межсетевого, компьютерного взаимодействия.

Стремительное развитие цифровой техники увеличивает объёмы данных, с которыми сталкиваются пользователи, что обуславливает необходимость увеличения скорости передачи этих данных. В наше время скорость в несколько десятков мегабит доступна многим, даже на домашних терминалах — например, сжатому видеопотоку в формате FullHD необходимо порядка 10 Мбит/с полосы пропускания. Активно внедряется услуга доставки видео-контента в формате 4k, для чего требуется уже не менее 15 Мбит/с. Такие скорости были немыслимы в домашних условиях всего лишь одно десятилетие назад. В профессиональной среде необходимость в доступной пропускной способности достигает нескольких сотен гигабит в секунду.

Из вышеизложенного ясно, что понятие «высокоскоростная передача данных» имеет неразрывную связь с временным контекстом, в котором оно рассматривается. Так, высокоскоростная передача данных 40 лет назад — это килобиты в секунду; сейчас для большинства случаев — это десятки и сотни мегабит. Не исключено, что через 10 лет контент будет доставляться до терминала пользователя со скоростями, превышающими десятки Гбит/с.

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

Необходимость в эффективной передаче данных

На вопрос о необходимости в эффективной передаче данных хорошо отвечают результаты тестов традиционного инструмента — FTP (File Transfer Protocol) по TCP, представленные на рисунке 1 (стр. 21). Даже имея свободный от постороннего трафика канал (с пропускной способностью 1 Гбит/с, без потерь, но с большой задержкой) он будет занят лишь частично, в зависимости от задержки, т. е. от расстояния между узлами. Производительность становится ещё хуже при наличии потерь в канале. Индустрией диктуется сразу несколько аспектов необходимости в эффективности. Первый из них — экономическая целесообразность. Если предприятие арендует канал с какой-либо пропускной способностью, то оно должно иметь возможность передавать данные с этой скоростью. А приобретение большего объёма сетевых ресурсов только из-за отсутствия возможности заполнить меньшее количество более эффективно — экономически нецелесообразно. Второй аспект — это тот факт, что данные должны быть переданы в течение ограниченного промежутка времени. С учётом того, что рост объёма цифрового контента никогда не будет прекращён, а будет только увеличиваться с каждым годом, логично предположить, что потребности промышленности в увеличении скорости передачи данных также возрастают с течением времени. Более того, появляются такие предприятия, основным бизнесом которых является создание и распространении больших объёмов данных. К примеру, в [7] показывается, как компания Google в 2007 году выполнила задачу по передаче 120 терабайт данных (120-1012байт), собранных при помощи космического телескопа Хаббл. Эта задача была выполнена посредством так называемого «Федексинга» — физического переноса носителей. Это позволило передать данные в течение 24 часов между географически распределенными исследовательскими университетами. Для обеспечения передачи этих данных в течении 24 часов по сети Интернет потребовалась бы средняя скорость передачи более чем в 11 Гбит/с. Подобные соединения существуют, и, значит, в наше время такую задачу можно выполнить простой передачей данных по сети. Однако, учитывая удалённость исследовательских университетов друг от друга, картина передачи данных даже по каналу с пропускной способностью 20 Гбит/с вряд ли отличалась бы от поведения на рисунке 1 (стр. 21).

На выставке CeBIT 2014, проходившей в Ганновере в марте 2014 года, специалисты из IBM на консультации предоставили информацию, что компания в тот момент находилась в поиске решения для скоростной передачи данных. Была поставлена задача по передаче архива

данных, сгенерированных в течение года Большим Адронным Коллайдером. Совокупный объем данных, которые необходимо было передать в США, составлял порядка 1 петабайта. Похожие задачи не разовые, т. к. результаты экспериментов с подобным международным оборудованием, как правило, используются сразу несколькими научными институтами.

В 2013 году институт Макса Планка в Гамбурге оказался не в состоянии работать с данными архива прогнозов погоды, расположенного в Великобритании. Причиной тому было только то, что даже доля этого архива, необходимая исследователям, составляла несколько петабайт.

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

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

Для чего нужна информация о доступной полосе пропускания ?

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

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

Другими словами, этот процесс можно описать как передачу данных между двумя узлами через некий «чёрный ящик»; про который известно лишь, с какой максимальной скоростью он может принимать данные (пропускная способность отправляющего интерфейса) и потенциально отдавать данные (пропускная способность принимающего интерфейса). Всё остальное, в общем случае, можно почерпнуть лишь эмпирическим методом, посылая в сеть данные и анализируя характеристики потока на приёмной стороне, а также сообщения обратной связи на отправляющей. Наиболее используемый транспортный протокол TCP устанавливает основные характеристики передачи в рамках сессии, ориентируясь на Период Кругового Обращения (RTT) и потери в соединении. От RTT, тем или иным образом, зависит размер скользящего окна (congestion window), с помощью которого происходит управление перегрузками. В различных версиях TCP управление перегрузками происходит по-разному. По мере передачи данных, в случае отсутствия потерь, окно плавно увеличивается до тех пор, пока они не будут зафиксированы. Реакцией на это, как правило, является уменьшение этого окна, что ведёт к уменьшению скорости пересылки данных. Другими словами, скорость наращивается до тех пор, пока сеть не будет перегружена, а некоторые данные — потеряны. После этого происходит резкое уменьшение окна, а при отсутствии потерь его плавный рост.

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

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

соединения, оставаясь при этом достаточно «справедливым» (fair) к конкурентным потокам данных в соединении.

В контексте транспортных протоколов тема «справедливости» стоит довольно остро. Так, в сетях общего пользования, где подавляющее большинство данных, которые непременно должны быть доставлены, передаются с помощью TCP, считается невозможным использование других протоколов, если они ведут себя по отношению к TCP «несправедливо». Однако, помимо транспортных протоколов с гарантией доставки, в сети есть много участников, которые передают данные реального времени по UDP. При этом, с нарастающим развитием технологий, требуются большие полосы пропускания для таких приложений. К примеру, видеокамеры, доступные каждому, снимают всё более и более высококачественное видео. Поток таких данных, как правило, ведёт себя «несправедливо», ведь данные должны быть переданы с постоянной скоростью. Количество пользователей, передающих данные подобным образом, растёт; а, значит, количество трафика в сети, которое ведёт себя «несправедливо» по отношению к TCP, увеличивается.

Концепция «справедливости» TCP предполагает, что, если N TCP потоков присутствуют в соединении, то каждый из них должен использовать не более чем 1/N пропускной способности соединения. Уже упомянутая выше реакция TCP на потери в сети делает его очень уязвимым со стороны UDP-потоков реального времени. Другими словами, если в соединении помимо N TCP-потоков присутствует UDP-поток, занимающий половину доступной полосы пропускания, то каждый из потоков будет использовать не более чем 1/(2N) от общей пропускной способности. Кроме этого, концепция не выполняется и самим протоколом TCP. В [9] показано, что TCP-потоки в соединениях с меньшей задержкой RTT ведут себя менее «честно» к потокам, передающим данные на большие расстояния. Кроме этого, в работе [10] описывается, что в высокоскоростных сетях на «честность» потоков TCP влияет также режим обслуживания очередей маршрутизаторами.

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

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

80% соединения агрессивно, а оставшуюся его часть «справедливо». Таким образом, смежные потоки не будут полностью блокированы и смогут передавать данные; в это время высокоскоростной транспорт будет делать то, для чего он был спроектирован — передавать данные быстрее.

Подобные решения будут интересны, если не в сетях общего пользования, то, как минимум, для корпоративного использования. В настоящее время, всё больше компаний с географически распределенными подразделениями приобретают в частное пользование так называемые L2-VPN. В этом случае в распоряжении организации оказываются целые каналы, которые необходимо использовать максимально эффективно. При этом, по 80% полосы пропускания будет передаваться необходимый для корпоративного бизнеса, «тяжёлый», контент; а остальные 20% будут использованы для нормального информационного взаимодействия подразделений.

Анализ доступной полосы пропускания ещё более интересен для приложений с передачей потокового трафика реального времени — к примеру, аудио- или видео-данных. Чем выше качество видео-потока, тем шире полоса пропускания из конца в конец требуется такому приложению. Как правило, подобный трафик передаётся посредством UDP без гарантии доставки. В случае перегрузки сети, при передаче такого трафика, некоторые IP-пакеты теряются безвозвратно, и на приёмной стороне часть данных не будет получена. В случае с видео-потоком, изображение может стать неразборчивым, и могут происходить «замирания». Если перегрузку в сети не устранить, то дальше этим сервисом невозможно будет пользоваться. Такие проблемы решаются, к примеру, снижением качества изображения при обнаружении потерь. Таким образом, приложению требуется меньше полосы пропускания, и перегрузка устраняется.

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

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

Вопросами передачи данных с высокой скоростью и оценкой доступной полосы пропускания занимаются в ряде университетов: Самарском государственном аэрокосмическом университете, Университете Colgate в США, Технологическом институте Джорджии в США, Университете прикладных наук Саксонии-Анхальт, Германия и др.

Значимый вклад в развитие тематики внесли такие исследователи, как C. Dovrolis, J. Sommers, E. Siemens, M. Janin, V. Jacobson, А. Кучерявый, Т. Сулатнов. Кроме этого, выдающийся вклад был сделан Yonghong Gu и Robert Grossman, которые в явном виде ввели в транспортный протокол процедуру измерения доступной полосы пропускания.

В диссертационной работе:

• выполнен сравнительный анализ существующих транспортных протоколов, предназначенных для организации высокоскоростной передачи данных;

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

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

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

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

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

• разработана программная библиотека ABC (Available Bandwidth Control), которая была встроена в высокоэффективный транспортный протокол RWTP для управления перегрузками.

Результаты исследования соответствуют следующим пунктам паспорта научной специальности 05.12.13 «Системы, сети и устройства телекоммуникаций»:

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

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

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

Пункт 4: «Исследование путей совершенствования управления информационными потоками».

А именно: создана программная библиотека ABC (Available Bandwidth Control), предназначенная для оценки доступной полосы пропускания и разработана схема её взаимодействия с алгоритмом управления перегрузками. Библиотека может быть интегрирована в любой транспортный протокол.

Объект, предмет исследования и цель работы

Объектом исследования являются модели и алгоритмы оценки доступной полосы пропускания в IP-сетях.

Предметом исследования является процесс оценки доступной полосы пропускания.

Цель работы и задачи исследования. Целью диссертации является разработка методики оценки доступной полосы пропускания для обеспечения передачи данных со скоростями до 10 Гбит/с и анализ возможности использования данной методики в высокоэффективных транспортных протоколах.

Для достижения поставленной цели в работе определены и решаются следующие задачи:

1. Анализ и экспериментальное сравнение существующих высокоскоростных транспортных протоколов;

2. Анализ существующих методов оценки доступной полосы пропускания соединений из конца в конец;

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

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

для управления перегрузками.

Научная новизна работы

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

2. Разработан алгоритм оценки доступной полосы пропускания, отличающийся возможностью корректного функционирования при использовании объединения прерываний на приёме, позволяющий оценивать доступную полосу пропускания с погрешностью не более 10%. (Применяемые сегодня Pathload и Calibrated Pathload при тех же условиях имеют погрешность до 60%);

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

4. Разработаны алгоритмы, позволяющие увеличить точность оценки доступной полосы пропускания: алгоритм «отрезания головы», способный увеличить точность оценки временных характеристик приёма данных на 50%; алгоритм «своевременной» посылки данных для проведения оценки, предоставляющий возможность снизить зависимость оценки доступной полосы пропускания от непредвиденных задержек отправителя.

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

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

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

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

Программная библиотека ABC (Available Bandwidth Control), предназначенная для оценки доступной полосы пропускания, имеет интуитивный интерфейс для использования, а предложенная в диссертационной работе схема её взаимодействия с алгоритмом управления перегрузками позволит интегрировать её в любой транспортный протокол.

Методы исследования. Для решения поставленных задач использовалось математическое моделирование, а также натурные эксперименты, методы статистического исследования.

Экспериментальная проверка алгоритмов проводилась на реальных соединениях сети Интернет, а также в лабораторных условиях с использованием аппаратных сетевых эмуляторов Apposite Netropy 10G и 10G2. Кроме этого, для тестирования использовался вычислительный кластер ФГБОУ СибГУТИ.

Личное участие автора в получении научных результатов. Основные результаты диссертационного исследования получены автором самостоятельно. В ходе диссертационной работы, автором был самостоятельно разработан алгоритм оценки доступной полосы пропускания в соединении с джиттером и при объединении прерываний на стороне приёмника. Автором были сделаны все аналитические выводы и экспериментальные исследования. Соавторы считают, что результаты научных работ являются неделимыми и вклад каждого соавтора одинаков.

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

1. Оценка доступной полосы пропускания с автоматическим выбором необходимого числа проб и адаптация процесса оценки к высоким значениям джиттера для мултигигабитных скоростей передачи данных в IP-сетях.

2. Оценка доступной полосы пропускания при активной технике объединения прерываний на сетевом интерфейсе приёмной стороны.

3. Критерий использования техники объединения прерываний на приёмной стороне.

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

Внедрение

• Программная библиотека ABC была успешно интегрирована в коммерческий протокол компании Tixel GmBH, Reliable WAN Transfer Protocol (RWTP). Результаты экспериментов, приведённые в главе 5 диссертационной работы, демонстрируют эффективность ин-

тегрального взаимодействия алгоритмов;

• Алгоритмы оценки доступной полосы пропускания, представленные в работе, используются Институтом IMT e.V. Кётен (Германия) для проекта LiCA;

• Предложенные схемы измерения доступной полосы пропускания используются в высокоскоростных транспортных решениях лаборатории Future Intenet Lab Anhalt, таких как протокол RMDT, предоставляющий возможность высокоскоростной передачи данных в режиме «точка—многоточка»;

• Вопросы оценки доступной полосы пропускания для передачи данных включены в учебное пособие «Сетевые технологии высокоскоростной передачи данных» под редакцией Шувалова В.П. Кроме того, представленные в диссертации материалы используются в курсе лекций «Коммуникационные технологии» в Университете прикладных наук Ан-хальт, Кётен, Германия (Anhalt University of Applied Sciences).

Апробация работы

Основные результаты работы докладывались на следующих международных конференциях и форумах: конференция «Телекоммуникационные и вычислительные системы», Москва, 2011 г.; Конференция «Технологии информационного общества», Москва, 2012 г.; Конференция International Conference on Networking and Services, Лиссабон, 2013 г.; Конференция International Conference on Applied Innovations in IT, Кётен, 2013 г.; IV Научно-практическая конференция «Информационно-измерительная техника и технологии», Томск, 2013 г.; Конференция International Conference on Applied Innovations in IT, Кётен, 2014 г.; Future Talk на выставке «CeBIT 2014», Ганновер 2014 г.; Future Talks на выставке «CeBIT 2015», Ганновер 2015 г.;

Список литературы диссертационного исследования кандидат наук Качан Дмитрий Сергеевич, 2016 год

источник

9

получатель

11

12

1.3

Рисунок 9 - Топология для иллюстрации дисперсии пар пакетов

Рассмотрим случай, когда в соединении нет кросс-трафика; буферы в промежуточных устройствах бесконечно большого размера; а, также, сочтём задержку в маршрутизаторах на предоставление сервиса и буферизацию пренебрежительно малой. Тогда взаимодействие пакетов в сети можно представить, см. рисунок 10.

Т:

т1

I

Си = 2С = 2С

Рисунок 10 - Дисперсия пакетов при прохождении через сеть с «узким» каналом

На рисунке пакеты, уходящие от источника, имеют межпакетный интервал времени Т1 и время передачи пакета Т1. Отметим, что время передачи пакета определяется по (3):

С

(3)

где т — время передачи в 1-ом канале пакета размером S бит, при пропускной способности канала С бит/с.

При переходе из канала L1 в канал L2 время передачи пакета изменяется в соответствии с пропускной способностью канала и становится Т2. Ввиду того, что время передачи пакета во втором канале превышает межпакетный интервал Т1, данные будут выходить из буфера с максимально возможной скоростью. Тогда, т2 будет равно Т2. Даже несмотря на это, буфер будет по-

т

стоянно заполняться. При переходе пакетов из канала L2 в канал L3, время передачи вновь становится равным Т1, потому что пропускная способность в L1 и L3 совпадают. Однако, межпакетный интервал не может быть сокращён, а, значит, в L3 он также равен Т2. Таким образом, скорость приёма информации получателем будет меньше, чем скорость отправки информации; за счёт увеличения межпакетного интервала в так называемых, «узких», каналах соединения.

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

ИСТОЧНИК

получатель

Направление исследуемого трафика

--► Направление кросс-трафика

Рисунок 11 - Топология для иллюстрации дисперсии пакетов кросс-трафиком

На рисунке все каналы имеют равную пропускную способность С; которой и определяется, в соответствии с (3), время передачи пакета. Исследуемый трафик делит канал L2 с кросс-трафиком. Скорость передачи данных кросс-трафика, как и скорость передачи исследуемого потока данных, максимальна и равна пропускной способности каналов. В этой ситуации пакеты будут взаимодействовать друг с другом, см. рисунок 12. Пакеты на протяжении всего пути имеют постоянную длительность передачи Ti, определяемую в (3). Межпакетный интервал в канале L1 минимальный и очень близок к Ti, т. е. пакеты выходят один за одним, без паузы между ними. Этот временной интервал используется источником для генерации пакетов. В дальнейшем, будем называть его IpIS (Inter-packet Interval on Sender).

При переходе пакетов из канала L1 в L2 межпакетный интервал исследуемого трафика увеличится на величину длительности пакета кросс-трафика, которая в нашем случае также равна Ti. Это увеличение обусловлено тем, что поступающий на вход канала L2-трафик в 2 раза интенсивнее, чем этот канал может обслужить. В идеальном случае, пакеты будут буферизоваться в маршрутизаторе и, чередуясь, передаваться по каналу. После прохождения канала межпакетный интервал остаётся неизменным, и данные поступают в канал L3. С таким распределением

пакеты поступят к приёмнику. Межпакетный интервал, с которым данные поступают к приёмнику, обозначим IpIR (Inter-packet Interval on Reception).

■ ■ I

L3

Рисунок 12 - Дисперсия пакетов при прохождении через сеть с «плотным» каналом

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

Канал L2, в таком случае, называют «плотным» каналом. Резюмируя, можно сказать, что «узкий» канал соединения — это такой канал, пропускная способность которого наименьшая среди всех каналов, и он, по сути, определяет пропускную способность. «Плотный» канал, в свою очередь, является каналом, доступная полоса пропускания которого минимальная. Он определяет доступную полосу пропускания соединения. «Узкий» и «плотный» каналы могут совпадать, а могут быть распределены физически.

Опираясь на определение «плотного» канала, можно записать формулу для доступной полосы пропускания:

А = min (А1 ,A 2,... ,Ai,... ,AK), (4)

где A — это доступная полоса пропускания соединения; Ai — это доступная полоса пропускания i-го канала.

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

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

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

источник

получатель

1рВ

а1 ^ о*

14

.2 2 Л

с! в

Ш

-задержка распространения

- время обслуживания

- время ожидания в очереди

Рисунок 13 - Задержки в составе OWD

Как изображено на рисунке, от источника к получателю было отправлено два пакета P1 и P2. В соединении участвуют два маршрутизатора; и пакеты передаются, соответственно, по трём каналам: L1, L2 и L3. В процессе передачи по каналу, каждому пакету требуется время на задержку распространения в передающей среде. Эта задержка напрямую зависит от характеристик среды и пропорциональна её длине. Эта задержка на рисунке представлена буквой d1k, где ! — это номер пакета; а k — это номер канала, по которому пакет был передан. Так, d1l — это время, затраченное первым пакетом на распространение по каналу L1.

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

редь и, в соответствии с наипростейшим принципом обработки очередей FIFO, ожидает в очереди ровно столько времени, сколько потребуется для всех пакетов, прибывших до него, чтобы быть обслуженными и переданными дальше. Эту задержку будем обозначать как qin, где i — номер пакета; а n — номер маршрутизатора, на котором эта задержка случилась.

Также, в маршрутизаторе пакет будет задержан на время передачи пакета (packet transmission delay), см.(3). Ещё устройству необходимо время, чтобы определить, на какой интерфейс этот пакет должен быть дальше отправлен — время обслуживания пакета. Эти две задержки будем рассматривать вместе как s'n, где i — номер пакета, а n — маршрутизатора.

В этом случае, задержка в один конец для i-го пакета может быть вычислена по (5):

k n n

OWD=Z dj+Z qj + Z j (5)

j=1 j=1 j=1

где k и n — общее количество каналов и маршрутизаторов в соединении, соответственно. В общем случае k = n+1

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

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

Вышесказанное даёт возможность предполагать, что характеристика OWD отображает, насколько перегружены промежуточные сетевые устройства. Так, если перегрузки не наблюдается, и каждый пакет может быть тут же обслужен; то значение q в (5) будет также равно для всех пакетов, посланных с этой скоростью. Тогда OWD всех пакетов будет постоянной величиной. Однако, если буфер будет перегружен, как показано на рисунке 12, а скорости кросс- и исследуемого трафиков не изменятся, то OWD каждого последующего пакета будет больше предыдущего, что приведёт к монотонно возрастающему тренду характеристики задержки в один конец.

Джиттер двух последовательных пакетов в сети, в соответствии с [45], определён как абсо-

лютная разница между OWD этих пакетов. Применив (5), имеем:

J (t+1> ,)=|OWDl+1-OWDj =

I j +Z j +Z j-(I Jj +Z qj + I s

j=1 j=1 j=1 j=1 j=1 j=1

n n

I qi+ '-I q1 j=1 j=1

где J(i+1,i) — джиттер между пакетами i и i+1. Из (6) следует, что джиттер в сети - это результат изменения загруженности сетевого устройства к моментам поступления пакетов-проб. Предположим, что через маршрутизатор на рисунке 11, в том же направлении, что и исследуемый трафик, поступают данные от «on/off» приложения; в соответствии с которым передача осуществляется с постоянной скоростью в «оп»-режиме и приложение «молчит» в <^Ь>-режи-ме. Режимы сменяют друг друга с заданной периодичностью, воспроизводя при этом импульсивный трафик. В описанной ситуации значение джиттера будет равно нулю в моменты, когда приложение кросс-трафика выключено; и отличным от нуля при взаимодействии с кросс-трафиком. Примечательно, что в случае постоянной скорости кросс- и исследуемого трафика джиттер также не изменит своего значения.

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

С другой стороны, в современных маршрутизаторах с пропускной способностью 10 Гбит/с на каждый порт, размер буфера каждого интерфейса измеряется сотнями Мбайт; следовательно, время буферизации q намного более существенно, чем время s. Из этого следует, что предлагаемыми далее моделями можно пользоваться.

n

n

n

n

3.2 Измерения доступной полосы пропускания, основанные на оценке

дисперсии пар пакетов

В основе модели PGM (Модель дисперсии проб) лежит анализ изменения межпакетного

временного интервала на приёме относительно межпакетного временного интервала на отправляющей стороне. В различных вариациях этот метод используется в следующих алгоритмах и соответствующих им программах: Delphi [46], Spurce [47], IGI [48] и прочих.

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

1. все промежуточные сетевые устройства обслуживают трафик по схеме FIFO (First In First Out);

2. кросс-трафик подчиняется так называемой «жидкостной» модели трафика [49], в соответствии с которой поведение трафика в каналах описывается подобно поведению жидкостей в трубах;

3. среднее значение скорости кросс-трафика изменяется медленно и в рамках одного измерения принимается за постоянную величину;

4. время получения пробы фиксируется в момент её приёма интерфейсом;

5. в сети есть только один, «узкий», канал, который является и «плотным» каналом.

Эти допущения необходимо иметь в виду при анализе алгоритмами данных. Несмотря на то, что большинство соединений не удовлетворяет этим условиям, алгоритмы все равно способны производить измерения, хоть и менее точно.

Для измерения доступной полосы пропускания выше упомянутые программы посылают последовательности пар пакетов, называемые составами пар пакетов (trains of packet pairs), от источника к получателю. Пары пакетов посылаются с различным межпакетным интервалом и межпарным временным интервалом, в зависимости от алгоритма. Примечательно, что, как правило, для измерения достаточно послать всего один состав пар пакетов.

Рассматривая рисунок 12 как топологию с единственным «плотным» каналом, что удовлетворяет модели PGM, можно заключить, что время, занимаемое кросс-трафиком в канале L2,

равно IpIR - IpIS. Тогда скорость кросс-трафика равна

R"=IpIR-f§C' (7)

где С — пропускная способность «узкого»/«плотного» канала; а IpIS и IpIR — межпакетные интервалы стороне отправителе и стороне получателе, соответственно. Доступная полоса пропускания в соответствии с PGM моделями определяется как

— f!-^)- (8)

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

К её недостаткам можно отнести предположение, что пропускная способность «узкого» канала известна. Кроме этого известна проблема неточности измерения доступной полосы пропускания, описанная в [50]. Здесь на соединениях присутствуют и «плотный», и «узкий» каналы, не являясь при этом единым каналом. Это исследование показывает, что методы, основанные на PGM — в частности, Spruce, имеют тенденцию к недооценке доступной полосы пропускания; а кроме того, что точность измерения зависит и от направления кросс-трафика. Авторы заключают, что необходимость в очень быстром методе определения полосы пропускания очевидна, однако PGM модель не подходит для этой задачи.

Более того, в публикации [41] показано, что модель PGM измеряет не доступную полосу пропускания, а так называемую скорость, основанную на асимптотической дисперсии (Asymptotic Dispersion Rate), которая асимптотически стремится к пропускной способности соединения.

3.3 Измерение доступной полосы пропускания периодической посылкой потоков с постоянной скоростью передачи (PRM) — модель периодических потоков проб

3.3.1 Общие положения

Модель PRM базируется на концепции создания коротких, искусственно сгенерированных перегрузок в сети. Возможность проводить измерения связана с тем, что при посылке источником проб со скоростью, не превышающей доступную полосу пропускания, скорость их приёма получателем будет совпадать со скоростью передачи. С другой стороны, если источник посылает данные со скоростью выше, чем доступная полоса пропускания, тогда очереди на промежуточных сетевых устройствах будут заполняться и, в соответствии с принципом FIFO, пробный трафик будет задержан в сети и даже частично отброшен. В результате этого скорость приёма получателем станет ниже, чем скорость отправки. Таким образом, доступная полоса пропускания может быть измерена методом подбора такой максимальной скорости посылки данных, при которой она будет совпадать со скоростью приёма данных. Ввиду того, что уменьшение скорости происходит посредством увеличения межпакетного интервала на приёме, можно записать [51]:

IpIRj< i •

.(< i; R<A "( >1; R>A'

IpIS { >1; R:

где R — скорость передачи данных; А — доступная полоса пропускания; IpIS и IpIR — межпакетные интервалы при посылке и при приёме, соответственно.

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

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

Такие приложения как Pathload [52], Yaz [51], Pathchirp [53], PTR [48] и TOPP [54] используют вышеописанную модель.

3.3.2 Алгоритм Pathload

Принято считать Pathload наиболее классическим методом, основанным на PRM. В соответствии с его алгоритмом, в ходе каждой итерации измерения посылается не один, а сразу несколько составов проб (по умолчанию 12), называемых вместе флотом (fleet) составов. При этом, между посылкой составов в рамках одного флота, выдерживается пауза, необходимая для освобождения буферов в промежуточных сетевых устройствах, искусственно наполненных предыдущим составом. Каждый состав состоит из постоянного количества проб (по умолчанию 100) неизменного размера. В каждой пробе содержится порядковый номер, а также временная метка генерации этой пробы. На принимающей стороне регистрируется время получения пробы. После приёма состава проб вычисляются значения задержки в один конец (OWD) для каждого пакета, как разница между временем посылки пробы и временем её получения, как показано в (10):

OWDi=Tai-Tdi ' (10)

где Tai и Tdi, соответственно, время отправления и время получения пробы.

Ввиду неидеальности конечных систем, на значениях OWD всегда наблюдаются незначи-

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

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

Анализ тренда OWD осуществляется посредством двух характеристик [52]: PCT (Pairwise Comparison Test) и PDT (Pairwaise Difference Test), которые определены в соответствии с (11) и (12), соответственно.

г

X l(Dk>Dk-l) ( ) S — k—__1 у 4

D г-D1

S —

PDT— Г >

1.В - В, (12)

к=2

где Di — среднее значение 1-й группы OWD. Значение функции I равно 1; если среднее OWD предыдущей было меньше чем текущей и 0 в обратном случае, или при равенстве.

Характеристика РСТ может принимать значения от 0 до 1. Значение 0.5 указывает на то, что тренд OWD невыраженный; а чем ближе значение к 1, тем более ярко выраженный возрастающий тренд задержки у текущего состава. Эта характеристика судит о тренде, исходя лишь из того, является ли среднее OWD значение каждой группы больше последующего или нет. В абсолютных величинах разница между средними значениями никак не учитывается. Ввиду того, что абсолютная разница между значениями может быть существенной, истинный тренд OWD может быть все равно возрастающим, несмотря на низкий показатель этой метрики. Поэтому её не используют без характеристики PDT.

Характеристика PDT позывает, насколько отличается задержка в один конец в начале состава и в его конце. Она может принимать значения от -1 до 1. При этом значение 0 говорит о том, что тренд OWD невыраженный. Чем ближе значение к 1, тем ярче выражен возрастающий тренд. В отличие от РСТ, данная характеристика оценивает именно абсолютную разницу между

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

В [52] авторы определяют граничные значения для вышеописанных характеристик. Так, тренд OWD считается возрастающим, если РСТ больше значения 0.66; нейтральным, если меньше 0.54; а во всех остальных случаях — неопределённым. Для характеристики PDT тренд является возрастающим при значении характеристики больше 0.55; нейтральным, если меньше 0.45; и неопределённым во всех остальных случаях.

Алгоритм Pathload выносит суждение о том, что тренд состава возрастающий, когда одна из характеристик РСТ или PDT фиксирует возрастающий тренд; а другая либо возрастающий, либо неопределённый. Соответственно, выносится суждение о том, что тренд нейтральный, если одна из характеристик указывает на нейтральный тренд; а вторая либо на нейтральный, либо на неопределённый тренд. Если обе характеристики показывают на неопределённый тренд — этот состав отбрасывается.

Характеристиками РСТ и PDT проверяются все составы флота. Если более 70% составов имеют возрастающий или нейтральный тренд, то и тренд этого флота считается возрастающим или нейтральным, соответственно. В противном случае, тренд флота является неопределённым. Скорость передачи данных в последнем случае попадает в так называемую «серую область».

В ходе определения доступной полосы пропускания Pathload оперирует 4 введёнными значениями скоростей передачи данных:

• Rmin — это максимальная скорость передачи данных, при которой у флота был нейтральный тренд;

• Rmax — это минимальная скорость передачи данных, при которой у флота был возрастающий тренд;

• Gmin — это минимальная скорость, при которой тренд флота был не определён;

• Gmax — это максимальная скорость, при которой тренд флота был не определён.

Эти значения используются для определения скорости передачи данных для последующих итераций. Алгоритм выбора новой скорости подробно представлен в [52]. Его принцип схож с бинарным поиском с использованием вышеуказанных значений. Так, например, в случае, если тренд флота нейтральный, и минимальная граница серой области ещё не определена, то следу-

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

R _ R

т-j _ max min /л

Ri+i - 2 •

Pathload начинает определение доступной полосы пропускания с так называемой «экспоненциальной» фазы, которая необходима для того, чтобы определить начальные значения Rmax и Rmin. В соответствии с [52], начальная скорость передачи, по умолчанию, равна 1 Мбит/с. В случае, если у флота нейтральный тренд, скорость для следующего флота будет удвоена. Таким образом, скорость увеличивается с каждой итерацией до тех пор, пока очередной флот не покажет возрастающий тренд. Тогда Rmax — это скорость передачи последнего флота, а Rmin — это скорость передачи предпоследнего флота.

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

Другие два важных параметра, введённые для определения доступной полосы пропускания — это разрешение измерения q и разрешение серой области /.

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

• разница между Rmax и Rmin меньше или равна разрешению измерения:

Rmax _ Rmin< W >'

• обе границы доступной полосы пропускания находятся в рамках разрешения серой области относительно соответствующей границы серой области: Rmax _Gmax < х и G _ R < х

rl min min — Л •

В качестве финального результата, Pathload предоставляет область полосы пропускания, в которой находится доступная полоса пропускания [Rmm;Rmax].

Недостатком решения Pathload является то, что измерение занимает значительное время. Так, в [52] авторы указывают, что этот процесс, в соединении с RTT 90 мс, может занять до 12 секунд при измерении полосы пропускания в 10 Мбит/с, произведя 10 итераций; при измерении полосы в 75 Мбит/с, процесс может занимать до 22 с, при количестве итераций до 18. Кроме того, каждое измерение использует значительное количество трафика: если одна проба

— это UDP-дейтаграмма размером 1500 Байт, то один состав проб (по умолчанию, 100 проб в составе) будет переносить 150 КБ. В этом случае, один флот (по умолчанию, 12 составов) имеет размер 1.8 МБ. Для измерения может потребоваться заранее непредсказуемое количество итераций; но, если рассмотреть случай, приведённый выше, то необходимо послать 18 флотов; а, значит, цена измерения доступной полосы пропускания порядка 32.4 МБ.

3.3.3 Алгоритм Claibrated Pathload

Алгоритм Pathload лежит в основе алгоритма Calibrated Pathload, который используется приложением Yaz.

Создатели Yaz в [51] учитывают, что в сети присутствуют не только эффекты расширения, но и эффекты сжатия. Наглядно эффект сжатия проиллюстрирован на рисунке 14.

Рисунок 14 - Дисперсия покетов, иллюстрирующая эффект сжатия

Подобная дисперсия пакетов справедлива для топологии на рисунке 11. Из рисунка видно, что в канале L2 межпакетный интервал изменяется, причём для части пакетов он подвергается сжатию, а для другой части — расширению. Таким образом, имеем Т2<Ъ<Тз. Подобное сжатие вносится кросс-трафиком в промежуточных сетевых устройствах.

С учётом возможного сжатия пакетов, авторы переопределяют (9) следующим образом:

|lpIR- IpISl =

< Z-IpIS; R <A >Z-IpIS; R>A'

(14)

где ^ — это пограничный параметр, определяющий доверительный интервал. Находясь

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

Новый постулат, введенный авторами и следующий из уравнения (14), показывает, что перегрузкой считается не только «растяжение» межпакетных интервалов, но и их «сжатие» при прохождении соединения. В [51] также показано, что подходы в определении полосы пропускания наиболее близкие к классическому — Pathload и Spruce — не фиксируют «сжатие». Это видно в результатах экспериментов, представленных их авторами. Этот эффект понижает точность определения поросы пропускания.

Определение скорости передачи для последующей итерации, основывается не на результатах всех предыдущих измерений, как это делается в Pathload, а на результате только последнего измерения[51] (15):

lIpIR-IpISl

IpIS= IpIS 2 " ', (15)

где IpISn — это межпакетный интервал для следующей итерации; а IPIS и IPIR — это средние значения межпакетных интервалов посылки и приема, собранные получателем.

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

В отличие от Pathload, Yaz посылает всего лишь один состав проб в ходе итерации; а имея в виду то, что предложенный алгоритм определения следующей скорости позволяет добиться результата при меньшем количестве итераций для каждого измерения, можно предположить, что время измерения будет значительно меньше, чем у Pathload. Практически, в [51] показано, что измерение Yaz, в среднем, в 5 раз быстрее чем для метода, предлагаемого в Pathload. Более того, Yaz обеспечивает приемлемую ошибку измерения, составляющую 10%, в 80% случаев, что на 30% лучше, чем у Pathload.

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

К недостаткам алгоритма Calibrated Pathload можно отнести то, что он, как и Pathload, для

измерения использует постоянное, предопределённое, количество проб в составе на всех скоростях, что может быть не эффективно. Кроме этого, им никак не учитывается вариация задержки, значит, джиттер может существенно снизить точность измерений. Также Yaz, при необходимости, может измерять доступную полосу пропускания разным размером проб, что не в полной мере отвечает использованию его в высокоскоростных транспортных протоколах. Стоит отметить, что введённый постулат о том, что эффект компрессии всегда сигнализирует о перегрузке в сети нуждается в проверке (см. 4.14).

3.4 Выводы к главе 3

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

Были рассмотрены две наиболее распространённые модели, которые, опираясь на описанные свойства, позволяют определить доступную полосу пропускания, избегая при этом пересылки большого объёма данных. Методы на основе модели PGM позволяют осуществлять измерения значительно быстрее; однако исследования показывают, что уровень их ошибки значительно выше чем для модели PRM. Кроме этого, в [41] говорится, что с помощью этой модели определяется не доступная полоса пропускания, а так называемая скорость асимптотической дисперсии, не всегда являющаяся реальной полосой пропускания. Более точный класс алгоритмов использует модель PRM, о чём говорят многочисленные исследования. Помимо этого, основные положения модели PRM хорошо вписываются в алгоритм передачи данных транспортным протоколом.

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

4 Алгоритм Kite и сопутствующие алгоритмы

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

В ходе данного исследования существующий алгоритм Calibrated Pathload был существенно улучшен. Для тестирования алгоритмов измерения доступной полосы пропускания, а также алгоритмов, улучшающих качество измерений, в ходе диссертационной работы была написана программа с использованием языка C++ под называнием Kite (англ. воздушный змей — последовательности пакетов можно представить как хвост воздушного змея). Оптимизированный алгоритм получил такое же название.

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

r=StS- (16)

где R — скорость передачи данных в бит/с; S — размер пакета в битах; а IpIS — межпакетный интервал времени при посылке данных в секундах.

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

4.1 Изменение количества тестовых пакетов в зависимости от скорости передачи в ходе итерации

В описанных, в предыдущем разделе, алгоритмах, источник посылает данные составами

заранее определённой длины. В ходе экспериментов с различной длиной пакетов, становится ясно, что для медленных соединений до 100 Мбит/с необязательно посылать много проб для получения измерения с приемлемой величиной ошибки. Увеличение количества проб приведёт лишь к несущественному увеличению точности измерений, однако значительно увеличит использование ценной пропускной способности. Более того, для таких алгоритмов как Pat:hload, посылающих несколько составов в ходе одной итерации, будет затрачено существенно больше времени на измерение.

Это можно проиллюстрировать экспериментально. В сети с различной пропускной способностью и кросс-трафиком, занимающим 40% пропускной способности, производятся измерения. При пропускной способности до 1000 Мбит/с размер проб составлял 1472 байт, от 1 до 10 Гбит/с — 8972 байт. На 15А размер состава для всех измерений равен 50 проб. На участке до 400 Мбит/с ошибка оценки незначительна, однако уже при 800 Мбит/с ошибка увеличивается до 9%. Уровень ошибки уменьшается начиная с 1 Гбит/с, потому что размер проб был увеличен, но уже при 8 Гбит/с ошибка вновь на уровне 7%.

т (и о. (и

го

^

3 О

0.5

0

сс

-0.5

I

<Ь>

а_

ш -1

Е

^ -1.5

ГО

¥ ю -2

^

3 -2.5

О

-3

В)

10

80 100 200 400 800 1000 2000 4000 8000 10000 Пропускная способность, Мбит/с

1 ч 1 1 1 1 ошибка о

\ * вр емя -■ ■ о - - -

< >> '-Л

\ / р—■< ----- * \

1 1 0 1 1 II Г 1

20

40

80

100 200 400 800 1000 2000 4000 8000 10000 Пропускная способность, Мбит/с Рисунок 15 - Ошибка измерения при постоянном размере состава

A) размер состава 50 проб;

B) размер состава 200 проб;

и (К I

и о. ш г

п ^

и; г <и а_ со

12 10

8 6 4 2 0

и

(К ^

т и а_ ш

г п

б:

ОС

г и а_ со

При измерении с постоянным размером составов в 200 проб, точность измерения варьируется в пределах 3% для всех рассмотренных случаев — рисунок 15В. Однако, время измерения выше примерно в два раза, чем в случае с 50-ю пробами в составе.

Исходя из вышеописанного, предлагается посылать различное количество проб в зависимости от скорости передачи (17). Проведённые эксперименты показывают, что 50 проб в составе — это минимальное количество, при котором большинство помех в среде передачи данных будут сглажены. В свою очередь, 200 проб, как это видно из рисунка15 — достаточно для измерения доступной полосы пропускания с высокой точностью (ошибка не более 3%), вплоть до 10 Гбит/с.

N (R ) =

50, ifR < 100 Мбит / с

132.5-Ы(0.05^)|, if R ^100 Мбит/с'

(17)

где R — это скорость передачи данных в Мбит/с; а N — количество проб в составе для следующего измерения.

Предложенная зависимость размера состава от скорости передачи (17) представлена на рисунке 16.

200

1 10 100 1000 10000 Скорость передачи данных, Мбит/с Рисунок 16 - Количество проб в зависимости от скорости передачи данных

Начиная со 100 Мбит/с, число необходимых проб имеет логарифмический характер потому, что на участке от 100 до 1000 Mбит/с необходимо быстро нарастить количество проб и плавно увеличивать их дальше на участке до 10 Гбит/с. Такая зависимость позволяет экономить пропускную способность и время на низких скоростях и проводить более детальный анализ на высоких, при которых джиттер и другие помехи могут существенно ухудшить результаты измерений.

4.2 Коэффициент понижения шага

В соответствии с алгоритмом Calibrated Pathload, после каждой итерации источнику задаётся скорость передачи данных, которая должна быть использована для следующей итерации. Межпакетный интервал, в этом случае, вычисляется по (17).

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

Джиттер двух последовательных пакетов в сети, как это следует из (6), — это абсолютная разница OWD двух пакетов. Ji = IOWDi+1-OWD;|

Тогда будем считать джиттером состава проб сумму всех джиттеров этого состава, делённую на величину состава — (18).

J состава =

^ 31 (18) N '

где J состава — джиттер состава; Ji — джиттер 1-й пары пакетов; а N — размер состава.

Однако, интерес предоставляет не сам джиттер, а то, как он изменяется при получении этого состава. Для этого определим среднеквадратическое отклонение джиттера (19). СКО показывает отклонение джиттера от математического ожидания.

N

I (1Э)

(I J )2

i = 1

о j= —

N-1

где Oj — СКО джиттера.

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

N

ация задержки повлияла на межпакетный интервал, полученный в ходе измерения. Для этого введём дополнительную метрику JtI (20), характеризующую размер межпакетного интервала 1рШ относительно СКО джиттера. Используя данную метрику, можно сделать выводы, была ли величина вариации джиттера соизмеримой с межпакетным интервалом.

за=

(20)

1рШ

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

В (15) джиттер может исказить лишь составляющую 1рГО., ведь 1р^ никак не взаимодействует с сетью. Ситуации, которые могут исказить измерение 1рК, такие как переключение контекста или непредвиденные системные прерывания, должны быть отфильтрованы алгоритмом контроля контекстных переключений (см. 4.10) или алгоритмом «своевременной» посылки данных (см. 4.11).

Следовательно, если в соединении во время следования состава проб джиттер ощутимо изменялся, полученное значение 1рГО. может быть значительно больше, чем 1рШ, отображающее ситуацию в соединении. В качестве значения 1рШ, отображающий ситуацию в соединении, в этом контексте будем понимать такой межпакетный интервал, при использовании которого для генерирования потока данных с постоянной скоростью будет занята все доступная полоса пропускания, и не произойдёт перегрузки. Если же фактический 1рГО. будет больше отображающего, а, соответственно и скорость передачи данных будет меньше, тогда любое из условий (14) и (9) укажет, что эта скорость не превышает доступную полосу пропускания и отрапортует её как результат оценки. Это может привести к серьёзным неточностям результата.

Предлагается увеличивать межпакетный интервал 1р^п в зависимости от метрики JtI. Для этого введём понятие коэффициента понижения шага SDF, которое будет нелинейно увеличиваться с ростом JtI.

SDF используется для расчёта скорости передачи для следующей итерации, см. (21).

11рШ - 1рН\

№ = ^ + БО^ЗТ) , (21)

Для определения характера зависимости SDF, наиболее подходящего для рассматриваемого случая, был проведён эксперимент с различными схемами вычисления: а, Ь, с, d см (22).

Оз

a: SDF (JtI )=2,

b: SDF (JtI )

c: SDF (JtI):

1.5, if JtI < 0.5

0.79-exp(0.92 J), if JtI >1 ;

1.5, if JtI < 0.5

0.9-exp( 1.2-JtI), if JtI >1 '

d: SDF (JtI):

1.5, if JtI < 0.5

0.9-exp (0.65- JtI), if JtI >1

Графически предложенные схемы отображены на 17.

О 0.5 1 1.5 2 2.5 3

JTI

Рисунок 17 - Коэффициент понижения шага

Схема а — это неизменное значение, отображающее вычисление IpIS для следующей итерации, соответствующее алгоритму Calibrated Pathload. Три остальные схемы были предложены в рамках диссертационной работы по следующему принципу: значение коэффициента предлагается приравнять к 1.5 при малом значении JtI (до 0.5) и экспоненциально увеличивать с ростом JtI. Из (21) вытекает, что если среднеквадратичное отклонение джиттера незначительно по сравнению с межпакетным интервалом на приёме, то межпакетный интервал для следующей итерации стремится быстрее к значению IpIR; если же нет — медленнее. Такая методика позволяет уменьшать количество итераций в случае с малым джиттером без потери точности оценки. В противном случае, будет произведено больше итераций, чтобы обеспечить достаточную точность. Чем больше значение JtI, тем меньше можно доверять оценке. Предлагается использовать экспоненциальную зависимость SDF от JtI, чтобы минимизировать возможную ошибку при ощутимых значениях JtI (1 и более). Представленные схемы b, c и d, на рисунке 17, отображают «крутую», «нормальную» и «пологую» характеристики, что показывает, насколько сильно будет

изменяться SDF в зависимости от JtI.

Эффект от внедрения SDF, предложенного в этой работе, проиллюстрирован на рисунке 18. В ходе эксперимента эмулировались: задержка RTT — 40 мс; вариация задержки по нормальному закону распределения с СКО 0.3 мс; кросс-трафик для каждого значения пропускной способности составлял 40%. Для пропускной способности до 1 Гбит/с включительно был использован MSS 1472 Байта, в остальных случаях MSS был равен 8972 Байта. В экспериментах использовалась схема изменения количество проб в составе, представленная в разделе 4.1.

1-1-г

схема а; времея, с схема Ь; времея, с схема с; времея, с схема с1; времея, с

о. ш

100 200 400 800 1000

Пропускная способность, Мбит/с

=1

О

100 200 400 800 1000

Пропускная способность, Мбит/с

2000

4000

8000

10000

Рисунок 18 - Ошибка и время оценки для предложенных схем (22)

Стоит отметить, что для всех исследуемых схем до пропускной способности 200 Мбит/с ошибка оценки не превышает 5%. А после этой пропускной способности ошибка достигает, в худшем случае, значения 17% для схем а и d, и значения порядка 8% для схем Ь и с. При значении пропускной способности 2 Гбит/с для всех схем наблюдается значительное увеличение точности оценки — это связано с тем, что именно начиная с этого значения в экспериментах ис -пользуется MSS 8972 Байта.

«Пологая» схема d требует не больше времени чем схема а (постоянное значение SDF), однако, и ошибка оценки, и вариация ошибки достигают также больших значений. Схема с при

пропускной способности 800 Мбит/с достигает малого среднего значения ошибки оценки. На низких скоростях, этой схемой затрачивается значительно больше времени для проведения оценки, обеспечивая при этом высокую точность. Однако, на высоких скоростях (4 и 8 Гбит/с) именно этой схемой обеспечивается наиболее точная оценка

В проделанном эксперименте схема b обеспечивает среднее значение ошибки, не превышающее 10% для всех рассмотренных случаев. При этом зафиксировано лишь незначительное увеличение времени оценки для пропускной способности до 400 Мбит/с.

В итоге, в обозначенных условиях, использование схемы b и с позволяет увеличить точность оценки доступной полосы пропускания при средней ошибке оценки не более 10%. Так как схема b к тому же затрачивает меньше времени на измерение, именно она будет использована в реализации алгоритма Kite. Обозначенная в (22) и на рисунке17 характеристика зависимости SDF от JtI (схема b) не единственно возможная. Схожие результаты увеличения точности будут достигнуты при использовании характеристики, отличающейся до 20% от схемы b на рисунке 17.

4.3 Алгоритм измерения Kite

Алгоритм измерения содержит три основные части (см. рисунок 19):

1. алгоритм установки начальной скорости (AIR);

2. алгоритм «возрастающая фаза»;

3. алгоритм «убывающая фаза»;

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

blncPhaselsNeeded

AIR algorithm blncPhaselsNeeded = air()

IncPhase ()

Result = decPhase(result)

result

Рисунок 19 - Общий алгоритм измерения Kite

В качестве результата измерения каждого состава (21 блок 2; 23 блок 1; 24 блок 14) возвращается структура, содержащая консолидированные данные от получателя состава (см. 27) и характеристик посылки состава. UML-диаграмма структуры-результата измерения представлена на рисунке 20.

MeasurementResult

bMeasurementlsBroken : bool

bTooMuchCS : bool

bCongestion : bool

dPLR : double

¡NextRate : int

¡SentBytes: int

¡SendRate : int

¡RequestedRate : int

Рисунок 20 - UML-диаграмма структуры MeasurementResult

На диаграмме:

• Флаг bMeasurementIsBroken указывает на то, что по каким-либо причинам измерение не увенчалось успехом;

• bTooMuchCS — флаг, указывающий на то, что в ходе посылки данных было слишком много непредвиденных задержек — больших, чем величина желаемого межпакетного интервала (см. 4.10);

• флаг bCongestion указывает на то, что скорость, с которой был послан состав, вызвала перегрузку в соединении; т. е. скорость превышает доступную полосу пропускания (см. 4.8);

• dPLR — уровень потерь пакетов в соединении, зафиксированном при передаче состава;

• iNextSendRate — значение скорости передачи состава для последующей итерации (см. 4.8);

• iSentBytes — количество байт, переданных в ходе измерения;

• iSendRate — фактическая скорость отправки состава;

• iRequestedRate — желаемая скорость отправки состава.

Каждое измерение включает в себя передачу состава источником в соответствии с алгоритмом, описанным в 4.11, и анализ состава приёмником в соответствии с алгоритмом описанным в 4.8

4.4 Алгоритм установки начальной скорости (Adjustment of Initial

Rate - AIR)

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

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

• iNrOfAttempt — номер итерации;

• iMinAmOfAttempts — минимальное количество итераций; прежде, чем алгоритм завершится с, возможно, неточным измерением;

• NOCONGESTЮN — при передаче состава по соединению не было зафиксировано перегрузки;

• iMinAllowedPLR, iMaxAllowedPLR — соответственно, минимальная и максимальная границы потерь пакетов для измерений.

Диаграмма работы этого алгоритма приведена на рисунке 21. Измерение (блок 2) считается искажённым, если по той или иной причине было получено меньше 10 проб. В таком случае, в зависимости от количества потерь (блок 6), следующая скорость передачи будет либо уменьшена в 2 раза (чтобы не вызывать сильную перегрузку), либо на процент потерь в ходе измерения.

I

2

Ке$иИ = теа5иге(ПтШа1е)

I __'

Рисунок 21 - Диаграмма алгоритма установки начальной скорости

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

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

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

В ходе эксперимента исследовались значения количества проб от 3 до 50 включительно. Для каждого количества проб последовательно передавалось 100 составов соответствующего размера от источника к получателю (топология сети совпадает с рисунком 11). Использовалось соединение с пропускной способностью 10 Гбит/с между серверами с сетевыми картами ^еЫо. В ходе каждой итерации измерялись средние значения 1рК и 1рШ для каждого состава. Эксперимент был проведён для приёма данных с объединением прерываний и без него (см. подробнее об объединении прерываний в 4.14). Результаты исследования изображены на рисунке 22.

без объединения прерываний

п-1-1-г

стандартное отклонение 1р1К, мкс I-среднее значение 1р1К, мкс среднее значение 1р1Б, мкс -стандартное отклонение 1р1Р относительно среднего значения 1р1К, % -

100

80

60

jmJÎfffÎfÎ!'"

20 25 30

количество проб

с объединением прерываний

п-1-1-г

стандартное отклонение мкс I—I—I среднее значение 1р1К, мкс среднее значение 1р1Б, мкс —*— стандартное отклонение 1р1Р относительно среднего значения 1р1К, % —•—

100

80

20 25 30

количество проб

Рисунок 22 - Характеристика работы алгоритма AIR в зависимости от размера состава

A) с объединением прерываний на приёмной стороне

B) без объединения прерываний на приёмной стороне

Стандартное отклонение IpIR для сетевых карт Intel несколько меньше, чем для Chelsio,

поэтому в качестве результата продемонстрирована худшая характеристика — для адаптеров ^еЫо. Из характеристики видно, что для обоих случаев и с объединением прерываний

и без него, при посылке менее 15 проб относительное стандартное отклонение, в большинстве случаев, превышает 50%; начиная с 20 проб, относительное отклонение не превышает 40%, а начиная с 40 проб - не превышает 20%. Так как алгоритм AIR, опираясь на среднее значение IpIR, выполняет грубую оценку доступной полосы пропускания, то чем меньше вариация IpIR, тем точнее будет полученный результат. При этом стоит помнить, что посылка большого количества пакетов с максимальной скоростью может привести к перегрузке в сети.

Исходя из вышеизложенного, необходимо выбирать количество проб для алгоритма AIR, которое бы обеспечивало необходимую точность оценки, и при этом не создавало перегрузку в сети. Текущая версия программы запускает 20 проб, что обеспечивает приемлемую точность грубой оценки (ожидается ошибка не более 40%). Кроме этого, в ходе экспериментов в реальных сетях, при таком количестве проб не возникали перегрузки, сопровождаемые потерями пакетов.

4.5 Алгоритм возрастающей фазы

Возрастающая фаза (см. рисунок 23) призвана увеличить скорость передачи проб в случае, если оценка при использовании алгоритма AIR закончилась безуспешно, или при измерении не было зафиксировано перегрузки. Алгоритм увеличивает скорость передачи на 10% в каждую итерацию (блок 5) до тех пор, пока не будет зафиксирована перегрузка. Количество проб в составе определяется в соответствии с (17). Алгоритм ведёт подсчёт количества выполненных итераций (блок 1). В случае, если в ходе передачи состава были обнаружены потери, но при этом перегрузка не была зафиксирована, следующий состав будет передаваться со скоростью, увеличенной только на 5%. Если были обнаружены потери, и количество итераций превзошло минимальное количество попыток (в текущей версии это количество равно 3), то возрастающая фаза заканчивается, сообщая отправителю, что где-то в соединении есть буфер малого размера; и невозможно засечь перегрузку — блок 7.

В случае, если была зафиксирована перегрузка, то последняя итерация повторяется с той же скоростью (блок 9). Если в ходе повторной передачи состава также фиксируется перегрузка, то возрастающая фаза заканчивается, и начинается алгоритм убывающей фазы. Ситуация, при которой измерение не увенчалось успехом (количество принятых пакетов не позволяет получить корректный результат) не отображена на диаграмме. В этой ситуации, если количество итераций не превышает минимального значения, скорость следующего состава уменьшается на 10%. В противном случае, возрастающая фаза заканчивается, сообщая отправителю, что качество сети низкое.

Result

Result = measure(iRate) ¡NrOfAttempt++

¡Rate = iRate*l.l bRepetition = False