Probleme R.I.B.L(I) - Comutatoare cu buffere la intrare

Probleme R.I.B.L(I) - Comutatoare cu buffere la intrare

1. Se da un comutator cu buffere la intrare de dimensiune 4*4 (4 intrari, 4 iesiri). La momentele 0, T, 2T, 3T, 4T, 5T sosesc pe intrarile comutatorului pachetele:

0: (1 ), (2,1), (3,1), (4,1);

T: (1 ), (2,3), (3,3), (4,2);

2T: (1 ), (2,3), (3,2), (4,2);

3T: (1 ), (2,3), (3,2), (4,1);

4T: (2 ), (3,2), (4,2);

5T: (2 ), (3,1), (4,2);

care se introduc in buffer-ele de intrare.

Sa se deseneze diagrama extragerii pachetelor din buffer-ele de intrare figurindu-se si starea buffer-elor de intrare la fiecare moment t=kT , k Z pentru politica de selectie circulara si fereastra de analiza unitara.

Obs. 1) Prin notatia (x,y) se intelege:

x= indice buffer de intrare in care este atocat pachetul;

y= adresa solicitata de pachet.

2) Se presupune ca pentru t >5T nu mai sosesc alte pachete in buffer-ele de intrare.

3) Analiza se va efectua pina la golirea tuturor buffer-elor de intrare.

2. Sa se deseneze diagrama extragerii pachetelor din bufferele de intrare ale unui C-ATM 44 stiind ca distributia pachetelor in functie de adresele solicitate este:

Observatii:

1) Se presupune ca pe toata durata analizei nu sosesc pachete in bufferele de intrare, iar politica de selectie utilizata este politica cu analiza lungimii cozilor de asteptare.

2) Daca exista 'competitori' ai aceleiasi iesiri in cozi de lungimi egale se alege coada cea mai apropiata de pozitia initiala a pointerului in sensul de parcurgere 1234 al bufferelor de intrare.

3) Pozitiile initiale ale pointerilor sunt loc[i i unde loc[i] este pozitia aferenta iesirii i.

3. Se da un comutator de dimensiune 4*4 cu buffere de intrare. La momentele t= 0, T, ,MT cu M N^* sosesc pe intrarile comutatorului pachete dupa urmatoarea lege:

-in intervalul [0,MT] pe fiecare intrare i, i= 14, k_ij pachete solicita adresa j, unde: k_ij N. Traficul pe fiecare intrare este 1 iar pentru t > MT in buffer-ele de intrare nu mai intra nici un pachet.

Daca se foloseste o fereastra de analiza de dimensiune 1, sa se determine timpul minim dupa care toate buffer-ele de intrare sunt vide, in functie de k_ij, atunci cind ordinea solicitarilor pentru o anumita iesire variaza, indiferent de politica de selectie utilizata.

4. Se defineste coeficientul mediu de utilizare al unei iesiri in intervalul [0,t] (t=MT, MN^*);

c_{j med}=(nr. pachete dirijate pe iesirea j in [0,t])/(M+1)

a) In aceleasi ipoteze ca la problema anterioara sa se calculeze (c_{j med})_max, j=14 (coeficienti maximi de utilizare pentru fiecare iesire), in functie de k_ij, atunci cind ordinea solicitarilor pentru fiecare iesire variaza, indiferent de politica de selectie utilizata, cu fereastra de analiza unitara.

b) Explicati calitativ motivele pentru care valoarea lui c_{j med} poate sa scada fata de (c_{j med)max.}

Traficul pe fiecare intrare este 1.

5.In aceleasi ipoteze ca la problema 3 in conditii de trafic 1 pe intrare si fereastra de analiza unitara sa se evalueze timpul maxim dupa care se golesc buffer-ele de intrare, precizind distributia de pachete pentru care se obtine acest maxim.

₄

Obs. 1. Se noteaza N_i= k_ij, i=14

^j=1

2. Se presupune ca N_i, i=14 sunt numere divizibile cu 4.

3. Pentru simplificarea relatiilor obtinute calculul se face in functie de N₁, N₂,N₃,N₄.

` 4. Fereastra de analiza si traficul sunt unitare.

6. In ipotezele problemei 4 si cu observatiile de la problema 5 sa se evalueze coeficientii (c_{j med})_min.(sa se determine minimele coeficientilor de utilizare ai unei iesiri), precizind distributia adreselor solicitate de pachetele pentru care obtin acest minim.

7. Sa se repete problema 1,comparand rezultatele obtinute d.p.d.v. a perioadei de analiza,pentru w=1si w=2,stiind ca distributia sosirilor la momentele t=0,T,,3T pe intrarile comutatorului este:

0: (1 ) (2,1) (3,1) (4,1)

T: (1 ) (2,1) (3,3) (4,4)

2T: (1 ) (2,4) (3,3) (4,4)

3T: (1 ) (2,1) (3,2) (4,2)

Observatii:

1) Pentru t>3T nu mai soseste nici un pachet in bufferele de intrare.

2) Pozitiile initiale ale pointerilor aferenti iesirilor sunt loc[i i.

3) Se presupune o politica de selectie circulara.

a) In fiecare din bufferele de intrare ale unui comutator 44 exista la t=0, 4*M=8

pachete,fiecare iesire fiind solicitata de M=2 pachete , cu o distributie a acestor pachete a.i. sa se obtina un timp maxim de golire al bufferelor de intrare. Exemplificati o distributie cu proprietatilr de mai sus. Cit este acest timp in conditiile W=1.

b) Cit devine acest timp pentru W= daca se pastreaza aceeasi distributie?

9. Sa se rezolve 10. pentru M oarecare (M2).

Solutii:

1.

Se presupune initial pozitia pointerilor asociati iesirilor ca in figura ºi vom nota '' celulele extrase:

t=T t=2T

t=3T t=4T

t=5T t=6T

t=7T t=8T

t=9T t=10T

t=11T

2

Ordinea de extragere a pachetelor este:

t=0 : (1 ) , (4,2)

t=T : (1,1) , (4,2)

t=2T: (1 ) , (2,2)

t=3T: (3 ) , (2,3) , (4,2)

t=4T: (1 ) , (2,4) , (4,2)

t=5T: (1 ) , (3,4) , (4,2)

Diagramele se fac ca in problema anterioara.

3.

Notam N_j=numarul total de pachete ce solicita iesirea j pe intervalul [0,MT].Din ipotezele problemei

N_j= (1)

Deoarece pe o iesire intr-un interval [kT k+1)T],kN pot scoate un singur pachet pentru golirea bufferelor de intrare timpul minim este:

t_min=T+T (2)

(T=interval elementar=durata unei celule ATM).

Pentru a obtine t_min dat de (2) trebuie sa nu existe blocaje 'HOL',pentru iesirea maxim solicitata (iesirea maxim solicitata este acea iesire l pentru care exista N_l solicitari si

N_lN_k, lk, l,k=)

Deci t_min +1]*T (3) in conditiile in care nu am blocaj 'HOL' pentru iesirea maxim solicitata.

4.

Coeficientii de utilizare vor fi calculati in intervalul de timp [0,t] unde t=timpul scurs intre introducerea primelor pachete in bufferele de intrare si golirea bufferelor de intrare.

Folosind problema anterioara putem considera t=t_min+T (1),unde este o 'suplimentare' a timpului minim de golire a bufferelor de intrare datorate blocajului 'HOL' al iesirii cea mai solicitata.

Cu relatia (3) din problema anterioara t +1+]*T M₁= +1+ (2) (numar necesar de perioade elementare pentru extragerea tuturor pachetelor din bufferele de intrare).

Coeficientii medii de utilizare se obtin sub forma (C_{j med})_max= ,j=.

b) Cauza este blocajul 'HOL' al iesirii celei mai solicitate care conduce la un timp mai mare de golire a tuturor bufferelor de intrare.Cum numarul de solicitari pentru fiecare iesire este fix, daca k_ij sunt date (difera doar ordinea lor) vom avea acelasi numar de pachete scoase pe fiecare iesire, dar intr-un timp mai mare (C_{j med}) < (C_{j med})_max.

5

Pentru a obtine un timp maxim de golire trebuie sa avem un blocaj 'HOL' cat mai pronuntat.Vom construi intai o distributie cu aceasta proprietate (blocaj 'HOL' maxim) si vom evalua timpul de golire obtinut pe aceasta distributie .Acest timp va fi maximul timpului de golire al tuturor bufferelor de intrare.

Un exemplu de distributie cu blocaj 'HOL' maxim este prezentat in figura de mai jos:

Prima extragere se face la t₀ =T

. fig. 12

La t₁=[4(N₁/4-1)]*T+T structura este echivalenta cu structura cu distributia sosirilor din figura de mai jos (la acest moment este dirijat primul pachet spre iesirea 2 si unul din pachetele (2 ),(3,1) sau (4,1) pe iesirea 1).

Pentru a pastra situatia de blocaj 'HOL' maxim este necesar ca la momentele t₁+T,t₁+2T,t₁+3T sa fie dirijate pe iesiri pachetele : la t₁+T, la t₁+2T, la t₁+3T.La t₁+4T distributia sosirilor in bufferele de intrare este:

La t₂=t₂+4T+4(N₂-1-1)T+T este extras pachetul ultim (1,2).Inainte de t₂+T distributia sosirilor este:

La t₂+T,t₂+2T,t₂+3T,t₂+4T se extrag pachetele:

la t₂+T

la t₂+2T

la t₂+3T

la t₂+4T

Inainte de extragerea de la t₂+4T distributia sosirilor este:

La t=t2+4T+4(N3/4-1-1)T+T se extrage ultimul pachet (1,3).

La t₃+T,t₃+2T,t₃+3T,t₃+4T au loc extragerile:

la t₃+T

la t₃+2T

la t₃+3T

la t₃+4T

Dupa extragerea de la t₃+4T ramin 4(N₄/4-1) pachete in fiecare buffer de intrare, toate solicitind iesirea Pentru extragerea lor este necesar timpul 4(N₄/4-1)T.Deci timpul este:

t=t₃+4T+4(N₄/4-1)T+T=t₃+N₄*T=t₂+4T+N₃*T-8T+N₄*T=t₁+4T+N₂*T-8T+T+4T9+N₃*T-8T=(N₁+N₂+N₃+N₄)T-11T=(_i-9)T

Dar _i=4(M+1) (numarul total de celule in intervalul [0,M*T]=4*(M+1)=4M+4 t_max=(4M-5)T.

6.

Pentru minima utilizare a iesirilor trebuie sa avem maxim de blocaj 'HOL', deci o distributie de tipul celei din problema II.5.Se obtine M₁ (definit la II.4.) ca numar maxim de tacti pentru golirea tuturor bufferelor de intrare.

M₁=_i-9

C_jmed=N_j/M₁ ,j=1..4

Observatii:

1) S-au presupus N₁,N₂,N₃,N₄ suficienti de mari a.i. _i>9

_i=4+(M+1) (trafic pe intrare =1 numarul total de celule sosite in [0,M*T] este (M+1)T*nr.intrari=(4M+4)*T

3)Conform (2) obtinem :

t_max=(4M-5)T

(C_jmed)_min=N_j/(4M-5) ,j=1..4.

7.

t=T t=2T

t=3T t=4T

La t=5T : (1,1) , (2,3) , (3,2)

t=6T : (2,1) , (4,2)

la t=7T bufferele sunt goale

Pentru w=1 au loc extragerile succesive:

t=T : (1 )

t=2T : (1,2) , (2,1)

t=3T : (1,2) , (3,1)

t=4T : (3,3) , (4,1)

t=5T : (1,1) , (3,3) , (4,4)

t=6T : (2,1) , (3,2) , (4,4)

t=7T : (3,4) , (4,2)

t=8T : (2,1)

La t=9T bufferle sunt goale

8)

a) Un exemplu de distributie care maximizeaza timpul de golire a bufferelor de intrare este:

fig. 21

Sa presupunem loc[1]=1 (notatiile anterioare).Atunci succesiunea de extragere a pachetelor este (presupunand o politica circulara de servire a bufferelor de intrare) :

t=0 : (1 )

t=T₀ : (2 )

.

.

.

t=4T₀ : (1 )

t=5T₀ : (2 ),(1,2)

t=6T₀ : (3 ),(2,2)

t=7T₀ : (4 ),(3,2)

t=8T₀ : (4 )

t=9T₀ : (1 )

t=10T₀ : (2,2),(1,3)

t=11T₀ : (3,2),(2,3)

t=12T₀ : (4,2),(3,3)

t=13T₀ : (4,3)

t=14T₀ : (1,3)

t=15T₀ : (2,3),(1,4)

t=16T₀ : (3,3),(2,4)

t=17T₀ : (4,3),(3,4)

t=18T₀ : (4,4)

t=19T₀ : (1,4)

t=20T₀ : (2,4)

t=21T₀ : (3,4)

t=22T₀ : (4,4)

Deci timpul de golire a bufferelor este 23T₀

b) Pentru fereastra de analiza W=2 succesiunea de extragere a pachetelor este:

t=0 : (1 )

t=T₀ : (2 ),(1,2)

t=2T₀ : (3 ),(2,2)

t=3T₀ : (4 ),(3,2)

t=4T₀ : (1 ),(4,2)

t=5T₀ : (2 ),(1,2)

t=6T₀ : (3 ),(2,2),(1,3)

t=7T₀ : (4 ),(3,2),(2,3),(1,4)

t=8T₀ : (4 ),(3,3),(2,4)

t=9T₀ : (4 ),(1,4)

t=10T₀ : (1,3),(2,4)

t=11T₀ : (2,3),(3,4)

t=12T₀ : (3,3),(4,4)

t=13T₀ : (4,3),(3,4)

t=14T₀ : (4,4)

timpul de golire =15T₀.

9) Distributia cea mai defavorabila este formata din cate 4M pachete pentru fiecare ieºire plasate ca in figura de mai jos:

(1 ) (2,1) (3,1) (4,1)

(1 ) (2,1) (3,1) (4,1)

. . . .

(1 ) (2,1) (3,1) (4,1)

(1 ) (2,2) (3,2) (4,2)

(1 ) (2,2) (3,2) (4,2)

(1 ) (2,2) (3,2) (4,2)

. . . .

(1 ) (2,2) (3,2) (4,2)

(1 ) (2,3) (3,3) (4,3)

(1 ) (2,3) (3,3) (4,3)

. . . .

(1 ) (2,3) (3,3) (4,3)

(1 ) (2,4) (3,4) (4,4)

(1 ) (2,4) (3,4) (4,4)

. . . .

(1 ) (2,4) (3,4) (4,4)

fig. 21

a) W=1.

Pentru 'eliminarea' primelor 4M pachete este necesar timpul 4MT₀. In acest timp, dupa extragerea ultimelor pachete (1,1),(2,1),(3,1) mai pot fi scoase pe iesiri 3 pachete ce solicita iesirea 2 ( (4,2),(2,2),(3,2) ).

Deci dupa 4MT₀ s-au extras: -4M-pachete cu iesirea 1

-3 -pachete cu iesirea 2.

Pachetele ce solicita iesirea 2 vor fi 'eliminate' in (4M-3)T₀. Dupa extragerea ultimelor pachete (1,2),(2,2),(3,2) se scot pe iesiri si pachetele (1,3),(2,3),(3,3) astfel ca dupa (4M+4M-3)T₀ in bufferele de intrare mai exista (4M-3) pachete ce solicita iesirea 3 si 4M pachete ce solicita iesirea 4.

Continuand rationamentul de mai sus obtinem timpul de golire t 16M-9)T₀.

b) W=2.

Presupunem M>2 (cazul M=2 a fost tratat in problema anterioara). La t₁=4(M-2)T₀ situatia in bufferele de intrare este:

(1 ) (2,1) (3,1) (4,1)

(1 ) (2,1) (3,1) (4,1)

(1 ) (2,2) (3,2) (4,2)

. . . .

. . . .

. . . .

(1 ) (2,2) (3,2) (4,2)

. . . .

. . . .

. . . .

Urmeaza 'extragerile' :(W=2)

t₁ : (2 ),(1,2)

t₁+T₀ : (3 ),(2,2)

t₁+2T₀ : (4,1),(3,2)

t₁+3T₀ : (1,1),(4,2)

t₁+4T₀ : (2,1),(1,2)

t₁+5T₀ : (3,1),(2,2)

t₁+6T₀ : (4,1),(3,2)

Deci in 4MT₀ se extrag toate pachetele ce solicita iesirea 1 + 7 pachete ce solicita iesirea 2.

Dupa (4M+4M-6)T₀ bufferele de intrare nu mai contin nici un pachet ce solicita iesirea 2.

Continuand rationamentul t 16M-16)T₀.

10)Se da un comutator cu buffere la iesire 'knockout' 88 cu concentrator de L=4 iesiri.

La momentele t=0,T,2T pe intrarile comutatorului sosesc pachetele:

0 : (1,1) (2,1) (3,2) (4,3) (5,3) (6,1) (7,2) (8,3)

T : (1,2) (2,2) (3,1) (4,3) (5,4) (6,6) (7,7) (8,7)

2T : (1,1) (2,1) (3,2) (4,5) (5,1) (6,8) (7,4) (8,3)

1) Sa se precizeze iesirile active ale filtrelor de adresa de pe iesirea 1 la momentele t=0,T,2T.

2) Sa se precizeze iesirile active ale shifterului corespunzatoare iesirii 1 la momentele t=0,T,2T.

3) Precizati starea bufferului de iesire BO₁ incepand cu t=0 ,pana la golirea sa completa , stiind ca este organizat sub forma a L=4 buffere servite circular.

Obs.:Se presupune ca pentru t>2T pe intrarile comutatorului nu mai sosesc pachete

Solutie

Schema unei iesiri pentru comutatorul 'knockout' este prezentata in fig.1:

a) Filtrele de adresa de pe iesirea 1 au iesiri active atunci cand adresa de destinatie a pachetului sosit pe intrarea filtrului este 1. Deci iesirile active ale filtrelor de adresa de pe iesirea 1 vor fi :

1,2,6

T : 1,3

2T : 1,2,5

b) Tinand cont de principiul de functionare al shifterului ,iesiri active din shifter vor fi :

1,2,3

T : 4,1

2T : 2,3,4