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


20

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?

Dwa roboty jedna sieć asymetryczna


5
Zobacz Synchronizacja zegara w sieci z asymetrycznymi opóźnieniami (która wymaga wykonania czegoś przy typowej infrastrukturze internetowej). Myślę, że z tego, co widzieliśmy, omawiając błędne odpowiedzi na to pytanie, odpowiedź na twoje pytanie jest niemożliwa.
Gilles „SO- przestań być zły”

Czy powinniśmy scalić pytania, czy też są wystarczająco różne, aby rozdzielić je?
Craig Gidney

Nie, to różne pytania. Twoje pytanie pokazuje, że jest to niemożliwe w ustawieniach dwóch maszyn z samym przekazywaniem wiadomości. Mam nadzieję, że rozwiązania oparte na powiedzmy, że informacje o opóźnieniu są dostępne dla niektórych łączy pośrednich na trasie między klientem a serwerem i mam sposób na propagowanie tych informacji do klienta.
Gilles „SO- przestań być zły”

3
Gdyby istniał sposób na zrobienie tego, teoria względności Einsteina nie działałaby, ponieważ zależy to od tego, że dwóch obserwatorów, którzy są podobni do przestrzeni kosmicznej i mają nieznane jednokierunkowe opóźnienia, nie mogą uzgodnić właściwego czasu.
Peter Shor

NTP rzeczywiście pozwala / implementuje pomiar tego różnicy opóźnień w oparciu o maszyny wysyłające sobie nawzajem swój czas, a nie tylko śledzące czas wysyłania / odbierania własnych wiadomości, ale także inne serwery za pośrednictwem zawartości wiadomości, patrz odpowiedź na pytanie
Gillesa

Odpowiedzi:


14

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

Przesunięcie przesunięcia zegara dokładnie zrównoważone przez asymetrię opóźnień

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-1n-1

Choroba morska

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ę!



@CMCDragonkai Pamiętaj, że układanka jest bardziej restrykcyjna niż rzeczywistość. W praktyce masz takie opcje, jak pomiar długości linii światłowodowych, logowanie w punktach pośrednich, korzystanie z wiedzy o topologii sieci, powolne przenoszenie zegara z jednego miejsca do drugiego itp. Na przykład satelity GPS poruszają się po znanych orbitach, a ty może go użyć do usunięcia stopni swobody podczas rozwiązywania. Na pierwszy rzut oka nie widzę żadnego problemu z jednokierunkowym narzędziem ping, o ile ono lub zegary, na których polega, wykorzystują niektóre z tych słodkich słodkich trzeciorzędowych informacji.
Craig Gidney

Och, w takim razie, czy mógłbyś zaktualizować swoją odpowiedź o możliwe obejścia?
CMCDragonkai

@CMCDragonkai Wystarczy mieć je w komentarzach. Są poza zakresem układanki.
Craig Gidney

Opóźnienie w jedną stronę ma znaczenie, na przykład w przypadku gier sieciowych. Ponadto wszyscy mówią, że jest to niemożliwe, ale mogę z łatwością rozwiązać zagadkę na papierze - po zsynchronizowaniu zegarów wystarczy zmierzyć opóźnienie od A do B, wysyłając czas A do B, przy czym opóźnienie A-> B jest równe B's time - A's sent timei B-> Istota równalatency - A->B delay
Llamageddon,

1

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

ZAbdoZA1
bdob1=1
ZAdoZA2)=9
bdob2)=5
ZAb

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


0

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:

Pierwsze sekundy symulacji

Kolejne sekundy symulacji

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!


3
Nie sądzę, że to działa. Ponieważ przepustowość jest taka sama, jedyną różnicą, którą widzą A i B, jest to, że jeśli zaczną się w tym samym czasie, B czeka 3 sekundy przed otrzymaniem jakichkolwiek danych, a A czeka 1 s. Ale nie mają wspólnego zegara, więc nie wiedzą, że zaczęli w tym samym czasie. Może A nic nie słyszy przez 10 sekund, ponieważ zaczął najpierw uruchamiać protokół.
David Richerby

Nie ma wymogu, aby rozpocząć w tym samym czasie, gdy każdy może rozpocząć w dowolnym momencie. Obaj muszą działać przez pewien czas. Doceniam poświęcenie czasu na sprawdzenie, ale proszę przeczytać jeszcze raz. Jest to metoda statystyczna i obejmuje konwergencję. Nie twierdzę, że jestem w 100%, to absolutnie słuszne, ponieważ nie przeprowadziłem symulacji, ale moim zdaniem tak naprawdę nie ma zastosowania. Być może wyjaśnia to ideę bardziej ogólnie: jeśli zaakceptujesz, że produkt opóźniający przepustowość * jest różny dla dwóch łączy, wówczas jedno łącze będzie w rzeczywistości zawierać więcej pakietów - i to może być wyczuwalne przez algo powyżej ...
użytkownik3134164

Nie sądzę, że źle zrozumiałem, ale jest to możliwe. Czy zgadzasz się, że przepustowość jest taka sama, więc zarówno A, jak i B odbierają dane z tą samą prędkością? Jeśli tak, to czy oboje nie zbiegną się w dokładnie to samo?
David Richerby

Tak, oczywiście, otrzymują w tym samym tempie, co nie znaczy, że zbiegają się w tym samym. W sieci są pakiety A i B, pytanie brzmi, jaki jest stosunek obserwowanych pakietów A do B. Przeprowadziłem teraz prostą symulację i ciągle otrzymuję błąd. Aby uzyskać pomysł, ponieważ chyba nie mogę opublikować tutaj całego tego założenia, załóżmy, że b jest taki, że 1 pakiet zajmuje jedną sekundę transmisji. Następnie przesyłane są zawsze 4 pakiety. Zastosuj algorytm i boom, którym udało się zmierzyć OTT, unikając zsynchronizowanych metod zegara / zdarzeń, które nie działają z metodami zbieżności statystycznej!
user3134164

Jaka jest „proporcja pakietów A do B”?
Gilles „SO- przestań być zły”

0

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

P.xxRxx

  • R1=(1-R2))×(1-P.2))R2)=(1-R1)×(1-P.1)1-R2)1-P.2)
  • R1R2)R11-R1R2)1-R2)

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.


Witamy w informatyce ! Twoja odpowiedź wygląda ładnie, ale, jak sam twierdzisz, jest tak naprawdę dogłębnym komentarzem do uwagi @ user3134164. Myślę, że możesz rozwiązać ten problem w następujący sposób: 1) Spróbuj rozszerzyć swoją odpowiedź, aby była to również odpowiedź na rzeczywiste pytanie. lub 2) Utwórz nowe pytanie, które zasadniczo zawiera kluczowe błędne przekonanie z komentarza użytkownika i odpowiedzi własnej z odpowiedzią podobną do tej. Który z nich jest odpowiedni, zależy od ciebie. Myślę, że może zadanie nowego pytania jest dobrym pomysłem, ale może możesz rozwinąć więcej, niż myślę. Zapytaj, czy masz dodatkowe pytania.
Dyskretna jaszczurka

Oczywiście, @ user3134164 może również „promować” komentarz w pytaniu,
Dyskretna jaszczurka

„Px prawdopodobieństwo, że robot x wybierze własne pakiety po otrzymaniu jednego z pakietów drugiego robota” pochodzi z funkcji losowej komputera (), jak w założeniu - na przykład dla dwóch rodzajów pakietów będzie to zawsze 0,5. Jeśli funkcja random () jest wystarczająco jednorodna, wówczas można obliczyć „rzeczywisty stosunek opóźnienia RTT A do B”. Według twojej definicji R myślę, że R1 = (1-R2) * 0,5, więc stosunek jest znany. Nadal uważam, że moja odpowiedź działa dobrze. Dziękuję bardzo za poświęcenie czasu na przyjrzenie się temu.
user3134164
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.