| CATEGORII DOCUMENTE |
Protocoale cu fereastra glisanta
Date fiind dezavantajele protocolului de tip pas-cu-pas de a fi numai unidirectionale (simplex) si de a se potea bloca daca pauza de asteptare de la emitator este prea mica, s-au cautat alte protocoale care sa ramana sincronizate in conditiile oricaror combinatii de cadre alterate si de pauze de asteptare prea scurte. Astfel de protocoale sunt cele din clasa cu fereastra glisanta sliding window
In aceste protocoale, fiece cadru emis contine un numar de ordine de la 0 la 2n - 1 (deci necesita un camp de n biti pentru acesta). Protocolul pas-cu-pas utilizeaza valoarea n = 1 (numarul de ordine putand fi 0 sau 1).
La baza protocoalelor cu fereastra glisanta sta faptul ca, in orice moment, emitatorul mentine o lista cu cele n numere de ordine consecutive corespunzatoare cadrelor carora li se permite sa fie transmise fara a se astepta confirmarea fiecaruia in parte. Se zice ca aceste cadre se afla in fereastra de emisie sending window Receptorul accepta pachetele numai in ordinea corecta (am mentinut ipoteza ca protocolul va livra pachetele nivelului de retea destinatar in aceeasi ordine cu cea in care au fost trecute nivelului DLC de la emisie, ca si ipoteza ca mediul fizic livreaza cadrele in ordinea in care acestea au fost transmise) si trimite cereri de numere de ordine (RN) catre emitator; efectul unei anumite RN este de a confirma toate pachetele anterioare lui RN si a cere transmiterea pachetului cu numarul de ordine RN
Mai clar, nodului emitator A nu i se permite sa transmita pachetul i + n pana cand pachetul i nu a fost confirmat (adica pana cand nu i s-a cerut sa transmita pachetul i + 1). Astfel, daca RN = i este cea mai recenta cerere primita de la receptorul B, la A va exista o "ferestra" de n pachete (de la i la i + n -1) pe care emitatorul are voie sa le transmita.
Cand un nou pachet soseste de la nivelul de retea la nivelul DLC al emitatorului, el primeste numarul de ordine urmator celui maxim din fereastra - deci limita superioara a ferestrei se deplaseaza cu 1 unitate. Cand vine o confirmare, limita inferioara a ferestrei avanseaza cu 1 unitate. Astfel, fereastra mentine permanent o lista a cadrelor trimise si neconfirmate, "alunecand" spre numere de ordine tot mai mari (de aici si numele acestei clase de protocoale).
Intrucat cadrele din fereastra de emisie pot fi alterate sau pierdute in timpul transmisiei, emitatorul trebuie sa pastreze toate aceste cadre in memorie pentru o posibila retransmisie. Pentru o ferestra de dimensiune n, emitatorul are nevoie de n buffere pentru a stoca cadrele neconfirmate. Daca fereastra creste pana la dimensiunea ei maxima, nivelul DLC al emitatorului trebuie sa opreasca nivelul sau de retea sa mai paseze pachete pana cand un buffer devine liber.
Si receptorul mentine o fereastra de receptie receiving window ce corespunde cadrelor pe care receptorul are voie sa le accepte. Fereastra emitatorului si cea a receptorului nu trebuie sa aiba aceleasi limite inferioara si superioara si nici macar aceeasi dimensiune. Orice cadru sosit la receptor si care nu face parte din fereastra de receptie nu va fi acceptat. Cand se primeste un cadru cu numarul de ordine egal cu limita inferioara a ferestrei de receptie, el este pasat nivelului de retea receptor si se genereaza o confirmare; fereastra se va deplasa cu o unitate. Spre diferenta de fereastra emitatorului, fereastra receptorului ramane intotdeauna la dimensiunea sa initiala.
K Observatii
Dupa m deplasari (unde m este numarul de biti pentru SN), o fereastra de dimensiune n poate contine aceleasi numere de ordine ca initial (nu e nevoie de o incrementare permanenta a numerelor de ordine - care ar complica si "inscrierea" ei). De aceea se poate vorbi de "rotatia ferestrei".
O fereastra receptoare de dimensiune 1 inseamna ca nivelul DLC receptor accepta cadrele doar in ordine, dar pentru n > 1 nu se intampla asa; oricum, nivelul de retea receptor primeste intotdeauna pachetele in ordinea corecta, indiferent de dimensiunea ferestrei.
Iata un exemplu cu n = 1 pentru un numar de ordine pe 3 biti (de la 0 la 7).
Initial, nu exista cadre de transmis, deci limitele inferioara si superioara ale ferestrei sunt egale.
Cazul n =1, desi prezinta o serie de avantaje fata de protocolul pas-cu-pas (este bidirectional si mai robust - adica suporta orice combinatie de erori si pauze de asteptare fara a provoca pierderi sau dublari de pachete), prezinta si un neajuns. Pana acum am facut presupunerea tacita ca timpul necesar unui cadru pentru a ajunge la destinatie plus timpul de transmitere a confirmarii constituie o durata neglijabila - ceea ce este fals. Iar timpul de propagare dus-intors poate avea implicatii importante asupra eficientei de utilizare a largimii de banda.
Astfel, de exemplu, sa consideram un canal de satelit de capacitate 50 [kbiti/s] cu o durata de propagare dus-intors de 500 [ms]. Se vor transmite, cu ajutorul protocolului cu fereastra glisanta de largime n = 1, cadre de lungime l = 1000 biti. La t = 0, emitatorul incepe sa transmita primul cadru. La t [ms], cadrul a fost complet transmis. In cele mai bune conditii (adica fara asteptare pentru servire la receptie si pentru un cadru de confirmare scurt), cadrul cu date emis va ajunge de abia la t = 270 [ms], iar confirmarea va ajunge la emitator de abia la t = 520 [ms]. Aceasta inseamna ca emitatorul a fost blocat pe 500/520 = 96 % din timpul total - cu alte cuvinte, a folosit doar 4 % din largimea de banda disponibila.
Este clar ca o combinatie intre un timp lung de propagare, o largime de banda mare si o lungime mica a cadrelor duce la un rezultat dezastruos in ceea ce priveste eficacitatea utilizarii canalului. Cauza o constituie algoritmul de transmisie, care cere ca emitatorul sa astepte confirmarea unui cadru inainte de a-l putea transmite pe urmatorul. Solutia o constituie permisiune ca emitatorul sa transmita n > 1 cadre inainte de a fi blocat in asteptarea confirmarii. Alegand convenabil largimea n a ferestrei, emitatorul va fi capabil sa transmita continuu cadre pe o durata egala cu timpul de propagare dus-intors, fara sa umple fereastra.
In cazul exemplului de mai sus, va trebui ca n 26. Daca emitatorul incepe sa transmita primul cadru la t = 0, atunci la t = 520 [ms] el a terminat de transmis cele 26 cadre (n = 26) si tocmai primeste confirmarea pentru cadrul cu numarul de ordine 0. Apoi, confirmarile vor sosi la fiecare 20 [ms], astfel incat emitatorul va avea permanent permisiunea sa transmita (daca are ce transmite). In orice moment vor exista 25 sau 26 de cadre transmise si neconfirmate inca. Deci dimensiunea maxima a ferestrei de emisie este de 26.
Aceasta tehnica de transmisie este numita pompare pe conducta banda de asamblare pipelining]. Daca avem o capacitate a canalului fizic de C [biti/s] ]i o dimensiune a cadrului de l [biti], iar durata de propagare dus-intors este de 2t [s], timpul necesar transmiterii unui cadru va fi l C [s]. Dupa ce a fost transmis ultimul bit al cadrului, exista un interval de timp de t [s] pana ce acest bit sa ajunga la receptor si (presupunand ca timpul de asteptare si de servire la receptor 0) inca t [s] pentru ca sa primeasca confirmarea. La protocolul pas-cu-pas, linia este ocupata timp de l C si este libera timp de 2t , rezultand un grad (eficacitate) de utilizare a liniei de l l Ct). Daca l < 2Ct , rezulta S < 50 %. Dar, intrucat, in realitate, avem t > 0 pentru propagarea inapoi a confirmarii, metoda pomparii poate fi utilizata, in principiu, pentru a folosi linia in acest timp, dar daca t este mic, complexitatea introdusa suplimentar de aceasta metoda de transmitere nu este justificata.
Pomparea cadrelor pe o linie nefiabila ridica unele probleme serioase, precum: ce se intampla daca se pierde sau se altereaza un cadru din mijlocul unui sir lung de cadre? Este posibil ca un sir lung de cadre (pentru o fereastra de emisie de dimensiuni mari) sa soseasca la receptie mai inainte ca emitatorul sa fie instiintat ca vreun cadru n-a ajuns corect. Evident, un cadru alterat va fi refuzat la receptie. Dar ce trebuie sa faca receptorul cu cadrele sosite corect dupa cadrul alterat? (A nu se uita ca nivelul DLC al receptorului trebuie sa livreze in ordine pachetele catre nivelul sau de retea).
Exista doua metode de a face fata erorilor de transmisie la tehnica pomp`rii cadrelor:
a Metoda intoarcerii cu n inapoi [go back n]
In aceasta metoda, receptorul neglijeaza pur si simplu cadrele ce urmeaza unui cadru sosit cu eroare - chiar daca acestea sunt corecte -, ne transmitand nici o confirmare.
Aceasta strategie corespunde unei ferestre de receptie cu largimea 1, nivelul DLC de la receptie refuzand sa accepte orice cadru cu exceptia celui ce contine urmatorul pachet pe care trebuie sa-l livreze nivelului sau de retea. Daca fereastra de emisie se umple inainte ca pauza de asteptare sa expire, "conducta" de cadre va incepe sa se goleasca. In final, pauza de asteptere se va termina si emitatorul va retransmite toate cadrele neconfirmate, in ordine, incepand cu cel alterat sau pierdut.
Sa analizam mai amanuntit efectele erorilor de transmisie asupra acestui algoritm, pentru cazul n = 4:
Cel de al doilea cadru, purtand pachetul numarul 1, ajunge eronat la B. Ca atare, nodul B continua sa ceara pachetul 1 (RN cu fiecare cadru de confirmare trimis spre A. Pachetele 2, 3 si 4 de la A ajung in B fara erori, dar nu sunt acceptate, intrucat B asteapta pachetul cu SN Dupa ce A a transmis pachetul cu SN = 4, epuizandu-si fereastra de emisie - care este inca isi incheie si pauza de asteptare si reia transmisia de la pachetul 1, trimitand ulterior si pachetele 2, 3 si 4, care se presupune ca ajung fara eroare la B. Cand vine la A confirmarea RN = 1, fereastra de emisie "aluneca" la
Sa urmarim acum efectul erorilor asupra confirmarilor de la B spre A:
Primul cadru de confirmare, purtand SN = 1, este alterat in transmisie, dar nu creaza probleme, caci este urmat de o confirmare (RN = 2) care ajunge corect si aceasta confirmare ajunge la A mai inainte ca pachetul cu numarul de ordine 3 (ultimul pachet al ferestrei curente de emisie) sa fi fost complet transmis si ca pauza de asteptare sa fi expirat - ceea ce se traduce la A ca o confirmare a ajungerii corecte la B a pachetelor 1 si 2. Cel de al doilea cadru de confirmare alterat (purtand RN = 3) provoaca retransmisia, intrucat urmatorul cadru de confirmare (avand RN = 4) este intarziat pana cand A isi transmite intreaga fereastra si isi epuizeaza pauza de asteptare; aceasta face ca A sa se intoarca cu transmisia de la pachetul 2.
K Observatii Se constata ca - asa cum stau lucrurile in exemplul ales -, in cazul unei ferestre de emisie de lungime mica si a unor cadre cu date lungi de la B la care sa se ataseze confirmarile, o eroare a confirmarii poate intarzia confirmarile pana cand ultimul pachet al ferestrei de emisie de la A este transmis, facand ca emitatorul A sa astepte sau sa se intoarca pentru retransmisie. Mai observam ca, atunci cand o confirmare intarziata ajunge la emitator, acesta poate executa un salt inainte (in cazul exemplului, de la pachetul 3 la pachetul 5).
Este posibil sa apara retransmisii chiar in absenta erorilor de
transmisie. Acesta se intampla in
cazul unor cadre lungi intr-un sens (de la A spre B) si a unor cereri de pachete ajungand
la emitator (in A) cu
intarziere. Iata un astfel de caz:
Cererea RN = 1 ajunge la timp pentru a permite pachetului 4 sa fie trimis, dar, dupa trimiterea pachetului cu SN = 4, nodul A termina pauza de asteptare si se intoarce la pachetul 1.
Dam mai jos regulile pentru protocolul intoarce cu n inapoi - presupunand ca SN si RN sunt numere intregi ce pot creste nelimitat (in practica, ele sunt modulo m):
- Regulile nu privesc initializarea protocolului: vom presupune ca, initial, nu sunt cadre de transmis pe linie, ca nodul A incepe sa transmita pachetul 0 si ca nodul B asteapta pachetul 0 (vom aborda mai incolo modul de initializare).
- Emitatorul utilizeaza variabilele SNmin si SNmax pentru fereastra (SNmin este cel mai mic numar de ordine al unui pachet care nu a fost inca confirmat si reprezinta limita inferioara a ferestrei de emisie; iar SNmax denota numarul de ordine al urmatorului pachet ce va fi preluat de la nivelul de retea). Deci nivelul DLC de la emitator va incerca sa transmita pachetele de la cel cu numarul de ordine SNmin pana la cel cu numarul de ordine SNmax (pastrate in buffere pentru eventuala retransmisie).
Iat` acum algoritmul intoarce cu n inapoi
La emi`tor (nodul A):
Initializeaza SNmin SNmax
Executa pasii si repetat, in orice ordine. Pot exista intarzieri arbitrare - dar limitate - intre momentul cand sunt satisfacute conditiile pentru un pas si momentul cand pasul este executat.
Daca
SNmax < SNmin + n
si daca este disponibil un pachet de la nivelul de retea, accepta un nou pachet in DLC, ii atribuie numarul de ordine SNmax si incrementeaza SNmax
Daca se primeste un cadru fara eroare de la B, continand
RN > SNmin
atunci creste SNmin pana cand
SNmin RN
Daca
SNmin < SNmax
si nu exista nici un cadru aflat in curs de transmisie, se alege un numar
SN I SNmin SNmax
se transmite pachetul cu numarul de ordine SN intr-un cadru, punand valoarea lui SN in antetul lui, in campul rezervat numarului de ordine. Se permite cel mult o intarziere limitata intre transmisiile la intervale succesive ale pachetului cu SNmin , daca SNmin nu se modifica.
La receptor (nodul B):
Initializeaza RN = 0 si repeta la nesfarsit pasii si
Ori de cate ori se primeste un cadru fara erori de la A, continand
SN RN
livreaza pachetul sosit nivelului de retea si incrementeaza RN
La momente arbitrare, dar cu intarzieri limitate dupa primirea oricarui cadru fara erori de la A, transmite un cadru catre A, continand RN in campul pentru numarul de ordine cerut.
Exista mai multe metode conventionale de a stabili temporizarile si ordinea diferitelor operatii din algoritmul dat.
Cel mai simplu ar fi ca nodul A sa initializeze un ceas ori de cate ori transmite un pachet. Daca timpul fixat la ceas expira inainte de sosirea confirmarii pentru acel pachet (adica inainte ca SNmin sa depaseasca numarul de ordine al acestui pachet), pachetul va fi retransmis. Cateodata, la utilizarea acestei metode, emitatorul, dupa ce se intoarce si retransmite pachetul cu SNmin , retransmite automat si urmatoarele pachete pana la cel cu numarul SNmax - 1, indiferent daca se primesc sau nu confirmarile cu cererile pentru urmatoarele pachete.
De exemplu, in cazul prezentat de erori la cadrele de confirmare pentru protocolul revenire cu , emitatorul ar fi putut trimite pachetul 4 dupa pachetul 3, in loc de pachetul 5. In conformitate cu algoritmul prezentat, aceasta corespunde situatiei ca emitatorul sa intarzie executarea pasului 4 atunci cand se afla in cursul retransmiterii ferestrei de pachete.
O alta posibilitate o constituie cea ca A sa revina la inceputul ferestrei dupa transmiterea tuturor pachetelor din fereastra.
De asemenea este posibil ca A sa raspunda unei cereri specifice a lui B pentru retransmisie. O astfel de comunicatie intre A si B poate fi considerata ca parte a acestei clase de protocoale, ghidand selectiile posibile din algoritm.
K Observatie Revenirea cu n reprezinta, in fond, o clasa de protocoale (algoritmi), caci nici temporizarile, nici modurile de organizare a retransmisiilor nu sunt precizate. Mai mult, nu se fixeaza nici modul de alegere a pachetelor intr-o fereastra.
Cea mai simpla metoda de temporizare la nodul B este atasarea valorii curente a RN la cadrele cu date transmise catre A (piggybacking), iar cand B nu are date de transmis lui A, sa trimita un cadru de confirmare izolat, continand RN, dupa fiecare receptie a unui cadru cu date nealterat trimis de A.
Dam in cele ce urmeaza un protocol de tip revenire cu n ce poate transmite o fereastra de largime w MAX_SEQ si in ipoteza ca nivelul de retea de la emisie nu are pregatit un pachet in orice moment, ci acesta provoaca un eveniment de tip Network_Layer_Ready cand are un pachet de transmis. La acest protocol, nivelul DLC de la emisie va impiedica nivelul sau de retea sa-i mai trimita pachete dupa ce fereastra s-a umplut (de fapt, buffer-ul), permitandu-i sa reia trimiterea de pachete atunci cand in fereastra s-a facut loc (prin transmiterea cu succes a unui numar de cadre de la inceputul ferestrei); aceasta se realizeaza prin intermediul functiilor disable_network_layer si respectiv enable_network_layer. Pe de alta parte, nivelul DLC receptor accepta cadrele in ordine; cadrele ce urmeaza dupa un cadru alterat de eroare nu mai sunt preluate. In acest protocol s-a adoptat o valoare MAX_SEQ = 7 (dar ea poate fi schimbata cu orice valoare impara).
/* Protocol Go_back_n */
#define MAX_SEQ 7 /* trebuie sa fie 2^n = 1 */
typedef enum event_type
/* evenimentele posibile
#include "protocol.h"
static boolean between(seq_nr a, seq_nr b, seq_nr c)
static void send_data(seq_nr frame_nr, seq_nr frame_expected, packet buffer
void gobackn(void)
confirmarea pachetului n implica confirmarile pachetelor n-1, n-2, etc. */
/* se verifica acest lucru */
while (between(ack_expected, r.ack, next_frame_to_send))
case cksum_err: ; /* cadrele eronate sunt ignorate */
case timeout: /* a expirat pauza de asteptare; se retransmit */
/* toate cadrele neconfirmate */
next_frame_to_send = ack_expected; /* retransmisia incepe de aici */
for (i=1; i<=nbuffered; i++)
if (nbuffered < MAX_SEQ)
enable_network_layer();
else
disable_network_layer();
Vom observa ca, in fiece moment, sunt gata de
transmis MAX_SEQ cadre (si nu MAX_SEQ + 1 !!), chiar
daca exista MAX_SEQ + 1 numere de
ordine
(SN MAX_SEQ
Pentru a intelege aceasta restrictie, sa consideram urmatorul scenariu pentru MAX_SEQ
1 - Emitatorul transmite cadrele de la 0 la 7;
2 - O confirmare, atasata la un cadru cu date, vine in fine la emitator;
3 - Emitatorul transmite alte 8 cadre, cu numerele de ordine 0 7;
4 - Soseste o noua confirmare (atasata) pentru cadrul numarul 7.
Se pune intrebarea: cele 8 cadre din al doilea lot au ajuns toate corect sau s-au pierdut toate (caci toate cadrele ajunse dupa un cadru eronat sunt ignorate) ? In ambele cazuri, receptorul trimitea confirmarea pentru numarul 7 si emitatorul nu are cum sa afle ce s-a intamplat. De aceea numarul maxim de cadre transmise trebuie limitat la MAX_SEQ
Fiecare cadru trebuie asociat unui alt ceas, caci pauza de asteptare pentru el poate fi diferita de cele pentru celelalte cadre. Aceste ceasutri pot fi usor simulate prin soft, utilizand un singur ceas hard care provoaca periodic intreruperi. Pauzele de asteptare formeaza o lista legata, pentru fiecare "nod " din lista indicandu-se cate tacturi sunt pana la expirarea pauzei de asteptare, numarul cadrului pentru care se marcheaza timpul si un pointer catre urmatorul nod.
Iata un exemplu:
Fie un ceas cu perioada de 100 [ms]. Fie timpul initial real 10.00:00.0. Sa admitem ca vor exista 3 pauze de asteptare: respectiv pana la 10:00:00.5, 10:00:01.3 si 10:00:01.9. La fiecare perioada a ceasului hard, timpul real este actualizat si ceasul din capul listei este decrementat. Cand contorul de perioade (tacturi) ajunge la 0, pauza de asteptare s-a terminat si nodul este eliminat din lista (vezi fig. b)).
Desi metoda necesita scanarea listei la apelarea functiilor start_timer si stop_timer, ea nu reclama multe operatiuni pentru fiecare tact.
p
Sa analizam acum performantele protocolului de tip revenire cu n
Daca SN si RN sunt numere intregi nemarginite, demonstrarea corectitudinii protocolului este similara cu cea pentru protocolul pas cu pas: vom presupune si aici ca toate cadrele alterate sunt depistate de CRC de la receptie, ca fiece cadru ajunge la destinatie corect cu o probabilitate q > 0 si ca sistemul este initializat corect (nu exista, initial, cadre in curs de transmisie, iar nodurile A si B incep amandoua cu pasul 1 din algoritmul lor).
Proprietatea de siguranta a protocolului de tip revenire cu n este exact aceeasi ca la protocolul pas cu pas: in speta, nodul B livreaza pachetele, in ordine, nivelului sau de retea, utilizand RN pentru a urmari viitorul pachet asteptat.
Pentru a demonstra durata de viata nelimitata, sa admitem ca, la A, la un anumit moment t , avem
SNmin = i
Fie t momentul la care pachetul i este receptionat corect si livrat nivelului de retea din B (daca aceasta nu se intampla, t ). Similar, fie t momentul la care este incrementat SNmin (daca aceasta nu se intampla, t
Fie RN(t ) valoarea variabilei RN din B in functie de timp si fie SNmin (t ) valoarea corespunzatoare a lui SNmin din A. Se constata direct din algoritm ca SNmin (t ) si RN(t ) nu sunt descrescatoare in timp. De asemenea, intrucat
SNmin (t ) este cel mai mare RN primit de la B pana in momentul t (daca s-a primit vreo astfel de confirmare), rezulta ca
SNmin (t ) RN(t )
Conform definitiilor lui t si t RN(t ) este incrementat la valoarea i in momentul t iar SNmin (t ) este incrementat peste valoarea i in momentul t . Tinand cont de inegalitatea de mai sus, rezulta ca
t < t
Se va observa ca este posibil ca
t < t
intrucat pachetul i s-ar fi putut sa fie receptionat fara eroare si livrat nivelului de retea din B mai inainte de momentul t si chiar mai inainte ca SNmin sa fi devenit egal cu i
Conform algoritmului, A transmite pachetul i in mod repetat, cu intarzieri finite intre retransmisiile succesive, de la t pana la t
Daca
t < t
rezulta ca
RN(t ) = 1 pentru t I [t , t
astfel incat prima receptionare fara erori a pachetului i dupa momentul t va fi acceptata, pachetul fiind livrat nivelului de retea din B. Intrucat t < t , A va retransmite pachetul i pana cand acesta va fi confirmat. Intrucat exista o probabilitate q > 0 ca fiece retransmisie sa fie receptionata corect, iar retransmisiile se fac la intervale finite, rezulta ca intervalul de la t la t este finit. Nodul B - indiferent daca t < t sau vice versa - transmite cadre continand RN i , de la momentul t pana cand un astfel de cadru este receptionat corect in A (la momentul t ). Cum A transmite si el cadre in acest interval, intarzierea intre transmisiile succesive de la B va fi finita si, intrucat q > 0, rezulta ca intervalul de timp de la t la t va fi finit.
Asadar am obtinut ca t este finit iar t < t si t < t . Utilizand acest fapt pentru fiecare valoare succesiva a lui SNmin , rezulta ca fiece pachet este transmis cu o intarziere finita - deci algoritmul are o durata de viata nelimitata.
Observatie Vom remarca faptul ca, in demonstratia de mai sus, nu s-a facut nici o presupunere privitoare la circulatia in ordine a cadrelor pe linie - deci algoritmul revine cu n lucreaza corect chiar in cazul in care cadrele circula fara o anumita ordine. Asadar, algoritmul se poate folosi si la nivelul de transport al retelelor de calculatoare. In acest caz, rolul nivelului legaturii de date va fi luat de subretea, iar rolul cadrului va fi jucat de pachet. In retelele de calculatoare transmitand cu metoda datagramelor, pachetele circula fara vreo ordine pana la destinatar - deci generalitatea algoritmului revine intoare inapoi cu n se dovedeste foarte utila.
p
Vom dovedi acum corectitudinea protocolului revine cu n si in cazul cand SN si RN sunt numere modulo m, cu m > n - daca se pastreaza conditia ca, pe linie, cadrele sa circule in ordine.
Sa analizam, insa, mai intai, cu atentie, ordinea evenimentelor atunci cand SN si RN sunt intregi nemarginiti.
Fie transmisia unui cadru oarecare de la A spre B. Sa presupunem ca acest cadru incepe sa fie generat la momentul t in A si este receptionat in B la momentul t
Numarul de ordine SN al cadrului transmis trebuie sa apartina ferestrei de emisie curente, din momentul t , de la nodul A, adica
SN I [SNmin (t , SNmin (t ) + n - 1
Valoarea i = SNmin (t trebuie
sa fie egala cu ultima valoare
receptionata a RN, care este
i RN (t RN (t
Rezulta
a
SNmin (t RN (t
Reciproc, nici un cadru cu numar de ordine SNmin (t ) + n nu putea fi transmis inainte de momentul t , caci aceasta valoare depaseste limita superioara a ferestrei de emisie. Intrucat cadrele circula in ordine pe linie, nici un cadru cu acest numar de ordine nu putea ajunge in B inainte de t . Rezulta ca
b
RN (t SNmin (t ) + n
Din (a b T
RN (t I [SNmin (t ) , SNmin (t ) + n - 1
Din (1), (2 T
Sa presupunem acum ca, atunci cand pachetul cu numarul SN este transmis, numarul de ordine din cadrul aferent este construit modulo m.
Fie
sn = SN (mod m )
Pasul al algoritmului de la receptor (B) trebuie modificat astfel:
Daca se primeste un cadru nealterat de la A, continand numarul de ordine sn dat de (4), livreaza pachetul nivelului de retea din B si incrementeaza RN
Intrucat am admis ca
m > n
din (3), (4), (5 T
sn = RN (mod m ) SN = RNPrin urmare, algoritmul lucreaza corect.
Sa analizam acum ordinea confirmarilor (RN) aferente ferestrei de emisia din A - utilizand numere intregi obisnuite (nemarginite).
Se constata imediat ca
RN I [SNmin (t ) , SNmin (t ) + n
Sa consideram acum ca RN este transmis modulo m si fie
rn = RN (mod m )
Atunci pasul al algoritmului de la emisie (A) trebuie modificat astfel:
Daca se primeste un cadru fara eroare de la B, continand
r n SNmin (mod m)
atunci incrementeaza SNmin pana cand
SNmin (mod m) = rn
Din cauza domeniului lui RN din (7), se constata ca noua regula este echivalenta cu cea veche, fiind suficienta pentru a putea transmite numerele de ordine ale pachetelor cerute in tehnica modulo m. Se constata, insa, ca nu este necesara memorarea lui SNmin SNmax si RN, la A si respectiv la B, ca numere intregi obisnuite (nemarginite); lucrand modulo m, algoritmul va functiona corect pentru m > n
Iata, deci, algoritmul revine intoarce inapoi cu n in cazul numerotarii modulo m
La emitator (nodul A):
Initializeaza snmin snmax
Repeta pasii si in orice ordine. Pot exista intarzieri arbitrare - dar limitate - intre momentul cand sunt satisfacute conditiile pentru un pas si momentul cand pasul este executat.
Daca
si daca este disponibil un pachet de la nivelul de retea, accepta un nou pachet in nivelul DLC, ii atribuie numarul de ordine snmax si incrementeaza snmax la (snmax + 1) (mod m)
Daca se primeste un cadru fara eroare de la B, continand o confirmare cu numarul de ordine asteptat r n si
(rn - snmin) (mod m ) (snmax - snmin) (mod m )
atunci face
snmin = rn
Daca
snmin snmax
si nu exista nici un cadru aflat in curs de transmisie, se alege un numar sn astfel incat
(sn - snmin) (mod m ) < (snmax - snmin) (mod m )
se transmite pachetul cu numarul de ordine sn intr-un cadru, punand valoarea lui sn in antetul lui, in campul rezervat numarului de ordine de la emisie ("SN"). Se permite cel mult o intarziere limitata intre transmisiile la intervale succesive ale pachetului cu snmin , daca snmin nu se modifica.
La receptor (nodul B):
Initializeaza r n = 0 si repeta la nesfarsit pasii si
Ori de cate ori se primeste un cadru fara erori de la A, continand
sn = r n
livreaza pachetul sosit nivelului de retea si incrementeaza r n la (rn + 1) (mod m)
La momente arbitrare, dar cu intarzieri limitate dupa primirea oricarui cadru fara erori de la A, transmite un cadru catre A, continand r n in campul pentru numarul de ordine cerut ("RN
p
Vom analiza in continuare eficacitatea utilizarii canalului de catre algoritmul intoarce revine cu n inapoi. Vom considera cazul atasarii confirmarilor la cadrele cu date in sens invers, astfel incat vom ignora aceste confirmari. De asemenea vom presupune, pentru simplitatea analizei, ca timpul de prelucrare a intreruperii este neglijabil, deci ca t reprezinta doar durata de propagare intr-un sens.
Precizam ca retransmisiile si intarzierile cauzate de epuizarea pauzei de asteptare apar in algoritmul intoarce revine cu n inapoi din urmatoarele 3 motive:
Largimea ferestrei de emisie si lungimea mai mare a cadrelor in sens invers decat a celor in sens direct.
Erorile ce afecteaza cadrele cu date.
Erorile ca afecteaza cadrele de confirmare.
Le vom analiza pe rand.
- A) Largimea ferestrei (w) de emisie. Distingem cazurile:
a) Fereastra este destul de larga astfel incat emitatorul poate transmite cu viteza maxima, intrucat confirmarile sosesc inainte ca fereastra de emisie sa se umple.
Durata de transmisie a unui cadru este l /C , astfel incat emitatorul poate continua transmisia pe durata w l /C , dup` care trebuie sa se opreasca daca primul cadru nu a fost confirmat. Prima confirmare poate sosi la t dup` ce primul cadru a fost transmis, deci confirmarea ajunge la momentul l /C t (am presupus ca primul cadru se construieste de la momentul t ). Emitatorul va putea transmite permanent daca
deci pentru o largime a ferestrei de emisie
.
Atunci
.
b) Daca fereastra de emisie este ingusta, emitatorul va trebui sa se opreasca la un moment dat, asteptand prima confirmare. Apoi va putea transmite inca un cadru, asteptand confirmarea lui, etc. Fiece ciclu consuma un timp l /C t , servind w cadre (respectiv wd biti de date). Rezulta ca
.
Asadar, pentru
rezulta
- B) Probabilitatea retransmisiilor cauzate de cadrele lungi care circula in sens invers poate fi scazuta prin cresterea parametrului n . Din p`cate, valoarea normala a modulului m in protocoalele standard este m = 8, ceea ce restrange valoarea numarului n la maximum 7.
Iata un exemplu in care - chiar pentru t = 0 - cadrele care circula in sens invers, avand o lungime de peste 3 ori mai mare ca a celor care circula in sens direct, pot cauza retransmisii pentru n
Se observa ca confirmarea
pentru pachetul 1 nu a ajuns la emitator (A) pana in momentul cand se termina
transmisia pachetului 6, provocand astfel o retransmisie a pachetului 0.
Se poate dovedi, de asemenea (recomandam cititorului sa o faca), ca, daca lungimile cadrelor au o distributie exponentiala, aceeasi pentru ambele sensuri, atunci probabilitatea p ca un cadru sa nu fie confirmat pana in momentul terminarii ferestrei de emisie (adica inainte de a se transmite urmatoarele n cadre) este
p = (1 + n ) -n
Ipoteza de mai sus este echivalenta cu urmatoarea situatie: momentele t de transmisie ale cadrelor au o distributie exponentiala, avand, de exemplu, o densitate de probabilitate
p (t ) = e -t (t
la terminarea transmisiei unui cadru se incepe transmisia urmatorului cadru (pentru ambele sensuri), momentele de transmisie sunt independente, iar duratele de prelucrare si de propagare sunt neglijabile.
Se va observa (recomandam cititorului sa arate acest lucru) ca multimea momentelor la care se termina transmisiile cadrelor la ambele noduri constituie un proces Poisson si ca un punct din acest proces este posibil cu probabilitate egala sa fie o terminare de transmisie la A sau la B, in conditii de independenta intre terminarile succesive de cadre.
Pentru n = 7, din ) rezulta
Uzual, cadrele au o lungime maxima posibila (dar, bineinteles, si o lungime minima, din cauza antetului si a marcajului terminal), astfel incat, in practica, p are o valoare ceva mai mica. Totusi, uneori, linia transporta cadre mai lungi intr-un sens decat in celalalt sens si, in acest caz, gradul de utilizare a liniei (eficienta) scade serios pentru n = 7. Cand durata de propagare este mare in raport cu lungimea cadrelor (ca la liniile de viteza mare si la legaturlile prin satelit), aceasta scadere a eficacitatii de utilizare a liniei poate fi destul de importanta. Din fericire, protocoalele standard au si alternativa de alegere a modulul m
Cand apar erori la transmisia in sens invers (la confirmare), confirmarea este amanata pana la urmatorul cadru care circula spre A. Aceasta scadere a eficacitatii de utilizare a liniei intr-un sens din cauza erorilor in celalalt sens poate fi evitata alegand largimea w a ferestrei de emisie (respectiv valoarea n) destul de mare.
Sa urmarim acum efectul erorilor asupra cadelor cu date. Daca n este destul de mare pentru a evita retransmisiile sau intarzierile cauzate de duratele lungi de propagare si de cadrele lungi sau de aparitia de erori in sensul opus si daca nivelul DLC emitator asteapta terminarea ferestrei pentru a putea retransmite, atunci se vor retransmite multe pachete pentru fiecare eroare aparuta la transmisia in sens direct. Solutia uzuala la aceasta problema o constituie utilizarea pauzelor de asteptare. In versiunea sa cea mai simpla, daca un pachet nu este confirmat pe durata unei anumite pauze de asteptare ce urmeaza transmisiei, pachetul va fi retransmis. Perioada de asteptare trebuie aleasa destul de lunga pentru a include durata de propagare dus-intors si durata de prelucrare, plus durata de transmisie pentru doua pachete de lungime maxima in sensul invers (spre A) - unul pentru cadrul in tranzit, cand se receptioneaza un pachet, si unul pentru a transporta noul RN. O versiune mai sofisticata este aceea in care nivelul DLC emitator (cand se cunosc duratele de propagare si de prelucrare) poate determina care cadru in sens invers va trebui sa poarte confirmarea pentru un anume pachet; el se intoarce inapoi daca acest cadru este fara eroare si nu livreaza confirmarea.
Cresterea eficacitatii de utilizare a liniei si scaderea intarzierilor se pot obtine efectuand intoarcerea inapoi rapid la aparitia unei erori in sensul direct, dar evitand retransmisiile cauzate de cadre lungi si erori in sensul invers. O posibilitate o constituie aceea ca nivelul DLC receptor sa transmita inapoi un cadru scurt de supraveghere la receptionarea unui cadru alterat, fapt ce permite emitatorului sa se intoarca inapoi mult mai devreme decat in cazul cand RN ar fi atasat la un cadru mai lung in sens opus.
a Metoda repetarii selective [selective repeat]
Chiar daca se elimina retransmisiile inutile, protocoalele de tip intoarce inapoi revine cu n trebuie sa retransmita cadre pe cel putin durata unei propagari dus-intors in situatia aparitiei unei singure erori in pachetul asteptat.
In multe situatii, liniile fizice sunt fiabile, prezentand o probabilitate a erorilor pentru un cadru transmis p In aceste cazuri, retransmisia unui numar mare de pachete pentru fiecare cadru alterat are un efect mic asupra eficacitatii de utilizare a liniei.
Sa consideram un protocol ideal de tip revine cu n, in care, de fiecare data cand un cadru purtator al unui pachet asteptat de nivelul DLC receptor este afectat de erori, nivelul DLC emitator va retransmite pachetele pe durata propagarii dus-intors. Fie g numarul probabil de cadre transmise de la A spre B pentru un pachet acceptat in B. Fie b numarul probabil de cadre transmise de la A spre B intr-un interval de propagare dus-intors - adica intre transmisia unui anumit cadru si receptionarea reactiei privitoare la acel cadru (inclusiv cadrul aflat in transmisie cand soseste reactia). Fie p probabilitatea ca un cadru sa ajunga in B cu erori (considerand cadrele succesive drept independente). Sa presupunem ca A transmite cadre incontinuu, ca n este destul de mare pentru ca A sa nu se intoarca inapoi in absenta reactiei si ca A se intoarce intotdeauna inapoi la urmatorul cadru, dupa ce a aflat ca, la receptie, cadrul asteptat a ajuns alterat.
Se poate arata (invitam cititorul sa demonstreze) ca:
g 1 + p (b g
Se observa ca eficacitatea utilizarii liniei este:
Se constata ca, pentru linii nefiabile (p de valori mari) sau linii de mare viteza ori de legaturi prin satelit (b de valori foarte mari), S va avea o valoare mica - irosindu-se astfel largimea de banda.
Pentru a remedia aceste neajunsuri se foloseste o alta subclasa a protocoalelor cu fereastra glisanta repetarea selectiva [selective repeat] La aceste protocoale, nivelul DLC receptor memoreaza toate cadrele corecte sosite dupa un cadru eronat (sau pierdut). Cand emitatorul afla ca un cadru din fereastra de emisie nu a ajuns corect la destinatie, el va retransmite numai acel cadru (nu si succesoarele lui). Daca retransmisia reuseste, nivelul DLC receptor va dispune acum de o secventa de cadre corecte, in ordine, pe care le poate pasa rapid nivelului sau de retea, confirmand numarul de ordine (cel mai mare) al ultimului pachet receptionat corect.
Deci, un astfel de protocol va accepta si pachete care nu sunt la rand (ordonate), dar au fost cerute sa fie retransmise. Va existra, ca la protocolul revine intoarce inapoi cu n, o fereastra de emisie de largime n, indicand cu cat o poate lua inainte A cu transmisia pachetelor fata de pachetul cu numarul de ordine cel mai mic nereceptionat inca corect in B. Dar fereastra de la receptie va fi acum mai larga decat 1. Orice cadru apartinand acestei ferestre poate fi acceptat si memorat (in buffer) pana cand toate cadrele precedente si-au descarcat pachetele in nivelul de retea receptor. Fereastra de emisie incepe cu largimea 0 si creste pana la n ; fereastra de receptie este de largime fixa, egala cu n
Receptionarea nesecventiala a cadrelor ridica insa o problema care nu aparea la protocoalele in care cadrele erau acceptate doar in ordine. Sa ilustram aceasta problema printr-un exemplu:
Sa presupunem ca m = 3, deci n
Nodul A transmite cadrele cu pachetele cu numere de ordine de la 0 la 6.
Intre timp, fereastra receptorului permite acceptarea oricarui cadru cu numarul de ordine de la 0 la 6 (inclusiv). Daca toate cele 7 cadre transmise ajung corect, receptorul le va confirma si isi va glisa fereastra, permitand receptionarea cadrelor cu numerele de ordine: 7, 0, 1, 2, 3, 4 sau 5. Toate cele 7 buffere sunt marcate drept goale.
Sa presupunem ca toate confirmarile sunt alterate. Emitatorul isi va termina pauza de asteptare si va retransmite cadrul cu pachetul cu nr. 0. Cand acest cadru ajunge la receptor, el este verificat daca apartine ferestrei de receptie. El va apartine noii ferestre, deci va fi acceptat. Receptorul va transmite (prin atasare) confirmarea pentru cadrul cu pachetul nr. 6 - intrucat au fost receptionate pachetele 0 6.
Emitatorul va traduce situatia ca o transmisie reusita a cadrelor, avansand fereastra de emisie si transmitand cadrele cu pachetele 7, 0, 1, 2, 3, 4 si 5. Cadrul cu SN = 7 va fi acceptat de receptor, pachetul din el fiind pasat nivelului de retea. Apoi, imediat, nivelul DLC receptor va verifica daca are deja un cadru corect cu pachetul cu numarul 0; va constata ca il are si va pasa pachetul din acest cadru nivelului sau de retea. Astfel, nivelul de retea receptor va primi un pachet incorect, deci protocolul va da gres.
Cauza care sta la baza acestei incorectitudini este faptul ca, dupa ce receptorul isi avanseaza fereastra, noul interval de numere de ordine valide se suprapune cu cel vechi. Urmatorul lot de cadre poate fi ori de dubluri (daca toate confirmarile s-au pierdut) ori de cadre noi (daca toate confirmarile au fost receptionate corect) si receptorul nu are cum sa distinga aceste doua situatii.
Calea de rezolvare a acestei dileme consta in a ne asigura ca, dupa ce receptorul a avansat fereastra sa, nu exista o suprapunere cu fereastra anterioara. Pentru a fi siguri ca nu exista suprapunere, dimensiunea maxima a ferestrei va trebui sa fie egala cu cel putin jumatate din valoarea lui m , adicam 2n
tinand cont ca
MAX_SEQ = m + 1
]i
w = n ,
se ia in practic`
.
De exemplu, pentru m = 4, obtinem MAX_SEQ = 15 si
rezulta ca doar
n =
8 cadre pot fi transmise intr-o fereastra. Astfel, daca receptorul a
acceptat cadrele 0, , 7 si avanseaza fereastra pentru a
permite acceptarea cadrelor 8, , 15, el va recunoaste
fara dubii daca urmatoarele cadre sunt retransmisii (ale
cadrelor 0, , 7) sau cadre noi (8, , 12).
SN I [RN(t ) - n , RN(t ) + n - 1]
Daca numerele de ordine sunt construite modulo m si pachetele sunt acceptate in fereastra [RN(t ) , RN(t ) + n - 1] , este necesar ca B sa distinga valorile lui SN in intreaga multime ( ). Rezulta de aici conditia (
Cu aceasta schimbare, corectitudinea acestei clase de protocoale - de tip repetare selectiva - se p`streaz`.
O problema importanta pentru implementarea acestui tip de protocoale este obtinerea unei eficacitati maxime de utilizare a canalului.
Se observa ca, oricare ar fi protocolul cu fereastra glisanta utilizat, numai cadrele sosite fara eroare in B pot livra pachetele nivelului de retea receptor si, deci, numarul probabil de pachete livrate in medie lui B de un cadru trimis din A este marginit de
S 1 - p
(unde p este probabilitatea ca un cadru sa ajunga alterat).
Un protocol ideal de tip repetare selectiva ar avea o viteza maxima de transmisie egala cu 1 - p
Sa remarcam, mai intai, ca utilizarea numai a RN pentru a furniza informatii de confirmare nu este prea eficienta, intrucat, daca apar mai multe cadre eronate intr-un interval de propagare dus-intors, nodul A nu poate afla despre al 2-lea cadru eronat pana cand nu trece un timp egal cu durata de propagare dus-intors dupa retransmiterea primului cadru alterat.
Exista mai multe modalitati de a furniza informatii suplimentare de confirmare necesare lui A:
o metoda este aceea ca B sa trimita catre A cel mai mic numar de ordine de pachet nereceptionat corect inca - numar de ordine care trebuie sa fie mai mare decat pb (numarul probabil de cadre eronate in perioada de propagare dus-intors), dar care este limitat de informatia de control (antet) necesara si pe reactie;
o alta posibilitate o constituie transmiterea RN plus k biti suplimentari (k = const.), fiece bit furnizand o ack/nack pentru fiecare din cele k pachete ce urmeaza dupa cel cu numarul de ordine RN
Sa presupunem acum ca reactia (cadrele de confirmare) aduce in A suficienta informatie pentru ca emitatorul sa poata determina, dupa o asteptare de b cadre, daca un pachet a fost sau nu receptionat cu succes. Algoritmul tipic pentru A este, deci, sa repete transmisia pachetelor de indata ce constata ca transmisia lor anterioara a fost afectata de erori; daca A descopera mai multe cadre eronate din fereastra de emisie, el le va retransmite in ordinea numerelor de ordine ale pachetelor ce le contin. Cand nu se solicita retransmisii, A continua sa transmita noi pachete, pana la cel cu numarul SMmax . Cand atinge aceasta limita, A poate astepta pe durata unei anumite pauze de asteptare fixate sau sa se intoarca imediat inapoi la cadrul cu pachetul nr. SNmin , pentru a transmite pachetele neconfirmate.
Nodul A actioneaza ca un sistem ideal de repetare selectiva pana cand este fortat sa astepte sau sa se intoarca inapoi de la SMmax . Cand aceasta se intampla, pachetul cu nr. SNmin trebuie sa se fi transmis eronat de cca. n b ori. Deci, marind suficient de mult n, probabilitatea unei intoarceri inapoi poate fi redusa pana la valori neglijabile. Dar valorile mari pentru n introduc 2 dificultati (presupunand ca pachetele trebuie reordonate la nivelul DLC receptor):
- trebuie asigurata la B o memorie pentru toate pachetele acceptate dupa cel cu nr. RN
- numarul mare de pachete stocate vor fi toate intarziate in asteptarea celui cu nr. RN
p
Iata un program de simulare pentru un protocol de tip repetare selectiva in care, pentru fiecare cadru transmis este asociat un ceas si, la expirarea respectivei pauze de asteptare, se retransmite doar cadrul cu pachetul respectiv. Fereastra de emisie incepe co largimea 0 si creste pana la dimensiunea predefinita MAX_SEQ ; fereastra de receptie are dimensiunea fixa MAX_SEQ. Receptorul are cate un buffer rezervat pentru fiecare numar de ordine din fereastra, iar fiecarui buffer ii este asociat un bit arrived ("sosit") care indica daca buffer-ul este plin sau gol; pentru fiecare cadru sosit, o functie numita between ("in_fereastra") verifica daca numarul de ordine apartine ferestrei si, daca acest lucru este adevarat si cadrul nu a fost inca primit, il accepta si il stocheaza - indiferent daca el contine sau nu urmatorul pachet asteptat de nivelul de retea receptor (fireste, el va fi pastrat fara a fi livrat nivelului de retea, pana cand toate pachetele cu numerele de ordine precedente au fost livrate, in ordinea corecta, nivelului de retea).
/* Protocol Nonsequential receive */
#define MAX_SEQ 7 /* trebuie sa fie 2^n = 1 */
#define NR_BUFS ((MAX_SEQ + 1)/2)
typedef enum
event_type; /* evenimentele posibile
#include "protocol.h"
boolean no_nak = true; /* nu s-a transmis inca nici o confirmare negativa */
static boolean between(seq_nr a, seq_nr b, seq_nr c)
static void send_frame(frame_kind fk, seq_nr frame_nr, seq_nr frame_expected, packet buffer
void selectrep(void)
if r kind nak) && between(ack expected, (r ack+1)%(MAX SEQ+1), next frame to send))
send_frame(data, (r.ack+1)%(MAX_SEQ+1), frame_expected, out_buf);
while (between(ack_expected, r.ack, next_frame_to_send))
case cksum_err:
if (no_nak) send_frame(nak, frame_expected, out_buf); cadru eronat
case timeout:
send_frame(data, oldest_frame, frame_expected, out_buf); a expirat pauza
case ack_timeout:
send frame(ack, frame expected, out buf a expirat timpul pt ack; trimite ack
if (nbuffered NR_BUFS) enable_network_layer(); else disable_network_layer;
O problema cu acest protocol o constituie numarul necesar de buffer-e de la receptor. Este clar ca receptorul nu va accepta nici o data cadre cu numar de ordine mai mic decat limita inferioara a ferestrei sau cu numar de ordine mai mare decat limita superioara a ferestrei. Deci, numarul de buffer-e necesar este egal cu dimensiunea ferestrei (nu cu intervalul de numere de ordine valide !).
De exemplu, pentru m = 4 sunt necesare 8 buffer-e (numerotate de la 0 la 7). Cand soseste cadrul i , el este depus in buffer-ul nr. i mod 8. Se va observa ca, desi cadrele i si (i + 8) mod 8 "concureaza" pentru acelasi buffer, ele nu se afla nici o data simultan in aceeasi fereastra (caci aceasta ar implica o largime a ferestrei cel putin egala cu 9).
Cantitatea necesara de memorie poate fi micsorata la n b fara probleme, intrucat, de fiecare data cand apare o intoarcere inapoi la SNmax , nodul A nu mai poate transmite noi pachete dincolo de SNmax pe durata unei perioade de propagare dus-intors. Deci el ar putea, foarte bine, sa retransmita pachetele inca neconfirmate de la SNmax b pana la SNmax . Aceasta inseamna ca B nu trebuie sa salveze aceste pachete.
Numarul necesar de contoare de timp este egal cu numarul de buffer-e (nu cu intervalul de numere de ordine valide !). Exista cate un contor de timp asociat fiecarui buffer. Cand timpul contorului expira, se retransmite continutul buffer-ului.
Spre diferenta de protocolul Go_back_n - la care, daca traficul intr-un sens este mare iar in sens invers este inexistent, sunt trimise doar MAX_SEQ cadre, dupa care protocolul se blocheaza - la protocolul Nonsequential receive acest lucru nu se petrece. Dupa sosirea unui cadru dintr-o secventa, este pornit un ceas (contor de timp) auxiliar prin start_ack_timer. Daca nu apare trafic in sens invers pana la expirarea timpului fixat la acest ceas, se va trimite un cadru de confirmare separat. Intreruperea provocata de acest ceas auxiliar este evenimentul ack_timeout. In acest fel, lipsa unui trafic in sens invers, la care sa se ataseze confirmarile, nu mai constituie un impediment. Este esential ca intervalul de timp fixat la acest contor auxiliar sa fie mult mai scurt decat cel al pauzei de asteptare, asigurandu-se asfel ca o confirmare pentru un cadru corect receptionat soseste inainte de retransmiterea cadrului din cauza expirarii pauzei de asteptare.
Protocolul tip repetare selectiva Nonsequential receive) utilizeaza o strategie mai eficienta de tratare a erorilor decat protoculul tip revenire cu n Go_back_n. Ori de cate ori receptorul constata o eroare, el trimite o confirmare negativa (nak) catre emitator. Cadrul cu nak reprezinta o cerere de retransmitere a cadrului cu date specificat in nak. Transmiterea unei nak se face in doua situatii: cand se primeste un cadru alterat sau cand soseste un cadru fara eroare dar nu cel asteptat (posibil un cadru "pierdut"). Pentru a evita aparitia de cereri multiple de retransmisie a aceluiasi cadru "pierdut", receptorul va tine evidenta daca s-a transmis deja o nak pentru un anumit cadru. Variabila no_nak are valoarea adevarat daca nu s-a trimis inca nici o nak pentru cadrul asteptat (frame_expected ). Daca nak este alterata sau se pierde, nu este grav, intrucat emitatorul isi va termina pauza de asteptare si va retransmite oricum cadrul care lipsea la receptie. Daca un cadru eronat soseste dupa ce o nak a fost transmisa si pierduta, no_nak va lua valoarea adevarat si va porni contorul de timp auxiliar; la expirarea timpului acestuia, va fi trimisa o ack pentru resincronizarea emitatorului cu starea curenta a receptorului.
In unele situatii, intervalul de timp necesar pentru propagarea cadrului si a confirmarii, plus cel pentru procesarea cadrelor cu date la receptor si elaborarea confirmarii este (relativ) constant. Atunci, emitatorul isi poate regla pauza de asteptare astfel incat sa fie cu putin mai mare decat intervalul (probabil) normal dintre momentul transmisiei cadrului si cel al receptionarii confirmarii sale. Dar daca acest interval de timp este puternic variabil, emitatorul este pus in situatia sa aleaga intre doua alternative: o pauza de asteptare mica, riscand astfel retransmisii inutile si risipind largimea de banda, sau o pauza de asteptare mare, ramanand astfel inactiv o buna bucata de timp dupa producerea unei erori de transmisie si risipind si in acest caz largimea de banda. Daca traficul in sens invers este sporadic, durata pana la confirmare va fi neregulata - scurta cand exista trafic in sens invers si lunga in caz contrar. Si durata diferita de prelucrare de la receptor poate crea probleme in acest sens. In general, atunci cand abaterea standard a intervalului de timp pana la confirmare este mica in comparatie cu intervalul insusi, ceasul poate fi reglat pentru o pauza de asteptare scurta si nak nu sunt utile; in caz contrar, ceasul trebuie reglat pentru o pauza de asteptare mai mare, iar nak pot accelera in mod substantial retransmisia cadrelor alterate sau pierdute.
O problema strans legata de pauza de asteptare si de nak-uri este aceea de a determina care anume cadru a provocat espirarea pauzei de asteptare. In protoculu tip revenire cu n Go_back_n), acest cadru era intotdeauna confirmarea asteptata ack_expected ), caci ea era mereu cel mai vechi cadru. In protocolul tip repetare selectiva Nonsequential receive) nu exist` o modalitate simpla de a determina cadrul care a produs expirarea pauzei de asteptare. Intr-adevar, sa presupunem ca au fost transmise cadrele 0 4, ceea ce inseamna ca lista cadrelor transmise si neconfirmate inca, in ordinea de la cel mai vechi la cel mai recent, este 0, 1, 2, 3, 4. Sa presupunem ca: pauza de asteptare pentru cadrul 0 s-a terminat, se transmite noul cadru 5, pauzele de asteptare pentru cadrele 1 si 2 expira si este transmis noul cadru 6. In acest moment, lista cadrelor transmise si neconfirmate, de la cel mai vechi la cel mai nou cadru, este: 3, 4, 0, 5, 1, 2, 6. Daca se pierd toate confirmarile, pauzele de asteptare aferente celor 7 cadre vor expira in aceasta ordine.
Fara a ne ocupa de administrarea timpului (care ar ingreuna exemplificarea), vom presupune ca variabilei oldest_frame (cel mai vechi cadru) i se atribuie valoarea pauzei de asteptare astfel incat sa indice care este cadrul care a provocat expirarea pauzei de asteptare.
p
Sa analizam acum eficacitatea utilizarii canalului fizic de catre protocolul repetarii selective
In cazul unei ferestre largi, transmisia se face tot continuu, dar trebuie trimise cadre suplimentare pentru a "corecta" cadrele eronate. Am vazut ca numarul probabil de transmisii pentru un cadru este
astfel incat,
pentru a receptiona w cadre fara eroare, trebuie transmise 
cadre. Rezulta ca:
pentru o fereastra larga si erori de transmisie:
pentru o fereastra ingusta si erori de transmisie:
S scazand din cauza retransmisiilor.
Observatie In prezenta erorilor, eficacitatea protocoalelor cu fereastra glisanta este diferita, din cauza numarului diferit de cadre ce trebuie retransmise dupa o eroare. Astfel, pentru protocolul cu intoarcere cu n inapoi vom avea:
pentru o fereastra larga si erori de transmisie:
tinand cont ca
numarul
maxim de cadre care pot fi transmise inainte de a primi o confirmare este 
pentru o fereastra ingusta si erori de transmisie:
caci
trebuie retransmise w cadre de un numar
de q (w - 1) ori, aparand
pentru fiecare o intarziere egala cu .
In formulele pentru S, limita dintre ferestrele mari si cele mici este
.
Timpul t este timpul de propagare intr-un singur sens pe canal, astfel incat, produsul C t reprezinta numarul de biti ce pot fi transmisi in acest timp, respectiv numarul de biti ce pot fi "continuti" de cablu sau, inca, "lungimea" cablului exprimata in biti. Deci C t l este "lungimea" cablului exprimata in cadre. Asadar, w este cu 1 unitate mai mare decat numarul de cadre ce pot "umple" cablul in ambele sensuri.
Daca w este cel putin cu o unitate mai mare decat numarul de cadre ce incap in cablu, transmisia se poate desfasura continuu (altfel zis: emitatorul nu se va bloca din cauza unei ferestre umplute in timpul necesar primului cadru sa ajunga la receptor si sa fie prelucrat acolo, plus timpul de propagare a confirmarii).
Ultimul factor din expresia lui S pentru o fereastra ingusta reprezinta raportul dintre largimea w a ferestrei si largimea minima a ferestrei necesare pentru o transmisie continua.
Din fig. a) se constata ca S scade rapid cu Ct l pentru protocolul pas-cu-pas, intrucat majoritatea timpului este consumat pentru asteptarea confirmarilor.
Din fig. b) se observa ca S creste odata cu w si ca, pentru orice w S este mai mic pentru un cablu lung decat pentru un cablu scurt.
Observatii
pentru LAN cu C [Mbiti/s] si lungimea cablului de 1 [km] rezulta Ct 50 biti si, deci, Ct l <<
pentru o linie transcontinentala de C [kbiti/s] si lungimea cablului de 3 000 [km] rezulta Ct 960 biti;
pentru un canal de satelit cu C [kbiti/s] si t [ms] rezulta Ct 17 280 biti si, pentru multe cadre, vom avea Ct l >>
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2017
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
