In retelele cu canal unic, o problema extrem de importanta o constituie alocarea canalului la statiile care concureaza simultan pentru obtinerea dreptului de transmisie. Metodele de alocare a canalului se clasifica in metode de alocare statica si metode de alocare dinamica.
Sa analizam metodele de alocare dinamica a canalului.
Protocoale de acces multiplu cu ascultarea mediului
Protocoale cu detectia coliziunilor
Protocoale cu evitarea coliziunilor
Protocoale cu concurenta limitata
1. Protocoalele ALOHA
Cea mai simpla metoda de alocare dinamica - conceputa in anii '70 la Universitatea din Hawaii pentru transmisii radio la sol si denumita metoda ALOHA (dupa formula de salut in hawaii-ana), dar aplicabila la orice retea de transmisie cu canal unic si utilizatori necoordonati este de a lasa utilizatorii sa transmita oricind au date de transmis. Fireste, vor apare coliziuni si cadrele alterate ce rezulta vor fi distruse. Dar, datorita proprietatii de reactie [feedback] a oricarei transmisii de tip difuzare, emitatorul va putea constata - prin simpla ascultare a canalului - daca un cadru transmis de el a fost distrus. La LAN, reactia este imediata, dar la retelele mari (WAN) cu transmisie prin sateliti, dureaza citeva sute de milisecunde pina ce emitatorul afla daca transmisia a fost efectuata cu succes. Daca a avut loc distrugerea cadrului, emitatorul va trebui sa astepte un interval de timp aleatoriu pentru a trimite iarasi cadrul (evitind astfel repetarea coliziunii).
Daca doua cadre incearca sa ocupe canalul in acelasi moment, va avea loc o coliziune si cele doua cadre se vor altera reciproc. Chiar daca numai primul bit al unui nos cadru se suprapune (in timp) doar cu ultimul bit al unui cadru aflat deja in transmisie, tot vor fi distruse ambele cadre, necesitind retransmiterea lor.
Un indicator important pentru metoda de multiacces la canal il constituie eficienta [efficiency] sa in utilizarea canalului, exprimata prin procentul de cadre care scapa de coliziuni din totalul cadrelor transmise. In acest sens se definesc marimile:
durata unui cadru [frame time], reprezentind timpul necesar transmiterii unui cadru standard, de lungime fixa, si care rezulta impartind lungimea (in biti) a cadrului la viteza de transmisie (a bitilor) [through-put];
viteza medie de transmisie a cadrelor pe canal S [cadre/durata unui cadru], viteza care trebuie sa fie inferioara vitezei maxime C suportate de canal - numite capacitatea [capacity] canalului - adica respectind conditia
S<1
(caci, in caz contrar, aproape orice cadru transmis va suferi o coliziune);
numarul mediu G de incercari de transmisie (inclusiv retransmisie de cadre care au suferit coliziuni) pe durata unui cadru - ca o masura a nivelului de trafic [traffic] (denotind incarcarea cu cadre a canalului) - satisfacind, evident, relatia
G>=S.
Se demonstreaza ca
S=G*e-2G
pentru metoda de acces ALOHA. Rezulta ca viteza maxima de transmisie este, in medie, de
S=1/(2e)~0,184 [cadre/durata unui cadru]
(pentru G=0,5), adica o utilizare maxima a canalului de cca. 18%. Rezultatul este foarte modest, dar explicabil prin lipsa totala de coordonare a transmisiei.
O modalitate de dublare a performantei metodei ALOHA de acces la mediu este aceea de a diviza timpul in intervale egale cu durata unui cadru, sincronizarea utilizatorilor facindu-se cu ajutorul unei statii care sa emita tactele de inceput ale intervalelor de timp, celelalte staii acordindu-se dupa aceste tacte. Metoda este cunoscuta ca ALOHA discreta [slotted ALOHA], spre deosebire de cea prezentata mai sus, care se mai numeste si ALOHA simpla [pure ALOHA]. In ALOHA discreta, transmisia unui cadru nu se poate face decit la inceputul fiecarei fante de timp, fapt ce reduce la jumatate intervalul de timp in care transmisiile pot provoca coliziuni.
Ca urmare, S=G*e-G si se obtine o eficienta (viteza) maxima de transmisie egala cu
S=1/e~0,368 [cadre/durata unui cadru]
(pentru G=1), dar si o probabilitate egala de a avea fante de timp neutilizate - deci 37% din cadre nu vor provoca coliziuni si 37% din fantele de timp vor fi irosite.
2. Protocoalele de acces multiplu cu ascultarea mediului
O mai buna utilizare a canalului in LAN se obtine prin metodele de acces la mediu bazate pe ascultarea canalului. O prima categorie de astfel de metode este CSMA. Trei protocoale de acest gen sint intilnite in practica:
Un prim protocol din categoria CSMA este cel numit CSMA cu persistenta 1 [1-persistent CSMA], in care o statie care vrea sa transmita asculta mai intii canalul si, daca constata ca acesta este ocupat, asteapta ca el sa se elibereze pentru a obtine cadrul; in caz ca apare o coliziune, statia asteapta un interval de timp aleator pina sa retransmita. Protocolul are denumirea susmentionata pentru ca o staie transmite, cu probabilitatea 1, de fiecare data cind gaseste canalul neocupat.
Timpul de propagare pe canal afecteaza performantele acestui protocol, caci, daca o statie a apucat sa transmita imediat dupa ce prima a inceput transmisia, dar inainte ca respectivul cadru sa fi ajuns la cea de a doua statie, aceasta din urma va considera canalul neutilizat si va emite, cauzind o coliziune. Cu cit este mai mare durata de propagare, cu atit riscul coliziunilor creste si performantele protocolului scad.
Chiar si in cazul unei propagari instantanee, tot ar rezulta coliziuni, ca in cazul a doua statii gata de emisie in timpul unei transmisii efectuate de o a treia statie, caci ambele statii vor astepta pina cea de a treia isi termina transmisia si vor emite cadre simultan.
Totusi, acest protocol ofera performante mai bune decit precedentul, care rezulta din faptul ca doua statii ce concureaza pentru obtinerea canalului nu vor interfera cu o a treia, aflata deja in emisie.
In cazul unui timp de propagare nul, viteza de transmisie (eficienta utilizarii canalului) este data de relatia:
S=(G*e-G*(1+G))/(G+e-G)
Acest rezultat este valabil si in cazul transmisiei discrete, atunci cind fanta de timp este nult mai mica decit durata unui cadru, cadrele putind ocupa mai multe fante de timp. La valori scazute ale lui G, viteza de transmisie este mica (G apare ca factor la numaratorul lui S); deci, daca nimeni nu incearca sa transmita, viteza de transmisie va fi scazuta. La valori mari pentru G rezulta ca S->0.
Un al doilea protocol cu ascultarea canalului este cel numit CSMA nepersistent [nonpersistent CSMA]. In acest protocol, statiile nu se mai reped sa intre in posesia canalului imediat dupa terminarea unei transmisii, ci asteapta un interval de timp aleator inainte de a reasculta canalul. Aceasta conduce la o mai buna utilizare a canalului, dar si la intirzieri mai mari in transmisie, in cazul unui trafic ridicat.
Pentru o durata nula de propagare, acest protocol ofera - atit in versiunea continua, cit si in versiunea discreta - o viteza de transmisie (eficienta utilizarii liniei) ce depinde de incarcare (traficul solicitat) dupa legea:
S=G/(1+G).
Un al treilea protocol este CSMA cu persistenta p [p-persistent CSMA], care se aplica la transmisia cu fante de timp si lucreaza in felul urmator: cind o statie este gata sa transmita, ea incepe sa asculte canalul. Daca acesta este neocupat, va incepe transmisia cu probabilitatea q=1-p - transmisia pina la inceputul fantei urmatoare de timp. Daca aceasta fanta este neocupata, statia ori transmite ori amina din nou transmisia, cu probabilitatile p si respectiv q. Procesul se repeta pina cind statia isi transmite cadrul sau o alta statie incepe sa transmita. In acest ultim caz, statia actioneaza ca si cum ar fi avut loc o coliziune, adica asteapta un interval aleator de timp si reporneste procesul de obtinere a accesului la canal. Daca, insa, statia constata initial ca linia este ocupata, ea va astepta pina la inceputul urmatoarei fante de timp si va aplica algoritmul de mai sus.
Pentru o durata de propagare nula, viteza de transmisie este:
G=(G*e-G*(1+pGX))/(G+e-G),
unde
X=(qG)k/((1-qk+1)*k!).
Pentru orice p>0, S->0 cind G->4. Pentru p->0 se obtine valoarea asimptotica 1,00 a vitezei de transmisie, dar intirzierea in transmisie devine 4.
Fig.1. Variatia vitezei de transmisie S cu gradul de incarcare (traficul) G pe canalul fizic, atit pentru cele trei protocoale de tip CSMA, cit si pentru protocoalele ALOHA simplu si ALOHA discret.
3. Protocoale cu detectia coliziunilor
O categorie superioara de protocoale de acces la mediul fizic (unic) o constituie protocoalele cu detectia coliziunilor [collizion detection protocol].
Protocoalele CSMA de tip persistent si nepersistent reprezinta o imbunatatire fata de protocoalele ALOHA, intrucit ele asigura faptul ca nici o statie nu incepe sa transmita daca constata canalul ocupat.
O alta imbunatatire o constituie incetarea emisiei de indata ce statia constata o coliziune (adica fara a mai termina de transmis acele cadre care vor conduce cu siguranta la o alterare reciproca si irecuperabila). O astfel de terminare 'abrupta' a cadrelor deteriorate scuteste atit timpul, cit si banda de frecvente. Protocoalele de acest tip se numesc CSMA/CD (o varianta a lor este CSMA/CD cu persistenta 1 [1-persistent CSMA/CD]).
Algoritmul lucreaza astfel: la terminarea transmisiei unui cadru de catre o statie, oricare alta statie care este gata pentru transmisie va incerca sa capete acces la canal. Daca doua sau mai multe staii incearca simultan sa transmita, va rezulta o coliziune. Toate statiile emitatoare vor detecta coliziunea, isi vor incetas transmisia si, dupa o abtinere de o durata aleatorie, vor incerca din nou sa-si plaseze pe canal cadrul ce asteapta a fi transmis - presupunind ca, intre timp, nu a inceput sa transmita nici o alta statie. Asadar, apar alternativ intervale de timp de transmisie si intervale de timp in care are loc concurenta pentru obtinerea accesului la canal, plus intervale de timp in care linia este neocupata, nici o statie neavind de transmis.
Pentru a constata daca transmisia cadrului sau s-a realizat cu succes, o statie trebuie sa transmita - in cel mai defavorabil caz - pe o durata egala cu 2*t fara sa observe o coliziune (unde t reprezinta timpul de propagare intre cele mai indepartate statii din retea) - adica pina cind semnalul alterat de catre coliziune revine la statia emitatoare.
Asadar, modelul starilor succesive ale LAN cu protocol CSMA/CD va arata ca in fig. 2, unde intervalul concurential este de tip ALOHA discret, cu fante de timp de durata 2*t. Cu titlu informativ, pentru un cablu coaxial cu lungimea de 1 km, t~5 ms. Pentru simplificare, vom presupune ca fiecare fanta de timp contine doar 1 bit; dar transmisia cadrului se poate face cu orice viteza, nu doar cu 1 bit la fiecare 2*t s.
Fig.2. Modelul starilor succesive ale LAN cu protocol CSMA/CD.
Detectarea coliziunilor este un proces analogi, hardul de
la nivelul ierarhic 1 al statiei 'ascultind' linia fizica in timp ce
transmite si constatind coliziunea prin faptul ca ceea ce receptioneaza difera
de mesajul transmis. Ca urmare, la nivelul fizic trebuie procedat la o
codificare a semnalelor astfel incit sa permita detectarea coliziunilor (caci,
de exemplu, coliziunea intre doua semnale cu valoare identica de 0 nu poate fi
detectata in mod normal. Se utilizeaza curent, in acest scop, o codificare
numita codificare
Fig.3. Codificarea Manchester.
In codificarea
La codificarea
4. Protocoale cu evitarea coliziunilor
Desi pentru protocoalele CSMA/CD nu apar coliziuni din momentul in care o statie a obtinut accesul cert la canal, este posibil sa apara, totusi, coliziuni in intervalul de timp concurential (in care statiile incearca sa obtina accesul la canal). Aceste coliziuni afecteaza negativ performantele retelelor, mai ales in cazul unor cabluri lungi (deci pentru t mari) si al cadrelor de lungime mica - adica tocmai cazul retelelor cu fibre optice. Protocoalele cu evitarea coliziunilor [collizion-free protocol] reusesc aceasta chiar si pe durata perioadei concurentiale.
Presupunem ca cele N statii din retea au adrese unice ('cablate' in ele) de la 0 la N-1 (fara a lua in consideratie daca sint toate active sau nu la un moment dat).
Un protocol de acest tip este cel numit al corespondentei pozitiei bitilor cu lista logica a statiilor [basic bit-map]. El prevede ca intervalului concurential sa ii corespunda un numar de fante de timp - de 1 bit - egal cu numarul N al utilizatorilor. Fiecare statie (cu numarul de ordine j] isi poate anunta intentia de a transmite date prin plasarea unei valori 1 in fanta de timp cu numarul de ordine aferent, ca in exemplul din Fig.4. ce ilustreaza cazul a N=8 statii.
Fig.4.
Dupa trecerea perioadei concurentiale, fiecare statie va cunoaste statiile care vor transmite. Incepe transmisia cadrelor, in ordinea numerica a statiilor care s-au 'inscris' in 'lista' alcatuita pe durata concurentiala. Intrucit exista o ordine de transmitere acceptata de toate statiile, nu vor apare coliziuni. Dupa ce statiile care au avut de transmis date au factu acest lucru, incepe o noua perioada concurentiala cu N fante de timp de 1 bit. Daca o statie este gata sa transmita dupa ce fanta ei de timp a expirat, ea va trebui sa astepte pina la urmatoarea perioada concurentiala pentru a se putea inscrie in sirul de transmisie.
Luam ca unitate de timp fanta de 1 bit din perioada concurentiala pentru a evalua performantele acestui protocol. Fie d lungimea unui cadru, masurata in aceste unitati de timp. In cazul ca nici o statie nu are de transmis, cele N fante de timp se vor repeta premanent, continind doar valori 0.
Cind o statie cu numar de ordine mic devine pregatita sa transmita, acest fapt se va intimpla pe la mijlocul perioadei concurentiale. Deci, o astfel de statie va trebui sa astepte, in medie, N/2 fante de timp pentru explorarea curenta a statiilor care au de transmis, plus alte N fante de timp ale explorarii urmatoare (in care se va inscrie si ea) pina ce isi va putea incepe transmisia. Din aceleasi considerente, o statie cu numar mare va trebui sa astepte numai N/2 fante de timp, ea nemaiavind nevoie, de regula, sa mai astepte o noua explorare pentru a se inscrie in vederea transmisiei. Asadar, media de asteptare pentru o statie din retea va fi de N fante de timp.
Cum, pentru a transmite efectiv d biti, trebuie adaugati cei N biti ai perioadei concurentiale, eficienta utilizarii canalului va fi
d/(N+d).
La un trafic ridicat, cind toate statiile au permanent de transmis, se vor transmite N cadre cu lungimea de d biti dupa cei N biti concurentiali, ceea ce conduce la o eficienta de
N*d/(N+N*d)=d/(1+d).
Protocolul expus prezinta, deci, doua dezavantaje:
pe de o parte, statiile cu numar de ordine mare sint privilegiate fata de cele cu numar de ordine mic in privinta timpului de asteptare pentru a putea transmite;
pe de alta parte, in caz de trafic redus, o statie trebuie sa astepte cel putin terminarea explorarii curente a candidatelor la transmisie.
Pentru eliminarea acestor neajunsuri s-au conceput doua protocoale similare: metoda de acces cu recunoastere la (retele cu) difuzare [Broadcast Recognition Access Method (BRAM)] si metoda cu minifante si prioritati alternante [Mini Slotted Alternating Priorities (MSAP)] - numite colectiv de unii autori - metoda recunoasterii la (retele cu) difuzare si prioritati alternante [Broadcast Recognition with Alternating Priorities (BRAP)].
In cadrul acestei metode, de indata ce o statie inscrie o valoare 1 in fanta de timp aferenta, ea va incepe sa transmita imediat. In plus, explorarea din perioada concurentiala nu incepe intotdeauna cu statia avind numarul 0, ci cu statia cu numar de ordine succesor al statiei care transmite momentan, deci permisiunea de transmisie se propaga circular la toate statiile. O statie care nu are de transmis lasa neocupat bitul din fanta de timp corespunzatoare. Un exemplu pentru algoritmul BRAP este dat in Fig.5., pentru o situatie identica cu cea presupusa in Fig.4.
Se observa ca fiecare perioada concurentiala consta dintr-o succesiune initiala de fante libere ce se termina cu o fanta continind valoarea 1.
Fig.5.
BRAP poate fi descrisa si ca un algoritm ce provoaca, pentru fiecare statie, o intirziere in incercarea ei de a obtine accesul la canal, intirziere care este proportionala cu diferenta modulo N dintre numarul de ordine al statiei respective si numarul de ordine al ultimei statii care a reusit sa transmita fara coliziuni. Data fiind aceasta esalonare a intirzierilor, nu vor exista coliziuni.
Eficienta utilizarii canalului cu metoda BRAP este aceeasi ca la metoda corespondentei pozitiei bitilor cu lista logica a statiilor, dar intirzierile in transmisie sint mai mici la BRAP. Astfel, la trafic redus, o statie va avea de asteptat, in medie, doar N/2 fante de timp (pentru N mare) spre a capata acces la canal (in metoda anterioara, intirzierea medie era egala cu N); la trafic ridicat, cele doua metode provoaca aceleasi intirzieri, caci principala cauza a intirzierilor o constituie durata cadrelor si nu fantele de timp din intervalul concurential.
Protocolul de multiacces cu mai multe niveluri [Multi-Level Multi Access (MLMA)] ofera o eficienta similara cu BRAP la trfic ridicat, dar permite intirzieri mai mici in cazul unui trafic scazut. In cazul acestui protocol, o statie isi anunta intentia de a transmite prin difuzarea adresei sale intr-un format special.
o Exemplu: Utilizam baza de numeratie zecimala, pentru o retea cu N=1000 de statii. In metoda preconizata, o adresa va consta din 3 cifre zecimale exprimate prin cite un grup de 10 pozitii ('decada'), unde cifra zecimala este codificata printr-o cifra 1 pe pozitia aferenta a respectivei decade. De exemplu, numarul 305 va fi codificat prin: un 1 in pozitia 3 a primei decade, un 1 in pozitia 0 a celei de a 2-a decade si un 1 in pozitia 5 a celei de a 3-a decade.
Daca o singura statie incearca sa transmita pe durata unei fante de timp, ea va utiliza antetul cu 30 de biti pentru a-si anunta adresa si apoi isi va transmite cadrul.
In caz ca doua sau mai multe statii incearca sa-si inscrie adresa in acelasi antet, protocolul va actiona dupa cum urmeaza. Statiile isi inscriu cifra 'sutelor' (in modul specificat mai sus) in prima decada a cadrului (cea care corespunde cifrei 'sutelor'). Statiile care nu si-au instalat un bit in aceasta decada vor trebui sa astepte pina ce toate statiile care s-au inscris isi vor fi trimis cadrele. Fie i pozitia ocupata si avind cel mai mare numar de ordine in cadrul acestei decade. In cea de a doua decada, toate statiile care au numar de ordine incepind cu i isi vor inscrie cifra 'zecilor'. Fie j pozitia ocupata avind cel mai mare numar de ordine din aceasta a 2-a decada. In a 3-a decada, toate statiile a caror adresa incepe cu ij isi vor instala cifra 'unitatilor' (exista cel mult 10 statii in aceasta situatie).
Numarul de decade necesare pentru rezolvarea conflictelor depinde de insasi valoarea adeselor: pentru un trafic minim, este necesar un antet de 30 de pozitii (biti), ceea ce duce la o eficienta de folosire a canalului egala cu
d/(d+30)
iar la un trafic maxim, cadrul va consta din 11 decade in antet plus 1000 de cadre cu date, rezultind o eficienta de
d/(d+1,11)
- apropiata de cea a algoritmului corespondentei pozitiilor bitilor cu lista logica a statiilor.
Evident, alegerea bazei de numeratie 10 a fost arbitrara. Se poate alege baza 2 si atunci, pentru N=1000 vor fi necesare 10 niveluri continind cite 2 biti ('binade'). Primul nivel va fi utilizat pentru separarea grupului de statii cu adresele 0-511 de grupul cu adresele 512-999. Pentru a minimiza numarul de biti din antet in cazul unei singure cereri de transmisie intr-un cadru, sa adoptam baza de numeratie b. Numarul de niveluri necesare in baza b va fi cea mai mica valoare n astfel incit
bn>=N.
Se va incerca minimizarea numarului de biti din antet (n*b) sub restrictia de mai sus. Va rezulta un minim pentru
b=e.
Deci, pentru N=1000, obtinem b=2 si n=10, iar pentru N=2000, optimul se obtine pentru b=3 si n=7.
Un caz limita al algoritmului MLMA este cel in care, la fiecare nivel de codificare a adreselor statiilor, exista doar 1 bit. Pentru N statii vor fi necesare
[log2N]+1
niveluri (unde [x] semnifica partea intreaga a numarului x). Pentru a-si semnala intentia de a transmite, o statie isi va inscrie adresa, sub forma binara, in antet. Protocolul acesta poarta numele de numaratoare inversa binara [binary countdown].
Regula aplicata pentru evitarea coliziunior va fi urmatoarea: de indata ce o statie constata ca intr-o pozitie binara dintr-un nivel superior - unde adresa sa contine un 0 - se inscrie un 1, ea va ceda accesul la canal. Dupa ce statia care a cistigat accesul si-a transmis adresa, nu mai exista nici o informatie privind numarul de statii care vor sa mai transmita; asadar, algoritmul se va repeta pentru fiecare nou cadru. Eficienta utilizarii canalului pentru acest protocol este
d/(d+lnN).
Daca se alege formatul cadrului astfel incit adresa expeditorului sa se afle in primul cimp al cadrului, nu se vor irosi cei lnN biti.
O varianta a metodei numaratorii inverse binare prevede, pe linga utilizarea unei interfete paralele in locul celei seriale, utilizarea unor numere virtuale in locul adreselor efective ale statiilor. Aceste numere virtuale incep de la 0 si merg pina la (inclusiv) numarul statiei care a reusit sa transmita. Numerele de ordine sint permutate circular dupa fiecare transmisie, pentru a acorda o prioritate mai mare celor care nu au transmis un timp mai indelungat.
5. Protocoale cu concurenta limitata
Metodele de alocare dinamica a canalului - prezentate mai sus - se clasifica, in esenta, in doua mari categorii: cele cu concurenta pentru obtinerea accesului la canal (precum CSMA) si cele cu evitarea coliziunilor. Valoarea lor se masoara prin doi indici de performanta importanti:intirzierea in transmisie la trafic redus si eficacitatea utilizarii canalului la trafic ridicat. In conditii de incarcare redusa, se prefera metoda concurentiala (de exemplu ALOHA simpla sau discreta), care permite intirzieri mai mici. Pe masura ce traficul creste, metoda concurentiala devine mai putin performanta din cauza cresterii dimensiunii antetului necesar rezolvarii problemei alocarii canalului. Situatia este exact inversa pentru metodele cu evitarea coliziunilor. La trafic redus, ele provoaca intirzieri mari in transmisie dar, pe masura incarcarii retelei, eficienta utilizarii canalului creste.
De aici apare ideea de a combina avantajele celor doua metode de alocare a canalului intr-o noua metoda (protocol) care sa foloseasca varianta concurentiala la incarcari reduse - pentru a realiza intirzieri mici - dar sa se comporte precum varianta cu evitarea coliziunilor la trafic ridicat - oferind astfel o eficienta utilizare a canalului. Asemenea protocoale au aparut, purtind numele generic de protocoale cu concurenta limitata [limited contention protocol].
Pentru a prezenta ideea de baza a acestor protocoale, observam mai intii ca toate protocoalele de tip concurential au prezentat proprietatea de simetrie - adica probabilitatea de acces la canal era egala pentru toate statiile. Probabilitatea P ca o statie (oarecare) sa reuseasca sa obtina accesul la canal pe durata unei anumite fante de timp, atunci cind concureaza pentru obtinerea accesului un numar de k statii, fiecare transmitind cu probabilitatea p, este
P=k*p*(1-p)k-1
care are o valoare maxima - pentru un k dat - la
p=1/k;
pentru aceasta probabilitate optima de transmisie, probabilitatea P de obtinere a accesului la canal este
P=(1-1/k)k-1.
Se constata ca pentru un numar mic k de statii, sansele de succes in obtinerea accesului la canal sint destul de bune, dar ca de indata ce numarul statiilor creste peste k=4, P atinge aproape valoarea asimptotica 1/e.
Din cele expuse rezulta ca probabilitatea unei statii sa obtina accesul la canal poate fi marita doar prin scaderea numarului de statii care concureaza pentru obtinerea accesului intr-o fanta de timp data. De aici apare ideea unor algoritmi asimetrici in raport cu probabilitatea de transmisie a statiilor, idee care s-a materializat in diverse protocoale din categoria numita 'cu concurenta limitata'.
Metoda de baza consta in separarea statiilor in doua grupuri (nu neaparat disjuncte). Li se permite sa concureze pentru obtinerea fantei de timp numarul 0 doar statiilor din grupul 0. Daca una din aceste statii cistiga procesul concurential, ea va capata imediat accesul la canal si isi va transmite cadrul. Daca, insa, acea fanta de timp ramine neocupata sau daca se petrece o coliziune, atunci statiile din grupul 1 vor concura pentru fanta de timp numarul 1 etc. Efectuind o separare convenabila a statiilor in grupuri, sa va reduce astfel numarul concurentilor pentrrru fiecare fanta de timp si va creste, in consecinta, probabilitatea lor de a obtine accesul la canal.
Protocoalelor cu concurenta limitata li se mai spune si protocoale cu separare [splitting protocol].
In caz general, problema care se pune este aceea de a gasi o modalitate de a aloca statiile unei fante de timp in mod dinamic, cu un numar mare de statii pentru fiecare fanta de timp, in situatia unui trafic scazut, si cu un numar mic de statii (eventual doar una) pentru o fanta de timp, in conditiile unui trafic ridicat.
Un prim algoritm din aceasta categorie este cel care sta la baza protocolului de tip arbore (adaptiv) [(adaptive) tree protocol]. El presupune o 'reactie' imediata de la receptor prin care orice statie afla daca in respectiva fanta de timp au fost transmise 0 pachete - adica fanta a ramas neocupata - sau 1 pachet - ceea ce se traduce prin succesul transmisiei cadrului emis - sau mai mult de un pachet - adica a avut loc o coliziune ce a generat un semnal alterat (deci eronat - notat cu 'e').
Algoritmul este urmatorul: Daca in fanta de timp numarul k apare o coliziune, toate statiile care nu sint implicate in acea coliziune vor trece intr-o stare de asteptare, iar toate statiile implicate in coliziune se separa in doua submultimi. Statiile din prima submultime vor incerca sa transmita in fanta de timp numarul k+1 si, daca acea fanta ramine neocupata sau este preluata (cu succes) de o singura statie pentru a-si transmite cadrul, atunci statiile din a doua submultime vor transmite in fanta numarul k+2. In situatia contrara - adica la aparitia unei noi coliziuni in fanta k+1 - prima din cele doau submultimi se va diviza la rindul ei si cea de a doua sub-submultime va astepta rezolvarea acestei noi coliziuni.
O statie cu un cadru restant poate determina momentul cind sa transmita, folosind un contor ce tine evidenta submultimii curente de cadre din stiva. Cind un cadru este implicat intr-o coliziune, contorul este pus pe 0 sau 1 in functie de submultimea in care este plasat cadrul. Cind contorul contine un 0, cadrul este transmis, iar daca valoarea din contor este nenula, atunci ea va fi incrementata cu 1 unitate pentru fiecare fanta de timp neocupata ori care preia cu succes un cadru.
O problema care trebuie rezolvata in cadrul acestui algoritm este aceea a cadrelor nou sosite pe durata rezolvarii unei coliziuni. In acest sens s-a definit o durata de rezolvare a coliziunii [Collision Resolution Period (CRP)] care se incheie atunci cind apare o fanta de timp neocupata sau cu transmisie reusita a unui cadru si stiva aferenta ramine goala. In acel moment incepe o noua CRP utilizind cadrele sosite pe durata precedentei CRP. Daca se intimpla ca in CRP anterioara sa fie necesare multe fante de timp, atunci va exista un numar mare de cadre nou sosite, care vor provoca numeroase coliziuni ce, prin urmare vor apare unor submultimi mici pentru noua CRP. Solutia adoptata a fost urmatoarea: la finalul unei CRP, multimea de noduri cu cadre nou sosite este divizata imediat in j submultimi, unde j este ales astfel incit numarul de cadre rezultat in fiecare submultime sa fie putin mai mare ca 1. Aceste noi submultimi sint incarcate in stiva si se porneste o noua CRP.
Asadar, protocolul de tip arbore va lucra astfel: Fiecare nod avind un cadru implicat in CRP curenta tine evidenta pozitiei sale in stiva, iar toate nodurile tin evidenta numarului de elemente din stiva si a numarului de fante de timp de la finele CRP precedente; la finalul acelei CRP, fiecare nod determina numarul probabil de cadre nou sosite si stabileste noul numar j de submultimi, nodurile care au cadre nou venite alegind aleatoriu cite una din aceste j submultimi si actualizindu-si contorul conform pozitiei corespunzatoare in stiva.
Prin optimizarea valorii lui j fata de numarul probabil de cadre nou sosite se poate obtine, prin acest protocol, o viteza maxima de transmisie de 0,43 [cadre/fanta de timp].
Se pot aduce unele imbunatatiri algoritmului de tip arbore descris mai sus.
n O prima imbunatatire rezulta constatind faptul ca o coliziune poate fi urmata de o fanta ce ramine neutilizata - ceea ce inseamna ca toate cadrele implicate in coliziune au fost alocate celei de a doua submultimi. Conform algoritmului, aceasta submultime va fi transmisa, generind cu siguranta o coliziune. Asadar, se poate aduce o imbunatatire algoritmului de tip arbore prin netransmiterea acestei a doua submultimi si divizarea ei in doua sub-submultimi, din care se va transmite doar prima. In general, daca apare o fanta neocupata, cea de a 2-a submultime (care se afla in asteptare) va fi divizata si se va transmite numai prima sub-submultime care rezulta.
Aceasta imbunatatire poate fi privita si prin prisma implementarii cu o stiva si a utilizarii unor contoare, ca in algoritmul initial. Fiecare nod va trebui sa tina evidenta unei variabile (binare) de stare, suplimentare, care ia valoarea 1 daca, pentru oriacare ar fi i>=1, ultimele i fante de timp au prezentat o coliziune urmata de i - 1 fante neocupate, in caz contrar, variabila de stare va lua valoarea 0. Daca reactia pentru fanta curenta indica 0 si variabila de stare are valoarea 1, atunci variabila de stare isi va mentine valoarea 1 si submultimea din virful stivei va fi descompuse in 2 sub-submultimi care vor fi incarcate in stiva in locul elementului din virf. Efectul acestei imbunatatiri este cresterea vitezei de transmisie la 0,46 [cadre/fanta].
n O alta imbunatatire a algoritmului de tip arbore este urmatoarea: in cazul unei coliziuni urmate de o alta coliziune - deci cind prima submultime de dupa divizare contine mai mult de 1 cadru, nu se mai aloca o fanta de timp pentru cea de a doua submultime - care se dovedeste ca are un numar probabil de cadre foarte mic - ci se incorporeaza aceasta submultime ca o parte a multimii cadrelor nou sosite si aflate in asteptare (deci, neimplicate in prima coliziune), cadre care vor participa la urmatoarea perioada de rezolvare a coliziunilor.
Trebuie mentionat faptul ca algoritmul de tip arbore necesita monitorizarea (reactiei) canalului de catre toate nodurile, pentru a afla cind se termina fiecare perioada de rezolvare a coliziunilor. Aceasta poate constitui un dezavantaj atunci cind spatiile se inchid din lipsa de mesaje de transmis. Situatia se poate rezolva facind ca pachetele nou sosite sa se alature submultimii de statii memorate in virful stivei, ceea ce obliga doar statiile restante in acel moment sa monitorizeze reactia. Un asemenea tip de algoritm se numeste cu stiva neblocata [unblocked stack], pentru a indica faptul ca noile sosite nu sint blocate pina la finalul perioadei curente de rezolvare a coliziunilor - spre deosebire de algoritmul clasic de tip arbore, numit si cu stiva blocata [blocked stack].
Utilizind, pe de o parte, drept criteriu de separatie in submultimi a cadrelor implicate intr-o coliziune momentul sosirii lor - adica formind o submultime cu toate cadrele sosite intr-un anume interval de timp si, pe de alta parte, divizind, la aparitia unei coliziuni, acest interval in subintervale si transmitind totdeauna mai intii cadrele din primul subinterval (cele sosite mai devreme), va rezulta o transmitere a cadrelor - care obtin accesul la canal - in ordinea sosirii lor. Algoritmul rezultat este primul venit - primul servit (FCFS) - fiind identic du disciplina de servire FIFO a sirurilor de asteptare.
Pe scurt: la fiecare valoare intreaga k a timpului, algoritmul stabileste cadrele ce vor fi transmise in fanta de timp numarul k (de la momentul k la momentul k + 1) ca fiind multimea tuturor cadrelor sosite intr-un interval anterior - fie el de la T(k) la T(k) + a(k) - numit interval de alocare [allocation interval] pentru fanta de timp numarul k. Cadrele sosite dupa momentul T(k) + a(k) constituie un sir de asteptare - deci intervalul de la T(k) + a(k) pina la momentul curent k va reprezenta un interval de asteptare [waiting interval] -, pe cind cadrele sosite in intervalul de alocare sint deja in curs de a fi servite (transmise). Numarul cadrelor din sirul de asteptare este necunoscut, in pofida faptului ca toate nodurile tin evidenta intervalului de alocare.
In esenta, algoritmul FCFS contine regulile prin care nodurile calculeaza T(k) si a(k) pentru fiecare valoare succesiva a lui k, pe baza reactiei de la fanta de timp precedenta. Aceste reguli sint chiar cele de la algoritmul de tip arbore, cu cele doua imbunatatiri semnalate si adaptate la criteriul de divizare dupa timpii de sosire ai cadrelor.
Astfel, la aparitia unei coliziuni in fanta de timp nr. k, intervalul de alocare este divizat in doua subintervale de durate egale, iar subintervalul din stinga (S) - continind cadrele cu durate de asteptare (inceputul intervalului ramine neschimbat) si a(k+1)=a(k)/2. Daca, dupa coliziune, urmeaza o fanta neocupata, se va utiliza prima imbunatatire a algoritmului de tip arbore: precedentul interval din dreapta (D) va contine sigur mai mult de un cadru si va fi imediat divizat, rezultind subintervalul DS ca interval de alocare pentru fanta k+2. Deci T(k+2)=T(k+1)+a(k+1) si a(k+2)=a(k+1)/2. In final va avea loc o transmisie reusita, incheind CRP.
Daca o coliziune in fanta nr. k este urmata de o alta coliziune in fanta nr. k + 1, se apeleaza la a doua imbunatatire din algoritmul de tip arbore: intrucit intervalul S contine mai mult de un pachet, coliziunea din fanta nr. k nu aduce nici o informatie despre intervalul D si, atunci, putem privi D ac si cum nici n-ar fi facut parte din intervalul de alocare. CRP se incheie cind cadrul din sub-subintervalul SS si cel din sub-subintervalul SD sint transmise cu succes in fantele k + 2 si k + 3.
Spre deosebire de algoritmul de tip arbore, operatia de divizare in submultimi a cadrelor aflate in asteptare, la sfirsitul unei CRP, este inlocuita cu alegerea unui nou interval de alocare, de durata a0 (noul interval de alocare pentru fanta k + 4 include si vechiul interval D care si-a pierdut identitatea de interval separat).
Pierderea identitatii unui interval 'din dreapta' (D) atunci cind intervalul corespunzator 'din stinga' (S) se divide, se traduce, in conceptul de arbore, prin 'tunderea' arborelui astfel incit el sa nu aiba niciodata mai mult de 2 frunze (respectiv, in varianta de lucru cu o stiva, aceasta sa nu memoreze mai mult decit cele doua elemente din virf). De fiecare data cind intervalul de alocare corespunde submultimii stingi rezultate dintr-o divizare, va exista o submultime dreapta corespunzatoare, care va trebui transmisa mai tirziu. Invers, cind intervalul de alocare corespunde unei multimi drepte, inseamna ca nu mai exista interval de asteptare. Deci, in algoritmul FCFS, nodurile trebuie sa memoreze doar amplasamentul intervalului de alocare si faptul daca el este de tip interval sting sau drept. Prin conventie, intervalul initial dintr-o CRP se considera interval drept.
Asadar, algoritmul FCFS calculeaza intervalul de alocare -T(k) si a(k) - precum starea s (= S sau D) pentru fanta nr. k, pe baza reactiei, a intervalului de alocare si a starii pentru fanta nr. k - 1:
daca reactia =e, atunci
T(k)=T(k-1)
a(k)=a(k-1)/2
s(k)=S
daca reactia=1 si s(k-1)=S, atunci
T(k)=T(k-1) + a(k-1)
a(k)=a(k-1)/2
s(k)=D
daca reactia=0 si s(k-1)=S, atunci
T(k)=T(k-1) + a(k-1)
a(k)=a(k-1)/2
s(k)=S
daca reactia=0 si s(k-1)=D, atunci
T(k)=T(k-1) + a(k-1)
a(k)=min[a0, k-T(k)]
s(k)=D,
care indica finalul CRP. Valoarea a0 a noului interval de alocare se alege fie prin minimizarea intirzierilor in transmisie, pentru o frecventa data de sosire a cadrelor, fie prin maximizarea vitezei de transmisie.
Algoritmul FCFS cere ca toate nodurile sa monitorizeze reactia canalului, in fiecare moment. O modificare a acestui algoritm permite nodurilor sa monitorizeze reactia doar dupa ce primesc un cadru pentru a-l transmite.
Ideea consta in a trimite cadrele aproximativ in ordinea ultimul venit - primul servit [Last-Come First-Serve (LCFS)], ceea ce face ca cele mai recent sosite cadre sa nu mai trebuiasca sa cunoasca lugimea sirului de asteptare, ele avind prioritate la transmisie.Cadrele nou sosite sint puse intr-o stare de 'preasteptare' [prewaiting mode] pina cind capata suficienta informatie - din reactie - pentru a constata finalul unei CRP; se demonstreaza ca sfirsitul unei CRP se recunoaste prin una din urmatoarele doua situatii intilnite pe reactie: fie o fanta (de timp) cu continutul 1 urmata de o fanta cu continut 0 sau 1, fie h fante succesive cu continut 0 (unde h este numarul maxim posibil de repetitii cu succes a pasului din algoritmul FCFS ce corespunde cazului reactia=0 si starea s(k-1)=S) urmate de o fanta cu continut 1 sau 0. Odata cu inceputul noii CRP, intervalull de alocare se va alege la dreapta intervalului de asteptare (adica spre valori mai recente ale timpului), inglobind si o parte sau chiar tot intervalul nou de preasteptare - fapt ce face posibil ca intervalul de asteptare si cel de alocare sa poata fi formate din intervale disjuncte, intervalul de asteptare va avea totdeauna dimensiunea a0 (fara a considera subintervalele sale de discontinuitate).
Cind numarul statiilor restante este mare, algoritmul LCFS creaza o intirziere ceva mai mare decit algoritmul FCFS, in primul rind din cauza timpului consumat de cadre pentru a sta in starea de preasteptare.
O alta varianta a algoritmului cu separare dupa disciplina FCFS este aplicabila atunci cind avem un numar fix si identificabil m de noduri. Putem concepe atunci o succesiune logica a nodurilor in ordinea crescatoare, ciclica, a numerelor lor de ordine si, in loc de a forma multimile de noduri de alocat la canal dupa criteriul momentului sosirii cadrelor, sa constituim multimile de alocare din succesiuni ne noduri consecutive, intr-un numar dat l, de pe circumferinta logica.
Dupa terminarea CRP, daca a existat o transmisie cu succes sau nici o transmisie, algoritmul va aloca urmatorul set de noduri de lungime l; daca a existat o coliziune, lungimea setului de noduri - numit si 'fereastra' - se va reduce la jumatate, iar daca apare din nou o coliziune reducerea ferestrei la jumatate va continua pina ce nu mai apare nici o coliziune. Dupa modul de lucru al acestui algoritm, protocolul corespunzator a fost numit protocol de separare cu baleiere ciclica [round-robin splitting protocol]. Metoda este asemanatoare cu algoritmul de multiacces numit inel cu fante [slotted ring] - o versiune discretizata a metidei inel cu jeton si utilizata, ca si aceasta din urma, la realizarea unor LAN.
Problema care se pune este stabilirea dimensiunii (largimii) ferestrei. Ca si algoritmul de baza tip arbore, acest algoritm limiteaza numarul de statii care capata dreptul de a transmite in fiecare set de alocare, asatfel incit sa maximizeze probabilitatea de a avea exact o statie gata sa transmita in fiecare fanta de timp. Dar conceptul de baza pentru acest algoritm nu este cel de arbore binar, ci acela de urna cu bile - de unde si numele de protocol tip urna [urn protocol] sub care mai este cunoscut acesta.
In prezentul protocol se face o analogie intre statiile care au cadre de transmis si respectiv cele care nu au ce transmite cu bilele de culori diferite dintr-o urna (i statii care au de transmis; se alcatuieste o fereastra de lungime l).
Pentru i=1, probabilitatea de a transmite cu succes un cadru (intr-o fanta) este maxima daca se alege
l=[m/v]
Numarul mediu de statii care sint gata de transmisie intr-o fereastra este egal cu
l*v/m,
valoare aproximativ egala cu 1.
Modul de comportare al acestui algoritm, in conditii
diverse de incarcare a retelei, pune in evidenta urmatoarele: daca numarul
estimat de statii gata de transmisie este mai mic sau egal cu 1 (incarcare
slaba a retelei), dimensiunea ferestrei va fi m (adica egala cu
numarul total de statii din retea), deci fereastra se va tot roti pe inelul
logic si oricare statie va putea transmite oricind are nevoie; in aceste
conditii, protocolul degenereaza in protocolul ALOHA discret. Daca valoarea
estimata v ramine
|
Politica de confidentialitate |
 .com |
Copyright ©
2024 - Toate drepturile rezervate. Toate documentele au caracter informativ cu scop educational. |
Personaje din literatura |
| Baltagul – caracterizarea personajelor |
| Caracterizare Alexandru Lapusneanul |
| Caracterizarea lui Gavilescu |
| Caracterizarea personajelor negative din basmul |
Tehnica si mecanica |
| Cuplaje - definitii. notatii. exemple. repere istorice. |
| Actionare macara |
| Reprezentarea si cotarea filetelor |
Geografie |
| Turismul pe terra |
| Vulcanii Și mediul |
| Padurile pe terra si industrializarea lemnului |
| Termeni si conditii |
| Contact |
| Creeaza si tu |
