Synchronizacja zegara w sieci z asymetrycznymi opóźnieniami

Załóżmy, że komputer ma dokładny zegar, który nie został zainicjowany. Oznacza to, że czas na zegarze komputera to czas rzeczywisty plus pewne stałe przesunięcie. Komputer ma połączenie z siecią i chcemy korzystać z tego połączenia, aby określić stałą przesunięcia $B$ .

Prosta metoda polega na tym, że komputer wysyła zapytanie do serwera czasu, zwracając uwagę na czas lokalny $B + C_1$ . Serwer czasu odbiera zapytanie w czasie $T$ i wysyła odpowiedź zawierającą $T$ powrotem do klienta, który odbiera je w czasie $B + C_2$ . Następnie $B + C_1 \le T \le B + C_2$ , a więc $T - C_2 \le B \le T - C_1$ .

Jeśli czas transmisji w sieci i czas przetwarzania serwera są symetryczne, to $B = T - \dfrac{C_1 + C_2}{2}$ . O ile mi wiadomo,NTP, protokół synchronizacji czasu używany w środowisku naturalnym, działa na tym założeniu.

Jak można zwiększyć precyzję, jeśli opóźnienia nie są symetryczne? Czy istnieje sposób zmierzenia tej asymetrii w typowej infrastrukturze internetowej?

Niemożność zmierzenia asymetrii

Nie, nie można zmierzyć asymetrii. Rozważ te dwa schematy komunikacyjne, pierwszy z ujemnym przesunięciem zegara i równymi opóźnieniami, a drugi bez przesunięcia zegara i całkowicie asymetrycznymi opóźnieniami (ale z tym samym czasem podróży w obie strony).

Należy zauważyć, że z punktu widzenia komputera i serwera obie interakcje są dokładnie identyczne. Otrzymują wiadomości w tym samym czasie. Wysyłają wiadomości w tym samym czasie.

Możesz utworzyć więcej przypadków, „chwytając” oś czasu komputera i „przesuwając” ją, utrzymując punkty wysyłania / odbierania wiadomości w stosunku do ich odpowiednich osi czasu. Wywołane asymetrie są dokładnie zanegowane przez przesunięcie zegara. W rzeczywistości możesz nawet sprawić, że wiadomości będą W TYM CZASIE POWRÓT w jedną stronę (pod warunkiem, że czas podróży w obie strony jest taki sam), a serwer / klient STILL nie może powiedzieć!

Dlatego nie można zmierzyć asymetrii opóźnienia. W najgorszym przypadku, gdy nie masz żadnych informacji poza tym, że opóźnienia w jedną stronę są dodatnie i sumują się do czasu podróży w obie strony, dokładność synchronizacji zegara jest ograniczona do czasu podróży w obie strony.

Czy infrastruktura pośrednia może pomóc?

To, czy pośrednia infrastruktura może pomóc, będzie w dużej mierze zależeć od twojego teoretycznego modelu sytuacji.

Jeśli asymetria jest stała, a infrastruktura pośrednia to routery na ścieżce komunikacyjnej między tobą a serwerem, to nie. Nawet jeśli każdy router zsynchronizuje swój zegar z sąsiednim routerem, błędy spotęgują się w taki sam sposób, jakbyś zsynchronizował się z serwerem poprzez komunikację między routerami.

W prawdziwym świecie można polegać na tym, że opóźnienia są nieco symetryczne ze względów architektonicznych, powtarzane synchronizacje w celu zmniejszenia asymetrii z powodu opóźnień w kolejce (itp.) Oraz wiele ścieżek komunikacyjnych w celu zmniejszenia innych rodzajów asymetrii.

Jeśli umieścisz założenia modelu gdzieś pośrodku (ponieważ interesujące jest zbadanie przestrzeni modelu, oczywiście), spodziewam się, że wynik powinien również znajdować się gdzieś pośrodku.

Rozważmy sieć serwerów czasu wiadomo, że są synchroniczne, i komputer kliencki .$\theta = \{A, B, C\}$$P$

Niech będzie czasem przelotu z maszyny do maszyny w jedną stronę , z możliwością, że . X Y T X Y ≠ T Y $T_{XY}$$X$$Y$$T_{XY}\neq T_{YX}$

Niechjako środek asymetrii pomiędzy maszyny i .$\Delta_{XY} = |T_{XY} - T_{YX}|$$X$$Y$

Rozważmy teraz, że asymetrię między dwoma maszynami synchronicznymi można zmierzyć, gdy maszyny synchroniczne zgodzą się na przesłanie sobie jednokierunkowego komunikatu w tym samym czasie. Różnica w czasie przyjazdu wynosi między tymi maszynami, tj .:$\Delta$

$\Delta_{AB} = |T_{AB} - T_{BA}|$

$\Delta_{BC} = |T_{BC} - T_{CB}|$

$\Delta_{CA} = |T_{CA} - T_{AC}|$

można zmierzyć.

Teraz rozważ czas ucieczki obwodów:

$P \rightarrow A \rightarrow B \rightarrow P$ , oznaczony jako ,$C_{AB}$

$P \rightarrow B \rightarrow A \rightarrow P$ , oznaczony jako .$C_{BA}$

$C_{AB} = T_{PA} + T_{AB} + T_{BP}$

$C_{BA} = T_{PB} + T_{BA} + T_{AP}$

Rozważ komputer kliencki aby zainicjował oba te obwody jednocześnie i mierzy różnicę w czasach przybycia, :$P$$x$

$x = C_{AB} - C_{BA} = \Delta_{PA} + \Delta_{AB} + \Delta_{BP}$

Zarówno jak i są znane z wcześniej wspomnianych pomiarów, więc przenoszenie niewiadomych na lewą stronę:$x$$\Delta_{AB}$

$x - \Delta_{AB} = \Delta_{PA} + \Delta_{BP}$

Podobnie w przypadku i można wykazać, że:$\{C_{AC}, C_{CA}\}$$\{C_{BC}, C_{CB}\}$

$y - \Delta_{BC} = \Delta_{PB} + \Delta_{CP}$

$z - \Delta_{CA} = \Delta_{PC} + \Delta_{AP}$

Sprawdzając uważnie, zauważamy, że . Lewa strona zawiera wartości znane z pomiarów, prawa strona zawiera 3 niewiadome w 3 równaniach.$\Delta_{XY} \equiv \Delta_{YX}$

Jednoczesne rozwiązywanie

$\Delta_{AP} = \frac{r + s - t}{2}$

$\Delta_{BP} = \frac{r - s + t}{2}$

$\Delta_{CP} = \frac{t - r + s}{2}$

gdzie,

$r = x - \Delta_{AB}$

$s = y - \Delta_{BC}$

$t = z - \Delta_{CA}$

Jeśli kontrolujesz tylko punkty końcowe. Nie możesz Zobacz odpowiedź Craiga.

Nawet jeśli dodasz więcej maszyn i bardziej złożony zestaw komputerów, jak w odpowiedzi Bingo, możesz zredukować do samych maszyn, dzięki którym te zsynchronizowane będą miały natychmiastowy dostęp do innych (opóźnienie = 0).$T_{XY}$

Zauważ, że jeśli zrobisz , otrzymasz .$T_{AB} = T_{BC} = T_{CA} = 0$$\Delta_{AP} = \Delta_{BP} = \Delta_{CP} = 0$

Więc co jest nie tak? $x = C_{AB}-C_{BA} = \Delta_{PA}+\Delta_{AB}+\Delta_{BP}$

Δ P A = T P A - T A $\Delta_{PA} = |T_{PA} - T_{AP}|$, nie$\Delta_{PA} = T_{PA} - T_{AP}$

A jeśli użyjesz drugiego, nie możesz użyć założenia (a jeśli nie użyjesz tego, twoje równania końcowe się anulują).$\Delta_{XY} \equiv \Delta_{YX}$

Więc co możesz zrobić? Wyślij naprawdę dobry zegar pocztą. ;)

Lub, jeśli masz kontrolę nad wszystkimi węzłami między nimi, możesz sprawdzić czas przetworzenia każdego pakietu i obliczyć opóźnienie między kolejnymi parami, które powinny być symetryczne, jeśli używają tego samego medium fizycznego w obie strony.

Może być konieczne uwzględnienie ogólnej teorii względności i pamiętaj, że równoczesność nie istnieje.

NTP faktycznie używa 4 pomiarów czasu do obliczenia „przesunięcia”. są one „punktami czasowymi” w podróży powrotnej pakietu między klientem a serwerem z powrotem do klienta, ale można je uznać za przesunięcia czasowe. przyjęto, że przesunięcie czasu może być wyłączone między klientem a serwerem, ale oba mogą dokładnie zliczyć lokalne przesunięcia czasu, które upłynęły.$t_0, t_1, t_2, t_3$

klient po otrzymaniu pakietu zwrotnego ma wszystkie 4 wartości i oblicza rzeczywiste przesunięcie. po obliczeniu względnego przesunięcia między klientem a serwerem przesunięcie „czasu bezwzględnego” można zsynchronizować, tj. klient może dokładnie oszacować dokładne przesunięcie serwerów mierzone względem lokalnego przesunięcia czasu, tj. „delta”.

$t_0$ = czas [przesunięcie] wysłane na klienta = czas [przesunięcie] odebrane na serwerze = czas [przesunięcie] wysłane na serwerze = czas [przesunięcie] odebrane na kliencie
$t_1$
$t_2$
$t_3$

faktyczna formuła to$\theta = {(t_1 - t_0) + (t_2 - t_3) \over 2}$

zwróć uwagę, że ta formuła może obsłużyć przypadek, w którym czas od klienta do serwera nie jest taki sam jak od serwera do klienta (krótszy lub dłuższy).$t_1 - t_0$$t_3 - t_2$

w sieciach opóźnienie wynika z dwóch głównych czynników, głównie z opóźnienia i przepustowości.

• opóźnienie to krótkie opóźnienie routerów w wysyłaniu nowych [małych] pakietów i jest mniej więcej inną stałą na każdym routerze. można to zmierzyć za pomocą narzędzia traceroute .
• szerokość pasma to szybkość, z jaką duże ilości danych mogą być wysyłane, np. „przesyłanie kontra czas pobierania”, i może być również mierzona przez zdalne strony internetowe „mierzące szerokość pasma”.

w wielu nowoczesnych domowych / firmowych połączeniach internetowych szybkość wysyłania jest znacznie mniejsza niż szybkość pobierania i prawdopodobnie wpłynęłoby to na różnicę vs podczas gdy opóźnienia mogą być małe lub nieco podobne między klientem na serwerze a serwerem na serwerze. klient.$t_1 - t_0$$t_3 - t_2$

Podstawowym algorytmem poprawiającym dokładność obliczania przesunięcia stosowanym w NTP (i może korygować pewien stopień losowego opóźnienia sieci) jest wielokrotne powtarzanie procesu i stosowanie „wierzchołka scattergramu klina”. widać to na „algorytmie filtra zegara” na slajdzie 10 tego PPT na NTP autorstwa Davida Millsa. patrz także algorytm filtrowania zegara według Millsa. (zwróć uwagę, że nadal można go stosować między pojedynczym serwerem a klientem, chociaż ogólny kod został napisany, aby zezwolić na wiele serwerów.) Jest to część „algorytmów łagodzących” opisanych w architekturze i algorytmach NTP .

Gdybyśmy tylko mogli wysłać pakiety z powrotem w czasie

Założenia:

$(B+C_2) - T_b = T_f - (B+C_1)$

$T_f - (B + C_2) = (B + C_1) - T_b$

Oto pomysł, który brzmi dla mnie absolutnie przekonująco i dlatego może być całkowicie głupi w niemądry sposób.

Rozważ następujący scenariusz. Mamy dwa węzły i z zegarami odpowiednio i . Dla uproszczenia załóżmy, że zegary biegną z tą samą prędkością; oznaczamy ich różnicę przez która jest stała dla naszych celów. Załóżmy ponadto, że opóźnienia transmisji i są stałe¹.$N_1$$N_2$$C_1$$C_2$$\delta = C_1 - C_2$$d_{1 \to 2}$$d_{2 \to 1}$

Niech wyśle ​​wiadomość oznaczoną znacznikiem czasu do i niech bieżący czas na po otrzymaniu (zrób to samo dla drugiego kierunku). Ponadto zmierz czas podróży w obie strony (w dowolnym węźle) , wysyłając komunikat tam iz powrotem. Teraz skonfiguruj ten układ równań:$N_1$$T_1^m$$N_2$$T_2^r$$C_2$$D$

$\qquad\begin{align*} T_2^r - T_1^m &= d_{1 \to 2} + \delta \\ T_1^r - T_2^m &= d_{2 \to 1} - \delta \\ D &= d_{1 \to 2} + d_{2 \to 1} \end{align*}$

Ponieważ ten system składa się z trzech równań, ma trzy niewiadome i wiemy, że istnieje rozwiązanie, można je rozwiązać. Oczywiście węzły muszą wymieniać swoje pomiary, aby oba mogły obliczyć tę samą wartość dla (w razie potrzeby).$\delta$

1] Myślę, że założenia są naturalne i konieczne. Można je usprawiedliwić nadzieją, że odpowiednie wielkości nie zmieniają się zbytnio w czasie naszej próby synchronizacji.