Messung einer Netzwerklatenz messen

Question

Dies ist ein Rätsel über die Messung der Netzwerklatenz, die ich erstellt habe. Ich glaube, die Lösung ist, dass es unmöglich ist, aber Freunde sind anderer Meinung. Ich suche nach überzeugenden Erklärungen oder so. (Obwohl es als Rätsel dargestellt wird, ist es meiner Meinung nach aufgrund seiner Anwendbarkeit auf das Design und die Erfahrung von Kommunikationsprotokollen wie in Online -Spielen, ganz zu schweigen von NTP.)

Angenommen, zwei Roboter befinden sich in zwei Räumen, die von einem Netzwerk mit unterschiedlichen Einweg-Latenzen verbunden sind, wie in der unten stehenden Grafik gezeigt. Wenn Roboter A eine Nachricht an Roboter B sendet, dauert es 3 Sekunden, bis sie ankommt. Wenn Robot B jedoch eine Nachricht an Roboter A sendet, dauert es 1 Sekunde, bis es ankommt. Die Latenzen variieren nie.

Die Roboter sind identisch und haben keine gemeinsame Uhr, obwohl sie den Zeitverlauf 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 (dessen Nachrichten um 1s verzögert werden).

Ein Protokoll, um die Hin- und Rückfahrt zu entdecken, ist:

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, um die Auslöseverzögerungen zu bestimmen? Können die Roboter entdecken, welcher von ihnen die längere Nachricht hat, die Verzögerung sendet?

Answer 1

Das folgende Diagramm von Ein Blog -Beitrag, den ich schrieb, ist ein visueller Beweis dafür, dass es unmöglich ist:

Beachten Sie, wie die Ankunftszeiten der Paket auf jeder Seite gleich bleiben, auch wenn sich die Einweglatenzen ändern (und sogar negativ werden!). Das erste Paket erreicht den Server immer mit 1,5 Sekunden auf der Uhr des Servers, das zweite erreicht den Client immer mit 2s auf der Uhr des Clients usw. Der Paketinhalt und die lokalen Ankunftszeiten sind die Nur Dinge Ein Protokoll könnte basieren, aber die Inhalte und die Ankunftszeiten können konstant gehalten werden, da die Asymmetrie auch variiert, was auch die anfängliche Uhr verzerrt.

Grundsätzlich sieht die Asymmetrie in den Einweglatenzen aus exakt wie die Uhr verzerrt. Da das Problem besagt, dass wir nicht anfangen, die anfängliche Uhr verzerrt oder die Einweg-Latenzasymmetrie zu kennen, und das Variieren einer Variation der anderen, sodass ihre Auswirkungen nicht zu unterscheiden sind, können wir ihre Beiträge nicht trennen, um für die zu lösen Einweglatenzasymmetrie. Es ist unmöglich.

Ausführlicher können Sie nicht die Kantenlängen lösen, wenn Sie nur die Längen der Zyklen gegeben haben. Die Zyklusbasis hat Freiheitsgrade $ N-1 $, was dem Unbekannten $ N-1 $ $ entspricht, der sich im Vergleich zu einem der Teilnehmer verdrängt. Sie können immer die Einweglatenzen verbergen, auch wenn es viele Teilnehmer gibt:

Wenn Sie nicht so visuell geneigt sind, habe ich ein anderes intuitives Argument. Stellen Sie sich ein Zeitportal zu hundert Jahren in der Zukunft vor. Wenn Sie sich mit jemandem auf der anderen Seite darüber unterhalten, stellen Sie fest, dass das Gespräch trotz der hundertjährigen Asymmetrie bei Einwegverzögerungen völlig normal ist. Jeder beobachtbare Effekt wäre in dieser Skala offensichtlich gewesen!

Answer 2

Ich denke, es ist unmöglich, eine Einweg-Latenz zu finden, indem sie Stoppschuhe verglichen.

$ A $ sendet $ b $ seine Uhr $ c_ {a1} $, sagen wir, der Wert beträgt 5.
$ B $ bestätigt die Nachricht zum Zeitpunkt $ c_ {b1} = 1 $
$ A $ sendet seine Uhr erneut, $ c_ {a2} = 9 $ (Initial + Roundtrip-Latenz).
$ B $ erhält zum Zeitpunkt $ C_ {B2} = 5 $.
Usw. Weder $ a $ noch $ B $ können herausfinden, wann der andere Roboter eine Nachricht in Bezug auf ihre Uhren erhalten hat.

Wenn Sie es zu einer Kopfgeldfrage machen, wird jemand es knacken. Bis dahin ein großes Lob.

Answer 3

Ich habe einen Weg gefunden, um beide zu entdecken, welcher Knoten wer ist (dh wer die längere Nachrichtenverzögerung hat) und die Einweg -Ausladungsverzögerung abzuschätzen. Während die anderen Antworten korrekt sind, berücksichtigen sie nur eine direkte Uhrmessung, die natürlich nicht funktionieren kann. Da ich hier jedoch beweise, ist dies nur ein Teil der Geschichte, da hier mein Arbeitsalgorithmus für das oben genannte ist:

Nehmen Sie wie im wirklichen Leben an:

• Links der endlichen Bandbreite B

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

• Paketgröße P viel kleiner als die Bandbreite*Latenzprodukt

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

• Knoten haben a zufällig() Funktion

Jeder Knoten füllt den Kanal mit seinen eigenen Paketen (mit A oder B gekennzeichnet) oder leitet die Pakete weiter, die er wie folgt von anderen Knoten erhalten hat:

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ärungDa A's Bandbreite*Latenzprodukt höher ist (weil die Latenz höher ist), wird A daher mehr Pakete erhalten als B, daher Jeder Knoten kann wissen, wer er im Diagramm ist.

Außerdem, mit genügend Konvergenzzeit Das Verhältnis von Paketen von a zu b über den Algorithmus über den Algorithmus zu rennen, wird das bezeichnen Tatsächliches Verhältnis der RTT -Verzögerung von A zu B und damit der gewünschten OTT.

SimulationsergebnisspurHier ist eine Simulation, die die oben genannten beweist und zeigt, wie sich ein erfolgreiches Zusammenhang in Richtung 3 -Sekunden -Verzögerung und B konvergiert um 1 Sekunde Verzögerung:

Erläuterung der Figuren:Jede Zeile repräsentiert 1 Sekunde Zeit (Paketgröße wird für die Klarheit von 1 Sekunde über die Übertragungszeit ausgewählt). Beachten Sie, dass jeder Knoten das Algo jederzeit in einer bestimmten Reihenfolge oder Zeit starten kann. Die Spalten sind wie folgt:

• Knoten A empfängt: Was Knoten A in seiner Empfangsseite sieht (dies ist auch P4 unten)

• Knoten A Injects: Was der Knoten A sendet (beachten Sie, dass dies ein oder zufällig a oder b ist)

• P1, P2, P3: Die drei Pakete, die in der Reihenfolge (in der Reihenfolge) zwischen A und B sind (1 Sekunde Transmission -Mittelwerte 3 -Pakete sind für eine Latenz von 3 unterwegs)

• Knoten B empfängt: Was B in seiner Empfangsseite sieht (dies ist P3)

• Knoten B Injects: Was B sendet (beachten Sie, dass dies b oder zufällig a oder b pro Algo ist)

• P4: Das Paket in Transit von B zu A (siehe auch P1, P2, P3)

• A zählt a: Was für ein Paket zählt, das es gesehen hat

• A zählt B: Was für ein Zählungen für die B -Pakete, 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: Welche B zählt für die B -Pakete, die es gesehen hat

• A-> B: Die Latenz, die A schätzt, dass B (Verhältnis von RTT von 4 Sekunden basierend auf Paketen beobachtet wird)

• B-> A: Die Latenz, die B zu A (Verhältnis von RTT von 4 Sekunden basierend auf Paketen beobachtet) schätzt)

Wie wir sehen können, konvergieren beide Knoten und bleiben in ihrer wahren Latenz (tatsächlich sehen wir das nicht für A, weil mehr Sekunden erforderlich sind, um zu konvergieren, aber das gleiche Verhalten wie B konvergiert)

Bessere Filter könnten schneller konvergieren, aber wir können deutlich sehen, wie beide die richtigen Werte für ihre Verzögerungen konvergieren, deshalb können sie sie exakt Kennen Sie ihre Verzögerung (obwohl ich ihre Schätzung nur zur Illustration zeige).

Auch wenn sich die Bandbreiten zwischen den Links unterschiedlich unterscheiden, könnte die obige Methode noch gelten (obwohl man mehr darüber nachdenken muss, um sicherer zu sein), indem sie Paketpaare verwenden, um Bandbreitenschätzungen herauszufinden, und dann nur für die obige Anteilsgleichung angewendet werden.

FazitWir haben einen Algorithmus für A und B zur Verfügung gestellt, um ihre Position im Netzwerk zu kennen und ihre Latenz zum anderen Knoten für das obige Diagramm zu kennen. Wir haben eine Methode zur Schätzung von Netzwerkmessungen anstelle von taktbasierten Ansätzen verwendet, die aufgrund eines rekursiven Takt-Synchronisierungsproblems tatsächlich nicht zu einer Lösung führen können.

Notiz Ich habe diese Antwort jetzt bearbeitet und alle Simulationen bereitgestellt, weil niemand mir glauben würde, dass ich sie so weit gelöst habe, wie Sie in den ersten Kommentaren sehen können. Hoffentlich kann jemand mit diesen Ergebnissen überzeugt und genehmigt werden, um allen zu helfen, zumindest einen Fehler oder eine Korrektheit in diesem Netzwerkmessrätsel zu finden!

Answer 4

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

Hier ist mein Versuch zu zeigen, warum dies nicht funktionieren kann (mathematischer Ansatz). Nennen wir $ P_X $ die Wahrscheinlichkeit, dass Roboter $ x $ seine eigenen Pakete wählt, wenn er eines der anderen Roboterpakete erhält, und $ r_x $ Die Wahrscheinlichkeit, dass ein Paketroboter $ x $ erhalten ist, ist seine eigene. Nachdem das stationäre Regime erreicht wurde (dh nach einer "unendlichen" Zeit, dh alle Konvergenz ist durchgeführt) haben wir Folgendes:

• $ R_1 = (1 - r_2) mal (1 - p_2) $ und ähnlich $ r_2 = (1 - r_1) mal (1 - p_1) $. Die Idee ist, dass ein Roboter, wenn ein Roboter eines seiner eigenen Pakete erhält, der andere Roboter ihn anstelle eines seiner eigenen erhielt (daher die $ 1 - r_2 $) und dass er es immer noch entschied, es anstelle eines von selbst zu senden (eigene Daher das Produkt von $ 1 - p_2 $).
• Dies gibt ein System von zwei Gleichungen mit zwei Unbekannten, $ R_1 $ und $ R_2 $. Vielleicht möchten Sie es lösen, aber es spielt keine Rolle. Tatsächlich sind die Verhältnisse, die Sie suchen, jeweils $ frac {r_1} {1 - r_1} $ und $ frac {r_2} {1 - r_2} $. Wie Sie bemerken können, sind die einzigen Begriffe, die in diesen Ausdrücken erscheinen, die Wahrscheinlichkeiten, mit denen jeder Roboter sein eigenes Paket über das andere auswählt. Die Latenzen erscheinen nicht einmal in der Formel, nur weil beide Roboter die Pakete ständig pumpen, sodass beide ständig Pakete erhalten. Sie erhalten in der Tat unterschiedliche Verhältnisse von Paketen, hängen jedoch nur von den oben genannten Wahrscheinlichkeiten ab.

Deshalb glaube ich, dass Sie dies nirgendwo führen werden. Bitte weisen Sie auf einen Fehler hin, den ich in dieser Argumentation hätte machen können.