Am uitat parola x Creaza cont nou   Home Exploreaza Upload

Retelele cu Conexiuni Directe

Retele

ALTE DOCUMENTE Documentatie de proiect - retele Componentele ruterului Instalarea si configurarea placilor de retea Tipuri de protocoale TCP/IP

Retelele cu Conexiuni Directe

Cuprins

Problema: Conexiunea fizica a retelelor

Elemente construnctive hardware

1.1 Noduri

Legaturi

Tehnici de codificare (NRZ, NRZI, Manchester, 4B/5B)

Incadrarea

3.1 Protocoale orientate pe byte (BISYNC, IMP-IMP, DDCMP)

3.2 Protocoale orientate pe bit (HDLC)

3.3 Incadrarea bazata pe ceas (SONET)

Detectia erorilor

4.1 Controlul ciclic prin redundanta

4.2 Parietate bidimensionala

4.3 Algoritmul suma de control Internet

Transmisii fiabile

5.1 Stop-and-Wait

5.2 Ferestre glisante

5.3 Canale logice concurente

CSMA/CD (Ethernet)

6.1 Proprietati fizice

6.2 Protocolul de acces

6.3 Experienta cu Ethernet

Inele cu jeton (FDDI)

7.1 proprietati fizice

7.2 Algoritmul jeton temporal (timed-token)

7.3 Intretinerea jetonului

7.4 Formatul cadrului

Adaptor de retea

8.1 Componente

8.2 Vedere dinspre host

8.3 Exemple de driveri de dispozitiv

Retele cu conexiuni directe

Introducere

In acesta lucrare au fost prezentate elemenetele constructive hardware ale unei retele de calculatoare, in speta nodurile si legaturile, si au fost discutate cele cinci probleme cheie care trebuie rezolvate astfel incat doua sau mai multe noduri conectate prin intermediul unei retele fizice sa fie capabile de a schimba mesaje unul cu altul.

Mai intai, legeaturile transporta semnale. Ca atare, este necesara codarea bitilor care transforma un mesaj binar in semnal la nodul sursa si apoi recuperarea bitilor din semnal la nodul receptor. Aceasta constituie problema codarii, iar dificultatea sa deriva din necestitatea de a mentine sincronizarea intre ceasurile emitatorului si receptorului. Au fost discutate patru tehnici de codare diferite – NRZ, NRZI, Manchester si 4B/5B – care difera semnificativ sub aspectul coadarii informatiilor legate de ceas odata cu datele transmise. Unul dintre atributele cheie ale unei scheme de codare este eficienta cesteia, cu alte cuvinte raportul dintre impulsurile de semnal si bitii codati.

Odata ce transmiterea de biti intre doua noduri a devenit posibila, urmatoare etapa o reprezinta modalitatea de impachetare a acestora in cadre. Aceasta reprezinta problema incadrarii, care se reduce la capacitatea de a recunoaste inceputul si sfarsitul fiecarui cadru. Din nou, au fost abordate diferite metode, incluzand protocoale orientate pe bit, protocoale orientate pe byte, respectiv protocoale bazate pe ceas.

Presupunand ca fiecare nod este capabil sa recunoasca ansamblul de biti care alcatuiesc un cadru, a treia problema consta in a determina daca acesti biti sunt corecti, sau daca au fost alterati in timpul tranzitului. Aceasta reprezinta problema detectiei erorilor, pentru a carei rezolvare au fost prezentate trei metode: controlul ciclic prin redondanta , paritatea bidimensionala si sumele de control. Dintre acestea, metoda CRG ofera cele mai puternice garantii si este cea mai frecvent folosita la nivel de legatura.

Daca se stie ca unele cadre vor ajunge la nodul destinatie cu erori si, ca atare, vor trebui ignorate, urmatoarea problema o reprezinta recuperarea acestor pierderi. Scopul este ca legatura sa apara ca fiind sigura. Metoda generala de rezolvare a acestei probleme este abreviata ARQ si implica utilizarea unei combinatii de confirmari si temporizari. S-a discutat despre trei algoritmi ARQ specifici, in speta SAW, fereastra glisanta si canalele concurente. Ceea ce face acesti algoritmi interesanti este eficienta de utilizare a legaturii, scopul fiind acela de a mentine canalul permanent ocupat.

Problema finala nu este relevanta pentru legaturile punct-la-punct, dar reprezinta problema centrala a retelelor cu ceas multiplu. Problema o reprezinta intermedierea accesului la o legatura partajata astfel ca toate nodurile sa aiba , in final, posibilitatea de a-si transmite datele. In acest caz, ne-am oprit asupra doua protocoale de acces la mediu diferite: CSMA/CD si inelul cu jeton-care au fost puse in practica in retele locale de tip Ethernet, respectiv FDDI. Elementul comun al acestor tehnologii este repartizarea in retea a controlului pe toate nodurile existene; n exista nici un fel de dependenta de un arbitru central.

Am incheiat lucrarea prin a observa ca, in practica, majoritatea algoritmilor care rezolva aceste cinci probleme sunt implementati pe adaptorul care realizeaza conexiunea intre host si legatura. S-a remarcat ca modul de proiectare a acestui adaptor este de o importanta capitala asupra performantelor de ansamblu ale retelei.

Problema: conexiunea fizica a retelelor

Cea mai simpla retea posibila este aceea n care toate host-urile sunt cionectate in mod direct prin intermeiul unui mediu fizic. Acesta poate fi un cablu sau o fibra optica si poate acoperi o regiune mica (de ex. O cladire cu birouri). Cu toate acestea, conectarea a doua sau mai multe noduri prin intermediul unui mediu corespunzator reprezinta numai primul pas. Exista cinci probleme aditionale care trebuie rezolvate inainte de a exista posibiltatea de transfer a pachetelor intre noduri.

Prima o reprezinta codarea bitilor pe cablu sau pe fibra astfel incat acestia sa poata fi acceptati de catre host-ul receptor. A doua o constituie defalcarea secventei de biti transmisi prin conexiunea in mesaje complete, care pot fi livrate nodului terminal. Aceasta se numeste problema incadrarii, iar mesajele livrate host-urilor finale sunt deseori numite cadre. In al treilea rand, deoarece cadrele sunt uneori alterate in timpul transmisiunii, este necesara detectia acestor erori si executarea unor actiuni corespunzatoare; aceasta repreinta problema detectiei erorilor. A patra problema consta in a face o legatura sa apara ca sigura, in ciuda faptului ca altereaza uneori cadrele. In final, in acele cazuri in care legatura este partajata de host-uri multiple, spre deosebire de o legatura simpla punct-la-punct, este necesara intermedierea accesului la aceasta conexiune. Aceasta reprezinta problema controlului accesului la media.

Desi aceste cinci probleme – codificare, incadrarea, detectia erorilor, livrarea in sigurant si medierea accesului – pot fi discutate in mod abstract, reprezinta probleme foarte reale, care sunt rezolvate in diferite moduri de catre diferite tehnologii de retea. Lucrarea de fata va discuta aceste probleme in contextul a trei tehnologii de retea specifice: legaturi punct-la-punct, retele cu acces multiplu prin detectarea semnalului purtator (Carrier Sense Multiple Access - CSMA), din care Ethernetul este cel mai cunoscut exemplu si inelele cu jeton (dintre care cel mai cunoscut exemplu este FDDI). Scopul acestei lucrari il reprezinta parcurgerea tehnologiei de retea disponibile simultan cu explorarea acestor cinci aspecte fundamentale.

Inainte de a aborda problematica specifica conectarii host-urilor, aceasta lucrare incepe prin a examina elementele constuctive ce urmeaza a fi folosite, in speta nodurile si conexiulnile. In continuare vor fi explorate primele trei probleme – codarea, incadrarea si detectia erorilor – in contextul unei legaturi simple punct-la-punct. Tehnicile prezentate in aceste trei sectiuni au un caracter general si ca atare au o buna aplicabilitate in retelele cu acces multiplu. Problema unei livrari sigure a datelor este luata in considerare in continuare. Din moment ce fiabilitatea nu este de regula implementata in retelele cu acces partajat, aceasta discutie se concentreaza numai asupra legaturilor punct-la-punct. In final, se trateaza problema accesului media prin examinarea principalelor doua metode de gestionare a accesului la o legatura partajata, in speta CSMA si inelul cu jeton.

Se va retine ca aceste cinci functii sunt, in general, implementate intr-un adaptor de retea, in speta o placa conectata la magistrala I/O a unui host la un capat, respectiv la mediul fizic la capatul celelalt. Cu alte cuvinte, intre adaptoare are loc un schimb de biti, dar cadrele corecte sunt transferate intre noduri. Acest adaptor este controlat de programe care ruleaza pe nodul respectiv – in speta driver-ul de dispozitiv – care la randul sau este reprezentat ca protocolul de la baza grafului de protocoale. Aceasta lucrare se incheie cu un exemplu concret de adaptor de retea si schiteaza driver-ul de dispozitiv pentru un atare adaptor.

1. Elemente constructive hardware

Retelele sunt alcatuite din doau clase de elemente constructive hardware: nodurile si legatrile. Aceasta afirmatie este la fel de adevarata si pentru cea mai simpla retea posibila – in cadrul careia o singura legatura punct-la-punct conecteaza o pereche de noduri - dar si pentru un internet la scara mondiala. Aceasta sectiune contine o scurta vedere de ansamblu asupra notiunilor de nod si legatura, definind astfel tehnologia de baza care va sta la baza restului acestei lucrari.

1.1 Noduri

Nodurile sunt cel mai adesea calculatoare de uz general, precum o statie de lucru, un multiprocesor sau un PC. Pentru scopurile noastre, sa presupunem ca este un sistem de clasa statie de lucru. Aceasta statie de lucru poate servi drept host pentru rularea de programe de aplicatie de catre utilizatori sau poate fi folosita in interiorul retelei drept comutator pentru transferul mesajelor de la o legatura la alta, sau poate fi configurata ca ruter care transfera pachete internet dintr-o retea in alta. In unele cazuri, un nod de retea – cel mai adesea un comutator sau un ruter in interiorul retelei, rareori un host – este implementata prin echipamente hardware cu destinatie speciala. Aceasta se realizeaza de obicei din ratiuni de performanta: in general este posibila constructia unui echipament cu o anumita destinatie, care executa o anumita functie mai rapid decat o poate face un procesor de uz general, dupa care vom explica de ce si cum poate fi impenetata aceasta functionalitate de catre echipamente speciale.

Desi am putea ramane la aceasta faza, este util de cunostcut cateva detalii despre infrastructura unei statii de lucru. Aceasta informatie devine eosebit de importanta cand se pune problema performantelor retelei. Fig. 1 reprezinta o diagrama bloc a unui sistem de clasa masina de lucru. Trebuie retinute trei caracteristici cheie ale acestei figuri.

Mai intai, cantitatea de memorie a oricarei masini este finita. Poate fi 4 MB sau 128 MB, dar nu este infinita. Acesta este un aspect important deoarece memoria se dovedeste a fi una dintre cele doua resurse rare in retea (cealalta este largimea de banda a legaturii), care trebuie gestionata cu atentie daca se doreste ca fiecare utilizator al retelei sa dispuna de o alocare corecta a resurselor acesteia. Memoria este o resursa pretioasa deoarece, pe un nod care serveste drept comutator sau ruter, pachetele trebuie stocate in buffere de memorie pana le soseste randul de a fi transmise pe o legatura de transmitere in exterior.

In al doilea rand, fiecare nod se conecteaza la retea prin intermediul unui adaptor de retea. Acest adaptor se afla in geeral plasat pe magistrala I/O a sistemului si transporta date intre memoria statiei de lucru si lagatura de retea. Un modul software care ruleaza pe statia de lucru – driver-ul de dispozitiv – gestioneaza acest adaptor. Acesta emite comenzi catre adaptor, indicind-ui, de exemplu, din ce locatie de memorie trebuie transmise datele care ies din sistem si in ce locatie de memorie trebuie stocate datele care intra in sistem.

In final, desi viteza de lucru a microprocesoareler creste intr-un ritm incredibil, despre memorii nu se poate spune acelasi lucru. Studii recente de performanta indica o dublare a vitezelor de procesare la fiecare 18 luni, dar viteza memoriei creste cu numai 7% pe an. Semnificatia acestei diferente este ca, in calitate de nod de retea, o statie de lucru ruleaza la viteza memoriei, nu la acea a procesorului, inrtr-o prima aproximare. Aceasta inseamna ca programele de retea trebuie sa fie atente cu privire la utilizarea memorie si, in particular, la numarul de accesari ale memoriei necesar la procesarea unui mesaj. Nu ne putem permite luxul de a fi lenesi numa din

Adaptor

de retea

 

Memorie

 

Cache

CPU

  pricina cresterii la infinit a vitezei procesoarelor.

(Spre retea)

Magistrala I/O

Figura 1. Exemplu de arhitectura a unei statii de lucru.

1.2 Legaturi

Legaturile de retea sunt implementate pe o varietate de medii fizice diferite, inclusiv cablu bifilar torsadat (genul de cablu prin care se conecteaza telefonul Dvs.), cablu coaxial (cablu prin care se conecteaza televizorul Dvs.), fibra optica (la care dorim sa ne conectam cu totii) si spatiul (mediul de propagare a undelor radio, a microundelor si razelor laser). Indiferent de mediul fizic, acesta este folosit la propagarea de semnale. Unele semnale iau numai valori discrete, cum ar fi impulsurile de tensiune pozitive sau negative. Legaturile prin care sunt transmise semnalele discrete se numesc digitale. Alte legaturi transporta semnale electromagnetice continui a caror frecventa variaza intre, sa zicem, 300 si 3300 Hz (domeniul telefoniei). Legaturile prin care sunt transmise semnalele continui se numesc analoge.

Legaturile digitale si analoge asigura fundatia pentru transmiterea tuturor categoriilor de informatii, inclusiv a genului de date pe care suntem interesati sa le transmitem, in speta succesiuni de 1 si 0. Se spune ca datele binare sunt codate in semnal. De exemplu, in modem (modulator / demodulator) este un dispozitiv care codifica datele binare intr-un semnal digital in partea de transmisie, respectiv le decodifica inapoi in date binare in partea de receptie. Un transmitator digital este un dispozitiv care transmite datele binare (digitale) pe o legatura digitala. Vom reveni asupra problemei codificarii datelor binare in sectiunea 2.

Un alt atribut al unei conexiuni il reprezinta numarul de fluxuri de biti care poate fi codificat in acesta la un moment dat. Daca raspunsul este unul singur, atunci nodurile conectate la legatura trebuie sa partajeze accesul la aceasta. Aceasta este situatia pentru legaturile cu acces multiplu descrisa in sectiunile 6 si 7. Cu toate acestea, pentru legaturile punct-la-punct se intampla deseori ca doua fluxuri de biti sa fie transmise simultan prin legatura, cate unul in fiecare directie. O asemenea legatura se numeste duplex. O legatura punct-la-punct care suporta parcurgerea legaturii intr-un singur sens la un moment dat – si care se numeste semiduplex – implica necesitatea ca nodurile conectate prin aceasta legatura sa o utilizeze in mod alternativ. Pentru scopurile acestei lucrari, vom presupune ca toate legaturile punct-la-punct sun de tip duplex.

Dintre celelalte proprietati ale unei legaturi, singura de interes in acest moment este una extrem de pragmatica – anume distanta la care ajunge. Pe de alta parte, daca nodurile care se doresc a fi conectate se afla in aceeasi camera, aceeasi cladire sau chiar in acelasi site (ex. un campus universitar) atunci se poate cumpara un cablu si se poate realiza legatura fizica intre noduri. (Uneori este nevoie de o oarecare asistenta, dar implementarea unei asemenea legaturi este de domeniul posibilului.) Tipul de cablu care urmeaza a fi folosit depinde de tehnologia caer va fi folodita pentru transmiterea datelor prin legatura; pe parcursul acestei lucrari vor fi date numeroase exemple. Pentru moment, tabelul 1 prezinta o lista a tipurilor de cablu (fibra) folosite curent.

Tip cablu	Largimi de banda si distante specifice
Bifilat torsadat de categoria 5 Coaxial ThinNet ThickNet coaxial Fibra multimod Fibra monomod	10-100 Mbps, 100 metri 10-100 Mbps, 200 metri 10-100 Mbps, 200 metri 100 Mbps, 2 km 100-2400 Mbps, 40 km

Tabelul 1. Tipuri comune de cablu si fibra disponibile pentru legaturi locale

Pe de alta parte, daca cele doua noduri care se doreste a fi conectate se afla la mari distante georafice, sau chiar in parti diferite ale unui oras, se recomanda ca utilizatorul sa nu instaleze el insusi legatura. Unica optiune o reprezinta inchirierea unei legaturi de la compania de telefoane, caz in care tot ce aveti de facut este sa purtati o conversatie inteligenta cu reprezentantul de relatii cu clientii al companiei. Tableul 2 prezinta servicii asigurate de compania de telefoane. Din nou, alte detalii vor fi oferite pe parcursul acestei lucrari.

Serviciu	Largimi de banda
ISDN T1 T3 STS-1 STS-3 STS-12 STS-24 STS-48	64 Kbps 1,544 Mbps 44,736 Mbps 51,840 Mbps 155,250 Mbps 622,080 Mbps 1,244160 Gbps 2,488320 Gbps

Tabelul 2. Largimi de banda comune disponibile de la purtatori

Desi aceste largimi de banda par oarecum arbitrar, in toata aceasta babilonie exista totusi un dram de ordine. Mai intai, capacitatea de 64 Kbps a ISDN (retea digitala pentru servicii integrate) a fost selectata deoarece reprezinta largimea de banda folosita frecvent pentru transmiterea divoce digitizata, iar unul dintre scopurile ISDN este de a putea manipula atat voce, cat si date. (Un serviciu care codifica un semnal analog de tip voce intr-o legatura ISDN digitala se numeste CODEC, de la codor/decodor.) In al doilea rind, T1 si T3 sunt tehnologii relativ vechi, definite pentru medii de transmisie pe baza de cupru. T1 este egala cu alaturearea a 24 de circuite digitale de voce iar T3 esdte egala cu 30 de legaturi tip T1. In final, toate legaturile de tip STS-N sunt destinate fibrei optice (STS este abreviera de la Synchronous Transport Signal – semnal sincron de transport). STS-1 este viteza de baza a legaturii iar fiecare STS-N are o largime de banda egala de N ori largimea lui STS-1. O legatura STS-N este deseori denumita legatura OC-N (OC este abrvierea de al optical carrier – purtator optic). Diferenta dintre STS si OC este subtila; prima se refera la transmisia electrica pe dispozitivele conectate la legatura, iar ultima desemneaza semnalul optic efectiv care este propagat prin fibra.

Toate leagturile de mai sus sunt digitale, nu analogice. De asemnea, cu exceptia legaturii ISDN, acestea sunt de asemenea inchiriate ca linii dedicate, ceea ce inseamna ca linia este intotdeauna disponibila; nu este necesara stabilirea telefonica a unei conexiuni inainte de a o utiliza. (De fapt este posibila utilizarea unei conexiuni T1 stabilita telefonic, dar T1 este de obicei inchiriata ca linie dedicata.) Alternativa, desigur, este de a folosi un modem pentru a transmite datele binare prin intermediul unei linii telefonice conventionale, obtinuta prin solicitarea telefonica. Desi tehnologia modemurilor analogice a cunoscut o puternica dezvoltare in ultimii ani – un modem de 28 Kbps costa numai catva sute de dolari – aceasta tehnologie are un potential limitat si nu sunt de prevazut dezvoltari ulterioare.

Trebuie retinut faptul ca compania de telefoane nu implementeaza “legatura“ proaspat comandata printr-o singura portiune , neintrerupta de cablu sau fibra optica. Legatura eset implementata pe propria sa retea. Desi compania de telefoane a avut un aspect mult diferit de tipul de retea descrisa in aceasta lucrare, fiind conceputa special pentru a furniza un serviciu de voce, folosind tehnologia comutatiei de circuite si bazindu-se pa legaturi analogice – tendinta curenta de adoptare a stilului de retea descris in aceasta lucrare, mai exact a modului de transfer asincron (Asynchronous Transfer Mode – ATM). Aceasta nu trebuie sa surprinda – piata potentiala pentru transferul de date, voce si imagini este imensa.

In orice caz, indeferent daca legatura este o conexiune fizica sau logica prin intermediul retelei telefonice, problema alcatuirii unei retele de calculatoare pornind de la aceste legaturi nu se schmba. Astfel, vom proceda ca si cum fiecare lagatura este implementata de un singur cablu sau de o singura fibra, si numai la final ne vom pune problema daca am construit o retea pe baza retelei telfonice existente sau daca reteaua de calculatoare constituita serveste ea inasasi drept coloana vertebrala pentru reteaua telefonica.

2. Tehnici de codificare (NRZ, NRZI, Manchester, 4B/5B)

Prima etapa in transformarea nodurilor si a legaturilor in elemente constructive utilizabile o reprezinta intelegerea modului de conectare a acestora de asa maniera incat bitii sa poata fi transmisi de la un nod la altul. Dupa cum s-a aratat in sectiunea anterioara, semnalele se propaga prin legaturi fizice. Ca atare, este necesara codificarea datelor pe care nodul sursa doreste sa le transmita in semnale pe care legaturile sunt capabile sa le transporte, iar apoi decodificarea semnalului in datele binare corespunzatoare, la nodul receptor. Vom discuta aceasta problema in contextul unei legaturi, in care caz vom lucra cu doua semnale discrete. Pe acestea le vom desemna in mod generic ca semnal inalt si semnal redus, desi in practica aceste semnale sunt doua tensiuni diferite pe o legatura pe baza de cupru si doua nivele de putere diferite pe o legatura optica.

Asa cum am spus, majoritatea functiilor discutate in aceasta lucrare sunt executate de un adaptor de retea – adica o componenta hardware care conecteaza o legatura la un nod. Adaptorul de retea conecteaza o componenta semnal care codifica bitii in semnale la nodul emitator si decodifica semnalele in biti la nodul receptor. Astfel, asa cum s-a aratat in figura 2, semnalele parcurg legatura intre doua componente semnal, iar bitii sunt transmisi intre adaptoarele de retea.

Adaptor

 

Nod

Figura 2.

Semnalele calatoresc intre componentele de scmnalizare iar bitii se deplaseaza intre adaptori

Sa revenim la problema codificarii bitilor in semnale. In mod evident, valoarea 1 trebuie atribuita semnalului inalt, iar valoarea 0 semnalului redus. Aceasta reprezinta exact transpunerea folosita de catre o schema de codificare denumita – intr-un mod destul de criptic – fara revenire la zero (non-return to zero - NRZ). De exemplu, figura 3 determina schematic semnalul codat cu NRZ (partea de jos) care corespunde unei transmisii a unei anumite secvente de biti (partea de sus).

Biti 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0 NRZ

Figura 3. Codarea de tip NRZ a unui flux de biti

Problema NRZ este aceea ca o secventa de mai multe valori 1 consecutive inseamna ca semnalul ramane la valori ridicate pentru o perioada prelungita de timp; similar, mai multe valori de 0 succesive semnifica faptul ca semnalul ia valoarea redusa pentru o periada indelungata de timp. Exista mai multe probleme determinate de siruri lungi de 1 sau de 0. Mai intai, un semnal 0 prelungit poate corespunde, in realitate, absentei unui semnal. Astfel, receptorul nu poate distinge intre un sir prelungit de zerouri si o legatura “moarta”. In al doilea rand, un semnal inalt prelungit poate deruta receptorul, deoarece acesta foloseste nivelul mediu al semnalului, denumit baseline, pentru a distinge intre semnalul inalt si cel redus. Prea multi de 1 consecutivi determina modificarea acestei valori medii, situatia cunoscuta sub numele de oscilatia liniei medii. In al treilea rand, tranzitiile frecvente de la mare la mic si invers sunt necesare pentru a permite restabilirea ceasului, asa cum se descrie mai jos.

Intuitiv, problema restabilirii ceasului este aceea ca atat procesul de codare, cat si cel de decodare sunt controlate de un ceas – un ciclu complet fiind alcatuit din transmiterea si receptia unui bit. Ceasurile emitatorului si al receptorului trebuie sa fie precis sincronizate, pentru ca receptorul sa recupereze aceiasi biti ca aceia trimisi de emitator. Daca ceasul receptorului este imperceptibil mai rapid sau mai lent decat acel al emitatorului atunci semnalul nu este corect decodat. Se poate imagina transmiterea ceasului catre receptor pe un cablu separat, dar procedeul este evitat datorita dublarii pretului la cablaj. Receptorul, in schimb, va deriva ceasul din semnalul receptionat – adica procesul de recuperare a ceasului. La fiecare modificare de semnal, cum ar fi o tranzitie de la 1 la 0 sau invers, receptorul stie ca este vorba de incheierea unui ciclu de ceas si se poate resincroniza. Cu toate acestea , o perioada lunga de timp care nu contine o asemenea tranzitie poate determina devieri ale ceasului. Astfel, recuperarea ceasului depinde de existenta unui mare numar de tranzitii in semnal, indiferent de datele transmise.

Una dintre metodele care rezolva aceasta problema, denumita codare fara revenire la zero inversata (non-return to zero inverted - NRZI ), determina emitatorul sa execute o tranzitie de la semnalul curent pentru a codifica 1 si de a ramanane la semnalul curent pentru a codifica 0. Aceasta rezolva problema sirurilor de 1, dar evident nu are nici un efect la sirurile de 0. NRZI este ilustrata in figura 4. O alternativa, denumita codarea Manchester [t t] , combina ceasul cu semnalul intr-un mod mai explicit, prin transmiterea functiei SAU EXCLUSIV a datelor codate cu NRZ si a ceasului. (Sa ne gandim la ceasul local ca la un semnal intern care alterneaza de la mic la mare; o pereche mic/mare este considerata un ciclu de ceas.) Codificarea Manchester este de asemenea prezentata in figura 4. Observati ca prin codarea Mancheter un 0 ste codificat ca o tranzitie mic-mare, iar 1 este codificat ca o tranzitie in sens invers. Deoarece atat 1, cat si 0 determina o tranzitie a semnalului, ceasul poate fi recuperat in mod eficient de catre receptor.

Dezavantajul schemei de codare de tip Manchester este aceea ca dubleaza viteza de executare a tranzitiilor de semnal pe legatura, ceea ce inseamna ca receptorul are la dispozitie jumatate de timp pentru a detecta fiecare impuls al semnalului. Viteza de modificare a semnalului se numeste viteza de baud a legaturii. In cazul codarii de tip Manchester, rata de biti este jumatate din viteza de baud, deci codificarea are o eficienta de numai 50%. Trebuie retinut ca daca receptorul ar fi fost capabil sa “tina pasul” cu viteza de baud superioara impusa de codarea Manchester prezentata in figura 4, atunci atat NRZ cat si NRZI ar fi fost capabile sa trasmita un numar dublu de biti in acelasi interval de timp.

Biti 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 0

NRZ

Ceas

Manchester

NRZI

Figura 4. Diferite strategii de codare

Ultima schema de codare pe care o vom lua in consideratie denumita 4B/5B, incearca sa rezolve ineficienta codarii de tip Manchester, fara a suferi de problema extinderii duratei semnalelor de amplitudine mare sau mica. Ideea metodei 4B/5B este de insera biti suplimentari in fluxul de biti pentru a intrerupe secventele lungi de 1 sau 0. Concret, fiecare 4 biti de date sunt codati intr-o secventa de 5 biti care este transmisa apoi receptorului; de aici si numele 4B/5B. Codurile 4B/5B sunt astfel selectate incat nici unul nu are mai mult de un 0 in fata si in spate. Astfel, cand sunt transmise spate in spate, nici o pereche de coduri pe 5 biti nu determina mai mult de trei zerouri consecutive. Codurile pe 5 biti rezultante sunt apoi tramsmise folosind codarea NRZI, care explica faptul de ce codul trateaza numai problema zerourilor consecutive; deoarece NRZI a rezolvat deja problema sirurilor de 1. Se retine ca schema de codare 4B/5Bare o eficienta de 80%.

Tabelul 3 prezinta codurile pe 5 biti care corespund fiecaruia dintre simbolurile posibile de date pe 4 biti. Se observa ca, deoarece 5 biti sunt suficienti pentru a coda 32 de coduri diferite, iar noi folosim numai 16 dintre acestia pentru date, reiese ca avem la dispozitie 16 coduri pentru alte scopuri. Din acestea, codul 11111 este folosit cand linia este inactiva, codul 00000 corespunde unei linii “moarte”, iar 00100 semnifica oprire. Din cele 13 coduri ramase, 7 sunt invalide deoarece incalca regula “un 0 in fata, doua in spate”, iar celelalte 6 reprezinta diverse simboluri de control. Dupa cum vom vedea in aceasta lucrare, unele protocoale de incadrare (ex. FDDI) folosesc aceste simboluri de control.

Tabelul 3. Codarea 4B/5B

3. Incadrarea

Acum, din moment ce se cunoaste modul de transmitere a unei secvente de biti printr-o legatura punct-la-punct, de la un adaptor la altul, sa discutam despre scenariul perzentat in figura 5. Adaptorul de retea este cel care permite nodurilor sa efectueze schimb de cadre.Cand nodul A doreste sa transmita un cadru catre nodul B, adaptorul nodului A primeste indicatia de a transmite un cadru din memoria sa. Aceasta are ca rezultat o secventa de biti care sunt transmisi prin legatura. Adaptorul din nodul B aduna apoi secventa de biti care soseste pe legatura si depoziteaza cadrul corespunzator in memoria lui B. Recunoasterea exacta a acelui set de biti care alcatuieste un cadru – cu alte cuvinte, determinarea punctului initial si al celui final al unui cadru – reprezinta principala problema pe care trebuie sa rezolve un adaptor.

Exista multiple modalitati de a rezolva problema incadrarii. Acesta sectiune foloseste mai multe protocoale diferite pentru a ilustra diferitele ascpecte din spatiul de proiectare. Se va retine ca desi se discuta despre cadre in contextul legaturilor punct-la-punct, problema are un caracter fundamental si trebuie rezolvata si in retelele cu acces multiplu, cum sunt CSMA si inelul jeton.

Adaptor

3.1 Protocoale orientate pe byte (BISYNC, IMP-IMP, DDCMP)

Una dintre primele abordari ale problemei incadrarii, ale carei inceputuri pornesc de la conectarea terminalelor la calculatoarele mainframe, o reprezinta vizualizarea fiecarui cadru ca pe o colectie de bytes (caractere) si nu ca pe o colctie de biti. O asemenea metoda orientata pe byte este exemplificata prin protocoalele: BISYNC (Binary Syncronous Communication – comunicare binara sincrona), creat de IBM la sfarsitul anilor `60; DDCMP (Digital Data Communication Message Protocol – protocol tip mesaj pentru comunicarea datelor digitale) folosit in reteaua DECNET a corporatiei Digital Equipment, si IMP – IMP, folosit in versiunea originala a ARPANET. (IMP abreviaza sintagma Intreface Message Processor – procesor tip mesaj pentru interfete, adica denumirea originala a nodurilor cu comutatie de pachete din ARPANET.) Uneori aceste protocoale presupun un anumit set de caractere – de ex., BISYNC admite ASCII, EBCDIC si Transcode pe 6 biti de la IBM – dar acest aspect nu trebuie generalizat.

Desi similare din multe aspecte, aceste trei protocoale pot fi definite ca folosind doua tehnici diferite de incadrare: metoda santinelei si cea a numararii de bytes.

Metoda santinelei

Protocoalele BISYNC si IMP-IMP folosesc metoda santinelei pentru incadrare; formatele de cadru aferente fiecaruia sunt prezentate respectiv in figurile 6 si 7. Aceste figuri sunt primele dintre multele de acest gen care vor aparea in lucrare, folosite pentru a ilustra formate de cadre sau de pachete, astfel incat se impun cateva explicatii. Un pachet este prezentat sub forma unor campuri de secvente. Deasupra fiecarui camp se afla un numar care indica lungimea acelui camp in biti. Se va retine ca pachetele sunt transmise incepand cu primul camp din stanga.

			8

Figura 6. Formatul de cadre BISYNC

Figura 7. Formatul de cadre IMP-IMP

Atat la protocolul BISYNC, cat si la IMP-IMP, inceptul unui cadru este semnalat prin trimiterea unui caracter special de sincronizare SYN. Portiunea de date a unui cadru este apoi inclusa intre caractere de delimitare speciale. La protocolul BISYNC, caracterele STX (start-of-text, inceputul textului), respectiv ETX (end-of-text, sfarsitul textului) sutn cele care limiteaza portiunea de date, in timp ce la protocolul IMP-IMP, caracterele omogene sunt DLE/ETX, unde DLE reprezinta abrevierea de la data-link-escape. Campul SOH (strat of header, inceputul antetului) are oarecum aceeasi semnificatie ca si campul STX.

Problema cu caracterele de delimitare este aceea ca in portiunea de date a cadrului poate aparea caracterul ETX, BISYNC rezolva problema prin procedura caracterului ETX printr-un caracter DLE la fiecare aparitie a acestuia in corpul unui cadru; caracterul DLE este de asemenea precedat prin alt caracter DLE in corpul cadrului. (Programatorii in C pot observa ca aceasta metoda este similara cu modul de evitarea a unui semn de citare la aparitia acestuia intr-un sir, prin intermediul unui caracter backslash.) Deoarece protocolul IMP-IMP deja insereaza DLE anterior caracterelor ETX si STX la extremitatile cadrului, este necesara numai evitarea caracterului DLE in corpul cadrului.

Ambele formate de cadru includ un camp (etichetat CRC, abreviere de la cyclic redundancy check – control ciclic prin redundanta care este folosit pentru detedtia erorilor de transmisie; diferiti algoritmi pentru detectia erorilor sunt prezentati in sectiunea 4. De asemenea, ambele formate includ spatiu pentru informatii suplimentare legate de antet. Aceste informatii sunt folosite, printre alte scopuri, la algoritmul fiabil de livrare a datelor la nivel de legatura (link-level reliable delivery algorithm). Exemple al acestor algoritmi sunt prezentate in sectiunea 5.

Metoda prin numarare de bytes

Dupa cum o stie fiecare student la atomatica, alternativa detectiei sfarsitului unui fisier cu o valoare de delimitare este de a include numarul de articole incluse in fisier la inceputul acestuia. Acelasi lucru este valabil si in cazul cadrelor, in sensul ca numarul de bytes inclus intr-un cadru poate fi inclus drept camp in antetul cadrului. Protocolul DDCMP folosit in reteaua DEKNET foloseste aceasta metoda, asa cum este prezentata in figura 8. In acest exemplu, campul COUNT indica numarul de bytes inclusi in corpul cadrului.

			42

Figura 8. Formatul de cadre

Figura 9. Formatul de cadre HDLC

Unul dintre riscurile utilizarii acestei metode rezida in aceea ca o eroare de transmisie poate altera campul COUNT, caz in care sfarsitul cadrului nu va fi detectat in mod corect. (O problema similara exista la metoda bazata pe caractere de delimitare, daca se altereaza campul ETX.) In cazul unei erori, receptorul va acumula numarul de bytes indicat de campul COUNT alterat si apoi va folosi campul de detectie a erorilor pentru a determina faptul ca respectivul cadru este alterat. Aceasta se numeste, uneori, eroare de incadrare. Receptorul va astepta pana la aparitia urmatorului caracter SYN si va incepe colectarea bytes-ilor care alcatuiesc cadrul urmator. Ca atare, este posibil ca o eroare de incadrare sa determine receptarea incorecta a unor cadre trimise spate in spate.

3.2 Protocoale orientate pe biti (HDLC)

Spre deosebire de protocoalele orientate pe byte, un protocol orientat pe bit nu are de a face cu limitele unui byte, ci pur si simplu “vede” un cadru ca pe o colectie de biti. Acesti biti pot proveni dintr-un det de caractere, cum ar fi ASCII, sau pot fi valorile unui pixel intr-o imagine, sau instructiuni sau operanzi intr-un fisier executabil. Protocolul Synchronous Data Link Control (SDLC) creat de IBM este un exeplu de protocol orientat pe bit; SDLC a fost standardizat ulterior de catre OSI sub numele de High-Level Data Link Control (HDLC). Protocolul PPP (Point-to-Point Protocol) este similar cu HDLC. In continuare, vom folosi HDLC drept exemplu, iar formatul sau de cadru este prezentat in figura 9.

HDLC noteaza atat inceputul, cat si sfarsitul unui cadru prin secventa de biti 01111110. Aceasta secventa este de asemenea transmisa pe toata durata inactivitatii conexiunii, pentru a perite sincronizare ceasurilor de la emitator si receptor. Astfel, ambele protocoale folosesc, in esenta, metoda cu caractere de delimitare. Deoarece aceasta secventa poate aparea oriunde in corpul cadrului – de fapt, bitii 01111110 pot depasi imaginea unui byte – protocoalele orientate pe bit folosesc anaogul caracterului DLE, o tehnica numita umplere cu biti (bit stuffing).

Metoda umplerii cu biti in cadrul protocolului HDLC este prezentata in continuare. La emitator, la fiecare transmitere a cinci de 1 consecutivi in corpul mesajului excluzand cazul in care emitatorul doreste sa transmita secventa de biti 01111110), acesta insereaza un 0 inainte de a trimite bitul urmator. La receptor, la sosirea a cinci de 1 consecutivi, acesta ia o decizie in functie de urmatorul bit care soseste (adica bitul urmator celor cinci de 1). Daca urmatorul bit este un 1, atunci exista doua posibilitati: fie acesta este delimitatorul de sfarsit de cadru, fie in fluul de biti a aparut o eroare. Prin consultarea bitului urmator , receptorul poate face distinctia intre cele doua cazuri; daca vede un 0 (adica ultimii opt biti consultati sunt 01111110) atunci este vorba de delimitatorul de sfarsit de cadru; daca vede un 1 (adica ultimii opt biti consultati sunt 011111111), atunci a aparut o eroare si cadrul este ignorat in totalitate. In ultimul caz, receptorul trebuie sa astepte urmatoarea secventa 01111110 inainte de a putea incepe sa receptioneze din nou, si in consecinta este posibil ca receptorul sa nu reuseasca sa primeasca doua cadre consecutive. Evident, exista modalitati prin care erorile de incadrare pot scapa nedetectate, cum ar fi generarea unui intreg model de sfarsit de cadru cu erori, dar aceste erori sunt putin probabile. Modalitati robuste de detectie a erorilor sunt prezentate in sectiunea 4.

O caracteristica interesanta a metodei umplerii cu biti, ca si aceea a ignorarii valorilor de delimitare aparute in corpul mesajului, este aceea ca dimensiunea unui cadru este dependenta de datele transmise in cadru. In realitate , obtinerea de cadre de aceeasi dimensiune este imposibila, datorita caracterului arbitrar al datelor care trebuie transportate in acelasi cadru. (Pentru a va convinge de aceasta, ganditi-va la ce se poate intampla cand ultimul byte al corpului unui cadru este caracterul ETX). O forma de incadrare care asigura aceeasi dimensiune pentru toate cadrele este descrisa in subsectiunea ulterioara.

3.3 Incadrarea bazata pe ceas (SONET)

O atreia metoda de obtinerea cadrelor este exemplificata de standardul Synchronous Optical Network (SONET). Din lipsa unui termen generic acceptat, vom denumi aceasta metoda incadrarea bazata pe ceas. SONET a fost propus pentru prima data de catre Vell Communications Research (Bellcore) si apoi dezvoltat sub egida Institutului National Pentru Standarde al SUA (ANSI) pentru transmisie digitala pe fibra optica; de atunci a fost adoptata de catre ITU-TI. Cine si cand a standardizat ceva nu este problema cea mai importanta. Ce trbuie retinut despre SONET este ca defineste modul de transmitere a datelor prin retelele cu fibra optica de catre companiile telefonice.

Un aspect important care trebuie cunoscut relativ la SONET inainte de a trece mai departe este ca speificatia completa a acestuia este substantial mai mare decat aceasta lucrare. Astfel, discutia urmatoare se va referi numai la elementele principale ale standardului. De asemena, SONEt rezolva atat problema cadrelor, cat si pe cea a codarii. De asemenea, trateaza o problema foarte imporanta pentru companiile, in speta multiplexarea mai multor legaturi de viteza redusa intr-o legatura de viteza ridicata. Vom incepe cu problema cadrelor, iar despre celelalte aspecte vom discuta in continuare.

Ca si in cazull schemelor de incadrare discutate nterior, un cadru SONET contine o informatie de natura mai speciala, care indica receptorului locatia de inceput si de final a cadrului. Asemanarile se opresc insa aici. Trebuie remarcat ca nu se foloseste metoda umplerii cu biti, astfel ca lungimea unui cadru nu depinde de datele trimise. Deci se pune intrebarea: cum afla receptorul care sunt locatiile de inceput si de final ale fiecarui cadru? Sa luam in considerare aceasta intrebare pentru legatura de tip SONET cu viteza cea mai mica, cunoscuta sub numele de STS-1 si ruleaza la 51 Mbps. Un cadru STS-1 este prezentat in figura 10. Cadrul este aranjat sub forma de 9 randuri a cate 90 de bytes fiecare, iar primii trei bytes din fiecare rand reprezinta suprasarcina, iar restul este disponibil pentru datele trimise prin legatura. Primii doi bytes ai cadrului contin un model de biti specia, acesti biti fiind cei care permit receptorului sa determine punctul de inceput al cadrului. Pentru a preveni aceasta, receptorul cauta in permanenta modelul special de biti, sperand sa-l vada aparand o data la fiecare 810 bytes, din moment ce fiecare cadru are o lungime de 9*90=810 bytes. Cand modelul special apare la locul potrivit de un numar suficient de ori, receptorul considera ca este sincronizat si va interpreta cadrul in mod corect.

Figura 10. Un cadru SONET STS-1

Unul dintre aspectele care nu vor fi descrise din motive de complexitate a SONET este utilizarea detaliata a tuturor celorlalti bytes de suprasarcina. Parte din aceasta complexitate poate fi atribuita faptului faptului ca SONET ruleaza pe reteaua optica a purtatorului, nu numai pe o simpla legatura. (Sa ne reamintim ca am pornit de la faptul ca purtatorii sunt cei care implementeaza o retea si ne concentram asupra aspectului ca putem inchiria o legatura sonet de la acestia si apoi putem folosi legatura respectiva pentru a ne construi propria retea cu comutatie de pachete.) O complexitate aditionala provine din aceea ca SONET asigura un set considerabil mai divers de servicii in afara transferului de date. De exemplu, 64 Kbps din capacitatea unei legaturi SONET este rezervata pentru un canal de voce folosit la intretinere.

Bytes-ii de suprasarcina ai unui cadru SONET sunt codati folosind NRZ, adica schema de codare simpla descrisa in sectiunea anterioara, unde 1 reprezinta mare si 0 reprezinta mic. Cu toate acestea, pentru a fi siguri ca exista suficiente tranzitii pentru a permite receptorului sa recupereze ceasul emitatorului, bytes-ii de date sunt disipati (scrambled). Aceasta se rezolva aplicand SAU EXCLUSIV datelor care urmeaza a fi transmise si prin utilizarea unui model de biti dedicat. Modelul de biti, lung de 127 de biti, contine destule tranzitii de la 1 la 0, astfel ca efectuarea unui XOR intre acesta si datele transmise va genera un semnal cu suficiente tranzitii pentru a permite recuperarea ceasului.

SONET admite multiplexarea de legaturi de viteza redusa, intr-o modalitate ce va fi descrisa in continuare. O legatura SONET data ruleaza la o viteza extrasa dintr-o multime prestabilita, care variaza intre 51 Mbps (STS-1) la 2488,32 Mbps (STS-48) si chiar mai mult. (Vezi tabelul 2 din sectiunea 1 pentru un set complet de viteze SONET de transmisie a datelor.) Se observa ca toate aceste viteze sunt multipli intregi de STS-1. Semnificatia incadrarii estee aceea ca un singur cadru SONET poate contine subcadre pentru mutiple canale cu rate mai reduse. O a doua facilitate este aceea ca fiecare cadru are lungimea de 125ms. Aceasta inseamna ca, la viteza canalului STS-1, un cadru SONET are 810 bytes, in timp ce la viteze tipice STS-3, fiecare cadru SONET are 2430 bytes. Se observa sinergia dintre cele doua caracteristici: 3*810=2430, ceea ce semnifica faptul ca trei cadre STS-1 se incadreaza exact intr-un cadru STS-3.

Intuitiv, cadrul STS-N poate fi asimilat ca fiind compus din N cadre STS-1, unde bytes-ii din aceste cadre sunt intercalati; cu alte cuvinte, se transmite un byte din primul cadru, dupa care se transmite un byte din al doilea cadru etc. Motivul perntru intercalarea bytes-ilor din fiecare cadru STS-1 este asigurarea faptului ca bytes-ii din fiecare cadru STS-1 sunt transmisi periodic, cu alte cuvinte acestia ajung la receptor cu o rata de 51 Mbps, in loc de o gramada care ajung la o anumita fractiune 1/N din intervalul de 125 ms.

Desi este corecta vizualizarea unui semnal STS-N ca utilizat pentru multiplexarea a N cadre STS-1, datele din aceste cadre STS-1 pot fi legate pentru a forma un STS-N cu o incarcatura mai mare; o asemenea legatura este notata STS-Nc (de la concatenat). Unul din campurile din suprasarcina este folosit in acest scop. Figura 11 prezinta schematic operatia de concatenare in cazul a trei cadre STS-1 concatenate intr-un singur cadru STS-3c. Semnificatia unei legaturi SONET sub forma STS-3c si nu STS-3 este aceea ca, in primul caz, utilizatorul legaturii o vizualizeaza ca pe un singur pipe de 155,25 Mbps, in timp ce un STS-3 trebuie vizualizat sub forma a trei legaturi de 51, 84 Mbps care partajeaza o fibra.

In final, descrierea precedenta a SONET-ului este excesiv de simplista in sensul ca se presupunea faptul ca sarcina pentru fiecare cadru este complet inclusa in cadrul respectiv. (De ce n-ar fi?) De fapt, cadrul STS-1 descris anterior poate fi asimilat unui inlocuitor al cadrului, unde incarcatura efectiva poate glisa intre limitele cadrului. Aceasta situatie este ilustrata in figura 12. Aici se poate vedea atat incarcatura unui cadru STS-1 glisand intre doua cadre STS-1, cat si faptul ca incarcatura a deplasat un numar de bytes la dreapta, determinind astfel infasurarea acestora. Unul dintre campurile de supraincarcare indica spre inceputul zonei de incarcatura. Valoarea acestei capabilitati este aceea ca simplifica operatia de sincronizare a ceasurilor folosite in retelele purtatorilor, sincronizare ce consuma o mare parte din activitatea purtatorilor.

Figura 11. Trei cadre STS-1 multiplexate intr-un singur cadru STS-3c

					8761

Figura 12. Cadre SONET decalate

4. Detectia erorilor

Dupa cum s-a aratat, erorile de biti apar deseori introduse in cadre. Aceasta se intampla de obicei datorita interferentei electrice sau a zgomotului termic. Desi erorile sunt rare, in special in mediile cu fibra optica, este necesar un mecanism pentru detectiei acesteia, in vederea luarii unor masuri de corectare. Astfel, utilizatorul va sfarsi prin a se intreba de ce programul C compilat cu succes cu un minut in urma a capata o eroare de sintaxa, din moment ce unica actiune petrecuta in acest interval a constat in copierea programului intr-ujn sistem de fisiere de retea.

Tehnicile de tratare a erorilor de bit in sistemele de prelucrare a datelor au o intrega istorie, care incepe de la codurile Hamming si Reed/Solomon, create la stocarea adtelor pe disc magnetic si in primele tipuri de memorie cu miez. In materie de retele de calculatoare, metoda dominanta o constituie o tehnica cunoscuta sub numele de control ciclic prin redundanta (cyclic redundancy check – CRC). Este folosita in aproape toate protocoalele de nivel legatura discutate in sectiunea anterioara – ex. IMP-IMP, HDLC, DDCMP, precum si protocoalele CSMA si inelul cu jeton, descrise ulterior in aceasta lucrare. Aceasta sectiune va prezenta algoritmul CRC de baza. De asemenea, sunt prezentate si alte metode de detectie la erori – paritatea bidimensionala si sumele de verificare. Prima este folosita de catre prtocolul BISYNC la transmiterea caracterelor ASCII (CRC este folodit drept cod de eroare cand BISYNC este folosit pentru transmiterea codului EBCDIC), iar ultimul este folosit de mai multe protocoale internet.

4.1 Controlul ciclic prin redundanta

Ideea de baza a oricarei scheme de detectie a erorilor consta in inserarea de informatii redundante la un cadru, informatie care poate fi folosita pentru detectarea eventualelor erori. La extrem, se poate imagina transmiterea a doua seturi complete de date. Daca cele doua copii sunt identice la receptor, atunci probabil ca ambele sunt corecte. Daca exista diferente, atunci eroarea a aparut in una dintre cele doua copii, sau in amandoua, caz in care treebuie elimnate. Din fericire, exista alternative mai bune decat a transmite n biti de redundanta pentru un mesaj de n biti. In general, trebuie transmisi doar k biti de redundanta pentru un mesaj de n biti, unde k<<n. Pe un Ethernet, de exemplu, un cadru care transmorta cel mult 12.000 de biti (1500 bytes) de date necesita un CRC de numai 32 biti sau, asa cum se spune, foloseste un CRC-32. Un asemenea cod va depista majoritatea cavarsitoare a erorilor, asa cum se va vedea in continuare.

Cu numai 32 de biti nu se poate realiza o detectie rezonabila a erorilor intr-un mesaj de 12.000 de biti in absenta un solid aparat matematic. In acest caz, fundatia teoretica a controlului ciclic al redundantei se regaseste in campurile finite. Despre erorile detectate de CRC vom discuta ulterior; pentru moment, ne intereseaza numai mecanica algoritmului CRC. Pentru inceput sa ne gandim la un mesaj de n biti ca fiind reprezentat printr-un polinom de grad n-1, unde valoarea fiecarui bit (0 sau 1) este coeficientul pentru fiecare termen din polinom. De ex., un mesaj care contine bitii 10011010 corespunde polinomului M(x x⁷+x⁴+x³+x¹. De asemenea, fie k gradul unui divizor al polinomului C(x). De ex., sa presupunem ca C(x x³+x²+1. In acest caz, k=3. Raspunsul la intrebearea “de unde provine C(x)?” este “Dintr-o carte”. Din nou, vom discuta despre acest subiect mai tarziu.

Ceea ce vom face este sa transmitem un polinom care se divide exact cu C(x); polinomul transmis va fi P(x). (in continuare se va prezenta modul de generare a polinomului P(x)). Apoi daca survine vreo eroare, va fi ca si cum un termen eroare E(x) a fost adaugat la P(x). Cand receptorul mesajului imparte (P(x E(x)) la C(x) rezultatul va fi 0 in doua cazuri: E(x) este zero (nu exista erori), sau E(x) se imparte exact la C(x). O alegere inspirata a lui C(x) poate reduce la minimum posibilitatea de aparitie a celui de-al doilea caz, astfel ca se poate trage concluzia ca un rezultat de zero indica absenta erorilor, iar un rezultat diferit de zero semnifica aparitia unei erori.

Cele prezentate in continuare vor fi mai usor de inteles daca se cunosc unele date despre aritmetica polinoamelor, usor diferita de aritmetica numerelor intregi. Mai intai se ia M(x) si se inmulteste cu x^k, pentru a obtine x¹⁰+x⁷+x⁶+x⁴, sau 10011010000 in exemplul nostru. Apoi rezultatul se imparte la C(x), care corespunde in acest caz secventei 1101. Figura 13 preznta impartirea polinomiala. Calculul este similar impartirii intregilor, cu doua diferente: C(x) divide orice polinom B(x) de acelasi grad cu C(x), iar restul este rezultatul operatiei SAU EXCLUSIV intre B(x) si C(x). Astfel, in prima etapa a exemplului nostru, se observa ca C(x), care este 1101 in cazul de fata, divide polinomul 1001 deoarece sunt de acelasi grad si da restul 100 (1101 XOR 1001). Urmatoarea etapa consta in coborarea de cifre din polinomul mesajului pana la obtinerea unui alt polinom de acelasi grad ca si C(x), calcularea din nou a restului si continuarea ciclului pana la incheierea calculului.

Figura 13. Calculul CRC folosind impartirea polinoamelor

Din figura 13 se poate vedea ca restul calculului dat ca exemplu este 101. Deci se stie ca 1001101000 - 101 se divide exact cu C(x) si acesta este mesajul care va fi transmis. Operatia minus in aritmetica polinomiala este operatia logica XOR, astfel ca de fapt se transmite secventa 10011010101. Se observa ca acesta este exact mesajul original, unde restul calculului CRC atasat acestuia. Receptorul imparte polinomul primit P(x C(x) la C(x) si, daca rezultatul este 0, concluzioneaza ca nu au existat erori. Daca rezultatul este diferit de zero, poate fi necesara ignorarea mesajului afectat; cu unele coduri este posibila corectarea unei erori mici (exemplu: daca eroarea a afectat un singur bit). Un cod care permite corectia erorilor se numeste cod corector de erori sau ECC (abreviere de la error-correcting code).

Acum vom lua in considerare problema provenientei polinomului C(x). Intuitiv, ideea este de a selecta acest polinom astfel incat sa nu se imparta exact intr-un polinom al unui mesaj cu erori; cu alte cuvinte, dorim sa ne asiguram ca C(x) nu se imparte exact la polinomul E(x) care reprezinta exact eroarea. De exemplu, o eroare in bitul i poate fi exprimata sub forma E(x xⁱ. Daca se selecteaza C(x) de asa maniera incat primul si ultimul termen sunt diferiti de zero, atunci avem deja doi termeni care nu se pot imparti exact la unicul termen E(x). Un astfel de polinom poate detecta toate erorile de un bit. In general, se pot demonstra urmatoarele propozitii referetoare la erorile care pot fi detectate de catre un C(x) cu proprietatile amintite:

Toate erorile de un bit, daca termenii x⁰ si x^k au coeficienti nenuli.

Toate erorile de doi biti, daca C(x) are un factor de minimum trei termeni.

Orice erori de ordin impar, daca C(x) contine factorul (x+1).

Orice eroare “burst”, adica o secventa de biti eronati amplasati consecutiv, pentru care lungimea burst-ului este mai mica de k biti. (Majoritatea erorilor burst de dimensiuni de k biti pot fi de asemenea detectate.)

In protocoalele de nivel legatura se folosesc 6 versiuni de polinom C(x). Acestea sunt prezentate in tabelul 4. De exemplu, retelele Ethernet si FDDI descrise ulterior in aceasta lucrare folosesc CRC-32, in timp ce HDLC foloseste CRC-CCITT.ATM. In final, sa retinem ca algoritmul CRC, desi complex in aparenta, este usor de implementat in hardware folosind un registru de deplasare de k biti si porti XOR.

4.2 Paritate bidimensionala

Paritatea bidimensionala este exact ceea ce ii sugereaza si numele. In timp ce paritatea simpla implica adaugarea unui bit suplimentar la un cod pe 7 biti pentru a echilibra numarul de cifre 1 din byte – ex. paritatea impara seteaza al optulea bit la 1 daca este necesar un numar impar de 1 in byte, iar paritatea para seteaza al optulea bit la 1 daca este necesara prezenta unui numar par de 1 in byte – paritatea bidimensionala executa o operatie similara pentru fiecare pozitie de bit de-a lungul fiecaruia dintre bytes-ii inclusi in cadru. Aceasta determina un byte supimentar de paritate pentru intregul cadru, in afara de un bit de paritate pentru fiecare byte. Figura 14 prezinta modul de functionare al paritatii bidimensionale pare pentru un cadru care contine sase bytes de date. Trebuie retinut ca al treilea bit al byte-ului de paritate este 1, deoarece exista un numar impar de 1 in al treilea bit de-a lungul celor sase bytes din cadru. Paritatea bidimensionala trateaza toate erorile de 1, 2 si 3 biti, precum si majoritatea erorilor pe 4 biti.

Figura 14. Paritatea bidimensionala

4.3 Algoritmul suma de control Internet

O a treia metoda de contro este exemplificata de catre suma de control internet. Desi nu este folosita la nivelul conexiune, asigura aceeasi categorie de functionalitate ca si CRC s paritatea, deci va fi discutata in continuare. Exemplele de utilizare a acestei metode vor fi prezentate in setiunile 5.2, 6.1 si 6.2.

Ideea care sta la baza sumei de control este foarte simpla; se aduna toate cuvintele transmise si apoi se transmite rezultatul sumei respective. Rezultatul se numeste suma de control. Receptorul executa aceeasi operatie asupra datelor receptionate si compara rezultatul cu suma de control primita. Daca orice ortiune din datele transmise, inclusiv suma de control, este alterata, atunci datele nu vor fi identice si receptorul va sti ca a survenit o eroare. Spre deosebire de CRC-uri, aceasta suma de control nu are proprietati de detectie deosebit de avansate. De exemplu, suma de control nu va detecta nici un fel de erori determinate de dispunerea eronata a cuvintelor.

Pornind de la ideea de baza a sumei de control se pot imagina suficiente variatii. Schema exacta foosita de catre protocoalele Internet este prezentata in continuare. Sa consideram ca datele care trebuie adunate intr-o suma de control se prezinta sub forma unei secvente de intregi pe 16 biti. Datele sunt adunate folosind complimenti fata de 1 pe 16 biti (despre care vom vorbi mai jos) si apoi se ia complimentul fata de 1 al rezultatului. Acel numar pe 16 biti este suma de control. Rutina urmatoare ofera o implementare directa a algoritmului suma de control Internet. Argumentul count contine lungimea lui buf, masurata in unitati de 16 biti. Rutina presupune ca buf a fost deja completat cu zerouri pana la limita celor 16 biti.

u_short

cksum (u_short *buf, int count)

return ~(sum & 0xFFFF);

Acest cod asigura faptul ca este folosita aritmetica complemenului fata de 1, si nu acea a complimentului fata de 2, utilizata in majoritatea sistemelor. In cadrul aritmeticii complementelor fata de 1, complemetul lui x este numarul negativ –x, cu alte cuvinte fiecare bit al lui x este inversat. La adunarea numerleor in cadrul aritmeticii complementelor fata de 1, un transport de la bitul cel mai semnificativ trebuie adaugat la rezultat. Acesta este motivul pentru instructiunea if din cadrul ciclului while.

Motivul peentru utilizarea unui algoritm ca acesta, in ciuda protectiei sale mai reduse impotriva erorilor in comparatie cu un CRC: acest algoritm este mult mai simplu de implementat software. Experienta acumulata in cadrul ARPANET a aratat ca o suma de control de aceasta forma este adecvata. Unul din motive este acela ca suma de control reprezinta ultima solutie de aparare in cazul unui protocol end-to-end; majoritatea erorilor sunt preluate de catre algoritmi de detectie mai puternici, plasati la nivelul legatura.

Un cuvant final asupra expresiei suma de legatura. Se poate observa ca suma de control Internet are o denumire corecta, in sensul ca reprezinta un procedeu de detectie a erorilor care foloseste un algoritm de insumare. Cuvantul suma de control este folosit deseori imprecis pentru a desemna orice forma de cod de detectie a erorilor, inclusiv CRC-urilor. Aceasta poate fi derutant, deci recomandam insistent utilizarea expresiilor suma de control numai pentru codurile care aplica efectiv insumarea, respectiv cod de detectie a erorilor pentru a desemna o clasa generala de coduri descrise in aceasta sectiune.

5. Transmisii fiabile

Dupa cum am vazut in sectiunea anterioara, cadrele sunt uneori alterate in timpul transportului, iar un cod de detectie cum este CRC-ul se foloseste pentru detectia acestor erori. Desi unele coduri de eroare sunt suficient de puternice si pentru corectia erorilor, in practica cele mai savante coduri de corectie a erorilor nu sunt suficient de avansate pentru a trata intregul domeniu de erori de bit si de burst care pot aparea intr-o legatura de retea si, in consecinta, cadrele alterate trebuie ignorate. Un protocol de nivel legatura care doreste sa asigure livrarea sigura a cadrelortrebuie sa recupereze intr-un fel ignorarea sau pierderea acestor cadre.

Aceasta se realizeaza de obicei folsind o combinatie a doua mecanisme fundamentale: confirmarile (acknowledgements) si temporizarile (timeouts). O confirmare (abreviata ACK – de la echivalentul din limba engleza – N.T.) este un mic cadru de control pe care un protocol il trimite inapoi perechii sale prin care ii comunica acesteia ca a primit un cadru anterior. Prin cadru de control se intelege un antet fara nici un fel de date, desi un protocol poate piggyback un ACK pe un cadru de date pe care s-a intamplat sa-l trimita in directia opusa. Primirea unei confirmari indica emitatorului cadrului original ca acel cadru a fost livrat in bune conditii. Daca emitatorul nu primeste o confirmare dupa un interval de timp rezonabil, atunci retransmite cadrul original. Aceasta actiune, de asteptare o anumita perioada de timp, se numeste temporizare.

Strategia generala de utilizare a confirmarilor si a temporizarilor pentru implementarea unei livrari sigure este denumita uneori cerere automata de repetare, de obicei abreviata ARQ (abreviere de la automatic repeat request). Aceasta sectiune descrie trei algoritmi ARQ folosind un limbaj general; cu alte cuvinte, nu vom furniza informatii generale cu privire la campurile antet ale unui anumit protocol.

5.1 Stop-and-Wait

Cea mai simpla schema ARQ este algoritmul stop-and-wait (in traducere stai si asteapta). Ideea algoritmului SAW (abrevierea ne apartine – N.T.) este simpla: dupa transmiterea unui cadru, emitatorul asteapta o confiramare inainte de a transmite cadrul urmator. In cazul in care confirmarea nu soseste dupa o anumita perioada de timp, emitatorul iese din temporizare si retransmite cadrul original.

Figura 15. Diagrama de timp care ilustreaza patru scenarii diferite pentru algoritmul SAW.(a) ACK este primit anterior expirarii timpului; (b) cadrul original se pierde; (c) ACK este pierdut; (d) timpul espira prea repede.

Figura 15 prezinta 4 scenarii diferite care deriva din acest algortm de baza. Aceasta figura este o diagrama de timp, o modalitate comuna de a descrie comportarea unui protocol. Partea emitatoare este prezentata in stanga, partea receptoare in dreapta, iar axa timpului este orientata de sus in jos. Figura 15 (a) prezinta situatia in care ACK este receptionat anterior expirarii de temporizare, (b) si (c) prezinta situatia in care cadrul original si respectiv ACK sunt pierdute iar (d) prezinta situatia in care timpul expira prea repede. Sa ne reamintim ca prin “pierdut” intelegem un cadru pierdut in timpul tranzitului, ca aceasta eroare a fost detectata de catre un cod de eroare la receptor si ca, in conscinta, cadrul a fost ignorat.

Exista o subtilitate importatnta a algoritmului SAW. Sa presupunem ca emitatorul trimite un cadru si ca receptorul il confirma, dar confirmarea este fie pierduta, fie intarziata la sosire. Aceasta situatie este ilustrata in diagramele de timp (c) si (d) din figura 15. in ambele cazuri, emitatorul iese din temporizare si retransmite cadrul original, dar receptorul va crede ca este vorba despre cadrul urmator, deoarece primul cadfru a fost corect primit si confirmat. Astfel exista posibilitatea de a transmite copii ale aceluiasi cadru la destinatar. Pentru a rezolva problema, antetul unui protocol SAW include de obicei un numar de secventa de un bit, adica numarul poate luia una din valorile 0 sau 1 – iar secventele folosite pentru fiecare cadru alterneaza, asa cum se vede in figura 16. astfel, cand emitatorul retransmite cadrul 0, receptorul poate crede ca a primit a doua copie a cadrului 0 in loc de prima copie a cadrului 1 si, ca atare, o poate ignora (receptorul totusi o confirma).

Principalul dezavantaj al algoritmului SAW este acela ca permite emitatorului sa aiba un singur cadru pe o legatura la un moment dat, ceea ce poate fi mai semnificativ mai putin decat capacitatea legaturii. Sa consideram, de exemplu, o legatura de 1,5 Mbps la un RTT de 45 ms. Aceasta legatura are un produs de intirziere x largime de banda egal cu 67,5 Kb, sau aproximativ 8 KB. Deoarece emitatorul poate trimite un singur cadru pe RTT, si presupunind dimensiunea unui cadru de 1 KB, aceasta implica o rata maxima de emisie de 1024*8/0,045=182 Kbps, deci aproximativ 1/8 din capacitatea lagaturii. Pentru a folosi legatura la capacitatea maxima este de preferat ca emitatorul sa fie capabil a transmite maximum 8 cadre inainte de a trebui sa astepte o confirmare.

Figura 17. Diagrama de timp pentru algoritmul tip fereastra gliasnta

5.2 Frestre glisante

Sa ne oprim din nou asupra scenariului in care legatura este caracterizata printr-un produs intirziere * largime de banda de 8 KB, iar cadrele au dimensiune de 1 KB. Se doreste ca emitatorul sa fie gata de a transmite al noulea cadru aproximativ in acelasi moment in care soseste ACK pentru primul cadru. Algoritmul care permite acest lucru se numeste fereastra glisanta, iar diagrama de timp asociata acestuia este prezentata in figura 17 ---fig 17----

Algoritmul tip fereastra glisanta

Modul de functionare al algoritmului tip fereastra glisanta este prezentat in continuare. Mai intai, emitatorul atribuie un numar de secventa, denumit SeqNum, fiecarui cadru. Pentru inceput, sa ignoram faptul ca SeqNum este implementat de catre un camp antet de dimensiune finita, presupunind in schimb ca este infinit de mare. Emitatoruil foloseste trei variabile: dimensiunea ferestrei de transmisie, notata SWS, determina limita superioara a numarului de cadre neconfirmate care pot fi transmise de catre emitator; LAR semnifica numarul de secventa al ultimei confirmari primite, iar LFS simbolizeazea numarul de secventa al ultimului cadru trimis. De asemenea, emitatorul pastreaza urmatoarea inegalitate: LFS – LAR <= SWS. Aceasta situatie este ilustrata in figura 18.

Figura 18. Fereastra glisanta la emitator

La sosirea unei confirmari, emitatorul deplaseaza LAR spre dreapta, permitand astfel emitatorului sa trimita un alt cadru. De asemenea emitatorul asociaza un interval de timp pentru fiecare cadru transmis, si retransmite cadrul daca timpul expira inaintea receptionarii unui ACK. Se observa ca emitatorul trebuie sa fie capabil de a memora in buffer un numar de maximum SWS cadre, deoarece trebuie sa foe gata sa le retransmita pana la primirea confirmarii.

Recepturul foloseste urmatoarele trei variabile: dimensiunea ferestrei de receptie, notata RWS (de la receiving window size), care da limita maxima a numarului de cadre nconfirmate pe care receptorul este dispus sa la accepte; prin RFA (last frame acceptable) se indica numarul de secventa al ultimului cadru acceptabil, iar NFE (next frame expected) desemneaza numarul de secventa al urmatorului cadru acceptat. De asemenea, receptorul pastreaza urmatoarea relatie de invarianta:

LFA – NFE + 1<= RWS.

Aceasta situatie este prezentata in figura 19.

La sosirea unui cadru cu numar de secventa egal cu SeqNum, receptorul procedeaza astfel: daca SeqNum < NFE sau SeqNum > LFA, atunci cadrul se afla in afara ferestrei de receptie si este ignorat. Daca NFE <= SeqNum <= LFA, atunci cadrul se afla in interiorul ferestrei de receptie si este acceptat. Acum, receptorul terbuie sa decida daca sa trimita sau nu un ACK. Fie SeqNumToAck cel mai mare numar de secventa inca neconfirmat, astfel incat toate cadrele cu numere de secventa mai mici decat SeqNumToAck au fost receptionate. Receptorul confirma primirea SeqNumToAck, chiar daca au fost primite pachete cu numere de secventa mai mari. Se spune despre aceasta confirmare ca este cumulativa. Apoi se seteaza NFE = SeqNumToAck +1 si se ajusteaza LFA = SeqNumToAck+RWS.

De exemplu, sa presupunem ca NFE=5 (cu alte cuvinte, ultimul ACK trimis de emitator a fost pentru numarul de secventa 4) si RWS=4. Aceasta implica faptul ca LFS = 9. In cazul in care sosesc cadrele 6 si 7, acestea vor fi memorate in buffer, deoarece se incadreaza in fereastra receptorului. Cu toate acestea, nu trebuie trimis nici un Ack, deoarece cadrul 5 trebuie sa soseasca. Se spune ca cadrele 6 si 7 au sosit in dezordine. (Sub aspect tehnic, erceptorul poate retransmite un ACK pentru cadrul 4 la sosirea cadrelor 6 si 7.) daca soseste cadrul 5 ulterior – poate a fost pierdut prima data si atrebuit sa fie retransmis, sau pur si simplu a fost intirziat – receptorul confirma cadrul 7 , seteaza NFE la 8 si apoi seteaza LFA la 12. daca cadrul 5 este in relitate pierdut, atunci la emitator va survieni o temporizare si cadrul 5 va fi retransmis. Deoarece emitatorul trebuie sa se intoarca cu un anumit numar de cadre (potential egal cu dimensuinea ferestrei), aceata schema este cunoscuta sub numele de go-back-n.

Se observa ca, la aparitia unei erori, cantitatea de date aflate in tranzit scade, deoarece emitatorul este incapabil sa-si deplaseze fereastra pana la confirmarea cadrului 5. Aceasta inseamna ca, la aparitia unor pierderi de pachete, aceasta schema nu mai poate pastra canalul complet ocupat. Cu cat este necesar un interval de timp mai mare pentru a detecta pierderea unui pachet, cu atat problema devine mai serioasa.

Se observa ca in acest exemplu, receptorul ar fi putut trimite o confirmare negativa (NAK) pentru cadrul 5 imediat dupa sosirea cadrului 6. Acest lucru este inutil deoarece mecanismul de temporizare al emitatorului este suficient pentru a trata aceasta situatie, iar trimiterea de semnale NAK adauga un plus de complexitate la receptor. De asemena, asa cum am aratat, ar fi fost corecta transmiterea de confiramri sulimentare pentru cadrul 4 la sosirea cadrelor 6 si 7 ; in unele cazuri, un emitator poate folosi ACK-uri dublate ca un indiciu al pierderii cadrelor. Ambele metode contribuie la imbunatatirea performantelor prin aceea ca permit detectia timpurie a pierderii pachetelor.

O alt avarianta a acestei metode o constituie utilizarea confirmarilor selective. Cu alte cuvinte, receptorul poate confirma exact acele cadre pe care le-a primit, in loc de aconfirma cu numarul cel mai mare, primit in ordine. Deci, in exemplul anterior, receptorul va confirma receptia cadrelor 6 si 7. Furnizarea mai multor informatii catre emitator simplifica sarcina acestuia de a mentine canalul ocupat, dar confera implemenbtarii un plus de complexitate.

Dimensiunea ferestrei la emisie este selectata in functie de numarul de cadre care se doreste sa apara neconfirmate pe legatura la un moment dat; SWS este simplu de calculat pentru produs intarziere * lungime de unda cunoscut. Pe de alta parte receptorul poate atribui lui RWS orice valoare doreste. Doua dintre valorile frecvent folodite sunt RWS=1, ceea ce implica faptul ca receptorul nu va memora in buffer nici un cadru care soseste neconfirmat, respectiv RWS=SWS, ceea ce arata ca receptorul poate memora toate cadrele transmise de emitator.

Numere de secventa finite si ferestre glisante

Acu trebuie sa revenim la singura simplificarea pe care am introdus-o in algoritm – anume presupunearea ca numerele de secventa pot creste la infinit. In practica, desigur, numarul de secventa al unui cadru este specificat intr-un camp antet de o anumita dimensiune finita. De exemplu, un camp de trei biti inseamna ca exista opt numere de secventa posibile, de la 0 la 7. Aceasta impune necesitatea reutilizarii numerelor de secventa sau, cu alte cuvinte, numerele de secventa sunt derulate din nou. Aceasta introduce problema capacitatii de a face distinctia intre diferite aparitii ale acelorasi numere de secventa, ceea ce implica faptul ca numarul de posibile numere de scventa sa fie mai mare decat numarul permis de cadre neconfirmate. De exemplu, algoritmult SAW permitea un singur cadru neconfirmat la un moment dat si avea 2 umere de secventa distincte.

Sa presupunem ca avem un numar in spatiul de numere de secventa in plus fata de numarul potential de cadre neconfirmate; cu alte cuvinte, SWS <= MaxSeqNum – 1, unde MaxSeqNum este numarul de numere de secventa disponibile. Este oare suficient? Raspunsul este negetiv. Pentru a demonstra aceasta, sa luam in considerare situatia in care avem cele 8 numere de secventa de la 0 la 7, iar SWS=RWS=7. Sa presupunem ca emitatorul cadrele 06, aceste sunt receptionate cu succes, dar confirmarile (ACK) se pierd. Acum receptorul transmite cadrele 7, 05, dar emitatorul intra in temporizare si retrimite cadrele 06. din pacate, receptorul asteapta a doua incarnare a cadrelor 05, dar primeste prima incarnare a acestora. Aceasta este exact situatia pe care doream sa o evitam.

Se observa ca dimensiunea ferestrei de transmisie nu poate depasi jumatate din numarul de numere de secventa disponibile cand RWS=SWS sau , mai precis,

SWS<(MaxSeqNum+ 1)/2.

Intuitiv, prin aceasta se intelege faptul ca protocolul tip fereastra glisanta alterneaza intre cele doua jumatati ale spatiului numerelor de secventa, exact cum algoritmul SAW alterneaza intre numerele de secventa 0 si 1. unica diferenta este aceea ca alternanta dintre cele doua jumatati se produce in mod continuu, nu discret.

Implementarea ferestrei glisante

Urmatoarele secvente de cod prezinta rutinele x-nucleu care implementeaza componenta de emisie,respectiv de receptie ale algoritmului tip fereastra glisanta. Aceste rutine sunt preluate dintr-un protocol de lucru al x-nucleului,denumit, suficient de convenabil, Sliding Window Protocol (protocol tip fereastra glisanta, abreviat SWP).

Vom incepe prn a defini o pereche de instructiuni. Mai intii, antetul cadrului este foarte simplu: contine un numar de secventa(SeqNum)si un numar de confirmare(AckNum). De asemenea contineuncimp Flags (indicatoare) care indica daca cadrul este de tip ACK sau este transportor de date.

typedef u_char SwpSeqno;

typedef struct SwpHdr;

In continuare, starea algoritmului tip fereastra glisanta are urmatoarea structura. Pentru partea de emisie a protocolului, aceasta stare include variabilele LAR si LFS,asa cum s-a aratat anterior in aceasta sectiune,precum si o coadacare memoreaza cadre ce au fost transmise, dar inca neconfirmate (txq). Partea de emisie include, de asemenea, un semafor denumit sendWindowNotFull . Vom vedea mai jos modul de utilizare a acestuia.

Pentru partea de receptie a protocolului, stare include variabila NFE,asa cum s-a aratatanterior in aceasta sectiune,plus o coada care memoreaza cadrele primite necomfirmate (rxq). In final, desiaceasta nu se vede, dimensiunile ferestrei glisante de la emitator, respectiv receptor, sunt definite prin

typedef struct txq[SWS] ;

/* receiver side state: */

SwpSeqno NFE; /* seqno of next frame expected */

struct rxq_slot rxq[RWS];

} SwpState;

Prtea de emisie a SWP este implementata de procedura swpPush. Aceasta rutina este destul de simpla. Mai intii, semWait determina blocarea acestiu proces pina in momentul in care se poate transmite cadrul urmator. Odata ce i s-a permis sa actioneze, swpPush seteaza numarul de secventa in antetul cadrului, salveaza o copie a cadrului in coada de emisie,trimite temporizare pentru tratarea cazului in care cadrul nu este confirmat.

Singurul element mai complex in aceasta rutina este utilizarea lui semWait si a semaforului sendWindowNotFull. Acesta este un semafor de numarare care este initializat la dimensiunea ferestrei glisantede emisie (SWS). De fiecare data cind emitatorul trimite un cadru, operatia semWait decrementeaza acest contor si blocheaza emitatorul daca contorul ajunge la 0. la fiecare receptionare a unui Ack, operatia semSignal invocata in swpPOP (vezi mai jos) incrementeaza acest contor, blocind astfel orice emitator aflat in asteptare.

static XkReturn

struct (Sessn s, Msg *msg)

Partea de receptie a SWP este implementata de rutina de x-nucleu swpPOP . Aceasta rutina trateaza de fapt doua tipuri diferite de mesaje receptate: ACK-uri pentru cadre trimise anterior de la acest nod, respectivcadre de date care sosesc la acest nod. Intr-un sens, jumatatea ACK a acestei rutine reprezinta omologul partii de emisie a algoritmului dat in swpPush. O decizie in sensul daca un mesaj receptat este in ACK sau in cadrul de date este luata prin verificarea campului Flags din antet. Se retine ca aceasta implementare particulara nu suporta alipirea particulara de ACK-uri la cadrele de date.

Cind cadrul receptat este un ACK, swpPOP pur si simplu gaseste spatiul din coada de emisie (txq) care corespunde lui ACK si simultan elibereaza cadrul salvat in pozitia respectiva si anuleaza evenimentul de temporizare. De obicei, acesta operatie are loc intr-un ciclu, deoarece ACK poate fi cumulativ. Singurul lucru care trebuie notat fata de acest caz este acela ca numarul de secventa pentru cadrul confirmat se afla in domeniul de ACK-uri pe care emitatorul se asteapta sa le primeasca la un moment dat.

Cind cadrul receptat contine date, swpPop apeleaza mai intii swpInWindow pentru a asigura ca numarul de secventa al cadrului se afla in domeniul de numere de secventa asteptat. In caz afirmativ, rutina cicleaza prin setul de cadre succesive primit si le transfera in sus catre protocolul de nivel imediat superior pri invocarea rutinei xDemux. De asemenea,trimite un ACK cumulativ inapoi la emitator, pri ciclarea prin coada de receptie (nu foloseste variabila SeqNumToAck folosita in descrierea data anterior in aceasta sectiune).

static Xkreturn

swpPop (Sessn s, Sessn ds, Msg * dg, void *inHdr)

while (state->LAR != hdr->AckNum);

}

if (hdr->flags & FLAGS_HAS_DATA)

msgContructCopy (&slot->msg, dg);

slot->received = TRUE;

if (hdr->SeqNum == state->NFE)

/* send ACK: */

ackhdr.AckNum = state->NFE – 1;

ackhdr.Flags = FLAG_ACK_VALID;

msgConstructBuffer (char *) &ackhdr, sizeof (ackhdr));

xPush (de, ^m);

msgDestroy (&m);

}

}

return XK_SUCCESS;

}

In final, swpInWindow este o subrutina simpla care verificadaca un numar de secventa dat se incadreaza in domeniul curins intre valoarea minima si cea maxima a numarului de secventa.

Static bool

SwpInWindow (SwpSeqno seqno, SwpSeqno max)

Ordinea cadrelor si controlul fluxlui

Protocolul tip fereastra glisanta este poate cel mai cunoscut algoritm folosit in retele de calculatoare. Ceea ce poate fi usor derutant cu privire la algoritm, totusi, este aceea ca poate fi folosit in trei scopuri diferite. Primul este acela asupra caruia ne-am concentrat in aceasta sectiune, in speta livrarea sigura a cadrelor peste o legatura nesigura. (In general, algoritmul poate fi folosit pentru livrarea sigura a mesajelor peste o retaea nesigura.) Aceasta o reprezinta functia de baza a algoritmului.

Al doilea scop in care poate fi folosit algoritmul de tip fereastra glisanta este conservarea ordinei de emisie a cadrelor. Aceasta este o operatie simpla in partea de receptie; din moment ce fiecare cadru dispune de un numar de secventa, receptorul nu face decit sa se asigure ca nu va transmite nici un cadru catre protocolul de nivel superior inainte de a fi transmis toate cadrele cu numar de secventa inferior. Cu alte cuvinte, receptorul memoreaza in buffer (adica nu transmite mai departe) cadre dezordonate. Versiunea algoritmului tip fereastra glisanta descris in aceasta sectiune conserva ordinea cadrelor, desi se poate imagina o variatie in care receptorul transmite cadre catre urmatorul protocol fara a astepta livrarea tuturor cadrelor anterioare. O intrebare care trebuie puse este daca exista intradevar necesitatea ca protocolul tip fereastra glisanta sa pastreze cadrele in ordine, sau daca aceasta functionalitate nu este necesara la nivelul legatura. Din pacate, cunostintele acumulate pina in acest moment in materie de retele de calculatoare nu ne permit sa raspundem la aceasta intrebare; in prealabil este necesara intelegerea modului in care o secventa de legaturi punct-la-punct este conectata prin comutatoare pentru a forma o cale end-to-end.

Cel de-al treilea rol pe care il joaca uneori algoritmul tip fereastra glisanta este acela al controlului fluxului, in speta un mecanism de reactie prin care receptorul este capabil sa stranguleze emitatorul. Un asemenea mecanism este folosit pentru a preveni emitatorul sa depaseasca receptorul, cu alte cuvinte previne transmiterea mai multor date decit este capabil receptorul sa proceseze. Acest meacnism se implementeaza de obicei prin augmentarea protocolului tip dfereastra glisanta de asa maniera incat receptorul nu umai ca confirma cadrele receptionate, dar de asemenea informeaza emitatorul asupra spatiului de receptie. Numarul de cadre pe care receptorul este capabil sa le primeasca corespunde spatiului liber din buffer. Ca si in cazul unei livrari comandate , este necesar sa ne asiguram ca controlul fluxului este necesar la nivelul legatura inainte de a-l incorpora in protocolul tip fereastra glisanta.

Aspectul important care trebuie retinut din aceasta discutie este principiul de proiectare a sistemelor cunoscut sub numele de separare a resposabilitatilor. Cu alte cuvinte, utilizatorul trebuie sa fie atent pentru a distinge intre functii diferite care sunt deseori incorporate in acelasi mecanism, si trebuie sa se asigure ca fiecare functie ste necesara si este implementata in cel mai eficient mod posibil. In acest caz, livrarea sigura, livrarea in ordine si controlul fluxului sunt deseori combinate intr-un singur protocol de tip fereastra glisanta, iar intrebarea care trebuie pusa este daca acestea reprezinta operatiile care trebuie efectuate la nivelul legaturii.

5.3 Canale logice concurente

Protocolul IMP-IMP folosit in cadrul ARPANET constituie o alternativa interesanta la protocolul tip fereastra glisanta, prin aceea ca este capabil sa mentina canalul ocupat folosind in continuare algoritmul SAW. O consecinta importanta a Acestei abordari este aceea ca si cadrele emise pe o legatura data sunt pastrate intr-o anumita ordine. Protocolul IMP-IMP nu contine nici o componenta legata de controlul fluxului.

Ideea care sta la baza protocolului IUMP-IMP cunoscuta sub numele de canale logice concurente, estede a multiplexa mai multe canale logice pe o singura legatura punct-la-punct si de a rula algoritmul SAW pe fiecare dintre aceste canale logice. Intre cadrele emise pe canalele logice nu exista nici un fel de relatie, insa deoarece un cadru poate fi confirmat pe fiecare dintre canalele logice, emitatorul poate tine legatura ocupata.

Mai precis, emitatorul pastreaza trei biti de stare pentru fiecare canal: unul de tip boolean, care indica daca acel canal este ocupat sau nu in momentul respectiv; numarul de secventa de 1 bit care va fi folosit la urmatoarea emisie a unui cadru pe canalul logic, si urmatorul numar de secventa de asteptat de la cadrul care soseste pe acest canal. Cand nodul are un cadru de trimis, acesta va folosi canalul inactiv din pozitia cea mai joasa, in alte situatii se comporta exact ca un SAW.

In practica, ARPANET suporta 8 canale logice pe fiecare legatura terestra si 16 canale logice pe fiecare legatura prin satelit. In cazul canalelor terestre, antetul pentru fiecare cadru includea un numar de canal pe 3 biti si un numar de secventa de 1 bit, pentru un total de 4 biti. Acesta este exact numarul de biti necesar protocolului de tip fereastra glisanta pentru a suporta maximum 8 cadre neconfirmate pe fiecare legatura.

6. CSMA/ CD (Ethernet)

Este evident ca tehnologia de retea locala de calculatore care s-a bucurat de cel mai mare succes al ultimilor 20 de ani este Ethernetul. Creat la mijlocul anilor 70 de catre cercetatori ai Centrului de Cercetatare Xerox de la Palo Alto (PARC), Ethernetul este un exemplu functional al une tehnologii mai generale de conectare in retele locale, cunoscuta sub numele de Crrier Sense, Multiple Access with Collision Detect (CSMA/ CD). Ethernetul admite o rata de transmisi de 10 Mbps. Aceasta sectiune se concentreaza asupra celei mai comune sau”clasice” forme de Ethernet. Desi algoritmii sai de baza au ramas nemodificati, Ethernetul s-a adaptat de-a lungul timpului pentru a putea rula cu o varietate de viteze si pe un intreg domeniu de medii fizice.

Dupa cum arata abrevierea CSMA, Ethernetul este o rete cu acces multiplu(adica un set de noduri primesc si emit cadre peste o legatura partajata). Ca atare, se poate concepe un Ethernet ca o magistrala cu multiple statii conectate la aceasta. “Detectia purtatorului” indica faptul ca toate nodurile pot deosebi o legatura libera de una ocupata, iar”detectia coliziunii” arata ca un nod “asculta” in timpul transmisiei si ca atare poate detecta momentul interferentei (coliziunei) cadrului transmis cu un cadru transmis de alt nod.

Originile Ethernetului se afla intr-o retea radio cu pachete, denumita Aloha si creata la Universitatea din Hawaii pentru suportul comunicatiei intre calculatoare de-a lungul arhipelagului Hawaii. Similar retelei Aloha, problema fundamentala a unei retele Ethernet o constituie medierea in mod corect si eficient a accesului la un mediu partajat (in Aloha mediul era atmosfera, in timp ce Ethernetul foloseste cablul coaxial). Cu alte cuvinte, ideea de baza atit la Aloha, cat si la Ethernet o constiuie algoritmul care sa contrileze momentul in care fiecare nod este liber sa transmita.

6.1 Proprietati fizice

Un segment de Ethernet este implementat pe un cablu coaxial de maximum 500 metri. Acest cablu este similar cu cel folosit pentru televiziunea prin cablu, cu deosibirea ca are o impedanta de 50 ohmi, in loc de 75 de ohmi. Hosturile se cnecteaza la un segment Ethernet prin lipire, iar nodurile trebuie sa fie separate de o distanta de minimum 2 metri. Un transceiver metalic – un mic dispozitiv atasat direct la lipitura – detecteza momentul cand linia este libera si antreneaza semnalul cand hostul este in emisie. La randul sau, transceiverul este conectat la un adaptor Ethernet, care este conectat la host. Toata logica de baza a protocolului Ethernet este implementata in adaptor (nu in transceiver).

Figura 20. Repetor Ethernet

fiecare etaj. Pe scurt, un Ethernet este limitat la 1024 de hosturi.

Figura 21. Formatul unui cadru Ethernet

codare Manchester.

Ne-am referit la Ethernet-ul descris anterior cu adjectivul “clasic” deoarece tehnologiile alternative au fost introduse pe parcursul anilor. De exemplu, in loc de a utiliza un cablu coaxial de 50 ohmi, un Ethernet poate fi construit folosind un cablu mai subtire, cunoscut sub numele de 10Base2; cablul original se numeste 10Base5 (cele doua cabluri sunt cunoscute sub numele de thin-net, respectiv thick-net). Semnificatia lui 10 este aceea ca reteaua opereaza la 10Mbps, “Base” se refera la faptul se foloseste deseori intr-un sistem banda de baza, iar 2 indica faptul ca un segment dat nu poate fi mai lung de 200 metri (un segment din cablul original 10Base5 poate avea cel mult 500 metri lungime). O tehnologie si mai recenta se numeste 10BaseT, unde T provine de la twisted pair (bifilar torsadat). 10BaseT este similar cu linia care intra intr-un aparat telefonic standard, desi este putin mai groasa. Un segment 10BaseT este de regul limitat la o lungime sub 100 m.

Deoarece cablul este foarte subtire, un cablu 10Base2 sau 10Baset nu se lipeste la fel ca un cablu 10Base5. Cu 10Base2, o sudura in T este introdusa in cblu in consecinta, 10Base2 este folosit pentru a inlantui un set de hosturi. Cu 10BaseT, configuratia frecvent folosita este de a folosi mai multe segmente punct-la-punct care provin dintr-un repetor multicale.

6.2 Protocolul de acces

Ne vom indrepta atentia in continuare asupra protocolului Ethernet implementat hardware pe adaptorul de retea. Nu vom descrie adaptorul in sine, ci ne vom concentra asupra algoritmului pe care il implementeaza.

Formatul cadrului

Fiecare cadru Ethernet este definit prin formatul dat in figura 21. preambulul pe 64 de biti permite receptorului sa se sincronizeze cu semnalul; este o secventa de 0 si 1 dispusi alternativ. Hostul sursa si cel destinatie se identifica ambele printr-o adresa de 64 de biti. Campul tip de pachet serveste drept cheie de multiplexare; cu alte cuvinte, identifica protocolul de nivel inalt (din gama de protcoale poibile) care trebuie sa primeasca acel cadru. Fiecare cadru contine maximum 1550 bytes de date. Minimal, un cadru trebuie sa contina cel putin 46 de bytes de date, chiar daca aceasta inseamna ca hostul trebuie sa completeza cadrul cu zerouri inainte de a-l transmite. Motivul acestei dimensiuni minime de cadru este acela ca respectivul cadru trebuie sa fie suficient de lung pentru a detecta o coliziune; despre aceasta vom discuta in continuare. In final, fiecare cadru contine un CRC pe 32 biti. Ca si protocolul HDLC descris in sectiunea 3.2, Ethernetul este un protocol de cadre orientat pe bit. Se observa ca, din perspectiva jostului, un cadru Ethernet are un antet pe 14 bytes: 2 adrese de 6 bytes si un camp de tip de 2 bytes. Adaptorul de la emisie aseaza preambulul, CRC-ul si postambulul inainte de a efectua transmisia, iar adaptorul de la receptie le elimina.

Formatul de cadru descris anterior este preluat din standardul Ethernet definit colectiv de catre Xerox, Digital Equipment Corporation si Intel Corporation in 1978. Un standard similar, cunoscut sub numele de IEEE 802.3, a fost definit ulterior. Cele doua standarde sunt in esenta echivalente, cu exceptia faptului ca 802.3 inlocuieste campul de tip de 16 biti Ethernet cu un camp de lungime de 16 biti. Acest camp de lungime este folosit pentru a determina lungimea cadrului, in loc de a folosi indicatorul de final de cadru; 802.3 folseste informatia din regiunea de date pentru demultiplexa cadrul. In practica, standardul Ethernet (nu 802.3) reprezinta formatul dominant. Este interesant ca, deoarece standardul Ethernet a evitat utilizarea de valori pentru tip mai mici de 1500 (lungimea maxima gasita intr-un antet 802.3) este posibila efectuarea unei diferente intre cele doua formate.

Adrese

Fiecare host de pe un Ethernet, de fapt, fiecare host Ethernet din lume - are o adresa Ethernet unica. Tehnic vorbind, adresa apratine adaptorului, nu hostului, deoarece este imprimata in memoria ROM. Adresele Ethernet sun afisate intr-un mod citibil de catre operatorul uman sub forma unei secvente de 6 numere separate prin coloane. Fiecare numar corespunde unui byte din adresa de 6 bytes si este dat de o pereche de numere hexadecimale, unu pentru fiecare secventa de 4 biti din byte; s-a renuntat la zarourile din fata. De exemplu, 8:0:2b:e4:b1:2 este reprezentarea citibila de catre om a adresei Ethernet:

00001000 00000000 00101011

11100100 10110001 00000010

Pentru a fi siguri ca fiecare adaptor are o adresa unica, fiecare dintre fabricantii de dispozitive compatibile Ethernet primeste un prefix diferit care trebuie atasat adresei fiecarui adaptor construit. De exemplu, Advanced Micro Devices (AMD) a premit prefixul pe 8 biti x08002 (sau 8:0:2). Un fabricant se asigura apoi ca sufixele adreselor pe care le produce sunt unice.

Fiecare cadru transmis pe un Ethernet este receptionat de catre fiecare adaptor conectat la acel Ethernet. Fiecare adaptor recunoaste acele cadre destinate adresei sale si le transfera hostului numai pe acelea. (Un adaptor poate fi configurat sa ruleze in mod promiscuu, in care caz livreaza toate cadrele primite catre host.) In afara de aceste adrese unicast, o adresa Ethernet alcatuita numai din cifre 1 este tratata ca o adresa pentru broadcast; toti adaptorii transfera cadre destinate adresei de broadcast in sus catre host. Similar, o adresa care are primul bit setat la 1, dar nu este adresa de broadcast, se numeste adresa de multicast. Un anumit host isi poate programa adaptorul sa accepte un anumit set de adrese multicast. Adresele multicast sunt folosite pentru transmisia mesajelor la un anumit subset al hosturilor de pe un Ethernet, de exemplu, catre toate serverele de fisier. In rezumat, un adaptor Ethernet receptioneaza toate cadrele si accepta:

cadre destinate propriei adrese

cadre destinate adresei de broadcast

cadre destinate unei adrese multicast, daca a primit instructiuni sa detecteze adresa respectiva

toate cadrele, daca a fost plasat in mod promiscuu.

Adaptorul transmite hostului numai cadre pe care le accepta.

Algoritmul de transmitere

Dupa cum s-a vazut anterior, partea de receptie a protocolului Ethernet este simpla; lucrurile se complica insa la partea de emisie. Algoritmul de transmitere va fi definit in cele ce urmeaza.

Cand adaptorul are un cadru de transmis si linia este inactiva, cadrul este transmis imediaty; nu exista nici o negociere cu alti adaptori. Limita superioara de 1500 bytes a mesajului are semnificatia ca adaptorul poate pastra linia ocupata pentru un interval de timp fixat. In plus, un adaptor trebuie sa astepte 9 ms inainte de a putea transmite un alt cadru. Aceasta permite altor adaptori sa-si trimita cadrele si, ca atare, impiedica un adaptor sa trimita cadre plasate spate in spate la distanta prea mica unul dealtul, fiind astfel capabil de a mentine un control continuu asupra retelii.

Cand un adaptor are de transmis un cadru si linia este ocupata, acesta asteapta ca linia sa se elibereze si apoi transmite imediat. Se spune ca Ethernetul este un protocol 1-persistent, deoarece un adaptor de cadru de transmis va transmite cu probabilitate 1 de indata ce linia devine libera. In general, un algoritm p-persistent transmite cu probabilitate 0<=p<=1 dupa ce linia devine libera. Ratiunea de alegere a unui p<1 este aceea ca la un moment dat pot exista mai multi adaptori care asteapta ca linia ocupata sa se elibereze, si nu este de dorit ca toti sa inceapa a transmite in acelasi timp. Daca fiecare adaptor imite emite imediat cu probabilitatea de, sa zicem, 33%, atunci exista maximum trei adaptori care sunt in asteptare si exista sanse ca numai unul sa transmita cind linia se elibereaza. In ciuda acestei motivatii, un adaptor Ethernet transmite intodeauna imediat dupa ce a observat ca reteaua s-a eliberat, si procedeaza foarte eficient.

Deoarece nu exista un control centralizat, este posibil ca doi sau mai multi adaptori sa inceapa transmisia in acelasi timp, fie deoarece amindoi au descoperit ca linia este libera fie deoareace ambii au asteptat eliberarea unei linii. Cand acest lucru se produce, se spune ca cele doua (sau mai multe) cadre se afla in coliziune pe retea. Fiecare emitator, deoarece Ethernetul implementeaza detectia coliziunii, este capabil sa depisteze o coliziune aflata in curs de derulare. In momentul in care un adaptor detecteaza ca exista o coliziune intre cadrul emis de el si un alt cadru, transmite mai intii o secventa de blocare(jamming sequence) de 32 biti si apoi opreste transmisia. Astfel, un transmitator va transmite minimul 96 de biti in cazul unei coliziuni, in speta un preambul de64 de biti si o secventa de blocare de 32 de biti.

Pe de alta parte, pentru a fi sigur ca cadrul recent emis nu va intra in coliziune cu un alt cadru, transmitatorul pooate fi nevoit sa emita maximum 512 biti. Acest timp de blocare de minimum 512 biti provine din faptul ca, pe un Ethernet de dimensiuni maxime, intarzierea de al o extremitate la alta a retelei poate fi de maximum de 51 ms. Acesta este un interval de timp suficient pentru o retea de 10Mbps in vederea transmisiei a 512 biti; cu alte cuvinte, produsul intarziere * largime de banda pentru Ethernet este de 512 biti. Deoarece dorim sa ne asiguram ca doi adaptori care transmit, situati la capete opuse ale Ethernetului sunt ambii capabili sa detecteze aparitia unei coliziuni, ambii trebuie sa transmita suficienti biti pentru a umple canalul Ethernet, in speta 512 biti. Aceasta necesitate de a transmite un minimum de 512 biti explica de ce fiecare cadru Ethernet trebuie sa contina minimum 64 bytes de date: 14 bytes de antet, 46 bytes de date si 4 bytes de CRC egal 64 de bytes, sau 512 biti.

O data ce u adaptor a detectat o coliziune si si-a incheiat transmisia, acesta asteapta un anumit interval de timp si incearca din nou. De fiecare data cand incearca sa transmita si esueaza, adaptorul dubleaza intervalul de timp pe care il asteapta inainte de a relua transmisia. Strategia de dublare a intervalului de intarziere intre fiecare tentativa de retransmisie este o tehnica generala, cunoscuta sub numele de backoff exponential. Mai precis, adaptorul asteapta la inceput fie 0, fie 51 ms, valoare selectata aleator. Daca aceasta tentativa esueaza, apoi asteapta 0,51,2 sau 102 ms inainte de a relua incercarea; apoi asteapta 0, 51,2, 102,4 sau 204,8 ms etc. Adaptorul renunta dupa un numar dat dfe inercari(de regula 16) si semnaleaza hostului o eroare de transmisie.

6.3 Experienta cu Ethernet

Deoarece retelele de tip Ethernet sunt in uz de multa vreme si se bucura de o mare popularitate, experienta in utilizarea acestora este deosebit de larga. Un dintre cele mai importante observatii efectuate vizavi de Etherneturi este acela ca randamentul acestora este maxim in conditii de incarcare usoara. Aceasta deoarece incarcarile mari- de obicei o utilizare de peste 30% este considerata mare pentru Ethernet – determina o irosire prea mare a resurselor retelei in tratarea coliziunilor.

Din fericire, majoritatea Etherneturilor sunt folosite intr-un mud cu molt mai conservator decat o permite standardul. De exemplu, majoritatea retelelor Ethernet au mai putin de 200 hosturi conectate, ceea ce este cu mult mai putin decat limita admisa de 1024. Similar, majoritatea Etherneturilor sunt mai scurte de 1500 metri, cu o intarziere de propagare mai apropiata de 5 ms decat de 51,2 ms. Un alt factor care accentuiaza caracterul practic al Etherneturilor este acela ca, desi adaptorii Ethernet nu impleneteaza controlul fluxului la nicel de lagatura, hosturil asigura de obicei un mecanism de control al fluxului end-to-end. In consecinta, situatiile in care orice host “pompeaza” continuu cadre in retea sunt extrem de rare.

In final, trebuie spuse cateva cuvinte si despre succesul acestui tip de retele, pentru a putea intelege proprietatile care trebuie emulate de catre orice tehnologie LAN care incearca sa inlocuiasca Ethernetul. Mai intai, un Ethernet este extrem de simplu de administrat si intretinut: nu exista comutatoare care se pot defecta, nu exista tabele de rotare sau de configurare care trebuie actualizate, iar reteaua accepta cu usurinta introducerea de noi hosturi. Problema majora pentru oricare dintre retelele bazate pe comutatie o va prezenta obtinerea simplitatii in operare a retelelor de tip Ethernet. Ina ldoilea rand, o retea ethernet este necostisitoare: cablul este ieftin si unicul cost este legat de adaptorul atasat la fiecare host. Din nou, orice retea bazata pe comutatori va necesita o investitie intr-o infrastructura costisitoare (comutatoarele) in afara de costul incremental al fiecarui adaptor.

Figura 22. Retea de tip inel cu jeton

7 Inele cu jeton (FDDI)

Pe langa Ethernet,retelele de tip inele cu jeton reprezinta o alta categorie semnificativa de retele cu mediu partajat. Exista mai multe tipuri de inele cu jeton decat Etherneturi; aceasta sectiune se va ocupa in detaliu de unul, in speta FDDI(Fiber Distributed Data Interface-interfata de datete distribuita pe fire). Retelele de tip inel cu jeton anterioare au inclus PRONET de 10Mbps si 80Mbps, IBM de 4Mbps si IEEE 802.5 de 16Mbps. Sub multe aspecte, ideile incorporate in FDDI reprezinta un superset al celor existente in orice retea ed tip inel cu jeton. Aceasta transforma FDDI intr-un model oportun de studiu al retelelor de tip inel cu jeton in general.

Dupa cum o arata si numele, o retea de tip inel cu jeton FDDI este alcatuita dintr-un set de noduri conectate in inel. (vezi figura 22) Datele tarverseaza reteaua intr-o anumita directie in jurul inelului, in cadrul caruia fiecare nod primeste cadre de la vecinul sau din amonte si le transmite mai departe vecinului sau din aval. Aceasta topologie de tip inel este in contrast cu topologia de magistrala folosita de Ethernet. Cu toate acestea, similar Ethernetului, inelul apre drept un unic mediu partajat; ca atare, nu se comporta ca o colectie de legaturi punct-la –punct independente care intimplator sunt conectate in cerc. Astefel, oretea de tip inel cu jeton are in comun cu Ethernetul doua caracteristici cheie; mai intai implica un algorit distribuit care controleaza momentul de timp fiecarui nod ii este permis sa transmita, si in al doilea rand toate nodurile “vad” toate cadrele, unde nodul identificat drept destinatiein antetul cadrului salveaza o copie a caetuia dupa ce cadrul paraseste nodul.

Termenul de jeton provine din modalitatea de gestionare a caestui inel partajat. Ideea ste ca un jeton, care in realitate nu este nimic altceva decat o secventa speciala de biti, circula in jurul inlului; fiecare nod primeste si apoi transmite jetonul mai departe. Cand un nod care are un cadru de transmis “vede” jetonul, preia jetonul din inel (adica nu transmite secventa speciala de biti mai departe) si in locul aestuia insereaza in inel propriul sau cadru. Cand cadrul revine la eitator, nodul elimina cadrul din inel (deci nu il transmite mai departe) si reinsereaza jetonul. Algoritmul de acces la mediu este corect, in sensul ca, pe masura ce jetonul circula in inel, fiecare nod are o sansa de a transmite. Astfel,nodurile sunt deservite pe rand.

a) b)

Figura 23 Inel cu fibra duabila

3.1 Proprietati fizice

Spre deosebire de ilustrarea simpla data in figura 22, un inel FDDI poate avea o configuratiemai complexa decat se poate imagina. Mai inai, o retea FDDI este in realitate alcatuita dintr-un inel dual – doua inele independente care transmit date in directii opuse, asa cum este ilustrat in figura 23 (a). Al doilea inel nu este folosit in timpul unei operari normale, ci intra in functiune numai la “caderea” inelului primar, asa cum este descris in figura 23 (b). Cu alte cuvinte, pe fibra secundara ciclul este parcurs in sens inverspentru a forma un inel complet, si in consecinta o retea FDDI este capabila sa tolereze o singura eroare in cablu.

Fiecare nod este conectat la inel prin patru fire – unul de intrare si unul de iesire pentru inelul principal, precum si unul de intrare si de iesire pentru inelul secundar. Aceste patru fire sunt in realitate in doua cabluri, cate unul pentru fiecare vecin de retea al unui nod. De asemenea, aceste cabluri se conecteaza la un adaptor de retea FDDI(nu la host in sine). Protocolul FDDI desris in sectiunea 7.2 este implementat in acest adaptor.

Al doilea element de complexitate in configuratia unui FDDI estea acela ca, datotita costului unei configuratii cu inele duale, FDDI permite conectarea nodurilor la retea printr-un singur cablu. Aceste noduri se numesc statii cu conectare simpla (single attachment stations -SAS); omogenele lor conectate dual se numesc, dupa cum era ed asteptat, statii cu conectare duala (dual attachment stations -DAS). Un concentrator este folosit pentru a atasa mai multe SAS-uri la ineluldual, dupa cum se vede in figura 24. se observa modul in care conexiunea cu un singur cablu (doua fire) intr-un SAS determina o portiune conectata a inelului. Daca acest SAS “cade”, concentratorul detecteaza aceasta situatie si foloseste un bypass optic pentru a izola SAS-ul defect,mentinind mai departe inelul conectat. Se retine de asemenea ca in aceasta situatie al doilea inel(de rezerva) este notat cu o linie punctata.

Al treilea element de complexitate este acela ca fiecare statie implementeaza un buffer de elasticitate care memoreaza temporar bitii dintr-un cadru pe masura ce acestia trec prin statie. Aceasta permite trimiterera cadrelor pe inel fara necesitatea sincronizarii tuturor spatiilor; bufferul separa receptia bitilor de la vecinul din amonte de transmisia bitilor catre vecinul din aval. Bufferul trebuie sa fie capabil a retine el putin noua biti, dar ajunge la dimensiuni de pina la 80 biti. Se retine ca acest buffer de elasticitate are semnificatia ca fiecare statie introduce o intirziere in timpul necesar datelor pentru a parcurge inelul. De exemplu, deoarece FDDI este o retea cu viteza de 100Mbps, timpul de bit este de 10 nanosecunde(fiecare bit are o latime de 10 ns). Daca fiecare statie implementeaza un buffer de 10 biti si asteapta umplerea pe jumatate a bufferului inainte de a incepe transmisia, apoi fiecare statie introduce o intirziere de 5*10=50 ns in timpul total de rotatie pe inel.

Figura 24. SAS-uri conectate la un concentrator

FDDI implica faptul ca fibra optica serveste ca mediu fizic de baza, standartul a fost definit pentru a fi operational pe un numar de medii fizice diferite, inclusiv capul coaxial si cablul bifilar torsadat. Desigur, este necesara atentie fata de distanta totala acoperita de inel. Dupa cum vom vedea in sectiunea 7.2, intervalul de timp necesar jetonului pentru a traversa inelul are un rol important in cadrul algoritmului de control al accesului.

FDDI foloseste codarea de 4B-5B. Dupa cum s-a aratat in sectiunea 2 a acestei lucrari. Deoarece FDDI a fost prima tehnologie de retele populara care a folosit fibra optica, cipurile 4B/5B care opereaza la viteze impuse de FDDI au devenit disponibile pe scara larga, 4B/5B s-a bucurat de o popularitate considerabila ca schema de codare pentru fibra optica.

7.2 Algoritmul jeton temporar (timed-token)

Algoritmul efectiv de control al accesului folosit de FDDI este mult mai complicat decat descrierea sumara data in partea introductiva a acestei sectiuni. In cele ce urmeaza vom discuta despre acest algoritm mai in detaliu.

Prima problema care trebuie amintita este cantitatea de date pe care un nod dat este autorizat sa le transmita la fiecare posesie a jetonului; cu alte cuvinte, intervalul de timp maxim care ii permis nodului sa retina jetonul. Acest interval va fi denumit timp de retinere a jetonului (token holding time-THT). Daca presupunem ca majoritatea nodurilor din retea nu au date de transmis la nici un moment dat- ceea ce este o presupunere rezonabila, de care Ehternetul se foloseste in mod evident- atunci se va permite fiecarui nod sa transmita toate datele de care despune anterior transmiterii jetonului catre urmatorul nod. Aceasta ar insemna setarea lui THT la infinit. limitarea unui nod la transmiterea unui singur mesaj, precum si fortarea aceluiasi nod sa astepte pina cand jetonul circula pe tot inelul inainte de a putea transmite un alt mesaj sunt procedee total nerecomandabile. Desigur, expresia ”toate datele disponibile” este periculoasa deoarece o singura statie poate pastra jetonul pentru un interval de timp arbitrrar de lung, dar este posibila setarea THT la o valoare foarte mare.

Este simplu de vazut ca, daca numarul de bytes pe care le poate transmite un nod la fiecare posesie a jetonului creste, inelul este mai bine utilizat in situatia in care un singur nod arev date de transmis. Dezavantajul, desigur, este acela ca strategia prezentata nu este functionala in momentul in care mai mullte noduri au date de transmis, in sensul ca favorizeaza acele noduri care au un volum mare de date de transmis, in detrimentul nodurilor care au de transmis un singur mesaj, chiar daca este important ca acel mesaj sa fie livrat in cel mai scurt timp posibil. Situatia este similara cu aceea a clientului care doreste sa incaseze un cec la banca si sta la coada in spatele unuia care solicita un imprumut pentru achizitionarea unei masini.

In ansamblu, este posibila definirea timpului de rotatie a jetonului(token rotation time-TRT) ca fiind timpul necesar unui jeton pentru a traversa un inel, din perspectiva unui nod dat. Este simplu de observat ca

TRT<=ActiveNotes*THT+RingLatency

unde RingLatency semnifica timpul necesar jetonului pentru a parcurge inelul cand nici un nod nu are date de transmis.

Pentru a fi sigur ca un nod dat are posibilitatea de a transmite intr-unn anumit interval de timp- cu alte cuvinte, pentru a impune o limita superioara pentru TRT-ul observat de orice nod- vom defini unn timp de rotatie a jetonuului tinta(target token rotation time-TTRT), iar nodurile accepta sa fie active in limitele TTRT. (Modul in care nodurile accepta un anumit TTRT este descris in subsectiunea urmatoare.) Concret, fiecare nod masoara intervalul de timp intre doua sosiri succesive ale jetonului. Vom numi acest timp TRT masurat daca acest TRT masurat este decat TTRT convenit, atunci jetonul este intarziat si nodul are permisiunea de a retine jetonul pentru diferenta dintre TTRT si TRT masurat.

Desi in aparenta problema a fost rezolvata, algoritmul descris nu asigura ca un nod ocupat cu emiterea unui cadru cu o intirziere liitata este capabil de aceasta actiune. Problema este ca un nod cu cantitati mari de date de transmis are posibilitatea, la aparitia unui jeton timpuriu, sa retina jetonul respectiv pentru un interval de timp suficient de lung astfel incat, in momentul in care un nod din aval primeste jetonul, TRT masurat al nodului devine egal sau mai mare decat TTRT, ceea ce inseamna ca este inca incapabil d e a-si transmite cadrul. Pentru a trata aceasta posibilitate, FDDI defineste doua clase de trafic: sincron si asincron. Cand un nod primeste un jeton, are intodeauna permisiunea de a emite date sincrone, indiferent daca nodul este timpuriu sau intarziat. Prin contrast, un nod poate emite tarfic asincron numai cand jetonul este timpuriu.

Sa observam ca terminii sincron si asincron sunt oarecum derutanti. Prin sincron, FDDI intelege faptul ca traficul este sensibil la intarziere. De exemplu, se poate transmite video sau voce sub form ade trafic sincron pe o retea FDDI. Prin contrast, asincron inseamna ca aplicatia este interesata in debit si mai putin in intarziere. O aplicatie de transfer de fisiere reprezinta o monstra de trafic FDDI asincron.

Am terminat? Nu chiar. Deoarece traficul sincron poate fi transmis indiferent daca jetonul este intirziat sau timpuriu, se pare ca daca fiecare nod avea o cantitate considerabila de date de transmis, atunci TTRT va deveni din nou lipsit de semnificatie. Pentru aceasta, volumul total de date sincrone care poate fi emis pe durata unei rotatii a jetonului este de asemenea limitat de catre TTRT. Aceasta inseamna ca, in cel mai rau caz, nodurile de trafic asincron folosesc mai intai timpul unui TTRT, iar apoi nodurile cu date sincrone consuma un alt TTRT, ceea ce inseamna ca TRT-ul masurat pentru orice nod sa aiba o valoare maxima de 2*TTRT. Se retine ca, daca traficul sincron a consumat deja un TTRT, atunci nodurile cu trafic asincron nu vor trimite nici un fel de date, deoarece jetonul va fi intirziat. Astfel, este imposibil sa apara rotatii spate-in-spate ale jetonului care sa consume un interval de timp egal cu 2* TTRT.

Cu aceasta discutia s-a incheiat, cu exceptia a doua chestiuni ramase nerezolvate. Mai inai, se pune intrebarea care este momentul exact de timp la care nodul emitator elibereaza jetonul. Dupa cum se vede in figura 25, emitatorul poate insera jetonul in inel imediat dupa emisia cadrelor (aceasta se numeste eliberarea imediata) sau odata ce cadrul transmis a parcurs tot inelul si a fost eliminat (ceea ce se numeste eliberare intarziata). Daca intarzierea in jurul inelului este mai mare decat intervalul de timp necesar emisiei unui, cadru atunci metoda de eliberare imediata iroseste largimea de banda a inelului. FDDI foloseste eliberarea imediata a jetonului. Initial IEEE 802.5 folosea eliberarea intarziata, dar in prezent a fost adauagt suport pentru eliberarea imediata a jetonului.

A doua problema se refera la modul exact in care un nod determina daca poate transmite trafic asincron. Asa cum s-a aratat anterior, un nod trimite date asincrone daca TRT masurat este mai mic decat TTRT. Se ridica urmatoarea intrebare: Ce se intampla daca TRT masurat este mai mic decat TTRT, dar diferenta este atat de mica incat nu este posibila transmiterea intregului mesaj fara depasirea TTRT? Raspunsul este ca nodului i se permite sa transmita in acest caz. In consecinta, TRT masurat este limitat de catre TTRT plus intervalul de timp necesar transmiterii unui cadru FDDI complet.

7.3 Intretinerea jetonului

Algoritmul descris anterior se bazaeaza pe existenta unui jeton valid. Deoarece un jeton nu este altceva decat o secventa de biti speciala, iar erorile de bit pot aparea oricand, este posibila pierderea jetonului. De asemenea, un jeton poate fi pierdut cand nodul care il memoreaza sufera o eroare. Ca atare, retelele de tip inel cu jeton necesita o metoda de memorizare a validitatii jetonului si de generare a unui jeton nou, daca jetonul vechi se pierde. Generarea unui jeton nou este de asemenea necesara la initializarea unui inel. Mai intai ne vom ocupa de problema generarii unui jeton si dupa aceea de monitorizarea validitatii jetonului.

Generarea unui jeton

Un nou jeton este generat potential ori de cate ori in inel este inserat un nod nou sau cand un nod suspecteaza aparitia unei erori de un anumit gen. In timpul procesului de generare a unui jeton, nodurile dintr-un inel convin asupra TTRT-ului curent.

Algoritmul, cunoscut si sub numele de proces de solicitare a jetonului, este simplu. Fiecare nod trimite un cadru de solicitare, care include oferta nodului pentru TTRT, cu alte cuvinte timpul de rotatie a jetonului necesar nodului pentru a satisface necesitatile aplicatiilor pe care le ruleaza. Un nod poate trimite un cadru de solicitare fara a detine jetonul si procedeaza de obicei la aceasta cand suspecteaza o eroare sau la prima intrare in retea. Daca acest cadru de solicitare parcurge intreg inelul, atunci emitatorul sau il elimna din inel, cunoscand ca oferta sa de TTRT a avut valoarea cea mai redusa. Nodul respectiv detine in acest moment jetonul - adica este responsabil cu insertia in inel a unui jeton corect – si poate initia algoritmul normal de jeton.

Figura 25. Eliberarea imediata(a) si intarziata(b) a jetonului

Monitorizarea validitatii jetonului

Intr-un inel cu o functionarecorecta, fiecare nod trebuie sa “vada” o transmisie valida – un cadru de date sau un jeton – cat mai frecvent posibil. Cel mai mare timp de repaos pe care un anumit nod trebuie sa-l intalneasca intre doua transmisii valide este egal cu latenta inelului plus timpul necesar pentru transmiterea unui cadru complet, ceea ce, pentru un inel de diminsiuni maximale, este putin mai mic de 2 ms. Ca atare, fiecare nod seteaza un eveniment de cronometru care expira dupa 2,5 ms. Daca acest interval expira, nodul suspecteaza o eroare si transmite un cadru de solicitare. Cu toate acestea, la fiecare primire a unei transmisii avlide, nodul reseteaza cronometrul la fiecare 2 ms.

7.4 Formatul cadrului

In acest moment suntem gata sa definim formatul cadruluii FDDI, descris in figura 26. FDDI foloseste schema de codare 4B/5B, descrisa in sectiunea 2. aceasta inseamna ca multe din campurile incluse in antet – de exemplu indicatorii de inceput si de sfarsit de cadru – sunt date de simbolurile de control aferente schemei 4B/5B.

Similar Ethernetului, adresele FDDI au o lungime de 48 biti. Standardul FDDI permite si adrese mai mici, de 16 biti, dar in mod normal se folosesc adrese de 48 de biti. La utilizarea adreselor de 48 biti, acestea sunt inerpretate de aceeasi maniera ca si pe Ethernet. De asemenea similar cu Ethernetul, FDDI foloseste incadrarea orientata pe bit, cu o secventa unica de biti care desemneaza inceputul si sfarsitul cadrului. De asemenea, un cadru FDDI contine un CRC de 32 biti. Cadrele FDDI pot avea o lungime de maximum 4500 bytes, inclusiv antetul FDDI, ceea ce inseamna ca un cadru care foloseste adrese pe 48 biti poate transporta 4478 bytes de date.

Figura 26. Formatul de cadru FDDI

sunt notate prin secvente speciale de biti plasate in acest camp.

In final, antetul FDDI include un camp de 24 de biti de stare a cadrului. Acest camp este in mod normal setat de catre destinatarul cadrului, pentru a raporta emitatorului informatii despre stare. (Sa ne reamintim ca cadrul parcurge tot inelul si este eliminat de catre emitator, care poate apoi citi acest camp de stare.) Concret, receptorul poate spune daca a existat o eroare in cadrul primit, daca a recunoscut sau nu adresa, precum si daca a copiat sau nu cadrul in timpul trecerii acestuia. Aceste ultime doua informatii par redundante, deoarece un nod care isi recunoaste adresa in antyet salveaza in mod normal o copie a cadrului. Cu toate acestea, este posibil ca un nod sa-si recunoasca adresa in campul destinatie, adr, deoarece nu dispune de suficient spatiu in buffer, sa refuze copierea cadrului in memoria sa locala. Astfel, FDDI permite receptorului sa trimita emitatorului informatii legate de controlul fluxului.

8. Adaptori de retea

Aproape toate functionalitatile de retea descrise in acest capitol sunt implementate in adaptorul de retea: incadrarea, detectia erorilor si protocolul de acces la mediu. Unicile exceptii le constituie schemele de cerere automata de repetare punct-la-punct (ARQ) descrise in sectiunea 5, care sunt implementate de obicei in protocolul de nivelul cel mai jos care ruleaza pe host. Vom incheia aceasta lucrare prin descrierea modului de proiectare a unui adaptor de retea specific, precum si a driver-ului de dispozitiv care il controleaza.

In timpul lecturarii acestei sectiuni, cititorul trebuie sa retina ca nu exista doi adaptori de retea perfect identici: acestia variaza in nenumarate detalii. Ca atare, preocuparea noastra s-a concentrat asupra caracteristicilor in general, desi vom include unele exemple preluate dintr-un adaptor efectiv pentru a mari nivelul de concret al discutiei.

8.1 Componente

Un adaptor de retea serveste ca interfata intre host si retea, iar in consecinta poate fi asimilat ca avind doua componente de baza: o interfata cu magistrala, care intelege modul de comunicare cu hostul si o interfata de comunicare cu legatura, care foloseste protocolul de retea corespunzator. De asemenea, trebuie sa existe o cale de comunicare intre aceste doua componente, cale peste care sunt tranferate datele de intrare si de iesire. O diagrama bloc simpla a unui adaptor de retea este prezentata in figura 27.

Adaptorii de retea sunt intotdeauna proiectati pentru o anumita magistrala I/O, ceea ce reprezinta motivul pentru care nu este posibila deplasarea unui adaptor de la calculatorul unei firme la un alt calculator, al altei firme. Ca efect, fiecare magistrala defineste un protocol care este folosit de microprocesorul hostului pentru a programa adaptorul, precum si de adaptor pentru a intrrupe microprocesorul hostului si pentru a citi si a scrie in memoria locala a hostului. Una dintre princiaplele caracteristici ale unei magistrale de I/O o reprezinta rata de transfer a datelor pe care o implementeaza. De exemplu, o magistrala obisnuita poate avea o acale de date cu o largime de 32 de biti (adica poate transfera in paralel 32 de biti) si poate rula la 25 MHz (adica intervalul de ciclare al magistralei este de 40 ns), ceea ce ii ofera un varf al vitezei de transfer de 800 Mbps, adica suficient pentru a admite o legatura (unidirectionala) STS-12 la 622 Mbps. Desigur, valoarea de varf a vitezei nu spune aproape nimic despre viteza medie de transfer, care poate avea o valoare mult inferioara.

Partea de interfata cu legatua a adaptorului implementeaza protocolul la nivel de legatura. Pentru tehnologii ajunse la maturitate cum sunt Ethernetul si FDDI, interfata cu legetura este implementata printr-un chipset care poate fi achizitionat la orice magazin de electronice. Pentru tehnologii de data mai recenta, protocolul de nivel legatura poate fi implementat software pe un microprocesor de uz general sau poate cu o anumita forma de hardware programabil, cum ar fi un FPGA. Aceste metode in general determina o crestere a costului unui adaptor, dar ii sporesc flexibilitatea; componentele software sunt mai simplu de modificat decat cele hardware, dupa cum este mai simplu de reprogramat un FPGA decat de reproiectat o placa de baza.

Deoarece magistrala hostului si legatura cu reteaua ruleaza, dupa toate probabiltatile, la viteze diferite, este necesara introducerea unui buffer intre cele doua jumatati ale adaptorului. De regula, un mic FIFO (coada de bytes) este suficient pentru a ascunde desincronizarea intre magistrala si legatura.

8.2 Vedere dinspre host

Deoarece mare parte din acest capitol a fost dedicata descrierii diferitelor protocoale implementate de interfata cu legatura a adaptorului, in continuare ne vom indrepta atentia spre adaptorul de retea asa cum este vazut de hostul pe care il deserveste.

Registru de stare al controlului

Un adaptor de retea, ca orice alt dispozitiv, este in ultima instanta programat de catre programe care ruleaza pe CPU. Din perspectiva microprocesorului, adaptorul exporta un registru de stare al controluli (CSR) care poate fi citit si modificat de catre microprocesor. De obicei, CSR este localizat la o anumita adresa din memorie, ceea ce permite scrierea si citirea din partea CPU ca pentru orice alta locatie de memorie. CPU scrie in CSR pentru a-l instrui sa transmita si/sau sa primeasca un cadru si sa citeasca din CSR starea curenta a adaptorului.

In continuare este prezentat un exeplu de CSR din dispozitivul Lance Ethernet, produs de Advanced Microsystem Devices (AMD). Acesta are patru registri de stare a controlului; uramatorul prezinta mastile de biti folosite pentru a interpreta registrul pe 16 biti CSR0. Pentru a seta un bit din adaptor, CPU efectueaza un SAU EXCLUSIV pe masca corespunzatoare bitului pe care doreste sa-l seteze si pe CSR0. pentru a determina daca un anumit bit este setat, CPU compara rezultatul unui SI intre masca si CSR0 cu 0.

* Control and status bits for CSR0.

*

* Legend:

* RO – Read Only

* RC – Read/Clear (writing 1 clears, writing 0 has no effect)

* RW – Read/Write

* W1 – Write – 1 – only (writing 1 sets, writing 0 has no effect)

* RW1 – Read/Write– 1 – only (writing 1 sets, writing 0 has no effect)

#define LE_ERR 0x8000 /* RO BABL | CERR | MISS | MERR */

#define LE_BABL 0x4000 /* RC transmitted too many bits */

#define LE_CERR 0x2000 /* RC No Heartbit */

#define LE_MISS 0x1000 /* RC Missed an incoming packet */

#define LE_MERR 0x0800 /* RC Memory Error; no acknowledge*/

#define LE_RINT 0x0400 /* Received packet Interrupt */

#define LE_TINT 0x0200 /* RC Transmitted packet Interrupt */

#define LE_IDON 0x0100 /* RC Initialisation Done */

#define LE_INTR 0x0080 /* RO BABL | MISS | MERR | RINT | TINT | IDON */

#define LE_INEA 0x0040 /* RW Interrupt Enable */

#define LE_RXON 0x0020 /* RO Receiver On */

#define LE_TXON 0x0010 /* RO Transmitter On */

#define LE_TDMD 0x0008 /* W1 Transmit Demand (send it now) */

#define LE_STOP 0x0004 /* RW1 Stop */

#define LE_STRT 0x0002 /* RW1 Start */

#define LE_INIT 0x0001 /* RW1 Initialize */

Definitia spune, de exemplu, ca hostul scrie un 1 in pozitia cea mai putin semnificativa a CSR0 (0x0001) pentru a initializa chip-ul Lance. Similar, daca hostul vede un 1 in al saselea bit semnificativ (0x0020) si in al cincilea bit semnificativ (0x0010), atunci va sti ca chip-ul Lance este capabil sa recepteze si sa emita cadre.

Intreruperi

In loc de polling, majoritatea hosturilor prefera sa acorde atentie dispozitivului de retea atunci cand adaptorul intrerupe hostul. Acest dispozitiv genereaza o intrerupere la aparitia unui eveniment care necesita atentia hostului – de exemplu emisia sau receptia cu succes a unui cadru, sau o eroare survenita in timpul tentativei de emisie sau de receptie a unui cadru. Arhitectura hostului include un mehanizm care determina apelarea unei anumite proceduri din interiorul sistemului de operare la aparitia unei asemenea intreruperi. Aceasta procedura este cunoscuta sub numele de instrument de tratare a intreruperii (interrupt handler) si inspecteaza CSR pentru a determina cauza intreruperii si apoi interprinde actiunea corespunzatoare.

In timpul tratarii unei intreruperi, hostul dezactiveaza de obicei intreruperile aditionale. Aceasta previne tratarea de catre driver-ul de dispozitiv a mai multor intreruperi simultan. Deoarece intreruperile sunt inactive, driver-ul trebuie sa-si termine treaba rapid (nu are timp sa execute intreaga stiva de protocoale) si sub nici o forma nu-si poate perminte sa se blocheze (cu alte cuvinte, sa-si suspende executia in asteptarea unui eveniment anume). Un x-nucleu, de exemplu, aceasta se realizeaza prin alocarea de catre instrumentul de tratare a intreruperii unui proces care sa se ocupe de messaj si apoi sa returneze. Astfel, instrumentul de tratare se asigura ca mesajul va fi procesat fara a trebui sa consume timp pretios prin procesarea mesajului in sine.

Acces direct la memorie sau I/O programabil

Una dintre problemele cele mai importante in proiectarea unui adaptor de retea o constituie modul in care datele dintr-un cadru sunt transferate intre adaptor si memoria hostului. Exista doua mecanisme necesare: accesul direct la memorie (direct memory acces- DMA) respectiv I/O programat (programmed I/O- PIO). Folosind DMA, adaptorul citeste si scrie direct in memoria hostului in absenta oricarei implicari a microprocesorului; hostul pur si simplu ofera adaptorului o adresa de memorie iar adaptorul citeste din sau scrie in acestea. Mecanismul PIO atribuie microprocesorului responsabilitatea directa pentru deplasarea datelor intre adaptor si memoria hostului; pentru a transmite un cadru, CPU executa un ciclu strans care citeste un cuvant din memoria hostului si apoi il scrie in adaptor; pentru a primi un cadru, CPU citeste cuvinte din adaptor si le scrie in memorie. In continuare vom discuta despre cele doua mecanisme in detaliu.

La utilizarea DMA nu este necesara memorarea cadrelor in bufferul adaptorului; adaptorul citeste si scrie in memoria hostului. (Sunt totusi necesari cativa bytes de buffer pentru a etapiza dsatele intre magistrala si legatura, asa cum s-a aratat anterior, dar adaptorul nu memoreaza in bufferul propriu cadre complete.) Ca atare, microprocesorul este responsabil pentru transmiterea catre adaptor a doua liste descriptor de buffer, una pentru a emite si una pentru a receptiona. O lista descriptor de buffer este un tablou de perechi adresa/lungime dupa cum este ilustart in figura 28.

La receptionarea cadrelor adaptorul foloseste pentru memorarea cadrului primit atatea buffere cate sunt necesare. De exemplu, descriptorul ilustrat un figura 28 va determina un adaptor Ethernet care intentiona sa primeasca un cadru de 1450 bytes sa insereze primii 100 de bytes in primul buffer si urmatorii 1350 in al doilea buffer. Daca un al doilea cadru, de 1500 bytes sosea imediat dupa primul, ar fi fost plasat integral in al treilea buffer. Cu alte cuvinte, cadre separate sunt plasate in buffere separate, desi un singur cadru poate fi dispersat pe mai multe buffere. Aceasta ultima caracteristica se numeste de obicei citire imprastiata (sctter-read). In practica, acest procedeu se foloseste cand dimensiunea a cadrului de retea este atat de mare, incat este neeconomic sa se aloce pentru buffere o dimensiune suficient de mare pentru a putea memora cel mai mare cadru posibil. In aceste conditii se va folosi un mecanism ca structura de date de tip mesaj x-nucleului pentru legarea la un loc a tuturor bufferelor care alcatuiesc un singur cadru. Citirea imprastiata nu se foloseste pe Ethernet, deoarece prealocarea unor buffere de 1550 bytes nu deduce la o irosire excesiva a memoriei.

La emisie se procedeaza similar. Cand hostul are de emis un cadru, insereaza un pointer catre bufferul ce contine cadrul in lista descriptor pentru emisie. Dispozitivele care implementeaza mecanismul gather-write permit fragmentarea cadrului pe ami multe buffere fizice. In practica, procedeul gather-write iste folosit mai pe larg decat citirea imrastiata, deoarece cadrele care parasesc hostul sunt deseori construite intr-o maniera compusa, cu ami multe protocoale care contribuie la un buffer. De exemplu, in momentul in care un mesaj coboara pe stiva de protocoale si este gata de a fi transmis, acesta este alcatuit dintr-un buffer care contine antetul compus (adica un ansamblu de antete atasate de catre diferitele protocoale care au procesat mesajul) si un buffer separat care contine datele necesare aplicatiei.

In cazul PIO, adaptorul de retea trebuie sa contina un oarecare spatiu de buffer – micorprocesorul copiaza cdre intre memoria hostului si acesta memorie a adaptorului, asa cum se vede in figura 29. principalul aspect care impune existenta unui buffer este acela ca, in cadrul majoritatii sistemelor de operare, utilizatorul nu sti niciodata cand microprocesorul este gata sa execute o anumita opratie, deci trebuie sa fie pregatit pentru aceasta. O problema importanta care trebuie rezolvata o re prezinta cantitatea de memorie necesara adaptorului. Evident este necesara o memorie echivalenta cu minimum un cadru, atat la emisie, cat si la receptie. De asemenea, adaaptorii care folosesc PIO dispun de obicei de memorie suplimentara care poate fi folosita pentru a memora un mic numar de cadre receptionate pana cand microprocesorul le poate copia in memoria hostului. Desi axioma sistemelor de calculatoare conform careia “memoria este ieftina” pare sa sugereze inserarea unui volum urias de memorie in adaptor, aceasta trebuie sa fie detip dual portat, deoarece atat microprocesorul cat si adaptorul o folosesc pentru scriere si citire. Adaptorii PIO dispun de o memorie cuprinsa intre 64-256 KB de memorie, desi exista si adaptori cu 1 MB de memorie.

8.3 Exemplu de driver de dispozitiv

In aceasta sectiune va fi descris un driver de dispozitiv pentru adaptorul Ethernet Lance. Unul dintre obiectivele urmarite este demonstararea modului de implementare a unui graf de protocoale de x-nucleu in driverul de dispozitiv. In exemplul urmator, variabila CSR este un pointer catre registrul Lance CSR0; am disimulat detaliile de manipulare a listelor descriptor pentru bufferii de emisie si de receptie in functiile next_xmit_buffer, next_rcv_desc si install_rvc_desc; rutina copy_data_to_lance copiaza datele gasite intr-un obiect mesaj intr-un buffer contiguu de memorie citibil de catre dispozitivul Lance. De asemenea, se presupune existenta urmatoarelor rutine de nucleu de nivel redus care implementeaa functiile evidente: process_create, disable_interrupts si enable_interrupts.

Codul prezentat este jumatatea dependenta de dispozitiv a protocolului Etherne; mai exista o jumatate independenta de protocol care exporta operatii standard din x-nucleu – cum ar fi xPush – catre protocoalele de nivel inalt. Aceasta jumatate dependenta de dispozitiv a protocului Ethernet implementeaza 3 proceduri: una apelata de rutina independenta de dispozitiv ethPush pentru emisia unui cadru (lance_transmit), una apelata de sistemul de operare al hostului pentru a deservi o intrerupere de la adaptorul Lance (lance_interrupt_handler) si una apelata in faza de initializare a sistemului pentru initializarea dispozitivului Lance (nu este prezentata).

lance_transmit (Msg * msg)

Rutina lance_transmit preia un mesaj msg care urmeaza a fi trnsmis dispozitivului Lance. Rutina asteapta mai intai un semafor de numarare care se asigura ca dispozitivul dispune de un buffer de transmisie liber pentru a trata mesajul. Acest semafor (xmit_queue) este initializat la numarul de buffere de transmisie implementate de acest dispozitiv, de regula 64. aceasta inseamna ca maximum 64 de mesaje se pot afla in lista de transmisie in orice moment de tip (iar procesul de apelare are permisiunea sa returneze), iar cand un proces incearca sa adauge in coada al 65-lea mesaj, acesta este blocat. Orice numar de procese poate bloca acest semafor in timp ce incearca sa adauge acest mesaj in coada listei de transmisie.

Odata aparut in buffer de transmisie disponibil, procesul invocator se protejeaza fat de alte procese de transmisie prin asteptarea unui semafor de excluziune mutuala (mutex) si fata de alte servicii prin dezactivarea intreruperilor. Apoi rutina de transmisie foloseste operatia msgWalk pentru a traversa structura de date mesaj si pentru a extrage toate bufferele individuale care contin portiuni de mesaj. In acest exemplu, rutina de transmisie copiaza datele din bufferele de mesaj in bufferul de transmisie disponibil; o alternativa ar fi transmiterea catre dispozitiv a adreselor si lungimilor bufferelor individuale din mesaj. Apoi rutina semnalizeaza semaforul mutex, activeaza intreruperile si returneaza.

lance_interrupt_handler ( )

/* transmit interrupt */

if (csr & LE_TINT)

/* receive interrupt */

if (csr & LE_RINT)

enable_interrupt ( );

return

Rutina lance_interrupt_handler este folosita la tratarea unei intreruperi provenite de la adaptorul Lance. La invocarea acestei rutine inseamna ca sa petrecut una din urmatoarele: a survenit o eroare, a fost incheiata o cerere de transmisie sau a fost receptionat un cadru. In primul caz, instrumentul de tratare a erorilor afiseaza un mesaj si sterge bitii de eroare; rutina print_error inspecteaza CSR si raporteaza care au fost bitii setati. In al doilea caz se stie ca s-a incheiat o cerere de transmisie inserata in coada de lance_transmit, ceea ce inseamna ca in acest moment exista un buffer de transmisie liber, care poate fi reutilizat. Astfel, se semnalizeaza semaforul xmit_queue, care permite derularea unui proces blocat in lance_transmit.

Al treilea caz din lance_interrupt_handler – intreruperea receptiei – este cel mai interesant. Mai intai, sa remarcam bucla while. Aceasta permite procesarea tuturor cadrelor sosite cu o singura intrerupere; next_rcv_buf va returna intrari din lista cu descriptori a bufferului de receptie atat timp cat contine cadre care nu au fost inca procesate. (Fiecare intrare intr-o lista cu descriptori de receptie contine un indicator care indica daca intrarea respectiva este proprietatea hostului sau a adaptorului; next_rcv_buf foloseste acel indicator pentru identificarea cadrelor neprocesate.) In al doilea rand, fiecare intrare in lista cu descriptori de receptie – reprezentat de variabila rdl – contine un pointer atat catre un mesaj x-nucleu (o structura de date) cat si catre bufferul efectiv care implementeaza mesajul (o zona de memorie). Adaptorul intelege numai bufferul, dar trebuie sa ne reamintim carui mesaj ii apartine bufferul erspectiv, pentru a putea procesa mesajul cand bufferul a fost umplut cu date noi din retea.

Odata localizat mesajul (msg), vom aloca un proces care va determina mesajul sa parcurga graful de protocoale in sens ascendent; acest nou proces incepe prin executia punctului de intrare de jos in jumatatea independenta de dispozitiv a protocolului Ethernet, in speta ethDemux. Rutina ethDemux se comporta exact ca orice alta rutina de demultiplexare a unui protocol; demultiplexeaza cadrul catre o sesiune, bazandu-se pe campul de tip inclus in antet. De asemenea, mesajul este eliberat ca ultima actiune a rutinei ethDemux.

In acest moment, instrumentul de tratare a intreruperilor a terminat procesarea mesajului proaspat sosit; noul proces se va ocupa de rest. Cu toate acestea, instrumentul de tratare a intreruperilor trebuie sa pregateasca un mesaj de inlocuire si sa il instaleze in lista de descriptori de la receptie. In acest scop se va folosi operatia msgConstructAllocate si se va reseta intrarea din descriptorul bufferului pentru a fi curent atat cu noul mesaj cat si cu bufferul corespunzator.

O ultima idee. Se retine ca rutina lance_interrupt_handler nu asteapta semaforul mutex. Aceasta deoarece un singur proces poate rula in instrumentul de tratare a intreruperilor la un moment dat; pe un uniprocesor nu poate exista nici o alta sursa de interferenta intrr-un instrument de tratare al intreruperilor.

Document Info

Accesari: 1018
Apreciat:

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta

Creaza cont nou