La mesure d'une façon latence du réseau

Question

Ceci est un casse-tête sur la mesure de la latence du réseau que j'ai créé. Je crois que la solution est qu'il est impossible, mais des amis en désaccord. Je cherche des explications convaincantes ou l'autre manière. (Bien qu'il se pose comme un casse-tête, je pense que cela correspond à ce site en raison de son applicabilité à la conception et l'expérience des protocoles de communication tels que dans les jeux en ligne, sans parler de NTP.)

Supposons que deux robots sont dans deux salles, reliées par un réseau avec différentes latences à sens unique comme le montre le graphique ci-dessous. Lorsque robot Un envoie un message au robot de B il faut 3 secondes pour qu'il arrive, mais quand robot de B envoie un message au robot de A, il faut 1 seconde pour arriver. Les latences ne varient jamais.

Les robots sont identiques et n'ont pas une horloge commune, mais ils peuvent mesurer le passage du temps (par exemple, ils ont chronomètres). Ils ne savent pas lequel d'entre eux est robot Un (dont les messages sont retardés 3s) et qui est robot de B (dont les messages sont retardés par 1s).

Un protocole pour découvrir le temps de retour est:

whenReceive(TICK).then(send TOCK)

// Wait for other other robot to wake up
send READY
await READY
send READY

// Measure RTT
t0 = startStopWatch()
send TICK
await TOCK
t1 = stopStopWatch()
rtt = t1 - t0  //ends up equalling 4 seconds

Y at-il un protocole pour déterminer la façon dont on les retards de voyage? Les robots peuvent découvrir lequel d'entre eux a le message plus envoyer retard?

Answer 1

Le schéma ci-dessous, à partir de un blog j'ai écrit , est une preuve visuelle qu'il est impossible:

Remarquez comment les temps d'arrivée des paquets de chaque côté restent les mêmes, comme le sens unique changement de latences (et même devenir négative!). Le premier paquet atteint toujours le serveur à 1.5s sur l'horloge du serveur, le second atteint toujours le client à 2 secondes sur l'horloge du client, etc. Le contenu du paquet et les heures d'arrivée locales sont les seules choses un protocole pourrait se fonder sur, mais le contenu et l'heure d'arrivée peut être maintenue constante que l'asymétrie varie également en faisant varier le biais d'horloge initiale.

En fait, l'asymétrie dans les latences sens unique apparence exactement comme un décalage d'horloge. Étant donné que le problème que nous ne dit pas commencé connaître le biais de l'horloge initiale ou l'asymétrie de latence à sens unique, et en faisant varier une ressemble à l'autre variant de sorte que leurs effets sont impossibles à distinguer, nous ne pouvons pas séparer leurs contributions afin de résoudre le un sens de l'asymétrie de latence. Il est impossible.

Plus formellement, vous ne pouvez pas résoudre pour des longueurs de bord lorsque donné que les longueurs des cycles. La base du cycle a $ n-1 degrés de liberté $, ce qui correspond à $ n-1 horloge inconnu par rapport à $ skews un des participants. Vous pouvez toujours cacher les latences à sens unique, même quand il y a beaucoup de participants:

Si vous n'êtes pas si visuellement incliné, j'ai un autre argument intuitif. Imaginez un temps portail à une centaine d'années dans l'avenir. Comme vous causez à travers elle à quelqu'un de l'autre côté, vous vous rendez compte que la conversation est tout à fait normal, malgré l'asymétrie de cent ans dans les délais à sens unique. Tout effet observable aurait été évident à cette échelle!

Answer 2

Je pense qu'il est impossible de trouver un moyen de latence tout en comparant chronomètres.

$ A $ envoie B $ $ son horloge $ C_ {A1} $, disons que sa valeur est 5.
$ B $ accuse réception du message au moment de $ C_ {B1} = 1 $
$ A $ envoie à nouveau son horloge, C_ $ {A2} = 9 $ (initial + de latence aller-retour).
$ B $ reçoit au moment C_ $ {B2} = 5 $.
Etc. Ni $ A $ ou $ B $ peut savoir quand l'autre robot a reçu un message par rapport à leurs montres.

Peut-être que si vous faites une question quelqu'un de prime va craquer. Jusque-là, kudos.

Answer 3

J'ai trouvé un moyen de découvrir quel noeud BOTH est qui (à savoir qui a le retard de message plus long) et d'estimer le seul moyen délai de déclenchement. Alors que les autres réponses sont correctes, ils sont seulement envisagent la mesure directe d'horloge approché qui bien sûr ne peut pas fonctionner. Cependant, comme je prouve ici que cela fait partie de l'histoire que comme ici est mon algorithme de travail pour ce qui précède:

On suppose que dans la vie réelle:

• Liens de b largeur de bande finie

• Chaque noeud comporte adresse unique (par exemple A et B)

• Taille des paquets p beaucoup plus petite que la bande passante * produit de latence

• noeuds A et B sont en mesure de remplir le canal

• noeuds ont un au hasard () Fonction

Chaque noeud remplit le canal avec ses propres paquets marqués (A ou B respectivement) OR transmet les paquets qu'il a reçus à partir d'autres noeuds comme suit:

Always fill the channel with my own packets except:
if I receive a packet from another node then
   Randomly choose to 
          either forward that packet from the other node
          or discard that packet and forward my own packet

Explication intuitive Depuis la bande passante de A * Le produit de latence est plus élevé (parce que la latence est plus élevé) A réussira à avoir plus de paquets reçus de B, donc chaque nœud peut savoir qui ils sont dans le diagramme .

En outre, avec suffisamment de temps de convergence de courir au-dessus de l'algorithme le rapport des paquets de A à B va désigner le rapport réel de retard RTT de A à B et, par conséquent souhaité OTT .

SIMULATION TRACE RESULTAT Voici une simulation qui montre ce qui précède et montre comment un convergeant avec succès vers délai de 3 secondes et B convergeant environ 1 seconde de retard:

Explication des figures: Chaque ligne représente 1 seconde de temps (taille de paquet est choisi pour avoir un seconde temps de transmission pour plus de clarté). A noter que chaque noeud peut démarrer l'algo à tout moment pas dans un ordre quelconque ou de temps particulier. Les colonnes sont les suivantes:

• NODE A reçoit: Ce noeud A voit dans son côté de réception (ce qui est également P4 ci-dessous)

• A NODE injectent: Qu'est-ce que le nœud A envoie (notez c'est A, ou au hasard A ou B)

• P1, P2, P3: Les trois paquets qui sont en transit (dans l'ordre) entre A et B (1 seconds moyens de transmission 3 paquets en transit pour un temps de latence de 3)

• NODE B reçoit: Qu'est-ce que B voit dans son côté de réception (ce qui est P3)

• NODE B injectent: Qu'est-ce que B envoie (note c'est B, ou au hasard A ou B par algo)

• P4: Le paquet en transit de B à A (voir aussi P1, P2, P3)

• A compte A: Qu'est-ce que A compte pour les paquets A, il a vu

• A compte B: Qu'est-ce que A compte pour les paquets B, il a vu

• B compte A: Qu'est-ce que B compte pour les paquets A, il a vu

• B compte B: Qu'est-ce que B compte pour les paquets B, il a vu

• A-> B: Le temps de latence qui estime A vers B (rapport de RTT de 4 secondes à base de paquets vu)

• B-> A: La latence que les estimations de B vers A (rapport de RTT de 4 secondes sur la base de paquets vu)

Comme on peut voir les deux nœuds convergent et rester autour de leur vrai temps d'attente (en fait, nous ne voyons pas que A cause secondes sont nécessaires pour Converge mais il ne converge même comportement que B)

Filtres meilleurs pourraient converger plus vite, mais nous pouvons voir clairement comment les deux convergent autour des valeurs correctes pour leurs retards, par conséquent, ils peuvent exactement connaissent savent leur retard (même si je montre leur estimation seulement pour illustration).

En outre, même si les bandes passantes entre les liens sont différentes de la méthode ci-dessus pourrait encore tenir (même si l'on devra penser à plus d'être plus certain) en utilisant des paires de paquets pour comprendre des estimations de bande passante, puis il suffit d'appliquer à la proportion équation ci-dessus.

Conclusisur Nous avons fourni un algorithme pour A et B pour connaître leur position dans le réseau et connaître leur temps d'attente à l'autre noeud pour le diagramme ci-dessus. Nous avons utilisé une méthode d'estimation de mesure du réseau plutôt que des approches fondées sur l'horloge, qui peut en effet pas conduire à une solution en raison de problème de synchronisation d'horloge récursive.

Remarque Je maintenant édité cette réponse fournissant toutes les simulations parce que personne ne me croire je l'ai résolu pour autant que vous pouvez voir dans les premiers commentaires. Espérons que ces résultats quelqu'un peut être plus convaincu et approuver aider tout le monde au moins une erreur ou trouver correct dans ce casse-tête de mesure du réseau!

Answer 4

Ceci est une réponse à @ user3134164 mais est trop grand pour un commentaire.

Voici ma tentative de montrer pourquoi cela ne peut pas fonctionner (approche mathématique). Let appel $ P_x $ la probabilité que $ robot x $ choisit ses propres paquets quand il reçoit l'un des paquets de l'autre robot, et R_x $ $ la probabilité qu'un robot de paquet $ x $ reçu est propre. Après régime stationnaire a été atteint (qui est, après une quantité « infinie » de temps, à savoir toute convergence est fait), nous avons ce qui suit:

• $ R_1 = (1 - R_2) \ fois (1 - P_2) $, de même $ R_2 = (1 - R_1) \ fois (1 - P 1) $. L'idée est que si un robot reçoit l'un de ses propres paquets, cela signifie que l'autre robot a reçu au lieu d'un de ses propres (d'où le 1 $ - R_2 $) et qu'il a quand même choisi de l'envoyer au lieu d'un de ses propres ( d'où le produit de 1 $ - $ P_2)
.
• Cela donne un système de deux équations à deux inconnues, $ R_1 $ et $ R_2 $. Vous voudrez peut-être de le résoudre, mais cela n'a pas vraiment d'importance. En fait, les rapports que vous recherchez sont respectivement $ \ frac {{1} R_1 - R_1} $ et $ \ frac {{1} R_2 - R_2} $. Comme vous pouvez le remarquer, les seuls termes qui apparaissent dans ces expressions sont les probabilités au cours de laquelle chaque robot choisit leur propre paquet sur les autres années. Les latences ne semblent même pas dans la formule tout simplement parce que les deux robots sont de pompage des paquets en permanence, de sorte que les deux sont constamment reçoivent des paquets. Ils seront en effet recevoir différents rapports de paquets, mais il ne dépend que des probabilités aforementionned.

Voilà pourquoi je crois que cela vous mènera nulle part. S'il vous plaît faire le point sur une erreur que je aurais pu faire au cours de ce raisonnement.