Synchronisation d'horloge sans aller/retour

**progfou** · 08/01/2011, 12h14

Bonjour tout le monde,

Ca fait un paquet de temps que je ne suis pas venu par ici...
Et en plus, je viens avec une question !!

Imaginez deux systèmes, l'un fixe, l'autre mobile.
Pour des raisons précises, il faut que l'horloge du mobile soit synchronisée avec celle du système fixe.
Il existe beaucoup d'algorithmes, mais j'ai une contrainte, selon moi, très gênante : je ne peux pas communiquer dans les deux sens.
Le fixe peut envoyer son horloge, mais le mobile ne peut pas parler.
Le délai de transmission n'étant pas connu mais est borné (on connait le min et le max) et relativement constant. Autre contrainte : au démarrage du système, on ignore quelle est sa valeur.

Est-il possible de synchroniser l'horloge du mobile dans ces conditions ??
Et tant qu'à faire, est-il possible d'estimer le délai de transmission ?
Ca me parait plus que compliqué, car de mon point de vue, ça ressemble à une boucle ouverte...
Mais peut-être qu'il y a des "astuces" ?

Merci d'avance pour vos idées !!

**pseudocode** · 08/01/2011, 12h41

Sans communication bidirectionnelle et sans connaitre le délai de transmission, ca ne me parait pas bien possible.

**progfou** · 08/01/2011, 13h01

En imaginant une communication bidirectionnelle, quel est le meilleur algorithme ?
Effectivement, sans aller/retour, je ne vois pas non plus comment c'est possible.

**pseudocode** · 08/01/2011, 13h04

Envoyé par progfou

En imaginant une communication bidirectionnelle, quel est le meilleur algorithme ?
Effectivement, sans aller/retour, je ne vois pas non plus comment c'est possible.

Je dirais le Precision Time Protocol (PTP).

**progfou** · 08/01/2011, 15h15

J'ai omis quelques contraintes...
Donc, pas d'A/R, un délai de transmission variable.
Cependant, on peut considérer que A (fixe) envoie un signal périodique, de période connue, que l'on peut considérer sans biais.
Donc, B reçoit des messages périodiquement, dont il connait l'instant relatif d'envoi. Le temps de propagation est variable, mais entre des bornes fixes et surtout, on peut faire en sorte que B connaisse une valeur probable de ce temps de transmission.

Est-ce que pour autant, une synchronisation est possible ?

**pseudocode** · 08/01/2011, 15h27

Envoyé par progfou

J'ai omis quelques contraintes...
Donc, pas d'A/R, un délai de transmission variable.
Cependant, on peut considérer que A (fixe) envoie un signal périodique, de période connue, que l'on peut considérer sans biais.
Donc, B reçoit des messages périodiquement, dont il connait l'instant relatif d'envoi. Le temps de propagation est variable, mais entre des bornes fixes et surtout, on peut faire en sorte que B connaisse une valeur probable de ce temps de transmission.

Est-ce que pour autant, une synchronisation est possible ?

Si le temps de propagation est variable il n'y a pas grand chose qu'on puisse faire, a part des moyennes ou des rattrapages.

Le protocole PTP a besoin d'un seul échange aller/retour pour estimer l'offset et le délai. Si pendant cet échange l'offset et le délai son constant, on a une bonne estimation de ces 2 paramètres.

**progfou** · 08/01/2011, 16h06

OK, donc en imaginant un A/R à l'init, faire du rattrapage est possible ?

**pseudocode** · 08/01/2011, 18h25

Envoyé par progfou

OK, donc en imaginant un A/R à l'init, faire du rattrapage est possible ?

Il faut faire de A/R de temps en temps pour vérifier que l'offset entre les 2 horloges reste stable ( = que les deux horloges tournent à la meme vitesse )

**progfou** · 08/01/2011, 18h38

Et une fois que les horloges sont synchronisées, il est possible d'avoir une estimation précise du délai de transmission instantané... OK, il faut donc pouvoir avec un échange au moins une fois de temps en temps...

**pseudocode** · 08/01/2011, 19h04

Envoyé par progfou

Et une fois que les horloges sont synchronisées, il est possible d'avoir une estimation précise du délai de transmission instantané... OK, il faut donc pouvoir avec un échange au moins une fois de temps en temps...

Oui. Avec un aller/retour on peut calculer l'offset et le délai.

**Nebulix** · 10/01/2011, 09h59

Ca veut dire quoi "synchronisation" ?
Pour pouvoir constater que 2 horloges sont synchronisées, il faut soit qu'elles aient un protocole pour se mettre d'accord, soit qu'elles soient observées par un système tiers.
P.S. Un certain Albert E a beaucoup étudié cette question, il y a 105 ans.

**progfou** · 11/01/2011, 19h11

Envoyé par pseudocode

Oui. Avec un aller/retour on peut calculer l'offset et le délai.

Hmmm, pas tout à fait... sauf si quelque chose m'échappe

.
Si on prend le schéma sur Wikipedia :

On connait T1, T'1, T2, T'2 (et même T3, T'3).
Soit :
T'1-T1 = o + delta_1
T'2-T2 = o + delta_2
(T'3-T3 = o + delta_3)

delta_1 = delta + erreur_1
delta_2 = delta + erreur_2
(delta_3 = delta + erreur_3)

On pourra approcher o seulement à |erreur_1+erreur_2|/2.
Idem pour delta.

On ne peut pas faire mieux ??

**pseudocode** · 11/01/2011, 22h58

T'1-T1 = offset_1 + delay_1
T'2-T2 = offset_2 + delay_2

"One assumption is that this exchange of messages happens over a period of time so small that this offset can safely be considered constant over that period."

offset_1 = -offset_2

(attention, les signes sont opposés)

"Another assumption is that the transit time of a message going from the master to a slave is equal to the transit time of a message going from the slave to the master."

delay_1 = delay_2

==>

(1) T'1-T1 = offset + delay
(2) T'2-T2 = -offset + delay

(1)+(2) --> (T'1-T1)+(T'2-T2) = 2*delay
(1)-(2) --> (T'1-T1)-(T'2-T2) = 2*offset

delay = ((T'1-T1)+(T'2-T2))/2
offset = ((T'1-T1)-(T'2-T2))/2

**progfou** · 12/01/2011, 07h23

On est d'accords. Mais si les deux délais ne sont pas égaux, on ne peut pas faire le calcul sans erreur. Aucune solution ne permettrait de contrer cela (au moins en partie) ?

**pseudocode** · 12/01/2011, 11h34

Envoyé par progfou

On est d'accords. Mais si les deux délais ne sont pas égaux, on ne peut pas faire le calcul sans erreur. Aucune solution ne permettrait de contrer cela (au moins en partie) ?

Une fois l'offset/delai évalué avec la méthode précédente, on peut affiner les choses.

Ce que croit le serveur, c'est que la liaison est symétrique:

serveur --- delay --> client
serveur <-- delay --- client

Si le serveur envoie un message a l'heure Ta, le client devrait le recevoir à l'heure Ta+offset+delay

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
Ta .......... Ta + offset
|  ---        |
|     ---     |
|        ---> Ta + offset + delay
|             |

En réalité, la liaison est asymétrique:

serveur --- d1 --> client
serveur <-- d2 --- client

Experience:

Le serveur envoie un message contenant son heure et son estimation de la liaison symétrique : (Ta,offset,delay)

En théorie, le client devrait recevoir le message à l'heure T'a_theoric = Ta + offset + delay
En réalité, le client reçoit le message à l'heure T'a_observed = Ta + offset + d1

Le client peut alors calculer l'erreur d'estimation du délai :

T'a_observed - T'a_theoric = (Ta + offset + d1) - (Ta + offset + delay) = d1-delay

==> d1 = T'a_observed - T'a_theoric + delay

Le delai moyen (qui a été correctement évalué) est de (d1+d2)/2 = delay

==> d2 = 2*delay - d1

**progfou** · 12/01/2011, 11h40

Donc, au pire, on fait une erreur d'estimation de |d2-d1|/2.
Et cette erreur sera faite à la fois sur l'offset et sur le délai estimé.
Too bad :/

Et en utilisant le retour (T'3, T3) on peut affiner. Mais on ne pourra pour autant jamais avoir un offset nul (donc une sychro "parfaite"), même en répétant ce processus...

**pseudocode** · 12/01/2011, 11h44

Envoyé par progfou

Donc, au pire, on fait une erreur d'estimation de |d2-d1|/2.
Et cette erreur sera faite à la fois sur l'offset et sur le délai estimé.
Too bad :/

Et en utilisant le retour (T'3, T3) on peut affiner. Mais on ne pourra pour autant jamais avoir un offset nul (donc une sychro "parfaite"), même en répétant ce processus...

Je pense meme qu'il a été prouvé que ca ne pouvait pas être possible.

(google: "Fundamentals of Large Sensor Networks: Connectivity, Capacity, Clocks and Computation")

**progfou** · 12/01/2011, 11h48

Merci pour le lien

.

On peut peut-être approcher d'un minimum ?

**pseudocode** · 12/01/2011, 12h02

Envoyé par progfou

Merci pour le lien

.

On peut peut-être approcher d'un minimum ?

En faisant des boucles d'estimation d'offset, puis de délai (d1/d2), ... On doit approcher d'un minimum. Je crois me souvenir qu'il est calculé dans le document que j'ai cité.

Si tu as vraiment besoin d'une précision si poussée, le plus simple c'est de tirer un fil entre le client/serveur et de générer un signal d'horloge.