2024_: Комп'ютерні системи і мережі. Контрольна робота. Прізвище, ім'я та по батькові.

• 2024_: Комп'ютерні системи і мережі. Контрольна робота. Прізвище, ім'я та по батькові.
• Тема. Синхронізація часу
  • Афінні моделі комп'ютерних годинників та неузгодженості
  • Простий протокол синхронізації годинника
  • Початкова оцінка поточної неузгодженості
    • Коефіцієнт асиметрії
  • Практичне завдання
    • Вибір варіанта практичного завдання
• Інформаційні матеріали

Тема. Синхронізація часу

Афінні моделі комп'ютерних годинників та неузгодженості

\[ \tau(t) = \theta_0 + \sigma\cdot t = \theta_0 + (1+\epsilon)\cdot t \tag{𝜏|1} \]
де
\(\theta_0\) - розузгодження комп'ютерного годинника з ідеальним годинником у початковий момент,
\(\sigma \approx 1\) - швидкість ходу комп'ютерного годинника щодо ідеального годинника, починаючи з початкового моменту,
\(|\epsilon| \ll 1\)- дрейф (відхилення швидкості) комп'ютерного годинника щодо ідеального годинника, починаючи з початкового моменту.
\[ \begin{align} \tau_1(t) = \theta_1 + \sigma_1\cdot t = \theta_1 + (1+\epsilon_1)\cdot t ,\\ \tau_2(t) = \theta_2 + \sigma_2\cdot t = \theta_2 + (1+\epsilon_2)\cdot t \end{align} \tag{$𝜏_1,𝜏_2$|2} \]
\[ \begin{align} \theta_{1,2}(t) = \tau_1(t) - \tau_2(t) = (\theta_1 - \theta_2) + (\sigma_1-\sigma_2)t =\\ =(\theta_1 - \theta_2) + (\epsilon_1-\epsilon_2)t =\theta_0 + \varepsilon t \end{align} \tag{$θ_{12}$|3} \]
де \(\theta_0\) -початкова відносна неузгодженість, а \(\varepsilon\) - дрейф другого годинника відносно до першого (\(|\varepsilon|\ll 1\)).

• Чи є функції \(\tau(t)\) і \(\theta_{1,2}(t)\) монотонно зростаючими? Доведіть.

• Чи є показання реальних кварцових годинників та неузгодженість пари реальних кварцових годинників монотонними функціями? Обґрунтуйте.

• Якщо ми знаємо \(\tau_1(t)\), \(\tau_2(t)\), \(\theta\), \(\varepsilon\), як дізнатися час атомного годинника?

• Якщо ми знаємо \(\theta_1\), \(\epsilon_1\), \(\theta_2\), \(\epsilon_2\), за якою формулою можна обчислювати залежність показань часу другого годинника від першого: \(\tau_2(\tau_1)\)?

• Запропонуйте процедуру (метод) визначення \(\varepsilon\)-дрейфу другого годинника відносно до першого

Простий протокол синхронізації годинника

У досить простих сценаріях узгодження часу можна знехтувати \(\varepsilon\)-дрейфом пар годинників і оцінювати тільки початкову відносну неузгодженість \(\theta_0\) годинників .

• Опишіть Ваші варіанти таких сценаріїв.

Початкова оцінка поточної неузгодженості

Початкова оцінка \(\tilde\theta_0 = T_0 - \tau_0\) поточної неузгодженості між часовими помітками клієнта та сервера:
\[ \tilde\theta_0= \frac{(T_1-\tau_0)+(T_2-\tau_3)}{2} \tag{$\tildeθ_0$|1} \]
де
\(\tau_0\) — часова помітка клієнта про передачу пакета запиту,
\(T_1\) — часова помітка сервера прийому пакета запиту,
\(T_2\) — часова помітка сервера передачі пакету у відповідь,
\(\tau_3\) — часова помітка клієнта про прийом пакету у відповідь.

• Що означають показання \(T_0\), \(\tau_1\), \(\tau_2\), \(T_3\) годинників ?

\[ \left\{ \begin{array} \, \tau_0 +\tilde\theta_0 + \frac{1}{2}\Delta=T_1 \\ \, \tau_3 +\tilde\theta_0 - \frac{1}{2}\Delta=T_2 \tag{$\tildeθ_0$|3} \end{array} \right. \]

• Поясніть побудову системи лінійних рівнянь (\(\tildeθ_0\)|3)

Для каналів з асиметричними затримками можна переписати систему рівнянь (\(\tildeθ_0\)|3) як системи з обмеженням (θ,p|4):
\[ \left\{ \begin{array} . \tau_0 +\theta_0+p\cdot\Delta=T_1 \\ \;\;\;\tau_3 +\theta_0-(1-p)\cdot\Delta=T_2 \\ \tag{θ,p|4} 0 < p < 1, \end{array} \right. \]
де \(p\) - параметр асиметрії (для симетричних затримок \(p=1/2\))

• Чому не можна розв'язати систему (θ,p|4) безпосередньо вiдносно до \(\theta_0\) та \(p\)?

Коефіцієнт асиметрії

Якщо нам відомі пряма (forward) \(\delta_f\) і зворотна (backward) \(\delta_b\) затримки (\(\Delta=\delta_f+\delta_b\)), то коефіцієнт асиметрії \(\xi_a\) визначається як
\[ \xi_a = { \delta_f \over \delta_b } \tag{$ξ_a$|5} \]
Для симетричних затримок \(\xi_a=1\).

• В якому діапазоні може бути величина \(\xi_a\)?

Маючи параметр \(p\), коефіцієнт асиметрії затримок \(\xi_a\) можна визначити як \[ \xi_a = { p \over 1-p } \tag{$ξ_a$|6} \]

• Як було отримано формулу \((ξ_a|6)\)?

Уточнення величини асиметрії - це важке завдання, навіть із використанням односторонніх протоколів, таких, як UDP і протоколів, заснованих на них, наприклад, WebRTC, якщо відсутні заздалегідь синхронізовані пари атомних годинників

• Обґрунтувати цю тезу

• Доведіть, що помилка \(|\partial\theta|=|\tilde\theta_0-\theta|\) визначення поточної неузгодженості за формулою (\(\tildeθ_0\)|1), якщо припущення про симетричність затримок виявилося хибним, не перевищує \({1 \over 2}\left|{\xi_a-1\over \xi_a +1}\right|\Delta\)

• Якою може бути мінімальна помилка \(|\partial\theta|\) визначення поточної неузгодженості \(\tilde\theta_0\) за формулою (\(\tildeθ_0\)|1), якщо припущення про симетричність затримок виявилося хибним, але нам відомий коефіцієнт асиметрії \(\xi_a\)? Доведіть!

• За якою формулою можна розрахувати помилку \(|\partial\theta|=|\tilde\theta_0-\theta|\) визначення поточної неузгодженості \(\theta_0\) годинників, якщо нам відомий параметр асиметрії \(p\)?

• За якою формулою можна розрахувати початкове неузгодження \(\theta_0\)
  годинників, якщо нам відомий параметр асиметрії \(p\) ?

• За якою формулою можна розрахувати початкове неузгодження \(\theta_0\)
  годинників, якщо нам відомий коефіцієнт асиметрії \(\xi_a\)?

Практичне завдання

Розглянемо мережну програму, в якій два клієнти (js програми всередині браузерів), що знаходяться, можливо, дуже далеко один від одного і від сервера, обмінюються своїм поточним часом, використовуючи тільки HTTP GET fetch() на боці браузерів.

• Варіант 1. Опишіть механізм і напишіть фрагменти коду на клієнтах і сервері, відповідальних за якомога більш своєчасну передачу свого часу першим клієнтом, що підключився, - другому за запитом другого клієнта. Які основні проблеми, пов'язані з використаним протоколом, Вам необхідно вирішити для виконання завдання?

• Варіант 2. Опишіть механізм і напишіть фрагменти коду на клієнтах і сервері, що відповідають якомога більш своєчасну передачу свого часу другим клієнтом, що підключився, - першому. Які основні проблеми, пов'язані з використаним протоколом, Вам необхідно вирішити для виконання завдання?

• server.js

var express = require('express');
...
...
...

• client1 HTML

   <div id=Info></div>
   ....
   ....
   ....

• client1 javascript

 ...
 ...
 // get time
 setInterval(function () {
                          ....
                          ....
                          }, 100);
...                          

• client2 HTML

   <div id=Info></div>
   ....
   ....
   ....

• client2 javascript

 ...
 ...
 // req time
 ...                          
 ...

Вибір варіанта практичного завдання

Вибрати варіант за формулою
\[v = 1 + (d\mod 2),\]
де d – ваш день народження.

Якщо ви встигли запрограмувати Ваше рішення, треба надати посилання на invite Вашого проекту

Інформаційні матеріали

2024: Комп'ютерні системи і мережі. 3. Узгодження стану. Синхронізація часу