Pomiar opóźnień sieci w jedną stronę

To jest łamigłówka na temat pomiaru opóźnienia sieci, którą stworzyłem. Wierzę, że rozwiązaniem jest to, że jest to niemożliwe, ale przyjaciele się nie zgadzają. Tak czy inaczej, szukam przekonujących wyjaśnień. (Choć jest to układanka, myślę, że pasuje do tej strony internetowej ze względu na jej przydatność w projektowaniu i doświadczeniu protokołów komunikacyjnych, takich jak gry online, nie wspominając o NTP.)

Załóżmy, że dwa roboty znajdują się w dwóch pokojach, połączonych siecią o różnych opóźnieniach w jedną stronę, jak pokazano na poniższej grafice. Kiedy robot A wysyła wiadomość do robota B, dotarcie do niego zajmuje 3 sekundy, ale gdy robot B wysyła wiadomość do robota A, zajmuje 1 sekundę. Opóźnienia nigdy się nie różnią.

Roboty są identyczne i nie mają wspólnego zegara, chociaż mogą mierzyć upływ czasu (np. Mają stopery). Nie wiedzą, który z nich to robot A (którego komunikaty są opóźnione o 3 s), a który to robot B (którego komunikaty są opóźnione o 1 s).

Protokół wykrywania czasu podróży w obie strony to:

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

Czy istnieje protokół określający opóźnienia podróży w jedną stronę? Czy roboty mogą ustalić, który z nich ma dłuższe opóźnienie w wysyłaniu wiadomości?

Poniższy diagram z postu na blogu, który napisałem , jest wizualnym dowodem na to, że jest to niemożliwe:

Zauważ, że czasy dostarczania pakietów z każdej strony pozostają takie same, nawet jeśli zmieniają się opóźnienia w jedną stronę (a nawet stają się ujemne!). Pierwszy pakiet zawsze dociera do serwera o 1,5 sekundy na zegarze serwera, drugi dociera do klienta o 2 sekundy na zegarze klienta itp. Zawartość pakietu i lokalne czasy przybycia są jedynymi elementami, na których protokół może być oparty, ale zawartość i czas przybycia mogą być utrzymywane na stałym poziomie, ponieważ asymetria zmienia się, zmieniając również początkowe pochylenie zegara.

Zasadniczo asymetria opóźnień jednokierunkowych wygląda dokładnie jak pochylenie zegara. Ponieważ problem polega na tym, że nie zaczynamy od znajomości początkowego pochylenia zegara lub asymetrii opóźnień w jedną stronę, a zmienianie jednego wygląda jak zmienianie drugiego, więc ich efekty są nierozróżnialne, nie możemy oddzielić ich wkładu w celu rozwiązania problemu jednokierunkowa asymetria opóźnień. To niemożliwe.

Mówiąc bardziej formalnie, nie można rozwiązać problemu z długością krawędzi, jeśli podano tylko długości cykli. Podstawa cyklu ma stopni swobody, co odpowiada n - 1 nieznanym odchyleniom zegara w stosunku do jednego z uczestników. Zawsze możesz ukryć opóźnienia w jedną stronę, nawet jeśli jest wielu uczestników:$n-1$$n-1$

Jeśli nie jesteś tak skłonny wizualnie, mam kolejny intuicyjny argument. Wyobraź sobie portal czasu na sto lat w przyszłości. Gdy rozmawiasz z kimś po drugiej stronie, zdajesz sobie sprawę, że rozmowa jest całkowicie normalna, pomimo stuletniej asymetrii w jednokierunkowych opóźnieniach. Każdy zauważalny efekt byłby oczywisty na taką skalę!

Myślę, że nie da się ustalić jednokierunkowego opóźnienia poprzez porównanie stoperów.

$A$$B$$C_{A1}$
$B$$C_{B1}=1$
$A$$C_{A2}=9$
$B$$C_{B2}=5$
$A$$B$

Może jeśli zrobisz z tego pytanie o nagrodę, ktoś to rozwali. Do tego czasu cześć.

Znalazłem sposób ZARÓWNO, który węzeł jest kim (tj. Kto ma dłuższe opóźnienie komunikatu) ORAZ oszacowanie opóźnienia wyłączenia w jedną stronę. Podczas gdy inne odpowiedzi są poprawne, brane są pod uwagę TYLKO bezpośredni pomiar zegara, który oczywiście nie może działać. Jednak, jak tu dowodzę, jest to tylko część historii, ponieważ tutaj jest mój działający algorytm dla powyższego:

Załóżmy, jak w prawdziwym życiu:

• Linki o skończonej przepustowości b

• Każdy węzeł ma unikalny adres (np. A i B)

• Rozmiar pakietu p jest znacznie mniejszy niż iloczyn przepustowości *

• Węzły A i B są w stanie wypełnić kanał

• Węzły mają random () funkcji

Każdy węzeł wypełnia kanał własnymi pakietami (odpowiednio oznaczonymi A lub B) LUB przekazuje pakiety otrzymane z innych węzłów w następujący sposób:

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

Intuicyjne wyjaśnienie Ponieważ produkt opóźniający szerokość pasma * jest większy (ponieważ opóźnienie jest większe) A będzie w stanie odebrać więcej pakietów niż B, dlatego każdy Węzeł może wiedzieć, kto jest na schemacie .

Ponadto przy wystarczającym czasie konwergencji działania powyżej algorytmu stosunek pakietów A do B będzie oznaczał rzeczywisty stosunek opóźnienia RTT A do B, a zatem pożądany OTT .

ŚLEDZENIE WYNIKU SYMULACJI Oto symulacja, która dowodzi powyższego i pokazuje, w jaki sposób A z powodzeniem zbliża się do 3-sekundowego opóźnienia, a B zbliża się do około 1-sekundowego opóźnienia:

Objaśnienie rysunków: Każda linia reprezentuje 1 sekundę czasu (rozmiar pakietu jest wybierany, aby mieć 1 sekundowy czas transmisji dla zachowania przejrzystości). Zauważ, że każdy węzeł może uruchomić algo w dowolnym momencie, nie w żadnej określonej sekwencji ani czasie. Kolumny są następujące:

• NODE A odbiera: Co węzeł A widzi po swojej stronie odbierającej (jest to również P4 poniżej)

• NODE A wstrzykuje: Co wysyła węzeł A (zwróć uwagę, że jest to A lub losowo A lub B)

• P1, P2, P3: Trzy pakiety, które są w tranzycie (w kolejności) między A i B (1 sekunda oznacza, że ​​3 pakiety są w tranzycie z opóźnieniem 3)

• NODE B otrzymuje: Co B widzi w swojej stronie odbierającej (jest to P3)

• NODE B wstrzykuje: Co wysyła B (zauważ, że to B, lub losowo A lub B na algo)

• P4: Pakiet w drodze z B do A (patrz także P1, P2, P3)

• A liczy A: Co A liczy dla pakietów A, które widział

• A liczy się B: Co A liczy dla pakietów B, które widział

• B liczy się A: Co B liczy dla pakietów A, które widział

• B liczy się B: Co B liczy dla pakietów B, które widział

• A-> B: Opóźnienie, które A szacuje w kierunku B (stosunek RTT wynoszący 4 sekundy w oparciu o widoczne pakiety)

• B-> A: Opóźnienie, które B szacuje w kierunku A (stosunek RTT wynoszący 4 sekundy w oparciu o widoczne pakiety)

Jak widzimy, oba węzły zbiegają się i pozostają w pobliżu swojego prawdziwego opóźnienia (tak naprawdę nie widzimy tego dla A, ponieważ potrzeba więcej sekund, aby zbiegać się, ale zachowuje się tak samo jak B)

Lepsze filtry mogą zbiegać się szybciej, ale możemy wyraźnie zobaczyć, w jaki sposób oba zbiegają się wokół prawidłowych wartości dla swoich opóźnień, dlatego mogą dokładnie znać swoje opóźnienie (chociaż pokazuję swoje oszacowanie tylko dla ilustracji).

Ponadto, nawet jeśli szerokości pasma między łączami są różne, powyższa metoda może nadal zostać utrzymana (chociaż trzeba będzie o tym pomyśleć bardziej, aby być bardziej pewnym), wykorzystując pary pakietów do obliczenia oszacowań przepustowości, a następnie po prostu zastosuj się do powyższego równania proporcji.

Wniosek Udostępniliśmy algorytm dla A i B, aby poznać ich pozycję w sieci i poznać ich opóźnienie w stosunku do drugiego węzła dla powyższego schematu. Zastosowaliśmy metodę szacowania pomiaru sieci zamiast metod opartych na zegarze, co w rzeczywistości nie może prowadzić do rozwiązania z powodu problemu z rekurencyjną synchronizacją zegara.

Uwaga : Zredagowałem tę odpowiedź, podając wszystkie symulacje, ponieważ nikt mi nie uwierzył, że rozwiązałem ją tak dalece, jak widać w pierwszych komentarzach. Mam nadzieję, że dzięki tym wynikom ktoś może być bardziej przekonany i zatwierdzony, aby pomóc każdemu przynajmniej znaleźć jeden błąd lub poprawność w tej układance pomiaru sieci!

To jest odpowiedź na @ user3134164, ale jest zbyt duża, by komentować.

$P_x$$x$$R_x$$x$

• $R_1 = (1 - R_2) \times (1 - P_2)$$R_2 = (1 - R_1) \times (1 - P_1)$$1 - R_2$$1 - P_2$
• $R_1$$R_2$$\frac{R_1}{1 - R_1}$$\frac{R_2}{1 - R_2}$

Właśnie dlatego wierzę, że doprowadzi cię to nigdzie. Proszę wskazać każdy błąd, który mógłbym popełnić podczas tego rozumowania.