Algoritmi optimizaţi pentru gestiunea memoriilor cache în

servere Proxy

Conducător ştiinţific: Absolvent:Conf. Dr. Ing. Ştefan Stăncescu Lupu Anca Gabriela

Descrierea problemeiNumărul de utilizatori ce accesează World Wide Web este

într-o continuă creştereInternetul are şi în prezent o evoluţie rapidă, datorită

multitudinii de servicii şi informaţii care se transpun în mediul software

Au apărut probleme de acces la resursele de pe WWW (latenţe mari, supraîncărcarea serverelor, congestia în anumite puncte în reţea, timpi mari de conexiune)

Distanţele dintre reţele sunt într-o continuă creştere, datorită adăugării de noi echipamente pentru a face faţă cererilor

Cererea pentru bandwidth este foarte mare, datorită creşterii popularităţii serviciilor ce ocupă o mare parte din bandă: streaming video, jocuri online, VoIP etc.

Soluţia: web caching-ulWeb caching = tehnică ce presupune salvarea

obiectelor web pentru care s-au primit cereri într-o locaţie mai aproape de utilizatori

Avantaje: Reduce traficul în reţea Reduce latenţa de acces Reduce volumul de muncă al serverelor web • Dezavantaje: Clienţii pot primi date neactualizate de la serverele cache Un singur proxy într-o reţea – “single point of failure”

Tipuri de web cacheProxy cacheCache transparentReverse proxy cacheWeb cache adaptivCache activ

Proxy cache-ul SquidRolul de proxy = intermediar într-o tranzacţie

web între utilizatori şi serverele de pe Internet

Rolul de server cache = stochează conţinutul web adus de la serverele de origine pentru o viitoare reutilizare

Politici de înlocuireProxy-urile pot influenţa puternic performanţele unei

reţeleCapacitate limitată de stocare a datelor în cache ->

politici de înlocuire a obiectelor web din cacheParametri ce influenţează performanţele algoritmilor: Dimensiunea obiectelor Costul de aducere în cache Localitatea temporală Frecvenţa accesărilorPoliticile implementate în Squid: LRU LFUDA GDSF

GDSF (Greedy-Dual-Size-Frequency)Asociază fiecărui obiect din cache o cheieÎn funcţie de dimensiunea cheii, obiectele pot

fi favorizate sau nu pentru înlocuireCheia se calculează cu formula:H(p) = L + F(p) * C(p) / S(p) L – mecanism de îmbătrânire F – frecvenţa accesărilor C – costul asociat obiectului S – dimensiunea obiectului

GDSF - newIdei de îmbunătăţire a performanţelor: Se atribuie o pondere mai mică dimensiunii în formula de

calcul a cheii Se interpretează costul ca o măsură a recenţei obiectului în

cache• H(p) = L + F(p) * C(p) / S(p) ˆ x Unde x < 1 C(p) = (timp_curent – timp_lastref) / diferenta_medie_timp• diferenta_medie_timp = (timp_lastref – timp_insert_cache) / (F(p)

– 1)

Schema funcţională a aplicaţiei

Rezultate obţinuteHit rate pentru 10, respectiv 20 de utilizatori

Hit rate în funcţie de numarul de bytes transferaţi

Total network throughput

ConcluziiNoul algoritm, cu diferitele variante ce

corespund diferitelor valori ale parametrului x, prezintă în general performanţe mai bune decât algoritmul iniţial

Noul algoritm asigură un throughput total mai mare decât GDSF iniţial

Vă mulţumesc pentru atenţia acordată