2025: Комп'ютерні системи і мережі. 2. Керування передачею даних. Параметри каналу.

• 2025: Комп'ютерні системи і мережі. 2. Керування передачею даних. Параметри каналу.
• Параметри та алгоритми контролю стану інформаційного каналу
  • Керування передачею даних
    • Керування потоком
  • Найважливiши параметри методiв контролю
  • Контроль навантаження каналу
    • Популярні алгоритми контролю перенавантаження
    • Алгоритми адитивно-мультипликативного керування вікном
    • Формальна репрезентацiя AIMD
• Розширення методів контролю навантаження
  • Забезпечення неперевантаженого стану роботи серверу
  • Справедливий поділ обчислювальних ресурсів
  • Обчислювальна складність задач та навантаження серверу
  • Об’єднаний механізм
• Завдання на лабораторну роботу 2
• Ресурси

Параметри та алгоритми контролю стану інформаційного каналу

Керування передачею даних

Керування передачею даних зазвичай поділяють на два класи задач:

• Керування потоком
• Контроль перевантаження

Керування потоком

Завдання, яке вирішується методами керування потоком

Завдання, яке вирішується методами керування потоком: узгоджена робота відправника та одержувача потоку даних - відправник інформації не повинен переповнити буфери приймача.

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

Підходи до керування потоком мiж вузлами.

Контроль потоку класифікується на дві категорії:

1. Керування потоком на основі зворотного зв’язку: у цій техніці керування відправник просто передає дані, інформацію чи кадр отримувачу, а потім отримувач передає контрольні дані назад відправнику, а також дозволяє відправнику передавати більше даних або повідомляти відправнику про те, як одержувач працює. Це просто означає, що відправник передає дані або кадри після отримання підтвердження від користувача.

2. Контроль потоку на основі швидкості: у цій техніці керування зазвичай, коли відправник надсилає або передає дані на вищій швидкості до одержувача, а одержувач не може отримати дані з такою швидкістю, тоді механізм, відомий як вбудований механізм у протоколі, обмежує загальну швидкість, з якою дані чи інформація передаються відправником без будь-якого зворотного зв’язку чи підтвердження від одержувача.

• Вкажіть, на яких рівнях стека протоколу OSI та для яких завдань використовуються вказані методи контролю?

Найважливiши параметри методiв контролю

Параметрами, що треба відстежувати, є
затримка передачі (Delay=\(\delta\) або Latency) між термінальними вузлами з'єднання
і поточне значення
пропускної здатності каналу (Bandwidth=B).

• У яких одиницях виміру визначають пропускну здатність?
• Як можна назвати величину, зворотну до пропускної здатності B каналу?

Корисною інформацією для мережевих додатків типа P2P та розширень є \(BDP = B \cdot\delta\) (Bandwidth-Delay Product), яку можна назвати обсягом каналу (інформаційною наповнюваністю). Від цього параметру залежить розмір буферу даних відправника та приймача.

• Що таке протоколи та мережеві додатки типа P2P ?
• Чому обсяг каналу – важлива інформацією для оптимізації ?

Якщо джерело даних або приймач змушений часто зупинятися і чекати на отримання підтвердження (ACK) для раніше відісланих пакетів даних, з'являються перерви в потоці даних (data gaps), які обмежують реальну пропускну здатність каналу зі зворотним зв'язком. Наприклад, на ілюстрації продемонстровано вплив \(\delta\) каналу на продуктивність TCP протоколу або додатків, що працюють за тим самим принципом.

• Завдання
  Нехай нам відомі стабільні пропускна здатність \(B\) каналу та затримка \(\delta\) у каналі зв'язку. Для надійної передачі блоку інформації обсягу \(D\) знадобиться час \(T\), що обчислюється за формулою:
  \[ \begin{array} &1)\, T = \delta + \frac{D}{B} \\ 2)\, T = \max (2\delta,\frac{D}{B}) \\ 3)\, T = \min (\delta,\frac{D}{2B})\\ 4)\, T = \delta + \tau(D) \\ \end{array} \]
  Виберіть та обґрунтуйте правильну формулу.

Насправді параметри \(B\) і затримки \(\delta\) заздалегідь точно не відомі. Як не дивно, але параметр \(\delta\) складно (дорого) точно визначати, і неточність \(\delta\) впливає на точність визначення ефективного значення параметра \(B\). Крім того, \(B\) і \(\delta\) та змінюються в залежності від кількості запитів і просто протягом часу.

• Чому параметр \(\delta\) складно (дорого) точно визначати, і неточність \(\delta\) впливає на точність визначення ефективного значення параметра \(B\)?
• Чому \(B\) і \(\delta\) та змінюються в залежності від кількості запитів і просто протягом часу?

Розглянемо докладніше набір параметрів та оцінок для характеризації ефективності роботи каналів зв'язку або простих додатків типу P2P.

Затримка передавання – 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. \]

Наприклад, для протоколу зупинки та очікування, який застосовується як на рівні протоколів передачі даних, так і на простих мережевих додатках, загальний час \(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).

• Чому кругову затримку \(\Delta\) легше визначити ніж односторонню затримку поширення \(\delta\)?

Ефективність для протоколу зупинки та очікування:
\[ \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\)).

• Яка політика побудови протоколів забезпечуватиме максимальну ефективну пропускну здатність?

Контроль навантаження каналу

Завдання, які вирішуються методами контролю навантаження:

1. максимізація актуальної пропускної спроможності,
2. забезпечення нормального (неперевантаженого) стану каналу зв'язку,
3. справедливий поділ ресурсів каналу між кількома потоками.

Основними обмежувачами максимальної пропускної спроможності є параметри каналу передачі, якими сторони передачі не можуть керувати.

• Вкажіть, які та чому?

Контроль актуальної пропускної спроможності зазвичай виконується на боці відправника.

• Чому зазвичай контроль виконується на боці відправника?

Керування передачею при пропускній здатності, що змінюється в часі,
виконується множиною алгоритмів.

Щоб оптимізувати реальну пропускну здатність, вікно (контрольний розмір cwnd) даних, що відсилаються, слід максимально збільшувати, так щоб потоки відсилання даних і отримання підтвердження йшли безперервно по дуплексному каналу.

• Який із різновидів алгоритмів контролю при цьому використовується?
• Що таке дуплексний канал?
• Як пов'язані між собою величини cwnd та \(\text{BDP}\) ?

Оптимальне значення вікна (\(w\)) залежить від кругового часу подорожі (\(\Delta=\text{rtt}\)) дуплексним каналом. При виборі невеликого \(w\) буде обмежена реальна корисна пропускна здатність (goodput), незалежно від доступної фізичної пропускної здатності \(B\)(Bandwidth). Однак, при перевищенні оптимального розміру вікна відбудеться перевантаження (congestion) каналу .

Тому метою алгоритмів контролю навантаження каналу є оптимізація (максимізація) вікна передачі даних (\(w\)) і при цьому відстеження явища навантаження каналу з подальшою корекцією вікна та параметрів його зростання.

Популярні алгоритми контролю перенавантаження

Завдання, яке вирішується методами контролю перенавантаження, - забезпечення нормального (ненасиченого) стану каналу зв'язку.

• Які математичні та фізичні причини такого явища, як насичений стан каналу зв'язку?

Метою алгоритмів контролю перенавантаження каналу є оптимізація (максимізація) вікна передачі даних (\(w\)) шляхом відстеження подій перенавантаження каналу з подальшою корекцією вікна та параметрів його зростання.

Найбільш популярні алгоритми контролю перевантаження каналу і прикладного API виконують такі базові кроки:

​1) У початковій фазі - експоненційне зростання вікна w даних  до деякого
​     порогового рівня.
​     Якщо до цього було виявлено перевантаження, виконується крок 3)

​ 2) Потім, після перевищення цього порогового рівня, - лінійно збільшують розмір вікна
​     до тих пір, поки не відбувається втрати пакета даних внаслідок перенавантаження каналу.
​     Зазвичай це відстежується за сигналами підтвердження ACK від приймача
​     (Точніше, за їх відсутністю протягом тривалого часу).

​ 3) Як тільки виявляється перенавантаження, розмір вікна даних w зменшується
​     до граничного рівня.
​     (зазвичай, цей рівень у 2 рази менше перевантаженого w,
​      але, звісно, щонайменше 1 пакета даних).

​ 4) Після цього зазвичай відбувається перехід до кроку 2)

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

Найважливішою частиною цих алгоритмів є адитивно-мультиплікативна поведінка Additive increase/multiplicative decrease (AIMD), починаючи з кроку 2)

Мал. Порівняння поведінки двох популярних алгоритмів контролю перевантаження-Tahoe и Reno

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

Алгоритми адитивно-мультиплікативного керування вікном cwnd (AIMD) - це алгоритми керування зі зворотним зв'язком за часом запізнення сигналів ACK від приймача. Вони насамперед використовуються для контролю перевантаження у протоколі TCP. Однак, важливо знати їх властивості і при роботі з протоколами вищих рівнів і розробки прикладних алгоритмів балансування навантаження. Алгоритми класу AIMD завжди поєднують лінійне зростання вікна контролю до настання перевантаження і його мультиплікативну редукцію відразу після його виявлення.

Важливість алгоритмів цього класу полягає в тому, що при одночаснiй роботі з каналом декількох з'єднань відбувається адаптивна збіжність до рівного використання ресурсів каналу[1].
Інші схеми: мультиплікативне зростання/мультиплікативне зменшення (MIMD) та адитивне зростання/адитивне зменшення (AIAD) - не сходяться до стабільного і справедливого спільного поділу ресурсів каналу.

Формальна репрезентацiя AIMD

Нехай \(w(t)\) - розмір вікна контролю навантаження, що вказує кількість даних, що у процесі передачі на кроці з номером \(t\),
\(a>0\) - параметр адитивного зростання вікна,
\(0<b<1\) - параметр мультиплікативного скорочення розміру вікна.

Тоді роботу AIMD можна описати такою ітеративною схемою:
\[ w(t+1)= {\begin{cases} w(t)+a, & {\text{ якщо перевантаження не виявлено}}\\ w(t)\times b, & {\text{ в іншому випадку}} \end{cases} } \]

Наприклад, в алгоритмах TCP після початкового "низького старту" - малого значення \(w(0)\) і експоненційного зростання, що закономірно приводить до першого перевантаження або порушення порогового значення (treshold), параметр адитивного збільшення \(a=1\, \text{[MSS/rtt]}\) (MSS - Maximum Segment Size , rtt - round-trip time) і, як правило, параметр мультиплікативного скорочення розміру вікна \({\displaystyle b}=1/2 \, \text{[MSS/rtt]}\).

Пояснення

Клас алгоритмів – адитивно-мультиплікативне збільшення/зменшення (AIMD). Саме для них при одночасній роботі кількох з’єднань канал “самостійно” сходиться до справедливого (рівного) поділу пропускної спроможності.

\[ w(t+1) = \begin{cases} w(t) + a, & \text{якщо немає перевантаження},\\ b \cdot w(t), & \text{якщо є перевантаження},\quad 0 < b < 1 \end{cases} \]

Для двох потоків \(w_1 > w_2\):

• Під час збільшення: \(\Delta(t) = w_1 - w_2\) — стала.
• Після зменшення: \(\Delta' = b \cdot \Delta\).
• Після \(k\) циклів: \(\Delta(k) = b^k \cdot \Delta(0) \rightarrow 0\) при \(k \to \infty\).

• Чому схеми: мультиплікативне зростання/мультиплікативне зменшення (MIMD) та адитивне зростання/адитивне зменшення (AIAD) - не сходяться до стабільного і справедливого спільного поділу ресурсів каналу? Яку схему можно назвати найбільш нестабільною, а яку найбільш несправедливою?

Пояснення

• При MIMD кожне з’єднання і при нарощенні, і при зниженні змінює своє вікно мультиплікативно:
  \[ w_i(t+1) = \begin{cases} r\cdot w_i(t), & r>1\quad(\text{без перевантаження}),\\ s\cdot w_i(t), & 0<s<1\quad(\text{при перевантаженні}). \end{cases} \]
  Тоді відношення розмірів вікон двох потоків \({w_1}/{w_2}\) залишається сталим в усіх ітераціях, тому будь-яка початкова нерівність не вирівнюється, а амплітуда коливань може зростати експоненційно аж до межи пропускної здатності.

• При AIAD обидва потоки змінюють своє вікно адитивно на один і той самий крок \(a\):
  \[ w_i(t+1) = \begin{cases} w_i(t) + a, & \quad(\text{без перевантаження}),\\ w_i(t) - a & \quad(\text{при перевантаженні}). \end{cases} \]
  Різниця між їхніми cwnd, \(w_1 - w_2\), залишається незмінною при кожному збільшенні та зменшенні, тож початкова несправедливість не коригується.

• Найбільш нестабільна: MIMD — через експоненціальне зростання/скорочення вікон із великими коливаннями.

• Найбільш несправедлива: AIAD — бо різниця між потоками ніколи не змінюється і початкова перевага одного з’єднання зберігається.

Розширення методів контролю навантаження

Які методи контролю навантаження можна використовувати для вирішення задач:

1. забезпечення нормального (неперевантаженого) стану роботи серверу,
   
2. справедливий поділ обчислювальних ресурсів серверу між кількома одночасно працючими клієнтами?
   
   

Для яких обчислювальних задач можно використовувати ці методи?

3. Як впливає обчислювальна складність задачі на вибір методів контролю навантаження серверу?
   
   

Забезпечення неперевантаженого стану роботи серверу

Для вирішення 1) питання зазвичай застосовують такі основні методи контролю навантаження, як:

• Admission Control – відмовляти або відкладати нові запити при досягненні порогу завантаження.
• Rate Limiting – обмежувати швидкість запитів (Token Bucket, Leaky Bucket).
• Load Shedding – скидати запити низького пріоритету під час пікових навантажень.
• Backpressure – сигналізувати клієнтам/мікросервісам сповільнити відправку даних, коли внутрішні черги переповнені.
• Auto-Scaling – динамічно додавати/знімати екземпляри (горизонтальне масштабування) за метрикою CPU, latency тощо.

Справедливий поділ обчислювальних ресурсів

Для вирішення 2) питання (справедливого поділу обчислювальних ресурсів між одночасними клієнтами) можливе використання методів:

• Fair Scheduler – планування за принципом «рівного віртуального часу»:
• Weighted Fair Queuing (WFQ) або Deficit Round Robin (DRR) для мережевих/пакетних черг;
• Completely Fair Scheduler (CFS) для CPU.
• Квоти / Cgroups – обмеження CPU, пам’яті чи I/O на групу процесів або контейнер.
• Priority Queuing – виділяти гарантовані «слоти» ресурсів для високопріоритетних клієнтів.

Обчислювальна складність задач та навантаження серверу

Для вирішення 3) питання треба модифікувати методи детерминування складності обчислювальних задач для мережевих розподілених систем.
В простих випадках можно використовувати наступні методи контролю навантаження серверу:

• Низька складність (O(1), O(n)):
  можна використовувати прості ліміти запитів і базовий fair scheduling.
• Висока складність (O(n²), O(2ⁿ)):
  кожен новий запит може миттєво «вибити» систему. Тут потрібні жорсткі методи Admission Control (відмова понад ліміти) і, можливо, попередня оцінка складності (cost-based scheduling), щоб одразу відкидати «золотошукачів» із занадто дорогими запитами та, можливо, робити "інверсію" нагрузки з сервера на клієнтів.

Об’єднаний механізм

Об’єднаний механізм: комбінація механізму admission control + feedback‐контролера + fair scheduler (зворотний зв’язок із квотуванням і плануванням).
Це найбільш універсальне рішення, що дає можливість одночасно утримувати завантаження нижче критичного порога, гарантувати справедливий розподіл ресурсів між клієнтами.

Пояснення

Feedback-контролер
– Постійно моніторить метрики (CPU-завантаження, довжину черг, час відгуку).
– Порівнює їх із бажаним рівнем (setpoint) і обчислює помилку (відхилення від цільового стану).

Admission Control (регулювання надходження запитів)
– На підставі команд від feedback-контролера динамічно коригує швидкість прийому нових запитів (наприклад, через Token Bucket або відкладену чергу).
– Якщо завантаження занадто високе, знижує ліміти або відхиляє надлишкові запити → запобігає перевантаженню.

Fair Scheduler (чесне планування)
– Внутрішні черги обробки (CPU, I/O) організовані за WFQ/DRR або CFS-подібним алгоритмом.
– Кожному клієнту (потоці) привласнюється «віртуальний час» чи токени пропорційно його вазі → гарантує справедливий поділ.

Таким чином одна й та сама схема керування потоком + планування водночас:

• Запобігає перевантаженню (через регуляцію admission/rate limiting),
• Забезпечує QoS і справедливий доступ (через fair queuing чи CFS).

Завдання на лабораторну роботу 2

1. Зробити клієнт-серверний додаток на мові javascript, який повинен запускатися в локальній мережі (localhost) та у глобальній мережі (glitch.com, replit.com), на рівні протоколу HTTP, використовуючи методи
   I) GET
   II) POST,
   Додаток повинен тестувати часи подорожі та обробки матриць з числами \(x_{i,j}\) типу double (\(x_{i,j} \in [1..100]\)). Матриці повинні залежно від запиту оброблятися на сервері по-різному:
   a) сервер повинен обчислити за вхідною матрицею матрицю зі зверненими елементами
   b) сервер повинен обчислити за вхідною матрицею звернену матрицю

2. Перевірити роботу програми для розмірів матриць 256x256, 512x512, 1024x1024, 2048x2048, 4096x4096, 8192x8192 та указати класи матриць для якіх можливо виконання всіх запитів за розумний час.

3. Програма має оцінити такі параметри каналу як
   пряму \((\delta_1)\) та зворотню \((\delta_2)\) затримки передачі між термінальними вузлами з'єднання,
   пряму \((B_1)\) та зворотню \((B_2)\) пропускні здатності каналу (Bandwidth = B),
   пряму (\(\tau_1\)) та зворотню (\(\tau_2\)) затримки передавання в каналі (transmission delay = \(\tau\))
   пряму (\(r_1\)) та зворотню (\(r_2\)) відносні затримки каналу
   пряму (\(\eta_1\)) та зворотню (\(\eta_2\)) ефективністі каналу

4. Програма повинна передбачати час \({T_1}_\Sigma\) передачі даних на сервер, час \(T_s\) обробки даних на сервері, час \({T_2}_\Sigma\) передачі оброблених даних із сервера на клієнт та загальний сумарний передбачуваний час \(\tilde T = {T_1}_\Sigma + T_s + {T_2}_\Sigma\) та порівнювати його з реальним часом \(T\) отримання результату після початку запиту клієнта до сервера.

5. Вибрати методи контролю навантаження серверу та взаємодії сервера з клієнтами.

6. Результати представити у вигляді таблиць

7. Проаналізувати отримані результати та зробити висновки

Ресурси

1. Пропускна здатність каналу(Bandwidth=B).
2. Information_rate
3. Bandwidth-Delay Product
4. Керування потоком
5. Перевантаження каналу
6. Контроль перевантаження
7. Протокол зупинки та очікування
8. Sliding Window Protocol
9. Stop and wait and sliding window protocols
10. P2P та розширення
11. High Performance Browser Networking, Ilya Grigorik, online version
12. Transmission Control Protocol
13. TCP_congestion_control
14. Additive increase/multiplicative decrease (AIMD)
15. Dynamical Behavior of Rate-Base Flow Control Mechanisms
16. Балансування навантаження
17. Analysis of the increase and decrease algorithms for congestion avoidance in computer networks.
18. Maximum Segment Size
19. Round Trip Time
20. Сучасний підручник з JavaScript
21. Server overload