Synchronisation d'horloge dans un réseau à retards asymétriques

38

Supposons qu'un ordinateur possède une horloge précise qui n'est pas initialisée. C'est-à-dire que l'heure sur l'horloge de l'ordinateur est le temps réel plus un décalage constant. L'ordinateur est équipé d' une connexion réseau et nous voulons utiliser cette connexion pour déterminer le décalage constant .B

La méthode simple est que l'ordinateur envoie une requête à un serveur de temps, en notant l'heure locale . Le serveur de temps reçoit la requête à un instant et envoie une réponse contenant au client, qui le reçoit à un instant . Puis , c’est-à-dire .B+C1TTB+C2B+C1TB+C2TC2BT-C1

Si l'heure de transmission sur le réseau et l'heure de traitement du serveur sont symétriques, alors . Autant que je sache, NTP , le protocole de synchronisation de l'heure utilisé dans la nature, fonctionne sur cette hypothèse.B=T-C1+C22

Comment améliorer la précision si les retards ne sont pas symétriques? Existe-t-il un moyen de mesurer cette asymétrie dans une infrastructure Internet typique?

Gilles, arrête de faire le mal
la source
2
Il y a un brevet connexe mais qui veut lire ces ...
Raphael
@ Raphaël Merci. Lien Google plus convivial vers le brevet américain 7602873 , lien officiel de l'USPTO .
Gilles 'SO- arrête d'être méchant'
Premières réflexions: c'est probablement impossible avec 2 entités. Utilisation de (n2) paires denentités, une meilleure synchronisation est probablement possible. Ensuite, les horloges peuvent être utilisées pour mesurer des temps d'un voyage.
Rgrig
pouvez-vous clarifier l'application / le contexte ou s'agit-il principalement d'une question théorique?
vzn

Réponses:

10

Incapacité à mesurer l'asymétrie

Non, vous ne pouvez pas mesurer l'asymétrie. Considérez ces deux diagrammes de communication, le premier avec un décalage d’horloge négatif et des retards égaux et le second sans décalage d’horloge et des retards entièrement asymétriques (mais avec le même temps d’aller-retour).

schéma de communication

La chose importante à noter est que, du point de vue du PC et du serveur, les deux interactions sont exactement identiques. Ils reçoivent des messages en même temps. Ils envoient des messages en même temps.

Vous pouvez créer davantage de cas en "saisissant" la timeline du PC et en la "glissant", en maintenant le message points d'envoi / réception fixes par rapport à leurs timelines respectives. Les asymétries que vous causez sont exactement annulées par le décalage d'horloge. En fait, vous pouvez même envoyer les messages en sens inverse dans le temps (dans la mesure où le temps d'aller-retour est toujours le même) et le serveur / client ne peut toujours PAS le savoir!

Il est donc impossible de mesurer les asymétries de latence. Dans le pire des cas, si vous ne disposez d'aucune autre information, les temps de réponse unilatéraux sont positifs et correspondent au temps aller-retour, la précision de la synchronisation d'horloge est limitée au temps aller-retour.

Une infrastructure intermédiaire peut-elle aider?

Le fait que l'infrastructure intermédiaire puisse aider ou non dépendra fortement de votre modèle théorique de la situation.

Si l'asymétrie est constante et que l'infrastructure intermédiaire correspond aux routeurs sur le chemin de communication entre vous et le serveur, alors non. Même si chaque routeur synchronisait son horloge avec le routeur adjacent, les erreurs s'aggraveraient de la même manière que si vous aviez synchronisé avec le serveur via une communication entre les routeurs.

Dans le monde réel, les retards sont quelque peu symétriques pour des raisons d’architecture, des synchronisations répétées pour réduire l’asymétrie due aux retards de mise en file d’attente (etc.) et des voies de communication multiples pour réduire d’autres types d’asymétrie.

Si vous placez les hypothèses de votre modèle entre les deux (car il est intéressant d'explorer l'espace des modèles, bien sûr), j'espère que le résultat devrait également se situer quelque part entre les deux.

Craig Gidney
la source
Cela devrait être une réponse à votre question . Ici, je demande un cadre plus concret, où nous pourrions obtenir de l’aide de l’infrastructure sous-jacente.
Gilles 'SO- arrête d'être méchant'
J'ai ajouté plus de contenu pour vous.
Craig Gidney
cela me semble erroné et on peut le constater en notant que, si les heures d’envoi et de réception du PC sont identiques (les événements de la ligne de scénario supérieure coïncident dans les deux cas), les temps du serveur sont différents (ligne inférieure dans les deux cas) & par conséquent, la formule calculée par le client NTP est différente dans les deux cas. cela peut être mieux compris en étiquetant les valeurs NTP pour dans chaque cas (où t 2 , t 3 sont des valeurs enregistrées dans l’heure du serveur et renvoyées au client). comme dans ma réponse, le protocole de temps NTP peut en effet mesurer et ajuster pour ( t 1 - tt1,t2,t3,t4t2,t3(t1-t0)(t3-t2)
VZN
@vzn Les heures du serveur en ce qui concerne t sont identiques dans les deux exemples. La chronologie du serveur qui se déplace vers la gauche indique que la dérive de l'horloge de départ est différente. Les effets de la dérive d'horloge initiale et de l'asymétrie de latence se trouvent être équivalents. Par conséquent, si vous les ajustez dans des directions opposées, le comportement résultant est équivalent.
Craig Gidney
En poursuivant l’étude, le client / serveur peut dire quand leurs horloges sont très désynchronisées, au moins en dehors du temps aller-retour. plus d'informations dans la référence polycos et al., je cite ci-dessous, où elles mesurent différentes "latences unidirectionnelles" plus grandes que l'incertitude NTP (qui semble être inférieure au temps d'aller-retour des serveurs NTP - c'est-à-dire environ 10 ms)
midi
2

Considérons un réseau de serveurs de temps connus pour être synchrone, , et une machine cliente P .θ={A,B,C}P

Que soit le temps d' un mode de vol de la machine X à la machine Y , avec la possibilité que T X YT Y X .TXYXYTXYTYX

Soit la mesure de l'asymétrie entre la machine X et Y .ΔXY=|TXYTYX|XY

Maintenant, considérons que l'asymétrie entre deux machines synchrones peut être mesurée en faisant en sorte que les machines synchrones acceptent de s'envoyer un message unidirectionnel en même temps. La différence dans les temps d'arrivée est entre ces machines, à savoir:Δ

ΔAB=|TABTBA|

ΔBC=|TBCTCB|

ΔCA=|TCATAC|

peut être mesurée.

Considérons maintenant le temps de vol des circuits:

, noté C A B ,PABPCAB

, noté C B A .PBAPCBA

CAB=TPA+TAB+TBP

CBA=TPB+TBA+TAP

Considérons que la machine cliente lance ces deux circuits simultanément et mesure la différence de temps d’arrivée x :Px

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

Les mesures et Δ A B sont connues par les mesures mentionnées précédemment, ce qui permet de déplacer les inconnues vers la gauche:xΔAB

xΔAB=ΔPA+ΔBP

De la même manière, pour et { C B C , C C B }, on peut montrer que:{CAC,CCA}{CBC,CCB}

yΔBC=ΔPB+ΔCP

zΔCA=ΔPC+ΔAP

Inspectant soigneusement, nous notons que . Les côtés gauche contiennent des valeurs connues à partir de mesures, les côtés droits contiennent 3 inconnues dans 3 équations.ΔXYΔYX

Résoudre simultanément,

ΔAP=r+st2

ΔBP=rs+t2

ΔCP=tr+s2

où,

r=xΔAB

s=yΔBC

t=zΔCA

Bingo
la source
Comment cela contourne-t-il le problème que ma réponse et les autres ont?
Raphaël
Eh bien, pour un je utilise 3 services de chronométrage, pas un. Et il faut quelque chose comme 12 messages à envoyer - 6 pour trouver l'asymétrie entre les serveurs de temps et 6 pour trouver l'asymétrie entre le client et les serveurs. Ce n'est pas un espace de solution à 1 dimension, car il comprend entre 3 serveurs et pas un. Et cela ne suppose pas que le temps puisse reculer.
Bingo
Il repose en grande partie sur 3 serveurs temporels parfaitement synchronisés, dont la synchronisation est laissée à l’exercice. ^^
Bingo
@ Raphaël Je pense que je comprends votre commentaire maintenant. Le décalage horaire ne fonctionne pas car il est plus contraint. par exemple. Décalage dans le temps WRT P ne touche pas seulement le temps entre A et P , mais aussi les circuts P A C P , P A B P , P B A P , P C A P , les différences qui sont mesurées et pris en compte dans la calcul. Peut-être que je me trompe encore? Pas sûr: PAPAPPACP,PABP,PBAP,PCAP
Bingo
0

Si vous ne contrôlez que les points d'extrémité. Tu ne peux pas. Voir la réponse de Craig.

Even if you add more machines and a more complex set of computers, like in Bingo's answer, you can reduce to just to machines making the synchronized ones have instantaneous access to the others (delay TXY = 0).

Notice that if you do TAB=TBC=TCA=0, you get ΔAP=ΔBP=ΔCP=0.

So what's wrong? x=CABCBA=ΔPA+ΔAB+ΔBP

ΔPA=|TPATAP|, not ΔPA=TPATAP

And if you use the second, then you can not use the assumption ΔXYΔYX (and if you don't use this, your final equations cancel each other).

So, what can you do? Send a really good clock through mail. ;)

Or, if you have control over all nodes between them, you can check the time to process each packet and calculate the delay between each consecutive pair, that should be symmetrical, if they use the same physical medium both ways.

You may need to account for general relativity, and remember that simultaneity doesn't exist.

Luiz Afonso
la source
“You may need to account for general relativity” No, I don't. I'm perfectly fine with a solution that only works if all the clocks involved are in a fixed frame. There is relativity in a distributed system, but it comes from network latency, not from physics. Its mathematics are completely different.
Gilles 'SO- stop being evil'
-1

NTP actually uses 4 time measurements t0,t1,t2,t3 to compute the "offset". they are the "time points" in the round trip of the packet from client to server back to client but can be regarded as time offsets. its assumed that the time offset can be off between client and server but that both can count local elapsed time offsets accurately.

the client after receiving the return packet has all 4 values and computes the actual offset. once the relative offset is calculated between client and server, the "absolute time" offset can be synchronized ie the client can accurately estimate the servers exact offset measured wrt its local time offset, ie the "delta".

t0 = time [offset] sent at client
t1 = time [offset] recd at server
t2 = time [offset] sent at server
t3 = time [offset] recd at client

the actual formula is θ=(t1t0)+(t2t3)2

note this formula can handle the case where the time from client to server t1t0 is not the same as from server to client t3t2 (either shorter or longer).

on networks, delay time is due to two major factors, mainly latency and bandwidth.

  • latency is the brief delay in routers on sending new [small] packets and is roughly a different constant at each router. it can be measured with the traceroute utility.
  • bandwidth is the rate at which large amts of data can be sent eg "upload vs download time" and can also be measured by remote "bandwidth measuring" web sites.

in many modern home/business internet connections the upload rate is much smaller than download rates & this would probably affect the t1t0 vs t3t2 difference whereas latency may be small or somewhat similar between client-to-server and server-to-client.

a basic algorithm to improve accuracy of calculating the offset used in NTP (and can correct for some degree of random network latency) is to repeat the process multiple times and use the "apex of the wedge scattergram". this can be seen on the "clock filter algorithm" on slide 10 of this PPT on NTP by David Mills. see also clock filter algorithm by Mills. (note it can still be employed between a single server and client although the general code is written to allow multiple servers.) this is part of the "mitigation algorithms" described in NTP architecture & algorithms.

vzn
la source
1
The question is specifically about the case where the latency is not symmetric. Taking multiple measures won't tell you anything about the constant component in the asymmetry.
Gilles 'SO- stop being evil'
the question does not actually contain the word "latency". if you want to sketch out what case you actually have in mind in math form instead of words esp wrt the real NTP formulas, it would certainly help. the formulas & algorithms can indeed measure/handle/cover various cases of "latency" and "asymmetry".
vzn
C1 et C2 sont les valeurs de latence (je les ai appelées «delay», les deux mots sont synonymes dans ce contexte).
Gilles, arrête de faire le mal du
C1 and C2 are influenced by latency but are not really equal to it. in a sense the scattergram actually plots latency....
vzn
note (maybe its not totally obvious in above acct) the t1,t2 server values are sent in the return packet from server to client.
vzn
-3

If only we could send packets back in time

enter image description here

B=Tf+TbTf2C1+C22

Assumptions:

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

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

Pratik Deoghare
la source
1
This clever solution is ruled out by the assumption of a “typical Internet infrastructure”.
Gilles 'SO- stop being evil'
1
@Gilles I know. :D
Pratik Deoghare
-4

Here is an idea that sounds absolutely convincing to me and might therefore be absolutely wrong in a dumb way.

Consider the following scenario. We have two nodes N1 and N2 with clocks C1 and C2, respectively. For sake of simplicity, let us assume that the clocks run with the same speed; we denote their difference by δ=C1C2 which is constant for our purposes. Let us furthermore assume that transmission delays d12 and d21 are constant¹.

Have N1 send a message timestamped with T1m to N2 and let T2r the current time on C2 upon receiving it (do the same for the other direction). In addition, measure round trip time (on either node) D by sending a message back and forth. Now set up this equation system:

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

As this system consists of three equations, has three unknowns and we know there is a solution, it can be solved. Of course the nodes have to exchange their measurements so that they can both compute the same value for δ (if necessary).

1] I think the assumptions are natural and necessary. They can be justified with the hope that the respective quantities do not change too much for the duration of our synchronisation attempt.

Raphael
la source
(d12+δ)+(d21δ)(d12+d21)=0. There are three equations and three unknowns, but the family of solutions is 1-dimensional. It's the same problem we had with Ran's now-deleted answer and briefly discussed in chat: time is relative; we can't distinguish between delays in transmission and skewed clocks.
Gilles 'SO- stop being evil'
@Gilles Too bad. We should probably leave one instance of the fallacy for all to see?
Raphael
1
I can restore the wrong answer I wrote. It might be useful due to the comments made by Gilles.
Ran G.