Synchronizacja zegara w sieci z asymetrycznymi opóźnieniami

38

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+C1 . Serwer czasu odbiera zapytanie w czasie T i wysyła odpowiedź zawierającą T powrotem do klienta, który odbiera je w czasie B+C2 . Następnie B+C1TB+C2 , a więc TC2BTC1 .

Jeśli czas transmisji w sieci i czas przetwarzania serwera są symetryczne, to B=TC1+C22 . 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?

Gilles „SO- przestań być zły”
źródło
2
Istnieje pokrewny patent, ale kto chce je przeczytać ...
Raphael
@Raphael Thanks. Bardziej przyjazny link Google do patentu USA 7602873 , oficjalny link USPTO .
Gilles „SO- przestań być zły”
Pierwsze myśli: Prawdopodobnie jest to niemożliwe w przypadku 2 jednostek. Używając par jednostek, możliwa jest prawdopodobnie lepsza synchronizacja. Następnie zegary można wykorzystać do pomiaru czasów jednej podróży. (n2)n
rgrig
czy możesz wyjaśnić aplikację / kontekst, czy jest to głównie pytanie teoretyczne?
vzn

Odpowiedzi:

10

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).

schemat komunikacji

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.

Craig Gidney
źródło
To powinna być odpowiedź na twoje pytanie . Tutaj pytam o bardziej konkretne ustawienie, w którym możemy uzyskać pomoc z podstawowej infrastruktury.
Gilles „SO- przestań być zły”
Dodałem dla Ciebie więcej treści.
Craig Gidney
wydaje mi się to błędne i można zauważyć, że chociaż czasy wysyłania i odbierania komputera są takie same (zdarzenia na górnej linii czasu pokrywają się w dwóch przypadkach), czasy serwera są różne (dolna linia w dwóch przypadkach) i dlatego formuła obliczona przez klienta NTP jest inna w obu przypadkach. można to lepiej zrozumieć, oznaczając wartości NTP dla w każdym przypadku (gdzie są wartościami zapisanymi w czasie serwera i wysłanymi z powrotem do klienta). jak w mojej odpowiedzi, protokół czasu NTP może rzeczywiście mierzyć i dostosowywać dlat 2 , t 3 ( t 1 - t 0 ) ( t 3 - t 2 )t1,t2,t3,t4t2,t3(t1t0)(t3t2)
vzn
@vzn Czasy serwera w odniesieniu do t komunikatów są takie same w obu przykładach. Linia czasu serwera przesunięta w lewo przedstawia inny dryft zegara początkowego. Efekty początkowego dryftu zegara i asymetrii opóźnienia są równoważne, więc dopasowanie ich w przeciwnych kierunkach pozwala na zachowanie równoważności wynikowego zachowania.
Craig Gidney
po dalszych badaniach klient / serwer może stwierdzić, kiedy ich zegary są daleko od synchronizacji, przynajmniej poza czasem podróży w obie strony. więcej informacji w policy pol etos i wsp. Cytuję poniżej, gdzie mierzą różne „jednokierunkowe opóźnienia” większe niż niepewność NTP (która wydaje się być krótsza niż czas podróży w obie strony do serwerów NTP - tj. ~ 10ms)
vzn
2

Rozważmy sieć serwerów czasu wiadomo, że są synchroniczne, i komputer kliencki .Pθ={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 YT Y XTXYXYTXYTYX

Niechjako środek asymetrii pomiędzy maszyny i .ΔXY=|TXYTYX|XY

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 .:Δ

ΔAB=|TABTBA|

ΔBC=|TBCTCB|

ΔCA=|TCATAC|

można zmierzyć.

Teraz rozważ czas ucieczki obwodów:

PABP , oznaczony jako ,CAB

PBAP , oznaczony jako .CBA

CAB=TPA+TAB+TBP

CBA=TPB+TBA+TAP

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

x=CABCBA=ΔPA+ΔAB+ΔBP

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

xΔAB=ΔPA+ΔBP

Podobnie w przypadku i można wykazać, że:{CAC,CCA}{CBC,CCB}

yΔBC=ΔPB+ΔCP

zΔCA=ΔPC+Δ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.ΔXYΔYX

Jednoczesne rozwiązywanie

ΔAP=r+st2

ΔBP=rs+t2

ΔCP=tr+s2

gdzie,

r=xΔAB

s=yΔBC

t=zΔCA

Bingo
źródło
W jaki sposób omija to problem, na który mają moją odpowiedź i inni?
Raphael
Cóż, dla jednego używam 3 serwów czasu, a nie jednego. I wymaga wysłania około 12 wiadomości - 6, aby znaleźć asymetrię między serwerami czasu i 6, aby znaleźć asymetrię między klientem a serwerami. Nie jest to jednowymiarowa przestrzeń rozwiązań, ponieważ kompromis jest między 3 serwerami, a nie jednym. I nie zakłada, że ​​czas może cofnąć się.
Bingo,
Opiera się w dużej mierze na 3 doskonale zsynchronizowanych serwerach czasu, których synchronizacja pozostawia się jako ćwiczenie dla czytelnika. ^^
Bingo
@ Rafael Myślę, że rozumiem teraz twój komentarz. Przesunięcie czasu nie działa, ponieważ jest bardziej ograniczone. na przykład. Przesunięcie czasowe wrt wpływa nie tylko na czas między i ale także na , , których różnice są mierzone i uwzględniane w obliczeniach. Może nadal się mylę? Nie jestem pewien: PAPAPPACP,PABP,PBAP,PCAP
Bingo
0

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).TXY

Zauważ, że jeśli zrobisz , otrzymasz .TAB=TBC=TCA=0ΔAP=ΔBP=ΔCP=0

Więc co jest nie tak? x=CABCBA=ΔPA+ΔAB+ΔBP

Δ P A = T P A - T A PΔPA=|TPATAP|, nieΔPA=TPATAP

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ą).ΔXYΔ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.

Luiz Afonso
źródło
„Być może trzeba wziąć pod uwagę ogólną teorię względności” Nie, nie rozumiem. Nie mam nic przeciwko rozwiązaniu, które działa tylko wtedy, gdy wszystkie zaangażowane zegary są w stałej ramie. W systemie rozproszonym istnieje względność, ale wynika ona z opóźnienia sieci, a nie z fizyki. Jego matematyka jest zupełnie inna.
Gilles „SO- przestań być zły”
-1

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.t0,t1,t2,t3

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”.

t0 = 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
t1
t2
t3

faktyczna formuła toθ=(t1t0)+(t2t3)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).t1t0t3t2

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.t1t0t3t2

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 .

vzn
źródło
1
Pytanie dotyczy konkretnie przypadku, w którym opóźnienie nie jest symetryczne. Podejmowanie wielu pomiarów nie powie nic o stałym składniku asymetrii.
Gilles „SO- przestań być zły”
pytanie tak naprawdę nie zawiera słowa „opóźnienie”. jeśli chcesz naszkicować przypadek, który masz na myśli w formie matematycznej zamiast słów, zwłaszcza prawdziwych formuł NTP, z pewnością by to pomogło. formuły i algorytmy mogą rzeczywiście mierzyć / obsługiwać / obejmować różne przypadki „opóźnień” i „asymetrii”.
vzn
C1 i są wartościami opóźnień (nazwałem je „opóźnieniem”, w tym kontekście oba słowa są synonimami). C2
Gilles „SO- przestań być zły”
C1 mają wpływ na i ale tak naprawdę nie są one równe . w pewnym sensie scattergram faktycznie C2
kreśli
Uwaga (być może nie jest to całkowicie oczywiste w powyższym akcie) wartości serwera są wysyłane w pakiecie zwrotnym z serwera do klienta. t1,t2
vzn
-3

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

wprowadź opis zdjęcia tutaj

B=Tf+TbTf2C1+C22

Założenia:

(B+C2)Tb=Tf(B+C1)

Tf(B+C2)=(B+C1)Tb

Pratik Deoghare
źródło
1
To sprytne rozwiązanie wyklucza założenie „typowej infrastruktury internetowej”.
Gilles „SO- przestań być zły”
1
@Gilles Wiem. : D
Pratik Deoghare
-4

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¹.N1N2C1C2δ=C1C2d12d21

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ń:N1T1mN2T2rC2D

T2rT1m=d12+δT1rT2m=d21δD=d12+d21

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).δ

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.

Raphael
źródło
(d12+δ)+(d21δ)(d12+d21)=0 . Istnieją trzy równania i trzy niewiadome, ale rodzina rozwiązań jest jednowymiarowa. To ten sam problem, który mieliśmy z usuniętą teraz odpowiedzią Rana i pokrótce omówioną na czacie: czas jest względny; nie możemy rozróżnić opóźnień w transmisji i przekrzywionych zegarów.
Gilles 'SO - przestań być zły'
@Gilles Szkoda. Powinniśmy chyba zostawić jeden przypadek błędu, aby wszyscy mogli to zobaczyć?
Raphael
1
Mogę przywrócić złą odpowiedź, którą napisałem. Może to być przydatne ze względu na komentarze Gillesa.
Ran G.