# 2022: Компьютерные системы и сети. Лекция 5.
[TOC]
## Параметры и алгоритмы контроля информационных каналов сети

## Управление передачей данных
Управление передачей данных обычно разделяют на два класса задач:
* [Управление потоком](https://en.wikipedia.org/wiki/Flow_control_(data))
* [Контроль перегрузки](https://en.wikipedia.org/wiki/Network_congestion)

### Управление потоком
Задача, решаемая методами управления потоком: *согласованная работа отправителя и получателя потока данных - отправитель информации не должен переполнить буферы приемника*.
При решении этой задачи отправитель и получатель работают совместно, передавая друг другу управляющую информацию и корректируя объем отсылаемых данных и размер буфера принимаемых данных, в зависимости, в первую очередь, от состояния обработки данных на стороне приемника.
### Контроль перегрузки
Задачи, решаемые методами контроля перегрузки: *максимизация актуальной пропускной способности, обеспечение нормального (неперегруженного) состояния канала связи, справедливое разделение ресурсов канала между несколькими потоками*.
Здесь основными ограничителями являются параметры канала передачи, которыми стороны передачи не могут управлять.
Контроль, обычно, выполняется на стороне отправителя.

Управление передачей при изменяющейся во времени пропускной способности
выполняется [множеством алгоритмов](https://en.wikipedia.org/wiki/TCP_congestion_control).

#### Важнейшие параметры
Отслеживаемыми параметрами этих алгоритмов являются: **задержка** (Delay=D) передачи между терминальными узлами соединения и текущее значение **пропускной способности канала** (Bandwidth=B).

Важной информацией для оптимизации является **BDP= B*D** (Bandwidth-Delay Product), который можно назвать **объемом канала** (информационной наполняемостью).

### Популярные алгоритмы контроля перегрузки
Целью алгоритмов контроля перегрузки канала является оптимизация (максимизация) окна передачи данных (cwnd) путем отслеживания событий перегрузки канала с последующей коррекцией окна и параметров его роста.

Наиболее популярные алгоритмы контроля перегрузки канала (смотри [Tahoe и Reno](https://en.wikipedia.org/wiki/TCP_congestion_control#:~:text=Or%202%20*%20MSS-,TCP%20Tahoe,avoidance%20algorithm.%20The%20overall%20algorithm%20here%20is%20called%20fast%20recovery.,-Slow%20start%20assumes)) для протокола TCP (а значит, неявно и для протокола WebSocket и прикладного API, базирующегося на нем, например, Socket.IO) выполняют следующие базовые шаги:

 1) В начальной фазе - экспоненциальный рост окна данных cwnd до некоторого
     порогового уровня.
     Если до этого была обнаружена перегрузка, выполняется шаг 3)

 2) Затем, после превышения этого порогового уровня, - линейно увеличивают размер окна 
     до тех пор, пока не происходит потери пакета данных в результате перегрузки канала. 
     Обычно, это отслеживается по сигналам подтверждения ACK от приемника
     (точнее, по их отсутствию в течение длительного времени). 

 3) Как только обнаруживается перегрузка, размер окна данных cwnd уменьшается
     до порогового уровня. 
     (обычно, этот уровень в 2 раза меньше перегруженного cwnd,
      но, естественно, не меньше 1 пакета данных).

 4) После этого, обычно, происходит переход к шагу 2)

Варианты работы алгоритмов могут после обнаружении перегрузки уменьшать размер окна до 1 пакета и переходить к шагу 1). Некоторые варианты алгоритмов динамически адаптируют пороговые уровни.

Важнейшей частью этих алгоритмов является аддитивно-мультипликативное поведение [Additive increase/multiplicative decrease (AIMD)](https://en.wikipedia.org/wiki/Additive_increase/multiplicative_decrease#:~:text=Additive%20increase/multiplicative%20decrease), начиная с шага 2)

Рис. Сравнение поведения двух популярных алгоритмов контроля перегрузки- [Tahoe и Reno](https://en.wikipedia.org/wiki/TCP_congestion_control#:~:text=Or%202%20*%20MSS-,TCP%20Tahoe,avoidance%20algorithm.%20The%20overall%20algorithm%20here%20is%20called%20fast%20recovery.,-Slow%20start%20assumes)

#### Алгоритмы аддитивно-мультипликативного управления окном

Алгоритмы **аддитивно-мультипликативного управления окном** cwnd (AIMD) - это алгоритмы управления с обратной связью по времени запаздывания сигналов ACK от приемника. Они в первую очередь используются для контроля перегрузки в протоколе TCP. Однако, важно знать их свойства и при работе с протоколами более высоких уровней и при разработке прикладных алгоритмов [балансировки нагрузки](https://en.wikipedia.org/wiki/Load_balancing_(computing)). Алгоритмы класса AIMD всегда сочетают линейный рост окна контроля до наступления перегрузки и мультипликативную его редукцию сразу после его обнаружения.

Важность алгоритмов этого класса состоит в том, что при одновременной работе с разделяемым каналом нескольких соединений происходит **адаптивная сходимость к равному использованию ресурсов канала** [[1](https://www.researchgate.net/publication/222470347_Analysis_of_the_increase_and_decrease_algorithms_for_congestion_avoidance_in_computer_networks)].
Другие схемы: *мультипликативный рост/мультипликативный уменьшение* (MIMD) и *аддитивный рост/аддитивное уменьшение* (AIAD) - не сходятся к стабильному и [справедливому](https://en.wikipedia.org/wiki/Fairness_measure#:~:text=further%20investigations.%5B1%5D-,Jain%27s%20fairness%20index,-%5Bedit%5D) совместному разделению ресурсов канала.

#### Формальное представление AIMD
Пусть $cwnd(t)$ - размер окна контроля перегрузки, указыващий количество данных, находящихся в процессе передачи на шаге с номером $t$,
$a>0$ - параметр аддитивного роста окна,
$0<b<1$ - параметр мультипликативного сокращения размера окна.

$$
{\displaystyle
cwnd(t+1)= {\begin{cases}
cwnd(t)+a, & {\text{ если перегрузка не обнаружена}}\\
cwnd(t)\times b, & {\text{ в противном случае}}
\end{cases}
}
}
$$
### Зависимость полезной пропускной способности от размера окна данных

В алгоритмах TCP после "низкого старта" - малого значения $w$, параметр аддитивного увеличения $a=1\, \text{MSS}$ ([Maximum Segment Size](https://en.wikipedia.org/wiki/Maximum_segment_size)) на $1\, \text{rtt}$ ([round-trip time](https://en.wikipedia.org/wiki/Round-trip_delay)) и, обычно, параметр мультипликативного сокращения размера окна ${\displaystyle b}=1/2$.

#### Пропускная способность TCP канала
Для TCP канала в стационарном режиме получена [простая формула [3]](https://www.cs.utexas.edu/users/lam/395t/papers/Mathis1998.pdf):
$$
rate = {\displaystyle k\times\frac{cwnd}{rtt} = k\times\frac{\text{MSS}\cdot w}{rtt} },
$$
где
$rate$ - пропускная способность TCP канала,
$k$ - коэффициент, зависящий от метода контроля перегрузки,
(для большинства случаев принимают $k=1$),
$cwnd$ - размер контрольного окна передачи,
$\text{MSS}$ (Maximum Segment Size) - максимальный размер сегмента данных для данного TCP соединения
$rtt$ (round-trip time) - время круговой задержки по каналу,
$w$ - размер контрольного окна, измеряемый в количестве сегментов.

Если мы знаем вероятность $p$ отбрасывания сегментов данных в стационарном режиме из-за периодического кратковременного попадания в режим перегрузки канала, то [формула пропускной способности TCP соединения]((https://www.cs.utexas.edu/users/lam/395t/papers/Mathis1998.pdf)) принимает вид:
$$
rate = {\displaystyle k\times\frac{\text{MSS}}{rtt\cdot\sqrt p} },
$$

## Жизнеспособность канала

Канал, соединяющий клиента и сервер, может быть разорван внезапно как по требованию со стороны клиента или сервера, так и из-за временных ограничений браузера или серверного фреймворка, а также из-за банальных поломок или отключения электропитания оборудования.
[](https://github.com/websockets/ws/issues/119)

### Пример приложения, контролирующего жизнеспособность каналов
Пример тестовой реализации работы WebSocket, контролирующей жизнеспособность множества каналов клиент-сервер:
[](https://websocket-server.arthmax.repl.co/)

## Динамические статистические оценки параметров сетей
### [Моменты распределений случайных величин](https://en.wikipedia.org/wiki/Moment_(mathematics))
Если дана случайная величина $X$, определённая на некотором вероятностном пространстве, то:
* $k$-м *нача́льным моментом* случайной величины $X$, где ${k\in \mathbb N }$, называется величина
$$
{\displaystyle \nu _{k}=\mathbb {E} \left[X^{k}\right],}
$$
если математическое ожидание ${\mathbb E [*]}$ в правой части этого равенства определено;
* ${\displaystyle k}$-м *центра́льным моментом* случайной величины ${\displaystyle X}$ называется величина
$$
{\displaystyle \mu _{k}=\mathbb {E} \left[(X-\mathbb {E} X)^{k}\right],}
$$

### Геометрический смысл некоторых моментов
* $\mu_2$ равняется *дисперсии* распределения $(\mu_2=\sigma^2)$ и показывает разброс распределения вокруг среднего значения.
* $\mu_3$, будучи соответствующим образом нормализован, является числовой характеристикой симметрии распределения. Более точно, выражение
$$
\frac {\mu_3}
{\sigma^3}
$$
называется *[коэффициентом асимметрии](https://en.wikipedia.org/wiki/Skewness)*.
* $\mu_4$ показывает, насколько тяжелые у распределения хвосты. Величина
$$
{\displaystyle
\gamma_2 = {\frac {\mu_4}
{\sigma^4}} - 3
}
$$
называется *[коэффициентом эксцесса](https://en.wikipedia.org/wiki/Kurtosis)* распределения ${X}$.

### Матричные обобщения

Можно рассматривать **моменты многомерной случайной величины**.
* Тогда первый момент будет вектором той же размерности.
* Второй момент — тензором второго ранга (см. [матрица ковариации](https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D0%BA%D0%BE%D0%B2%D0%B0%D1%80%D0%B8%D0%B0%D1%86%D0%B8%D0%B8)) над пространством той же размерности (можно рассматривать и [след](https://ru.wikipedia.org/wiki/%D0%A1%D0%BB%D0%B5%D0%B4_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8B) этой матрицы, дающий скалярное обобщение дисперсии). И т. д.

### Трансформация центра моментов
Поскольку

$${\displaystyle (x-b)^{n}=(x-a+a-b)^{n}=\sum _{i=0}^{n}{n \choose i}(x-a)^{i}(a-b)^{n-i}} \, ,\tag{*}
$$
где ${\displaystyle {\dbinom {n}{i}}}$ - биномиальный коэффициент, то из этого следует, что моменты относительно $b$ могут быть вычислены из моментов относительно $a$ следующим образом:
$$
{ \displaystyle
E\left[(x-b)^{n}\right] =
\sum _{i=0}^{n}{n \choose i}E\left[(x-a)^{i}\right](a-b)^{n-i}.}
$$

## [k-Статистики](https://mathworld.wolfram.com/k-Statistic.html)
k-статистика $k_n$ - это несмещенная оценка [кумулянта $\kappa_n$](https://mathworld.wolfram.com/Cumulant.html) статистического распределения.
Важность кумулянтов связана с их важнейшим свойством:
$$
\kappa_n (X + Y) = \kappa_n(X) + \kappa_n(Y),
$$
если $X$ и $Y$ - независимые случайные величины.
Первые кумулянты связаны с моментами следующим образом:
$$
\kappa_1=\nu_1\\
\kappa_2=\mu_2\\
\kappa_3=\mu_3\\
\kappa_4=\mu_4-3\mu_2^2\\
\kappa_5=\mu_5-10\mu_2\mu_3.
$$
k-статистика определяется математическими ожиданиями эмпирических величин $k_n$:
$$
\mathbb {E} k_n = \kappa_n,
$$
k-статистику удобно записывать в терминах сумм степеней получаемых данных.
Если
$$
S_r= \sum_{i=1}^nX_i^r,
$$
тогда
$$
k_1 = \frac {S_1}
{n} \\
k_2 = \frac {nS_2-S_1^2}
{n(n-1)} \\
k_3 = \frac {2S_1^3-3nS_1S_2+n^2S_3}
{n(n-1)(n-2)} \\
k_4 = \frac {-6S_1^4+12nS_1^2S_2-3n(n-1)S_2^2-4n(n+1)S_1S_3+n^2(n+1)S_4} {n(n-1)(n-2)(n-3)} \\
$$
[*Unbiased Estimators of Cumulants](https://mathworld.wolfram.com/k-Statistic.html#:~:text=Rose%2C%20C.%20and%20Smith%2C%20M.%C2%A0D.%20%22k%2DStatistics%3A%20Unbiased%20Estimators%20of%20Cumulants.%22%20%C2%A77.2C%20in%20Mathematical%20Statistics%20with%20Mathematica.%20New%20York%3A%20Springer%2DVerlag%2C%20pp.%C2%A0256%2D259%2C%202002).

1. Задание
Используя формулу $(^*)$, доказать полезное соотношение:
$${\displaystyle
\mu _{k}=\sum \limits _{s=0}^{k}{(-1)^{s}C_{k}^{s}\nu_{s}\nu _{1}^{k-s}}}.
$$
Это соотношение означает, что центральные моменты могут быть выражены через начальные.

2. Задание
Получить соотношения
$${\displaystyle
\mu _{k}=\sum \limits _{s=0}^{k}{(-1)^{s}C_{k}^{s}\nu _{k-s}\nu _{1}^{s}}}.
$$
для первых $k=1,2,3,4$

## Задание на лабораторную работу №4
Создать мульти-клиент - серверное приложение, использующее хостинги
а) glitch.com,
б) replit.com
с реализацией функционала при помощи API WebSocket

**Проводится контест на максимально быструю круговую передачу 1 МB информации для каналов и серверов с заранее неизвестными ограничениями.**

Функции, которые должны быть реализованы на html странице:
а) контроль жизнеспособности соединений;
б) 100-кратный тест на максимально быструю круговую передачу заданного количества информации;
в) динамическую оценку задержки и полезной полосы пропускания по круговому пути клиент - сервер - клиент:

$$
\text{ RTT delay}: \\
\min = \\
\max = \\
\mu_1 = \\
\mu_2 = \\
\mu_3 = \\
\mu_4 = \\
\\
\text{ RTT Bandwidth}: \\
\min = \\
\max = \\
\mu_1 = \\
\mu_2 = \\
\mu_3 = \\
\mu_4 = \\
$$

# Ресурсы
1. https://www.researchgate.net/publication/222470347_Analysis_of_the_increase_and_decrease_algorithms_for_congestion_avoidance_in_computer_networks
2. https://hpbn.co/ High Performance Browser Networking, Ilya Grigorik, online version
3. https://www.cs.utexas.edu/users/lam/395t/papers/Mathis1998.pdf Matthew Mathis. The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm
4. https://replit.com/join/byvoqjthld-arthmax Пример тестовой реализации контроля жизнеспособности множества каналов по протоколу WebSocket
5. [Unbiased Estimators of Cumulants](https://mathworld.wolfram.com/k-Statistic.html#:~:text=Rose%2C%20C.%20and%20Smith%2C%20M.%C2%A0D.%20%22k%2DStatistics%3A%20Unbiased%20Estimators%20of%20Cumulants.%22%20%C2%A77.2C%20in%20Mathematical%20Statistics%20with%20Mathematica.%20New%20York%3A%20Springer%2DVerlag%2C%20pp.%C2%A0256%2D259%2C%202002).