Rolul nivelului: realizarea comunicatiei intre calculatoare interconectate direct.
Probleme:
Erorile de transmisie fac ca ocazional un bit 0 transmis sa fie receptionat ca un bit 1, sau reciproc, un 1 sa fie receptionat ca 0; se mai poate intampla ca un bit sa fie complet pierdut sau un bit (aleator) sa fie inserat in fluxul receptionat.
Daca emitatorul transmite mai multi biti decat strictul necesar pentru transmiterea informatiei, este posibil ca receptorul sa detecteze anumite erori de transmisie, si eventual chiar sa reconstituie mesajul original. In toate situatiile insa, se presupune ca numarul erorilor nu depaseste o anumita valoare; in caz contrar mecanismul nu functioneaza.
Exemplu: verificarea paritatii. Fiecare octet este transmis ca un sir de 9 biti, primii 8 fiind octetul de trimis, iar al 9-lea construit astfel incat numarul total de biti 1 sa fie par. de exemplu, 11001010 va fi transmis ca 110010100, iar 00101100 va fi transmis ca 001011001. Receptorul verifica daca numarul de biti 1 receptionati este par: daca da, ia primii 8 si-i considera ca fiind mesajul de primit (ignorand apoi al 9-lea), daca nu, decide ca transmisia a fost eronata si cere retrimiterea octetului. Mecanismul este capabil sa detecteze erorile de un singur bit; daca doi biti sunt inversati, eroarea nu poate fi detectata.
In general, detectia erorilor se bazeaza pe urmatorul mecanism: un mesaj de n biti este transmis ca un sir de n+m biti, unde m este un numar natural convenabil ales (a se vedea mai jos). Din cele 2^(m+n) mesaje de m+n biti posibile, sunt considerate valide doar 2^n; fie M multimea acestor mesaje valide. Corespondenta intre mesajele originale de transmis si mesajele din M este biunivoca si fixata prin protocol.
Acum, daca emitatorul vrea sa trimita un sir de n biti, trimite mesajul dim M asociat. Receptorul, daca receptioneaza un mesaj din M, deduce ca i-a fost trimis sirul de n biti asociat acelui mesaj valid, altfel declara ca s-a produs o eroare.
Un protocol capabil sa detecteze erori de cel mult k biti trebuie sa aleaga o multime M cu proprietatea ca distanta Hamming (adica nr. de biti care trebuie inversati pentru a transforma un cuvant in celalalt) dintre oricare doua mesaje din M este cel putin k+1. In felul acesta, un mesaj afectat de erori, dar nu mai mult de k erori, va fi transformat intr-un sir ce nu face parte din M, si va fi invalidat de receptor.
M este o multime de "puncte izolate" in {0,1}^(m+n): bila de raza k centrata intr-un punct din M nu contine nici un alt punct din M. Un mesaj trimis va fi insa transformat, in urma erorilor, intr-un element din {0,1}^(m+n), aflat in bila centrata in mesajul original si de raza k.
Daca se doreste corectarea erorilor de cel mult k biti, trebuie ca bilele de raza k centrate in elementele lui M sa fie disjuncte. In acest mod, daca receptorul primeste un mesaj afectat de erori, el va receptiona un sir care, ca element al lui {0,1}^(m+n) se gaseste in bila de raza k centrata in sirul trimis. Deoarece bilele sunt disjuncte, sirul trimis este unic determinat de sirul primit, astfel incat receptorul poate regasi sirul trimis, adica poate "corecta erorile".
Este mecanismul cel mai utilizat. Fiecare sir de biti este privit ca fiind un polinom cu coeficienti in corpul (F_2, +, *). De exemplu, sirul 01101100 va avea atasat polinomul X^6+X^5+X^3+X^2.
Protocolul presupune alegerea in prealabil a unui polinom de grad m, numit polinom generator, notat G(X). M va fi multimea polinoamelor de grad cel mult m+n-1 divizibile cu G(X).
Codarea se face astfel: sirului initial de n biti i se asociaza polinomul P(X) de grad cel mult n-1. Se calculeaza restul R(X) al impartirii lui X^m*P(X) la G(X); gradul lui R(X) este cel mult m-1. Deoarece R(X) este restul impartirii, rezulta ca X^m*P(X)-R(X) este divizibil cu G(X), si cum in F_2 1+1=0 rezulta ca X^m*P(X)+R(X) = X^m*P(X)-R(X) este divizibil cu G(X). Deci, secvanta formata din sirul de n biti al coeficientilor lui P(X) urmat de sirul de m biti ai coeficientilor lui R(X) este un element din M, si acesta este cuvantul ce va fi trimis.
Deci, sirul trimis este sirul original concatenat cu sirul coeficientilor restului impartirii polinomului X^m*P(X) la G(X).
La receptie, mesajul este recuperat ca fiind primii n biti din mesajul primit, iar verificarea daca au fost erori la transmisie se face impartind polinomul corespunzator mesajului primit la G(X).
Din considerente de linearitate, distanta minima dintre doua elemente din m este egala cu distanta minima intre un multiplu nenul al lui G(X) si polinomul nul. Aceasta distanta minus unu este numarul maxim de erori detectabile.
Scop:
La transmisia pe linii seriale, exista 2 metode folosite:
Acest protocol nu permite retrimiterea mesajelor eronate.
Protocol posibil: fiecare mesaj trimis este confirmat de receptor. Emitatorul, dupa transmiterea unui mesaj, asteapta confirmarea inainte de-al trimite pe urmatorul. Daca confirmarea nu soseste dupa un anumit intrval de timp, retrimite mesajul.
Problema: daca se pierde confirmarea unui mesaj, emitatorul va retrimite mesajul, dar receptorul va interpreta retransmisia ca fiind noul mesaj.
Solutia: se numeroteaza mesajele; fiecare mesaj va purta numarul de ordine. Daca receptorul primeste o copie a ultimului mesaj primit, o va confirma (caci a fost retrimisa ca urmare a faptului ca prima confirmare a fost pierduta), dar nu il va trensmite "utilizatorului final".
Solutie mai buna: se trimite doar ultimul bit din numarul mesajului, deoarece este suficient pentru receptor pentru a distinge intre noul mesaj si retransmiterea vechiului mesaj.
Protocolul cu confirmare si retransmitere obliga emitatorul sa astepte confirmarea mesajului trimis inainte de-a transmite urmatorul. Daca timpul necesar propagarii dus-intors a semnalului este mare, in raport cu timpul necesar transmiterii unui mesaj, emitatorul si canalul "dus" vor sta mult timp in asteptarea confirmarii unui mesaj. O imbunatatire consta in a permite emitatorului sa trimita in avans unanumit numar de pachete. Astfel, emitatorul va avea o fereastra de k1 pachete pe care le poate trimite; fereastra incepe cu primul pachet netransmis sau neconfirmat.
Emitatorul trimite pachetele din fereastra fara sa astepte confirmare. Daca termina de trimis pachetele din fereastra, asteapta. Daca primeste confirmari, avanseaza fereastra. Daca un pachet din fereastra nu este confirmat dupa un anumit interval de timp, este retrimis.
Receptorul poate aplica algoritmul anterior; in acest caz, daca primeste un mesaj cu numar de ordine mai mare decat cel asteptat (datorita pierderii unui mesaj anterior) il va ignora. Dupa expirarea timpului, emitatorul va retrimite mesajul asteptat de receptor, receptorul il va primi si confirma, dupa care va expira timpul si pentru mesajele ulterioare si emitatorul le va retrimite si pe acestea.
Este nevoie de mai mult de 1 bit pentru numarul de ordine al pachetului: care este numarul de biti necesari?
O alta imbunatatire a algoritmului se poate aduce daca receptorul memoreaza pachetele situate dupa un pachet pierdut; in acest fel, daca un pachet se pierde, emitatorul trebuie sa retransmita numai pachetul pierdut, nu si pachetele imediat urmatoare.
Pentru aceasta, receptorul va avea si el o fereastra de receptie, de o dimensiune fixata k2; fereastra incepe cu primul pachet nereceptionat. Daca soseste un pachet din fereastra de receptie, receptorul il memoreaza si trimite inapoi confirmarea. Daca pachetul primit a fost cel de la inceputul ferestrei, esta pasat nivelelor superioare si fereastra este avansata; daca nu, se asteapta mai intai sa fie primite toate pacheele din fata lui.
Astfel, protocolul anterior cu confirmare si retrenasmitere este un caz particular al ferestrei glisante pentru cazul k1=k2=1.
O alta imbunatatire ce se poate aduce este asa-numita confirmare negativa (negative acknowledge, NAK): daca receptorul primeste un pachet cu erori de transmitere, dar din care poate reconstitui numarul de ordine, el va trimite o confirmare negativa pentru acel pachet. Confirmarea negativa se mai trimite pentru primul pachet asteptat (cel de la inceputul ferestrei) daca receptorul primeste un pachet situat dupa el.
La primirea unei confirmari negative, emitatorul retrimite imediat pachetul confirmat negativ, fara sa mai astepte expirarea timpului.
Evident, confirmarile negative se pot pierde, motiv pentru care confirmarile negative reprezina doar optimizari,
Retele de calculatoare