Содержание к диссертации
Введение
1. Управление потоком: аналитический обзор и выбор направлений работ 10
1.1. Архитектура сетей передачи данных 11
1.2. Транспортный уровень и протокол TCP 12
1.3. Управление потоком и управление перегрузкой 14
1.4. Дополнительные функциональные возможности транспортных протоколов 23
1.5. Анализ моделей процедур управления потоком и перегрузкой 26
1.6. Выводы о направлении исследований 32
2. Модели процедур управления потоком в замкнутом тракте передачи данных 35
2.1. Модели процедур управления потоком в замкнутом однозвен ном тракте 35
2.2. Сравнительный анализ селективной и групповой процедур отказа в однозвенном тракте 41
2.3. Модель селективной процедуры управления потоком в замкнутом многозвенном тракте 47
2.4. Модель групповой процедуры управления потоком в замкнутом многозвенном тракте 53
2.5. Сравнительный анализ селективной и групповой процедур отказа в многозвенном тракте 59
2.6. Выводы 71
3. Модели процедур управления потоком в нагруженном тракте передачи данных 73
3.1. Модель селективной процедуры отказа в нагруженном тракте передачи 73
3.2. Анализ селективной процедуры отказа в нагруженном тракте 79
3.3. Исследование доступной полосы пропускания селективной процедуры отказа в нагруженном тракте передачи 86
3.4. Выводы 92
4. Математическое моделирование процедур управления перегрузкой 94
4.1. Математическое моделирование режимов медленного старта и обхода перегрузки 94
4.2. Математическое моделирование обнаружения потерь по тайм-ауту и подтверждениям-дублям 104
4.3. Математическое моделирование режима быстрого восстановления, алгоритма Карна и селективных подтверждений 119
4.4. Измерения пропускной способности процедуры TCP Reno. 140
4.5. Сравнительный анализ результатов представленных моделей. 141
4.6. Выводы 151
Заключение 153
Литература 155
- Управление потоком и управление перегрузкой
- Модель селективной процедуры управления потоком в замкнутом многозвенном тракте
- Анализ селективной процедуры отказа в нагруженном тракте
- Математическое моделирование обнаружения потерь по тайм-ауту и подтверждениям-дублям
Управление потоком и управление перегрузкой
Управление потоком - это функция регулирования количества данных, передаваемых отправителем. TCP является протоколом, основанным на механизме решающей обратной связи [85,152]: адресат должен подтвердить данные, переданные отправителем. Параметр «окно» (window) обозначает количество данных, выраженное в байтах, которое отправитель может передать не дожидаясь подтверждения. Чем больше размер окна, тем выше пропускная способность транспортного соединения, так как по сути размер окна -это количество байт, передаваемых за время круговой задержки. Так, например, если время круговой задержки составляет 50 мсек, а размер окна -64KB, то транспортное соединение способно достичь пропускной способности, равной 10.24 Мбит/сек. Размер окна, анонсируемый получателем, определяется настройками стека TCP/IP, и, обычно, ограничен размером буферного пространства, выделенного транспортному соединению для размещения поступающих сегментов.
Выбирая размер окна, получатель никаким образом не проверяет, способна ли сеть обработать поток, порожденный таким окном. В первичной спецификации TCP [152] не определены механизмы, позволяющие оценить количество свободных ресурсов в сети передачи данных. Следствием этого стала серия коллапсов (congestion collapse) в результате перегрузки сетевых ресурсов трафиком протокола TCP в 80-ых годах. Коллапс - это явление, при котором лишь малая часть всех сетевых ресурсов расходуется на передачу полезного трафика. Основная же часть ресурсов расходуется непродуктивно.
Количество трафика, передаваемого протоколом TCP, превышало количество доступных сетевых ресурсов. В результате этого появлялись большие очереди на сетевых интерфейсах транзитных маршрутизаторов, что в свою очередь приводило к значительному увеличению времени круговой задержки. В тот момент, когда время круговой задержки превышало величину тайм-аута ожидания подтверждения, TCP начинал передавать сегменты, не потерянные, но еще не дошедшие до получателя, повторно, что лишь усиливало перегрузку сети. В тот момент, когда очереди заполнялись на 100%, маршрутизаторы начинали сбрасывать пакеты, на обработку и буферирова-ние которых у них не было ресурсов. Потери в свою очередь приводили к еще большему количеству повторных передач. В результате в сети передачи данных в транзите между отправителем и получателем находилось много копий одного и того же сегмента данных, т.е. большая часть доступной полосы пропускания расходовалась на «непродуктивные» повторные передачи.
Для борьбы с явлением коллапсов было предложено расширить TCP функцией управления перегрузкой (congestion control). Одной из первых публикаций, посвященных проблеме контроля перегрузки и получивших широкое распространение, является [166].
Управление перегрузкой - это способность TCP не перегружать сеть своим потоком. Основной идеей управления перегрузкой является изменение скорости передачи информации (т.е. изменение размера окна отправителя) в зависимости от текущей загрузки сети передачи данных. Процедуры управления перегрузкой используют различные виды обратной связи, получаемые от сети, для принятия решений по изменению скорости передачи. Такой обратной связью могут быть интенсивность потери пакетов, время круговой задержки или же явное уведомление о перегрузке [154].
Также стоит отметить, что в данной работе рассматриваются лишь оконные методы управления потоком и перегрузкой, так как именно они закреплены в серии стандартов, выпущенных IETF, и получили широкое распространение.
Базовая спецификация TCP, описанная в [152], вводит только понятие управление потоком, а проблема управлению перегрузкой остается неосвещенной.
С 1988 года, когда была опубликована работа [166], было предложено множество механизмов управления перегрузкой в TCP: Tahoe [166], Reno [53], New-Reno [94], SACK [65,92,139], Vegas [69], High-Speed TCP [93], Scalable TCP [120], BIC [172], CUBIC [155], Hybla [71], Veno [96], Westwood [138], Illinois [132], YeAHCP [63], HTCP [161], FAST [113], CTCP [164], CHD [109], CDG [108], FIT [169], LP [129], и др.
Однако, только Tahoe, Reno, NewReno и SACK достигли статуса IETF стандарта и реализованы практически во всех современных ОС. Многие операционные системы имеют реализации некоторых дополнительных методов контроля перегрузки. Так, например, операционная система Linux поддерживает 13 реализаций TCP 2 [72]: NewReno, Vegas, Veno, Westwood+, BIC, CUBIC (является методом по-умолчанию, начиная с ядра 2.6.18), HSTCP, Hybla, Scalable, Illinois, YeAH, HTCP, LP. OS FreeBSD имеет реализацию 6 методов управление перегрузкой [91]: NewReno (является методом по-умолчанию, начиная с версии 9.0), CUBIC, HTCP, CHD, HSTCP, Vegas. А операционные системы компании Microsoft, начиная с версий Windows Vista/Windows Server 2008, имеют всего две реализации [85]: NewReno и СТСР.
Модель селективной процедуры управления потоком в замкнутом многозвенном тракте
Аналогично определениям, введенным в п. 2.1 будем считать, что w -это размер окна передачи управляющего протокола, a S - величина тайм-аута ожидания подтверждения (S w). Тактом мы будем называть время t: необходимое для передачи пакета в отдельном звене.
Динамика очереди переданных, но не подтвержденных сегментов на узле-отправителе для селективной процедуры функционирования управляющего протокола описывается цепью Маркова с дискретным временем и числом состояний равным S (см. рис. 2.7). Го 1-Г-о
Цепь Маркова, моделирующая динамику очереди отправленных, но неподтвержденных сегментов в узле-отправителе с селективной процедурой отказа для многозвенного тракта. Переходные вероятности цепи Маркова 7 в многозвенном тракте для селективного отказа имеют вид:
Так как, исходя из условий моделирования, время круговой задержки составляет 2D тактов, то первое подтверждение отправитель получит не раньше, чем через 2D тактов после начала передачи. Кроме того, данное подтверждение, как и любое другое, не несет в себе информации о судьбе последних 2D — 1 переданных сегментов. Ввиду вышесказанного очевидно, что из состояния 0 в состояние 1, из состояния 1 в состояние 2, и так далее вплоть до перехода из состояния 2D — 2 в состояние 2D — 1 узел-отправитель переходит с вероятностью детерминированного события. Дальнейший рост очереди неподтвержденных сегментов происходит с вероятностью искажения подтверждения в обратном канале. При получении подтверждения процедура управления передачей с селективным режимом отказа использует следующую логику: 1. Получение подтверждения в состоянии і (і = 2D — l,w — 1) вызывает переход в состояние 2D — 1, тж. поступившее подтверждение не несет информации об успешности передачи последних 2D — 1 переданных сегментов.
2. При получении квитанции отправителем в состоянии і (і = w,w + 2D — 3) происходит переход в состояние номер w + 2D — 2-і, т.к. поступившая квитанция несет информацию об успешности передачи всех сегментов кроме последних w + 2D — 2-і, которые не были подтверждены и находятся в очереди повторной передачи.
3. При получении подтверждения в состоянии і (і = w + 2D — 2,S — 2) происходит переход в состояние 0, так как становится известна судьба всех без исключения переданных сегментов.
Если отправитель переходит в состояние с номером 5-1 и в течение следующего такта не получает подтверждения (данное событие наступает с вероятностью 1 — F0): то вне зависимости от модели подтверждений происходит переход в состояние номер 0 с последующей повторной передачей содержимого очереди. Если, находясь в состоянии с номером 5—1, узел-отправитель получает квитанцию (событие наступает с вероятностью неискажения квитанции F0): то все равно происходит переход в состояние номер 0, но начинается передача новых сегментов.
Определим пропускную способность рассматриваемого многозвенного тракта передачи аналогично (2.3) в соответствии с определением, данным в [4], как отношение среднего объема данных, передаваемых до получения квитанции, к среднему времени получения квитанции: где L - это размер передаваемых сегментов (например, MSS, максимальный размер сегмента), t - среднее время между поступлением подтверждений, w -среднее количество сегментов, переданных верно, между последовательным получением подтверждений. Так как подтверждения переносятся в каждом сегменте независимо, то, согласно введенным предположениям, время прихода квитанции распределено по геометрическому закону с параметром F0. Следовательно, среднее время между поступлением квитанций можно представить в виде (2.4).
Расчет среднего количества сегментов w: передаваемых верно между последовательными поступлениями подтверждений, согласно [45] с учетом влияния длительности тайм-аута ожидания уведомления о корректности приема последовательности сегментов выполняется из соотношения:
В случае превалирования ширины окна над двойной длиной тракта передачи данных (w 2D) и тайм-аута, ограниченного с двух сторон неравенством w + 1 S 2D + if — 1, решение системы уравнений равновесия преобразуется к виду:
Анализируя и сопоставляя (2.35-2.41), а также учитывая выражения (2.4), (2.6) и (2.7) из параграфа 2.1, и выражение (2.42) получаем окончательное выражение нормированной пропускной способности управляющей процедуры селективного режима Z (w, S, D) функционирования протокола транспортного уровня в многозвенном тракте.
Если отправитель переходит в состояние с номером 5-1 и в течение следующего такта не получает подтверждения (данное событие наступает с вероятность 1 —F0), то вне зависимости от модели подтверждений происходит переход в состояние номер 0 с последующей повторной передачей содержимого очереди. Если, находясь в состоянии с номером 5-1, узел-отправитель получает квитанцию (событие наступает с вероятностью неискажения квитанции F0): то все равно происходит переход в состояние номер 0, но начинается передача новых сегментов. Формула пропускная способность рассматриваемого многозвенного тракта передачи представлена в выражении (2.35). Расчет среднего количества сегментов w: передаваемых верно между последовательными поступлениями подтверждений, выполняется в соответствии с выражением (2.36).
Анализ селективной процедуры отказа в нагруженном тракте
Расчет операционных характеристик сетей СМО с конечными буферными накопителями в транзитных узлах либо крайне сложен, либо вообще невозможен в силу высокой размерности задачи, особенно в постановке с дискретным временем [14,48]. В силу этого в данной главе предлагается индикаторный подход, основанный не на потоковых характеристиках, а на индикаторных показателях, являющихся следствием высокой нагрузки.
Очевидно, что индикатором нагрузки на тракт передачи данных являются очереди в узлах на пути следования сегментов транспортного потока. Если по результатам наблюдений и измерений вдоль маршрута удается задать распределение длин очередей, то можно перейти от потоковой модели в виде сети СМО к индикаторной модели виртуального соединения.
В данной главе предложена модель асинхронной процедуры управления виртуальным соединением транспортного протокола с селективным режимом отказа в виде двумерной цепи Маркова с дискретным временем. Модель учитывает влияние протокольных параметров размера окна и длительности тайм-аута ожидания сквозных квитанций, длину пути, вероятности искажения пакетов в отдельных звеньях тракта передачи данных и распределение длин очередей в транзитных узлах от «внешних» потоков на пропускную способность виртуального соединения.
Рассмотрим обмен данных между узлами, соединенными многозвенным трактом передачи произвольной длины. Предположим, что выполняются следующие допущения: 1. Узлы тракта соединены дуплексными каналами связи; 2. Все каналы связи имеют одинаковые пропускные способности в обоих направлениях; 3. Время обработки пакетов в источнике, адресате и транзитных узлах тракта одинаково; 4. Длина тракта передачи от источника до адресата, выраженная в количестве участков переприёма, равна D; 5. Длина обратного тракта передачи от получателя до отправителя также равна D; 6. Источник и адресат имеют неограниченный поток данных для передачи; 7. Обмен выполняется транспортными сегментами одинаковой длины; 8. Потерь пакетов из-за отсутствия буферной памяти в узлах тракта не происходит; 9. Вероятности потери пакетов в прямом направлении передачи равна Rni: а вероятности потери в обратном направлении - R0i: где і определяет номер участка переприёма в многозвенном тракте; 10. Потери пакетов являются независимыми случайными событиями; 11. Получатель использует селективную процедуру формирования подтверждений; 12. Задана функция вероятностей Ъп (п = 0, N) того, что каждый сегмент из потока анализируемого соединения в транзитном узле встретит очередь размера п N: где N - максимальный размер очереди, определяемый емкостью буферных пулов транзитных узлов.
Вероятности потери пакетов при передаче в прямом и обратном направлениях тракта (Rn, R0)i а также достоверности передачи Fn и F0: являющиеся величинами обратными к потерям, вычисляются на основе Rni и R0i по формулам (2.31 - 2.33).
Тайм-аут длительности S запускается перед началом передачи первого сегмента последовательности и фиксируется для всех сегментов в пределах ширины окна. Будем считать, что размер окна управляющего протокола определяется величиной w: a S - задает длительность тайм-аута ожидания подтверждения корректности доставки данных. При этом w 2D, & S w. После передачи очередного сегмента, протокол копирует его в очередь переданных, но не подтвержденных данных и запускает тайм-аут. Как только размер очереди становится равным ширине окна w: управляющий протокол приостанавливает передачу в ожидании получения квитанции или истечения тайм-аута S ожидания подтверждения. При получении подтверждения, из очереди удаляются сегменты, дошедшие до адресата без искажений. При истечении тайм-аута S соответствующий сегмент передается повторно, и тайм-аут запускается вновь.
Будем называть тактом время t: необходимое для вывода сегмента в линию. Такт определяется суммой времени вывода сегмента в линию, времени распространения сигнала в канале связи и времени обработки сегмента принимающим узлом. Полагаем, что повторная передача сегментов организована в соответствии с селективной процедурой отказа. Тогда время получения отправителем сквозной квитанции распределено по геометрическому закону с параметром F0 и длительностью такта дискретизации t.
Динамика очереди переданных, но не подтвержденных сегментов на узле-отправителе может быть описана двумерной цепью Маркова с дискретным временем и числом состояний по одному измерению, равным длительности сквозного тайм-аута S: а по другому - увеличенной на единицу максимальной длине очереди: N+1. Очевидно, что длительность тайм-аута должна быть достаточной для того, чтобы пакеты с сегментами данных по прямому каналу достигли адресата и подтверждения получателя по обратному каналу были приняты отправителем потока. Отсюда следует, что размер тайм-аута, выраженный в длительностях тактов t: должен быть не меньше времени полной круговой задержки, состоящей из суммы двойной длины пути и размера максимальной возможной встреченной очереди в транзитном узле: S 2D+N—1. С учетом возможных повторных передач сегментов основного (прямого) потока и сегментов с подтверждениями во встречном потоке из-за искажений в отдельных звеньях тракта размер тайм-аута S целесообразно выбирать с «запасом» на повторные передачи.
Квитанция на первый сегмент последовательности может поступить отправителю через 2D интервалов длительности t: необходимых для достижения первым сегментом адресата и возвращения отправителю подтверждения о корректности его приема. Если при передаче последовательности сегментов отправителем или переносе подтверждения пакет с сегментом в прямом тракте (или подтверждением в обратном) встретил очередь размера п, то время, необходимое для получения квитанции, возрастает на размер встреченной очереди п и составит 2D + п.
Функционирование виртуального соединения в нагруженном многозвенном тракте передачи данных с очередями сегментов перед отправляемыми данными или подтверждениями может быть описано марковизированным процессом, в котором размер очереди перед прямым или обратным потоком данных исследуемого соединения является дополнительной переменной w + п + 1, 5 — 1. марковского процесса. В состоянии цепи Маркова (i,n) источник отправил последовательность размера (і — п) сегментов, которая в процессе переноса в одном из звеньев встретила очередь длиной п сегментов. Значениям координаты і = 0,it + n, п = О, N соответствует количество переданных, но не подтвержденных сегментов и время от начала передачи последовательности (і), а значениям і
которого отправитель ожидает получение квитанции. Обозначим через irj переходные вероятности цепи Маркова, где (i,n) - координаты исходного, а (j,m) - измененного состояний цепи. Тогда динамику процесса передачи информационного потока можно задать следующими значениями переходных вероятностей:
Математическое моделирование обнаружения потерь по тайм-ауту и подтверждениям-дублям
Предложенная в п. 4.1 математическая модель процедуры управления перегрузкой учитывает режимы медленного старта и обхода перегрузки. При разработке модели было сделано допущение о том, что протокол обнаруживает факт наличия потерь в текущем окне передачи сразу в конце такта. Данная идеализация процесса обнаружения потерь отличается от методов, применяемых современными транспортными протоколами. В этом параграфе предлагается математическая модель процедуры управления перегрузкой, учитывающая обнаружение потерь по тайм-ауту ожидания подтверждения и по подтверждениям-дублям. Кроме того данная модель является преемственной по отношению к модели, изложенной в п. 4.1.
Механизм обнаружения потерь по тайм-ауту является базовым методом для транспортных протоколов, гарантирующих доставку. Все отправленные, но не подтвержденные данные хранятся в специальной очереди на стороне отправителя. При получении подтверждения соответствующие ему данные удаляются из очереди повторной передачи. В том случае, если подтверждение не было получено в течение определенного интервала времени, наступает тайм-аут ожидания подтверждения, и неподтвержденные данные отправляются повторно. Для отслеживания тайм-аута используется механизм таймеров. TCP сбрасывает значение таймера при получении очередного подтверждения.
Подтверждения-дубли (duplicate acknowledgements, DupAcks) - это сегменты, имеющие одинаковые номера подтверждений (acknowledgement numbers), при установленном флаге АСК [167]. Дополнительная методика обнаружения потерь потребовалась ввиду того, что обнаружение потерь по тайм-ауту является неэффективным способом своевременного обнаружения потерянных или искаженных сегментов. Обнаружение потери по подтверждениям-дублям приводит к неотложной повторной передаче потерянного сегмента. В литературе такой алгоритм обнаружения также называется методом «быстрой повторной передачи» (fast retransmit) [53,85,167].
При обнаружении потерь методом подтверждений-дублей сегмент считается потерянным, если отправитель получил подряд некоторое количество подтверждений-дублей, каждое из которых подтверждает все данные вплоть до первого октета потерянного сегмента, но не включая его. Обычно получение трех подтверждений-дуб л ей, следующих одно за другим, трактуется как потеря соответствующего сегмента [53,85,167].
Обозначим через S величину тайм-аута ожидания подтверждения, выраженную в количестве тактов дискретизации, т.е. интервалов длительностью в одну круговую задержку. Тогда S вычисляется как отношение размера тайм-аута RTO, выраженного в секундах, к длительности круговой задержки RTT, выраженной также в секундах:
Округление вниз является необходимой и оправданной мерой. С одной стороны, необходимо, чтобы S было целочисленным значением, так как оно выражает количество тактов дискретизации. С другой стороны, округление вниз компенсирует среднестатистические 0.5 такта ожидания истечения тайм-аута, прошедшие в такте передачи, в котором случилась потеря.
Дальнейшее моделирование процедуры управления перегрузкой транспортного протокола проведем исходя из следующих допущений: 1. Источник имеет неограниченное количество данных к передаче; 2. Время круговой задержки (RTT) не меняется в процессе моделирования; 106 3. Показатель надежности тракта передачи, выраженные в форме вероятности потери пакета, не меняется в процессе моделирования; 4. Потери сегментов являются независимыми случайными событиями; 5. Обратное направление тракта передачи является абсолютно надежным, т.е. отсутствуют потери сегментов, переносящих подтверждения от адресата к отправителю; 6. Обмен ведется сегментами одинакового размера; 7. Время, необходимое для отправки количества данных, соответствующих окну передачи максимального размера, меньше времени круговой задержки. Дискретная цепь Маркова, моделирующая динамику изменения значений CWND и SSTHRESH, описывается с помощью следующих переходных вероятностей nj
Так как при отсутствии потерь все CWND переданных сегментов достигнут получателя и породят ровно CWND положительных подтверждений, подобное поведение обеспечивает увеличение размера окна передачи в 2 раза за время круговой задержки, но не больше величины порога переключения в режим обхода перегрузки (SSTHRESH). При этом значение SSTHRESH остается неизменным.
Вероятности второй группы описывают изменение параметра CWND при нахождении в режиме обхода перегрузки в случае отсутствия потерь. Каждое положительное подтверждение, получаемое отправителем приводит к увеличению размера CWND на 1/CWND: CWND (4 9)
Так как при отсутствии потерь все CWND переданных сегментов породят ровно CWND положительных подтверждений, каждое из которых увеличит текущий размер окна передачи на 1/CWND, подобное поведение обеспечивает увеличение окна передачи отправителя за время одного такта на 1 сегмент. Значение SSTHRESH также остается неизменным.
Так как величина окна передачи отправителя не может превышать размер, анонсированный получателем, то вероятности третьей группы описывают сохранение значения параметра CWND равным W при условии, что очередной такт прошел без потерь. Ввиду отсутствия потерь параметр SSTHRESH не корректируется.
Переходные вероятности четвертой группы описывают действия про токола в случае наличия потерь в текущем такте при размере окна не превы шающем 3 сегмента для размера SSTHRESH менее 4. Столь малый размер окна не позволит обнаруживать потери по подтверждениям-дублям, так как не наберется достаточного их количества. В результате происходит переход в состояния, соответствующие ожиданию истечения тайм-аута (строки с но мерами большими или равными L / J + 1) (5) Вероятности пятой группы аналогичны вероятностям четвертой группы, за исключении того, что они описывают ту же ситуацию, но для SSTHRESH 4: состояния, соответствующие размеру CWND равного 3, являются невозвратными, так как в них нет переходов из других состояний.
