Taktsynchronisation in einem Netzwerk mit asymmetrischen Verzögerungen

38

Angenommen, ein Computer verfügt über eine genaue Uhr, die nicht initialisiert wurde. Das heißt, die Uhrzeit auf der Uhr des Computers ist die Echtzeit zuzüglich eines konstanten Versatzes. Der Computer hat eine Netzwerkverbindung und wir möchten diese Verbindung verwenden, um den konstanten Offset zu bestimmen B.

Die einfache Methode besteht darin, dass der Computer eine Abfrage an einen Zeitserver sendet und dabei die Ortszeit notiertB+C1 . Der Zeitserver empfängt die Abfrage zu einem Zeitpunkt T und sendet eine Antwort, die T zurück an den Client, der sie zu einem Zeitpunkt empfängt B+C2. Dann ist B+C1TB+C2 , dh T-C2BT-C1 .

Wenn die Netzwerkübertragungszeit und die Server-Verarbeitungszeit symmetrisch sind, ist B=T-C1+C22 . Soweit mir bekannt ist, gehtNTP, das in freier Wildbahn verwendete Zeitsynchronisationsprotokoll, von dieser Annahme aus.

Wie kann die Präzision verbessert werden, wenn die Verzögerungen nicht symmetrisch sind? Gibt es eine Möglichkeit, diese Asymmetrie in einer typischen Internetinfrastruktur zu messen?

Gilles 'SO - hör auf böse zu sein'
quelle
2
Es gibt ein verwandtes Patent, aber wer möchte das lesen ...
Raphael
@ Raffael Danke. Freundlicherer Google-Link zum US-Patent 7602873 , offizieller USPTO-Link .
Gilles 'SO - hör auf, böse zu sein'
Erste Gedanken: Mit 2 Entities ist es wahrscheinlich unmöglich. Durch die Verwendung von Paaren von Entitäten ist wahrscheinlich eine bessere Synchronisation möglich. Dann können die Uhren verwendet werden, um Einwegzeiten zu messen. n(n2)n
Rgrig
Können Sie die Anwendung / den Kontext klarstellen oder handelt es sich hauptsächlich um eine theoretische Frage?
vzn

Antworten:

10

Unfähigkeit, Asymmetrie zu messen

Nein, Sie können die Asymmetrie nicht messen. Betrachten Sie diese beiden Kommunikationsdiagramme, das erste mit einem negativen Taktversatz und gleichen Verzögerungen und das zweite ohne Taktversatz und mit vollständig asymmetrischen Verzögerungen (aber derselben Umlaufzeit).

Kommunikationsdiagramm

Wichtig ist, dass die beiden Interaktionen aus Sicht von PC und Server exakt identisch sind. Sie erhalten gleichzeitig Nachrichten. Sie senden gleichzeitig Nachrichten.

Sie können weitere Fälle erstellen, indem Sie die PC-Zeitachse "greifen" und verschieben und die Sende- / Empfangspunkte für Nachrichten im Verhältnis zu den jeweiligen Zeitachsen festhalten. Die von Ihnen verursachten Asymmetrien werden durch den Taktversatz genau negiert. Tatsächlich können Sie Nachrichten sogar in eine Richtung ZURÜCKVERKEHREN lassen (solange die Umlaufzeit noch dieselbe ist), und der Server / Client kann dies NOCH nicht feststellen!

Daher ist es unmöglich, Latenzasymmetrien zu messen. Im schlimmsten Fall, wenn Sie keine anderen Informationen als diese Einweglatenzen haben, sind diese positiv und summieren sich auf die Umlaufzeit. Die Genauigkeit der Uhrensynchronisation ist auf die Umlaufzeit beschränkt.

Kann die Zwischeninfrastruktur helfen?

Ob die Zwischeninfrastruktur helfen kann oder nicht, hängt stark von Ihrem theoretischen Modell der Situation ab.

Wenn die Asymmetrie konstant ist und die Zwischeninfrastruktur die Router auf dem Kommunikationspfad zwischen Ihnen und dem Server ist, dann nein. Selbst wenn jeder Router seine Uhr mit dem benachbarten Router synchronisiert hätte, würden sich die Fehler auf dieselbe Weise verschlimmern, als hätten Sie über die Kommunikation zwischen den Routern mit dem Server synchronisiert.

In der realen Welt können Sie sich darauf verlassen, dass Verzögerungen aus architektonischen Gründen etwas symmetrisch sind, dass wiederholte Synchronisationen Asymmetrien aufgrund von Verzögerungen in der Warteschlange (usw.) reduzieren und dass mehrere Kommunikationspfade andere Arten von Asymmetrien reduzieren.

Wenn Sie die Annahmen Ihres Modells irgendwo dazwischen setzen (da es natürlich interessant ist, den Modellraum zu erkunden), erwarte ich, dass das Ergebnis auch irgendwo dazwischen liegen sollte.

Craig Gidney
quelle
Dies sollte eine Antwort auf Ihre Frage sein . Hier frage ich nach einer konkreteren Umgebung, in der wir möglicherweise Hilfe von der zugrunde liegenden Infrastruktur erhalten.
Gilles 'SO - hör auf, böse zu sein'
Ich habe weitere Inhalte für Sie hinzugefügt.
Craig Gidney
Dies scheint mir falsch zu sein. Dies lässt sich daran erkennen, dass die Sende- und Empfangszeiten des PCs zwar gleich sind (Ereignisse auf der oberen Zeitachse stimmen in beiden Fällen überein), die Serverzeiten jedoch unterschiedlich sind (untere Zeile in beiden Fällen). Daher ist die vom NTP-Client berechnete Formel in beiden Fällen unterschiedlich. Dies kann besser verstanden werden, indem die NTP-Werte für jeweils gekennzeichnet werden (wobei t 2 , t 3 Werte sind, die in der Serverzeit aufgezeichnet und an den Client zurückgesendet werden). Wie in meiner Antwort, kann das NTP - Zeitprotokoll tatsächlich ( t 1 - tt1,t2,t3,t4t2,t3(t1t0)(t3t2)
vzn
@vzn Die Serverzeiten bezüglich t Nachrichten sind in beiden Beispielen gleich. Die nach links verschobene Zeitachse des Servers zeigt, dass die Drift der Startuhr unterschiedlich ist. Die Auswirkungen der anfänglichen Taktdrift und der Latenzasymmetrie sind äquivalent. Wenn Sie beide in entgegengesetzte Richtungen anpassen, ist das resultierende Verhalten äquivalent.
Craig Gidney
Nach einer weiteren Untersuchung kann der Client / Server feststellen, ob seine Uhren zumindest außerhalb der Hin- und Rücklaufzeit weit voneinander entfernt sind. Weitere Informationen in der Literaturstelle von Polycos et al., wo sie unterschiedliche "unidirektionale Latenzen" messen, die größer sind als die NTP-Unsicherheit (die weniger als die Umlaufzeit zu NTP-Servern zu sein scheint - dh ~
10
2

Betrachten wir ein Netz von Zeit - Server bekannt ist, dass synchron, , und einen Client - Rechner P .θ={A,B,C}P

Lassen Sie die eine Art und Weise Flugzeit von Maschine seiner X auf Maschine Y , mit der Möglichkeit , dass T X YT Y X .TXYXYTXYTYX

Sei sein , das Maß für die Asymmetrie zwischen Maschinen X und Y .ΔXY=|TXYTYX|XY

Angenommen, die Asymmetrie zwischen zwei Synchronmaschinen kann gemessen werden, indem die Synchronmaschinen damit einverstanden sind, gleichzeitig eine Einwegnachricht aneinander zu senden. Die Differenz der Ankunftszeiten beträgt zwischen diesen Maschinen, dh:Δ

ΔAB=|TABTBA|

ΔBC=|TBCTCB|

ΔCA=|TCATAC|

kann gemessen werden.

Betrachten Sie nun die Flugzeit der Schaltkreise:

, bezeichnet mit C A B ,PABPCAB

, bezeichnet durch C B A .PBAPCBEIN

CEINB=TPEIN+TEINB+TBP

CBEIN=TPB+TBEIN+TEINP

Es sei angenommen, dass die Client-Maschine beide dieser Schaltungen gleichzeitig initiiert und die Differenz der Ankunftszeiten x misst :Px

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

Sowohl & Dgr; A B sind durch zuvor erwähnte Messungen bekannt, so dass die Unbekannten nach links verschoben werden:xΔAB

xΔAB=ΔPA+ΔBP

In ähnlicher Weise für und { C B C , C C B } es kann gezeigt werden , daß:{CAC,CCA}{CBC,CCB}

yΔBC=ΔPB+ΔCP

zΔCA=ΔPC+ΔAP

Inspizieren sorgfältig, stellen wir fest , dass . Die linke Seite enthält aus Messungen bekannte Werte, die rechte Seite enthält 3 Unbekannte in 3 Gleichungen.ΔXYΔYX

Gleichzeitig lösen,

ΔAP=r+st2

ΔBP=rs+t2

ΔCP=tr+s2

woher,

r=xΔAB

s=yΔBC

t=zΔCEIN

Bingo
quelle
Wie umgeht dies das Problem, das meine und andere Antworten haben?
Raphael
Nun, für einen benutze ich 3 Zeitgeber, nicht einen. Und es müssen ungefähr 12 Nachrichten gesendet werden - 6, um die Asymmetrie zwischen den Zeitservern zu ermitteln, und 6, um die Asymmetrie zwischen dem Client und den Servern zu ermitteln. Es handelt sich nicht um einen eindimensionalen Lösungsraum, da sich der Vergleich zwischen drei und keinem Server befindet. Und es geht nicht davon aus, dass die Zeit zurückgehen kann.
Bingo
Es hängt stark von 3 perfekt synchronisierten Zeitservern ab, deren Synchronisation dem Leser als Übung überlassen bleibt. ^^
Bingo
@Raphael lch glaube, ich verstehe Ihren Kommentar jetzt. Die Zeitverschiebung funktioniert nicht, weil sie eingeschränkter ist. z.B. Zeitversetztes WRT P wirkt sich nicht nur die Zeit zwischen A und P aber die circuts auch P A C P , P A B P , P B A P , P C A P , die Unterschiede von denen gemessen und berücksichtigt in der Berechnung. Vielleicht irre ich mich immer noch? Nicht sicher: PAPAPPACP,PABP,PBAP,PCAP
Bingo
0

Wenn Sie nur die Endpunkte steuern. Das kannst du nicht. Siehe Craigs Antwort.

Selbst wenn Sie mehr Maschinen und eine komplexere Gruppe von Computern hinzufügen, wie in Bingos Antwort, können Sie sich auf Maschinen beschränken, bei denen die synchronisierten sofort auf die anderen zugreifen können (Verzögerung = 0).TXY

Beachten Sie, dass Sie, wenn Sie tun , Δ A P = Δ B P = Δ C P = 0 erhalten .TAB=TBC=TCA=0ΔAP=ΔBP=ΔCP=0

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

ΔPA=|TPATAP|ΔPA=TPATAP

ΔXYΔYX

Also was kannst du tun? Senden Sie eine wirklich gute Uhr per Post. ;)

Wenn Sie die Kontrolle über alle Knoten zwischen ihnen haben, können Sie die Zeit für die Verarbeitung jedes Pakets überprüfen und die Verzögerung zwischen jedem aufeinanderfolgenden Paar berechnen, die symmetrisch sein sollte, wenn beide das gleiche physische Medium verwenden.

Möglicherweise müssen Sie die allgemeine Relativitätstheorie berücksichtigen und sich daran erinnern, dass keine Gleichzeitigkeit besteht.

Luiz Afonso
quelle
„Möglicherweise müssen Sie die allgemeine Relativitätstheorie berücksichtigen.“ Nein, das tue ich nicht. Ich bin vollkommen in Ordnung mit einer Lösung, die nur funktioniert, wenn sich alle beteiligten Uhren in einem festen Rahmen befinden. In einem verteilten System besteht eine Relativität, die sich jedoch aus der Netzwerklatenz und nicht aus der Physik ergibt. Die Mathematik ist völlig anders.
Gilles 'SO - hör auf, böse
-1

t0,t1,t2,t3

Der Client hat nach Empfang des Rückpakets alle 4 Werte und berechnet den tatsächlichen Offset. Sobald der relative Versatz zwischen Client und Server berechnet wurde, kann der Versatz "absolute Zeit" synchronisiert werden, dh der Client kann den exakten Versatz des Servers, der gemessen wurde, in Bezug auf seinen lokalen Zeitversatz, dh das "Delta", genau schätzen.

t0
t1
t2
t3

θ=(t1t0)+(t2t3)2

t1t0t3t2

In Netzwerken hängt die Verzögerungszeit von zwei Hauptfaktoren ab, hauptsächlich von der Latenz und der Bandbreite.

  • Die Latenz ist die kurze Verzögerung in Routern beim Senden neuer [kleiner] Pakete und ist bei jedem Router ungefähr eine andere Konstante. Sie kann mit dem Dienstprogramm traceroute gemessen werden .
  • Bandbreite ist die Rate, mit der große Datenmengen gesendet werden können, z. B. "Upload vs. Download-Zeit", und kann auch von Websites zur "Bandbreitenmessung" aus der Ferne gemessen werden.

t1t0t3t2

Ein grundlegender Algorithmus zur Verbesserung der Genauigkeit der Berechnung des in NTP verwendeten Offsets (und zur Korrektur einer gewissen zufälligen Netzwerklatenz) besteht darin, den Vorgang mehrmals zu wiederholen und die "Spitze des Keilstreuungsdiagramms" zu verwenden. Dies ist auf dem "Taktfilteralgorithmus" auf Folie 10 dieser PPT auf NTP von David Mills zu sehen. Siehe auch Taktfilteralgorithmus von Mills. (Beachten Sie, dass es weiterhin zwischen einem einzelnen Server und einem Client verwendet werden kann, obwohl der allgemeine Code so geschrieben wurde, dass mehrere Server zulässig sind.) Dies ist Teil der in NTP-Architektur und -Algorithmen beschriebenen "Minderungsalgorithmen" .

vzn
quelle
1
Die Frage bezieht sich speziell auf den Fall, dass die Latenz nicht symmetrisch ist. Das Ergreifen mehrerer Maßnahmen sagt nichts über die konstante Komponente in der Asymmetrie aus.
Gilles 'SO- hör auf, böse zu sein'
Die Frage enthält eigentlich nicht das Wort "Latenz". Wenn Sie herausfinden möchten, welchen Fall Sie tatsächlich in mathematischer Form anstelle von Wörtern vor Augen haben, insbesondere in Bezug auf die tatsächlichen NTP-Formeln, ist dies sicherlich hilfreich. Die Formeln und Algorithmen können tatsächlich verschiedene Fälle von "Latenz" und "Asymmetrie" messen / behandeln / abdecken.
vzn
C1C2
C1C2
t1,t2
-3

Wenn wir nur Pakete in der Zeit zurückschicken könnten

Bildbeschreibung hier eingeben

B=Tf+TbTf2C1+C22

Annahmen:

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

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

Pratik Deoghare
quelle
1
Diese clevere Lösung wird durch die Annahme einer „typischen Internetinfrastruktur“ ausgeschlossen.
Gilles 'SO - hör auf böse zu sein'
1
@ Gilles Ich weiß. : D
Pratik Deoghare
-4

Hier ist eine Idee, die für mich absolut überzeugend klingt und daher auf dumme Weise absolut falsch sein könnte.

N1N2C1C2δ=C1-C2d12d21

N1T1mN2T2rC2D

T2r-T1m=d12+δT1r-T2m=d21-δD=d12+d21

δ

1] Ich denke, die Annahmen sind natürlich und notwendig. Sie können mit der Hoffnung begründet werden, dass sich die jeweiligen Mengen für die Dauer unseres Synchronisationsversuchs nicht zu stark ändern .

Raphael
quelle
(d12+δ)+(d21δ)(d12+d21)=0
@ Gilles Schade. Wir sollten wahrscheinlich eine Instanz des Irrtums für alle sichtbar lassen?
Raphael
1
Ich kann die falsche Antwort, die ich geschrieben habe, wiederherstellen. Dies könnte aufgrund der Kommentare von Gilles nützlich sein.
Ran G.