CMT Seminar 5 2004: Protocoale de transmisiune 1. 1000 de staţii pentru transmisia datelor sunt conectate la o magistrală lungă de 500 m. Fiecare staţie trebuie să trimită 30 de pachete de câte 2000 biţi, în fiecare secundă, către altă staţie de pe magistrală. Rata de transmisie pe bus este de 100Mbps. Care din următoarele protocoale poate fi utilizat: P-Aloha, S-Aloha sau Ethernet? Se presupune că viteza de propagare pe bus este 2.25*108 m/s. Soluţie: OBS: Încărcarea totală (eficienţa necesară, traficul util normat, raportul între numărul de pachete transmisie cu succes şi numărul total de pachete) se defineşte ca fiind încărcarea per staţie * numărul de staţii. Dacă toate cele 30 de cadre s-ar transmite cu succes am avea:

6.01000*100

/2000*sec/30 ==⋅⋅=

=⋅⋅=

MbpscadrubiticadreN

RbN

NN

statiisucces

statiisucces τρ

unde: Nsucces = nr. de pachete transmise cu succes; b = nr. de biţi dintr-un pachet (cadru); R = rata de transmisie. τ = durata pachetului

Aloha pur Staţiile pot transmite oricând. Dacă nu primesc ACK, se re-transmite pachetul. Perioada de vulnerabilitate: τ2 Eficienţa necesară este 0.6 > 0.18 (eficienţa maximă asigurată de Aloha pur), deci Aloha pur nu poate fi utilizat. Slotted Aloha Staţiile pot transmite doar la începutul cadrelor. Perioada de vulnerabilitate: τ 0.6 > 0.368 (eficienţa maximă asigurată de slotted Aloha), deci nici slotted Aloha nu poate fi folosit. Ethernet (CSMA-CD - Carrier Sense Multiple Access with Collision Detection) Înaintea unei transmisii se ascultă mediul. Se începe tranmisia. Se detectează dacă avem coliziuni pe durata transmisiei. Dacă da, se abandonează transmisia, se aşetaptă un timp aleator şi se re-transmite. Timpul maxim de propagare între două staţii (timpul în care detectăm dacă există activitate în

canal): ssm

mTp µ22.2/10*25.2

5008 ==

Timpul pentru a transmite cu succes un pachet este 2Tp + Tix. Deoarece Tix > 2Tp rezultă că toate coliziunile pot fi detectate.

Timpul de transmisiune: ssbiti

bitiTix µ20/10*100

20006 ==

Eficienţa protocolului Ethernet: a51

1+

, ix

p

TT

a = => 64.051

1511 =

+=

+=

ix

pEthernet

TTa

ρ , deci se

poate utiliza protocolul Ethernet. 2. Fie o reţea cu două staţii de transmisie a datelor A şi B care au acces la o resursă comună L (ex. două calculatoare care sunt conectate la o imprimantă). A şi B încearcă să acceseze L trimiţând mai multe cadre şi se presupune că A şi B implementează următoarea strategie: fiecare încearcă să transmită într-un anumit slot temporal cu probabilitatea pA, respectiv pB, independent unul de celălalt. Dacă ambele staţii transmit în acelaşi slot se produce o coliziune şi cadrele trebuie retransmise.

a. Calculaţi eficienţa schemei propuse ρ; b. Care este valoarea maxim posibilă a lui ρ? Este de dorit ca reţeaua să funcţioneze la

eficienţa maximă? c. Se presupune că lui A i se impune o probabilitate pA = 0.3. Care este valoarea maximă

a lui ρ cu această constrângere? Care este numărul mediu maxim al cadrelor per slot pe care le poate trimite A cu pA = 0.3? Care este numărul mediu maxim al cadrelor per slot pe care le poate trimite B şi ce se întâmplă cu A în acest caz?

d. Presupunem că pA = 0.5. În acest caz ρ mai depinde de pB? Comentaţi răspunsul. Soluţie: a. ρ = P{succes} = P{A transmite şi B nu transmite} sau P{B transmite şi A nu transmite}= = pA (1 - pB) + pB (1 - pA) = pA + pB – 2 pA pB; b. Valoarea maximă a lui ρ se atinge când pA = 1 şi pB = 0, sau pB = 1 şi pA = 0. În fiecare din aceste cazuri ρ = 1. Aceasta nu este o situaţie de dorit, deoarece în acest caz doar o singură staţie transmite. c. Temă. d. Temă. Protocolul slotted Aloha 3. Monitorizând performanţele unei scheme S-Aloha se observă că în medie 10% din sloturi sunt libere şi 60% din sloturi poartă pachete afectate de coliziune. Se poate presupune că această acest proces este de tip Poisson? Soluţie: P{slot gol} = 0.1 = e-G => G = 2.3; P{slot cu pachet afectat de coliziune} = 0.6; Transmisia este cu succes când pachetul se găseşte într-un slot care nu este nici gol, nici nu conţine un pachet afectat de coliziune. P{transmitere cu succes} = 1 – 0.1 – 0.6 = 0.3. Dar se ştie că P{succes pentru S-Aloha} = Ge-G şi dacă utilizăm valoarea calculată a lui G (=2.3) rezultă P{succes} = 2.3e-2.3 ≈ 0.23 ceea ce este diferit de 0.3. Deci procesul nu poate fi de tipul Poisson.

Protocolul Ethernet 4. 200 de calculatore sunt legate prin protocolul Ethernet utilizând o magistrală de 1500m (trei segmente de cablu coaxial de câte 500m). Rata de transmisie este 10Mbps şi fiecare cadru are 800 biţi. Câte pachete pe secundă poate trimite fiecare PC cu succes? Se presupune că viteza de propagare pe bus este 2.25*108 m/s. Soluţie:

Timpul maxim de propagare: ssm

mTp µ67.6/10*25.2

15008 ==

Timpul de transmisiune: ssbiti

bitiTix µ80/10*10

8006 ==

706.051110*33.8

8067.6

max2 =

+==>=== −

aTT

aix

p ρ

=> rata de transmisie efectivă: 0.76*10Mbs=7.06 Mbps. Din aceasta, un calculator transmite efectiv (cu succes) 7.06 Mbps/200=35.5 kbps, ceea ce înseamnă: 35.5 kbps/(800 biţi/pachet)=44.125 pachete/secundă Traficul în reţele celulare 5. În tabelele de mai jos sunt prezentate rezultatele supravegherii traficului într-o reţea de telecomunicaţii în decursul unei ore de vârf. În primul tabel sunt prezentate duratele apelurilor efectuate în decursul ore de vârf în funcţie de procentajul abonaţilor în grupuri. În al doilea tabel este prezentată distribuţia numărului de apeluri în funcţie de procentajul de abonaţi.

Durata apelurilor (min) Procent abonaţi (%) 0 – 1 50 1 – 2 30 2 – 3 15

3 – 10 5

Număr apeluri Procent abonaţi (%) 0 – 1 60 1 – 2 30

2 – 10 8 > 10 2

Să se calculeze densitatea traficului per abonat. Soluţie: Traficul celular se defineşte ca numărul de apeluri de la telefoanele mobile pe un grup de canale, luându-se în considerare durata apelurilor. Densitatea traficului celular într-o celulă este definită ca produsul între numărul de apeluri efectuate într-un interval de timp şi durata medie de aşteptare a apelului:

htE ⋅= λ

unde λ este rata de sosire a apelurilor (variabilă aleatoare - exprimată în apeluri/oră) iar th este timpul mediu de aşteptare exprimat în ore/apel (variabilă aleatoare - timpul de ocupare a unei căi de trafic de către o convorbire). E este adimensoinal, dar uzual se exprimă în erlangi (după numele teoreticianului danez A.K. Erlang). Se determină durata medie a apelurilor per oră cu ajutorul primului tabel:

th = 0.5min*0.5 + 1.5min*0.3 + 2.5min*0.15 + 6.5min*0.05 = = 1.4 min /convorbire /abonat = 0.023 ore / convorbire / abonat.

Presupunând că numărul de apeluri mai mare de cât 10 este egal cu 10 din motive legate de uşurinţa calculelor, se determină rata medie de sosire a apelurilor:

λ = 0.5*0.6 + 1.5*0.3 + 6*0.08 + 10*0.02 = 1.43 apeluri / oră. Prin urmare, rezultă traficul total per abonat este:

E = λ*th = 1.43 apeluri / oră * 0.023 ore/ convorbire / abonat = 0.033 erlangi / abonat. Alocarea fixă a canalelor 6. Fie un sistem de radiocomunicaţii celulare în care densitatea traficului este A = 0.25 erlangi. În condiţiile în care numărul de trunchiuri este S = 1, 2 şi 5 să se determine probabilitatea de blocare utilizându-se fiecare din formulele Erlang B, Erlang C şi Poisson. Soluţie: În cazul modelului Erlang B apelurile blocate sunt rejectate imediat şi nu apar într-o coadă de aşteptare. Pentru modelul Erlang C apelurile blocate sunt întârziate până la deservire. În cazul adoptării modelului Poisson, un apel care apare în momentul în care toate trunchiurile sunt ocupate aşteaptă până la expirarea duratei de aşteptare. Dacă un trunchi devine liber înaintea expirării duratei de aşteptare, apelul este deservit; dacă nu, apelul este rejectat. Distribuţia Poisson

AS

i

iA

Si

i

B eiAe

iAP −

−

=

−∞

=∑∑ ==1

0 !!

S = 1 => PB = 0.2212; S = 2 => PB = 0.0265; S = 5 => PB = 0.000133; Algoritmul Erlang-B

∑=

=S

i

i

S

B

iA

SA

P

0 !

!

S = 1 => PB = 0.2; S = 2 => PB = 0.0243; S = 5 => PB = 0.000006339;

Algoritmul Erlang-C

∑−

= −+

−=1

0 !!

!S

i

Si

S

B

ASS

SA

iA

ASS

SA

P

S = 1 => PB = 0.25; S = 2 => PB = 0.003226; S = 5 => PB = 0.00000845159; Traficul adiţional 7. Se consideră că pentru un singur trunchi ce deserveşte utilizatorii unei reţele mobile, probabilitatea de a fi complet ocupat în decursul orelor de vârf este 20%. Dacă numărul de trunchiuri creşte de 6 ori, să se determine traficul adiţional disponibil în condiţiile aceleiaşi probabilităţi de blocare. Se vor utiliza modelele Erlang B, Erlang C şi Poisson. Soluţie: Se determină traficul iniţial pentru S = 1, utilizând cele 3 modele: Poisson:

erlangiPAeP BA

B 223.0)1ln(1 =−−==>−= − Erlang-B:

erlangiP

PAA

APB

BB 25.0

11=

−==>

+=

Erlang-C:

erlangiPA

AAA

A

P BB 2.0

11

1 ===>

−+

−=

Pentru cazul S > 1 ecuaţiile sunt transcedentale şi găsirea soluţiei se face prin metoda iteraţiilor succesive. În cazul modelului Poisson, după 113 iteraţii se obţine: A = 3.90366 erlangi, în cazul modelului Erlang-B după 58 iteraţii se obţine densitatea traficului: A = 5.10864 erlangi, iar în cazul Erlang-C după 117 iteraţii se obţine densitatea traficului: A = 3.6173 erlangi, cu o eroare mai mică de 10-8. Traficul per canal se determină împărţind densităţile de trafic obţinute anterior la numărul de trunchiuri, iar traficul adiţional se obţine scăzând această densitate de trafic din densitatea de trafic obţinută în cazul S = 1.