Auto-similaritatea traficului in internet

Figura 9. Raspunsul in timp normalizat R(p)/p
Parametrii de partajare asigura discriminare efectiva pentru timpul de transfer al documentelor mici iar throughputul pentru ambele clase tinde catre pe masura ce marimea documentelor creste. Throughputul limita pentru obiectele mari este explicat prin aceea ca indifferent de parametrul de partajare , un transfer foarte lung utilizeaza toata banda exceptand cea solicitata de alti useri, egala in medie .

Rezultatele pentru distributii hiperexponentiale arata ca discriminarea este mai eficienta pe masura ce variabilitatea distributiei marimii documentelor creste. Este deci mai probabil ca pentru o distributie cu coada lunga cele mai multe transferuri de documente vor inregistra o imbunatatire a throughputului cu o pondere in crestere desi imbunatatirea este mai mica decat proportionala si tinde sa dispara pentru documentele foarte mari.

Throughputul obiectelor mari nu este afectat de catre rata asignata transferului de obiecte mici care incepe si se termina pe durata unui transfer de obiect mare. Throughputul global poate fi imbunatatit dand prioritate obiectelor mici. Se stie ca performanta timpului de raspuns a unei resurse partajate este optimizata folosind timpul cel mai mic ramas pentru procesare din toti timpii pentru procesari diferite. Aceasta disciplina de programare presupune existenta unui controller care sa stie volumul de date ramas al tuturor documentelor ce trebuie transferate si confera capacitatea liniei exclusiv celui mai mic. Daca o noua sosire vizeaza un document a carui marime este mai mica decat a celui care este deservit, acesta este preluat si transferul care era in curs este reluat de unde a ramas de indata ce volumul acestuia devine din nou cel mai mic.

Performanta acestei abordari a fost studiata de catre Schrage si Miller. Ei au obtinut expresii pentru timpul de raspuns R(p) a unui document de marime p sub presupunerea ca sosirile sunt distribuite Poisson si o distribuite generala a timpilor de deservire. Figura 10 arata o evaluare numerica formulelor pentru distributii ale marimii documentelor de tip exponential si Pareto cu dispersie infinita. Incarcarea liniei este 2/3. axa p, in unitati ale marimii medii a documentelor, este o scara logaritmica pentru a scoate in evidenta particularitatea de coada lunga a distributiei Pareto.

Figura 10. Raspunsul normalizat in timp R(p)/p
Timpul de raspuns normalizat este considerabil mai mic ca acela al unei partajari perfect echitabile. Acest exemplu ofera o ilustrare clara a faptului ca echitabilitatea sau echitabilitatea ponderata nu constituie neaparat un obiectiv folositor in impartirea benzii. Se arata ca atat userii cat si providerul de retea castiga prin favorizarea obiectelor mici. Modelul de procesor de partajare arata cum performanta se poate deteriora dintr-o data pe masura ce se apropie de 1: daca capacitatea liniei c este mare, performanta throughputului e buna chiar daca este aproape de 1. Pentru incarcari mai mari, throughput este zero si numarul de transferuri in desfasurare descreste indefinit. Binenteles, modelul nu mai este de acuratete deoarece multi utilizatori reali vor abandona transferurile de indata ce vor remarca efectele unei asemenea congestii.
5.7.2 Controlul acceptarii pentru traficul elastic

Controlul acceptarii prin limitarea numarului de fluxuri ce folosesc o legatura data, asigura ca throughputul nu descreste niciodata sub un nivel minim acceptabil pentru fluxurile care sunt admise. Nu este clar ce inseamna throughput cu nivel minim acceptabil. Alegerea depinde de un compromis intre utilitatea suplimentara de a accepta un nou flux si riscul ca transferurile sa fie prematur intrerupte daca rata lor descreste. Un asemenea minim exista altfel o retea saturata ar fi instabila.

Controlul acceptarii nu implica neaparat operatii complexe cu schimburi de semnale explicite intre utilizator si nodurile retelei. Acest lucru ar fi destul de inacceptabil pentru majoritatea fluxurilor elastice care sunt de durata foarte scurta. Nodurile care implementeaza controlul acceptarii tin o evidenta a identitatilor fluxurilor existente ce traverseaza fiecare legatura pentru a putea recunoaste sosirea unui pachet de la un lux nou. Asemenea pachet este acceptat si identificatorul sau adaugat la lista fluxurilor active daca numarul de fluxuri aflate in derulare este mai mic decat un prag si altfel este rejectat. Un flux este sters din lista daca nu a trimis pachete intr-un interval de timp prestabilit.

Insa, date fiind noile evolutii a tehnologiei routerelor, aceasta procedura nu mai este fezabila din punct de vedere tehnica. Cunoasterea starii legaturilor retelei in termeni de numar de fluxuri aflate in desfasurare permite de asemenea strategii de rutare inteligente caz in care fluxurile nu sunt trimise orb catre legaturi saturate atunci cand sunt disponibile alte legaturi.

5.7.3 Definirea unui model simplu de servicii.

5.7.3.1 Clasele de servicii

Se defineste un model de serviciu cu doar doua clase de servicii, una bazata pe control in bucla deschisa si alta ce foloseste control in bucla inchisa pentru trafic elastic. In acest model de servicii, fluxurile destinate pentru prima clasa declara doar o rata de varf care este influentata de distanta dintre pachete la intrarea in retea. Controlul acceptarii bazat pe masuratori este folosit pentru a asigura pierderi de date neglijabile presupunand multiplexarea fara buffere. Desi, in practica, este necesar un mic buffer pentru a compensa natura nonfluida a traficului, intarzierea si variatia intarzierii ramanand foarte mici. Performantele pierderilor si intarzierilor sunt independente de orice dependenta de raza lunga in procesul de rata a fluxurilor. O rata mica a pierderilor (10^-9) este compatibila cu o utilizare medie rezonabila a legaturii (50%) daca rata de varf a fluxurilor nu e mai mare decat o mica fractiune a benzii legaturii (1/100).

Caracteristicile necesare ale controlului in bucla inchisa sunt mai putin bine intelese. Ne putem baza pe utilizatorii care reactioneaza inteligent la semnalele de congestie, ca in cazul TCP, daca reteaua implementeaza in mod aditional mecanisme de management al cozii ce previn ca fluxurile necooperative sa afecteze adevers calitatea serviciilor celorlalti utilizatori. O solutie promitatoare este de a face cozi per flux cu identificarea fluxurilor realizata pe loc. Identificarea setului de fluxuri ce folosesc o anumita legatura permite implementarea unei proceduri de control al acceptarii unde orice pachete ce provin din fluxuri noi sunt rejectate cand numarul de fluxuri aflate in derulare depaseste pragul dependent de capacitatea legaturii.

Partajarea capacitatii legaturii dinamic intre fluxuri si traficul elastic este avantajos pentru ambele tipuri de trafic: o rata de pierderi foarte mica pentru traficul in fluxuri nu este incompatibila cu utilizarea rezonabila daca traficul elastic constituie o portiune semnificativa din incarcarea totala ; fluxurile elastice castiga throughput mai mare fiind capabile sa exploateze capacitatea reziduala necesar ramasa de la traficul in fluxuri pentru a atinge obiectivele de rata de pierderi de date si de probabilitate de blocare. Controlul acceptarii atat pentru traficul in fluxuri cat si pentru traficul elastic ia in considerare incarcarea fluxului masurat si de numarul curent de fluxuri elastice rapide.

Prioritatea simpla cap de linie este suficienta pentru a este suficienta pentru a satisface cererile de intarziere ale traficului in fluxuri in timp ce fenomenul de formare a cozilor per flux este solutia preferata pentru traficul elastic. Aglomerarea echitabila in cozi pentru fluxurile elastice conduce la partajarea echitabila a benzii. Totusi, performanta ar putea fi imbunatatita prin implementarea schemelor de programare a pachetelor dand prioritate documentelor mici. Performanta schemelor de paratjare a ratei ca fenomenul de formare a cozilor echitabile si timpul de procesare cel mai scurt ramas nu pare a fi afectata de natura de coada lunga a distribuitiei marimilor documentelor.

Pentru orice aplicatie data un utilizator poate alege sa formeze un flux sau trafic elastic. Alegerea depinde de calitatea serviciilor si de cost.

5.7.3.2 Influenta incarcarii

Din motive istorice, cei mai multi useri ai internetului azi sunt taxati pe baza unei rate constante. Ei platesc o taxa fixa pe luna care este independenta de volumul de trafic pe care il produc, desi incarcarea depinde de capacitatea liniei lor de acces la retea. Avantajul major al acestui tip de taxare este simplitatea ce conduce costuri mai mici ale operarii retelei. Un punct negativ este faptul ca nu este echitabila, deoarece un utilizator care nu foloseste prea mult reteaua plateste la fel de mult ca unul ce o foloseste intens. O problema imediata ce apare este lipsa retinerii de la aceasta practica ce contribuie la starea prezenta de congestie in internet.

Folosirea retelei poate fi controlata prin introducerea incarcarii sensibile la utilizare, cu rate determinate de nivelul de congestie. Acesta este principiul taxarii in functie de congestie. Taxarea in functie de congestie conduce in mod ideal la un optim economic, unde resursele disponibile sunt folosite pentru a produce utilitate maxima. Obiectivul de control al congestiei poate fi atins prin prin oferirea unui numar de clase de servicii diferite din punctul de vedere al taxarii cu taxe care cresc in functie de nivelul de calitate a serviciilor. Utilizatorii determina suma cu care sunt taxati in functie de clasa de servicii pe care o aleg. In cazuri de congestie, inclina sa aleaga clase mai scumpe de servicii. Asemenea scheme sufera de lipsa de transparenta: cum pot utilizatorii sa isi dea seama daca providerul nu cuzeaza in mod deliberat congestia? De ce sa plateasca mai mult unui provider ineficient? Platesc mai mult decat necesar pentru date fiind nivelele actuale de traffic?

O alternativa este de a taxa utilizatorii pentru utilizare. Acesta depinde de cantitatea de resurse per tranzactie. O astfel de schema se numeste taxarea tranzactionala. Aceasta taxare este folosita in retelele telefonice. Taxarea diferentiala in functie de momentul zilei este introdusa pentru a uniformiza profilul cererii dar nu este vazut ca un mecanism de control al congestiei. Alegerea tipului de taxare depinde de capacitatea lor de a asigura viabilitatea economica a providerului. Taxarea congestiei este intentionata pentru a optimiza folosirea unei retele. Daca reteaua este bine aprovizionata din punctul de vedere al resurselor si ofera intotdeauna o calitate buna a serviciilor, atunci taxarea trebuie sa fie uniforma.

O alta problema majora este complexitatea implementarii diferitelor scheme. Orice abatere de la taxerea uniforma reprezinta o provocare in materie de implementare.

Costul implementarii unor astfel de taxari trebuie pus in balanta cu imbunatatirile in materie de eficienta.

5.7.3.3 Dimensionarea retelei

Proiectarea traficului pentru o retea multiserviciu ce manevreaza atat traficul in fluxuri cat si cel elastic nu este usoara.

Pentru a determina capacitatea retelei necesara pentru a satisface conditiile de probabilitate de blocare pentru traficul in fluxuri, este necesar sa se faca presupuneri despre procesul de sosiri ale cererilor noi, despre rata lor si despre durata lor. Se considera un model simplu de trafic ce consta dintr-o legatura ce primeste trafic de la o populatie foarte mare de useri.

Se presupune ca este posibil sa se identifice m clase distincte omogene, fluxurile din fiecare clasa avand o distributie comuna a ratelor. Fluxurile din clasa i sosesc conform unui proces Poisson de intensitate (cerere per secunda) si au o durata estimata de secunde. Rata de varf a lor este p_i. Pentru o capacitate a legaturii fixa si suficient de mare c, impactul unui flux de clasa i asupra probabilitatii de pierderi de date poate fi sumarizata intr-o singura figura, banda efectiva: banda efectiva e_i este astfel incat probabilitatea pierderii de date este neglijabila (mai mica decat o valoare propusa ca ideal) atat timp cat unde n_i este numarul de fluxuri de clasa i aflate in desfasurare.

Desi controlul acceptarii bazat pe masuratori nu se bazeaza pe identificarea diferitelor clase (unui nou flux ii este negat accesul daca rata sa de varf este mai mare decat un estimat in timp real al benzii disponibile) in scopuri de dimensionare se poate presupune ca fluxul unei clase j va fi blocat daca . Cu aceasta conditie de blocare si cu presupunerea sosirilor de tip Poisson, distributia n_i are o forma cunoscuta a produsului permitand calculul probabilitatii de blocare. Probabilitatile de blocare si ratele de pierderi de date sunt insensibile la distributia duratei fluxurilor.

O aproximatie rezonabila a probabilitatii de blocare a unui flux cu rata de varf p_i cand c este mare in raport cu e_i este data de:

(54)

Unde , si

(55)

este formula lui Erlang.

Formula este o simplificare a formulelor date de Lindberger. Are acuratete mai mica dar demonstreaza mai clar relatia structurala dintre performanta si caracteristicile de trafic. In loc de a identifica clasele de trafic pe baza trasaturilor comune de trafic, se poate dovedi mai practic sa se estimeze parametrii esentiali a si direct.

Se stie ca aplicarea formulei lui Erlang duce la economii de scala: pentru a obtine o probabilitate mica de blocare si o utilizare mare a/c, este necesar a avea o capacitate mare c. Pentru traficul multirata, si probabilitatile de blocare date de formula lui Erlang, aceeasi cerinta implica o valoare mare a . Fluxul etichetat arata cum utilizabilitatea a/c intr-un sistem simplu Erlang de pierderi variaza in functie de c pentru o probabilitate de blocare de 0.01.

5.7.3.4 Alocarea resurselor pentru trafic elastic

Urmand acelasi exemplu de servicii, se presupune ca calitatea serviciilor throughput este satisfacuta limitand numarul de fluxuri elastice pe o legatura si prin a cauta sa se dimensioneze capacitatea legaturii astfel incat probabilitatea de blocare sa fie mai mica decat o valoare mica vizata .

Se considera mai intai o legatura izolata ce are de a face numai cu fluxuri elastice. Presupunand sosiri de tip Poisson, un throughput minim , partajari echitabile si o banda a legaturii de , probabilitatea de blocare este egala cu probabiliatea de saturatie intr-un procesor M/G/1 de partajare a cozii de capacitate n:

unde este incarcarea liniei.

Deoarece fluxurile elastice folosesc banda mai eficient, probabilitatea de blocare poate fi considerabil mai mica decat probabilitatea corespunzatoare pentru traficul in fluxuri ce cere o rata constanta , dupa cum este dat in formula lui Erlang. In figura 10 se prezinta utilizarea pentru traficul elastic astfel incat B_e sa fie egala cu 0.01. rezultatele ilustreaza economiile de scala si eficienta mai mare pentru partajarea elastica.

Figura 11. Utilizarea pentru traficul in fluxuri si traficul elastic.

Avantajul partajarii elastice fata de alocarile rigide este oarecum atenuat intr-o retea unde fluxurile nu pot mereu obtine parte completa din banda diponibila a liniei din cauza congestiei pe alte legaturi din drumul lor si a ratei lor proprii limitate. Daca totusi fluxurile pot castiga o rata si aceasta rata este garantata de controlul accesibilitatii pe fiecare legatura a retelei, utilizarea prezisa de formula lui Erlang constituie o margine limita inferioara. Formula lui Erlang poate fi folosita ca o unealta conservativa de dimensionare pentru a determina capacitatea traficului unei legaturi dedicate traficului elastic : o legatura de capacitate c poate manipula un volum de trafic elastic A_e (rata de sosire a fluxului x marimea medie) cu throughput minim si probabilitate de blocare mai mica ca daca . Avand in vedere economiile de scala oferite de formula lui Erlang, o dimensionare simpla este eficienta daca este mare.

Un avantaj al unei asemenea abordari este ca integrarea traficului in fluxuri si a traficului elastic se face prin includerea ultimului ca o clasa de trafic aditional in metodele de dimensionare multirate.

Realizarea calitatii serviciilor intr-o retea multiserviciu depinde mai mult de o proiectare adecvata decat de definirea unui model de serviciu.

6. Concluzii

S-au facut progrese in a intelege proprietatile satistice ale traficului masurat. Problemele care pot aparea sunt grupate in jurul a trei domenii- caracterizarea incarcarii, analiza performantei si controlul traficului.

Interesul original in rafalele auto-similare s-a extins sub aspectul general al modelarii incarcarii, care include comportamentul sursei si proprietatile structurale al sistemelor de retea. Performanta retelei (masurata in pierderea de pachete, intarzierea in coada, jitter la punctele de multiplexare ale retelei) este afectata de catre o multitudine de factori ca variabilitatea fluxurilor video-ului VBR, patternurile de sosire a conexiunilor, duratele conexiunilor, tipul de fisiere care trebuie transmise, actiunile de control din protocoale si comportamentul utilizatorilor. Cercetarea presupune identificare, cuantificarea si modelare a caracteristicilor. Modelarea fizica consta din combinarea trasaturilor relevante ale modelarii incarcarii, ale arhitecturii retelei-protocoale si tehnologie de transmisie- comportamentul utilizatorului si modelare analitica intr-o descriere consistenta a sistemelor de retea. Modelarea traficului multifractal are insemnatate in imbunatatirea modelelor. Incarcarea trebuie monitorizata si controlata.

Analiza performantei a sistemelor de cozi cu input auto-similar a dus la concluzia fundamentala a descresterii de tip polinomial a acestor cozi fata de cele cu input markovian care descresc exponential. Pentru alocarea resurselor acest lucru face ca alocarea bufferelor sa fie ineficienta in comparatie cu alocarea corespunzatoare a benzilor. Bufferele pot fi de doua tipuri: finite si infinite. Evaluarea performantei este pe de o parte orientata pe statistica de ordinul 1 (rata pierderii de pachete, intarzierea datorata cozii) si pe de alta pe statistica de ordinul 2 (variatii ale intarzierii si ale pierderilor de pachete) in special pentru trafic multimedia sau trafic sensibil la QoS. Aceste variatii de ordinul 2 influenteaza negativ QoS. Analiza performantei este de obicei efectuata in conditii de echilibru ceea ce nu este mereu adevarat. In anumite cazuri de incarcari ale retelei, convergenta se manifesta greu.

Controlul traficului pentru traficul auto-similar a fost exploatat din doua perspective: 1) ca extensie a analizei performantei in contextul alocarii de resurse si 2) din perspectiva controlului traficului cu scala multipla de timp. In ultimul caz, structura corelatiei la scari mari de timp este exploatata activ pentru a imbunatati performanta retelei. Controlul traficului sensibil la incaracare poate fi imbunatatit prin cercetari in materie de detectie si exploatare de predictibilitate, de programare a pachetelor, de control dinamic al acceptarii.

Bibliografie.

[1] Mandelbrot B. The Fractal Geometry of Nature, W. H. Freeman, New York, 1982.

[2] May, R. M. Simple Mathematical Models With Very Complicated Dynamics. Nature 261.459, 1976

[3] Feigenbaum, M.J., Quantitative Universality for a Class of Nonlinear Transformations. J.Stat.Phys. 19,25, 1978

[4] Feigenbaum, M.J., The Universal Metric Properties of Nonlinear Transformations, J.Stat.Phys. 21,69, 1979

[5] Feigenbaum, M.J., Universal Behaviour in Nonlinear Systems. Los Alamos Sci. 1,4, 1980.

[6] Strogatz, S. Nonlynear Dynamics and Chaos, with Applications to Physics, Biology, Chemistry and Engineering., Westview Press, 1994.

[7] www.mathworld.wolfram.com

[8] Glenn Elert, The Chaos Hypertextbook, 1995-2005

[9] Grassberger P. and Procaccia I. Measuring the Strangeness of Strange Attractors Physica D 9, 189 ,1983

[10] Halsey T., Jensen M. H., Kadanoff L. P., Procaccia I. and Shraiman B. I., Fractal Measures and Their Singularities: the Characterization of Strange Sets, Phys. Rev. A 33, 1141, 1986

[11] Leland W., Taqqu M., Willinger W. and Wilson D., On the Self-similar Nature of Ethernet Traffic, Proc. ACM SIGCOMM ’93, pp. 183-193, 1993.

[12] Crovella M and Bestavros A., Self-similarity in World Wide Web Traffic: Evidence and Possible Causes, Proceedings of the 1996 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, May 1996.

[13] Park K., Kim G. and Krovella M., On the relationship between file sizes, transport protocols and self-similar network traffic., Proc. IEEE International Conference on Network Protocols, pp. 171-180, 1996.

[14] Willinger W., Taqqu M., Sherman R. and Wilson D., Self-similarity through high variability: statistical analysis of Ethernet LAN traffic at source level, Proc. ACM SIGCOMM ’95, pp. 100-113, 1995.

[15] Mandelbrot B. and Van Ness J. , Fractional Brownian motions, fractional noises and applications. SIAM Rev. , 10:422-437, 1968.

[16] Likhanov N., Tsybakov B. and Georganas N. , Analysis of an ATM Buffer with self-similar (“fractal”) input traffic. Proc. IEEE INFOCOM ’95,pp. 985-992,1995.

[17] Taqqu M., Willinger W. and Sherman R., Proof of a fundamental result in self-similar traffic modeling, Comput. Comm. Rev, 26:5-23,1997.

[18] Taqqu M., Willinger W, Sherman R. and Wilson D., Self-similarity through high variability: statistical analysis of Ethernet LAN traffic at the source level. , Proc. ACM SIGCOMM ’95, pp. 100-113, 1995.

[19] Cox D. R. , Long-range dependence: a review. H.A.David and H.T. David, eds., Statistics: An Appraisal, pp.55-74, Iowa State University, Press, Ames, 1994.

[20] Beran J., Statistics for Long-Memory Processes. Monographs on Statistics and Applied Probability. Chapman and Hall, New York, 1994.

[21] Goncalves P. and Flandrin P., Scaling exponents estimation from time-scale energy distributions, IEEE Int. Conf. on Acoust., Speech and Signal Proc. ICASSP’92, San Francisco, 1992

[22] Veitch D., Abry P. and Bolot J., A wavelet based joint estimator of the parameters of long-range dependence., IEEE Trans. Inf. Theory, Special Issue on Multiscale Statistical Signal Analysis and its Applications, 45(3):878-897, April 1999.

[23] Massoulie L. and Simonian A., Large buffer asymptotics for the que with FBM input, J. Appl. Probab., 36(3), 1999.

1 Daca sunt sparte chiar si in bucati neregulate, in momentul iluminarii bucatelelor rezultate cu radiatia corespunzatoare se va obtine o holograma identica cu cea initiala doar de dimensiuni mai mici.