Az eddigi protokollokban adatkeretek csak az egyik irányba haladtak. A legtöbb gyakorlati helyzetben viszont mindkét irányba kell adatokat átvinni. A duplex adatátvitel elérésének egyik módja az, hogy vesszük az előzőekben megismert protokollok közül az egyiknek két példányát úgy, hogy egyiket szimplex adatkapcsolatként az egyik irányba, a másikat szimplex adatkapcsolatként a másik irányba működtetjük. Mindkét adatkapcsolat így megvalósít egy „előremenő” (forward) csatornát (adatok számára) és egy „visszajövő” (reverse) csatornát (nyugták számára). A visszairányú csatorna sávszélessége mindkét esetben majdnem teljesen kihasználatlanul marad.
Jobb ötlet ugyanazt az adatkapcsolatot használni az adatok számára mindkét irányra. Végül is a 2. és 3. protokollban már mindkét irányba továbbítottunk kereteket, és a visszairányú csatornának normális körülmények között ugyanakkora kapacitása van, mint az előreirányúnak. Ebben a modellben az A-tól B felé tartó adatkeretek összekeverednek az A-tól B felé menő nyugtakeretekkel. A vevő a beérkező keret kind mezője alapján tudja megmondani, hogy a keret adat- vagy nyugtakeret-e.
Bár az adat- és a vezérlőkeretek átlapolódása egyetlen adatkapcsolaton történő továbbítás során nagy fejlődés ahhoz képest, mintha két különálló fizikai kapcsolat lenne, még van további fejlődési lehetőség. Amikor egy adatkeret megérkezik, ahelyett, hogy azonnal küldene egy külön vezérlőkeretet, a vevő türtőzteti magát, és megvárja, hogy a hálózati réteg átadja neki a következő csomagot. A nyugtát hozzácsatolja a kimenő adatkerethez (a fejrész ack mezőjét használva). Valójában a nyugta így ingyen utazik a következő kimenő adatkerettel. Az a módszer, amikor a kimenő nyugtákat átmenetileg késleltetjük, hogy rá tudjuk akasztani a következő kimenő adatkeretre, ráültetésként (piggybacking) ismert.
A ráültetés alkalmazásának fő előnye a különálló nyugtakeretekhez képest a csatorna rendelkezésre álló sávszélességének jobb kihasználása. Az ack mező a keret fejrészében csak néhány bitbe kerül, míg egy külön kerethez kellene saját fejrész, a nyugta maga és ellenőrző összeg. Ráadásul a kevesebb elküldött keret a vevő oldalán csökkenti a feldolgozási terhelést is. A következő protokollban, amit megvizsgálunk, a ráültetett nyugta mező csak egy bitet foglal el a keret fejrészében. Egyéb esetekben is ritkán foglal többet néhány bitnél.
A ráültetés azonban olyan komplikációt okoz, ami a különálló nyugtáknál nem jelentkezett. Meddig várakozzon az adatkapcsolati réteg a csomagra, amelyre ráülteti a nyugtát? Ha az adatkapcsolati réteg tovább vár, mint a küldő időzítési intervalluma, a küldő állomás a keretet újraküldi, meghiúsítva a nyugta célját. Ha az adatkapcsolati réteg jós lenne, és meg tudná jósolni a jövőt, meg tudná mondani, hogy mikor fog bejönni a következő csomag a hálózati rétegtől, és attól függően, hogy milyen hosszú a várható várakozás, el tudná dönteni, hogy várjon-e, vagy azonnal küldjön egy külön nyugtakeretet. Természetesen az adatkapcsolati réteg nem tudja megjósolni a jövőt, így valamilyen ad hoc elgondolásra kell hagyatkoznia, mint például, hogy várjon rögzített számú milliszekundumot. Ha az új csomag hamar megérkezik, a nyugtát ráültetjük; ha viszont nem érkezik új csomag az időzítési intervallum végéig, az adatkapcsolati réteg elküld egy önálló nyugtakeretet.
A következő három protokoll a csúszóablakos (sliding window) protokollok osztályába tartozó, kétirányú protokoll. A három protokoll hatékonyság, bonyolultság és pufferigény kérdésében tér el egymástól, ahogy azt később meg is fogjuk tárgyalni. Ezekben, mint a többi csúszóablakos protokollban is, minden kimenő keret tartalmaz egy sorszámot, amely 0 és egy meghatározott legnagyobb érték között lehet. A maximum általában , hogy a sorszámot pontosan be lehessen illeszteni egy n bites mezőbe. A megáll-és-vár csúszóablakos protokoll
-et használ, amellyel a sorszámokat a 0-ra és az 1-re korlátozza, de a fejlettebb változatok tetszőleges n-et is használni tudnak.
Minden csúszóablakos protokoll lényege az, hogy az adóállomás folyamatosan karbantart egy sorszámhalmazt, amely az elküldhető kereteknek felel meg. Azt mondjuk, hogy ezek a keretek az adási ablakba (sending window) esnek. Ehhez hasonlóan a vevő is karbantart egy vételi ablakot (receiving window), amely azon keretek halmazának felel meg, amelyeket befogadhat. Az adó és a vevő ablakainak nem kell azonos alsó és felső határral rendelkeznie, sőt a méretének sem kell megegyeznie. Néhány protokollban az ablakok rögzített méretűek, másokban azonban az idő előrehaladtával nőhetnek vagy csökkenhetnek, ahogyan a kereteket az állomások küldik és veszik.
Habár ezek a protokollok nagyobb szabadságot biztosítanak az adatkapcsolati rétegnek abban, hogy milyen sorrendben küldi és fogadja a kereteket, azért még határozottan nem mondtunk le arról az elvárásról, hogy a protokoll a csomagokat ugyanolyan sorrendben továbbítsa a címzett gép hálózati rétegének, mint amilyen sorrendben a küldő adatkapcsolati rétege azokat megkapta. Azt az elvárásunkat sem változtattuk meg, hogy a fizikai kommunikációs csatorna „vezetékszerű” legyen, vagyis minden keretet a küldés sorrendjében kell továbbítania.
A küldő ablakába eső sorszámok azokat a kereteket jelképezik, amelyeket már az adó elküldött, vagy amelyek elküldhetők, de a vevő még nem nyugtázta. Amikor egy új csomag érkezik a hálózati rétegtől, az megkapja a következő legmagasabb sorszámot, és az ablak felső széle eggyel előre ugrik. Amikor egy nyugta érkezik, akkor az ablak alsó széle lép egyet előre. Ezzel a módszerrel az ablak a még nem nyugtázott keretek listáját tartja folyamatosan karban. A módszerre a 3.15. ábra mutat egy példát.
3.16. ábra - Egy 1-es méretű csúszóablak 3 bites sorszámmal. (a) Kezdetben. (b) Az első keret elküldése után. (c) Az első keret vétele után. (d) Az első nyugta vétele után
Mivel azok a keretek, amelyek a küldő ablakában vannak, végső soron elveszhetnek vagy megsérülhetnek az átvitel során, a küldő állomásnak az összes ilyen keretet a memóriájában kell tartani az esetleges újraküldések miatt. Ezért, ha a maximális ablakméret n, a küldőnek n pufferre van szüksége a nyugtázatlan keretek megtartásához. Ha az ablak eléri a maximális méretét, a küldő adatkapcsolati rétegnek erőszakkal le kell kapcsolnia a hálózati réteget, amíg egy puffer fel nem szabadul.
A vevő adatkapcsolati rétegének ablaka azokhoz a keretekhez tartozik, amelyeket az adatkapcsolati réteg elfogadhat. Minden keret, amely az ablakon belülre esik, a vevő pufferébe kerül. Amikor egy olyan keret érkezik, melynek a sorszáma egyenlő az ablak alsó szélével, a vevő elfogadja, és átadja a hálózati rétegnek és az ablakot eggyel elforgatja. Az olyan kereteket, amelyek az ablakon kívül esnek, eldobja. Az előbbi esetekben egy soron következő nyugtát is továbbít az adónak, hogy az folytatni tudja működését. Megjegyezzük, hogy az 1 méretű ablak azt jelenti, hogy az adatkapcsolati réteg csak sorrendben fogadja el a kereteket, de nagyobb ablakoknál ez nem így van! A hálózati réteget azonban mindig a megfelelő sorrendben táplálja adatokkal, tekintet nélkül arra, hogy mekkora az adatkapcsolati réteg ablakának mérete.
A 3.15. ábrán egy példa látható az 1-es maximális ablakméretre. Kezdetben egyetlen keret sincs kinn, így az adó ablakának alsó és felső szélei egyenlők, de ahogy az idő telik, a helyzet az ábrán látható módon változik. A vételi ablak mérete – az adási ablakkal ellentétben – minden esetben marad a kezdeti értéken, és előre lép, ahogy a következő keret megérkezik és továbbítódik a hálózati réteghez.
Az általános esettel való megbirkózás előtt vizsgáljunk meg egy olyan csúszóablakos protokollt, amelynek maximum 1 nagyságú ablaka lehet. Egy ilyen protokoll a megáll-és-vár technikát alkalmazza, mivel a küldő állomás elküld egy keretet és megvárja ennek nyugtáját, mielőtt a következőt elküldené.
A 3.16. ábra egy ilyen protokollt ábrázol. Hasonlóan a többihez, ez is néhány változó definiálásával kezdődik. A next_frame_to_send azt mutatja meg, hogy éppen melyik keretet próbálja az adóállomás elküldeni. Ehhez hasonlóan, a frame_expected azt mutatja meg, hogy a vevő melyik keretet várja. Mindkét változónál csak 0 és az 1 érték jöhet szóba.
Rendszerint a két adatkapcsolati réteg közül az egyik korábban kezd adni. Ezért csak az egyik adatkapcsolati réteg programjának kellene tartalmaznia a to_physical_layer és a start_timer eljáráshívásokat a fő cikluson kívül. A kezdő gép lekéri az első csomagot a hálózati rétegétől, egy keretet épít belőle, és elküldi azt. Amikor ez a keret (vagy bármelyik) megérkezik, a vevő adatkapcsolati rétege – pontosan úgy, mint a 3. protokollban – megnézi, hogy duplikátum-e. Ha a keret az, amelyiket várta, átadja a hálózati rétegnek, és a vevő ablakát feljebb csúsztatja.
A nyugta mező a legutolsó hibátlanul vett keret sorszámát tartalmazza. Ha ez a szám megegyezik annak a keretnek a sorszámával, amit az adó próbál elküldeni, az adó tudja, hogy végzett a buffer-ben tárolt csomaggal, és lekérheti a következőt a hálózati rétegtől. Ha a sorszám nem egyezik, folytatnia kell a próbálkozást ugyanazzal a kerettel. Minden alkalommal, amikor egy keret érkezik, egyet el is küld.
Most vizsgáljuk meg a 4. protokollt, hogy lássuk, mennyire ellenálló hibás eseménysorozatok esetén! Tételezzük fel, hogy A a 0-s keretét próbálja elküldeni B-nek, és B szintén a 0-s keretét próbálja elküldeni A-nak. Tegyük fel, hogy A elküldi a keretet B-nek, de az időzítési intervalluma egy kicsit rövidebb, mint kellene. Ezért több ízben lejárhat az időzítője, így egy sor azonos keretet küldhet, mindet seq = 0-val és ack = 1-gyel.
Amikor az első érvényes keret megérkezik B-be, az elfogadja és a frame_expected-et 1-re állítja. Az összes ezt követő keretet elutasítja, mert B most olyan keretet vár, melynek a sorszáma 1, nem pedig 0. Továbbá, mivel minden duplikátumnál és B még 0-s nyugtára vár, B nem fog lekérni újabb csomagot a hálózati rétegétől.
Miután mindegyik elutasítandó duplikátum megérkezett, B küld A-nak egy keretet -val és
-val. Végül is ezek közül az egyik megérkezik A-hoz, és A elkezdi küldeni a következő csomagot. Az elveszett keretek vagy idő előtti időtúllépések semmilyen kombinációja nem tudja azt okozni, hogy a protokoll akár megkettőzött csomagokat küldjön a hálózati rétegnek, akár kihagyjon egy csomagot, vagy akár holtpontba kerüljön, tehát a protokoll megfelelően működik.
Hogy megmutassuk, milyen körmönfont események történhetnek egy protokollal, kiemelünk egy sajátos helyzetet: ha mindkét oldal egyszerre küldi el a kezdeti csomagot. Ez a szinkronizációs probléma látható a 3.17. ábrán. Az (a) részben a protokoll normális működése figyelhető meg. A (b) rész a sajátos helyzetet illusztrálja. Ha B megvárja A első keretét, mielőtt a sajátjai közül egyet elküldene, az eseménysorozat olyan, mint az (a) részen látható, és minden keretet elfogadunk.
Ha azonban A és B egyszerre indítja el a kommunikációt, az első kereteik keresztezik egymást, és az adatkapcsolati réteg a (b) részen látható helyzetbe kerülhet. Az (a) ábrán minden keret érkezése új csomagot hoz a hálózati rétegnek, nincsenek duplikátumok. A (b) ábrán a keretek fele duplikátumot tartalmaz, még akkor is, ha nincsenek átviteli hibák. Hasonló helyzetek alakulhatnak ki idő előtti időtúllépések eredményeként, még akkor is, ha az indulásnál egyértelműen csak az egyik állomás kezd adni. Ha többszörös korai időtúllépés következik be, a keretek háromszor vagy még többször is elküldhetők, ami értékes sávszélesség vesztést eredményez.
3.17. ábra - Két eseménysorozat a 4. protokollhoz. (a) Normális működés. (b) Hibás működés. A jelölés: (sorszám, nyugtaszám, csomagsorszám). A csillag azt jelzi, hogy az adatkapcsolati réteg továbbította a keretet a hálózati rétegnek
Az eddigiekben azzal a hallgatólagos feltételezéssel éltünk, hogy egy keret vevőhöz való megérkezéséhez és a nyugta visszaérkezéséhez együttesen szükséges idő elhanyagolható. Néha ez a feltételezés egyáltalán nem helytálló. Ezekben a szituációkban a hosszú körülfordulási idő fontos következményeket von maga után a sávszélesség kihasználtságára nézve. Példának okáért, vegyünk egy 50 kb/s-os műholdas csatornát 500 ms-os körülfordulási idővel. Képzeljük el, hogy a 4. protokollt szeretnénk használni 1000 bites keretek küldésére a műholdon keresztül. A időpillanatban az adóállomás elkezdi küldeni az első keretet. A
ms-ban már a teljes keretet elküldte. Nem előbb, mint
ms érkezik meg a teljes keret a vevőhöz, és nem előbb, mint
ms érkezik vissza a nyugta az adóállomáshoz a legjobb esetben (nincs várakozás a vevőben, és rövid a nyugtakeret). Ez azt jelenti, hogy az adó az idő 500/520 részében, azaz 96%-ában blokkolva van (tehát a rendelkezésre álló sávszélességnek csupán a 4%-át használja ki). Tisztán látszik, hogy a hosszú átviteli idő, a nagy sávszélesség és a rövid keretek kombinációja végzetes a hatékonyságra nézve.
A fent leírt problémát azon szabály következményének tekinthetjük, amely megköveteli az adóállomástól, hogy megvárja az elküldött keret nyugtáját, mielőtt egy másik keretet küldene. Ha lazítunk ezen a korlátozáson, sokkal nagyobb hatékonyságot érhetünk el. A megoldás alapvetően arra épül, hogy megengedjük az adónak, hogy a blokkolódás előtt 1 helyett legfeljebb w darab keretet elküldjön. Elegendően nagy w megválasztásával az adó folyamatosan küldhet kereteket, hiszen a már elküldött keretekre a nyugták azelőtt megérkeznek, mielőtt az ablak betelne, tehát az adó nem blokkolódik.
A megfelelő w megválasztásához tudnunk kell, hogy az adótól a vevőig történő terjedés során hány csomag fér el a kommunikációs csatornán egy időben. Ezt a kapacitást bit mértékegységben meghatározhatjuk a csatorna sávszélességének és egyirányú késleltetésének a szorzatával, más néven a sávszélesség-késleltetés szorzattal (bandwidth-delay product). Ha ezt a mennyiséget elosztjuk a keret bitekben mért hosszával, akkor megkapjuk, hány keret lehet kinn a csatornán. Nevezzük ezt a mennyiséget BD-nek. Ebben az esetben a w-t értékűre kell választani. A BD kétszerese azt mutatja, hogy hány keret lehet a csatornán, ha az adó folyamatosan adja a kereteket, figyelembe véve, hogy a nyugta megérkezésére egy körülfordulásnyi idő szükséges. A „+1” veszi figyelembe azt a tényt, hogy a nyugta elküldése csak egy teljes keret beérkezése után lehetséges.
Az előző példánkban, ahol a sávszélesség 50 kb/s és az egyirányú késleltetés 250 ms, a sávszélesség-késleltetés szorzat 12,5 kilobit, amely 1000 bit hosszúságú keretekkel számolva 12,5 keretnek felel. A kifejezés értéke tehát 26 keret. Tegyük fel, hogy az adó kezdetben a 0. keretet, majd minden 20 ms múlva egy újabb keretet küld. Mire végez 26 keret küldésével, a
Mivel ez az érték a keret feldolgozási idejét elhanyagolja, és a nyugták hosszát 0-nak veszi (ugyanis azok általában rövidek), ezért csupán egy felső határt állapít meg. Az egyenlet viszont jól mutatja, hogy ha a sávszélesség-késleltetés szorzat nagy, akkor szükségszerűen az ablakméretet is nagyra kell választani. Ha a késleltetés nagy, az adó hamar elfogyasztja az ablakméretét – még közepes sávszélesség esetén is –, ahogy a műholdas csatorna esetén láttuk. Hasonlóan, ha a sávszélesség nagy, akkor az adó szintén gyorsan kiüríti az adási ablakot – akár közepes késleltetés esetén is –, hacsak nem használ nagy ablakméretet (például egy 1 Gb/s adatkapcsolat 1 ms késleltetéssel 1 megabites szorzattal rendelkezik). A megáll-és-vár protokoll értéke még egy keretnyi késleltetési idő esetén is kevesebb mint 50% kihasználtságot eredményez.
Azt a módszert, amely több csomagot is mozgásban tart a csatornán, csővezetékezésnek (pipelining) nevezik. A csővezetékezés alkalmazása megbízhatatlan kommunikációs csatornán néhány komoly kérdést vet fel. Először is: mi történik, ha egy hosszú folyam közepén egy keret megsérül vagy elveszik? Mielőtt az adó egyáltalán észrevenné, hogy valami nincs rendben, nagyszámú további keret érkezik meg a vevőhöz. Amikor egy sérült keret érkezik a vevőhöz, nyilvánvalóan el kell dobnia, de mit csináljon az azt követő hibátlan keretekkel? Ne feledkezzünk meg róla, hogy a vevő adatkapcsolati rétegének mindenképpen a helyes sorrendben kell a hálózati rétegnek átadnia a csomagokat. A hiba kezelésére csővezetékezés esetén két alapvető megközelítés létezik, melyeket a 3.18. ábrán mutatunk be.
3.18. ábra - Csővezetékezés és hibakezelés. Egy hiba hatása, (a) ha a vételi ablak mérete 1 (n-nel történő visszalépés esetén), (b) ha a vételi ablak mérete 1-nél nagyobb (szelektív ismétlés esetén)
Az egyik megközelítést n visszalépéses (go-back-n) eljárásnak nevezik. Ekkor a vevő eldobja az összes keretet, amely a hibás után érkezik, és nem küld nyugtát róluk, ahogy az a 3.18.(a) ábrán látható. Ez a stratégia az 1 hosszúságú vételi ablaknak felel meg. Más megközelítésből, az adatkapcsolati réteg elutasít minden keretet, kivéve a soron következőt, amit a hálózati rétegnek át kell adnia. Ha az adó ablaka betelik mielőtt az időzítő lejár, a csővezeték elkezd kiürülni. Végül is az adónak lejár az időzítője, és újraküldi az összes nyugtázatlan keretet, kezdve a sérült vagy elveszett kerettel. Ez a megközelítés nagy sávszélességet pazarolhat el, ha nagy a hibaarány.
Amikor a vevő ablakának mérete nagy, akkor a 0-s és 1-es sorszámú kereteket a vevő helyesen veszi és nyugtázza. A 2-es sorszámú keret azonban megrongálódott vagy elveszett. Az adó ezt nem tudva, folytatja a további keretek küldését, amíg a 2-es keret időzítése le nem jár. Ekkor visszamegy a 2-es kerethez, és onnan kezdi újra az átvitelt, a 2-es, 3-as, 4-es stb. sorszámú kereteket újra elküldve. A 0-s és 1-es sorszámú kereteket a vevő helyesen veszi és nyugtázza. A 2-es sorszámú keret azonban megrongálódott vagy elveszett. Az adó ezt nem tudva, folytatja a további keretek küldését, amíg a 2-es keret időzítése le nem jár. Ekkor visszamegy a 2-es kerethez, és onnan kezdi újra az átvitelt, a 2-es, 3-as, 4-es stb. sorszámú kereteket újra elküldve.
A csővezetékezett keretek esetén alkalmazható másik általános hibakezelési stratégia a szelektív ismétlés (selective repeat). Ennek a módszernek a használatakor a vevő a rosszul vett kereteket eldobja, de az ezután érkező jó kereteket tárolja egy pufferben. Amikor az adó időzítése lejár, csak a legrégebbi nyugtázatlan keretet küldi el újra. Ha ez a keret helyesen megérkezik, akkor a vevő a helyes sorrendben adja tovább a hálózati rétegnek az összes, addig pufferelt keretet is. A szelektív ismétlés módszere egyenértékű azzal, hogy a vevő ablakmérete nagyobb mint 1. Ez a megközelítés nagy ablakméretekre nagy mennyiségű memóriát igényel az adatkapcsolati rétegben.
A szelektív ismétlést gyakran alkalmazzák együtt azzal a megoldással, hogy a vevő negatív nyugtát (negative acknowledgement, NAK) küld, amikor hibát észlel, például hibás ellenőrző összeg vagy nem soron következő keret esetén. A negatív nyugták még azelőtt kikényszerítik az újraküldést, hogy a megfelelő időzítő lejárna, ezért javítják a rendszer hatásfokát.
A 3.18.(b) ábrán a 0-s és az 1-es sorszámú keret ismét helyesen megérkezik, de a 2-es sorszámú keret elveszett. Amikor a 3-as keret megérkezik a vevőhöz, az adatkapcsolati rétege észreveszi, hogy kimaradt egy keret, ezért elküld egy NAK-ot a 2-esről, de puffereli a 3-ast. Amikor a 4-es és 5-ös keret megérkezik, az adatkapcsolati réteg ezeket is puffereli ahelyett, hogy továbbadná őket a hálózati rétegnek. Előbb-utóbb a 2-es NAK visszaér az adóhoz, amely azonnal újraküldi a 2-es keretet. Amikor ez megérkezik, az adatkapcsolati réteg már rendelkezik a 2-es, a 3-as, a 4-es és az 5-ös kerettel, így azokat a megfelelő sorrendben tovább is adhatja a hálózati rétegnek. Ezenfelül nyugtázhatja az összes keretet az 5-ösig bezárólag, amint az ábrán is látható. Ha a NAK elveszik, az adó időzítése a 2-es keretre előbb-utóbb lejár és magától ismét elküldi azt (és csak azt), de ez akár sokkal később is lehet.
Ez a két megközelítés lehetőséget ad arra, hogy kompromisszumot kössünk a sávszélesség-kihasználás és az adatkapcsolati rétegbeli memória mérete között. Attól függően, hogy melyik erőforrás az értékesebb, az egyik vagy a másik megközelítés használható. A 3.19. ábrán egy olyan n visszalépéses protokoll látható, amelyben az adatkapcsolati réteg csak sorrendben fogadja el a kereteket; egy hibás keretet követően az összes keretet eldobja. Ebben a protokollban – első ízben – szakítottunk azzal a feltételezéssel, hogy a hálózati réteg végtelen sok csomagot tud az adatkapcsolati réteg rendelkezésére bocsátani. Amikor a hálózati rétegnek van egy csomagja, amit el akar küldeni, ez egy network_layer_ready eseményt okozhat. Annak érdekében azonban, hogy forgalomszabályozási megkötéseket tegyünk az adási ablakra vagy a nyugtázatlan keretek számára, az adatkapcsolati rétegnek meg kell tudnia akadályozni a hálózati réteget abban, hogy az több munkával zaklassa. Az enable_network_layer és a disable_network_layer könyvtári rutinok végzik ezt a feladatot.
A tetszőleges pillanatban maximálisan kint lévő keretek száma nem egyezik meg a sorszámok maximális méretével. Az n visszalépéses protokollra legfeljebb MAX_SEQ keret lehet kint, annak ellenére, hogy MAX_SEQ + 1 különböző sorszám van (ezek: 0, 1, 2, ..., MAX_SEQ). Látni fogjuk, hogy a szelektív ismétlés protokollra még szorosabb megkötés tartozik. Hogy megértsük, miért szükséges ez a korlátozás, vegyük a következő eseménysort MAX_SEQ = 7 mellett.
Az adóállomás elküldi a kereteket a 0.-tól a 7.-ig.
A 7. keretre végül is visszajön az adóállomáshoz egy ráültetett nyugta.
Az adóállomás újabb nyolc keretet küld, megint 0 és 7 közötti sorszámokkal.
Most még egy ráültetett nyugta érkezik a 7. keretre.
A kérdés: a második sorozathoz tartozó nyolc keret mind megérkezett sikeresen, vagy mind a nyolc elveszett (a hibás keretet követő keretek eldobását is keretvesztésnek számítva). A vevőnek mindkét esetben a 7. keretre kellene nyugtát küldenie. Az adóállomás semmilyen módon nem tudja a kérdést eldönteni. Emiatt a kint levő keretek száma legfeljebb MAX_SEQ lehet.
Bár az 5. protokoll nem puffereli az érkező kereteket egy hibás keret után, mégsem ússza meg teljesen a pufferelés problémáját. Mivel lehet, hogy az adóállomásnak újra kell küldenie az összes nyugtázatlan keretet egy későbbi időpontban, meg kell tartania az összes elküldött keretet addig, amíg biztosan nem tudja, hogy a vevő elfogadta azokat. Amikor nyugta jön az n. keretre, az stb. szintén automatikusan nyugtázódik. Az ilyen típusú nyugtázás halmozott nyugtázás (cumulative acknowledgement) néven ismert. Ez a tulajdonság különösen fontos akkor, amikor néhány előző nyugtahordozó keret elveszik vagy tönkremegy. Mindig, amikor egy nyugta beérkezik, az adatkapcsolati réteg ellenőrzi, hogy fel lehet-e szabadítani valamelyik puffert. Ha fel lehet szabadítani puffereket (azaz van hely az ablakban), a korábban blokkolt hálózati rétegnek engedélyezni lehet, hogy további network_layer_ready eseményeket okozzon.
Ennél a protokollnál feltesszük, hogy mindig van forgalom az ellenkező irányba is, vagyis van mire ráültetni a nyugtákat. A 4. protokoll esetében nincsen szükség erre a feltételezésre, mivel az minden egyes keret vételekor elküld egy keretet, még akkor is, ha valamivel korábban azt a keretet már elküldte. A következő protokollban egy elegáns módszert mutatunk az egyirányú forgalom problémájának megoldására.
Mivel az 5. protokollban több kint levő keret van, logikailag több időzítőre van szükség: minden kint levő kerethez egyre. Minden keret időzítője az összes többiétől függetlenül jár le. Az összes időzítő könnyedén szimulálható szoftverből egy olyan hardveridőzítővel, amelyik periodikusan megszakításokat okoz. A járó időzítők egy láncolt listát alkotnak, melyben minden csomópont azt mutatja, hogy mennyi óraütés van hátra, amíg az időzítő lejár, és hogy melyik kerethez tartozik az adott időzítő. A csomópont ezenkívül tartalmaz még egy mutatót is a következő csomópontra.
3.20. ábra - Több időzítő szimulációja szoftverből. (a) A sorba kötött időzítők. (b) Az első időzítő lejárta utáni helyzet
Illusztrációként arra, hogy hogyan lehet megvalósítani az időzítőket, vegyük a 3.20.(a) ábra példáját. Tételezzük fel, hogy az óra minden 1 ms-ban üt egyet. Kezdetben a valós idő 10:00:00.000, és három függőben levő időzítés van: 10:00:00.005-kor, 10:00:00.013-kor és 10:00:00.019-kor. Mindig, amikor a hardveróra üt, a valós időt aktualizáljuk, és az ütésszámlálót a lista fejében csökkentjük eggyel. Amikor az ütésszámláló nulla lesz, az időzítő időtúllépést okoz, és a csomópontot eltávolítjuk a listából, ahogyan a 3.20.(b) ábrán látható. Bár ez a szervezés azt kívánja, hogy a listát végignézzük, amikor a start_timer-t vagy a stop_timer-t meghívjuk, óraütésenként nem kell sok mindent csinálni. Az 5. protokollban mindkét rutinnak egy paramétert adtunk át, mely azt jelzi, hogy melyik kerethez tartozik az időzítő.
Az n visszalépéses protokoll jól működik akkor, ha a hibák ritkán fordulnak elő. Ha azonban a vonal gyenge minőségű, nagy sávszélességet pazarol el a keretek újraküldésére. Egy másik stratégia – a szelektív ismétlés – szerint megengedjük a vevőnek, hogy elfogadja és pufferelje a kereteket, melyek egy elveszett vagy megsérült keretet követnek.
Ebben a protokollban az adó karbantart egy ablakot a kint lévő keretek sorszámairól, a vevő pedig egy ablakot az elfogadható sorszámokból. Az adó ablakának mérete 0-ról indul és valamilyen előre definiált maximumig növekszik. A vevő ablaka ezzel ellentétben rögzített méretű, és egy előre meghatározott értékkel egyenlő. A vevőnek minden, az ablakában levő sorszámhoz fenntartott puffere van. Mindegyik pufferhez tartozik egy bit (arrived), mely azt mutatja, hogy a puffer tele van-e vagy üres. Amikor egy keret megérkezik, a between függvénnyel ellenőrzi a sorszámát, hogy beleesik-e az ablakba. Ha beleesik, és a keretet még nem vette korábban, akkor elfogadja és tárolja. Ezt mindig megteszi, tekintet nélkül arra, hogy a keret azt a csomagot tartalmazza-e, amit a hálózati réteg vár, vagy sem. Természetesen, a keretet meg kell őrizni az adatkapcsolati rétegben, és nem szabad átadni a hálózati rétegnek addig, amíg az összes alacsonyabb sorszámú keretet nem továbbította a hálózati rétegnek a helyes sorrendben. Az ezt az algoritmust használó protokoll a 3.21. ábrán látható.
A keretek nem sorrendben történő vétele további megkötéseket ad a sorszámokhoz, szemben azokkal a protokollokkal, melyek a kereteket csak sorrendben fogadják el. A problémát legkönnyebben egy példával illusztrálhatjuk. Tételezzük fel, hogy 3 bites sorszámunk van, így az adóállomás legfeljebb hét keretet továbbíthat, mielőtt várakoznia kellene nyugtára. Kezdetben az adó és a vevő ablakai olyanok, mint az a 3.22.(a) ábrán látható. Az adóállomás most továbbítja a kereteket a 0-tól a 6-ig. A vevő ablaka megengedi bármely keret elfogadását, melynek a sorszáma 0 és 6 közé esik, a határokat is beleértve. Mind a hét keret rendben megérkezik, így a vevő nyugtázza azokat, és lépteti az ablakát, hogy lehetővé tegye a 7., 0., 1., 2., 3., 4. és az 5. keret vételét. A beállt állapot a 3.22.(b) ábrán látható. Mind a hét puffert üresnek jelöljük meg.
3.22. ábra - (a) Kezdeti állapot héthosszúságú ablakkal. (b) Hét keret elküldése és vétele után, de még a nyugtázás előtt. (c) Kezdeti állapot négyhosszúságú ablakkal. (d) Négy keret elküldése és vétele után, de még a nyugtázás előtt
Most érkeztünk el ahhoz a ponthoz, amikor beüt a mennykő egy villám formájában, mely a telefonoszlopot veszi célba, és kipucolja a vonalról az összes nyugtát. A katasztrófa ellenére a protokollnak továbbra is helyesen kell működnie. Az adóállomásnak előbb-utóbb lejár az időzítője, és újraadja a 0. keretet. Amikor ez a keret megérkezik a vevőhöz, a vevő ellenőrzi, hogy beleesik-e a vételi ablakba. Szerencsétlenségünkre a 3.22.(b) ábrán a 0. keret az új ablakon belül van, így új keretként elfogadja. A vevő egy ráültetett nyugtát küld a 6. keretről, hiszen a 0. és a 6. közötti kereteket vette.
Az adóállomás örül, amikor megtudja, hogy mindegyik továbbított kerete rendben megérkezett, így lépteti az ablakát, és azonnal elküldi a 7., 0., 1., 2., 3., 4. és 5. keretet. A 7. keretet a vevő elfogadja, és a benne levő csomagot rögtön átadja a hálózati rétegnek. Közvetlenül ezután a vevő adatkapcsolati rétege megnézi, hogy van-e már érvényes 0. kerete, rájön, hogy van, és továbbadja a benne levő öreg pufferelt csomagot a hálózati rétegnek, mintha az új csomag lenne. Ennek következtében a hálózati réteg helytelen csomagot kap, tehát a protokoll hibázik.
A probléma lényege az, hogy miután a vevő léptette az ablakát, az új érvényes sorszámok tartománya átlapolódik a régiekével. Ennek következtében az ezt követő keretköteg lehet akár duplikátum (ha az összes nyugta elveszett), akár új keretek kötege (ha az összes nyugta megérkezett). A szegény vevő sehogyan sem tud különbséget tenni a két eset között.
A dilemmából kivezető megoldás azon alapul, hogy biztosnak kell lennünk abban, hogy miután a vevő léptette az ablakát, nincs átfedés az eredeti ablakkal. Ahhoz, hogy ne legyen átfedés, a maximális ablakméret legfeljebb a sorszámok tartományának fele lehet. Ezt a helyzetet látjuk a 3.22.(c) és a 3.22.(d) ábrákon. 3 bit esetén a sorszámok 0-tól 7-ig terjednek. Így mindössze 4 nyugtázatlan keret lehet kint tetszőleges időpillanatban. Ha a vevő éppen elfogadta a 0.-tól 3.-ig tartó kereteket, és léptette az ablakát, hogy lehetővé tegye a 4.-től 7.-ig tartó keretek elfogadását, egyértelműen megmondható, hogy a következő keretek újraküldések (0.-tól 3.-ig) vagy újak (4.-től 7.-ig). Az ablakméret a 6. protokollnál általában (MAX_SEQ + 1)/2.
Érdekes kérdés az, hogy a vevőben hány puffernek kell lennie. A vevő semmilyen körülmények között nem fogad el olyan kereteket, amelyek sorszáma kisebb, mint az ablak alsó széle, vagy nagyobb, mint a felső. Következésképpen a szükséges pufferek száma az ablak méretével egyenlő, nem a sorszámok tartományával. A fenti, 3 bites sorszámokat tartalmazó példában négy puffer kell 0-tól 3-ig számozva. Amikor az i. keret megérkezik, az (i mod 4). pufferbe kell tenni. Vegyük észre, hogy bár az i. és az (i + 4) mod 4. ugyanazért a pufferért „verseng”, soha nincsenek az ablakban egyszerre, mert ehhez legalább 5 hosszúságú ablak kellene.
Ugyanezért az időzítők száma is a pufferek számával egyenlő, nem pedig a sorszámmező méretével. Valójában minden pufferhez tartozik egy időzítő. Amikor az időzítő lejár, a puffer tartalmát az adó újraküldi.
A 6. protokoll enyhíti azt az implicit feltételezést, miszerint a csatorna alaposan le van terhelve. Ezt a feltételezést még az 5. protokollban tettük, amikor a visszairányban ráültetett nyugtákat használtunk. Ha a visszairányú forgalom kicsi, a nyugta hosszú ideig várakozhat, ami problémákat okozhat. Szélsőséges esetben, ha nagy a forgalom az egyik irányban és nincs forgalom a másikban, a protokoll blokkolódik, amikor az adó ablaka eléri a maximumát.
A probléma megoldása érdekében egy segédidőzítőt indítunk el a start_ack_timer-rel, miután egy sorrendben következő adatkeret megérkezik. Ha nem jelentkezik visszairányú forgalom, mielőtt az időzítő lejár, egy külön nyugtakeretet küldünk. A segédidőzítő által okozott megszakítás az ack_timeout esemény. Ezzel a megoldással most már egyirányú forgalom is lehetséges, mert a visszairányú adatkeretek (melyekre a nyugták ráültethetők) hiánya már nem akadály. Csak egyetlen segédidőzítő van, és ha a start_ack_timer-t meghívjuk, miközben az időzítő jár, a hívásnak semmilyen hatása nem lesz. Az időzítő nem áll vissza kezdeti állapotba, és nem állítódik be újra, hiszen a célja éppen az, hogy valamilyen rendszeres, a protokoll működéséhez szükséges nyugtázási sebességet biztosítson.
Lényeges, hogy a segédidőzítő időzítési intervalluma jelentősen rövidebb legyen a keretek időzítéséhez használt időzítőénél. Ez a feltétel ahhoz szükséges, hogy biztosak lehessünk benne, hogy egy rendben vett keret nyugtája megérkezik, mielőtt az adó időzítője lejárna és újraadná a keretet.
A 6. protokoll hatékonyabb stratégiát alkalmaz a hibák kezelésére, mint az 5. protokoll. Amikor a vevőnek oka van gyanítani, hogy hiba történt, egy negatív nyugtakeretet (NAK) küld vissza az adóállomásnak. Egy ilyen keretkérés a NAK-ban megjelölt keret újraadására. Két eset van, amikor a vevő gyanakodhat: egy sérült vagy egy a várttól különböző keret érkezett (potenciális keretvesztés). Ahhoz, hogy elkerüljük, hogy ugyanarra az elveszett keretre több újraküldési igény jelentkezzen, a vevőnek nyomon kell követnie, hogy küldött-e már NAK-ot egy adott keretre. A no_nak változó értéke a 6. protokollban igaz, ha még nem küldtünk NAK-ot a frame_expected-re. Ha a NAK tönkremegy vagy elveszik, ez semmi kárt nem okoz, hiszen az adóállomásnak végül is lejár az időzítője, és mindenképpen újraküldi a keretet. Ha rossz keret érkezik, miután egy NAK-ot elküldtünk és az elveszett, a no_nak igaz lesz, és elindítjuk a segédidőzítőt. Amikor lejár, egy nyugtát küldünk, hogy újraszinkronizáljuk az adóállomást a vevő aktuális állapotához.
Néhány helyzetben a keret célba jutásához, ottani feldolgozásához és a nyugta visszaéréséhez szükséges idő (közel) konstans. Ezekben a helyzetekben az adóállomás az időzítési intervallumát beállíthatja úgy, hogy éppen csak egy kicsit legyen hosszabb, mint az a várható idő, ami egy keret elküldése és nyugtájának vétele között telik el. A negatív nyugtázás ebben az esetben nem túl hasznos.
Néhány esetben azonban ez az idő tág határok közt változik. Például, ha a visszairányú forgalom esetleges, akkor a nyugtázáshoz szükséges idő rövid, ha van visszairányú forgalom, és ez az idő hosszú, ha nincs visszairányú forgalom. Az adó ekkor azzal a problémával szembesül, hogy vagy rövidre állítja ezt az intervallumot (kockáztatva a felesleges újraküldéseket), vagy hosszúra állítja (és sokáig várakozik egy hiba után). Mindkét választás sávszélesség-pazarló. Általában, amikor a nyugtázási időtartam szórása nagy magához az időtartamhoz képest, az időzítést „tág”-ra lehet állítani, és a NAK-ok észrevehetően felgyorsíthatják az elveszett vagy megsérült keretek újraküldését.
Szorosan kapcsolódva az időtúllépések és NAK-ok problémájához, felmerül azon kérdés eldöntése, hogy melyik keret okozta az időtúllépést. Az 5. protokollban ez mindig az ack_expected, mert ez mindig a legidősebb. A 6. protokollban nincs triviális módja annak, hogy meghatározzuk, hogy melyik okozta az időtúllépést. Tegyük fel, hogy a 0.-tól a 4.-ig tartó kereteket küldtük el, ami azt jelenti, hogy a kint levő keretek listája 0 1 2 3 4, a legidősebbtől a legfiatalabbig. Most képzeljük el, hogy a 0. időzítője lejár, az 5-et (egy új keretet) továbbítjuk, az 1. időzítője lejár, a 2. időzítője lejár, és a 6.-at (egy másik új keret) továbbítjuk. Ezen a ponton a kint levő keretek listája 3 4 0 5 1 2 6 a legidősebbtől a legfiatalabbig. Ha egy ideig az összes bejövő forgalom (például ráültetett nyugtát hordozó keretek) elvész, a hét kint levő keretnek ebben a sorrendben jár le az időzítője.
Hogy ne bonyolítsuk tovább a már eddig is elég bonyolult példát, nem mutatjuk be az időzítők adminisztrációját. Ehelyett csak azt feltételezzük, hogy az oldest_frame változót időtúllépéskor beállítjuk, hogy jelezze, hogy melyik keret időzítése járt le.