Minimum-parprotokoll

Minimi-paren (eller MP) är ett aktivt mätprotokoll för att i realtid uppskatta den minsta av framåt- och bakåtriktade envägsnätverksfördröjningar ( OWDs). Den är designad för att fungera i fientliga miljöer, där en uppsättning av tre nätverksnoder kan uppskatta en övre gräns för OWD mellan sig själva och en fjärde otillförlitlig nod. Alla fyra noderna måste samarbeta, även om ärligt samarbete från den fjärde noden inte krävs. Målet är att utföra sådana uppskattningar utan att involvera de otillförlitliga noderna i klocksynkronisering , och på ett sätt som är mer exakt än bara halva tur-och-retur-tiden (RTT). MP-protokollet kan användas i fördröjningskänsliga applikationer (som att placera innehållsleveransnätverk ) eller för säker geolokalisering på Internet .

Metodik

Illustration av MP-protokollet. Ett tal i cell <i, j> indikerar den beräknade OWD (t.ex. i millisekunder) från noden som anges på rad i till nod X till noden som anges i kolumn j .

MP-protokollet kräver att de tre betrodda nätverksnoderna synkroniserar sina klockor och säkert har tillgång till sina publika nycklar, vilket skulle kunna uppnås genom ett slutet offentligt nyckel-infrastruktursystem (PKI). Den opålitliga noden behöver inte följa efter eftersom den inte antas samarbeta ärligt. För att uppskatta en övre gräns till den minsta av framåt och bakåt OWD mellan nod A och den opålitliga noden X (se figuren för notation), upprättar X först en applikationslageranslutning till alla tre noderna. Detta kan göras transparent över webbläsaren med t.ex. WebSockets . De tre noderna turas sedan om att utbyta digitalt signerade tidsstämplar.

Förutsatt att nod A börjar, skickar den en signerad tidsstämpel till X . Nod X vidarebefordrar det meddelandet till de andra två noderna. När meddelandet tas emot, registreras dess mottagningstid. Den mottagande noden verifierar sedan signaturen och beräknar den tid det tog meddelandet att passera nätverket från dess upphovsman till mottagaren som passerade den opålitliga noden. Detta görs genom att subtrahera tidsstämpeln i meddelandet från mottagningstiden. Nod B upprepar sedan processen, följt av nod C. Efter att alla tre noderna har turats om, slutar de med sex fördröjningsuppskattningar som motsvarar länkarna:

A → X → B och B → X → A
A → X → C och C → X → A
B → X → C och C → X → B

För att uppskatta den minsta av framåt- och bakåt-OWD på de tre nätverkslänkarna mellan A , B , C och X , tas minimum av varje sådant par ovan (dvs. det större kasseras). Vart och ett av de tre paren representerar sedan en ungefärlig till den mindre OWD på varje länk, vilket genererar ett system med tre ekvationer i tre okända. Att lösa dessa samtidigt för a , b och c (se figur) ger fördröjningsuppskattningen.

Numeriskt exempel

Antag att de faktiska fördröjningarna (t.ex. i millisekunder) till nod X från noderna A , B och C och vice versa är följande:


	A	B	C
Till nod X	5	8	2
Från nod X	6	4	4

Det är de okända förseningarna. Vi måste uppskatta den minsta av framåt och bakåt på var och en av de tre länkarna. I det här exemplet är den minsta 5 ms, 4 ms och 2 ms på länkarna mellan X och de tre betrodda noderna ( A , B och C ). När noderna utbyter tidsstämpelmeddelanden kan de bara se följande:

A → X → B = 9 ms och B → X → A = 14 ms (9 ms är det mindre)
A → X → C = 9 ms och C → X → A = 8 ms (8 ms är det mindre)
B → X → C = 12 ms och C → X → B = 6 ms (6 ms är det mindre)

Ekvationssystemet blir alltså:


 $a+b=9$  $a+c=8$  $b+c=6$

vilket resulterar i uppskattningar till de mindre OWDs av:


 $a=5,5~{\text{ms}}$  $b=3,5~{\text{ms}}$  $c=2,5~{ \text{ms}}$

I detta fall är de absoluta felen $|5-5,5|=0,5~{\text{ms}}$ , $|4-3.5|=0.5~{\text{ms}}$ och $|2-2.5|=0.5~{\text{ms}}$ på alla tre respektive länkar. Som jämförelse skulle den genomsnittliga RTT beräkna OWD på alla tre länkarna som 5,5 ms, 6 ms och 3 ms, vilket resulterar i absoluta fel på 0,5 ms, 2 ms respektive 1 ms. Därför är MP-protokollet mer exakt i det här exemplet.

Analys

Genom att injicera konstgjorda fördröjningar genom att t.ex. hålla kvar meddelandet en liten stund istället för att snabbt vidarebefordra det, gör det möjligt för den opålitliga noden att öka de uppskattade OWDs. MP-protokollet kan således uppskatta en övre gräns för OWDs på alla tre länkarna kollektivt mellan de betrodda noderna och den otillförlitliga. Till exempel, om de uppskattade fördröjningarna (framåt eller bakåt) var 30 ms, 40 ms och 50 ms, kan den faktiska inte vara 60 ms, 70 ms och 80 ms eftersom det betyder att den otillförlitliga noden lyckades minska alla tre tillsammans, vilket är svårt att uppnå eftersom förseningar är bundna av överföringsmediets fysiska egenskaper. Observera dock att den otillförlitliga noden i vissa fall kan minska en delmängd av länkarna, men inte alla, genom att selektivt fördröja några av länkarna.

Jämfört med genomsnittet (dvs. RTT/2) returnerar MP-protokollet aldrig en uppskattning till den minsta av framåt- och bakåt-OWD som är större än den som returneras av medelmetoden. Dessutom har sannolikhetsfördelningen av absolut fel för MP-protokollet härletts som en funktion av den underliggande fördröjningsfördelningen. Detta är användbart eftersom det möjliggör beräkning av förväntat fel med kännedom om arten av fördröjningar på länkarna mellan den otillförlitliga noden och de betrodda.

Se även