Az adatkapcsolati réteg
Az adatkapcsolati réteg három feladatot hajt végre:
A hálózati rétegektől kapott információkat keretekbe rendezi.
Hibavédelem megvalósítása.
A keretek továbbítása és nyugtázása.
A feladatkörből látszik, hogy az egyik legfontosabb feladat a keretek összeállítása, de mik is azok a keretek? A keret az adat valamilyen határoló jelek közé foglalt része, amely rendszerint a tényleges adaton kívül egyéb információkat is tartalmaz. Mivel nagyon fontos, hogy a biztonságos és hibamentes átvitel biztosítása, ezért nagyon fontos, hogy olyan ellenőrzést is kell a keretbe foglalni, amely alapján felfedezhetők a hibák. Ilyen esetben a rossz keretet újra le lehet kérni a küldőtől. Hibavédelem valamilyen ellenőrző kód, amely bonyolult matematikai eljárással kerül meghatározásra. A keret vételekor a vevő ismét kiszámolja ezt az összeget és ha a tárolttal nem egyezik, akkor a keret megsérült, a vevő eldobja és kéri újra a küldőtől.
Átvitel során bináris információt, vagyis biteket kell továbbítani az adó és a vevő között. A hatékonyabb működés érdekében egyszerre a lehető legtöbb bitet kell továbbítani. A számítógépek kialakulásakor nagyon sokszor kellett szöveges információt, vagyis karaktersorozatokat küldeni. A karakterek mindig azonos módon, az ASCII kódnak megfelelően tárolódtak. Az ilyen információtovábbítást karakterorientált átvitelnek nevezzük.
A fejlődéssel együtt járt, hogy már egyre többször kellett nem karakteralapú adatokat továbbítani. Ilyen esetekben a biteket sorosan küldjük egymás után át a vonalon, de célszerű több (például védelmi) szempontból ezeket csoportokba foglalni. Ezt a módszert nevezzük bitorientált átvitelnek.
Karakterszámláló módszer alapján a keret fejlécében megadjuk a átvitelre kerülő karakterek számát. A vevő egy számlálóba beállítja ezt az értéket és minden vett karakter után egyel csökkenti annak értékét. Mikor a számláló elérte a nulla értéket, jelzi, hogy ott a keret vége.
Vezérlőkarakterek beszúrásával jelezzük a keret kezdetét és végét. Ha visszaemlékszünk, az ASCII kódkészletben meglehetősen sok vezérlőkarakter található. Ezek nem jeleníthetők meg csupán jelzési és vezérlési feladatra használhatók. Ha ilyen karaktereket helyeznénk el a keret elején és végén, akkor az jelezhetné a keret határait. Milyen vezérlőkaraktereket választhatunk?
A keret elejét rendszerint a DLE STX, a végét a DLE ETX karakterpáros jelzi. A DLE rövidítés a Data Link Exchange (adatkapcsolat átkapcsolás), az STX a Start of Text (szöveg kezdete) az ETX pedig az End of Text (szöveg vége) kifejezésekből kialakított betűszavak.
EZT AZ UZENETET SZERETNENK ELKULDENI
keretezés után
DLE STX EZT AZ UZENETET SZERETNENK ELKULDENI DLE ETX
A vevő a vezérlőkaraktereket levágja és így rendelkezésre áll az eredeti üzenet. Ez a megoldás elsősorban karakterorientált átvitelnél használatos, de lehetőség van tetszőleges bitcsoport továbbítására is. Ilyen esetekben felmerülhet, hogy a bitcsoport valamely vezérlőkarakter bináris megfelelője. Ha ezt nem vennénk figyelembe, akkor átvitel során a vevő máshol határozná meg a kerethatárokat, ami hibához vezethet. Amikor az adó összeállít egy bináris keretet és DLE karakterkódot érzékel, akkor beszúr oda még egy DLE karaktert. A vevő ha egymás után két DLE karaktert vesz, akkor ez egyiket egyszerűen eldobja.
Bitorientált keretképzés bitbeszúrásos módszernél a bitcsoport elejére és végére speciális bitcsoportot szúrunk be. A gyakorlatban általában a 01111110 botsorozatot használják. Mint látjuk a bitsorozat közepén hat 1 szerepel, amit egy 0 zár le. Biztosítani kell, hogy ilyen sorozat ne szerepelhessen a keretben máshol. Ennek a módszere, hogy ha az adó öt 1-est talál, akkor ezek után automatikusan beszúr egy 0-át. Így hat 1-es sohasem lehet egymás után. A vevő feladata, hogy öt 1-es után következő nullát automatikusan kitörli.
A hálózati réteg által küldött üzenet:
100111111111110111100011111111000000011111101010100001101
keretezés után (a keretjelző a 01111110 bitsorozat)
0111111010011111111111011110001111111100000001111110101010000110101111110
a hibák kiküszöbölése (kék szín jelzi a beszúrt 0-ákat)
01111110100111110111111001111000111110111000000011111010101010000110101111110
A keretezés még megvalósítható olyan állapotokkal is, amelyek az adatcsomagban biztosan nem fordulhat elő.
Minden hibakezelési eljárás az eredeti bitsorozatot redundanciával (ismétlődéssel) küldi. Ha ezekkel a kódokkal a hiba felismerhető, akkor hibajelző (Error Detecting Codes, EDC) kódokról, ha a vevő azt is képes megállapítani, hogy minek kellett volna érkeznie, akkor hibajavító (Error Correcting Codes, ECC) kódokról beszélünk. A redundáns kódok az eredeti adatmennyiséget értelemszerűen megnövelik, ami a hasznos sávszélességet csökkentik.
A hibák időtartamának figyelembevételével megkülönböztethetünk egyedi- és csoportos hibákat. Ha a hiba csak 1 bitre hat ki, akkor egyedi-, ha több bit átvitele alatt fennáll, akkor csoportos bithibákról beszélünk.
Hamming-távolság
A hibák egy speciális fajta, amikor úgy változik meg egy kód, hogy egy másik, de értelmes kód lesz belőle. Ez abban az esetben valósulhat meg, ha a két kódszó Hamming-távolsága 1. Hamming távolságnak nevezzük azoknak a biteknek a számát, amelyek megváltozásakor az egyik kód a másik kódra alakítható. Ha például két kód Hamming-távolsága 1, akkor ezek 1 bitben térnek el egymástól. Az ASCII kód Hamming-távolsága 1. A Hamming-távolság meghatározásához a két szó között kizáró-vagy (XOR) logikai műveletet kell végrehajtani, majd az eredményben meg kell számolni az egyesek számát. Ismétlésképpen a kizáró vagy kapcsolat kimenete csak akkor lesz logikai 1, ha a bemenetei eltérő állapotúak.
A kód Hamming-távolsága alapján lehet egy kód hibajelző, vagy hibajavító tulajdonságú. Egy n-bites hiba jelzéséhez n+1 bites kódot kell használni, mivel ilyen kódolás során egy n-bites hiba nem tudja az egyik kódszót a másik érvényes kódba átvinni. A hiba javításához a használt kódok távolságának 2n+1 (n a kódbitek száma) Hamming-távolságú kód kell.
A hibajelzés fajtái
A hibajelzés feladata egy- vagy több bit hibájának jelzése. Mivel nincs szükség a hiba javítására, a megoldások viszonylag egyszerűnek tekinthetők. A hibajelzés gyakorlatban alkalmazott típusai:
Paritásbites hibajelzés a hibajelzés legegyszerűbb az egyik leggyakrabban használt fajtája. Két alapvető típusát különböztethetjük meg, a páros- és a páratlan paritást. Páros-paritás használatakor az adatot olyan bittel egészítjük ki, hogy az adatcsomagban, amelyben már a paritásbit is benne van, az egyesek száma páros legyen. A páratlan-paritás megoldás is hasonló, csak itt az adatcsomag 1-eseinek száma páratlannak kell lennie. Ha átvitel során bármelyik bit megváltozik, akkor azt képes a vevő érzékelni. Természetesen a módszer csak akkor működik, ha az átvitel előtt a résztvevők megállapodnak a paritás típusában. A működésből látható, hogy a bithiba helyét nem tudjuk meghatározni. Amennyiben páros számú bit változik meg, akkor azt nem képes ez a módszer felismerni. Ilyen védelmet használnak az RS-232C soros adatátvitelnél is.
Tömbparitás vizsgálat: A paritásbites hibajelzés továbbfejlesztése. Az átvitelre kerülő információblokkot egy mátrixnak tekintjük. A mátrix oszlopainak száma a paritásbittel kiegészített kódszó hossza, a sorok száma pedig a blokkban lévő kódszavak száma. Minden sor tartalmaz egy paritásbitet, ezen túlmenően minden képzeletbeli oszlophoz is kiszámítunk egy paritásbitet. Ezt a paritásszót az utolsó kódszó után továbbítjuk. Ez a megoldás nem csak egyedi bithibák felismerésére használható, hanem képes jelezni az egyedi csoporthibákat is.
CRC (Cyclic Redundancy Check, ciklikus redundancia ellenőrzés) az előzőekhez képes jelentősen bonyolultabb megoldás, amellyel csoportos bithibák felismerése valósítható meg. A kódot alkotó biteket egy polinom együtthatóiként kezeljük. Egy n-bites kód esetén az együtthatók xn-1 és x0 közöttiek lesznek. Így a polinom felírható
xn-1+ xn-2+xn-3 +xn-4 +xn-5 + xn-6+ xn-7+ .......... +x4 +x3 +x2 + x1+ x0
Például: legyen a kód 10011001. Ebben az esetben a polinom a következő lesz:
x7 +x4 + x3+ x0
Csak azokat a tagokat kell felírnunk, amelyik helyiértéken az eredeti kódban 1 állt.
A polinomok alkalmazásakor a kommunikációban résztvevőknek meg kell egyezniük egy közös polinomban, amelyet generátor polinomnak (Generator Polynomial) nevezünk és általában a G(x) módon jelöljük. A generátor polinommal kapcsolatban alapvető követelmény, hogy a legalsó és a legfelső bitjének 1-esnek, valamint a továbbítandó keretnek hosszabbnak kell lennie, mint a generátor polinom.
A CRC védelem során olyan ellenőrző összeget fűzünk a továbbítandó kerethez, amely úgy egészíti ki azt, hogy az így kapott keret által meghatározott polinom osztható legyen a generátor polinommal. Miután a vevő megkapta a keretet, megpróbálja elosztani a generátor polinommal. Ha az osztás során van maradék, akkor hiba történt az átvitel során. Az eljárás meglehetősen bonyolult matematikailag, de a számítógépek ezt nagyon gyorsan képesek elvégezni, sőt. 1961-ben Peterson és Brown bebizonyította, hogy az ellenőrző kód léptető-regiszterekkel előállítható. Ezt a hardvert ma már a legtöbb hibajavítással kapcsolatba kerülő áramkör használja. A m-bites ellenőrző bittel ellátott polinomkód legfeljebb m-bites csoportos bithibát hibát képes jelezni. A gyakorlatban három polinom vált szabvánnyá:
CRC-12 = x12+x11+x2+ x1+ 1, amit olyankor használhatunk, amikor a karakterhossz 6 bit.
CRC-16 = x16+x15+x2+ 1, 8 bites karakterekhez használható.
CRC-CCITT = x16+x12+x5+ 1, szintén 8 bites karakterekhez alkalmazhatjuk.
A 16 bites CRC kódok képesek felismerni minden egybites-, kétbites-, minden páratlan hibás bitet tartalmazó hibát, minden 16 vagy kevesebb bitnyi csoportos bithibát, a 17 bites csoportos bithibák 99, 997%-át, a 18 vagy magasabb bitszámú hibák 99,998%-át (forrás: Andrew S. Tannenbaum Számítógéphálózatok, Panem kiadó).
Az adatkapcsolati réteg, mint azt már tudjuk, a keretek elkészítését valósítja meg, valamint előállítja a védelemhez szükséges ellenőrző összeget (CRC). A kereteket átadja a fizikai rétegnek, amely azt továbbítja a vevő irányába. Felmerülhet a kérdés, hogy honnan tudja a fizikai réteg, hogy ki a címzett? Természetesen a létrehozott keretnek rendelkeznie kell egy címmező résszel, amelyből már kiolvasható az a cím, ahová el kell küldeni a csomagot. A másik kérdés, ami felmerülhet, hogy hogyan értesül az adó, ha a vevő hibásan kapta meg a csomagot, vagy még rosszabb esetben (bár a végeredmény szempontjából majdnem mindegy) meg sem kapta a csomagot? A hibalehetőségek száma csak növekszik, ha az adó és a vevő egyszerre adhat. Ezeknek a problémáknak a kezelésére több módszert fejlesztettek ki.
Az előző megoldás továbbfejlesztése, annak hibáinak bizonyos mértékű lecsökkentése. Az előző megoldás legnagyobb problémája az, hogy szinte soha sem képes a vevő olyan sebességgel feldolgozni a kereteket, ahogy az adó küldi, vagy a hibás keretek adását meg kell ismételni. A hibalehetőség és az elárasztás lehetősége fokozottan jelentkezik akkor, ha a vevőnek több vonalra is figyelnie kell.
A megoldás meglehetősen kézenfekvő, a vevőnek közölnie kell az adóval, hogy mikor adhatja a következő keretet, amelyet már képes fogadni. Ezt legegyszerűbben nyugtázással lehet ezt megvalósítani. A vevőnek egy nyugtázást kell küldenie az adónak akkor, ha végzett az előző keret vételével, feldolgozásával. A nyugta megérkezéséigaz adó egyszerűen várakozik. Abban az esetben, ha az adó nem kap egy időtartam alatt a vevőtől nyugtázást az elküldött keretre, akkor ismét elküldi az utolsó keretet.
Súlyosabb probléma az, ha a nyugtakeret veszik el, vagy sérül meg. Ebben az esetben szintén elküldi az adó az utolsó keretet, amit a vevő úgy értelmezhet, hogy egy új keretet kapott. Ez nagyon súlyos hiba, kivédéséhez a vevőnek kell felismernie az egymás után kapott azonos üzeneteket.
Az előzőekben említett hibákat képes kiküszöbölni a szimplex hálózatoknál. Az adó egy sorszámot helyez el az éppen elküldött keret fejrészébe. A vevő mikor veszi a keretet ezt a bitet vizsgálja. Amennyiben értéke 0, akkor a kapott keretet az adó először küldte. Ha az adó nem kapja meg erre a nyugtázást, akkor ismét elküldi a keretet, de a nyugtát jelző bitet 1-re állítja be. A vevő veszi ismét a keretet, amit el is dob, mivel a fejrészben 1 értékű nyugtabitet talált. Ismét nyugtát küld az adónak, amely vételekor folytatódhat az információ továbbítása.
Az előbbiekben ismertetett protokollok csak szimplex csatornákon voltak használhatók. A duplex vonalak esetében a keretek és a nyugták egy időben képesek a vonalon haladni, emiatt az üres várakozási állapotok lecsökkennek. A legkézenfekvőbb megoldás, ha két vonalat építünk ki az adó és a vevő között és mindegyiket szimplex, de ellentétes irányú átvitelre használjuk. Amilyen egyszerű ez a struktúra, az esetek többségében annyira gazdaságtalan is, hiszen a nyugtázásra használt vonal csak nagyon ritkán használt, tehát a kihasználtsága nagyon kicsi. Sokkal célszerűbb ugyanazt a vonalat használni a két ellentétes irányú átvitelhez használni. Tulajdonképpen erre láthattunk példát az előzőekben is.
Amikor a vonalat kétirányú átvitelre használjuk, az adatkeretek összekeverednek a vezérlőkarakterekkel. Ennek kiküszöbölésére a keretben elhelyeznek egy bitet, amelyet megvizsgálva eldönthető, hogy milyen kerettel van dolgunk. A nyugtázás okozta sávszélesség veszteség csökkenthető, ha a nyugtakeretet egy, az ellenkező irányba továbbítandó adatkeretbe építünk be. Így tulajdonképpen a nyugtát ráültetjük az adatkeretekre, ezért nevezik ezt az eljárást ráültetéses (piggy-back) technikának.
A sávszélesség hatékonyabb kihasználása mellett a piggy-back technika felvet néhány olyan problémát, amely a különálló nyugták esetében nem jelentkezik. Az egyik legsúlyosabb, hogy meddig várakozzon az adatkapcsolati réteg, amíg kap a hálózati rétegtől egy olyan keretet, amelyre ráültetheti a nyugtát? Amennyiben az adó nem érzékel egy bizonyos időtartam alatt nyugtát, a keretet újraküldi. A várakozást egy időzítő határozza meg, ennek lejártakor az adatkapcsolati réteg egy önálló nyugtakeretet küld el az adónak.
A duplex átvitelhez a csúszóablakos protokollokat (sliding window) nagyon gyakran használják a gyakorlatban. A számítógép-hálózatokban a vonal kihasználtságát növeli, ha nem csak egy keret van egyszerre jelen. A küldő elküld bizonyos számú keretet, majd várakozási állapotba kerül. Ezeket a kereteket a vevő nyugtázza, aminek eredményeként a küldő ismét elküldhet annyi keretet, amennyi nyugtát kapott. A működés felépítése követhető nyomon a következő ábrán.
Minden keretnek sorszáma van, amely az egymást követő kereteknél egyesével növekszik (a példában 8 keret 0-7 sorszámmal). Az adó fenntart egy listát, amelyben azok a keretek szerepelnek, amelyeket elküldött, de még nem érkezett válasz. A vevőnek szintén van egy listája, amelyben azok a keretek szerepelnek, amelyeket az adótól vár. Amikor vesz egy keretet, akkor a sorszám alapján nyugtázza azt az adónak. Ha olyan keret érkezik, amely sorszáma nincs a saját listáján, akkor azt eldobja. A keretek nyugtázása csak sorfolytonosan történhet. Nem szükséges minden keretet nyugtázni. Ha a vevő vesz egy keretet és a listában előtte szereplő keretek már beérkeztek, akkor elegendő csak a legmagasabb sorszámút visszaigazolni és azablak annyival feljebb tolódik. Az adó a listában figyeli a keretek időtartamát. Ha egy értéket elér, akkor azt újraadja.
Olyan speciális csúszóablakos protokoll, amelyben az ablak mérete 1, tehát a egyszerre egy keret van a vonalon. Az adatátvitel kétirányú, a küldött keret tartalmazza az előzőleg elküldött keret nyugtáját (ráültetéses protokoll).
A következő részben néhány, a gyakorlatban használt, az előzőekre épülő adatkapcsolati protokollt mutatunk be.
Az adatkapcsolati réteg három feladatot hajt végre:
A hálózati rétegektől kapott információkat keretekbe rendezi.
Hibavédelem megvalósítása.
A keretek továbbítása és nyugtázása.
A feladatkörből látszik, hogy az egyik legfontosabb feladat a keretek összeállítása, de mik is azok a keretek? A keret az adat valamilyen határoló jelek közé foglalt része, amely rendszerint a tényleges adaton kívül egyéb információkat is tartalmaz. Mivel nagyon fontos, hogy a biztonságos és hibamentes átvitel biztosítása, ezért nagyon fontos, hogy olyan ellenőrzést is kell a keretbe foglalni, amely alapján felfedezhetők a hibák. Ilyen esetben a rossz keretet újra le lehet kérni a küldőtől. Hibavédelem valamilyen ellenőrző kód, amely bonyolult matematikai eljárással kerül meghatározásra. A keret vételekor a vevő ismét kiszámolja ezt az összeget és ha a tárolttal nem egyezik, akkor a keret megsérült, a vevő eldobja és kéri újra a küldőtől.
Átvitel során bináris információt, vagyis biteket kell továbbítani az adó és a vevő között. A hatékonyabb működés érdekében egyszerre a lehető legtöbb bitet kell továbbítani. A számítógépek kialakulásakor nagyon sokszor kellett szöveges információt, vagyis karaktersorozatokat küldeni. A karakterek mindig azonos módon, az ASCII kódnak megfelelően tárolódtak. Az ilyen információtovábbítást karakterorientált átvitelnek nevezzük.
A fejlődéssel együtt járt, hogy már egyre többször kellett nem karakteralapú adatokat továbbítani. Ilyen esetekben a biteket sorosan küldjük egymás után át a vonalon, de célszerű több (például védelmi) szempontból ezeket csoportokba foglalni. Ezt a módszert nevezzük bitorientált átvitelnek.
Keretek képzése
Természetesen a keretképzés attól függ, hogy az átvitel bit-, vagy karakterorientált. Több módszer alakult ki a feladat elvégzésére, a továbbiakban ezeket nézzük meg.Karakterszámláló módszer alapján a keret fejlécében megadjuk a átvitelre kerülő karakterek számát. A vevő egy számlálóba beállítja ezt az értéket és minden vett karakter után egyel csökkenti annak értékét. Mikor a számláló elérte a nulla értéket, jelzi, hogy ott a keret vége.
Vezérlőkarakterek beszúrásával jelezzük a keret kezdetét és végét. Ha visszaemlékszünk, az ASCII kódkészletben meglehetősen sok vezérlőkarakter található. Ezek nem jeleníthetők meg csupán jelzési és vezérlési feladatra használhatók. Ha ilyen karaktereket helyeznénk el a keret elején és végén, akkor az jelezhetné a keret határait. Milyen vezérlőkaraktereket választhatunk?
A keret elejét rendszerint a DLE STX, a végét a DLE ETX karakterpáros jelzi. A DLE rövidítés a Data Link Exchange (adatkapcsolat átkapcsolás), az STX a Start of Text (szöveg kezdete) az ETX pedig az End of Text (szöveg vége) kifejezésekből kialakított betűszavak.
EZT AZ UZENETET SZERETNENK ELKULDENI
keretezés után
DLE STX EZT AZ UZENETET SZERETNENK ELKULDENI DLE ETX
A vevő a vezérlőkaraktereket levágja és így rendelkezésre áll az eredeti üzenet. Ez a megoldás elsősorban karakterorientált átvitelnél használatos, de lehetőség van tetszőleges bitcsoport továbbítására is. Ilyen esetekben felmerülhet, hogy a bitcsoport valamely vezérlőkarakter bináris megfelelője. Ha ezt nem vennénk figyelembe, akkor átvitel során a vevő máshol határozná meg a kerethatárokat, ami hibához vezethet. Amikor az adó összeállít egy bináris keretet és DLE karakterkódot érzékel, akkor beszúr oda még egy DLE karaktert. A vevő ha egymás után két DLE karaktert vesz, akkor ez egyiket egyszerűen eldobja.
Bitorientált keretképzés bitbeszúrásos módszernél a bitcsoport elejére és végére speciális bitcsoportot szúrunk be. A gyakorlatban általában a 01111110 botsorozatot használják. Mint látjuk a bitsorozat közepén hat 1 szerepel, amit egy 0 zár le. Biztosítani kell, hogy ilyen sorozat ne szerepelhessen a keretben máshol. Ennek a módszere, hogy ha az adó öt 1-est talál, akkor ezek után automatikusan beszúr egy 0-át. Így hat 1-es sohasem lehet egymás után. A vevő feladata, hogy öt 1-es után következő nullát automatikusan kitörli.
A hálózati réteg által küldött üzenet:
100111111111110111100011111111000000011111101010100001101
keretezés után (a keretjelző a 01111110 bitsorozat)
0111111010011111111111011110001111111100000001111110101010000110101111110
a hibák kiküszöbölése (kék szín jelzi a beszúrt 0-ákat)
01111110100111110111111001111000111110111000000011111010101010000110101111110
A keretezés még megvalósítható olyan állapotokkal is, amelyek az adatcsomagban biztosan nem fordulhat elő.
Hibakezelés
Az adatkapcsolati réteg a keretezésen kívül a hibakezelésért is felelős. Hiba esetén a küldőnek ismételten el kell küldenie azt a csomagot, amelyben a vevő hibát talált. A hiba észlelésére számos megoldás alakult ki, a továbbiakban ezeket tekintjük át.Minden hibakezelési eljárás az eredeti bitsorozatot redundanciával (ismétlődéssel) küldi. Ha ezekkel a kódokkal a hiba felismerhető, akkor hibajelző (Error Detecting Codes, EDC) kódokról, ha a vevő azt is képes megállapítani, hogy minek kellett volna érkeznie, akkor hibajavító (Error Correcting Codes, ECC) kódokról beszélünk. A redundáns kódok az eredeti adatmennyiséget értelemszerűen megnövelik, ami a hasznos sávszélességet csökkentik.
A hibák időtartamának figyelembevételével megkülönböztethetünk egyedi- és csoportos hibákat. Ha a hiba csak 1 bitre hat ki, akkor egyedi-, ha több bit átvitele alatt fennáll, akkor csoportos bithibákról beszélünk.
Hamming-távolság
A hibák egy speciális fajta, amikor úgy változik meg egy kód, hogy egy másik, de értelmes kód lesz belőle. Ez abban az esetben valósulhat meg, ha a két kódszó Hamming-távolsága 1. Hamming távolságnak nevezzük azoknak a biteknek a számát, amelyek megváltozásakor az egyik kód a másik kódra alakítható. Ha például két kód Hamming-távolsága 1, akkor ezek 1 bitben térnek el egymástól. Az ASCII kód Hamming-távolsága 1. A Hamming-távolság meghatározásához a két szó között kizáró-vagy (XOR) logikai műveletet kell végrehajtani, majd az eredményben meg kell számolni az egyesek számát. Ismétlésképpen a kizáró vagy kapcsolat kimenete csak akkor lesz logikai 1, ha a bemenetei eltérő állapotúak.
A kód Hamming-távolsága alapján lehet egy kód hibajelző, vagy hibajavító tulajdonságú. Egy n-bites hiba jelzéséhez n+1 bites kódot kell használni, mivel ilyen kódolás során egy n-bites hiba nem tudja az egyik kódszót a másik érvényes kódba átvinni. A hiba javításához a használt kódok távolságának 2n+1 (n a kódbitek száma) Hamming-távolságú kód kell.
A hibajelzés fajtái
A hibajelzés feladata egy- vagy több bit hibájának jelzése. Mivel nincs szükség a hiba javítására, a megoldások viszonylag egyszerűnek tekinthetők. A hibajelzés gyakorlatban alkalmazott típusai:
Paritásbites hibajelzés a hibajelzés legegyszerűbb az egyik leggyakrabban használt fajtája. Két alapvető típusát különböztethetjük meg, a páros- és a páratlan paritást. Páros-paritás használatakor az adatot olyan bittel egészítjük ki, hogy az adatcsomagban, amelyben már a paritásbit is benne van, az egyesek száma páros legyen. A páratlan-paritás megoldás is hasonló, csak itt az adatcsomag 1-eseinek száma páratlannak kell lennie. Ha átvitel során bármelyik bit megváltozik, akkor azt képes a vevő érzékelni. Természetesen a módszer csak akkor működik, ha az átvitel előtt a résztvevők megállapodnak a paritás típusában. A működésből látható, hogy a bithiba helyét nem tudjuk meghatározni. Amennyiben páros számú bit változik meg, akkor azt nem képes ez a módszer felismerni. Ilyen védelmet használnak az RS-232C soros adatátvitelnél is.
Tömbparitás vizsgálat: A paritásbites hibajelzés továbbfejlesztése. Az átvitelre kerülő információblokkot egy mátrixnak tekintjük. A mátrix oszlopainak száma a paritásbittel kiegészített kódszó hossza, a sorok száma pedig a blokkban lévő kódszavak száma. Minden sor tartalmaz egy paritásbitet, ezen túlmenően minden képzeletbeli oszlophoz is kiszámítunk egy paritásbitet. Ezt a paritásszót az utolsó kódszó után továbbítjuk. Ez a megoldás nem csak egyedi bithibák felismerésére használható, hanem képes jelezni az egyedi csoporthibákat is.
CRC (Cyclic Redundancy Check, ciklikus redundancia ellenőrzés) az előzőekhez képes jelentősen bonyolultabb megoldás, amellyel csoportos bithibák felismerése valósítható meg. A kódot alkotó biteket egy polinom együtthatóiként kezeljük. Egy n-bites kód esetén az együtthatók xn-1 és x0 közöttiek lesznek. Így a polinom felírható
xn-1+ xn-2+xn-3 +xn-4 +xn-5 + xn-6+ xn-7+ .......... +x4 +x3 +x2 + x1+ x0
Például: legyen a kód 10011001. Ebben az esetben a polinom a következő lesz:
x7 +x4 + x3+ x0
Csak azokat a tagokat kell felírnunk, amelyik helyiértéken az eredeti kódban 1 állt.
A polinomok alkalmazásakor a kommunikációban résztvevőknek meg kell egyezniük egy közös polinomban, amelyet generátor polinomnak (Generator Polynomial) nevezünk és általában a G(x) módon jelöljük. A generátor polinommal kapcsolatban alapvető követelmény, hogy a legalsó és a legfelső bitjének 1-esnek, valamint a továbbítandó keretnek hosszabbnak kell lennie, mint a generátor polinom.
A CRC védelem során olyan ellenőrző összeget fűzünk a továbbítandó kerethez, amely úgy egészíti ki azt, hogy az így kapott keret által meghatározott polinom osztható legyen a generátor polinommal. Miután a vevő megkapta a keretet, megpróbálja elosztani a generátor polinommal. Ha az osztás során van maradék, akkor hiba történt az átvitel során. Az eljárás meglehetősen bonyolult matematikailag, de a számítógépek ezt nagyon gyorsan képesek elvégezni, sőt. 1961-ben Peterson és Brown bebizonyította, hogy az ellenőrző kód léptető-regiszterekkel előállítható. Ezt a hardvert ma már a legtöbb hibajavítással kapcsolatba kerülő áramkör használja. A m-bites ellenőrző bittel ellátott polinomkód legfeljebb m-bites csoportos bithibát hibát képes jelezni. A gyakorlatban három polinom vált szabvánnyá:
CRC-12 = x12+x11+x2+ x1+ 1, amit olyankor használhatunk, amikor a karakterhossz 6 bit.
CRC-16 = x16+x15+x2+ 1, 8 bites karakterekhez használható.
CRC-CCITT = x16+x12+x5+ 1, szintén 8 bites karakterekhez alkalmazhatjuk.
A 16 bites CRC kódok képesek felismerni minden egybites-, kétbites-, minden páratlan hibás bitet tartalmazó hibát, minden 16 vagy kevesebb bitnyi csoportos bithibát, a 17 bites csoportos bithibák 99, 997%-át, a 18 vagy magasabb bitszámú hibák 99,998%-át (forrás: Andrew S. Tannenbaum Számítógéphálózatok, Panem kiadó).
Adatkapcsolati protokollok
Az adatkapcsolati réteg, mint azt már tudjuk, a keretek elkészítését valósítja meg, valamint előállítja a védelemhez szükséges ellenőrző összeget (CRC). A kereteket átadja a fizikai rétegnek, amely azt továbbítja a vevő irányába. Felmerülhet a kérdés, hogy honnan tudja a fizikai réteg, hogy ki a címzett? Természetesen a létrehozott keretnek rendelkeznie kell egy címmező résszel, amelyből már kiolvasható az a cím, ahová el kell küldeni a csomagot. A másik kérdés, ami felmerülhet, hogy hogyan értesül az adó, ha a vevő hibásan kapta meg a csomagot, vagy még rosszabb esetben (bár a végeredmény szempontjából majdnem mindegy) meg sem kapta a csomagot? A hibalehetőségek száma csak növekszik, ha az adó és a vevő egyszerre adhat. Ezeknek a problémáknak a kezelésére több módszert fejlesztettek ki.
Korlátozás nélküli szimplex protokoll
Mint a nevében is benne van, egyirányú adatátvitelt feltételez. Amilyen egyszerű, a gyakorlatban annyira használhatatlan is. A vevő akármilyen sebességgel és bármikor küldhet kereteket, a vevő mindig képes fogadni azokat. Ez azt jelenti, hogy a hosztok hálózati rétegei mindig készen állnak az adatátvitelre, a feldolgozási idő elhanyagolhatóan rövid, a keretek tárolásához végtelen kapacitás áll rendelkezésre. Az két adatkapcsolati réteg közötti csatorna hibamentes, tehát nem fordul elő semmilyen hiba.
Szimplex megáll- és vár protokoll
Az előző megoldás továbbfejlesztése, annak hibáinak bizonyos mértékű lecsökkentése. Az előző megoldás legnagyobb problémája az, hogy szinte soha sem képes a vevő olyan sebességgel feldolgozni a kereteket, ahogy az adó küldi, vagy a hibás keretek adását meg kell ismételni. A hibalehetőség és az elárasztás lehetősége fokozottan jelentkezik akkor, ha a vevőnek több vonalra is figyelnie kell.
A megoldás meglehetősen kézenfekvő, a vevőnek közölnie kell az adóval, hogy mikor adhatja a következő keretet, amelyet már képes fogadni. Ezt legegyszerűbben nyugtázással lehet ezt megvalósítani. A vevőnek egy nyugtázást kell küldenie az adónak akkor, ha végzett az előző keret vételével, feldolgozásával. A nyugta megérkezéséigaz adó egyszerűen várakozik. Abban az esetben, ha az adó nem kap egy időtartam alatt a vevőtől nyugtázást az elküldött keretre, akkor ismét elküldi az utolsó keretet.
Súlyosabb probléma az, ha a nyugtakeret veszik el, vagy sérül meg. Ebben az esetben szintén elküldi az adó az utolsó keretet, amit a vevő úgy értelmezhet, hogy egy új keretet kapott. Ez nagyon súlyos hiba, kivédéséhez a vevőnek kell felismernie az egymás után kapott azonos üzeneteket.
Egyirányú összetett protokoll
Az előzőekben említett hibákat képes kiküszöbölni a szimplex hálózatoknál. Az adó egy sorszámot helyez el az éppen elküldött keret fejrészébe. A vevő mikor veszi a keretet ezt a bitet vizsgálja. Amennyiben értéke 0, akkor a kapott keretet az adó először küldte. Ha az adó nem kapja meg erre a nyugtázást, akkor ismét elküldi a keretet, de a nyugtát jelző bitet 1-re állítja be. A vevő veszi ismét a keretet, amit el is dob, mivel a fejrészben 1 értékű nyugtabitet talált. Ismét nyugtát küld az adónak, amely vételekor folytatódhat az információ továbbítása.
Kétirányú protokollok
Az előbbiekben ismertetett protokollok csak szimplex csatornákon voltak használhatók. A duplex vonalak esetében a keretek és a nyugták egy időben képesek a vonalon haladni, emiatt az üres várakozási állapotok lecsökkennek. A legkézenfekvőbb megoldás, ha két vonalat építünk ki az adó és a vevő között és mindegyiket szimplex, de ellentétes irányú átvitelre használjuk. Amilyen egyszerű ez a struktúra, az esetek többségében annyira gazdaságtalan is, hiszen a nyugtázásra használt vonal csak nagyon ritkán használt, tehát a kihasználtsága nagyon kicsi. Sokkal célszerűbb ugyanazt a vonalat használni a két ellentétes irányú átvitelhez használni. Tulajdonképpen erre láthattunk példát az előzőekben is.
Amikor a vonalat kétirányú átvitelre használjuk, az adatkeretek összekeverednek a vezérlőkarakterekkel. Ennek kiküszöbölésére a keretben elhelyeznek egy bitet, amelyet megvizsgálva eldönthető, hogy milyen kerettel van dolgunk. A nyugtázás okozta sávszélesség veszteség csökkenthető, ha a nyugtakeretet egy, az ellenkező irányba továbbítandó adatkeretbe építünk be. Így tulajdonképpen a nyugtát ráültetjük az adatkeretekre, ezért nevezik ezt az eljárást ráültetéses (piggy-back) technikának.
A sávszélesség hatékonyabb kihasználása mellett a piggy-back technika felvet néhány olyan problémát, amely a különálló nyugták esetében nem jelentkezik. Az egyik legsúlyosabb, hogy meddig várakozzon az adatkapcsolati réteg, amíg kap a hálózati rétegtől egy olyan keretet, amelyre ráültetheti a nyugtát? Amennyiben az adó nem érzékel egy bizonyos időtartam alatt nyugtát, a keretet újraküldi. A várakozást egy időzítő határozza meg, ennek lejártakor az adatkapcsolati réteg egy önálló nyugtakeretet küld el az adónak.
A duplex átvitelhez a csúszóablakos protokollokat (sliding window) nagyon gyakran használják a gyakorlatban. A számítógép-hálózatokban a vonal kihasználtságát növeli, ha nem csak egy keret van egyszerre jelen. A küldő elküld bizonyos számú keretet, majd várakozási állapotba kerül. Ezeket a kereteket a vevő nyugtázza, aminek eredményeként a küldő ismét elküldhet annyi keretet, amennyi nyugtát kapott. A működés felépítése követhető nyomon a következő ábrán.
Minden keretnek sorszáma van, amely az egymást követő kereteknél egyesével növekszik (a példában 8 keret 0-7 sorszámmal). Az adó fenntart egy listát, amelyben azok a keretek szerepelnek, amelyeket elküldött, de még nem érkezett válasz. A vevőnek szintén van egy listája, amelyben azok a keretek szerepelnek, amelyeket az adótól vár. Amikor vesz egy keretet, akkor a sorszám alapján nyugtázza azt az adónak. Ha olyan keret érkezik, amely sorszáma nincs a saját listáján, akkor azt eldobja. A keretek nyugtázása csak sorfolytonosan történhet. Nem szükséges minden keretet nyugtázni. Ha a vevő vesz egy keretet és a listában előtte szereplő keretek már beérkeztek, akkor elegendő csak a legmagasabb sorszámút visszaigazolni és azablak annyival feljebb tolódik. Az adó a listában figyeli a keretek időtartamát. Ha egy értéket elér, akkor azt újraadja.
Egybites csúszóablakos protokoll
Olyan speciális csúszóablakos protokoll, amelyben az ablak mérete 1, tehát a egyszerre egy keret van a vonalon. Az adatátvitel kétirányú, a küldött keret tartalmazza az előzőleg elküldött keret nyugtáját (ráültetéses protokoll).
N visszalépést alkalmazó protokoll
Elsősorban a nagy távolságú hálózatok (pl. Műholdas) esetében nem gazdaságos, ha addig nem kerül újabb keret küldésre, amíg az előküldöttre nem érkezik válasz. Az adó nyugtázás nélkül elküld n keretet. Az m. keret után várja a nyugtázásokat. Hogy ezek megérkeznek, az adó folytatja a küldést az n+1 kerettel. Abban az esetben, ha a valamelyik keret megsérül, akkor a vevő az azt követő kereteket nyugtázás nélkül eldobja, ami az adót arra kényszeríti, hogy újraadja azokat. Ez a megoldás a zajos, rossz vonalakon a sávszélességet és ezzel együtt a kommunikációs sebességet jelentősen lecsökkenti.Szelektív ismétlő (selective repeat) protokoll
Az előzőhöz hasonló, de annak továbbfejlesztett változata. Ha a vevő egy rossz keretet vesz, akkor azt eldobja, de a következőket eltárolja és nyugtázza. Az adónak csak azt a keretet kell ismételnie, amelyre nem érkezett nyugtázás.A következő részben néhány, a gyakorlatban használt, az előzőekre épülő adatkapcsolati protokollt mutatunk be.
Nincsenek megjegyzések:
Megjegyzés küldése