Skjutfönsterprotokoll - Sliding window protocol
Ett glidande fönster-protokoll är en funktion av paketbaserad dataöverföring protokoll . Skjutfönsterprotokoll används där tillförlitlig beställning av paket krävs, till exempel i datalänkskiktet ( OSI-lager 2 ) samt i Transmission Control Protocol (TCP). De används också för att förbättra effektiviteten när kanalen kan innehålla hög latens .
Paketbaserade system är baserade på idén att skicka ett parti data, paketet , tillsammans med ytterligare data som gör att mottagaren kan se till att den mottogs korrekt, kanske en kontrollsumma . Paradigmet liknar ett fönster som glider åt sidan för att tillåta inmatning av färska paket och avvisa de som redan har bekräftats. När mottagaren verifierar data skickar den en bekräftelsessignal , eller "ACK", tillbaka till avsändaren för att indikera att den kan skicka nästa paket. I ett enkelt automatiskt upprepningsförfrågningsprotokoll (ARQ) stannar avsändaren efter varje paket och väntar på att mottagaren ACK. Detta säkerställer att paket kommer i rätt ordning, eftersom endast ett kan skickas åt gången.
Den tid det tar för ACK -signalen att tas emot kan representera en betydande tid jämfört med den tid som krävs för att skicka paketet. I detta fall kan den totala genomströmningen vara mycket lägre än teoretiskt möjligt. För att åtgärda detta kan glidande fönsterprotokoll tillåta att ett valt antal paket, fönstret , skickas utan att behöva vänta på en ACK. Varje paket får ett sekvensnummer och ACK: erna skickar tillbaka det numret. Protokollet håller reda på vilka paket som har ACKats, och när de tas emot skickas fler paket. På detta sätt glider fönstret längs den ström av paket som utgör överföringen.
Skjutfönster är en viktig del av många protokoll. Det är en viktig del av TCP-protokollet, som tillåter paket att komma ur funktion, och finns också i många filöverföringsprotokoll som UUCP-g och ZMODEM som ett sätt att förbättra effektiviteten jämfört med icke-fönsterfria protokoll som XMODEM .
Grundläggande koncept
Konceptuellt tilldelas varje del av överföringen (paket i de flesta datalänklagren, men byte i TCP) ett unikt på varandra följande sekvensnummer, och mottagaren använder numren för att placera mottagna paket i rätt ordning, kassera dubblettpaket och identifiera saknade . Problemet med detta är att det inte finns någon gräns för storleken på sekvensnumret som kan krävas.
Genom att sätta gränser för antalet paket som kan överföras eller tas emot vid varje given tidpunkt tillåter ett glidande fönsterprotokoll ett obegränsat antal paket att kommuniceras med hjälp av sekvensnummer med fast storlek. Termen "fönster" på sändarsidan representerar den logiska gränsen för det totala antalet paket som mottagaren ännu inte ska bekräfta. Mottagaren informerar sändaren i varje kvittenspaket om den aktuella maximala mottagarens buffertstorlek (fönstergräns). TCP -rubriken använder ett 16 -bitars fält för att rapportera mottagarfönsterstorleken till avsändaren. Därför är det största fönstret som kan användas 2 16 = 64 kilobyte.
I långsam startläge börjar sändaren med lågt paketantal och ökar antalet paket i varje sändning efter mottagande av bekräftelsepaket från mottagaren. För varje mottaget paket glider fönstret ett paket (logiskt) för att överföra ett nytt paket. När fönstertröskeln nås sänder sändaren ett paket för ett mottaget paket.
Om fönstergränsen är 10 paket kan sändaren i sakta startläge börja sända ett paket följt av två paket (innan du skickar två paket måste ett paketack tas emot), följt av tre paket och så vidare tills 10 paket. Men efter att ha nått 10 paket är ytterligare överföringar begränsade till ett paket som överförs för ett mottaget paket. I en simulering verkar detta som om fönstret rör sig med ett paketavstånd för varje mottaget paket. På mottagarsidan flyttar fönstret också ett paket för varje paket som tas emot.
Glidfönstermetoden säkerställer att trafikstockningar i nätverket undviks. Applikationsskiktet kommer fortfarande att erbjuda data för överföring till TCP utan att oroa sig för problem med nätverkstrafik när TCP på avsändar- och mottagarsidan implementerar glidfönster i paketbuffert. Fönsterstorleken kan variera dynamiskt beroende på nätverkstrafik.
För högsta möjliga genomströmning är det viktigt att sändaren inte tvingas sluta skicka med glidfönsterprotokollet tidigare än en tur -retur-fördröjningstid (RTT). Gränsen för mängden data som den kan skicka innan den slutar vänta på ett kvitto bör vara större än produkten för bandbreddfördröjning av kommunikationslänken. Om det inte är det kommer protokollet att begränsa länkens effektiva bandbredd .
Motivering
I alla kommunikationsprotokoll som bygger på automatisk upprepad begäran om felkontroll måste mottagaren bekräfta mottagna paket. Om sändaren inte får ett kvitto inom rimlig tid skickar den data igen.
En sändare som inte får en bekräftelse kan inte veta om mottagaren faktiskt mottog paketet; det kan vara så att den försvann eller skadades i transmissionen. Om feldetekteringsmekanismen avslöjar korruption ignoreras paketet av mottagaren och en negativ eller duplicerad bekräftelse skickas av mottagaren. Mottagaren kan också konfigureras att inte skicka någon bekräftelse alls. På samma sätt är mottagaren vanligtvis osäker på om dess bekräftelser tas emot. Det kan vara så att en bekräftelse har skickats, men förlorats eller skadats i överföringsmediet. I detta fall måste mottagaren bekräfta vidarebefordran för att förhindra att data kontinuerligt skickas vidare, men måste annars ignorera den.
Protokoll drift
Sändaren och mottagaren har var och en ett aktuellt sekvensnummer n t respektive n r . De har också en fönsterstorlek w t och w r . Fönsterstorleken kan variera, men i enklare implementeringar är de fixade. Fönstret måste vara större än noll för att eventuella framsteg ska kunna göras.
Som typiskt implementerat är n t nästa paket som ska sändas, dvs sekvensnumret för det första paketet som ännu inte överförs. På samma sätt är n r det första paketet som ännu inte mottagits. Båda siffrorna ökar monotont med tiden; de ökar bara någonsin.
Mottagaren kan också hålla reda på det högsta sekvensnummer som ännu tagits emot; variabeln n s är en mer än sekvensnumret för det högsta mottagna sekvensnumret. För enkla mottagare som bara accepterar paket i ordning ( w r = 1) är detta detsamma som n r , men kan vara större om w r > 1. Observera skillnaden: alla paket under n r har tagits emot, inga paket ovan n s har tagits emot, och mellan n r och n s , har vissa paket mottagits.
När mottagaren tar emot ett paket uppdaterar den sina variabler på lämpligt sätt och sänder en bekräftelse med det nya n r . Sändaren håller reda på den högsta bekräftelsen den har fått n a . Sändaren vet att alla paket upp till, men inte inklusive n a har mottagits, men är osäker på paket mellan n a och n s ; dvs n a ≤ n r ≤ n s .
Sekvensnumren följer alltid regeln att n a ≤ n r ≤ n s ≤ n t ≤ n a + w t . Det är:
- n a ≤ n r : Den högsta kvitteringen som mottagaren mottar kan inte vara högre än den högsta n r som mottagaren bekräftar.
- n r ≤ n s : Intervallet för fullt mottagna paket kan inte sträcka sig längre än slutet på de delvis mottagna paketen.
- n s ≤ n t : Det högsta mottagna paketet kan inte vara högre än det högsta skickade paketet.
- n t ≤ n a + w t : Det högsta paketet som skickas begränsas av det högsta mottagna kvittot och sändningsfönstret.
Sändardrift
Närhelst sändaren har data att sända, kan den sända upp till w t paket inför den senaste bekräftelse n en . Det vill säga, det kan sända paketnummer n t så länge n t < n a + w t .
I avsaknad av ett kommunikationsfel får sändaren snart ett kvitto på alla paket den har skickat, vilket ger n ett lika med n t . Om detta inte sker efter en rimlig fördröjning måste sändaren överföra paketen mellan n a och n t .
Tekniker för att definiera "rimlig fördröjning" kan vara extremt utarbetade, men de påverkar bara effektiviteten; den grundläggande tillförlitligheten för glidfönsterprotokollet beror inte på detaljerna.
Mottagare
Varje gång ett paket numrerat x tas emot kontrollerar mottagaren om det faller i mottagningsfönstret, n r ≤ x < n r + w r . (De enklaste mottagarna behöver bara hålla reda på ett värde n r = n s .) Om det faller inom fönstret accepterar mottagaren det. Om det är numrerat n r ökas mottagningssekvensnumret med 1, och möjligen mer om ytterligare på varandra följande paket tidigare mottogs och lagrades. Om x > n r lagras paketet tills alla föregående paket har mottagits. Om x ≥ n s uppdateras det senare till n s = x +1.
Om paketets nummer inte ligger inom mottagningsfönstret, kasserar mottagaren det och ändrar inte n r eller n s .
Oavsett om paketet accepterades eller inte, sänder mottagaren ett kvitto som innehåller det aktuella n r . (Bekräftelsen kan också innehålla information om ytterligare paket som tas emot mellan n r eller n s , men det hjälper bara effektiviteten.)
Observera att det inte är någon mening med mottagningsfönstret w r större än sändningsfönstret w t , eftersom det inte finns någon anledning att oroa sig emot ett paket som aldrig kommer att sändas; det användbara intervallet är 1 ≤ w r ≤ w t .
Sekvensnummerintervall krävs
Hittills har protokollet beskrivits som om sekvensnummer är av obegränsad storlek, ständigt ökande. Emellertid, än att överföra den fullständiga sekvensnumret snarare x i meddelanden, är det möjligt att sända endast x mod N , av någon ändlig N . ( N är vanligtvis en effekt på 2. )
Till exempel kommer sändaren endast att ta emot kvitteringar i intervallet n a till n t , inklusive. Eftersom det garanterar att n t - n a ≤ w t , finns det högst w t +1 möjliga sekvensnummer som kan komma fram vid en viss tidpunkt. Sålunda kan sändaren entydigt avkoda sekvensnumret så länge som N > w t .
En starkare begränsning åläggs av mottagaren. Protokollets funktion beror på att mottagaren på ett tillförlitligt sätt kan skilja nya paket (som bör accepteras och bearbetas) från vidarebefordran av gamla paket (som ska kasseras och den sista bekräftelsen vidarebefordras). Detta kan göras med kännedom om sändarens fönsterstorlek. Efter att ha fått ett paket numrerat x vet mottagaren att x < n a + w t , så n a > x - w t . Således kommer paket numrerade x - w t aldrig mer att sändas igen.
Det lägsta sekvensnummer vi någonsin kommer att få i framtiden är n s - w t
Mottagaren vet också att sändarens n a inte kan vara högre än den högsta kvitteringen som någonsin skickats, vilket är n r . Så det högsta sekvensnummer vi möjligen kan se är n r + w t ≤ n s + w t .
Således finns det 2 w t olika sekvensnummer som mottagaren kan ta emot samtidigt. Det kan därför vara att vi måste ha N ≥ 2 w t . Den faktiska gränsen är dock lägre.
Den ytterligare insikten är att mottagaren inte behöver skilja mellan sekvensnummer som är för låga (mindre än n r ) eller som är för höga (större än eller lika med n s + w r ). I båda fallen ignorerar mottagaren paketet förutom att vidaresända ett kvitto. Således är det bara nödvändigt att N ≥ w t + w r . Eftersom det är vanligt att ha w r < w t (t.ex. se Go-Back-N nedan), kan detta tillåta större w t inom en fixerad N .
Exempel
Det enklaste skjutfönstret: stanna och vänta
Även om det vanligtvis skiljer sig från protokollet med skjutfönster, är stopp-och-vänta ARQ- protokollet faktiskt den enklaste möjliga implementeringen av det. Sändningsfönstret är 1 paket och mottagningsfönstret är 1 paket. Således krävs N = 2 möjliga sekvensnummer (bekvämt representerat av en enda bit ).
Tvetydighetsexempel
Sändaren skickar växelvis paket märkta "udda" och "jämna". Bekräftelserna säger också "udda" och "jämna". Antag att sändaren, efter att ha skickat ett udda paket, inte väntat på ett udda kvittering och istället omedelbart skickat följande jämna paket. Det kan då få ett bekräftelse som säger "väntar ett udda paket nästa". Detta skulle lämna sändaren i en fråga: har mottagaren mottagit båda paketen, eller inte heller?
Gå tillbaka-N
Go-Back-N ARQ är det glidande fönstret protokoll med w t > 1, men en fast w r = 1. Mottagaren vägrar att acceptera något paket, men nästa paket i följd. Om ett paket går förlorat under transport ignoreras följande paket tills det saknade paketet sänds igen, en förlust på minst en tur och retur . Av denna anledning är det ineffektivt på länkar som ofta drabbas av paketförlust.
Tvetydighetsexempel
Antag att vi använder ett 3-bitars sekvensnummer, som är typiskt för HDLC . Detta ger N = 2 3 = 8. Eftersom w r = 1 måste vi begränsa w t ≤7. Detta beror på att efter överföring av 7 paket finns det 8 möjliga resultat: Överallt från 0 till 7 paket kunde ha mottagits framgångsrikt. Detta är 8 möjligheter, och sändaren behöver tillräckligt med information i bekräftelsen för att skilja dem alla.
Om sändaren skickade 8 paket utan att vänta på bekräftelse kan det hamna i en fråga som liknar stopp-och-vänta-fallet: betyder bekräftelsen att alla 8 paket mottogs framgångsrikt, eller inget av dem?
Selektiv upprepning
Det mest allmänna fallet med glidfönsterprotokollet är Selective Repeat ARQ . Detta kräver en mycket mer kapabel mottagare, som kan acceptera paket med sekvensnummer som är högre än nuvarande n r och lagra dem tills luckan är fylld.
Fördelen är emellertid att det inte är nödvändigt att kasta följande korrekta data under en rundresetid innan sändaren kan informeras om att en vidarebefordran krävs. Detta är därför att föredra för länkar med låg tillförlitlighet och/eller en produkt med hög bandbreddfördröjning .
Fönsterstorleken w r behöver bara vara större än antalet på varandra följande förlorade paket som kan tolereras. Således är små värden populära; w r = 2 är vanligt.
Tvetydighetsexempel
Det extremt populära HDLC-protokollet använder ett 3-bitars sekvensnummer och har valfri möjlighet för selektiv upprepning. Om selektiv upprepning ska användas måste dock kravet att n t + n r ≤ 8 upprätthållas; om w r ökas till 2 måste w t minskas till 6.
Antag att w r = 2, men en omodifierad sändare används med w t = 7, som vanligtvis används med go-back-N-varianten av HDLC. Antag vidare att mottagaren börjar med n r = n s = 0.
Antag nu att mottagaren ser följande paketserie (alla modulo 8):
- 0 1 2 3 4 5 6 (paus) 0
Eftersom w r = 2 kommer mottagaren att acceptera och lagra det slutliga paketet 0 (tror att det är paket 8 i serien), samtidigt som det begär en återutsändning av paket 7. Det är emellertid också möjligt att sändaren inte mottog några bekräftelser och har vidarebefordrat paket 0. I det senare fallet skulle mottagaren acceptera fel paket som paket 8.
Lösningen är att sändaren begränsar w t ≤6. Med denna begränsning vet mottagaren att om alla kvitteringar förlorades skulle sändaren ha stannat efter paket 5. När den tar emot paket 6 kan mottagaren dra slutsatsen att sändaren mottog kvitteringen för paket 0 (sändarens n a ≥1) , och därför måste följande paket med nummer 0 vara paket 8.
Tillägg
Det finns många sätt att förlänga protokollet:
- Exemplen ovan antog att paket aldrig är ordnade i överföring; de kan gå förlorade under transporten ( feldetektering gör korruption lika med förlust), men kommer aldrig att visas ur funktion. Protokollet kan utökas för att stödja paketbeställning, så länge avståndet kan begränsas; sekvensnummermodulen N måste expanderas med det maximala felbestämda avståndet.
- Det är möjligt att inte bekräfta varje paket, så länge en bekräftelse skickas så småningom om det finns en paus. Till exempel kvitterar TCP normalt vartannat paket.
- Det är vanligt att omedelbart informera sändaren om ett gap i paketsekvensen detekteras. HDLC har ett särskilt REJ -paket (avvisa) för detta.
- De sändnings- och mottagningsfönsterstorlekar kan ändras under kommunikation, så länge som deras summa förblir inom gränsen för N . Normalt tilldelas de var och en maximivärden som respekterar denna gräns, men arbetsvärdet vid varje given tidpunkt kan vara lägre än maxvärdet. Särskilt:
- Det är vanligt att minska sändningsfönstret för att sakta ner överföringen för att matcha länkens hastighet, undvika mättnad eller trängsel .
- En vanlig förenkling av selektiv upprepning är så kallad SREJ-REJ ARQ. Detta fungerar med w r = 2 och buffrar paket efter ett gap, men tillåter bara ett enda förlorat paket; i väntan på det paketet, w r = 1 och om ett andra paket går förlorat, buffras inga fler paket. Detta ger det mesta av prestandafördelarna med det fullständiga selektiva upprepningsprotokollet, med en enklare implementering.
Se även
Referenser
- Comer, Douglas E. "Internetworking with TCP/IP, Volume 1: Principles, Protocols, and Architecture", Prentice Hall, 1995. ISBN 0-13-216987-8
externa länkar
- RFC 1323 - TCP -tillägg för hög prestanda
- TCP -fönsterskalning och trasiga routrar , 2004
- Glidande fönsterdemo ( blixt krävs)
