Messung der Einweg-Netzwerklatenz

20

Dies ist ein Rätsel zur Messung der Netzwerklatenz, das ich erstellt habe. Ich glaube, die Lösung ist, dass es unmöglich ist, aber Freunde nicht einverstanden sind. Ich suche so oder so nach überzeugenden Erklärungen. (Obwohl es sich um ein Puzzle handelt, passt es meiner Meinung nach auf diese Website, da es sich auf das Design und die Erfahrung von Kommunikationsprotokollen wie in Online-Spielen bezieht, ganz zu schweigen von NTP.)

Angenommen, zwei Roboter befinden sich in zwei Räumen, die durch ein Netzwerk mit unterschiedlichen Latenzen in eine Richtung verbunden sind (siehe Abbildung unten). Wenn Roboter A eine Nachricht an Roboter B sendet, dauert es 3 Sekunden, bis sie eintrifft, aber wenn Roboter B eine Nachricht an Roboter A sendet, dauert es 1 Sekunde, bis sie eintrifft. Die Latenzen variieren nie.

Die Roboter sind identisch und haben keine gemeinsame Uhr, obwohl sie den Lauf der Zeit messen können (z. B. haben sie Stoppuhren). Sie wissen nicht, welcher von ihnen Roboter A ist (dessen Nachrichten 3s verzögert sind) und welcher Roboter B ist (dessen Nachrichten um 1s verzögert sind).

Ein Protokoll zur Ermittlung der Umlaufzeit lautet:

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

Gibt es ein Protokoll zur Ermittlung der Einwegverspätungen? Können die Roboter herausfinden, welcher von ihnen die längere Verspätung beim Senden von Nachrichten hat?

Zwei Roboter ein asymmetrisches Netzwerk

Craig Gidney
quelle
5
Weitere Informationen finden Sie unter Synchronisierung der Uhr in einem Netzwerk mit asymmetrischen Verzögerungen . Nach dem, was wir gesehen haben, als wir falsche Antworten auf diese Frage besprochen haben, ist die Antwort auf Ihre Frage, dass es unmöglich ist.
Gilles 'SO - hör auf böse zu sein'
Sollten wir die Fragen zusammenführen, oder unterscheiden sie sich im Ziel genug, um getrennt zu bleiben?
Craig Gidney
Nein, das sind unterschiedliche Fragen. Ihre Frage zeigt, dass es in einer Zwei-Maschinen-Umgebung nicht möglich ist, nur Nachrichten zu übermitteln. Ich hoffe auf Lösungen, die beispielsweise darauf basieren, dass Latenzinformationen für einige Zwischenverbindungen auf der Route zwischen dem Client und dem Server verfügbar sind und diese Informationen auf irgendeine Weise an den Client weitergeben können.
Gilles 'SO - hör auf, böse zu sein'
3
Wenn es einen Weg gäbe, würde Einsteins Relativitätstheorie nicht funktionieren, da es von der Tatsache abhängt, dass zwei Beobachter, die räumlich getrennt sind und unbekannte Einweglatenzen haben, sich nicht auf einen geeigneten Zeitpunkt einigen können.
Peter Shor
NTP erlaubt / implementiert tatsächlich das Messen dieser Differenzverzögerung basierend auf Maschinen, die sich gegenseitig ihre Zeit senden und nicht nur die Sende- / Empfangszeit ihrer eigenen Nachrichten, sondern auch der anderen Server über Nachrichteninhalte
verfolgen

Antworten:

14

Das folgende Diagramm von einem Blogbeitrag, den ich geschrieben habe , ist ein visueller Beweis dafür, dass es unmöglich ist:

Verschieben des Taktversatzes exakt versetzt durch Latenzasymmetrie

Beachten Sie, dass die Paketankunftszeiten auf jeder Seite gleich bleiben, auch wenn sich die Einweglatenzen ändern (und sogar negativ werden!). Das erste Paket erreicht den Server immer um 1,5 Sekunden nach der Uhr des Servers, das zweite erreicht den Client immer um 2 Sekunden nach der Uhr des Clients usw. Der Paketinhalt und die lokalen Ankunftszeiten sind die einzigen Dinge, auf denen ein Protokoll basieren könnte Inhalt und Ankunftszeiten können konstant gehalten werden, da die Asymmetrie variiert, indem auch der anfängliche Taktversatz variiert wird.

Grundsätzlich sieht Asymmetrie bei den Einweg-Latenzen aus genau der Zeitverschiebung. Da das Problem besagt, dass wir den anfänglichen Taktversatz oder die Einweg-Latenz-Asymmetrie nicht kennen und das Variieren des einen wie das Variieren des anderen aussieht, so dass ihre Effekte nicht zu unterscheiden sind, können wir ihre Beiträge nicht trennen, um das zu lösen Einweg-Latenz-Asymmetrie. Es ist unmöglich.

n1n1

Seekrankheit

Wenn Sie visuell nicht so geneigt sind, habe ich ein anderes intuitives Argument. Stellen Sie sich ein Zeitportal für hundert Jahre in der Zukunft vor. Wenn Sie sich mit jemandem auf der anderen Seite darüber unterhalten, stellen Sie fest, dass die Konversation trotz der hundertjährigen Asymmetrie bei einseitigen Verzögerungen völlig normal ist. Jeder beobachtbare Effekt wäre in dieser Größenordnung offensichtlich gewesen!

Craig Gidney
quelle
Was ist deine Meinung dazu? software.internet2.edu/owamp
CMCDragonkai
@CMCDragonkai Beachten Sie, dass die Puzzle-Anweisung restriktiver ist als die Realität. In der Praxis haben Sie die Möglichkeit, die Länge von Glasfaserleitungen zu messen, an Zwischenpunkten zu protokollieren, die Netzwerktopologie zu kennen, eine Uhr langsam von einem Ort zum anderen zu transportieren usw. Beispielsweise bewegen sich GPS-Satelliten in bekannten Umlaufbahnen und Sie Damit können Freiheitsgrade beim Lösen entfernt werden. An der Oberfläche sehe ich also kein Problem mit einem Einweg-Ping-Tool, solange es oder die Uhren, auf die es sich verlässt, einige dieser süßen, süßen tertiären Informationen ausnutzen.
Craig Gidney
Oh, könnten Sie in diesem Fall Ihre Antwort mit möglichen Umgehungsmöglichkeiten aktualisieren?
CMCDragonkai
@CMCDragonkai Es reicht aus, sie in den Kommentaren zu haben. Sie sprengen den Rahmen des Puzzles.
Craig Gidney
Die Latenz in eine Richtung spielt zum Beispiel für die Vernetzung von Spielen eine Rolle. Außerdem sagt jeder, unmöglich, aber ich kann das Rätsel leicht auf Papier lösen. Sobald Sie die Uhren synchronisiert haben, müssen Sie nur die Verzögerung von A nach B messen, indem Sie die Zeit von A nach B senden, wobei die Verzögerung von A-> B gleich B's time - A's sent timeund ist B-> Ein Wesen gleichlatency - A->B delay
Llamageddon
1

Ich denke, es ist unmöglich, die Latenz in eine Richtung nur durch einen Vergleich der Stoppuhren zu ermitteln.

EINBCEIN1
BCB1=1
EINCEIN2=9
BCB2=5
EINB können herausfinden, wann der andere Roboter eine Nachricht bezüglich seiner Uhren erhalten hat.

Vielleicht wird es jemand knacken, wenn Sie es zu einer Kopfgeldfrage machen. Bis dahin ein dickes Lob.

rath
quelle
0

Ich habe einen Weg gefunden, BEIDES herauszufinden, welcher Knoten wer ist (dh wer die längere Nachrichtenverzögerung hat) UND die Einweg-Auslöseverzögerung abzuschätzen. Die anderen Antworten sind zwar korrekt, sie berücksichtigen jedoch NUR die Annäherung an die direkte Taktmessung, was natürlich nicht funktionieren kann. Wie ich hier beweise, ist dies jedoch nur ein Teil der Geschichte, da hier mein Arbeitsalgorithmus für das Obige ist:

Angenommen, wie im wirklichen Leben:

  • Links mit endlicher Bandbreite b

  • Jeder Knoten hat eine eindeutige Adresse (zB A und B)

  • Die Paketgröße p ist viel kleiner als das Latenzprodukt für Bandbreite *

  • Die Knoten A und B können den Kanal füllen

  • Knoten haben eine zufällige () Funktion

Jeder Knoten füllt den Kanal mit seinen eigenen Paketen (mit A oder B markiert) ODER leitet die von anderen Knoten empfangenen Pakete wie folgt weiter:

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

Intuitive Erklärung Da das Latenzprodukt für Bandbreite * von A höher ist (weil die Latenz höher ist), kann A mehr Pakete empfangen als B, sodass jeder Knoten wissen kann, wer sie im Diagramm sind .

Weiterhin mit genügend Konvergenzzeit wird bezeichnen obigen Algorithmus des Laufens das Verhältnis von Paketen , von A zu B das tatsächliche Verhältnis von RTT Verzögerung von A nach B und damit die gewünschte OTT .

VERFOLGUNG DER SIMULATIONSERGEBNISSE Hier ist eine Simulation, die das Obige beweist und zeigt, wie A erfolgreich in Richtung einer Verzögerung von 3 Sekunden und B in Richtung einer Verzögerung von 1 Sekunde konvergiert:

Erste Sekunden der Simulation

Nachfolgende Sekunden der Simulation

Erläuterung der Figuren: Jede Zeile repräsentiert 1 Sekunde der Zeit (die Paketgröße wird aus Gründen der Klarheit so gewählt, dass sie 1 Sekunde Übertragungszeit hat). Beachten Sie, dass jeder Knoten den Algo jederzeit und nicht in einer bestimmten Reihenfolge oder Zeit starten kann. Die Spalten lauten wie folgt:

  • NODE A empfängt: Was Node A auf seiner Empfangsseite sieht (dies ist auch P4 unten)

  • Knoten A injiziert: Was Knoten A aussendet (beachten Sie, dass dies A oder zufällig A oder B ist)

  • P1, P2, P3: Die drei Pakete, die zwischen A und B (in der Reihenfolge) übertragen werden (1 Sekunde bedeutet, dass 3 Pakete für eine Latenz von 3 übertragen werden)

  • NODE B empfängt: Was B auf seiner Empfangsseite sieht (dies ist P3)

  • NODE B injiziert: Was B aussendet (beachten Sie, dass dies B ist oder zufällig A oder B pro Algo)

  • P4: Das Paket auf dem Weg von B nach A (siehe auch P1, P2, P3)

  • A zählt A: Was A für die A-Pakete zählt, die es gesehen hat

  • A zählt B: Was A für die B-Pakete zählt, die es gesehen hat

  • B zählt A: Was B für die A-Pakete zählt, die es gesehen hat

  • B zählt B: Was B für die B-Pakete zählt, die es gesehen hat

  • A-> B: Die Latenz, die A in Richtung B schätzt (Verhältnis der RTT von 4 Sekunden basierend auf den gesehenen Paketen)

  • B-> A: Die Latenz, die B in Richtung A schätzt (Verhältnis der RTT von 4 Sekunden basierend auf den gesehenen Paketen)

Wie wir sehen können, konvergieren beide Knoten und bleiben um ihre wahre Latenz herum (tatsächlich sehen wir das für A nicht, weil mehr Sekunden benötigt werden, um zu konvergieren, aber es konvergiert dasselbe Verhalten wie B)

Bessere Filter könnten schneller konvergieren, aber wir können deutlich sehen, wie sie beide um die korrekten Werte für ihre Verzögerungen konvergieren, daher können sie genau sie ihre Verzögerung kennen (obwohl ich ihre Schätzung nur zur Veranschaulichung zeige).

Auch wenn die Bandbreiten zwischen den Verbindungen unterschiedlich sind, könnte das obige Verfahren immer noch gelten (obwohl man sich mehr Gedanken darüber machen muss, um sicherer zu sein), indem Paketpaare verwendet werden, um Bandbreitenschätzungen herauszufinden, und dann einfach auf die obige Proportionsgleichung angewendet werden.

Schlussfolgerung Wir haben einen Algorithmus bereitgestellt, mit dem sowohl A als auch B ihre Position im Netzwerk und ihre Latenz zum anderen Knoten für das obige Diagramm kennen. Wir verwendeten eine Schätzmethode für die Netzwerkmessung anstelle von taktbasierten Ansätzen, die aufgrund von Problemen mit der rekursiven Taktsynchronisation in der Tat nicht zu einer Lösung führen können.

Hinweis: Ich habe diese Antwort jetzt bearbeitet und alle Simulationen bereitgestellt, da mir niemand glauben würde, dass ich sie gelöst habe, wie Sie in den ersten Kommentaren sehen können. Hoffentlich kann jemand mit diesen Ergebnissen überzeugter sein und jedem helfen, mindestens einen Fehler oder eine Richtigkeit in diesem Netzwerk-Messrätsel zu finden!

user3134164
quelle
3
Ich denke nicht, dass das funktioniert. Da die Bandbreite gleich ist, besteht der einzige Unterschied, den A und B sehen, darin, dass B bei gleichzeitigem Start 3 Sekunden warten würde, bevor Daten empfangen werden, und A 1 Sekunde warten würde. Sie haben jedoch keine gemeinsame Uhr, sodass sie nicht wissen, dass sie zur gleichen Zeit gestartet sind. Vielleicht hört A 10s lang nichts, weil er das Protokoll zuerst gestartet hat.
David Richerby
Es ist nicht erforderlich, zur gleichen Zeit zu starten, die jeder jederzeit starten kann. Sie müssen nur einige Zeit lang ausgeführt werden. Ich freue mich, dass Sie sich die Zeit genommen haben, dies zu überprüfen, aber bitte lesen Sie es noch einmal. Dies ist eine statistische Methode und beinhaltet Konvergenz. Ich sage nicht, dass ich 100% bin, es ist absolut richtig, da ich nicht simuliert habe, aber nur der Kommentar, den Sie gemacht haben, trifft meiner Meinung nach nicht wirklich zu. Vielleicht erklärt dies die Idee allgemeiner: Wenn Sie akzeptieren, dass das Produkt Bandbreite * Verzögerung für die beiden Links unterschiedlich ist, dann enthält ein Link tatsächlich mehr Pakete - und das kann von algo oben
festgestellt werden
Ich glaube nicht, dass ich falsch verstanden habe, aber es ist möglich. Stimmen Sie zu, dass die Bandbreite identisch ist, sodass A und B Daten mit derselben Rate empfangen? Wenn ja, laufen die beiden dann nicht genau auf dasselbe zusammen?
David Richerby
Ja, natürlich erhalten sie die gleiche Rate, das heißt aber nicht, dass sie in der gleichen Weise konvergieren. Es gibt A- und B-Pakete im Netzwerk. Die Frage ist, wie hoch das Verhältnis von A- zu B-Paketen ist. Ich habe jetzt einige einfache Simulationen durchgeführt und bekomme die Tendenz die ganze Zeit. Um eine Vorstellung zu bekommen, da ich denke, dass ich das Ganze hier nicht posten kann, gehe ich davon aus, dass b so ist, dass 1 Paket eine Sekunde Übertragung benötigt. Dann sind immer 4 Pakete unterwegs. Wenden Sie Algorithmus und Boom an. Wir haben es geschafft, die OTT zu messen, indem wir synchronisierte Takt- / Ereignismethoden vermieden haben, die mit statistischen Konvergenzmethoden nicht funktionieren!
user3134164
Was ist das Verhältnis von Paketen von A zu B?
Gilles 'SO- hör auf böse zu sein'
0

Dies ist eine Antwort auf @ user3134164, aber für einen Kommentar zu groß.

PxxRxx

  • R1=(1-R2)×(1-P2)R2=(1-R1)×(1-P1)1-R21-P2
  • R1R2R11-R1 und R21-R2. Wie Sie sehen, sind die einzigen Begriffe, die in diesen Ausdrücken vorkommen, die Wahrscheinlichkeiten, mit denen jeder Roboter sein eigenes Paket über das des anderen auswählt. Die Latenzen erscheinen nicht einmal in der Formel, nur weil beide Roboter ständig Pakete auspumpen, also beide ständig Pakete empfangen. Sie erhalten zwar unterschiedliche Paketverhältnisse, dies hängt jedoch nur von den oben genannten Wahrscheinlichkeiten ab.

Deshalb glaube ich, dass Sie dies nirgendwo hinführen wird. Bitte weisen Sie auf einen Fehler hin, den ich bei dieser Überlegung hätte machen können.

Matrefeytontias
quelle
Willkommen in der Informatik ! Ihre Antwort sieht gut aus, ist aber, wie Sie sagen, ein ausführlicher Kommentar zur Bemerkung von @ user3134164. Ich denke, Sie können dieses Problem auf folgende Weise lösen: 1) Versuchen Sie, Ihre Antwort so zu erweitern, dass dies auch eine Antwort auf die eigentliche Frage ist. oder 2) Erstellen Sie eine neue Frage , die im Wesentlichen das Schlüsselfehlverständnis aus dem Kommentar und der Selbstantwort von user3134164 mit einer ähnlichen Antwort wiedergibt. Welches angemessen ist, liegt bei Ihnen. Ich denke, vielleicht ist es eine gute Idee, eine neue Frage zu stellen, aber vielleicht können Sie mehr erweitern, als ich denke. Fragen Sie, wenn Sie weitere Fragen haben.
Diskrete Eidechse
Natürlich steht es @ user3134164 auch frei, den Kommentar in eine Frage zu „promoten“.
Diskrete Eidechse
"Px die Wahrscheinlichkeit, dass der Roboter x seine eigenen Pakete auswählt, wenn er eines der Pakete des anderen Roboters empfängt" stammt aus einer Computer-Zufallsfunktion () wie in der Annahme - zum Beispiel für zwei Arten von Paketen wird sie immer 0,5 sein. Wenn die random () -Funktion einheitlich genug ist, kann das "tatsächliche Verhältnis der RTT-Verzögerung von A zu B" berechnet werden. Durch Ihre R-Definition denke ich, dass R1 = (1-R2) * 0,5, so dass das Verhältnis bekannt ist. Deshalb glaube ich immer noch, dass meine Antwort gut funktioniert. Vielen Dank, dass Sie sich die Zeit genommen haben, sich damit zu beschäftigen.
user3134164