Оценка дисперсии производительности алгоритма предотвращения насыщения в сети передачи данных

Проблема распределенного управления и справедливого разделения ресурсов инфраструктуры между источниками данных носит фундаментальный характер для обеспечения функционирования и развития глобальных сетей передачи данных. Современная парадигма распределенного управления, предложенная в 1974 году [1], не предполагает использование механизмов резервирования каналов и/или ресурсов маршрутизаторов источниками данных1. Маршрутизаторы различных уровней сети отличаются по уровню производительности и набору аппаратного обеспечения, однако функционально являются однородными, обеспечивая трансляцию кадров локальных сетей и перенаправление дейтаграмм в соответствии с таблицами маршрутизации.

Интенсивное развитие методов распределенного управления началось, когда в 1984 году был описан, а в октябре 1986-го наблюдался так называемый коллапс перегрузки (congestion collapse) [2]. Анализ этого явления показал, что из-за переполнения очереди промежуточного маршрутизатора сеть была полностью заполнена повторно отправленными данными. При этом новые данные в сеть не поступали. Для решения проблемы был предложен ряд новых методов. Согласно последним, функции распределенного управления реализуются источниками данных, которые, следуя специальным алгоритмам, на основе сигналов обратной связи согласованно

наращивают или сокращают пропускную способность соединений.

В частности, такими алгоритмами успешная доставка данных интерпретируется как свидетельство о наличии в сети свободных ресурсов, а событие потери данных трактуется как сигнал обратной связи, означающий, что загрузка каналов и маршрутизаторов близка к критическим значениям. В первом случае алгоритм наращивает производительность, во втором уменьшает ее. Актуальность задач анализа производительности таких протоколов весьма высока как из-за быстрого роста масштабов сети, так и ввиду диверсификации носителей сигнала и сетевых приложений. Основные механизмы распределенного управления реализуются протоколом Transmission Control Protocol (TCP), который контролирует соединения на уровне точка – точка. Заметим, что этот протокол является единственным программным модулем в архитектуре OSI, реализующим такие функции.

Одним из важнейших алгоритмов, включенным во все существующие реализации TCP, является алгоритм предотвращения насыщения Congestion Avoidance (CA)2. Для утилизации доступной мощности канала связи и одновременного контроля доставки данных TCP использует механизм скользящего окна. Скользящее окно – это объем данных, которые источник может отправить в сеть без подтверждения об их доставке.

Алгоритм CA управляет размером скользящего окна. Если доставка данных подтвержда- ется получателем, то размер скользящего окна линейно возрастает со скоростью b, где последняя определяется величиной времени кругового оборота и реализацией протокола. Если источник получает сведения о потере данных, то размер скользящего окна уменьшается в 0 < 1/α < 1 раз. Стандарт IETF [3] определяет α = 1/2, реализации могут использовать другие значения. Если сведений о доставке данных не было получено вовсе, то алгоритм CA прекращает передачу данных, включает механизм случайной отсрочки и передает управление алгоритму Slow Start. Однако стабильное TCP-соединение, для которого уровень потерь данных на сетевом маршруте не превышает 2,5 %, большую часть времени находится под управлением алгоритма CA. Анализ производительности TCP-соединения под управлением пары алгоритмов Slow Start и CA проведен в работе [4].

Подавляющее большинство исследований производительности алгоритма CA посвящены анализу математического ожидания его пропускной способности для разных видов потоков потерь данных. Анализу моментов более высокого порядка и анализу центральных моментов в литературе практически не уделяется внимание. Исключение составляет [5], где получена дисперсия алгоритма CA при условии, что потери данных являются случайным точечным процессом; ряд работ, где получены преобразования Лапласа для стационарного распределения (см., например, [6]) пропускной способности, а также [7], где построен точный численный алгоритм линейной сложности, позволяющий рассчитать стационарное распределение скользящего окна в условиях, когда потери данных описываются распределением Бернулли.

Однако качество услуг, предоставляемых большинством современных приложений (например, видео- и аудиопотоки), также существенно зависит от дисперсии пропускной способности потока. Поэтому оценки математического ожидания не дают информации, достаточной для дальнейшего анализа и эффективного решения задач проектирования и администрирования сетей. Кроме того, в настоящее время разработано более десятка экспериментальных версий протокола TCP, имеющих целью улучшить утилизацию широкополосных каналов связи и адаптировать свойства протокола к свойствам беспроводных носителей сигнала. В частности, протокол TCP CUBIC [8] используется по умолчанию в ОС Linux, начиная с версии 2.6.19. Характеристики производительности новых протоколов изучены весьма слабо, однако если для сравнения математических ожиданий пропускной способности имеется теоретическая основа, то дисперсия стандартного алгоритма CA также изучена слабо. Использование полученных в литературе преобразований Лапласа для расчета дисперсии требует громоздких вычислений, следовательно, построение аналитических оценок дисперсии алгоритма CA является весьма актуальным.

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

ПОСТРОЕНИЕ ОЦЕНКИ ДИСПЕРСИИ

Определим X ( t ) е R + объем данных, которые источник может отправить в сеть без получения подтверждения от получателя в момент времени t . Пусть на интервалах [ q n , q n + 1 ) n = 0,1, ... имеет место X(t)=X(t₀)+b(t-t₀)," [t o ,t] С [ q n , q n + 1 ), где b ^-1 = E[ X _n ] математическое ожидание времени кругового оборота сегмента данных. В случайные моменты времени { 0 _n } n > 0 процесс { X ( t ) } t > 0 совершает скачок вида X ( 0 _n + 0) = a X ( 0 _n ), где 0 < α < 1. При этом последовательность

⁰ n + 1 j X ( т ) d т 0 _n

(объем данных, последовательно доставленных получателю без потерь) образует процесс восстановления с абсолютно непрерывной функцией восстановления G ( у ) = P ( s_n <  у ), имеющей конечные моменты первого и второго порядков, E [ s_n ] = Х^{- 1} , Х> 0 и E [ s_n 2 ] <  . Пример траектории процесса X (t) представлен на рисунке.

Пример траектории размера скользящего окна

Определим последовательность { X_n = X ( 0 _n ) } n > 0 . Заметим, что из геометрических соображений для последней имеет место соотношение

X 2 + 1 =a ² X 2 + 2 bs n .           (1)

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

• 1.    Определяется последовательность случайных величин { 8 _n } n > o , где 8 _n - это интервал времени между двумя последовательными событиями потерь данных.

• 2.    Определяется последовательность случайных величин { s n } _n > 0 , где s n - объем данных, отправленных последовательно без потерь. Например, если предполагается, что потери сегментов происходят независимо с вероятностью p, то распределение s _n определяется по схеме Бернулли.

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

Если в качестве основного параметра модели используется распределение P { S n =6 _{n + 1} -6 _n <  x } , как это сделано, например, в работе [5], тогда рекуррентное соотношение

X n + 1 = aX „ + b 8 n             (2)

позволяет получить точное значение стационарного математического ожидания Xn в виде lim[ Xn ] = A- E[Sn ] n ^~      1 — a и затем вычислить дисперсию стандартным способом.

Однако идентификация параметров последовательности S n требует более сложных вычислений, а также получения данных из ядра ОС. Соответствующая выборка, как правило, имеет значительно меньший объем, чем выборка, которую, в некоторых случаях, можно построить для идентификации параметров последовательности s_n . Кроме того, связь между уровнем потерь данных и производительностью алгоритма CA является фундаментальной характеристикой протокола TCP. Поэтому в подавляющем большинстве работ именно характеристики объема данных, переданных последовательно без потерь, являются параметрами моделей производительности протокола TCP. В этом случае соотношение (1) позволяет получить явное выражение для второго начального момента, на основе которого в литературе строится оценка математического ожидания с помощью неравенства Гельдера. Последняя непригодна для построения оценок дисперсии.

Теперь построим оценку стационарного математического ожидания размера скользящего окна, не используя неравенство Гельдера. Опираясь на (1), получим

X 2 ₊ n = 2 b t a ² ' st + n — i            (3)

i = 0

или

X = . ^{k + n}

n

2 b t a ²s_k + n — i .

i = 0

Последнее выражение можно преобразовать к виду:

n ta i^t+n —i .

i = 0

X k+n

Тогда

n

E[ X t + n ] = E 2 b t a ² i s t + n — i N i = 0

n

<

i = 0

^sk + n — i .

Здесь и далее будем предполагать, что предел

E [ X ]= limE [ Xn ]

n ^^

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

E [ X ]= limE [ Xn ]< n ^^

n                  2 b

< v2 b lim t ^{a E} Г 4s — ^] = -—E г js n ⁿ ^~ i = 0    ^{L J 1 — a L}

Теперь заметим, что, согласно (3),

n lim E Г X21 = 2 b lim t E Г a2 isn—11 =-----E [ sn ] (5)

n ^^ l _i n ^^ i =0 *- -I 1 — a²

и, значит,

E [ X ]< /-X- e [ sn ].

V1 — a2

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

Теорема 1. Если функция распределения G (y) такова, что имеет место неравенство

E Г V s ; ]<. 1 1 —^ E [ s n ] ,          (6)

L J \ 1 — a то для стационарной дисперсии D последовательности {Xn } имеет место

D >  2b

E[ s „ ] 1 — a ²

V

E ² [ ^ s n ^] ( 1 — a ) 2 /

ПРИМЕРЫ

Положим значения b = 1 и а = 1/ 2, которые используются большинством реализаций протокола TCP. Тогда условие теоремы примет вид

где n – число степеней свободы. Используя оценки, построенные выше, получим

E [ 4s” ]

<

Оценки математического ожидания, получен-

ные выше, примут вид:

E [ X ]< 2V2E [ 4S ] и E [ X ]< ^ 3e [ S” ].

2 4 _гГ 2 ” ±1 I 4

Пример 1. Пусть s n удовлетворяют показательной функции распределения и G ( у ) = 1 - e ^-Л y .

Тогда

E [ S ” 1 = ¹

Л

Условие теоремы 1 выполняется, например, для n = 10.

и

E

Условие теоремы не выполняется, следовательно, оценка (7) не может быть использована.

Пример 2. Пусть s n удовлетворяют χ -распределению Пирсона. Тогда его моменты имеют

вид:

ЗАКЛЮЧЕНИЕ

Работа посвящена анализу дисперсии размера скользящего окна алгоритма предотвращения насыщения (Congestion Avoidance) протокола Transmission Control Protocol. Размер скользящего окна является ключевой характеристикой производительности протокола TCP, а его дисперсия – важным параметром для многих современных приложений сетей передачи данных. В работе построена модель эволюции размера скользящего окна, получена оценка его математического ожидания без использования неравенства Гельдера. Получена оценка стационарной дисперсии снизу и доказана теорема об условии ее применимости. Приведены примеры анализа условия теоремы.

ПРИМЕЧАНИЯ

• ¹    Заметим, что такие механизмы существовали в сети передачи данных, использовавших, например, комплексные стандарты X.25 или X.110, а также в сети «Автодин» Министерства обороны США. Однако эти технологии не получили широкого распространения и были вытеснены сетевыми стандартами DARPA.

• ²    Последовательно использовались версии Tahoe, Reno, NewReno. Дальнейший анализ проводится для версии NewReno.

• ³    Более подробно см. [5].

• ⁴    Заметим, что последняя оценка совпадает с оценкой, полученной в [9] для детерминированного потока потерь данных.

ESTIMATION OF PERFORMANCE VARIANCE FOR NETWORKING CONGESTION AVOIDANCE ALGORITHM