![Page 1: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/1.jpg)
Algoritmi optimizați pentru combatereacongestiei la nivel rețea
Conducător proiect:Conf. Dr. Ing. Ștefan Stăncescu
Absolvent:Dobrescu Răzvan
![Page 2: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/2.jpg)
Agenda
Congestia în rețele de comunicație Combaterea congestiei Metode de prevenire a congestiei (RED) Algoritmul RED modificat AOCC Evaluare RED vs RED modificat Evaluare RED vs RED modificat vs BLUE Concluzii
![Page 3: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/3.jpg)
Congestia în rețele de comunicație - I
Prezența în rețea a unui număr foarte mare de pachete
Mai multe căi de intrare căutând aceeași cale de ieșire
![Page 4: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/4.jpg)
Congestia în rețele de comunicație - II Pe măsură ce numărul de pachete
crește, numărul de pachete pierdute crește și el
![Page 5: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/5.jpg)
Combaterea congestiei – De ce?
Întârzieri cât mai mici
Viteză de trasmisie a informației mare
Obținerea unui throughput cât mai mare
![Page 6: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/6.jpg)
Combaterea congestiei – Unde? Nivelurile 3 & 4 – Rețea & Transport
Nivelul rețea Imagine completă asupra rețeleiAsigurarea căii optime
Nivelul transportTransferul fiabil al informațieiControl al erorilor
Aplicație
Prezentare
Sesiune
Transport
Rețea
Legături de date
Fizic
date
date
date
segmente
pachete
cadre
biți
Modelul OSI
![Page 7: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/7.jpg)
Combaterea congestiei – Când?
Buffer-ul router-ului este plin
Numărul de pachete eliminate este foarte mare
![Page 8: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/8.jpg)
Combaterea congestiei – Cum ? Implementarea unor algoritmi pentru
prevenirea apariției congestiei
Semnalarea congestiei – marcarea pachetelorSetarea unui bit în antetul pachetelorAruncarea efectivă a pachetelor din coadă
![Page 9: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/9.jpg)
Metode de prevenire a congestiei (RED) Random Early Drop (Discard) Pachetele sunt alese aleator Criteriul de marcare a pachetelor din
coadă : lungimea medie a cozii Algoritmul RED:
Calculul lungimii medii a coziiCompararea cu două praguri: minim &
maximDecizia: marcare sau nu
![Page 10: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/10.jpg)
Metode de prevenire a congestiei (RED)
se calculează lungimeamedie a cozii - avg
avg < min th min th < avg < max th max th < avg
se calculează probabilitateade marcare a pachetului
pachetașezat în coadă
pachetmarcat
probabilitate marealtfel
Pachet sosit avg – lungimea medie a coziimin th – pragul minimmax th – pragul maxim
![Page 11: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/11.jpg)
Algoritmul RED modificat I Optimizarea: micșorarea ratei de
pierdere a pachetelor Modalitate: modificarea calculului
lungimii medii a cozii, prin introducerea unui parametru în calculul lungimii medii a cozii
Criteriu de decizie: lungimea cozii curente
![Page 12: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/12.jpg)
Algoritmul RED modificat - II
pb= maxp
avg - minth
maxth - minth
pa=pb
1 – count * pb
q = lungimea curentă a cozii
q = 0
q < minth
q > minth
avg =(1-wq)m * avg
param
avg =(1-wq) * avg
param+ wq * q
avg = (1-wq) * avg + wq * q
![Page 13: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/13.jpg)
AOCC – I Tehnologii folosite
Network Simulator 2.33○ Simulator pentru rețele
MonoDevelop 2.0○ Mediu de dezvoltare – C# , .NET
Awk○ Aplicație folosită pentru filtrarea fișierul cu
rezultateGnuplot
○ Aplicație folosită pentru realizarea graficelor
![Page 14: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/14.jpg)
AOCC – II
Posibilitatea de a varia
parametri pentru studierea
comportamentului
algoritmilor Obținerea unei baze
statistice mari Câștig operațional
![Page 15: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/15.jpg)
AOCC - III
Evaluarea comparativă a 3 algoritmi: REDRED modificatBLUE
![Page 16: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/16.jpg)
AOCC - IV
Modul de funcționare:Se introduc parametrii dorițiParametrii sunt preluați de nsRezultatele simulărilor sunt salvateCu ajutorul awk sunt obținute rezultatele
finaleIn final, sunt afișate graficele cu rezultate
folosind gnuplot
![Page 17: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/17.jpg)
Evaluare RED vs RED modificat I Topologia considerată
S1
S2
S3
S18
S19
S20
R D
10 Mbps, 1ms
0.7 Mbps, 20msRED standard / RED modificat
minth = 5 pachetemaxth = 15 pachetewq = 0.002param = {1,1.05,…3}
![Page 18: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/18.jpg)
Evaluare RED vs RED modificat II Rezultate obţinute:
îmbunătăţirea ratei de pierdere a pachetelor
![Page 19: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/19.jpg)
Evaluare RED vs RED modificat III Gradul de utilizare al reţelei este acelaşi
![Page 20: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/20.jpg)
Evaluare RED vs RED modificat IV Imbunătăţire a lăţimii de bandă folosite
![Page 21: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/21.jpg)
Evaluare RED vs RED modificat vs BLUE - I Performanţe mai bune ale algoritmului
BLUE
![Page 22: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/22.jpg)
Evaluare RED vs RED modificat vs BLUE
![Page 23: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/23.jpg)
Concluzii Algoritmul RED modificat aduce
imbunăţiri de performanţă Găsirea valorilor optime ale pragurilor
maxth şi minth rămâne încă o problemă Pentru reţele cu schimbări mari de
trafic,algoritmul BLUE obţine rezultate mai bune
AOCC poate ajuta în studiul performanţelor algoritmilor de combatere a congestiei
![Page 24: Algoritmi opt imizați pentru combaterea congestiei la nivel rețea](https://reader036.vdocumente.com/reader036/viewer/2022062301/56815145550346895dbf6745/html5/thumbnails/24.jpg)
Vă multumesc!