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

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

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

Для виконання контрольної роботи Ви повинні скопіювати текст завдання (у форматі md ) та створити, використовуючи цей текст, на хостингу hack.md лист контрольної роботи із зазначенням Вашого прізвища, імені та по батькові.

Відразу після закінчення контрольної роботи ви маєте надіслати посилання на опублікований лист з розв'язаннями. Лист повинен бути опублікований з правами читання та правки signed-in users.
Остаточну оцінку буде поставлено після співбесіди у вибраних питаннях на знання записаних на Вашому листі контрольної роботи відповідей.

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

$$\begin{array}{}\text{(𝜏|1)}& \tau (t)={\theta }_0+\sigma \cdot t={\theta }_0+(1+ϵ)\cdot t\end{array}$$
де

${\theta }_0$ - розузгодження комп'ютерного годинника з ідеальним годинником у початковий момент,

$\sigma \approx 1$ - швидкість ходу комп'ютерного годинника щодо ідеального годинника, починаючи з початкового моменту,

$|ϵ|\ll 1$- дрейф (відхилення швидкості) комп'ютерного годинника щодо ідеального годинника, починаючи з початкового моменту.

$$\begin{array}{}\text{(}{𝜏}_1,{𝜏}_2\text{|2)}& \begin{array}{r}{\tau }_1(t)={\theta }_1+{\sigma }_1\cdot t={\theta }_1+(1+{ϵ}_1)\cdot t,\\ {\tau }_2(t)={\theta }_2+{\sigma }_2\cdot t={\theta }_2+(1+{ϵ}_2)\cdot t\end{array}\end{array}$$

$$\begin{array}{}\text{(}{\theta }_{12}\text{|3)}& \begin{array}{r}{\theta }_{1,2}(t)={\tau }_1(t)-{\tau }_2(t)=({\theta }_1-{\theta }_2)+({\sigma }_1-{\sigma }_2)t=\\ =({\theta }_1-{\theta }_2)+({ϵ}_1-{ϵ}_2)t={\theta }_0+\epsilon t\end{array}\end{array}$$
де

${\theta }_0$ -початкова відносна неузгодженість, а

$\epsilon$ - дрейф другого годинника відносно до першого (

$|\epsilon |\ll 1$).

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

---

---

---

---

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

---

---

---

---

• Якщо ми знаємо
  ${\tau }_1(t)$,
  ${\tau }_2(t)$,
  $\theta$,
  $\epsilon$, як дізнатися час атомного годинника?

---

---

---

---

• Якщо ми знаємо
  ${\theta }_1$,
  ${ϵ}_1$,
  ${\theta }_2$,
  ${ϵ}_2$, за якою формулою можна обчислювати залежність показань часу другого годинника від першого:
  ${\tau }_2({\tau }_1)$?

---

---

---

---

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

---

---

---

---

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

У досить простих сценаріях узгодження часу можна знехтувати

$\epsilon$-дрейфом пар годинників і оцінювати тільки початкову відносну неузгодженість

${\theta }_0$ годинників .

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

---

---

---

---

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

Початкова оцінка

${\tilde{\theta }}_0=T_0-{\tau }_0$ поточної неузгодженості між часовими помітками клієнта та сервера:

$$\begin{array}{}\text{(}{\tilde{\theta }}_0\text{|1)}& {\tilde{\theta }}_0=\frac{(T_1-{\tau }_0)+(T_2-{\tau }_3)}{2}\end{array}$$
де

${\tau }_0$ — часова помітка клієнта про передачу пакета запиту,

$T_1$ — часова помітка сервера прийому пакета запиту,

$T_2$ — часова помітка сервера передачі пакету у відповідь,

${\tau }_3$ — часова помітка клієнта про прийом пакету у відповідь.

• Що означають показання
  $T_0$,
  ${\tau }_1$,
  ${\tau }_2$,
  $T_3$ годинників ?

---

---

---

---

$$\begin{array}{}\text{(}{\tilde{\theta }}_0\text{|3)}& \{\begin{array}{}{\tau }_0+{\tilde{\theta }}_0+\frac{1}{2}\mathrm{\Delta }=T_1\\ {\tau }_3+{\tilde{\theta }}_0-\frac{1}{2}\mathrm{\Delta }=T_2\end{array}\end{array}$$

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

---

---

---

---

Для каналів з асиметричними затримками можна переписати систему рівнянь (

${\tilde{\theta }}_0$|3) як системи з обмеженням (θ,p|4):

$$\begin{array}{}\text{(θ,p|4)}& \{\begin{array}{}{\tau }_0+{\theta }_0+p\cdot \mathrm{\Delta }=T_1\\ {\tau }_3+{\theta }_0-(1-p)\cdot \mathrm{\Delta }=T_2\\ 0<p<1,\end{array}\end{array}$$
де

$p$ - параметр асиметрії (для симетричних затримок

$p=1/2$)

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

---

---

---

---

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

Якщо нам відомі пряма (forward)

${\delta }_f$ і зворотна (backward)

${\delta }_b$ затримки (

$\mathrm{\Delta }={\delta }_f+{\delta }_b$), то коефіцієнт асиметрії

${\xi }_a$ визначається як

$$\begin{array}{}\text{(}{\xi }_a\text{|5)}& {\xi }_a=\frac{{\delta }_f}{{\delta }_b}\end{array}$$
Для симетричних затримок

${\xi }_a=1$.

• В якому діапазоні може бути величина
  ${\xi }_a$?

---

---

---

---

Маючи параметр

$p$, коефіцієнт асиметрії затримок

${\xi }_a$ можна визначити як

$$\begin{array}{}\text{(}{\xi }_a\text{|6)}& {\xi }_a=\frac{p}{1-p}\end{array}$$

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

---

---

---

---

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

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

---

---

---

---

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

---

---

---

---

• Якою може бути мінімальна помилка
  $|\partial \theta |$ визначення поточної неузгодженості
  ${\tilde{\theta }}_0$ за формулою (
  ${\tilde{\theta }}_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\mathrm{mod}2),$$
де d – ваш день народження.

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

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

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