2023 : Комп'ютерні системи і мережі. 6.

# 2023: Комп'ютерні системи і мережі. 6. [TOC] ## Параметри та алгоритми контролю інформаційних каналів мережі ![](https://i.imgur.com/uNytWrG.png) ## Управління передачею даних Управління передачею даних зазвичай поділяють на два класи задач: * [Управління потоком](https://en.wikipedia.org/wiki/Flow_control_(data)) * [Контроль перевантаження](https://en.wikipedia.org/wiki/Network_congestion) ### [Управління потоком](https://en.wikipedia.org/wiki/Flow_control_(data)) #### Завдання, яке вирішується методами управління потоком Завдання, яке вирішується методами управління потоком: *узгоджена робота відправника та одержувача потоку даних - відправник інформації не повинен переповнити буфери приймача*. При вирішенні цього завдання відправник і одержувач працюють спільно, передаючи один одному керуючу інформацію і коригуючи обсяг даних, що відсилаються і розмір буфера даних, що приймаються, в залежності, в першу чергу, від стану обробки даних на стороні приймача. #### Підходи до керування потоком мiж вузлами. ![](https://i.imgur.com/MEqLxYM.png) Контроль потоку класифікується на дві категорії: 1. Керування потоком на основі зворотного зв’язку: у цій техніці керування відправник просто передає дані, інформацію чи кадр отримувачу, а потім отримувач передає контрольні дані назад відправнику, а також дозволяє відправнику передавати більше даних або повідомляти відправнику про те, як одержувач обробляє або робить. Це просто означає, що відправник передає дані або кадри після отримання підтвердження від користувача. 2. Контроль потоку на основі швидкості: у цій техніці керування зазвичай, коли відправник надсилає або передає дані на вищій швидкості до одержувача, а одержувач не може отримати дані з такою швидкістю, тоді механізм, відомий як вбудований механізм у протоколі, просто обмежує або обмежує загальну швидкість, з якою дані чи інформація передаються чи передаються відправником без будь-якого зворотного зв’язку чи підтвердження від одержувача. #### Найважливiши параметри методiв контролю **Затримка передавання** -- transmission delay ($\tau$) – час для передачі кадру (frame) даних від хоста в канал. Якщо **$B$** — це смуга пропускання каналу, а **$D$** — розмір фрейму даних, $$ \tau = D/B $$ **Затримка поширення** -- propagation delay ($\delta$) – це час, необхідний першому біту, переданому хостом в канал, щоб досягти пункту призначення. Вона залежить від відстані $l$ і швидкості поширення сигналу $s$ (залежить від характеристик середовища). $$ \delta = l/s $$ **Відносна затримка** $r$ - це відношення $\delta$ (затримки поширення) до часу $\tau$ передачі фрейма даних (затримки передавання) $$ r = \delta / \tau $$ **Ефективність** $\eta$ – визначається як відношення загального корисного часу $\tau_\Sigma$ до загального часу $T_\Sigma$ циклу передачi та контролю пакетy даних. $$ \eta = \tau_\Sigma / T_\Sigma. $$ Наприклад, для [протоколу зупинки та очікування](https://www.geeksforgeeks.org/efficiency-of-stop-and-wait-protocol/), ![](https://i.imgur.com/5bjRNNr.png) загальний час $T_\Sigma$ циклу передачi та контролю пакетy даних (оскільки підтвердження ACK набагато менші фрейму FRAME за розміром, затримкою їх передачі можна знехтувати): $$ \begin{array} T_\Sigma = \tau(FRAME) + \delta(FRAME) + \tau(ACK) + \delta(ACK) \approx \\ \approx \tau(FRAME) + \delta(FRAME) + \delta(ACK) \approx \\ \approx \tau + 2\delta = \tau +\Delta, \end{array} $$ де $\Delta$ — кругова затримка (rtt). Ефективність для протоколу зупинки та очікування: $$ \eta = \tau_\Sigma / T_\Sigma \approx \tau/(\tau + 2\delta) = 1/(1+2r) , $$ де $r$ -- це відносна затримка. **Ефективна пропускна здатність** ($B_e$) це ефективно використовувана пропускна здатність, тобто середня кількість біт кориснои информации, що надсилаються за секунду через канал. $$ B_e = D / T_\Sigma = \eta \cdot B $$ Відстежуваними параметрами цих методiв є **затримка** (Delay=$\delta$) передачi між термінальними вузлами з’єднaння i поточне значення **пропускної здатності каналу** (Bandwidth=$B$). Важливою інформацією для оптимізації є **$\text{BDP}= B\cdot \delta$** (Bandwidth-Delay Product), який можна назвати **об’ємом каналу** (інформаційною наповнюваністю). [Яка політика побудови протоколів забезпечуватиме максимальну ефективну пропускну здатність?](https://www.geeksforgeeks.org/difference-between-stop-and-wait-protocol-and-sliding-window-protocol/) ![](https://i.imgur.com/zeROV3U.png) ### Контроль навантаження каналу Завдання, які вирішуються методами контролю навантаження: *максимізація актуальної пропускної спроможності, забезпечення нормального (неперевантаженого) стану каналу зв'язку, справедливий поділ ресурсів каналу між кількома потоками*. Тут основними обмежувачами є параметри каналу передачі, якими сторони передачі не можуть керувати. Контроль зазвичай виконується на стороні відправника. Управління передачею при пропускній здатності, що змінюється в часі, виконується [множиною алгоритмів](https://en.wikipedia.org/wiki/TCP_congestion_control). ### Популярні алгоритми контролю перенавантаження Метою алгоритмів контролю перенавантаження каналу є оптимізація (максимізація) вікна передачі даних (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 завжди поєднують лінійне зростання вікна контролю до настання перевантаження і його мультиплікативну редукцію відразу після його виявлення. Важливість алгоритмів цього класу полягає в тому, що при одночаснiй роботі з каналом декількох з'єднань відбувається **адаптивна збіжність до рівного використання ресурсів каналу**[[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) спільного поділу ресурсів каналу. #### Формальна репрезентацiя AIMD Нехай $cwnd(t)$ - розмір вікна контролю навантаження, що вказує кількість даних, що у процесі передачі на кроці з номером $t$, $a>0$ - параметр адитивного зростання вікна, $0<b<1$ - параметр мультиплікативного скорочення розміру вікна. Тоді роботу AIMD можна описати такою ітеративною схемою: $$ {\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): $$ B=rate = {\displaystyle k\cdot\frac{cwnd}{rtt} = k\cdot\frac{\text{MSS}\cdot w}{rtt} }\approx \frac{D\cdot w}{\Delta} , $$ де $B=rate$ - пропускна спроможність TCP каналу, $k$ - коефіцієнт, що залежить від методу контролю навантаження, (для більшості випадків приймають $k\approx 1$), $cwnd$ - розмір контрольного вікна передачі, $D=MSS$ (Maximum Segment Size) - максимальний розмір сегмента даних для даного TCP з'єднання $\Delta=rtt$ (round-trip time) - час кругової затримки каналом, $w$ - розмір контрольного вікна, що вимірюється у кількості сегментів. Якщо ми знаємо можливість $p$ відкидання сегментів даних у стаціонарному режимі через періодичне короткочасне попадання в режим перевантаження каналу, то [формула пропускної здатності TCP з'єднання](https://www.cs.utexas.edu/users/lam/395t/papers/Mathis1998.pdf) набуває вигляду: $$ B = rate = {\displaystyle k\cdot\frac{\text{MSS}}{rtt\cdot\sqrt p} } \approx \frac{D}{\Delta\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/) # Розрахункові завдання ## [1.1 "Ненадійні WebSockets"](https://nexocode.com/blog/posts/websockets-friend-or-foe/) У момент часу $t=0$ серверна програма була з'єднана з $n$ незалежними клієнтськими програмами за протоколом WebSockets: ![](https://i.imgur.com/wrSCPxE.png) Щохвилини серверна програма надсилає повідомлення клієнтам і перевіряє, яка кількість клієнтів у нього знаходиться. На жаль, через стан каналів зв'язку, обмежень браузерів і серверів, ймовірність відключення сокету між черговими повідомленнями дорівнює $p$. Через деякий час усі сокети були відключені: ![](https://i.imgur.com/NEc8wfJ.png) Розподілений клієнт-серверний додаток вважається працюючим до тих пір, поки є хоча б одне з'єднання, що працює. Така поведінка називається [плавною деградацією роботи](https://en.wikipedia.org/wiki/Fault_tolerance#:~:text=The%20ability%20of%20maintaining%20functionality%20when%20portions%20of%20a%20system%20break%20down%20is%20referred%20to%20as%20graceful%20degradation.) клієнт-серверної системи. **Знайдіть середній час (у хвилинах) роботи цієї програми** з точністю 2 знаки після коми. ## [1.2 "Плавна деградація роботи"](https://en.wikipedia.org/wiki/Fault_tolerance#:~:text=The%20ability%20of%20maintaining%20functionality%20when%20portions%20of%20a%20system%20break%20down%20is%20referred%20to%20as%20graceful%20degradation.) У момент часу $t=0$ серверна програма була з'єднана з $n$ незалежними клієнтськими програмами за протоколом WebSockets: ![](https://i.imgur.com/wrSCPxE.png) Щохвилини серверна програма надсилає повідомлення клієнтам і перевіряє, яка кількість клієнтів у нього знаходиться. На жаль, через стан каналів зв'язку, обмежень браузерів і серверів, існує ненульова ймовірність $p$ відключення сокету між черговими повідомленнями. В середньому, через час $T$ хвилин всі сокети відключаються: ![](https://i.imgur.com/NEc8wfJ.png) і розподілений клієнт-серверний додаток вважається таким, що не працює. **Знайдіть верогідність $p$ відключення конкрентного сокету** з точністю 2 знаки після коми. # Динамічні статистичні оцінки параметрів мереж ### [Моменти розподілів випадкових величин](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}$. ### Матричнi узагальнення Можна розглядати **моменти багатовимірної випадкової величини**. * Тоді перший момент буде вектором тієї ж розмірності. * Другий момент - тензором другого рангу (див. [матриця коваріації](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) цiєї матрицi, що дає скалярне узагальнення дисперсiї). I т. iн. ### Трансформація центру моментів Оскільки $${\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 Створити мульти-клієнт - серверний додаток, що використовує хостинг 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 3. https://hpbn.co/ High Performance Browser Networking, Ilya Grigorik, online version 4. https://www.cs.utexas.edu/users/lam/395t/papers/Mathis1998.pdf Matthew Mathis. The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm 5. [Dynamical Behavior of Rate-Base Flow Control Mechanisms](https://people.engr.tamu.edu/xizhang/ECEN621/ResearchPapers/04_dynamic_behavior.pdf) 6. [Sliding Window Protocol](https://www.geeksforgeeks.org/sliding-window-protocol-set-1/) 7. https://replit.com/join/byvoqjthld-arthmax Пример тестовой реализации контроля жизнеспособности множества каналов по протоколу WebSocket 8. [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).