Mesurer la latence du réseau unidirectionnel

20

Il s'agit d'un puzzle sur la mesure de la latence du réseau que j'ai créé. Je crois que la solution est que c'est impossible, mais les amis ne sont pas d'accord. Je cherche des explications convaincantes de toute façon. (Bien qu'il soit posé comme un puzzle, je pense qu'il convient à ce site Web 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 se trouvent dans deux pièces, connectés par un réseau avec des latences unidirectionnelles différentes, comme indiqué dans le graphique ci-dessous. Lorsque le robot A envoie un message au robot B, cela prend 3 secondes pour qu'il arrive, mais lorsque le robot B envoie un message au robot A, il faut 1 seconde pour arriver. Les latences ne varient jamais.

Les robots sont identiques et n'ont pas d'horloge commune, bien qu'ils puissent mesurer le passage du temps (par exemple, ils ont des chronomètres). Ils ne savent pas lequel est le robot A (dont les messages sont retardés de 3s) et lequel est le robot B (dont les messages sont retardés de 1s).

Un protocole pour découvrir le temps d'aller-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

Existe-t-il un protocole pour déterminer les retards aller simple? Les robots peuvent-ils découvrir lequel d'entre eux a le délai d'envoi de message le plus long?

Deux robots un réseau asymétrique

Craig Gidney
la source
5
Voir Synchronisation d'horloge dans un réseau avec des retards asymétriques (qui demande quelque chose de faisable avec une infrastructure Internet typique). Je pense que d'après ce que nous avons vu en discutant de mauvaises réponses à cette question, la réponse à votre question est que c'est impossible.
Gilles 'SO- arrête d'être méchant'
Faut-il fusionner les questions, ou sont-elles suffisamment différentes dans l'objectif pour rester séparées?
Craig Gidney
Non, ce sont des questions différentes. Votre question établit qu'il est impossible dans un environnement à deux machines avec un simple passage de message. J'espère des solutions basées sur, disons, des informations de latence disponibles pour certains liens intermédiaires sur la route entre le client et le serveur et ayant un moyen de propager ces informations au client.
Gilles 'SO- arrête d'être méchant'
3
S'il y avait un moyen de le faire, la théorie de la relativité d'Einstein ne fonctionnerait pas, car elle dépend du fait que deux observateurs qui sont séparés comme un espace et qui ont des latences unidirectionnelles inconnues ne peuvent pas s'entendre sur un moment approprié.
Peter Shor
NTP autorise / implémente en effet la mesure de ce retard différentiel en fonction des machines qui s'échangent leur temps et pas seulement du suivi de l'heure d'envoi / réception de leurs propres msgs mais aussi des autres serveurs via le contenu des msg, voir réponse sur la question gilles
vzn

Réponses:

14

Le diagramme suivant, tiré d' un article de blog que j'ai écrit , est une preuve visuelle qu'il est impossible:

Glissement du décalage d'horloge exactement compensé par l'asymétrie de latence

Remarquez comment les heures d'arrivée des paquets de chaque côté restent les mêmes, même si les latences unidirectionnelles changent (et deviennent même négatives!). Le premier paquet atteint toujours le serveur à 1,5 s sur l'horloge du serveur, le second atteint toujours le client à 2 s sur l'horloge du client, etc. Le contenu du paquet et les heures d'arrivée locales sont les seules choses sur lesquelles un protocole pourrait être basé, mais le le contenu et les heures d'arrivée peuvent être maintenus constants car l'asymétrie varie en variant également le décalage d'horloge initial.

Fondamentalement, l'asymétrie dans les latences unidirectionnelles ressemble exactement à un décalage d'horloge. Étant donné que le problème indique que nous ne commençons pas par connaître le décalage d'horloge initial ou l'asymétrie de latence unidirectionnelle, et que la variation de l'une ressemble à la variation de l'autre, de sorte que leurs effets sont indiscernables, nous ne pouvons pas séparer leurs contributions afin de résoudre le problème. asymétrie de latence unidirectionnelle. C'est impossible.

Plus formellement, vous ne pouvez pas résoudre les longueurs de bord lorsque seules les longueurs des cycles sont données. La base du cycle a degrés de liberté, correspondant à n - 1 biais d'horloge inconnus par rapport à l'un des participants. Vous pouvez toujours masquer les latences unidirectionnelles, même lorsqu'il y a de nombreux participants:n-1n-1

Mal de mer

Si vous n'êtes pas si incliné visuellement, j'ai un autre argument intuitif. Imaginez un portail temporel vers une centaine d'années dans le futur. En discutant avec quelqu'un de l'autre côté, vous réalisez que la conversation est tout à fait normale malgré l'asymétrie centenaire des retards à sens unique. Tout effet observable aurait été évident à cette échelle!

Craig Gidney
la source
Quelle est votre opinion à ce sujet? software.internet2.edu/owamp
CMCDragonkai
@CMCDragonkai Gardez à l'esprit que l'énoncé du puzzle est plus restrictif que la réalité. En pratique, vous avez des options telles que la mesure de la longueur des lignes de fibre optique, la journalisation à des points intermédiaires, l'utilisation de la connaissance de la topologie du réseau, le transport lent d'une horloge d'un endroit à l'autre, etc. Par exemple, les satellites GPS se déplacent sur des orbites connues et vous peut l'utiliser pour supprimer les degrés de liberté lors de la résolution. Donc, à première vue, je ne vois aucun problème avec un outil de ping unidirectionnel, tant qu'il ou les horloges sur lesquelles il s'appuie exploitent certaines de ces informations tertiaires douces et douces.
Craig Gidney
Oh dans ce cas, pourriez-vous alors mettre à jour votre réponse avec des solutions de contournement possibles?
CMCDragonkai
@CMCDragonkai Les avoir dans les commentaires suffit. Ils dépassent le cadre du puzzle.
Craig Gidney
La latence unidirectionnelle est importante, par exemple pour la mise en réseau de jeux. De plus, tout le monde dit impossible, mais je peux facilement résoudre le casse-tête sur le papier - une fois que vous synchronisez les horloges, tout ce que vous faites est de mesurer le délai de A à B en envoyant le temps de A à B, avec A-> B délai égal à B's time - A's sent time, et B-> A étant égal àlatency - A->B delay
Llamageddon
1

Je pense qu'il est impossible de comprendre la latence à sens unique simplement en comparant les chronomètres.

UNEBCUNE1
BCB1=1
UNECUNE2=9
BCB2=5
UNEB

Peut-être que si vous en faites une question de prime, quelqu'un la fera craquer. Jusque-là, bravo.

rath
la source
0

J'ai trouvé un moyen de DÉCOUVRIR quel nœud est qui (c'est-à-dire qui a le délai de message le plus long) ET d'estimer le délai de déplacement aller simple. Bien que les autres réponses soient correctes, elles envisagent UNIQUEMENT une mesure d'horloge directe qui, bien sûr, ne peut pas fonctionner. Cependant, comme je le prouve ici, ce n'est qu'une partie de l'histoire, car voici mon algorithme de travail pour ce qui précède:

Supposons que dans la vraie vie:

  • Liens de bande passante finie b

  • Chaque nœud a une adresse unique (par exemple A et B)

  • Taille de paquet p beaucoup plus petite que la latence de la bande passante *

  • Les nœuds A et B sont capables de remplir le canal

  • Les noeuds ont un aléatoire () fonction

Chaque nœud remplit le canal avec ses propres paquets (marqués respectivement A ou B) OU transfère les paquets qu'il a reçus d'autres nœuds 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 Étant donné que le produit de latence de la bande passante * de A est plus élevé (car la latence est plus élevée), A réussira à recevoir plus de paquets que B, donc chaque nœud peut savoir qui ils sont dans le diagramme .

En outre, avec un temps de convergence suffisant pour exécuter l'algorithme ci-dessus, le rapport des paquets de A à B dénotera le rapport réel du délai RTT de A à B et donc l'OTT souhaité .

TRACE DE RÉSULTAT DE SIMULATION Voici une simulation qui prouve ce qui précède et montre comment A converge avec succès vers un retard de 3 secondes et B converge autour d'un retard de 1 seconde:

Premières secondes de simulation

Secondes de simulation suivantes

Explication des figures: Chaque ligne représente 1 seconde de temps (la taille du paquet est choisie pour avoir 1 seconde de temps de transmission pour plus de clarté). Notez que chaque nœud peut démarrer l'algo à tout moment, pas dans une séquence ou un moment particulier. Les colonnes sont les suivantes:

  • NODE A reçoit: ce que le nœud A voit de son côté récepteur (c'est également P4 ci-dessous)

  • NODE A injecte: ce que le nœud A envoie (notez que 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 seconde de transmission signifie que 3 paquets sont en transit pour une latence de 3)

  • Le NŒUD B reçoit: ce que B voit de son côté récepteur (c'est P3)

  • NODE B injecte: ce que B envoie (notez que c'est B, ou au hasard A ou B par algo)

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

  • A compte A: ce que A compte pour les paquets A qu'il a vus

  • A compte B: ce que A compte pour les paquets B qu'il a vus

  • B compte A: ce que B compte pour les paquets A qu'il a vus

  • B compte B: ce que B compte pour les paquets B qu'il a vus

  • A-> B: La latence qu'A estime à B (rapport de RTT de 4 secondes basé sur les paquets vus)

  • B-> A: La latence que B estime à A (rapport de RTT de 4 secondes basé sur les paquets vus)

Comme nous pouvons voir les deux nœuds converger et rester autour de leur vraie latence (en fait, nous ne voyons pas cela pour A car plus de secondes sont nécessaires pour converger mais il converge le même comportement que B)

De meilleurs filtres pourraient converger plus rapidement, mais nous pouvons clairement voir comment ils convergent tous les deux autour des valeurs correctes pour leurs retards, ils peuvent donc connaître exactement leur retard (même si je ne montre leur estimation qu'à titre d'illustration).

De plus, même si les bandes passantes entre les liens sont différentes, la méthode ci-dessus pourrait toujours tenir (bien qu'il faudra y penser davantage pour être plus certain) en utilisant des paires de paquets pour déterminer les estimations de la bande passante et ensuite simplement appliquer à l'équation de proportion ci-dessus.

Conclusion Nous avons fourni un algorithme pour A et B pour connaître leur position dans le réseau et connaître leur latence à l'autre nœud pour le diagramme ci-dessus. Nous avons utilisé une méthode d'estimation de mesure de réseau plutôt que des approches basées sur l'horloge qui, en effet, ne peuvent pas conduire à une solution en raison d'un problème de synchronisation d'horloge récursive.

Remarque J'ai maintenant édité cette réponse en fournissant toutes les simulations car personne ne me croirait, je l'ai résolu autant que vous pouvez le voir dans les premiers commentaires. Espérons qu'avec ces résultats, quelqu'un pourra être plus convaincu et approuver pour aider tout le monde à trouver au moins une erreur ou une correction dans ce puzzle de mesure de réseau!

user3134164
la source
3
Je ne pense pas que cela fonctionne. Puisque la bande passante est la même, la seule différence que A et B voient est que, s'ils ont commencé en même temps, B attendrait 3 secondes avant de recevoir des données et A attendrait 1 seconde. Mais ils n'ont pas d'horloge partagée, ils ne savent donc pas qu'ils ont commencé en même temps. Peut-être que A n'entend rien pendant 10 secondes parce qu'il a commencé à exécuter le protocole en premier.
David Richerby
Il n'est pas nécessaire de démarrer en même temps, tout le monde peut commencer à tout moment. Ils doivent tous deux fonctionner pendant un certain temps. J'apprécie que vous ayez pris le temps de l'examiner, mais veuillez relire. Il s'agit d'une méthode statistique et implique la convergence. Je ne dis pas que je suis à 100% c'est absolument correct car je n'ai pas simulé mais juste le commentaire que vous avez fait ne s'applique pas vraiment à mon avis. Cela explique peut-être l'idée plus généralement: si vous acceptez que le produit de retard de bande passante * est différent pour les deux liens, alors un lien contiendra en fait plus de paquets - et cela peut être détecté par algo ci-dessus ...
user3134164
Je ne pense pas avoir mal compris mais c'est possible. Êtes-vous d'accord pour dire que la bande passante est la même pour que A et B reçoivent les données au même débit? Si oui, ne convergeront-ils pas tous les deux exactement vers la même chose?
David Richerby
Oui, bien sûr, ils reçoivent au même rythme, cela ne signifie pas qu'ils convergent vers la même chose. Il y a des paquets A et B dans le réseau, la question est de savoir quel est le rapport entre les paquets A et B. J'ai exécuté une simulation simple maintenant et j'obtiens le biais tout le temps. Pour avoir une idée car je suppose que je ne peux pas publier le tout ici, supposons que b est tel qu'un paquet prend une seconde transmission. Ensuite, il y a toujours 4 paquets en transit. Appliquez l'algorithme et le boom, nous avons réussi à mesurer l'OTT en évitant les méthodes d'horloge / événements synchronisés qui ne fonctionnent pas avec les méthodes de convergence statistique!
user3134164
Quelle est «la proportion de paquets de A contre B»?
Gilles 'SO- arrête d'être méchant'
0

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

PXXRXX

  • R1=(1-R2)×(1-P2)R2=(1-R1)×(1-P1)1-R21-P2
  • R1R2R11-R1R21-R2

C'est pourquoi je crois que cela ne vous mènera nulle part. Veuillez signaler toute erreur que j'aurais pu commettre lors de ce raisonnement.

Matrefeytontias
la source
Bienvenue en informatique ! Votre réponse est belle mais est, comme vous le dites, un commentaire en profondeur sur la remarque de @ user3134164. Je pense que vous pouvez résoudre ce problème des manières suivantes 1) Essayez d'élargir votre réponse de telle sorte que ce soit également une réponse à la question réelle. ou 2) Créez une nouvelle question qui énonce essentiellement l'idée fausse clé du commentaire et de l'auto-réponse de l'utilisateur3134164 avec une réponse similaire à celle-ci. Laquelle est appropriée dépend de vous. Je pense que peut-être faire une nouvelle question est une bonne idée, mais peut-être pouvez-vous développer plus que je ne le pense. Demandez si vous avez d'autres questions.
Lézard discret
Bien sûr, @ user3134164 est également libre de «promouvoir» le commentaire en question,
Lézard discret
"Px la probabilité que le robot x choisisse ses propres paquets quand il reçoit l'un des autres paquets du robot" provient d'une fonction random () de l'ordinateur comme dans l'hypothèse - par exemple pour deux types de paquets, il sera toujours 0,5. Si la fonction random () est suffisamment uniforme, le "rapport réel du délai RTT de A à B" peut être calculé. Selon votre définition de R, je pense que R1 = (1-R2) * 0,5, donc le rapport est connu. Je crois donc toujours que ma réponse fonctionne bien. Merci beaucoup d'avoir pris le temps de l'examiner.
user3134164