Содержание к диссертации
Введение
Глава 1 Классические решения 1р-мультикаст 17
Введение 17
1.1 Unicast/broadcast/multicast 17
1.2 Принципы работы multicast
1.2.1 IGMP 21
1.2.2 PIM 21
1.3 Недостатки решения ip-multicast 23
1.3.1 Отсутствие гарантии доставки 24
1.3.2 Низкий уровень безопасности 24
1.3.3 Поддержка на промежуточных устройствах 1.4 варианты использования ip-multicast 25
1.5 Перспективы использования tcp на транспортном уровне ip-multicast
1.5.1 Механизмы установления соединения tcp 27
1.5.2 Механизмы контроля перегрузок в tcp 28
1.6 Математическая база высокоскоростного многопоточного трафика 32
1.6.1 Модель одного потока 33
1.6.2 Допущения модели 35 вывод 36
Глава 2 Существующие альтернативные протоколы введение 38
2.1 С чего начинается разработка альтернативного протокола? 38
2.1.1 Выбор базового протокола 39
2.1.2 Тестовая среда 41
2.1.3 Протокол передачи данных norm 43
2.2 Протокол передачи данных uftp 47
2.2.1 Протокол передачи данных pgm 50
2.2.2 Анализ полученных результатов 51
Вывод 55
Введение
Глава 3 Разработка и описание алгоритмов р2м введение 56
3.1 Что представляет собой р2м? 57
3.1.1 Установление соединения в р2м 57
3.1.2 Форматы пакетов в р2м 59
3.1.3 Структура р2м в режиме отправки 61
3.1.4 Управление группой получателей в р2м 63
3.1.5 Использование неблокирующих очередей в р2м 64
3.1.6 Неблокирующие буферы данных в р2м 66
3.1.7 Хранилище метаинформации в р2м 69
3.1.8 Потоки выполнения в р2м 82
3.1.9 Получатель р2м 89
3.1.10 Модуль управления перегрузками и контроля потока в р2м 96
3.2 Анализ алгоритмов контроля перегрузок в р2м 109
3.3 Гарантия доставки и понятие аварии в р2м 112
Вывод 117
Глава 4 Экспериментальное исследование р2м введение 119
4.1 Тестовая среда и сценарии 119
4.1.1 Настройка р2м 120
4.1.2 Базовые тесты производительности 120
4.1.3 Влияние вариации задержки на производительность р2м 124
4.1.4 Сценарии с медленным получателем в р2м 126
4.1.5 Кросс-трафик в р2м сессии 130
4.1.6 Расширение конфигурации р2м используя джамбо-кадры 133
4.1.7 Модель прогнозировании ситуации в канале связи и дальнейшие исследования 135
Вывод 141
Вывод по работе 143
Литература
- Недостатки решения ip-multicast
- Выбор базового протокола
- Форматы пакетов в р2м
- Влияние вариации задержки на производительность р2м
Недостатки решения ip-multicast
Следовательно, для организации передачи данных множеству получателей необходимо открыть N TCP соединений, где N - число получателей. Данный подход тяжело назвать эффективным, поскольку открытие множества соединений означает открытие множества программных интерфейсов, каждый из которых потребует память и процессорное время даже в состоянии покоя.
Следовательно, понятие «соединение» в TCP обладает особой строгостью и привязкой к одному получателю, которая наносит отпечаток на программную реализацию протокола.
В данной работе предложена альтернативная гибкая схема, когда состояние сокета «подключён» характеризуется наличием нескольких получателей, число которых может изменяться в течение сессии передачи данных. При этом поток данных для каждого получателя будет использовать один программный интерфейс на стороне отправителя, что позволит значительно увеличить эффективность работы протокола в контексте использования вычислительных ресурсов.
Как только соединение было установлено, TCP начнёт передачу пользовательских данных. Перед переходом к процессу передачи данных стоит заметить, что существует несколько реализаций TCP, характеризующиеся разными значениями внутренних таймаутов и некоторыми тонкостями работы внутренних алгоритмов. Среди существующих реализаций стоит выделить основную, являющуюся стандартом версию TCP CUBIC [16], [17], которая является версией «по умолчанию» для всех стандартных Linux-систем начиная с версии ядра 2.6.19. Целью выпуска данной версии являлось повышение эффективности работы TCP в сетях, характеризующихся высокой полосой пропускания и высокими сетевыми задержками (Long Fat Networks). Версия CUBIC является модификацией версии BIC TCP (Binary Increase Congestion control). Оба названия сигнализируют о различных подходах к проблеме контроля перегрузок в сети. Здесь стоит отметить, что TCP всегда оперирует понятием контроля перегрузок методом установки окна (Window - Based Congestion Control). Под окном понимается максимальное количество пакетов, которым разрешено быть «в пути», то есть они находятся в состоянии «отправлен, но не подтверждён». Долгое время у TCP существовала проблема при работе в длинных широкополосных сетях (LFN). Сети LFN являются нормой при передаче трафика на большие расстояния через Интернет. Такие сети характеризуются большим произведением полосы пропускания на задержку (BDP). В сетях вида LFN, для обеспечения максимальной утилизации всей доступной полосы пропускания, требуется большее количество пакетов “в пути”. В контексте TCP это означает расширение окна до достаточно больших размеров. В свою очередь, в классических версия TCP, как TCP Reno [18], увеличение окна производится один раз за время следования пакета туда и обратно (RTT). Следовательно, при большом RTT, который характерен для сетей вида LFN, увеличение размера окна TCP будет производиться достаточно редко, тем самым сильно замедляя процесс набора скорости протокола (в случае наличия такой возможности). Это приводит к тому, что пройдет ощутимое количество времени перед тем, как протокол доберётся до максимально эффективной скорости передачи данных. Более того, на коротких сессиях эффективное использование полосы пропускания так и не будет достигнуто.
В случае использования CUBIC применяется более эффективный подход к расширению размера окна. Принципиальное отличие CUBIC - использование кубической функции роста окна с учётом времени, прошедшего с момента последней перегрузки. Как показано на рисунке 1.6, TCP CUBIC использует как выпуклые, так и вогнутые профили изменения окна. После уменьшения размера окна, вызванного потерей пакета, записывается значение Wmax, которое отражает размер окна в момент потери, и окно уменьшается в X раз, где X - постоянная, являющаяся частью конфигурации CUBIC. После прохождения фазы быстрого восстановления (Fast Retransmission) происходит переход в режим избегания перегрузок с постоянным расширением окна. Расширение начинается с использованием вогнутого профиля. Функция построена так, чтобы её плато приходилось на значение Wmax. Глава 1 Классические решения IP-мультикаст
Данный подход принёс протоколу TCP новый уровень стабильности, поскольку, размер окна остается очень постоянным и всегда лежит в границах максимально эффективного. В [17] показано, что размер окна рассчитывается по формуле W(f) = C(t - fc)3 + Wmax (1.1) в которой С - параметр алгоритма, t - время, прошедшее с момента последнего уменьшения окна, k - период времени, необходимый для увеличения. Параметр k вычисляется по следующей формуле из [17]: 3 Wmax Р к = \— ±—! 4 (I-2) Далее, при получении каждого ACK окно пересчитывается и адаптивная функция подстраивает свои Как только значение окна добралось до Wmax, профиль функции меняется на выпуклый. параметры.
Представим, что произойдёт при наличии в сети нескольких получателей. Данный подход к контролю перегрузок целиком и полностью базируется на факте того, что получатель в сети один, и каждый параметр формулы уникален. Но в нашем случае это не так. Более того, параметры соединения, такие как RTT, частота потерь и др. могут значительно варьироваться от получателя к получателю. И адаптироваться под такие Глава 1 Классические решения IP-мультикаст изменения достаточно сложно. Например, идёт передача данных от одного источника к пяти получателям. В случае потерь на одном из соединений, подход TCP резко уменьшит ширину окна до W1, что значительно снизит утилизацию соединений, на которых проблем не было обнаружено. Далее, возможны следующие шаги алгоритма:
Выбор базового протокола
Несмотря на то, что MFTP (в виде UFTP) показал лучшие результаты, отсутствие механизма контроля перегрузок существенно ограничивает области использования данного решения. Проведённый анализ решения показал, что наиболее эффективным подходом можно назвать реализацию схемы контроля перегрузок без привязки к RTT, поскольку в случае передачи данных среди географически распределённых получателей трудно говорить о RTT, как об универсальной метрике. Наиболее правильным же подходом будет привязка скорости передачи данных к уровню сетевых потерь и как будет показано в Глава 2 Существующие альтернативные протоколы разделе 3.1.10, к свободному месту в буфере получателей, что является достаточно универсальной метрикой качества соединения как в случае одного, так и нескольких получателей.
Принципиальным моментом является противостояние между двумя видами алгоритмов: на базе окна передачи и на базе скорости передачи. Результаты показали, что алгоритмы на базе скорости передачи данных обладают значительно более высокой эффективностью и адаптивностью, что особенно заметно в сетях с потерями. Более того, при передаче данных нескольким получателям одновременно неизбежная и логичная зависимость окна передачи от RTT делает применение подобных алгоритмов особенно неэффективным в силу географического разброса получателей и, как следствие, большой вариации RTT в рамках одной сессии. Более же эффективным методом является привязка скорости передачи данных к уровню потерь. В рамках данной работы будет предложен расширенный вариант этой схемы: добавляется новая метрика -количество свободного места в буфере принимающего приложения. Введение новой метрики позволит алгоритму принимать более точные решения, основанные на отчётах о состоянии каждого получателя.
Большинство программных реализаций того или иного протокола передачи данных оперирует понятием буферизации пользовательских данных. Под буферизацией понимается сохранение данных, которые необходимо послать, в промежуточном хранилище, находящемся под управлением протокола. Схематически данный процесс приведен на рисунке 2.6.
Проведенные исследования показали, что именно процесс копирования данных часто вызывает наибольшую задержку по сравнению с другими шагами (например, сборка пакета данных). Центральный элемент приведённой схемы, а именно реализация доступа к нему, является одной из критически важных задач разработки протокола передачи данных.
Относительно низкий лимит скорости передачи данных (сравнивая с поставленной задачей) в исследованных протоколах в большей степени объясняется низким уровнем производительности процесса буферизации, поскольку при полном отсутствии потерь в сети остаются лишь три лимитирующих фактора: скорость работы жесткого диска, либо шины оперативной памяти в зависимости от конкретного случая; пропускная способность сетевой платы; время, затраченное на буферизацию данных в протоколе.
И если первые два фактора легко поддаются оценке, то последний напрямую зависит от эффективности, программной реализации. Решение, предложенное в данной диссертации базируется на использовании буфера данных, обладающего принципиальной особенностью: а именно возможностью разделения процесса чтения и записи данных на два независимых потока, способных выполняться одновременно и независимо друг от друга на различных ядрах микропроцессора.
Анализ исследованных протоколов явно показал, что работа в формате точка-многоточка требует наличия негативных сообщений (NACK) в схеме ARQ. Это является единственным решением по ряду причин, основной из которых все также является высокий разброс RTT, что усложняет принятие решения о потере пакета исходя из какого-либо тайм-аута. Стоит при этом помнить, что проблема перегрузки отправителя из-за большого объёма потока ARQ сообщений, как было показано в работах [65], [66], [67] также является важной проблемой, которой необходимо решение. Глава 2 Существующие альтернативные протоколы
В этой области, из существующих решений, лидером является протокол MFTP, который предполагает агрегацию ACK/NACK сообщений с целью снижения количественной нагрузки на отправителя (количество получаемых отчётов в единицу времени). Данный подход демонстрирует высокую стабильность и лёгкость масштабирования путём изменения максимального количества подтверждённых либо потерянных пакетов в одном отчёте. Подход в NORM не оправдывает себя по двум причинам: перенос чрезмерной ответственности на отправителя, что приводит к удвоенному времени ожидания перед повторной отправкой потерянного пакета (поскольку запрос должен дойти до каждого получателя, а ответ вернуться назад, то есть проходит время RTT); дополнительное снижение скорости передачи поскольку помимо траты времени на повторную передачу, отправитель вынужден тратить время на генерацию и отправку запросов каждому получателю. А это, в свою очередь, может занимать значительное время, особенно в случае множества получателей.
PGM, в свою очередь, полностью опирается на поддержку протокола на промежуточных сетевых устройствах и реализует схему немедленного уведомления о потере, что, разумеется, может привести к увеличению числа NACK.
Форматы пакетов в р2м
Из приведённой схемы видно, что как на отправителе, так и на получателе, буфер является неотъемлемой частью, пропускающей через себя каждый бит пользовательской информации. Вопросы производительности этих элементов не раз поднимались, и предложенные решения [69] одинаково хорошо подходят как для передачи данных в формате точка-точка, так и точка – многоточка. Этому есть простое объяснение: при передаче данных нескольким получателям необходимо прочитать данные из буфера, собрать пакет и послать его нескольким получателям одним из способов (либо через multicast-адрес, либо посредством нескольких unicast-отправок). Модель высокопроизводительного буфера приема/отправки мало чем отличается в рассматриваемом случае от классического точка-точка. Однако необходимо рассмотреть базовые принципы организации такого буфера.
В целом, модель буфера, позволяющего вести одновременные чтение/запись/удаление из разных потоков исполнения без использования синхронизационных сущностей представляет собой кольцевой буфер с набором указателей на определённые участки памяти. В каждом участке памяти разрешено работать только одному потоку. Этим и гарантируется безопасность ведения операций даже на гигабитных скоростях. Так например, для случая с буфером отправки, структура буфера представляет собой кольцевой буфер, изображённый на рисунке 3.5. Указателям разрешено двигаться только в одном разрешенном направлении. Можно выделить четыре указателя, разделяющих буфер на три части:
Указатель начала буфера – необходим для чёткого детектирования местоположения каждого пакета: при создании пакета система запоминает значение указателя на данные ожидающие отправки. Данное значение может быть позднее использовано для обработки повторной передачи пакета. Этот указатель полностью статичен.
Указатель начала данных – показывает где начинаются пользовательские данные в буфере отправки. Неважно, были ли они отправлены или лишь ожидают её, данный указатель может быть передвинут лишь потоком отвечающим за удаление данных из буфера (обработчиком отчётов получателей). Глава 3 Разработка и описание алгоритмов Р2М Указатель на данные, ожидающие отправки, – показывает, откуда должны браться данные для создания пользовательской нагрузки следующего пакета. Данный указатель перемещается потоком, отвечающим за генерацию и отправку пакетов.
Указатель конца данных – место где заканчиваются пользовательские данные в буфере. Этот указатель двигается только потоком пользователя посредством предоставления новых данных для отправки экземпляру P2M.
Как уже было замечено, это приводит к делению буфера на три участка: От указателя начала данных до указателя на данные, ожидающие отправки, - это отражает нагрузку пакетов, которые были посланы, но ещё не подтверждены всеми получателями. При этом, в случае успешного подтверждения, данные могут быть удалены путём перемещения указателя начала данных. От указателя на данные, ожидающие отправки, до указателя конца данных - отражает поле деятельности потока, ведущего непрерывную генерацию и отправку новых пакетов, в случае если размер этой области не равен 0. От указателя конца данных до указателя начала данных - поле деятельности потока пользователя. В данную область происходит сохранение новый пользовательских данных при условии что размер этой области не меньше, чем объём данных поступающих от пользователя. Глава 3 Разработка и описание алгоритмов P2M
При такой архитектуре каждый поток работает в своей области и даже теоретически не может возникнуть ситуации пересечения областей. Это позволяет избежать блокировок, характерных для многопоточной среды.
В случае с буфером приёма ситуация идентична, но присутствуют некоторые специфические модули, отвечающие за сохранение данных пакета в необходимом месте буфера с учётом потерь в сети, если они имели место. В целом же, логика работы нисколько не отличается и будет косвенно разобрана при рассмотрении принципов работы остальных компонентов P2M.
Ядром P2M является так называемое “хранилище метаинформации”. Оно является областью динамической памяти, которая хранит в себе информацию о всех посланных, но не подтверждённых (или не до конца подтвержденных) пакетах. Соответственно, любая операция из приведённого списка проводиться при участии хранилища метаинформации (ХМИ):
Создание нового пакета – в ХМИ будет занесена полная информация о пакете: время отправки, размер, указатель на область памяти, откуда была сформирована пользовательская нагрузка.
Запрос на повторную передачу пакета – ХМИ вернет информацию о том откуда необходимо взять пользовательскую нагрузку для вновь переданного пакета
Обработка положительных подтверждений от получателей (ACK ARQ) – учёт числа подтверждений определённого пакета Обработка случаев потерь ACK ARQ Удаление данных из буфера отправки – ХМИ самостоятельно решает когда данные можно безопасно удалить из буфера отправки. Важно определять это правильно, поскольку операция является необратимой (не существует способа уведомить пользователя о необходимости предоставления определённых данных ещё раз) Глава 3 Разработка и описание алгоритмов P2M
Каждая из приведённых операций является жизненноважной для нормальной работы протокола и, более того, значительно влияет на производительность протокола в целом (в силу частого повторения операций). В связи с этим существует проблема организации подобного хранилища данных для высокоскоростных протоколов. В случае с передачей данных нескольким получателям ситуация усложняется необходимостью обрабатывать подтверждения от разных получателей. Соответственно, число подтверждений возрастает в N раз, где N – число получателей. Это накладывает строгие рамки на производительность данного хранилища.
Идея реализовать подобное хранилище, используя классические контейнеры STL (с++ Standard Template Library), как например std::vector, не оправдала себя в связи с тем, что контейнеры STL не являются безопасными при работе в многопоточной среде. Существует альтернатива в виде TBB (Thread Building Blocks от Intel), которая может выступать как основа для построения подобного хранилища. При этом есть ряд неопределённостей с TBB, как например поведение объектов TBB на различных уровнях оптимизации (компилятором) машинного кода (в случае CPU, отличного от Intel). Это привело к реализации собственного хранилища, которое, забегая вперёд, показало очень положительные характеристики в экспериментах.
ХМИ в P2M является структурой данных реализованной в выделенной динамической памяти (heap), представляющей собой таблицу, где в первой колонке хранится ключ для доступа к данным, хранящимся во второй колонке. Данная таблица удовлетворяет нескольким условиям: необходимые данные можно найти, лишь зная ключ к ним; в определённый момент времени каждый ключ в таблице уникален; размер таблицы не может изменяться ни при каких условиях; данные в таблице всегда отсортированы по значению ключа; минимальный ключ не всегда находится на первой позиции; ключи имеют возможность меняться с течением времени. Разработка и описание алгоритмов Р2М Выполнение этих шести условий является необходимым набором требований к структуре данных. В ХМИ ключом является так называемый дескриптор – целое неотрицательное число, являющееся уникальным идентификатором каждой ячейки. Данными является некоторая информация о IP-пакете. Структура ХМИ представляет собой некую логическую модификацию std::map, приведённую на рисунке 3.6 Эта модель была взята за основы ХМИ, техническая реализация и функционал которого будут рассмотрены далее.
Влияние вариации задержки на производительность р2м
Как было показано в [5],[17], [44], вариация задержки (джиттер) часто является существенным препятствием для протокола, работающего на высоких скоростях. Стоит пояснить, что под вариацией задержки понимается разница во времени следования (сетевая задержка пакета из конца в конец) двух последовательных пакетов. Причиной вариации задержки чаще всего являются кросс-трафик и наличие маршрутизаторов на пути следования. В идеальном случае, пакет попадает в очередь обработки маршрутизатора и немедленно перенаправляется на соответствующий порт. В реальности кросс-трафик попадает в ту же очередь и «вклинивается» в существующий поток данных. Это приводит к эффектам «разрежения/уплотнения» потока пакетов. Кроме того, причиной джиттера также является перегрузка промежуточных устройств, приводящая к неодинаковому времени обработки последовательных пакетов. Ещё одна скрытая причина появления джиттера - это проблема точного определения временных интервалов на стороне отправителя пакетов. Важным является также тот факт, что джиттер чаще всего наблюдается на достаточно высоких RTT. По этой причине, эксперименты с P2M проводились на RTT в 150 мс. Рисунок 4.4 показывает тенденции изменения скорости передачи данных на один поток в зависимости от величины джиттера. На данном примере явная зависимость просматривается лишь для случая без потерь (плавное снижение скорости передачи данных). Это объясняется тем, что сам по себе джиттер опасен ложным срабатыванием механизмов определения потерь в протоколе. Это означает, что уже при наличии константных потерь в 0.2 % эффекты присутствия джиттера размываются на фоне эффектов от наличия потерь. В случае же без потерь влияние явно наблюдается.
Если сравнить результаты исследования протокола, приведённые в 4.1.2, то влияние джиттера становится более заметным. Рисунок 4.5 демонстрирует разницу в скоростях передачи данных для протокола P2M при наличии джиттера и без него. Фиксированные значения эксперимента: вариация задержки - 0.6 мс и RTT 150 мс. На графике явно видно уменьшение скорости при наличии джиттера в сети. Как уже было показано ранее, для получения наиболее достоверных эффектов от вариации задержки требуется проводить измерения при отсутствии потерь в сети.
На графике (Рисунок 4.6) приведена расширенная зависимость скорости передачи данных от вариации задержки. Явно просматривается значительное уменьшение скорости передачи данных при возрастании джиттера. Это объясняется ложным срабатыванием механизма детектирования задержек в Р2М, количество которых возрастает с возрастанием вариации задержки. На уровне 2 мс джиттера наблюдается уже более чем 30 % снижение скорости передачи данных. Следует пояснить, что наличие вариации задержки в 2 мс означает наличие значительных
Основной проблемой при борьбе с джиттером является то, что единственным действенным методом избавления от вариации задержки является наличие дополнительного буфера, обеспечивающего равномерность межпакетных интервалов. Однако в случае с высокоскоростной передачей данных наличие дополнительного буфера неизбежно приведет к снижению скорости передачи данных в связи с дополнительным копированием и, как следствие, дополнительной нагрузкой на CPU. Другим способом является приобретение услуг вида IaaS (Infrastructure as a Service), что означает аренду инфраструктуры для передачи трафика. Такие услуги зачастую являются достаточно затратным мероприятием и, более того, не всегда возможны в определённых регионах.
Последний фактор не имеет места в проводимых экспериментах по причине того, что контроль выполнения определённых системных требований к приложению лежит на администраторе сети/инфраструктуры, а не на протоколе. В ходе эксперимента каждый из трёх получателей запускался на одинаковых серверах, что в определённой производителем мере гарантирует равенство всех получателей с точки зрения вычислительной мощности. В то же время первые два фактора являются реалистичным развитием событий, которые должны быть протестированы. В P2M существует два варианта развития событий при возникновении «медленного получателя»: отключение получателя из группы; подстройка скорости под медленного получателя.
В данном разделе будет рассмотрен второй случай как наиболее интересный с точки зрения поведения протокола. На Рисунок 4.7 приведены два вида сценариев: красный – нормальная передача данных (равномерные потоки), синий – передача данных в одном из потоков замедлена введением дополнительных джиттера/задержки/потерь по отдельности и вместе (режим комби). Значение скорости передачи данных, как и раннее, среднее на один поток. Описания режимов приведены в Таблица 4.1. Каждый режим соответствует определённой комбинации параметров джиттера/RTT/потерь. Красные столбцы отражают скорость передачи, полученную при равномерной передаче данных (RTT 150 мс, потери 0,1 %, джиттер 0,1 мс).