Protokoll för skjutfönster
Ett glidande fönsterprotokoll är en funktion i paketbaserade dataöverföringsprotokoll . Sliding window-protokoll används där tillförlitlig leverans i ordning av paket krävs, såsom i datalänklagret ( OSI lager 2 ) såväl som i Transmission Control Protocol (TCP). De används också för att förbättra effektiviteten när kanalen kan ha 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 säkerställa att den mottagits korrekt, kanske en kontrollsumma . Paradigmet liknar ett fönster som glider i sidled för att tillåta inmatning av nya paket och avvisa de som redan har bekräftats. När mottagaren verifierar datan, skickar den en bekräftelsesignal , eller "ACK", tillbaka till avsändaren för att indikera att den kan skicka nästa paket. I ett enkelt automatic repeat request protocol) stannar avsändaren efter varje paket och väntar på att mottagaren ska ACK. Detta säkerställer att paket kommer fram i rätt ordning, eftersom endast ett kan skickas åt gången.
Den tid som det tar för ACK-signalen att tas emot kan representera en betydande tidsperiod jämfört med den tid som behövs för att skicka paketet. I detta fall kan den totala genomströmningen vara mycket lägre än vad som är teoretiskt möjligt. För att åtgärda detta tillåter glidfönsterprotokoll att ett utvalt antal paket, fönstret , skickas utan att behöva vänta på ett ACK. Varje paket får ett sekvensnummer och ACK skickar tillbaka det numret. Protokollet håller reda på vilka paket som har blivit ACKade och när de tas emot skickas fler paket. glider fönstret längs strömmen 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 i sig 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önsterförsedda protokoll som XMODEM . Se även SEAlink .
Grundläggande koncept
Begreppsmässigt tilldelas varje del av överföringen (paket i de flesta datalänkslager, men bytes i TCP) ett unikt konsekutivt sekvensnummer, och mottagaren använder numren för att placera mottagna paket i rätt ordning, kassera dubbletter av paket 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 sändas eller tas emot vid varje given tidpunkt, tillåter ett glidande fönsterprotokoll att ett obegränsat antal paket kan 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 ännu inte ska bekräftas av mottagaren. Mottagaren informerar sändaren i varje bekräftelsepaket om den aktuella maximala mottagarbuffertstorleken (fönstergräns). TCP-huvudet använder ett 16 bitars fält för att rapportera mottagarfönstrets storlek 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 startar sändaren med lågt paketantal och ökar antalet paket i varje sändning efter att ha tagit emot bekräftelsepaket från mottagaren. För varje ack-paket som tas emot, glider fönstret med ett paket (logiskt) för att sända ett nytt paket. När fönstertröskeln nås, sänder sändaren ett paket för ett mottaget ack-paket.
Om fönstergränsen är 10 paket kan sändaren i långsam startläge börja sända ett paket följt av två paket (innan två paket skickas måste ett paketackum tas emot), följt av tre paket och så vidare tills 10 paket. Men efter att ha nått 10 paket, begränsas ytterligare sändningar till ett paket som överförs för ett mottaget ack-paket. I en simulering ser detta ut som om fönstret rör sig ett paketavstånd för varje mottaget ack-paket. På mottagarsidan flyttar fönstret också ett paket för varje mottaget paket.
Sliding window-metoden säkerställer att trafikstockningar på nätverket undviks. Applikationsskiktet kommer fortfarande att erbjuda data för överföring till TCP utan att oroa sig för problem med trafikstockningar i nätverket eftersom TCP på avsändar- och mottagarsidan implementerar glidande fö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 sända av det skjutbara fönsterprotokollet tidigare än en tur och retur fördröjningstid (RTT). Gränsen för mängden data som den kan skicka innan den stannar för att vänta på en bekräftelse bör vara större än bandbreddsfördröjningsprodukten för kommunikationslänken. Om det inte är det kommer protokollet att begränsa länkens effektiva bandbredd .
Motivering
I vilket kommunikationsprotokoll som helst baserat på automatisk upprepad begäran om felkontroll måste mottagaren bekräfta mottagna paket. Om sändaren inte får en bekräftelse inom rimlig tid, skickar den om uppgifterna.
En sändare som inte får en bekräftelse kan inte veta om mottagaren faktiskt tagit emot paketet; det kan vara så att den har tappats eller skadats under överföringen. Om feldetekteringsmekanismen avslöjar korruption kommer paketet att ignoreras av mottagaren och en negativ eller duplicerad bekräftelse kommer att skickas av mottagaren. Mottagaren kan också vara konfigurerad 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 har gått förlorad eller skadad i överföringsmediet. I det här fallet måste mottagaren bekräfta återsändningen för att förhindra att data kontinuerligt skickas på nytt, men måste annars ignorera den.
Protokolldrift
Sändaren och mottagaren har vardera ett aktuellt sekvensnummer . nt nr respektive De har också varsin fönsterstorlek w t och w r . Fönsterstorlekarna kan variera, men i enklare implementeringar är de fasta. Fönsterstorleken måste vara större än noll för att framsteg ska kunna göras.
Som typiskt implementerat är nt nästa paket som ska sändas, dvs sekvensnumret för det första paketet som ännu inte har sänts. På samma sätt n r det första paketet som ännu inte tagits emot. Båda siffrorna ökar monotont med tiden; de bara ökar.
Mottagaren kan också hålla reda på det högsta sekvensnumret som hittills 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. Notera skillnaden: alla paket under n r har tagits emot, inga paket ovanför n s har tagits emot, och mellan n r och n s har några paket tagits emot.
När mottagaren tar emot ett paket uppdaterar den dess variabler på lämpligt sätt och sänder en bekräftelse med den 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 tagits emot, 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 bekräftelsen som tas emot av sändaren kan inte vara högre än den högsta n r som kvitteras av mottagaren.
- n r ≤ n s : Spännet av helt mottagna paket kan inte sträcka sig längre än till slutet av 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 den högsta mottagna bekräftelsen och sändningsfönstrets storlek.
Sändarens funktion
Närhelst sändaren har data att skicka kan den sända upp till w t paket före den senaste bekräftelsen n a . Det vill säga, den kan sända paketnummer n t så länge som n t < n a + w t .
I frånvaro av ett kommunikationsfel får sändaren snart en bekräftelse för alla paket den har skickat, vilket lämnar n a lika med n t . Om detta inte sker efter en rimlig fördröjning måste sändaren återsända paketen mellan n a och n t .
Tekniker för att definiera "rimlig fördröjning" kan vara extremt komplicerade, men de påverkar bara effektiviteten; den grundläggande tillförlitligheten för skjutfönsterprotokollet beror inte på detaljerna.
Mottagarens funktion
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 nr . , ökas mottagningssekvensnumret med 1, och möjligen mer om ytterligare på varandra följande paket tidigare tagits emot och lagrats Om x > n r lagras paketet tills alla föregående paket har tagits emot. Om x ≥ n s uppdateras den senare till n s = x +1.
Om paketets nummer inte finns inom mottagningsfönstret kasserar mottagaren det och ändrar inte n r eller n s .
Oavsett om paketet accepterades eller inte, sänder mottagaren en bekräftelse som innehåller strömmen nr . (Bekräftelsen kan också innehålla information om ytterligare paket som tas emot mellan n r och n s , men det hjälper bara effektiviteten.)
Observera att det inte är någon mening med att ha mottagningsfönstret w r större än sändningsfönstret w t , eftersom det inte finns någon anledning att oroa sig för att ta emot ett paket som aldrig kommer att sändas; det användbara området är 1 ≤ w r ≤ w t .
Sekvensnummerintervall krävs
Hittills har protokollet beskrivits som om sekvensnummer är av obegränsad storlek, ständigt ökande. Istället för att sända hela sekvensnumret x i meddelanden är det emellertid möjligt att sända endast xmodN , för vissa ändliga N. ( N är vanligtvis en potens av 2. )
Till exempel kommer sändaren endast att ta emot bekräftelser inom området n a till n t inklusive. Eftersom den garanterar att n t − n a ≤ w t , finns det som mest w t +1 möjliga sekvensnummer som kan komma fram vid vilken tidpunkt som helst. Således kan sändaren entydigt avkoda sekvensnumret så länge som N > wt .
En starkare begränsning påläggs av mottagaren. Protokollets funktion beror på att mottagaren på ett tillförlitligt sätt kan särskilja nya paket (som bör accepteras och bearbetas) från återsändningar av gamla paket (som bör kasseras och den sista bekräftelsen återsändas). Detta kan göras med kunskap om sändarens fönsterstorlek. Efter att ha tagit emot ett paket numrerat x vet mottagaren att x < n a + w t , alltså n a > x − w t . Således kommer paket numrerade x − w t aldrig mer att återsändas.
Det lägsta sekvensnumret 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 bekräftelsen som någonsin skickats, vilket är n r . Så det högsta sekvensnumret vi möjligen kan se är n r + w t ≤ n s + w t .
Det finns alltså 2 w olika sekvensnummer som mottagaren kan ta emot när som helst. Det kan därför tyckas 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 återsända en bekräftelse. Således är det bara nödvändigt att N ≥ w t + w r . Eftersom det är vanligt att ha w r < w t (se t.ex. Go-Back-N nedan), kan detta tillåta större w t inom ett fast N .
Exempel
Det enklaste skjutfönstret: stopp-och-vänta
Även om det vanligtvis skiljer sig från protokollet med skjutfönster, är stop-and-wait ARQ- protokollet faktiskt den enklaste möjliga implementeringen av det. Sändningsfönstret är 1 paket och mottagningsfönstret är 1 paket. Sålunda krävs N = 2 möjliga sekvensnummer (lämpligen representerade av en enda bit ).
Tvetydighet exempel
Sändaren skickar växelvis paket märkta "udda" och "jämnt". Bekräftelserna säger också "udda" och "jämnt". Antag att sändaren, efter att ha skickat ett udda paket, inte väntade på en udda bekräftelse, utan istället omedelbart skickade följande jämna paket. Den kan då få en bekräftelse som säger "förväntar sig ett udda paket nästa". Detta skulle lämna sändaren i ett problem: har mottagaren tagit emot båda paketen, eller ingetdera?
Gå tillbaka-N
Go-Back-N ARQ är det glidande fönsterprotokollet med w t >1, men en fast w r =1. Mottagaren vägrar att acceptera något paket utom nästa i följd. Om ett paket försvinner under överföring ignoreras följande paket tills det saknade paketet återsänds, en minsta förlust på en tur och retur . Av denna anledning är det ineffektivt på länkar som ofta lider av paketförlust.
Tvetydighet exempel
Antag att vi använder ett 3-bitars sekvensnummer, som är typiskt för HDLC . Detta ger N =23 = 8. Eftersom w r =1 måste vi begränsa w t ≤7. Detta beror på att det finns 8 möjliga resultat efter att ha sänt 7 paket: Allt från 0 till 7 paket kunde ha tagits emot framgångsrikt. Detta är 8 möjligheter, och sändaren behöver tillräckligt med information i bekräftelsen för att särskilja dem alla.
Om sändaren skickade 8 paket utan att vänta på bekräftelse, kan den hamna i ett problem som liknar stoppa-och-vänta-fallet: betyder bekräftelsen att alla 8 paket togs emot framgångsrikt, eller inget av dem?
Selektiv upprepning
Det mest allmänna fallet med protokollet för glidfönster är Selective Repeat ARQ . Detta kräver en mycket mer kapabel mottagare, som kan ta emot paket med sekvensnummer högre än nuvarande n r och lagra dem tills luckan är fylld.
Fördelen är dock att det inte är nödvändigt att kassera efterföljande korrekta data under en tur och retur innan sändaren kan informeras om att en återsändning 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 bandbreddsfö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.
Tvetydighet exempel
Det extremt populära HDLC-protokollet använder ett 3-bitars sekvensnummer och har valfri möjlighet för selektiv upprepning. Men om selektiv upprepning ska användas måste kravet att n t + n r ≤ 8 bibehå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.
Anta nu att mottagaren ser följande serie av paket (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 den begär en återsändning av paket 7. Det är dock också möjligt att sändaren misslyckades med att ta emot några bekräftelser och har återsänt 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 bekräftelser gått förlorade så skulle sändaren ha stannat efter paket 5. När den tar emot paket 6 kan mottagaren dra slutsatsen att sändaren tagit emot bekräftelsen för paket 0 (sändarens n a ≥1 ) , och därför måste följande paket numrerat 0 vara paket 8.
Tillägg
Det finns många sätt som protokollet kan utökas på:
- Ovanstående exempel antog att paket aldrig omordnas vid överföring; de kan gå förlorade under transporten ( felupptäckt gör korruption likvärdig med förlust), men kommer aldrig att visas ur funktion. Protokollet kan utökas för att stödja paketomordning, så länge avståndet kan begränsas; sekvensnummermodulen N måste utökas med det maximala felordningsavståndet.
- Det är möjligt att inte kvittera varje paket, så länge en bekräftelse skickas så småningom om det blir en paus. Till exempel bekräftar TCP normalt vartannat paket.
- Det är vanligt att omedelbart informera sändaren om en lucka i paketsekvensen upptäcks. HDLC har ett speciellt REJ (reject)-paket för detta.
- Sändnings- och mottagningsfönsterstorlekarna kan ändras under kommunikation, så länge som deras summa förblir inom gränsen för N . Normalt tilldelas de var och en maxvärden som respekterar den gränsen, men arbetsvärdet vid varje given tidpunkt kan vara mindre än maxvärdet. Särskilt:
- Det är vanligt att minska storleken på sändningsfönstret för att sakta ner överföringen för att matcha länkens hastighet och undvika mättnad eller överbelastning .
- 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 enstaka förlorat paket; medan man väntar 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
- 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