---
# System prepended metadata

title: '2022: Компьютерные системы и сети. Лекция 5.'
tags: [Old, CSN, Lecture]

---

# 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) выполняют следующие базовые шаги:
 ```json
 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) 
    
  
![](https://upload.wikimedia.org/wikipedia/commons/thumb/b/be/CongWin_in_TCP_Tahoe_e_Reno.png/700px-CongWin_in_TCP_Tahoe_e_Reno.png)
Рис. Сравнение поведения двух популярных алгоритмов контроля перегрузки- [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://i.imgur.com/kAGHfCQ.png)](https://github.com/websockets/ws/issues/119)

### Пример приложения, контролирующего жизнеспособность каналов
Пример тестовой реализации работы WebSocket, контролирующей жизнеспособность множества каналов клиент-сервер:
[![](https://i.imgur.com/xTDZRQQ.png)](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).
