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!