Proceduri pentru controlul transferului unui flux de date - Controlul erorilor

Ne ocupam de comunicatii în care intervine un flux de unitati de date.

Prin unitate de date vom întelege, în general, un octet sau un sir de octeti. Vom

distinge segmentele de date transferate între utilizatorul si furnizorul serviciului, numite

unitati de date de serviciu (SDU).

1. Functii care intervin în transferul unui flux de date.

Structurarea si manevrarea fluxului de date (pe nivelul (N)):

• La transmisie,

din (N)-SDU sunt create segmente de date care sunt încapsulate în (N)-PDU, în

vederea transmiterii catre entitatea de protocol-(N) corespondenta,

- din (N)-PDU sunt create (N-1)-SDU, care sunt livrate nivelului (N-1) pentru transfer.

• La receptie,

- din (N-1)-SDU sunt extrase (N)-PDU si interpretate,

- din fluxul de (N)-PDU se extrag segmentele de date, se reconstituie (N)-SDU (daca este cazul) si sunt livrate utilizatorului.

Am notat cu PDU unitatile de date de protocol.

În procesul de creare a (N)-PDU si reconstituire a (N)-SDU pot sa intervina

proceduri de segmentare/reasamblare si/sau grupare/degrupare, care adapteaza dimensiunea (N)-PDU în functie de anumite constrângeri, de exemplu dimensiunea buffer-elor sau eficienta transferului.

• Controlul erorilor:

Daca serviciul (N) prevede cerinte privind reconstituirea fluxului de date care sunt

superioare posibilitatilor oferite de serviciul (N-1), protocolul (N) trebuie sa

dispuna de mecanisme adecvate de detectare si corectare a erorilor.

• Controlul fluxului:

Pe fiecare flux de date simplex, volumul de date transferat într-un interval de timp

este limitat de resursele de stocare si de prelucrare de care dispune entitatea

receptoare. Datele primite sunt memorate temporar în tamponul de receptie, în care

asteapta efectuarea prelucrarilor necesare reconstituirii fluxului originar si livrarea

catre utilizator, pe masura ce acesta le poate prelua.

Protocoalele trebuie sa asigure adaptarea de viteza între entitati, prin limitarea de

catre entitatea receptoare a volumului de date si a ritmului de transfer.

2. Proceduri pentru controlul erorilor.

Ne vom ocupa doar de erorile de secventa (pierderea, duplicarea, reordonarea unitatilor de date).

Consideram ca pachetele alterate sunt detectate folosind un cod detector de erori si sunt

eliminate, deci devin pachete pierdute. (Alterarea pachetelor se datoreaza în principal

perturbatiilor care apar pe canalul de comunicatie).

•Mecanisme cu confirmare protejate de temporizatoare:

Efectuarea unei operatii este confirmata. Diversele tipuri de erori pot afecta cereri de efectuare a unei operatii si confirmarile asociate. În consecinta, orice mecanism cu confirmare este protejat prin temporizare. Asteptarea confirmarii este cronometrata si,

la expirarea unei temporizari, se initiaza o procedura de recuperare. De obicei, procedura consta în repetari ale cererii. Anomalia poate fi irecuperabila, astfel încât numarul de repetari este limitat. Daca recuperarea esueaza, operatia se abandoneaza si se raporteaza utilizatorului esecul indeplinirii serviciului solicitat.

Numerotarea fluxului de date

Numerotarea permite verificarea reconstituirii secventei si controlul avansului

transferului, astfel încât este utila atât pentru controlul erorilor, cât si pentru controlul fluxului.

Domeniul valorilor numerelor de secventa este finit - pentru un câmp de n biti în

pachet, este disponibila secventa: S=0 ÷ (2ⁿ-1). Fie N=2ⁿ marimea domeniului de

valori.

• Controlul secventei (figura 1). Pentru fiecare flux simplex de date:

Transmitatorul si receptorul întretin câte un contor de secventa care indica

pozitia curenta în secventa de numerotare. Conventii:

în transmitator, contorul VS (S=Send) memoreaza limita secventei transmise, prin numarul urmatoarei unitati de date de transmis. Avanseaza modulo-N dupa transmiterea fiecarei unitati de date.

În receptor, contorul VR (R=Receive) memoreaza limita secventei continue receptionate, prin numarul urmatoarei unitati de date asteptate. Avanseaza modulo-N pe masura receptiei unitatilor de date în secventa continua.

Pentru transferul numerelor de secventa, pachetele contin câmpurile de

control:

NS = înscris cu valoarea curenta a contorului VS;

NR = înscris cu valoarea curenta a contorului VR.

Receptorul foloseste câmpul NS pentru identificarea pozitiei unitatii de date primite în fluxul de date.

Transmitatorul interpreteaza câmpul NR ca o confirmare a transferului corect al unitatilor de date precedente si memoreaza valoarea sa într-o variabila pe care o vom nota VA (A = Acknowledgement, confirmare).

Numerotarea segmentelor de date (cu lungime variabila) înscrise în PDU de

date se face astfel: fiecare segment transferat consuma o unitate în secventa de numerotare.

La transmisie, NS reprezinta numarul în flux al segmentului transmis, iar VS avanseaza la valoarea (VS + 1) mod N. La receptie, daca VR = NS, atunci VR avanseaza la valoarea VR = (VR + 1) mod N, deci,în confirmarea asociata, NR = (NS + 1) ,modN.

Figura 1. Controlul secventei într-un flux de date.

Transferul unei secvente de date

Transmitatorul trebuie sa memoreze segmentele de date transmise într-un buffer de transmisie pâna la confirmarea receptiei lor, pentru a le putea repeta în cazul unor incidente.

Variante:

- Procedura cu oprire si asteptare- transmitatorul se opreste dupa fiecare pachet de date transmis si asteapta primirea confirmarii (exista o singura unitate de date în curs de transfer). Transmitatorul poate opera, la limita, cu un buffer de transmisie capabil sa stocheze o singura unitate de date. Metoda este neeficienta pentru durate relatv mari ale transferului. Aceasta metoda a fost analizata în lucrarea de laborator numarul 2.

- Proceduri multi-pachet (figura 2) - transmitatorul trimite un grup de (maxim) n_t> 1

pachete de date fara a astepta dupa fiecare pachet transmis primirea confirmarii asociate (exista mai multe unitati de date în curs de transfer). Transmitatorul trebuie sa dispuna de un buffer capabil sa stocheze n_t unitati de date. Devine posibila o transmisie continua in masura în care confirmarile sunt primite în timp util.

În procedurile multi-pachet, pentru cronometrarea asteptarii confirmarilor se poate recurge la:

Temporizatar unic pentru toate segmentele de date transmise si neconfirmate (figura 2). Este o solutie simpla, mai putin exacta, dar convenabila în majoritatea cazurilor.

Temporizatoare individuale pentru fiecare segment de date transmis si neconfirmat. Exita diverse variante de control al temporizatoarelor

Figura 2. Transferul unui flux de date. Procedura multi-pachet.

Receptorul poate livra utilizatorului doar segmente de date numerotate în secventa continua. Segmentele de date sunt memorate într-un buffer de receptie pâna la livrarea lor catre utilizator.

Duplicatele sunt eliminate. Exista doua metode de tratare a unitatilor de date care nu respecta secventa (NS ≠VR):

eliminare si recuperare ulterioara prin repetare - este suficient un buffer pentru stocarea unitatii de date curente,

memorare pâna la completarea secventei - dispunând de un buffer (de ordonare) cu capacitatea de n_r>1 unitati de date, receptorul stocheaza unitati de date cu NS în intervalul (VR + 1) mod N .. (VR + n_r) mod N pâna când sosesc unitatile care lipsesc.

• Volumul maxim de date în curs de transfer. Daca receptorul utilizeaza un buffer de ordonare care poate memora o secventa cu lungimea n_r < N, transmitatorul poate trimite fara a astepta o confirmare secventa cu lungimea n_t≤ N – n_r.

Tipuri de confirmari în transferul unui flux de date

Confirmari pozitive. Pentru datele primite în secventa continua se utilizeaza confirmari pozitive cumulative: câmpul NR confirma toate unitatile de date cu numere de secventa anterioare. O solutie uzuala este trimiterea unui pachet cu confirmare pozitiva în replica la fiecare pachet de date care respecta secventa (NS = VR). Caracterul cumulativ permite însa confirmarea mai multor pachete DT cu un singur pachet AK (figura 3) si compensarea pierderii unor confirmari.

Într-un transfer duplex, pachetele de date pe un sens pot purta confirmari pentru sensul invers, prin adaugarea informatiei de stare în antetul pachetelor de date (câmpul NR=VR). Aceasta metoda, numita confirmare “piggy-back”, permite reducerea numarului de pachete de control.

• Confirmari negative. Pentru datele care nu respecta secventa, în completarea confirmarilor pozitive, se pot utiliza confirmari negative (pachete de respingere). Prin acestea receptorul solicita repetarea anumitor unitati de date:

Respingere neselectiva- toate unitatile de date începand cu NR (determina: VS←NR); notam REJ(NR) confirmarile negative neselective;

respingere selectiva doar unitatea de date cu numarul NR; notam SREJ(NR) confirmarile negative selective.

Receptorul transmite o confirmare negativa atunci când primeste un pachet DT care nu respecta secventa (NS≠VR)

Dupa transmiterea unei confirmari negative, receptorul nu mai transmite alte confirmari negative cât timp persista conditia care a cauzat-o. Aceasta regula evita efectuarea repetata a retransmisiei solicitate de confirmarea negativa

Fig. 3. Transferul confirmarilor pozitive cu un singur pachet AK, ce poate cpnfirma un grup de unitati de date. (confirmare pozitiva cumulativa)

Restabilirea transferului de date în situatii de eroare.

Situatiile sunt detectate de transmitator prin:

Primirea unei confirmari negative (daca este prevazuta în procedura).recuperarea se face prin retransmiterea datelor indicate de confirmarea negativa.

Expirarea temporizatorului asociat asteptarii confirmarii datelor transmise. În acest caz se initiaza o procedura de recuperare care consta în:

repetarea automata a datelor neconfirmatesau

un dialog cu receptorul pentru determinarea starii sale curente, urmat de o eventuala retransmitere a datelor (considerate a fi ) pierdute.

3. Exemple de proceduri

proceduri cu retransmisie neselectiva

• Receptorul accepta doar unitatile de date în secventa continua (NS=VR) si elimina celelalte unitati. Aceasta solutie simplifica substantial receptorul, deoarece evita activitatea complexa asociata ordonarii unitatilor care nu sosesc în secventa (buffer si procedura de ordonare).

Transmitatorul utilizeaza o procedura de recuperare care consta, în esenta, în reluarea integrala a transmisiei datelor neconfirmate (reluare de la numarul de secventa VA).

Variante, din punct de vedere al confirmarilor utilizate:

• Se folosesc doar confirmari pozitive si recuperarea este initiata doar la expirarea temporizarii (fig.4.a.).

Se folosesc, în plus, confirmari negative care reluarea transmisiei de la numarul de secventa NR (respingere neselectiva) (figura 4.b.).

Recuperarea dupa expirarea temporizatorului se poate face prin:

retransmitere automata a datelor neconfirmate (figura 4.a ) sau

dialog initiat de transmitator pentru a afla starea curenta a receptorului,urmat de eventuala retransmitere a datelor neconfirmate (figura 5.a.).

Dialogul este initiat prin repetarea unui pachet de date (de obicei ultimul neconfirmat) sau trimiterea unui pachet de control pentru care este prevazut un raspuns. Pentru realizarea dialogului se adauga în pachetul AK un câmp care distinge semnificatiile posibile: interogare, raspuns la interogare, replica normala la un pachet DT.Numarul de tentative de recuperare este limitat.

Figura 4. Controlul erorilor folosind proceduri cu retransmisie ,neselectiva

a). Fara confirmari negative, cu retransmisie imediata la expirarea temporizatorului.

b). Cu confirmari negative neselective.

Figura 5. Exemple de situatii pentru o procedura cu retransmisie neselectiva, confirmari negative (neselective) si dialog pentru aflarea starii receptorului la expirarea temporizatorului.

a).  Pierderea pachetului REJ. b). Situatie în care nu poate interveni confirmarea negativa. Notatii: AK(rq, NR) este interogare, iar AK(rp, NB.) este raspuns la interogare.

Proceduri cu retransmisie selectiva

• Receptorul accepta unitatile de date cu NS într-un interval VR ..( VR+n_r) mod N, cu n_r>1, chiar daca nu sunt în secventa continua, si asigura memorarea lor intr-un buffer de ordonare cu capacitatea n_r pâna la completarea secventei cu unitatile care lipsesc.

Transmitatorul utilizeaza o procedura de recuperare care consta, în esenta, în repetarea anumitor unitati de date dintre cele neconfirmate, considerate ca fiind pierdute.

Variante, din punct de vedere al confirmarilor:

Se folosesc doar confirmari pozitive si recuperarea este initiata doar la expirarea temporizatorului, prin repetarea unitatii de date cu numarul VA (figuna 6.a).

Se folosesc, în plus, confirmari negative care indica retransmiterea segmentului NR (respingere selectiva). Acestea pot grabi recuperarea erorilor, evitând asteptarea expirarii temporizatorului, dar pot indica doar câte un singur pachet lipsa (figura 6.b).

Se folosesc confirmari mixte, care confirma cumulativ secventa continua si indica (toate) segmentele primite peste secventa continua.

Figura 6. Controlul erorilor folosind proceduri cu retransmisie selectiva.

a). Fara confirmari negative. b). Cu confirmari negative selective.

Recuperarea dupa expirarea temporizatorului se face printr-un dialog initiat de transmitator printr-un pachet la care este prevazut ca receptorul sa raspunda:

repetarea primei unitati de date neconfirmate (presupusa pierduta) (figura 4) sau

- trimiterea unui pachet de control, pentru aflarea starii curente a receptorului, urmata de eventuala repetare a datelor pierdute.

Numarul de tentative de recuperare este limitat.

Observatii:

Retransmisia selectiva este mai eficienta decât cea neselectiva în conditii de produs banda-întârziere mare, în care un volum important de date se poate afla permanent în curs de transfer. În astfel de conditii, o procedura cu retransmisie neselectiva ar repeta toate datele în curs de transfer la pierderea unui singur pachet.

4. Descrierea procedurilor de control al erorilor analizate în aceasta lucrare.

Sunt analizate urmatoarele solutii pentru controlul erorilor:

1. retransmisie neselectiva Go Back N cu/fara confirmari negative,

2. retransmisie selectiva cu/fara confirmari negative,

3. retransmisie neselectiva cu dialog la expirarea temporizatorului.

Graful tranzitiilor de stari pentru protocolul de nivel N este similar celui prezentat în lucrarea de laborator numaruI 2, difera doar transmisia si receptia datelor în starea de conexiune stabilita (“open”) astfel:

pentru prima varianta Go Back N cu retransmisie neselectiva automata la expirarea temporizatorului:

Fig. 4.1. Detalierea transmisiei si receptiei datelor pentru procedura Go Back N

- varianta cu retransmisie selectiva:

Fig. 4.2. Transmisie si receptie date pentru procedura de retransmisie selectiva

Notatii:

xt reprezinta expirarea temporizatorului.

cnt este controlul încercarilor de transmisie/retransmisie a unei unitati de date.

În descrierea tranzitiilor din specificatia Estelle sunt folosite functii si proceduri:

store_sdu_in_tbuf, salveaza în buferul de la transmisie datele sosite de la utilizator în vederea transmiterii lor ulterioare spre mediu,

data_to_send verifica daca exista date în buferul de transmisie,

can_send_data verifica daca numarul de unitati de date transmise si neconfirmate este mai mic decât un numar maxim prevazut, în functie de numarul maxim pentru numerotarea secventei de date,

store_in_rbuf memoreaza în buferul de la receptie datele sosite

ack_sent-data elibereaza buferul de transmisie de unitatile de date ce au fost confirmate.

Graful starilor pentru sistemul ce asigura procedura de retransmisie cu dialog la expirarea temporizarii este reprezentat în fig.4.3. Sistemul are în plus starea dialog în care trece la expirarea temporizarii.

5. Desfasurarea lucrarii.

Se vor simula interactiv cele trei proceduri pentru controlul erorilor si se va urmari functionarea acestora.

5.1. Simularea procedurii cu retransmisie neselectiva

Initierea simularii. Se lanseaza în executie simulatorul prin comanda ./l3v1.edb –n. dupa aparitia prompterului edb>,se încarca fisierul de comenzi si macrodefinitii S3 cu comanda S3().

Configuratia de simulare corespunde figurii 3.1 din lucrarea 2. Sa se analizeze structura de instantieride module, afisata cu comanda d $h.

-Scenarii simulate. Una dintre macrodefinitiile isc1 ÷isc5 din fisierul S3, este apelata automat la încarcarea fisierului. Aceasta initializeaza specificatia si înscrie valorile parametrilor scenariului simulat în variabilele modulelor Estelle. Oricare dintre macrodefinitii poate fi folosita pentru reinitializarea scenariului, cu alte valori ale parametrilor, determinând o evolutie diferita a sistemului.

Valorile parametrilor pot fi modificate apoi manual, din mediul edb.pentru simulari repetate, cu alti parametri, se apeleaza start() si apoi isc1()÷isc5().(isc1 este varianta implicita de evolutie a sistemului).

(a). Simularea procedurii cu confirmari negative

În scenariul S3 este selectat implicit modul cu confirmari negative.

Se vor executa variantele:

Isc1- stabilire cu succes a unei conexiunisi deconectare la terminare transmisie date, cu #sc=1,

Isc1- tot stabilire cu succes a conexiunii, dar deconectarea se face la terminarea livrarii datelor, se obtinepentru valoarea variabilei #sc:=6

Isc2- utilizatorul apelat refuza stabilirii conexiunii,

Isc3- furnizorul refuza stabilirea,

Isc4- initiatorul abandoneaza stabilirea,

Isc5- coliziune de ConReq, când ambii utilizatori încearca simultan stabilirea unei conexiuni,pentru cazul cu eroride tipul pierderi de pachete, în fiercarefaza a comunicatiei pe conexiune.

Se vor pierde unitatile de date sau confirmarile acestora folosind comanda mp1() sau mp2() în timpul simularii atunci când pachetul a ajuns în mediul de comunicatie.

Sa se studieze comportarea protocolului si sa se deseneze diagramele pachetelor transferate pentru fiecare caz, completând pe diagrama valorile variabilelor va, vs, vr. Aceste valori se pot vizualiza folosind din edb comanda dst(), apelând astfel macrodefinitia cu acelasi nume.

(b). Simularea procedurii fara confirmari negative.

Se seteaza valorile variabilelor ce permit selectarea modului fara confirmari negative astfel: #p1->rej_opt:=false si #p2->rej_opt:=false

Se simuleaza functionarea pentru variantele de evolutie a sistemului din 5.1.a. si se vor desena diagramele pachetele transferate.

5.2. Simularea procedurii cu retransmitere selectiva.

Initierea simularii se obtine cu comanda ./13v2.edb –n. Apoi se încarca fisierul de comenzi si macrodefinitii S3 cu comanda S3().

Configuratia de simulare este aceeasi ca si la 5.1.

scenariile simulate se obtin cu una dintre macrodefinitiile isc1÷isc5 din fisierul S3.

(a)    Simularea procedurii cu confirmari negative. Acesta este modul setat implicit

(b)   Simularea procedurii fara confirmari negative. Se obtine setând valorile variabilelor de obtiune srej la valoarea false: #p1->srej_opt:=false si #p2->srej_opt:=false.

Se vor desena diagramele pachetelor transferate pentru cazurile cu erori de pierderi a pachetelor.

5.3. Simularea procedurii cu retransmitere neselectiva si dialog la expirarea temporizarii

Variantele de proceduri prezentate în 5.1. si 5.2. sunt cu retransmisie automata la expirarea temporizarii daca nu soseste un pachet de confirmare negativa. În continuare este prezentata procedura prin care transmitatorul care nu a primit un raspuns, pozitiv sau negativ de la receptor în timp util, initiaza o procedura de interogare cu pachete de control a receptorului asupra starii acestuia

Initierea simularii se obtine cu comanda ./l3v3.edb –n. Apoi se încarca fisierul de comenzi si macrodefinitii S3 cu comanda S3().

Variantele de evolutie a sistemului se obtin cu isc1÷isc5.

Se vor desena diagramele pachetelor transferate pentru cazurile cu erori de pierderi a pachetelor.

Observatii:

1.În timpul simularii se pot vizualiza doar tranzitiile executate de catre utilizatori folosind tr:=2 sau cele executate de catre utilizatori si mediu cu tr:=3 sau, doar tranzitiile executate de catre entitatile protocol cu tr:=4

Implicit sunt vizualizate tranztiile executate de catre entitatile de la toate cele trei nivele (utilizator, mediu, si protocol).

2. Se va folosi macrodefinitia dst, apelata cu comanda dst() pentru a observa starea la transmisie si la receptie: valoarea variabilelor va, vr, vs precum si continutul buffer-elor la transmisie si la receptie.

Se vor executa simulari pentru diverse evolutii ale sistemului: isc1, isc2, …isc5.

În faza de transfer de date se vor pierde pachete de date, pachete de confirmare pozitiva (AK) sau confirmare negativa (REJ sau SREJ). Deasemeni se poate seta în timpul simularii modul de recuperare fara confirmari negative.

Tema: Se vor reprezenta diagramele cu pachete transferate între entitatile protocol pentru cazuri mai reprezentative cu pierderi de pachete de date si de confirmare.Se va urmarii functionarea sistemului prin simulare pentru fiecare scenariu pâna când acesta ajunge în starea de blocare activa deadlock.

Se vor reprezenta pe diagrame valorile variabilelor va, vr, vs la fiecare moment al executiei unei tranzitii.