Protokół minimalnych par

Minimalne pary (lub MP) to aktywny protokół pomiarowy do szacowania w czasie rzeczywistym mniejszych jednokierunkowych opóźnień sieciowych (OWD) do przodu i do tyłu. Jest przeznaczony do pracy w nieprzyjaznych środowiskach, w których zestaw trzech węzłów sieci może oszacować górną granicę OWD między nimi a czwartym niezaufanym węzłem. Wszystkie cztery węzły muszą ze sobą współpracować, chociaż uczciwa współpraca ze strony czwartego węzła nie jest wymagana. Celem jest przeprowadzenie takich szacunków bez angażowania niezaufanych węzłów w synchronizację zegarów oraz w sposób dokładniejszy niż po prostu połowa czasu podróży w obie strony (RTT). Protokół MP może być używany w aplikacjach wrażliwych na opóźnienia (takich jak umieszczanie sieci dostarczania treści ) lub do bezpiecznej geolokalizacji w Internecie .

Metodologia

Ilustracja protokołu MP. Liczba w komórce <i, j> wskazuje obliczoną OWD (np. w milisekundach) od węzła wskazanego w wierszu i do węzła X do węzła wskazanego w kolumnie j .

Protokół MP wymaga, aby trzy zaufane węzły sieci synchronizowały swoje zegary i miały bezpieczny dostęp do swoich kluczy publicznych, co można osiągnąć za pomocą zamkniętego systemu infrastruktury klucza publicznego (PKI). Niezaufany węzeł nie musi iść w jego ślady, ponieważ nie zakłada się uczciwej współpracy. Aby oszacować górną granicę mniejszego z OWD do przodu i do tyłu między węzłem A a niezaufanym węzłem X (patrz notacja na rysunku), X najpierw ustanawia warstwę aplikacji połączenie ze wszystkimi trzema węzłami. Można to zrobić w sposób przejrzysty w przeglądarce, używając np. WebSockets . Następnie trzy węzły na zmianę wymieniają podpisane cyfrowo znaczniki czasu.

Zakładając, że węzeł A zaczyna, wysyła podpisany znacznik czasu do X . Węzeł X przekazuje tę wiadomość do pozostałych dwóch węzłów. Po odebraniu wiadomości rejestrowany jest czas jej odebrania. Węzeł odbiorczy następnie weryfikuje podpis i oblicza czas, w jakim wiadomość przeszła przez sieć od nadawcy do odbiorcy przechodzącego przez niezaufany węzeł. Odbywa się to poprzez odjęcie znacznika czasu w wiadomości od czasu jej otrzymania. węzeł B powtarza proces, a następnie węzeł C . Po tym, jak wszystkie trzy węzły wykonają po kolei, kończą z sześcioma oszacowaniami opóźnień odpowiadającymi łączom:

A → X → B i B → X → A
A → X → C i C → X → A
B → X → C i C → X → B

W celu oszacowania mniejszego z OWD do przodu i do tyłu na trzech łączach sieciowych między A , B , C i X , brane jest minimum z każdej takiej pary powyżej (tj. większa jest odrzucana). Każda z trzech par reprezentuje następnie przybliżenie mniejszego OWD na każdym łączu, co generuje układ trzech równań z trzema niewiadomymi. Rozwiązywanie ich jednocześnie dla a , b i c (patrz rysunek) daje oszacowanie opóźnienia.

Przykład liczbowy

Załóżmy, że rzeczywiste opóźnienia (np. w milisekundach) do węzła X z węzłów A , B i C i odwrotnie są następujące:


	A	B	C
Do węzła X	5	8	2
Z węzła X	6	4	4

To są nieznane opóźnienia. Musimy oszacować mniejszą z wartości do przodu i do tyłu na każdym z trzech łączy. W tym przykładzie mniejszy wynosi 5 ms, 4 ms i 2 ms na łączach między X a trzema zaufanymi węzłami odpowiednio ( A , B i C ). Gdy węzły wymieniają komunikaty ze znacznikami czasu, widzą tylko następujące informacje:

A → X → B = 9 ms i B → X → A = 14 ms (9 ms jest mniejsze)
A → X → C = 9 ms i C → X → A = 8 ms (8 ms jest mniejsze)
B → X → C = 12 ms i C → X → B = 6 ms (6 ms jest mniejsze)

Układ równań staje się zatem:


 $= 9} za$  ${\ Displaystyle a + c = 8}$  ${\ Displaystyle b + c = 6}$

co daje szacunki dla mniejszych OWD:


 ${\ Displaystyle a = 5,5 ~ {\ tekst {ms}}}$  ${\ Displaystyle b = 3,5 ~ {\ tekst {ms}}} do$  ${\ Displaystyle c = 2,5 ~$

W tym przypadku błędy bezwzględne to ${\ Displaystyle | 5-5,5 | = 0,5 ~ {\ tekst {ms}}$ ${\ Displaystyle | 4-3,5 | = 0,5 ~ {\ tekst {ms}}}$ | i ${\ displaystyle | 2-2,5|= 0,5 ~ {\ tekst {ms}}}$ odpowiednio na wszystkich trzech łączach. Dla porównania, średni RTT obliczyłby OWD na wszystkich trzech łączach jako 5,5 ms, 6 ms i 3 ms, co skutkowało błędami bezwzględnymi odpowiednio 0,5 ms, 2 ms i 1 ms. Dlatego protokół MP jest dokładniejszy w tym przykładzie.

Analiza

Wstrzykiwanie sztucznych opóźnień, np. przez chwilę przetrzymując wiadomość zamiast natychmiastowego jej przekazania, umożliwia niezaufanemu węzłowi zwiększenie szacowanych OWD. Protokół MP może zatem oszacować górną granicę dla OWD na wszystkich trzech łączach łącznie między węzłami zaufanymi i niezaufanymi. Na przykład, jeśli szacowane opóźnienia (do przodu lub do tyłu) wynosiły 30 ms, 40 ms i 50 ms, rzeczywiste nie mogą wynosić 60 ms, 70 ms i 80 ms, ponieważ oznacza to, że niezaufanemu węzłowi udało się zredukować wszystkie trzy razem, co jest trudne do osiągnięcia, ponieważ opóźnienia są związane z fizycznymi właściwościami mediów transmisyjnych. Należy jednak zauważyć, że niezaufany węzeł może w niektórych przypadkach być w stanie zredukować podzbiór łączy, ale nie wszystkie, poprzez selektywne opóźnianie niektórych łączy.

W porównaniu ze średnią (tj. RTT/2), protokół MP nigdy nie zwraca oszacowania mniejszego z OWD do przodu i do tyłu, które jest większe niż wartość zwrócona przez metodę uśredniania. Dodatkowo, rozkład prawdopodobieństwa błędu bezwzględnego dla protokołu MP został wyprowadzony jako funkcja podstawowego rozkładu opóźnienia. Jest to przydatne, ponieważ umożliwia obliczenie oczekiwanego błędu znając charakter opóźnień na łączach między niezaufanym a zaufanym węzłem.

Zobacz też