Известия РАН. Теория и системы управления, 2019, № 1, стр. 13-30

Введение. Одной из актуальных областей приложения теоретических результатов первой части статьи в области анализа и оценивания управляемых марковских процессов является разработка алгоритмического обеспечения протоколов передачи данных транспортного уровня [1]. Их создание и модернизация происходит обычно на основе эмпирических доводов, в основном реактивно, в качестве ответа на существенные объективные изменения аппаратной платформы (например, появление и широкое внедрение беспроводных сетей) или характера пользовательских запросов (например, развитие вредоносной активности типа DOS/DDoS атак).

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

марковские и скрытые марковские модели [2–6],

модели систем массового обслуживания [7–9],

модели, основанные на жидкостной и/или диффузионной аппроксимации скачкообразных процессов [10–13],

модели, основанные на самоподобных процессах [14–17],

конкурентные модели и игры [18–20]

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

Объекты исследования данной работы – транспортные протоколы TCP [1], осуществляющие последовательную передачу данных, разделенных на отдельные сегменты (пакеты). Главная особенность протоколов семейства TCP состоит в гарантированной доставке данных по каналам связи, допускающим потери пакетов. Характеристики канала связи не известны, и стратегия управления передачей данных основывается на обработке статистической информации о результатах передачи предыдущих пакетов, источником которой служит случайный поток подтверждений об успешной передаче пакетов (acknowledgement, ACK). Отправитель соблюдает очередность отправки пакетов, потерянные пакеты подлежат повторной пересылке вне очереди. При стабильной работе канала отправитель постепенно наращивает скорость отправки, тестируя возможности канала, а адресат получает пакеты в том же порядке, в котором они отправлены. В случае успешной доставки очередного пакета k получатель возвращает отправителю подтверждение, содержащее номер данного пакета ${\text{ACK}}\left( k \right)$. Получение пакета с номером, превосходящим ожидаемый по очереди (например, k + 2, когда ожидается k + 1), может означать потерю пакета, на которую получатель реагирует отправкой подтверждения, содержащего номер последнего не нарушающего очередности полученного пакета ${\text{ACK}}\left( k \right)$. Получение четырех подтверждений с одинаковым номером трактуется отправителем как потеря пакета (loss), произошедшая по какой-либо причине. Кроме того, на потерю пакета также указывает отсутствие подтверждения в течение долгого времени (timeout), и такая ситуация считается признаком серьезного снижения качества связи, поскольку свидетельствует о нарушении обратной связи между отправителем и получателем. Обе описанные ситуации требуют от отправителя снижения скорости передачи данных с целью устранения возможной перегрузки и адаптации к изменившимся характеристикам канала. За скорость передачи данных в протоколе TCP отвечает величина окна перегрузки – объема неподтвержденной порции отправленных данных, т.е. числа пакетов, отправленных получателю из узла-отправителя, на которые еще нет подтверждения о доставке. Второй управляемый параметр – тайм-аут повторной передачи – предельное значение времени ожидания ACK, превышение которого трактуется как потеря пакета. Стратегия управления заключается в выборе закона изменения окна перегрузки в зависимости от потоков подтверждений передачи пакетов и их потерь, а также определения тайм-аута повторной передачи, от которого также зависит учет потерянных пакетов.

Ранние версии протокола TCP использовали стратегию AIMD (additive-increase/multiplicative-decrease) линейного роста окна перегрузки на интервалах успешной передачи данных, его мультипликативного уменьшения с каждым фактом потери пакетов и отката к минимальному значению при тайм-ауте. Такая стратегия доказала свою эффективность для проводных каналов связи, отличающихся высокими скоростью и надежностью передачи, где любой факт потери пакета естественно трактовать как признак перегрузки – потери пакета в канале из-за переполнения буфера передачи в каком-либо коммуникационном устройстве в составе канала, а тайм-аут – как динамическое изменение маршрута передачи данных или даже отказ оборудования и временную потерю связи.

Получившие широкое распространение гетерогенные сети, включающие в себя как проводные, так и беспроводные участки, отличаются большими емкостью канала и вероятностью потерь пакетов, а также наличием случайных периодов снижения скорости передачи данных. В таких условиях потеря пакета или превышение тайм-аута повторной передачи не являются однозначным признаком сбоя или перегрузки канала, а могут быть порождены снижением качества связи на беспроводном участке соединения. Поэтому базовые версии протокола TCP, снижающие скорость при любом из указанных событий, склонны недостаточно загружать канал связи и в итоге обеспечивают меньшую, чем возможно, пропускную способность. Кроме того, развитие проводных технологий передачи данных привело к появлению высокоскоростных каналов связи, в которых линейного роста скорости передачи на интервалах успешной передачи данных недостаточно для достижения максимума пропускной способности за разумное время: окно перегрузки растет слишком медленно, и реальная пропускная способность ниже технически доступной. Для учета этих фактов алгоритм управления TCP многократно модернизировался: были предложены версии протокола Illinois [21], Westwood+ [22], Hybla [23], CUBIC [24], BBR [25] и некоторые другие. При этом все авторы отмечают, что знание или достаточно точная оценка текущего состояния соединения позволит повысить его пропускную способность.

Первая часть данной статьи [26] предоставляет математическое обеспечение решения задач анализа и оценивания в стохастических системах наблюдения с марковским скачкообразным процессом (МСП) в роли состояния. Цель второй части состоит в развитии на основе полученных теоретических результатов алгоритмического обеспечения сетевых протоколов TCP для повышения эффективности и устойчивости их работы.

Статья организована следующим образом. Раздел 1 содержит подробное неформальное описание работы сетевого соединения, функционирующего под управлением протокола TCP. В разд. 2 представлена формальная математическая модель функционирования TCP-соединения версии New Reno в виде некоторой управляемой стохастической системы наблюдения с состоянием в форме марковских скачкообразных процессов (МСП). В разд. 3 собраны результаты комплекса проведенных численных экспериментов. Их целями являются:

анализ соответствия свойств предложенной математической модели свойствам реального TCP New Reno,

проверка возможности высокоточного оценивания текущего состояния канала по косвенным статистическим данным потоков ACK, потерь пакетов и тайм-аутов,

демонстрация возможности оптимизации имеющегося протокола TCP New Reno путем учета оценок текущего состояния канала.

Выводы и заключительные замечания даны в разд. 4.

Описание функционирования TCP-соединения. Имеется компьютерное соединение (см. рис. 1), функционирующее по протоколу семейства TCP [1].

Канал, обеспечивающий соединение, состоит из проводного и беспроводного участков. Одно из коммуникационных устройств обладает минимальной производительностью, образуя в канале так называемое “бутылочное горло”. Размер буфера “бутылочного горла” равен $\bar {Q}$.

Информация по каналу передается в форме управляемого потока TCP-пакетов, при этом максимальное число пакетов, которое может одновременно находиться в канале без учета буфера “бутылочного горла”, равно B. Управление передачей данных осуществляется путем выбора окна перегрузки, т.е. числа пакетов U_t, переданных из узла-отправителя, но еще не подтвержденных на момент времени t. Устройства, образующие канал, включая “бутылочное горло”, могут использоваться другими пользователями для передачи данных, что порождает неопределенность и нестационарность характеристик канала. Но основным фактором, влияющим на состояние канала, является, разумеется, управление ${{U}_{t}}$. Текущее состояние канала полностью определяется числом пакетов, передающихся в настоящий момент по его различным участкам, а также ожидающих передачи в буферах коммуникационных устройств. Однако вся эта информация недоступна на передающем узле и не может быть оперативно обработана, поэтому для описания состояния канала связи естественно использовать доступные для оценки косвенные характеристики, такие, как время кругового обращения сегмента данных (round-trip time, RTT), вероятности потери пакета (loss probability, ${{P}_{l}}$) и тайм-аута доставки подтверждения (timeout probability, ${{P}_{{to}}}$) одного TCP-пакета. Предполагается, что в каждый момент времени канал может находиться только в одном из четырех качественно различных состояниях, каждое из которых характеризуется следующим набором параметров $(RT{{T}^{i}},P_{l}^{i},P_{{to}}^{i})$, $i = \overline {1,4} $:

${{{\mathbf{X}}}_{t}} = {{e}_{1}}$ – канал свободен,

${{{\mathbf{X}}}_{t}} = {{e}_{2}}$ – умеренная загрузка канала,

${{{\mathbf{X}}}_{t}} = {{e}_{3}}$ – перегрузка проводного участка,

${{{\mathbf{X}}}_{t}} = {{e}_{4}}$ – деградация сигнала на беспроводном участке.

Время кругового обращения для каждого индивидуального пакета случайно и варьируется во времени. Важным его свойством является то, что при отсутствии проблем на беспроводном участке, т.е. в состояниях e_i, $i = \overline {1,3} $, его моментные характеристики – среднее ${\mathbf{E}}\{ {\text{RT}}{{{\text{T}}}^{{\text{i}}}}\} $ и дисперсия ${\mathbf{D}}\{ {\text{RT}}{{{\text{T}}}^{i}}\} $ – зависят от текущего размера окна перегрузки U_t, т.е. от управления. Вероятность потери TCP-пакета в таком случае также зависит от U_t. Вид этих зависимостей представлен на графиках рис. 2. Вероятность тайм-аута доставки подтверждения $P_{{to}}^{i}$, напротив, не зависит ни от управления, ни от общей загрузки канала, поскольку связана с возникновением технических проблем или сбоем коммуникационного оборудования, таким образом, $P_{{to}}^{1} = P_{{to}}^{2} = P_{{to}}^{3} = {\text{const}}$. Следует отметить, что в силу высокой надежности проводных линий передачи данных эта величина является достаточно малой.

Причины нахождения канала в состояниях e₁, e₂ и e₃ связаны с загрузкой канала потоком данных исследуемого соединения, в то время как пропадание и восстановление сигнала на беспроводном участке происходят независимо от текущей загрузки. Необходимо подчеркнуть, что загрузка канала исследуемым потоком влияет на состояние не однозначно из-за наличия потоков данных других пользователей, одновременно использующих ресурсы канала.

Представленная на рис. 2 зависимость вероятности потери пакета ${{P}_{l}}\left( u \right)$ соответствует применению на коммуникационном оборудовании узла, являющегося “бутылочном горлом” канала, централизованного алгоритма предотвращения перегрузки (переполнения буфера) Random Early Detection (RED) [27]. Начиная с некоторого уровня загрузки $W{\text{'}}$, устройство случайным образом отклоняет или помечает с помощью отметки ECN (explicit congestion notification, явное уведомление о перегрузке), если такая технология доступна, часть пакетов. При этом вероятность отклонения линейно растет с ростом загрузки u. Достигая некоторого порогового значения вероятности отклонения P₁ при уровне загрузки $W{\text{''}}$, устройство начинает отклонять все поступающие пакеты. Подобный алгоритм обеспечивает справедливый равноправный доступ всех пользователей к ресурсам канала.

Кусочно-линейная зависимость среднего ${\mathbf{E}}\left\{ {{\text{RTT}}} \right\}$ и дисперсии ${\mathbf{D}}\left\{ {{\text{RTT}}} \right\}$ времени кругового обращения сегмента данных от загрузки объясняется следующим образом. Пока загрузка u меньше порога B, величина ${\text{RTT}}$ складывается из неслучайного времени распространения сигнала и суммарного случайного времени его обработки на всех коммуникационных устройствах канала. С превышением этого порога к RTT прибавляется случайное время ожидания пакета в очереди “бутылочного горла”. При этом все пакеты обрабатываются независимо друг от друга, и времена обработки пакетов имеют одинаковое распределение. Этот факт объясняет линейный рост среднего и дисперсии в зависимости от u при u > B. Параметры этих функций: сдвиги (${{\delta }_{0}} + {{\xi }_{i}}$ и ϕ_i) и коэффициенты наклона (${{\upsilon }_{i}}$ и ${{\psi }_{i}}$), различаются для разных состояний канала ${{e}_{i}}$.

Состояние e₄ соответствует наличию проблем передачи данных на беспроводном участке канала, появление которых может быть связано с деградацией сигнала вследствие увеличения расстояния между устройством и базовой станцией, появлению препятствий на пути распространения сигнала и прочими причинами, не связанными непосредственно с загрузкой канала U_t. Поэтому для этого состояния среднее ${\mathbf{E}}\{ {\text{RT}}{{{\text{T}}}^{4}}\} $ и дисперсия ${\mathbf{D}}\{ {\text{RT}}{{{\text{T}}}^{4}}\} $, так же как и вероятности потери $P_{l}^{4}$ и тайм-аута пакета $P_{{to}}^{4}$, полагаются постоянными, но заметно более высокими, чем для состояний ${{e}_{i}}$, $i = \overline {1,3} $.

Алгоритм управления большинства версий TCP подразумевает различное поведение при тестировании возможностей канала в начале передачи или при восстановлении после сбоя и на промежутках стабильной передачи данных. Для этого выделяются две фазы функционирования протокола: медленного старта (slow start) и предотвращения перегрузки (congestion avoidance). В фазе предотвращения перегрузки алгоритм управления New Reno использует описанную выше схему аддитивного роста и мультипликативного снижения окна перегрузки, тогда как в фазе медленного старта рост окна перегрузки подчиняется более агрессивной экспоненциальной зависимости. Принцип работы алгоритма управления окном перегрузки New Reno в указанных фазах изображен на рис. 3.

Пусть $\overline {{\text{RTT}}} $ – среднее значение параметра ${\text{RTT}}$, вычисленное по ретроспективным статистическим данным за время, прошедшее с момента последней потери пакета или тайм-аута. Фаза медленного старта начинается с минимального окна перегрузки, равного $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{W} $. При поступлении стабильного потока подтверждений (при отсутствии потерь и тайм-аутов) окно перегрузки увеличивается на единицу за каждое полученное подтверждение. В среднем это соответствует двукратному увеличению окна за промежуток времени ${\text{RTT}}$. При достижении окном некоторого фиксированного порога ${{W}^{{th}}}$ (порог медленного старта) алгоритм переходит в фазу предотвращения перегрузки. В этой фазе окно U_t растет линейно с коэффициентом, равным $\frac{1}{{\overline {{\text{RTT}}} }}$. При регистрации потери пакета в любой из фаз окно уменьшается вдвое, при тайм-ауте – возвращается к минимальному значению $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{W} $. При тайм-ауте также происходит корректировка порога медленного старта ${{W}^{{th}}}$, который устанавливается равным половине окна перегрузки на момент регистрации тайм-аута. В любой момент времени, если значение окна перегрузки U_t становится меньше порога ${{W}^{{th}}}$, алгоритм переходит в фазу медленного старта.

Текущее состояние канала неизвестно, в качестве наблюдений доступны поток случайных значений времени кругового обращения сегментов данных ${\text{RTT}}$, а также случайные потоки потерь пакетов и тайм-аутов. Управление формируется на основании только этой статистической информации: в частности, параметр $\overline {{\text{RTT}}} $, характеризующий скорость роста окна U_t в фазе предотвращения перегрузки, является результатом экспоненциального осреднения потока измеренных ${\text{RTT}}$.

Изначально протокол New Reno предназначался для передачи данных по проводным сетям. Вероятность потери пакета, не связанной с переполнением буфера в каком-либо каналообразующем коммуникационном устройстве, в этой ситуации крайне низкая. Поэтому потеря пакета являлась практически несомненным индикатором перегрузки канала, и оптимальным поведением в данном случае было кратное уменьшение окна перегрузки. Однако для рассматриваемой модели, включающей в себя беспроводной участок, причина потери пакета не так однозначна: например, она может быть результатом ухудшения сигнала на беспроводном участке канала. Кроме того, одинаково большой коэффициент мультипликативного уменьшения окна перегрузки как в случае реального переполнения буфера коммуникационного устройства при высокой загрузке, так и вследствие раннего срабатывания алгоритма RED в “бутылочном горле” при умеренной загрузке очевидным образом приводит к недостаточному использованию пропускной способности канала и слишком низкой скорости передачи данных по сравнению с технически достижимой.

Оптимальная стратегия в каждом случае будет разной, поэтому актуальной задачей является оценка текущего состояния канала по имеющимся наблюдениям. В [28] оценка состояния канала была построена только по потоку потерь пакетов. В данном исследуемом случае дополнительно доступны также потоки подтверждений о доставке пакетов ACK и тайм-аутов, которые позволят значительно повысить качество оценивания, основываясь на теоретических результатах из области оптимальной фильтрации [26]. Для того, чтобы это сделать, необходимо формализовать описание функционирования TCP-соединения в виде математической модели частично наблюдаемой управляемой системы с состоянием в форме МСП. Этому посвящен следующий подраздел.

2. Математическая модель протокола TCP New Reno. 2.1. Модель состояния соединения. Построим управляемую стохастическую систему наблюдения, определяющую функционирование TCP-соединения. Из приведенного выше описания алгоритма TCP New Reno следует, что процесс X_t (ненаблюдаемое состояние соединения) принимает четыре возможных состояния. Текущее состояние X_t определяется совокупной нагрузкой всех коммуникационных устройств, участвующих в образовании физического канала, обеспечивающего исследуемое соединение, а также уровнем сигнала на беспроводном участке. Поскольку устройства, образующие канал, являются разделяемыми ресурсами, используемыми большим числом независимых пользователей, то наличие марковского свойства у процесса X_t представляется вполне естественным. Отсюда следует, что процесс состояния X_t есть МСП:

где X_t – текущее состояние системы: ${{{\mathbf{X}}}_{t}} \in {{\mathbb{S}}^{4}}$ (${{\mathbb{S}}^{4}} \triangleq \left\{ {{{e}_{1}}, \ldots ,{{e}_{4}}} \right\}$ – множество единичных векторов в ${{\mathbb{R}}^{4}}$),M_t – мартингал, $\Lambda ( \cdot ) \in {{\mathbb{R}}^{{4 \times 4}}}$ – управляемая матрица интенсивностей переходов состояния X_t, ${{U}_{t}} \geqslant \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{W} $ – управление, представляющее собой текущее значение окна перегрузки. При этом факт, что M_t – мартингал, служит прямым следствием формулы Дынкина для процесса X_t [29] для МСП и леммы 2 из [26] для управляемого МСП. Распределение начального условия выбрано равномерным, исходя из того соображения, что оно обладает наибольшей неопределенностью.

Матрица интенсивностей переходов $\Lambda \left( u \right) \triangleq {\text{||}}{{\lambda }^{{ji}}}\left( u \right){\text{|}}{{{\text{|}}}_{{j,i = \overline {1,4} }}}$ ограничена и имеет следующий вероятностный смысл:

где o(Δ) – функция, бесконечно малая по сравнению с Δ. Предполагается, что матрица Λ(u) удовлетворяет обычным условиям, накладываемым на матрицы интенсивностей переходов: ее внедиагональные элементы неотрицательные, а сумма элементов по строкам тождественно равна 0. Матрица имеет вид (громоздкие выражения для диагональных элементов заменены точками)

Компоненты ${{\lambda }^{{14}}}$, ${{\lambda }^{{24}}}$, ${{\lambda }^{{34}}}$, ${{\lambda }^{{41}}}$ и ${{\lambda }^{{42}}}$ не зависят от управления потому, что качество связи беспроводного участка соединения не зависит от характеристик потока данных, передаваемых по каналу. При этом интенсивность λ³⁴ полагается нулевой, поскольку сразу после восстановления качества беспроводной передачи данных высокая загрузка проводного участка канала невозможна в силу вынужденно низкого потока данных от источника во время нестабильной работы беспроводного соединения. Непосредственные переходы между состояниями e₁ и e₃, минуя промежуточное состояние e₂, полагаются невозможными, поэтому соответствующие интенсивности также равны нулю.

Управляемые компоненты матрицы $\Lambda $ имеют вид

где B – емкость канала (максимальное число пакетов в канале при пустом буфере “бутылочного горла”), $W{\text{''}}$ – порог гарантированного отклонения пакета алгоритмом RED, $\bar {\lambda }$ – интенсивность, достаточно высокая для гарантированного перехода из одного состояния в другое за время ${\text{RTT}}$, $\lambda _{0}^{{ij}}$, ${{C}^{{ij}}}$ – экспериментально подбираемые константы.

Предлагаемая выше зависимость компонентов ${{\lambda }^{{ji}}}$ от управления u объясняется следующими обстоятельствами. Канал свободен, пока количество пакетов в нем не достигло значения B, соответствующего его емкости. По мере приближения управления u к этому значению вероятность перехода из состояния e₁ в состояние e₂ должна расти, а при достижении B переход в состояние умеренной загрузки, когда начинает заполняться буфер “бутылочного горла”, должен быть гарантирован. Такое поведение обеспечивает обратнопропорциональная зависимость интенсивности ${{\lambda }^{{21}}}\left( u \right)$ от управления $u$ и гарантирующая интенсивность $\bar {\lambda }$. При этом даже при низких значениях собственного управления ${{U}_{t}} < B$, переход e₁ → e₂ возможен и за счет потоков передачи других пользователей канала связи. Для учета этого обстоятельства в закон изменения интенсивности перехода ${{\lambda }^{{21}}}\left( u \right)$ введен постоянный аддитивный член $\lambda _{0}^{{21}}$. При снижении собственного управления до значений, не превышающих порог B, вероятность обратного перехода в состояние, соответствующее свободному каналу, должна повышаться. Линейная зависимость в формуле для ${{\lambda }^{{12}}}\left( u \right)$ объясняется тем, что скорость обработки данных в телекоммуникационных устройствах не зависит от входящего потока. Иными словами, интенсивность обработки пакетов в буфере “бутылочного горла” постоянна. Интенсивности переходов между состояниями e₂ и e₃ подчиняются законам, аналогичным описанным выше для состояний e₁ и e₂, разница заключается лишь в том, что граничным значением управления здесь является $W{\text{''}}$, соответствующее порогу гарантированного отклонения пакета алгоритмом предотвращения переполнения буфера “бутылочного горла”. Очевидно, превышение этого значения приводит к потерям в канале, т.е. означает переход от состояния умеренной загрузки к перегрузке канала.

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

где ${{\ell }_{t}}$ – поток потерь пакетов, h_t – поток тайм-аутов, Z_t – поток подтверждений об успешной передаче пакетов.

Поток Z_t является высокочастотным и не есть, в общем случае, процесс Кокса [30] – неоднородный пуассоновский процесс, интенсивность которого зависит от ненаблюдаемого состояния X_t. Поэтому в качестве его модели используется диффузионная аппроксимация, в которой f(⋅) и g(⋅) представляют собой управляемые снос и диффузию, а W_t – стандартный броуновский процесс.

Модель Z_t  устроена следующим образом. Согласно аргументации, приведенной в подразд. 2.1, время кругового обращения $\tau $ отдельного пакета является случайной величиной, условные моменты которого в зависимости от текущих состояния канала X_t и окна перегрузки ${{U}_{t}}$ задаются следующими формулами:

где ${{\delta }_{0}}$ – время распространения сигнала по каналу, $\Xi \triangleq row\left( {{{\xi }_{1}},\; \ldots ,\;{{\xi }_{4}}} \right)$ – вектор-строка, определяющая для разных состояний канала X_t среднее время ожидания отправленного пакета в очередях, связанное с обработкой пакетов других пользователей, $\Upsilon \triangleq row\left( {{{\upsilon }_{1}},\; \ldots ,\;{{\upsilon }_{4}}} \right)$ – вектор-строка, определяющая для разных состояний канала X_t среднее время ожидания отправленного пакета в очередях, связанное с обработкой порции “своих” пакетов объема ${{U}_{t}}$, $\Phi \triangleq row(\phi _{1}^{2}, \ldots ,\phi _{4}^{2})$ – вектор-строка, определяющая для разных состояний канала X_t дисперсию части времени ожидания в очередях отправленного пакета, связанной с обработкой пакетов других пользователей, $\Psi \triangleq row(\psi _{1}^{2}, \ldots ,\psi _{4}^{2})$ – вектор-строка, определяющая для разных состояний канала X_t дисперсию части времени ожидания в очередях отправленного пакета, связанной с обработкой порции “своих” пакетов объема U_t.

Исходя из центральной предельной теоремы для процессов восстановления [31] и учитывая то, что время кругового обращения одного пакета $\tau $ соответствует доставке U_t подтверждений об успешной передаче, получаем, что

и

Процессы ${{\ell }_{t}}$ и h_t в (2.4) являются считающими с управляемыми интенсивностями

а процессы $M_{t}^{\ell }$ и $M_{t}^{h}$ – мартингалами. Предлагаемая выше зависимость компонентов $\theta \left( \cdot \right)$ и $\nu \left( \cdot \right)$ от управления объясняется тем, что потоки потерь и тайм-аутов представляют собой поток подтверждений, прореженный с соответствующими вероятностями ${{P}_{l}}\left( {{{U}_{t}}} \right)$ и ${{P}_{{to}}}$, а функции имеют также смысл интенсивности получения подтверждений об успешной доставке пакетов в каждом из состояний. Интенсивность потока потерь также содержит аддитивный член ${{\theta }_{0}} = row(\theta _{0}^{1}, \ldots ,\theta _{0}^{4})$, отвечающий за потери, вызванные потоками данных других пользователей канала. Интенсивность потока тайм-аутов при этом такого члена не содержит, поскольку сбои оборудования проводного участка канала или деградация сигнала на беспроводном участке от действий пользователей не зависят. Вероятности потерь пакетов в силу соображений, изложенных в подразд. 2.1, имеют вид

Известно, что признаками наступления перегрузки и падения качества канала выступают потеря пакета или появление тайм-аута. Одновременно два эти события произойти не могут, поэтому ${{\langle {{M}^{\ell }},{{M}^{h}}\rangle }_{t}} \equiv 0$. В то же время моменты потерь пакетов или появления тайм-аутов могут совпадать с моментом перехода канала в состояние e₃ или e₄. Однако не все переходы подобного рода, т.е. смены состояний канала, наблюдаемы как моменты потерь пакетов или тайм-ауты: некоторые из них могут быть порождены потоками других пользователей. Пусть сетевые устройства, включая “бутылочное горло”, используются N + 1 независимым потоком вместе с рассматриваемым потоком. Пусть $n_{t}^{{14}}$ – считающий процесс переходов e₁ → e₄ процесса X_t. Будем полагать, что

Аналогичным образом описывается зависимость наблюдаемых скачкообразных процессов $\ell $, h и процессов переходов n²³ и n²⁴. Остальные процессы сильно ортогональны, т.е. их скачки с вероятностью 1 не совпадают.

2.3. Модель протокола управления New Reno. Для синтеза управления U_t в протоколе New Reno используется оценка r_t текущего значения ${\text{RTT}}$, полученная из Z_t с помощью алгоритма экспоненциального сглаживания:

где $0 < \gamma < 1$ – некоторый известный параметр сглаживания. В (2.6) используется соотношение $d{\mathbf{Z}} = {{U}_{t}}dt{\text{/RTT}}$, которое основано на следующем соображении. В каждый момент времени в канале находится набор неподтвержденных пакетов, размер которого равен окну перегрузки U_t. При стабильной работе канала (без потерь и тайм-аутов) для получения подтверждений об успешной доставке всех пакетов из указанного набора потребуется время, равное RTT. Таким образом, если за время dt приходят подтверждения для df пакетов, простейшей оценкой времени кругового обращения пакетов ${\text{RTT}}$ является величина ${{U}_{t}}dt{\text{/}}d{{{\mathbf{Z}}}_{t}}$. Использование алгоритма экспоненциального сглаживания нивелирует осцилляционный характер ${\text{RTT}}$ каждого индивидуального пакета.

Управление U_t, выработанное по алгоритму New Reno, определяется следующим уравнением:

где $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{W} $ – минимальный размер окна, $W_{t}^{{th}}$ – пороговый размер окна, при котором начинается фаза предотвращения перегрузки, r_t – текущее сглаженное значение RTT, оцененное пользователем по данным Z_t, $\alpha $ и $\beta $ – коэффициенты линейного роста и мультипликативного уменьшения, параметры схемы управления AIMD, в стандарте TCP равные $\alpha = 1$, $\beta = 0.5$.

Первый интеграл в уравнении для U_t (2.7) соответствует фазе медленного старта, второй – фазе предотвращения перегрузки, третий – уменьшению окна вдвое при потере пакета, четвертый – уменьшению окна до $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{W} $ при возникновении тайм-аута.

Таким образом, уравнения (2.1), (2.4), (2.6) и (2.7) образуют замкнутую управляемую систему наблюдения с состоянием в форме МСП:

по виду близкую к системе (0.2) из первой части работы [26]. При этом непрерывные наблюдения представляют собой диффузионную аппроксимацию потока подтверждений об успешной передаче пакетов, а скачкообразные наблюдения складываются из потока потерь пакетов и тайм-аутов: $\mu \left( {{{U}_{s}}} \right) = {{(\theta \left( {{{U}_{s}}} \right),\nu \left( {{{U}_{s}}} \right))}^{{\text{Т }}}}$, ${{{\mathbf{H}}}_{t}} = {{(M_{t}^{l},M_{t}^{h})}^{{\text{Т }}}}$.

Уравнения оптимальной фильтрации состояния МСП, представленные в [26], не могут быть непосредственно применены для оценивания состояния X_t по наблюдениям $\left( {{{{\mathbf{Y}}}_{t}},{{{\mathbf{Z}}}_{t}}} \right)$. Во-первых, интенсивность шумов в наблюдениях Z_t зависит от X_t, а такие системы наблюдения не входят в исследованные в [26]. Во-вторых, уравнение для Z_t является лишь аппроксимацией истинного потока ACK, поэтому использовать Z_t в виде непрерывных наблюдений некорректно: данная аппроксимация будет давать удовлетворительную точность только при дискретизации Z_t с достаточным временным шагом. Поэтому для применения статистической информации, содержащейся в Z_t, правомерно использовать их дискретизованную версию:

где $\Delta > 0$ – шаг по времени, на порядок больший среднего значения RTT, но на несколько порядков меньше, чем компоненты Λ.

Таким образом, непрерывные наблюдения с зависящей от состояния диффузией Z_t заменяются в (2.8) на дискретные наблюдения, доступные в неслучайные известные моменты времени D_r (2.9), и тогда использование уравнения оптимальной фильтрации МСП становится правомерным.

Пусть

– условная плотность распределения наблюдения D_r относительно ${{\mathcal{F}}^{{X,U}}}$. В этом случае уравнение оптимальной фильтрации состояния X_t по считающим $\left( {{{h}_{t}},{{\ell }_{t}}} \right)$ и дискретным наблюдениям D_r имеет вид где ${{\hat {k}}_{t}} \triangleq {\text{diag}}{{{\mathbf{\hat {X}}}}_{t}} - {{{\mathbf{\hat {X}}}}_{t}}{\mathbf{\hat {X}}}_{t}^{ \top }$,

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

3. Численные эксперименты. 3.1. Функционирование New Reno на проводном канале связи. Предлагаемая математическая модель (2.1), (2.4), (2.6), (2.7) при своей относительной простоте обладает достаточной гибкостью для описания функционирования TCP-соединения и позволяет учитывать большое число внутренних и внешних факторов, влияющих на его качество: наличие/отсутствие беспроводного участка в канале, коммуникационных устройств, использующих алгоритм RED, внешних пользователей, разделяющих коммуникационные ресурсы канала и пр. Помимо этого соответствующая корректировка закона управления (2.6), (2.7) позволит исследовать не только версию New Reno протокола TCP, но и другие версии: Illinois, CUBIC, BBR и пр. Использование диффузионной аппроксимации для описания потока ACK обеспечивает предлагаемой модели некоторую робастность по отношению к неопределенности вероятностного распределения потока подтверждений: характеристики процесса Z_t зависят только от двух моментных характеристик RTT отдельного пакета и не зависят от всего распределения RTT.

Рассмотрим модель (2.1), (2.4), (2.6), (2.7) со следующими параметрами:

где параметры B, $W{\text{''}}$, ${{\delta }_{0}}$ и $\upsilon $ соответствуют каналу передачи данных с пропускной способностью C = 100 Мбит/c, временем распространения сигнала, равным ${{\delta }_{0}} = 0.1$ с, размером буфера устройства “бутылочного горла” в $Q = 100$ пакетов и размером полезной части самого пакета в $MSS$ = 1000 байт: $B = ({{10}^{6}}C{{\delta }_{0}}){\text{/}}(8MSS)$ = 1250, $W{\text{''}} = B + Q = 1350$, $\upsilon = (8MSS){\text{/}}({{10}^{6}}C)$ = 8 × 10^–5. Выбранные параметры вполне соответствуют характеристикам реально существующих сетевых соединений.

Модель с данными параметрами описывает функционирование New Reno на стабильном проводном канале, где тайм-ауты отсутствуют, а потери пакетов связаны только с переполнением буфера “бутылочного горла”. При этом канал используется монопольно: потоки данных от других пользователей полностью исключены. В таких условиях модель канала в целом и, как следствие, управление New Reno в таком случае ведет себя “детерминированным” образом, демонстрируя линейный рост и мультипликативный спад (AIMD). Соответствующие пилообразные графики, полученные путем анализа реального сетевого трафика, а также с помощью имитационного моделирования на симуляторе NS2 [32], приведены в [21].

На рис. 4 представлено поведение управления New Reno для соединения с выбранными параметрами.

График абсолютно соответствует предсказанному теоретическому поведению алгоритма New Reno. В самом начале наблюдается фаза медленного старта, во время которой окно перегрузки растет экспоненциально. Затем алгоритм переходит в фазу предотвращения перегрузки, во время которой окно растет линейно. При превышении окном порога B + Q происходит потеря пакета, приводящая к скачкообразному уменьшению окна перегрузки вдвое. После этого характерное поведение окна повторяется.

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

3.2. Мониторинг состояния соединения гетерогенного канала связи. Рассмотрим модель (2.1), (2.4), (2.6), (2.7) с исходными параметрами для канала передачи данных пропускной способности C = 100 Мбит/c, временем распространения сигнала ${{\delta }_{0}} = 0.1$ с, размером буфера Q = 100 и $MSS = 1000$ байт.

Она описывает работу протокола New Reno на гетерогенном (проводном–беспроводном) канале при наличии “бутылочного горла”, функционирующему по алгоритму RED. В этих условиях потери пакетов не гарантируют факта перегрузки: возможно, что в состоянии умеренной загрузки срабатывает алгоритм RED или на беспроводном участке произошло пропадание сигнала.

Решение задачи фильтрации состояния соединения по имеющейся информации является ключевым для последующей оптимизации передачи данных. Задача оптимальной фильтрации была решена в [28] для случая, когда в качестве доступной информации выступал только поток потерь пакетов. В предлагаемой работе наблюдению также доступен поток подтверждений об успешной доставке подтверждений ACK, использование которого позволяет кардинально улучшить качество оценивания состояния. Результаты фильтрации состояния по комплексным наблюдениям ACK, потерь и тайм-аутов приведены на рис. 5 в сравнении с результатами фильтрации только по потокам потерь и тайм-аутов. На рис. 6 представлены соответствующее управление и сглаженное значение RTT. На обоих рисунках моменты потерь пакетов обозначены черными точками, а моменты тайм-аутов – косыми крестами.

Необходимо отметить, что в данном примере шаг Δ дискретизации непрерывных наблюдений ${{{\mathbf{Z}}}_{t}}$ по времени был выбран равным 0.5 с, что обеспечивало корректность применения центральной предельной теоремы для процессов восстановления и рассмотрения соответствующих приращений ${{{\mathbf{Z}}}_{t}}$ как гауссовских величин.

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

Рассмотрим модель стабильного проводного канала из подразд. 3.1. Модифицируем алгоритм New Reno так, чтобы учитывать информацию о текущем состоянии канала. Пусть в (2.7) параметры схемы AIMD зависят от оценки состояния следующим образом:

где ${{\alpha }_{0}}$ и ${{\beta }_{0}}$ – некоторые постоянные векторы. Идея состоит в том, чтобы для состояний, соответствующих низкой загрузке канала, использовать больший коэффициент линейного роста по сравнению с состояниями перегрузки сети или плохой беспроводной связи. Коэффициент мультипликативного уменьшения окна перегрузки, напротив, следует уменьшить для состояний, где потеря пакета может не означать перегрузку сети. Линейная зависимость, с одной стороны, достаточно проста, а с другой – позволяет добиться того, чтобы окно перегрузки стало вогнутой функцией времени на участках стабильного функционирования канала связи. Вогнутая зависимость позволяет добиться более рационального использования доступной пропускной способности канала, не допуская периодов долгого роста окна перегрузки, и вместе с тем положительно сказывается на работе сети в целом, поскольку не ведет к серьезным перегрузкам, предполагая гораздо более аккуратное поведение при больших размерах окна, чем стандартный New Reno. Вогнутым характером обладает и оптимальное управление, полученное в [28], и алгоритм управления TCP Illinois [21], авторы которого предлагают соответственно обратно пропорциональную и линейную зависимость параметров $\alpha $ и $\beta $ от времени кругового обращения сегмента данных.

На рис. 7 представлено модифицированное управление для α₀ = $row\left( {{{\alpha }_{{{\text{max}}}}},{{\alpha }_{{{\text{min}}}}},{{\alpha }_{{{\text{min}}}}},{{\alpha }_{{{\text{min}}}}}} \right)$, ${{\beta }_{0}} = row\left( {{{\beta }_{{{\text{min}}}}},{{\beta }_{{{\text{min}}}}},{{\beta }_{{{\text{max}}}}},{{\beta }_{{{\text{max}}}}}} \right)$. Состояние канала здесь предполагается доступным наблюдению явно, а параметры ${{\alpha }_{{{\text{min}}}}} = 0.1$, ${{\alpha }_{{{\text{max}}}}} = 10$, ${{\beta }_{{{\text{min}}}}} = 0.125$, ${{\beta }_{{{\text{max}}}}} = 0.5$ выбраны в соответствии с рекомендациями из [21]. Очевидным отличием модифицированного алгоритма является его более агрессивное поведение на свободном канале, обеспечивающее быстрое достижение окном перегрузки значений, близких к максимальным и, как следствие, приводящее к более эффективному использованию пропускной способности. Кроме того, более осторожное поведение модифицированного алгоритма при загруженном канале дает возможность поддерживать высокие значения управления в течение значительного времени, не приводя к перегрузке.

Сравнение характеристик исходной и модифицированной версий New Reno было проведено для модели с параметрами, заданными в подразд. 3.2. Графики оценки состояния соединения приведены на рис. 8, а соответствующее управление и сглаженные значения RTT – на рис. 9. Здесь также моменты потерь пакетов обозначены черными точками, а моменты тайм-аутов – косыми крестами.

Несмотря на осцилляцию состояния, предлагаемая оценка фильтрации демонстрирует весьма высокую точность: собственное среднеквадратическое отклонение (СКО) процесса X_t равно ${{\sigma }_{X}} = 0.84$, СКО ошибки оценки фильтра по комплексным наблюдениям, вычисленное при моделировании на длительном временном отрезке, составляет ${{\sigma }_{{z,l,to}}} = 0.12$, для фильтра только по считающим наблюдениям ${{\sigma }_{{l,to}}} = 0.30$.

Характеристики эффективности исходной и модифицированной версий New Reno были вычислены путем моделирования их функционирования на длительном временном интервале ($T$ = 100 000 с) с последующим статистическим анализом. Выбор в пользу моделирования одного интервала большой длины вместо осреднения по пучку коротких траекторий объясняется необходимостью нивелировать влияние переходных процессов на начальном этапе передачи данных, связанных с режимом slow start, и тестированием возможностей канала с постепенным наращиванием скорости отправки. Адекватность результатов такого моделирования обуславливается ограниченностью интенсивностей переходов скачкообразного процесса состояния канала связи и интенсивностей считающих процессов потерь пакетов и тайм-аутов. Выбранная длина интервала моделирования оказалась достаточной для обеспечения примерно равной доли пребывания в состоянии e₄ (деградация сигнала на беспроводном участке), интенсивность переходов в/из которого не зависит от управления.

Результаты моделирования, представленные в таблице, позволяют говорить о том, что применение оценки состояния канала при управлении окном перегрузки повышает его эффективность и приводит к серьезному выигрышу в пропускной способности канала при том же уровне потерь. Действительно, реальная скорость передачи данных возрастает при использовании модифицированной версии протокола более чем в 2 раза. При этом данный параметр по сути является единственным критерием качества управления, поскольку он учитывает в себе и время, затрачиваемое на передачу всех пакeтов, включая потерянные, опоздавшие и переданные повторно, как бы ни была велика их доля. Выигрыш производительности достигается за счет невысокой агрессивности модифицированной версии протокола в состоянии e₂, которая позволяет системе сравнительно большое время балансировать в этом состоянии, в котором, с одной стороны, имеется возможность поддерживать высокую скорость передачи, а с другой – вероятность перегрузки сети сравнительно невысока. Действительно, исходный алгоритм управления New Reno склонен к неэффективному использованию ресурсов, и канал находится в состоянии e₁, т.е. свободен, большую часть времени (>76%), тогда как модифицированный алгоритм более производителен и умеренно загружает канал более 55% от общего времени моделирования.

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