Post on 22-Jan-2016
description
Algoritmi optimizați pentru combatereacongestiei la nivel rețea
Conducător proiect:Conf. Dr. Ing. Ștefan Stăncescu
Absolvent:Dobrescu Răzvan
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
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
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
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
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
Combaterea congestiei – Când?
Buffer-ul router-ului este plin
Numărul de pachete eliminate este foarte mare
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ă
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
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
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
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
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
AOCC – II
Posibilitatea de a varia
parametri pentru studierea
comportamentului
algoritmilor Obținerea unei baze
statistice mari Câștig operațional
AOCC - III
Evaluarea comparativă a 3 algoritmi: REDRED modificatBLUE
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
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}
Evaluare RED vs RED modificat II Rezultate obţinute:
îmbunătăţirea ratei de pierdere a pachetelor
Evaluare RED vs RED modificat III Gradul de utilizare al reţelei este acelaşi
Evaluare RED vs RED modificat IV Imbunătăţire a lăţimii de bandă folosite
Evaluare RED vs RED modificat vs BLUE - I Performanţe mai bune ale algoritmului
BLUE
Evaluare RED vs RED modificat vs BLUE
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
Vă multumesc!