AUTO-SIMILARITATEA TRAFICULUI IN INTERNET

1. Definitia auto-similaritatii. Sisteme haotice si fractali.

Fractalii si proprietatea de auto-similaritate au fost teoretizate la sfarsitul anilor ’70 de catre Benoit B. Mandelbrot. Fractalii pot fi functii matematice dar exista ca realitati concrete in natura (legumele de genul conopida, broccoli, arterele si venele, raurile, norii, filmele holografice developate1). Fractalii se definesc in general prin intermediul auto-similaritatii insa aceasta poate fi intalnita si in cazul anumitor sisteme haotice. Astfel, se spune despre sistemele haotice auto-similare ca prezinta natura fractala. Exista totusi si obiecte auto-similare care nu sunt deloc fractale. Un exemplu in acest sens este linia dreapta din geometria euclidiana. Dreapta este autosimilara in timp si spatiu dar nu prezinta celelalte caracteristici ale fractalului.

1.1 Ce este auto-similaritatea? Auto-similaritatea este proprietatea prin care o anumita caracteristica a unui obiect (prin obiect putandu-se intelege functie matematica, forma geometrica complexa, imagine sau obiect concret din realitatea fizica) se conserva in raport cu rezolutia in timp sau spatiu.Ca forma geometrica complexa, un fractal prezinta mai multe proprietati tipice:

- structura fina la rezolutii mici luate arbitrar- iregularitate mare astfel incat nu poate fi descris usor folosind geometria

euclidiana- este auto-similar in mod determinist sau stochastic- este caracterizat prin dimensiuni specifice, nu prin geometrie euclidiana- are in general o definitie simpla si recursiva.

Exemplul clasic de fractal il reprezinta setul Cantor.

Figura 1. Setul Cantor unidimensional.

Se considera un interval inchis S0 =[0,1]. Pentru constructia intervalului S1 se imparte S0

in trei parti egale si se anuleaza cea de-a doua treime, adica valorile din intervalul ( ).

Rezulta ca setul S1 va fi format din reuniunea celor doua intervale ca in figura de mai sus. Cele doua intervale din setul S1 vor fi fiecare impartite in trei intervale egale din care se vor elimina valorile din intervalul din mijloc. Se va obtine astfel setul S2 format din reuniunea a patru intervale. Seturile superioare se obtin prin acelasi procedeu. Se numeste set Cantor setul limita si se constituie dintr-un numar infinit de bucatele separate de spatii libere de diferite dimensiuni.

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.

1

Setul Cantor are deci structura fina la rezolutii spatiale si temporale alese arbitrar si este auto-similar, continand copii ale sale indiferent de rezolutia temporala sau spatiala aleasa. Spre exemplu daca se ia doar partea stanga a setului S1 si se mareste de trei ori se obtine setul S0. in mod asemanator se poate obtine S0 din S2 prin scalarea setului S2 cu un factor 9.Acest tip de auto-similaritate stricta se regaseste doar in cazul fractalilor simpli. Pentru fractali complecsi, auto-similaritatea este doar aproximativa. Alte tipuri de fractali sunt Koch Coastline, San Marco Dragon, Koch snowflake, Sierpinski carpet.

Figura 2. Fractali: Koch Coastline, Koch Snowflake, Sierpinski Carpet.

Dintre sistemele haotice care au natura fractala se pot aminti seturile Mandelbrot si Julia si functia logistica.Functia logistica este un exemplu de sistem haotic unidimensional discret. Ea face parte din categoria functiilor iterate (iterated maps) si de asemenea din categoria functiilor unimodale (unimodal maps) si este descrisa de ecuatia :

(1)Unde n reprezinta numarul iteratiilor, x(n) valoarea functiei la iteratia n si x(n+1) valoarea functiei la iteratia n+1. r este un parametru al functiei.Valorile lui x variaza in intervalul [0,1] in timp ce parametrul r poate lua valori doar in intervalul [0,4]. Pentru valori ale lui r mai mari decat 4 valorile lui x vor depasi 1.Graficul functiei in functie de parametrul r poarta numele de diagrama de bifurcatie si este prezentata mai jos. Diagrama de bifurcatie se constituie ca o metoda de geometrica de vizualizare a zonelor periodice respectiv haotice ale unui sistem dinamic.

2

Figura 3. Diagrama de bifurcatie pentru functia logistica Analizand diagrama de bifurcatie, se poate observa ca zonele periodice alterneaza cu cele haotice. Figura de mai jos este un zoom al zonei diagramei de bifurcatie pentru care parametrul r variaza in intervalul [3.5, 4].

Figura 4. Diagrama de bifurcatie pentru functia logistica, zoom.

Cu ajutorul zoomului se poate observa o alta proprietate importanta a functiei logistice, cea de autosimilaritate. Datorita acestei proprietati, efectuand in orice zona haotica un zoom asupra functiei, se va descoperi aceeasi structura de arbore, practic aceeasi diagrama de bifurcatie dar in miniatura. Considerand rn acea valoare a lui r pentru care apare primul ciclu perioada 2n, Feigenbaum a urmarit evolutia acestor valori ale parametrului r.

3

Se demonstreaza ca rn converge geometric, distanta intre tranzitiile succesive micsorandu-se cu un factor de aproximativ 4.669.

(2)

reprezinta numarul universal al lui Feigenbaum.

1.2 Dimensiunile fractalilor auto-similariNotiunea de dimensiune depinde de geometria utilizata. In cazul geometriei euclidiene, dimensiunea se defineste ca numarul minim de coordonate necesare pentru descrierea fiecarui punct dintr-un set de puncte. Astfel, dreapta sau o curba foarte lina sunt unidimensionale deoarece fiecare punct situat pe ele este descris in mod unic de catre o singura coordonata. Planele si suprafetele netede sau cat mai netede sunt bidimensionale iar solidele sunt tridimensionale. Dimensiunea spatiului reprezinta numarul de puncte reale necesare pentru descrierea completa a fiecarui punct din spatiul respectiv.Dimensiunea poate fi stabilita si in functie de numarul de grade de libertate diponibile pentru miscari de translatie in spatiul respectiv. Insa geometria euclidiana nu se poate aplica in cazul fractalilor. Luand cazul curbei Koch, se va demonstra insuficienta rationamentului de mai sus. Se incepe constructia fractalului Koch coastline cu un segment de dreapta S0. Pentru a genera S1, se elimina treimea din mijloc a segmentului S0 si se inlocuieste cu doua din laturile unui triunghi echilateral. Seturile urmatoare se construiesc dupa acelasi principiu, astfel ca Sn se obtine inlocuind treimea din mijloc a fiecarui segment din setul Sn-1 cu doua din cele trei laturi ale triunghiului echilateral. Curba Koch este data de .In incercarea de a stabili dimensiunea curbei Koch se ajunge practic la un paradox. Fiind o curba se poate spune ca are dimensiune 1 dar K are lungime infinita.

(3)

Se deduce astfel ca dimensiunea K ar fi mai mare de 1. Daca se considera a fi 2 se constata ca este imposibil deoarece este o curba deschisa si nemarginita. Dimensiunea spatiului se stabileste a fi situata undeva intre 1 si 2.

Dimensiunea similaritatiiFractalii sunt alcatuiti deci din copii ale lor in miniatura. Dimensiunea acestor fractali se poate stabili prin inductie pornind de la fractalii rudimentari de genul patrate, linii.Se considera un fractal format din m copii si r factorul de micsorare a copiilor.Daca micsoram patratul cu un factor de 2 pe fiecare directie, rezulta ca patratul original va fi alcatuit din patru patrate mai mici. Daca se micsoreaza cu un factor de 3 pe fiecare directie, se vor obtine noua patrate componente. In general daca se foloseste un factor r, vor fi necesare r2 patrate componente. Daca in loc de patrat se considera un cub, vor fi necesare r3 componente.Exponentii 2 si 3 nu sunt intamplatori ci reflecta dimensiunea 2 a patratului si dimensiunea 3 a cubului.Se ajunge la urmatoarea definitie a dimensiunii similaritatii. Dimensiunea similaritatii d

4

este exponentul definit de relatia unde m este numarul de copii iar r factorul de micsorare. Echivalent,

(4)

Dimensiunea curbei Koch este de

Dimensiunea capacitatii (dimensiunea fractala)Dimensiunea capacitatii in sensul dimensiunii patrat se refera la aproximarea unui set cu o multime de patrate de dimensiune cat mai mica. Pentru o linie, numarul de patrate

necesare pentru aproximarea liniei cu acestea este de : , unde L este lungimea

liniei. Pentru o forma bidimensionala, , unde A este aria formei.

Se poate deduce ca .

Astfel dimensiunea capacitatii d este data de

. (5)

Aproximarea prin patrate are dezavantajul ca pentru dimensiuni intre 0 si 1 ea va da de fapt dimensiune 1.Pentru rezolvarea acestei probleme s-a introdus dimensiunea Hausdorff. Diferenta esentiala este ca aceasta metoda foloseste pentru acoperire inele formate din seturi de dimensiuni variabile.

Dimensiunea corelatieiMetoda a fost propusa de catre Grassberger si Procaccia si s-a dovedit a fi mai eficienta decat dimensiunea capacitatii. Este o metoda statistica de investigare.Se fixeaza un punct x si se ia un cerc de raza variabila dar mica si centrat in x. este numarul de puncte din cerc. Pe masura ce se mareste , numarul de puncte din cerc creste exponential dupa legea  Pentru evaluarea corecta a dimensiunii fractalului, se face o estimare a lui luand in considerare mai multi x. Rezultatul obtinut, va fi unde d este dimensiunea corelatiei.

(6)

Dimensiunea corelatiei tine cont de densitatea de puncte din diversele zone ale fractalului si deci difera de dimensiunea capacitatii care acorda aceeasi cuanta pentru orice zona indiferent de numarul de puncte din fractal. In general desi sunt foarte apropiate ca valoare.

1.3 MultifractaliiFractalii rudimentari de genul setului Cantor pot fi caracterizati complet prin dimensiunea lor. Pentru fractalii complicati, caracterizarea lor prin intermediul dimensiunii devine

5

insuficienta mai ales daca ei nu sunt determinist auto-similari. In acest caz avem nevoie de o functie de distributie (histograma) care sa scoata in evidenta cum variaza dimensiunea in diverse portiuni ale fractalului. Asemenea seturi poarta denumirea de mulifractali.

2. Traficul in internet2.1 Introducere.Traficul in internet este eterogen si in continua crestere. Asistam la o crestere a numarului de utilizatori, de provideri, de host-uri, precum si la o crestere a vitezelor conexiunilor. Serverele sunt si ele din ce in ce mai performante.Pentru analiza si modelarea traficului in internet s-a pornit de la traficul in telefonie. Pentru modelarea traficului telefonic se folosesc modele Markov (spre exemplu Poisson), acestea fiind in foarte buna concordanta cu realitatea si deci pe baza lor se pot face analize de acuratete si se pot elabora strategii de control pentru imbunatatirea calitatii serviciilor. In cazul validitatii analizei markoviene, in functie de diversi parametri de performanta (spre exemplu timpul de asteptare in sisteme de tip coada) se obtin zone distincte de echilibru (zone de comportament tipic). De asemenea, daca se folosesc surse Markov pentru modelare, traficul rezultat are o structura simpla din punct de vedere al corelatiei. In cazul aparitiei de evenimente negative (ca de exemplu concentrari de pachete), daca se face o rescalare adecvata in timp a acestor procese (dimensionarea corecta a bufferelor si alocarea benzii necesare in functie de caracteristicile traficului), procesele rezultate vor fi decorelate si se vor comporta ca o secventa de variabile aleatoare in model i.i.d (independente statistic si identic distribuite).

Exista doua variante pentru analiza si modelarea traficului in internet. In prima varianta se considera pentru analiza un anumit proces X(t) la momentul de timp t. Acest proces poate fi numarul de pachete transmise pe o anumita conexiune la momentul de timp t. Mai avantajoasa si mai des utilizata este varianta a doua in care se analizeaza procesul Y(t), Y(t) fiind volumul total de trafic pana la momentul de timp t.Se poate defini :X(t)=Y(t)-Y(t-1). (7)

Unde Y(t-1) este volumul de trafic la momentul de timp t-1 iar X(t) reprezinta intensitatea traficului in intervalul de timp t. Se pune problema stabilirii naturii auto-similare a traficului in internet atat in varianta proces instantaneu (varianta 1) cat si in varianta proces cumulativ (varianta 2). In cazul traficului in internet nu se poate discuta despre o auto-similaritate in sens determinist ci doar din punct de vedere stochastic.

2.2 Auto-similaritatea stochastica si traficul in internetAuto-similaritatea stochastica admite absenta determinismului din cauza masuratorilor asupra traficului dar este o proprietate care poate fi ilustrata vizual. Spre deosebire de fractalii deterministi, fractalii reprezentati de traficul in internet nu prezinta o asemanare a partilor lor cu intregul in cele mai fine detalii. Se considera pentru stabilirea gradului de

6

asemanare alura dependentei traficului de timp. Daca aceasta se pastraza indiferent de rezolutia in timp, cu magnitudinea valorilor corespunzator scalata, se deduce ca traficul este auto-similar in mod stochastic.

Figura 5. Trafic auto-similar.

In cazul traficului in internet nu se poate vorbi despre auto-similaritate in sens determinist deoarece foarte multe din evenimentele care au loc pe retea sunt de natura aleatoare si toate aceste evenimente influenteaza comportamentul traficului. Daca se considera seriile de trafic ca esantioane de realizari particulare ale unor procese aleatoare si se accepta un grad aproximativ de asemanare (auto-similaritate) prin evaluarea anumitor statistici a esantioanelor rescalate in timp, atunci se poate obtine o auto-similaritate in sens determinist a proceselor si o auto-similaritate aproximativa a realizarilor lor particulare. Statisticile de ordinul 2 sunt proprietati statistice care releva caracterul de rafale al traficului iar functia de autocorelatie este importanta in stabilirea etalonului in raport cu care se considera auto-similaritatea. Functia de autocorelatie isi pastreaza forma pe parcursul seriilor de timp rescalate. Existenta unei corelatii la distanta se numeste dependenta de raza lunga (long-range dependence).

2.3 Definirea notiunilor matematice. Procese auto-similare si dependenta de raza lunga2.3.1 Auto-similaritatea de ordinul 2 si stationaritatea

7

Se considera un proces stochastic de ordinul 2 in timp discret sau o serie de timp X(t), , unde X(t) are ca semnificatie volumul de trafic –pachete masurate, bytes sai biti-

la momentul de timp t. Se noteaza traficul cumulativ cu Y(t), X(t) fiind procesul ce reprezinta incrementul. X(t)=Y(t)-Y(t-1).Pentru a efectua modelari de trafic, se doreste ca X(t) sa fie stationar in sensul ca comportamentul sau structura sa sa fie invariabile in raport cu shifturile in timp. Fara un grad de stationaritate, totul devine posibil astfel incat modelul isi pierde utilitatea pentru descrierea unui fenomen care nu poate fi urmarit in timp. X(t) este strict stationar daca sirurile (X(t1), X(t2),…X(tn)) si (X(t1+k), X(t2+k), …..X(tn+k)) poseda aceeasi distributie oricare ar fi si . In contextul procesului shiftat cu k sau al unei serii de timp Xk, X si Xk sunt echivalente in sensul unor distributii de dimensiune finita . Impunerea unei stationaritati in sesns strict este mult prea restrictiva, astfel incat ceea ce intereseaza este o forma mai slaba de stationaritate- stationaritate de ordinul 2 (stationaritate slaba/covarianta/stationaritate in sens larg)- care cere ca functia de autocovariatie sa fie invarianta la translatie. Functia de autocovariatie se defineste ca: (8)iar conditia de invarianta la translatie se defineste ca pentru toti

. Momentul de ordinul 1 si doi exista si sunt finite.Pentru toti :-media: (9)-dispersia: . (10)Se presupune ca . Data fiind proprietatea de stationaritate, astfel incat se noteaza auto-covarianta cu Pentru a defini invarianta in functie de scala, se defineste mai intai procesul agregat X(m) al lui X la nivelul de agregare m.

. (11)

Formula de mai sus arata ca X(t) este impartit in blocuri nesuprapuse de marime m (lungime), iar valorile lor sunt mediate si folosit pe post de indice al acestor blocuri. Se foloseste pentru definirea auto-covariantei functiei X(m). Daca se considera auto-stationaritatea de ordinul 2 se deduc urmatoarele definitii pentru auto-similaritatea de ordinul 2.

Definitia auto-similaritatii de ordinul 2. X(t) prezinta o auto-similaritate de ordinul 2

exacta cu parametrul lui Hurst H ( ) daca

pentru toti . (12)

X(t) prezinta auto-similaritate de ordinul 2 asimptotica daca

(13)

Auto-similaritatea in sens strict implica pentru toti (14)

8

Prin urmare, suto-similaritatea de ordinul 2 implica ca structura corelatiei trebuie sa aiba exact forma relatiei (12) sau in mod asimptotic forma relatiei (13) care se respecta in

cazul agregarii in timp. Forma lui nu este

accidentala si implica alt tip de structura- dependenta de raza-lunga. Parametrul Hurst este o varianta a dimensiunii fractale in cazul in care se analizeaza seriile temporale.

2.3.2 Auto-similaritatea distributionalaSe considera procesul cumulativ Y(t), indiferent daca este continuu in timp sau discret in timp. Pentru cazul in care este in timp continuu se defineste auto-similaritatea pentru procese in timp continuu in sensul distributiilor finite dimensional H-ss astfel: Y(t) este auto-similar in raport cu parametrul Hurst (parametrul auto-similaritatii) H (0<H<1) daca pentru toti a>0 si ,

(15)Concluzia care se desprinde este ca Y(t) si versiunea sa scalata in timp Y(at)- dupa normalizarea cu - trebuie sa aiba aceeasi distributie. Pentru , are loc o dilatare in timp in timp si un factor de contractie se aplica pentru ca Y(at) sa poata fi comparabil cu Y(t). in cazul in care are loc o contractie in timp si atunci se aplica un factor de dilatare. a este variabil in timp ce H ramane constant. Dezavantajul major este acela ca Y(t) nu poate fi stationar din cauza normalizarii cu factorul . Pentru eliminarea acestei probleme se fac analize doar pe incrementul X(t)=Y(t)-Y(t-1). In cazul in care Y(t) este H-ss si are incrementi stationari, se spune ca Y(t) este H-sssi.Se presupune ca Y(t) are dispersie finita. Se poate verifica ca E[Y(t)]=0 si

.

(16)

Acestea se obtin din faptul ca Din aceasta relatie se obtine . Aceasta poate fi

folosita pentru deducerea functiei de auto-covariatie.

X(m) poate fi vazut ca si o medie experimentala, un estimator de medie.

(17)

Prin urmare, daca Y(t) este un proces H-sssi, atunci incrementul sau X(t) satisface relatia :

(18)

Relatia de mai sus arata cum este legat X(m) de X prin intermediul lui H in sensul unor distributii finite dimensional. X si m1-HX(m) trebuie sa aiba aceeasi structura de ordinul doi in mod exact sau asimptotic.

9

Daca procesul in timp discret satisface ecuatia pentru orice sau doar la limita , X(t) este exact auto-similar sau asimptotic auto-similar. In cazul gaussian aceasta definitie coincide cu auto-similaritatea de ordinul doi. Dispersia estimatorului de medie al unei variabile aleatoare Z satisface relatia

unde m este marimea esantionului.

Se deduce ca (19)Daca X(m) este vazut ca estimator de medie iar esantioanele sunt extrase independent,

var(X(m)) se reduce la daca Daca si atunci

cu si astfel incat se va forma o dependenta in cadrul

careia var(X(m)) converge catre 0 mai incet decat m-1.

2.3.3 Dependenta de raza lungaSe defineste functia de auto-corelatie

(20)

Pentru 0<H<1, cand .

Pentru cazul in care , r(k) se comporta asimptotic de forma pentru ,

unde c>0 este o constanta iar .

(21)

Functia de autocorelatie descreste incet ceea ce reprezinta motivul esential pentru care ea nu este sumabila. Cand r(k) descreste hiperbolic, astfel incat sa nu fie sumabila, procesul stationar X(t) prezinta dependenta de raza lunga. X(t) prezinta dependenta de raza scurta daca functia de autocorelatie este sumabila. O definitie echivalenta se poate da si in domeniul frecventa. Densitatea spectrala

trebuie sa satisfaca relatia:

. (22)Unde c>0 este o constanta si . Deci diverge in jurul originii ceea ce inseamna o contributie crescuta din partea componentelor de frecventa joasa.

Daca , atunci r(k)=0 iar X(t) prezinta dependenta de raza scurta deoarece este

complet necorelat. In cazul in care , atunci , conditie rar intalnita

de altfel. Daca H=1, r(k)=1 pentru toti si aceasta situatie se exclude. Valorile lui H mai mari decat 1 sunt interzise datorita conditiei de stationaritate a lui X(t).

10

Exista procese auto-similare care nu prezinta dependenta de raza lunga si procese care desi prezinta dependenta de raza lunga nu sunt auto-similare. De exemplu miscarea

browniana este de tip fata de zgomotul alb gaussian ca increment al acesteia dar

zgomotul alb gaussian nu prezinta dependenta de raza lunga. In cazul auto-similaritatii de

ordinul 2 asimptotice, punand restrictia , auto-similaritatea implica dependenta

de raza lunga si invers.

2.3.4 Distributia de tip coada lungaExista o stransa relatie intre distributiile cu coada lunga si dependenta de raza lunga. O variabila aleatoare Z este distribuita dupa o lege cu coada lunga daca

cand (23)Unde reprezinta indexul cozii sau parametrul de forma iar c este o constanta. Distributiile de tip coada scurta au cozi care descresc exponential spre deosebire de cele de tip coada lunga care descresc exponential. O caracteristica a distributiilor de tip coada lunga este ca ele au varianta finita pentru

. In domeniul retelisticii de interes este doar domeniul .Una din distributiile cu coada lunga des folosite este distributia Pareto caracterizata de functia de repartitie :

cu (24)

Unde reprezinta parametrul de forma iar b este parametrul de localizare.

Media este . Exista distributii, ca de exemplu Weibull si log normal care au cozi ce

descresc subexponential dar care poseda varianta finita. Principala caracteristica a unei variabile aleatoare care este distribuita dupa o lege de tip coada lunga este ca prezinta variabilitate extrema. O distributie cu coada lunga genereaza multe valori de probabilitati neneglijabile. Efectuand esantionari dintr-o astfel de distributie, se obtin multe valori mici si cateva valori foarte mari. Coada lunga afecteaza esantionarea prin incetinirea convergentei mediei esantionului catre media populatiei prin marirea mediei pe masura ce se apropie de 1. De exemplu, in cazul unei legi de tip Pareto acest lucru poate rezulta intr-o subestimare astfel inact trebuie luata in considerare eroare absoluta in estimarea mediei pentru a evita deteriorarea estimarii rezultatelor.

2.3.5 Distributiile de tip coada lunga si predictibilitateaAnumite variabile ale retelei- de exemplu marimea fisierelor si duratele conexiunilor- prezinta datorita traficului de retea dependenta de raza lunga si auto-similaritate. Spre exemplificare se considera o variabila aleatoare Z distribuita dupa o lege cu coada lunga. Aceasta variabila aleatoare Z se considera ca descrie durata medie de viata a unei conexiuni in retea (exemplu conexiune TCP, fluxuri IP). Duratele conexiunilor sunt evenimente masurabile fizic in sensul ca se poate observa de exemplu ca o conexiune a fost activa timp de secunde. Pentru simplificarea discutiei, se considera ca timpul este discret, . Se considera , o functie indicator astfel incat A(t)=1

11

daca . Ceea ce intereseaza este probabilitatea ca cconexiunea sa persiste in timp daca a fost activa timp de secunde. Se estimeaza astfel probabilitatea conditionata:

(25) poate fi exprimata ca :

(26)

Daca se calculeaza in cazul unor distributii cu coada scurta, adica pentru distributii ale caror cozi descresc exponential dupa legea unde c1,c2>0 sunt constante. Al doilea termen al ecuatiei (26) se calculeaza astfel :

. (27)

Pentru valori ale lui mari se obtine . Deci, in cazul distributiilor cu coada scurta predictia nu este influentata de cresterea lungimii perioadei de observatie.In cazul distributiilor cu coada lunga,

. (28)

pe masura ce .Astfel ca pe masura ce perioada de observabilitate a conexiunii creste, cu atat mai probabil este ca aceasta sa persiste. Se defineste persistenta activitatii in unitati de timp.

(29)In cazul unei distributii cu coada lunga, are un comportament asimptotic dupa legea

.

astfel incat predictibilitatea este sensibila exponential la intervalul .

Pentru orice , conditionand predictia de de o observatie pe termen lung al unei anumite activitati, eroarea de predictie poate fi redusa semnificativ.In cazul unei distributii empirice cu suport finit, faptul ca are un punct finit de anulare nu va influenta in mod semnificativ calculele computationale privind predictibilitatea atat timp cat coada este suficient de lunga.

2.3.6 Distributiile cu coada lunga si dependenta de raza lungaDistributiile cu coada lunga permit predictibilitatea si genereaza dependenta de raza lunga in traficul de retea. Mandelbrot a introdus notiunile de miscare browniana fractionara si zgomot gaussian fractionar, acesta din urma fiind incrementul miscarii browniene fractionare. Acestea procese auto-similare gausiene care au in general dependenta de raza lunga. Structura gaussiana le face extrem de folositoare ca modele de trafic agregat unde agregarea surselor independente de traffic- conform teoremei limita centrala- conduce la o structura gaussiana. In practica, fluxurile de trafic nu trebuie sa fie independente daca sunt

12

implicate in control de tip feedback si impart resurse commune in routere de tip bottleneck. Miscarea browniana fractionara (FBM): Y(t), poarta denumirea de miscare browniana fractionara cu parametrul H, 0<H<1, daca Y(t) este Gaussian si H-sssi.Zgomotul gaussian fractionar (FGN) : X(t), se numeste zgomot gaussian fractionar cu parametrul H daca X(t) este procesul increment al FBM cu pareametrul H. Conform definitiei H-sssi, FBM este miscare browniana iar FGN zgomot gaussian fractionar daca si numai daca H=0.5. Astfel, X(t), devine complet necorelat. In cazul proceselor gaussiene, auto-similaritatea distributionala si auto-similaritatea de ordinul doi sunt echivalente. Pentru a justifica de ce distributiile cu coada lunga sunt considerate cauza dependentei de raza lunga a traficului de retea, se prezinta in cele ce urmeaza procese de input cu timpi de activitate probabilistici, care se demonstreaza ca genereaza dependenta de raza lunga daca si numai daca fac parte dintr-o distributie cu coada lunga. Ca modele se folosesc modelul on/off definit de Willinger si o varianta a modelului definita de Likhanov.Modelul on/off considera N surse independente de trafic Xi(t), cu unde fiecare este un proces de reinoire a recompensei de tip 0/1 cu perioade on si off de tip i.i.d. Xi(t) ia valori 1 (on) sau 0 (off) pe parcursul unor intervale de timp alternante si care nu se suprapun si care poarta numele de perioade on/off. Astfel avem un tren de pachete, adica de perioade on.

Figura 6. Exemplu de model on/off.

Fie traficul agregat la momentul de timp t.

Se considera procesul cumulativ YN(Tt) definit ca:

13

(30)

unde T>0 este un factor de scala explicit incorporat.YN(Tt) masoara volumul total de trafic pana la momentul Tt. Se noteaza cu variabila aleatoare care descrie durata perioadelor on si variabila aleatoare asociata cu durata perioadelor off.

cu Unde si c>0 este o constanta. In ceea ce priveste , aceasta poate fi distribuita fie dupa o lege cu coada lunga fie dupa o lege cu coada scurta dar cu dispersie finita.YN(Tt) se comporta statistic ca

(31)

pentru T, N mari unde si BH(t) este FBM cu parametrul H iar C>0 este o

cantitate care depinde doar de distributiile si . YN(Tt) se comporta asimptotic deci ca o miscare browniana fractionara ce fluctueaza in

jurul atunci cand este normalizata in mod corespunzator. Acesta

prezinta dependenta de raza lunga ( ) daca , adica daca distributia lui

este de tip coada lunga. Daca niciuna din distributiile variabilelor sau este de tip coada lunga, atunci YN(Tt) prezinta dependenta de tip coada scurta. Chiar daca este distribuita dupa o lege de tip coada lunga, dar nu, YN(Tt) tot va prezenta o distributie de tip coada lunga. Acest caz nu este insa de interes deoarece in modelarea traficului conteaza perioadele on. Un alt model de sursa se obtine daca se considera fiecare sursa ca emitand un singur tren de pachete, in rest fiind inactiva. Astfel, o singura sursa on/off in modelul on/off poate fi construita astfel incat sa reprezinte comportamentul de output al unui host din retea, care poate deservi mai multe conexiuni TCP in timp ce in cazul trenului singular de pachete, sursa corespunde unei singure conexiuni de tip TCP ce transporta un stream de bytes ca de exemplu un fisier. Fiecarei surse ii asociem un interval de timp , , unde Xi(t)=1 daca si 0 in rest. Se presupune ca, sunt i.i.d si ti este determinat de catre un proces Poisson care indica cate conexiuni noi ajung la momentul t.

masoara cate conexiuni noi sunt active la momentul t. Alternativ,

X(t) poate fi vazut ca rata de trafic agregat emis la momentul t. Influenta distributiei cu coada lunga asupra dependentei de raza lunga poate fi observata studiand sistemul de cozi M/G/ .O coada de tip M/G/ se defineste ca fiind un proces server ocupat unde sosirile conexiunilor sunt distribuite Poisson si fiecare conexiune este deservita de catre un server- exista un numar infinit de servere- cu un timp general de deservire. Astfel, la fiecare moment de timp numaram cate servere sunt ocupate cu servirea cererilor. Daca

14

timpii de deservire distribuiti i.i.d sunt dati de , , atunci se poate observa ca procesul server ocupat din coada M/G/ corespunde ratei de trafic agregat X(t) din modelul Poisson cu o singura perioada on. Daca este distribuit cu coada lunga cu indexul cozii , atunci X(t), este

asimptotic auto-similar de ordinul doi cu parametrul .

Se poate arata ca FBM se produce in mod natural ca proces limita daca se dimensioneaza rata sosirilor Poisson si timpii de deservire. Sistemul M/G/ folosit pentru modelarea traficului de retea s-a dovedit a fi util in analiza comportamentului cozilor carora li se furnizeaza input cu dependenta de raza lunga.

Este important de mentionat ca distributiile de tip coada lunga nu genereaza neaparat dependenta de raza lunga in traficul agregat. Beran a aratat ca agregarea infinita a surselor cu dependenta de raza scurta- surse heterogene de tip on/off cu timpi on/off exponentiali- poate produce dependenta de raza lunga in cazul unei calibrari adecvate. Agregarile finite ale surselor cu dependenta de raza mica nu pot produce dependenta de raza lunga.

2.4 Domenii de cercetareCercetarile asupra traficului auto-similar se pot clasifica in patru domenii. In prima categorie intra modelarea traficului pe baza masuratorilor. Astfel esantioane de trafic sunt colectate din diverse retele existente fizic in internet si sunt analizate pentru a detecta, identifica si cuantifica caracteristicile traficului. Masuratorile au aratat invarianta rafalelor traficului la scalarea in timp (auto-similaritate) atat in retele de tip LAN cat si WAN, atat in retele bazate pe protocol IP cat si in retele de tip ATM, atat in retele formate din medii de transmisie din cupru cat si in retele formate din medii de transmisie de fibra optica. Analiza se face si din punct de vedere statistic. Validitatea unei tehnici de estimare este legata de procesul sau procesele care au generat datele. Astfel, un esantion de date a caror provenienta este necunoscuta nu poate fi atribuit unui anumit model de sursa sau proces si sunt necesare metode statistice de investigare pentru a stabili daca datele provin sau nu dintr-un anumit proces, model. Modelarea traficului bazata pe masuratori a dus la introducerea unei clase noi de modele, procesele auto-similare, modele folosite pentru traficul de retea.Din punct de vedere practic, foarte multe din tehnicile statistice folosite pentru stabilirea gradului de auto-similaritate sau dependenta de raza lunga (spre exemplu estimarea parametrului Hurst) sunt robuste. Datorita naturii lor, predominant euristice, aceste tehnici sunt usor de folosit si aplicat dar rezultatele obtinute sunt dificil de interpretat. Introducerea abordarilor bazate pe wavelet pentru analiza traficului reprezinta un pas important pentru dezvoltarea unor tehnici cu acuratete sporita care au sensibilitate crescuta la procedeul de scalare, putandu-se astfel discerne mai bine intre diferitele modele propuse. Deoarece wavelet-urile au proprietatea de localizare a unui semnal in spatiu si timp, ele au facut posibila detectarea, identificarea si descrierea comportamentului multifractal al scalarii (de exemplu un comportament al scalarii neuniform in timp care se manifesta in cazul traficului TCP masurat).

15

In a doua categorie se incadreaza modelarile fizice care incearca sa explice cauzele auto-similaritatii in cazul traficului in internet, bazandu-se pe mecanisme de retea si proprietati ale sistemelor distribuite stabilite empiric, care impreuna genereaza rafalele auto-similare ale traficului in internet in punctele de multiplexare ale nivelului de retea. Modelarea fizica are ca scop gasirea de modele pentru traficul de retea care se leaga de mecanismul fizic prin care traficul de retea este generat intr-o retea reala, care sa fie capabile sa explice fenomenele observate empiric (auto-similaritatea) si care eventual sa releve noi proprietati ale traficului de retea. Un prim tip de cauza care produce trafic auto-similar se datoreaza sosirii pachetelor de la o singura sursa, ca de exemplu VBR (variable rate video). MPEG-ul de exemplu, manifesta variabilitatea la rezolutii multiple in timp, variabilitate care se pune pe seama variatiei duratei dintre schimbarile succesive ale scenelor. Video-ul VBR poate fi aproximat prin modele de trafic de raza scurta.A doua cauza (cauza structurala) poate fi atribuita unei proprietati empirice a sistemelor distribuite si anume distributia cu coada lunga a marimii fisierelor sau obiectelor. O variabila aleatoare care asculta de o distributie cu coada lunga poata produce o gama larga de valori diferite de probabilitate neneglijabila. Daca host-urile schimba intre ele fisiere ale caror dimensiuni asculta de o distributie cu coada lunga, atunci traficul de retea rezultat este auto-similar in punctele de multiplexare ale nivelului de retea. Aceasta cauza este robusta in sensul ca este valabila pentru o gama larga de protocoale de transport cum ar fi TCP si UDP.Sistemul de fisiere UNIX are o distributie cu coada lunga. Acelasi tip de distributie o prezinta si obiectele web. Obiectele cu distributie cu coada lunga transportate de protocoale de tip TCP si UDP genereaza rafale auto-similare in punctele de multiplexare. Modelul on/off propus de catre Willinger et al. arata ca superpozitia unui numar mare de surse on/off cu perioade on si/sau off distribuite dupa o lege cu coada lunga duce la auto-similaritate in procesul agregat- un process de tip zgomot fractional Gaussian- a carui dependenta de raza lunga este determinata de distributia cu coada lunga a perioadelor on sau off. Agregarea spatiala este esentiala pentru inducerea dependentei de raza lunga, este responsabila pentru proprietatea gaussiana a traficului agregat prin aplicarea Teoremei limita centrala. Agregarea spatiala este relevanta pentru descrierea traficului de retea multiplexat. Una din slabiciunile acestui model este presupunerea surselor on/off ca fiind independente. Acest lucru s-a urmarit studiand influenta dependentei intre sursele multiple cuplate la routere bottleneck ce partajeaza resurse cand fluxurile sunt guvernate de protocoale ce implementeaza controlul congestiei prin feedback (ca de exemplu TCP la nivelul de transport). Cuplarea acestor surse nu influenteaza semnificativ dependenta de raza lunga. Modelul on/off este capabil sa genereze atat zgomot fractionar gaussian cat si un tip de auto-similaritate si dependenta de raza lunga numita auto-similaritate asimptotica de ordinul 2 (un singur proces cu perioade on/off distribuite dupa o lege cu coada lunga), acestea fiind doua din cele mai folosite modele auto-similare folosite pentru trafic in analiza performantei.Legatura intre masuratori si modelarea fizica releva faptul ca nivelul de aplicatie are proprietatea de a pastra distributia cu coada lunga a marimii fisierelor, proprietate pastrata de catre stiva de protocol si tradus prin perioade ocupate distribuite aproximativ dupa o lege cu coada lunga la nivelul de retea. Spatiile dintre pachete in cadrel aceleiasi sesiuni a fost catalogat ca avand propria variabilitate.

16

A treia categorie de cercetari se refera la modele matematice ale traficului de raza lunga in sensul teoriei cozilor. Prin investigarea comportamentului cozilor care primesc la input date cu dependenta de raza lunga se pot deduce caracteristici si limitari de performanta. Caracteristicile de performanta sunt cu totul diferite de cele prezentate in cazul unui input de tip Markov. Distribuita lungimii cozii in sisteme cu buffer infinit are o coada ce descreste mai incet decat exponential (subexponential) in contrast cu inputul cu dependenta de raza scurta a carui descrestere este exponentiala. In functie de modelul ales pentru coada, inputul cu dependenta de raza lunga poate da nastere la un comportament de descrestere al distributiilor lungimii cozii de tip Weibull sau polinomial. Scopul acestor analize a cozilor cu input non-markovian este de a vedea influenta asupra performantelor sistemului. Distributia lungimii cozii releva faptul ca bufferul ca strategie de alocare a resurselor, devine ineficient cand traficul de intrare este auto-similar, in sensul ca este afectata inegal intarzierea la nivelul cozii in paralel cu un castig in reducerea ratei de pachete pierdute. Aceasta a dus la propunerea unor buffere de capacitate mica si la marirea benzii ca strategii de alocare a resurselor. Daca capacitatea bufferului este mica, atunci probabilitatea de intarziere sau de aglomerare este mai mica. Cu cat capacitatea bufferului este mai mica, cu atat creste importanta corelatiilor de raza-mica in determinarea ocuparii bufferului. Aceste corelatii se dovedesc a fi importante in ceeea ce priveste imbunatatirea ratei de pierdere a pachetelor. Un dezavantaj major al sistemelor bazate pe cozi este ca acestea au natura asimptotica. Studiile de natura empirica cauta sa gaseasca o compatibilitate intre rezultatele asimptotice si sistemele cu buffere finite.Figura 6 ilustreaza dependenta dintre lungimea cozii si capacitatea bufferului cand un router bottleneck are ca input trafic auto-similar cu grade variate de dependenta de raza lunga dar cu aceeasi intensitate a traficului. aproape de 1 inseamna dependenta de raza-lunga puternica iar aproape de 2 se traduce prin dependenta de raza lunga slaba. Cand structura corelatiei de raza lunga e slaba, capacitatea bufferului de 60kB este suficienta pentru a face fata la variabilitatea inputului. Mai mult decat atat ocuparea medie a bufferului ramane su 5kB. Cand structura corelatiei de raza lunga e puternica, cresterea in capacitate a bufferului este insotita de o crestere corespunzatoare in gradul de ocupare a bufferului cu limita capacitatii bufferului pentru care lungimea medie a cozii se satureaza mult mai mare.

17

Figura 7. Lungimea medie a cozii in functie marimea bufferului in functie de gradul de dependenta de raza lunga.

In cazul analizelor de performanta se recomanda a se pune accent atat pe masuratorile performantelor de ordinul 1- ca de exemplu rata de pierdere a pachetelor- cat si pe masuratorile asupra performantelor de ordinul 2 –dispersia pierderii de pachete cunoscuta sub denumirea de jitter- deoarece acestea prezinta interes pentru multimedia. Doua procese care descriu pierderi pot avea statisticile de ordinul 1 identice dar unul din ele prezinta o dispersie mai mare decat celalalt in cazul perioadelor concentrate de pierdere de pachete- cum este cazul traficului auto-similar- si asta poate influenta negativ eficacitatea corectiei de erori la nivelul forwardarii pachetelor, corectie folosita in tehnicile de asigurare a calitatii serviciilor (QoS) pentru traficul in timp real. Un alt aspect care trebuie avut in vedere se refera la evaluarea performantelor in regim tranzitoriu, performante importante in practica cand convergenta catre comportamentul stabil pe termen lung este prea lenta pentru a fi de ajutor in proiectare. Cele mai multe rezultate obtinute in cazul sistemelor bazate pe cozi cu input de raza-lunga sunt pentru sisteme in bucla deschisa care ignora chestiunile legate de control prin feedback prezente in mediile actuale de retea (de exemplu TCP). Feedbackul poate influenta si determina forma traficului care ajunge in cozi astfel incat trebuie luat in considerare efectul sau.

A patra categorie de cercetari se refera la controlul traficului auto-similar. Se disting doua subcategorii : alocarea resurselor si dimensionarea. Problema estimarii cantitative a utilitatii unei unitati de resursa adtitionala cum ar fi largimea de banda sau capacitatea bufferului se bazeaza pe analiza cozilor cu input auto-similar. De asemenea sunt importante si sunt studiile asupra multiplexarii statistice ce utilizeaza largimea de banda efectiva. Aceste studii releva cat de eficient pot fi utilizate aceste resurse cand sunt partajate de mai multe fluxuri. Dimensiunea bufferelor trebuie sa fie mica si banda alocata mare. In cazul unui buffer de dimensiune mica corelatiile de raza mica afecteaza caracteristicile performantelor de ordinul 1.

18

Din punctul de vedere al controlului congestiei in sisteme cu multiscalare in timp se incearca sa exploateze structura de corelatie care exista intre diferitele scalari in timp in cazul traficului auto-similar. Dependenta de raza lunga ofera posibilitatea de utilizare a corelatiei in cazul unor scalari mari in timp pentru exploatarea predictibilitatii si astfel se poate usura controlul congestiei. Problema care apare in in proiectarea mecanismelor de control care permit folosirea structurii corelatiei in cazul unor scalari mari in timp implica doua neajunsuri: 1) structura corelatiei exista la scari de timp cu un ordin sau mai multe de marime mai mari decat bucla de feedback 2) informatia extrasa este imprecisa datorita naturii sale probabilistice.

Aceasta structura a corelatiei poate fi utilizata pentru a creste simtitor castigurile performantei si a cerintelor QoS precum si pentru controlul redundantelor. Importanta este si problema produsului intarziere-largime de banda in cazul retelelor de banda larga care face controlul traficului prin feedback ineficient in cazul RTT (round-trip times). Controlul congestiei ofera posibilitatea de compensare a incertitudinii care izvoraste din controlul feedbackului outdatat, compensare realizata de structura predictibilitatii prezenta la intervale de timp care depasesc RTT sau bucla de feedback (secunda in comparatie cu milisecunde). Un aspect important al controlului traficului il prezinta predictia duratei conexiunii. Rezultatele modelarilor fizice demonstreaza faptul ca aceste conexiuni sau fluxurile asculta de o distribuite cu coada lunga in ceea ce priveste durata lor in timp sau durata lor de viata si aceasta informatie poate fi exploatata pentru controlul traficului. Coada lunga implica faptul ca majoritatea conexiunilor au o durata mica de viata dar la volumul de trafic contribuie cateva fluxuri care au o durata mare de viata. Conform Legii lui Amdahl este importanta studierea influentei acestor fluxuri daca numarul lor este mic. O forma a Legii lui Amdahl afirma ca pentru a imbunatatii performanta unui sistem, functionarea sa in raport cu cele mai intalnite stari ale sale trebuie eficientizata. Castigul in termeni de performanta este limitat de functionarea sistemului. Idea folosirii duratei conexiunilor a fost introdusa prima oara in contextul echilibrarii incarcarii in sisteme distribuite in care procesele UNIX au fost demonstrate ca avand timpi de viata ce asculta de o distributie cu coada lunga. Prin contrast cu repartitiile exponentiale care nu permit predictia, distributiile cu coada lunga implica folosirea predictiei- o conexiune a carei durata masurata depaseste un anumit prag are o probabilitate mare de a persista in viitor. Aceasta informatie poate fi folosita pentru distribuirea incarcarii. Se incurajeaza distinctia intre fluxurile cu durata mare de viata si fluxurile cu durata mica astfel incat update-urile in tabela de rutare sa fie influentate mai mult de fluxurile cu durata mare. Aceasta mareste stabilitatea sistemului in defavoarea efectelor transiente declansate de fluxurile scurte. In general, informatia asupra duratei conexiunii poate fi oferita direct din informatia disponibila la nivelul de aplicatie-spre exemplu un server Web cand deserveste o cerere http, poate discerne marimea obiectului in cauza si aceasta informatie este facuta disponibila nivelelor inferioare de decizie pentru stabilirea tipului de control folosit : in bucla deschisa (pentru fluxuri cu durata mica de viata) sau in bucla inchisa (pentru fluxuri cu durata mare de viata).

19

3. Modelarea traficului. Folosirea transformarilor wavelet pentru analiza, estimarea si sinteza datelor de scalare.

3.1 IntroducereUna din problemele existente o reprezinta importanta fenomenului de scalare a traficului in domeniul retelisticii. In ceea ce priveste modelarea traficului, caracteristica de scalare trebuie inclusa in modele ca una din trasaturile fundamentale. Prin urmare, scalarea are implicatii imediate in alegerea claselor de modele de trafic si in consecinta-prin alegerea unei anumite clase- va influenta estimarea parametrilor modelului. Estimarea este necesara pentru verificarea initiala a modelului, pentru proceduri de optimizare si pentru monitorizarea traficului. Modelarea traficului nu se face izolat ci in contextul unor criterii de performanta. In functie de metrica aleasa din punct de vedere al performantei si de modelul retelei, influenta scalarii traficului va varia. Spre exemplu, in cazul anumitor cozi cu buffer infinit, daca la intrarea acestora se afla date proventite de la surse de tip on/off caracetrizate de do dependenta de raza lunga, distributia stationara a cozii va avea medie infinita (rezultat necalsic). Pentru eliminarea acestui inconveniente se folosesc buffere finite deoarece un buffer finit nu poate contine infinit de multe date. Dependenta de raza lunga a streamului de intrare influenteaza puternic pierderile de overflow dar nu poate mari semnificativ intarzierile conditionate ale pachetelor nepierdute, intarzieri legate de lungimea bufferului. Importanta fenomenului de scalare in trafic este dependenta de context. Probleme vitale sunt detectia, identificarea si masurarea comportamentului de scalare. Acestea nu pot fi ignorate chiar daca obiectivul urmarit sunt anumite criterii de performanta care nu sunt in mod direct legate de scalare deoarece scalarea introduce proprietati statistice neclasice ce afecteaza estimarea tuturor parametrilor si nu doar a celor legati de scalare. Aceasta afecteaza capabilitatile de predictie a modelelor de performanta si deci utilitatea lor in practica. Se impune astfel o detectie de acuratete a scalarii. Prin detectia prezentei sau a absentei scalarii se decide daca datele trebuie analizate folosind statistica obisnuita, traditionala sau folosind tehnici speciale de statistica care iau in considerare prezenta scalarii. Este important de asemena sa se faca distinctia intre particularitatile datorate nestationaritatilor care cauzeaza aparitia scalarii si intre comportamentul tipic de scalare. Identificarea este necesara deoarece exista mai multe tipuri de scalare ce prezinta interpretari si implicatii diferite in alegerea modelului. Odata determinat un anumit tip de scalare, se cere determinarea cu precizie a parametrilor care il caracterizeaza. Acesti parametrii vor controla proprietatile statistice ale estimatilor tuturor celorlalte marimi cum ar fi parametrii necesari in modelarea traficului sau in metrica serviciilor de asigurare a calitatii. Pentru exemplificarea celor de mai sus, se considera un proces de ordinul 2 X(t), stationar, a carui medie se doreste a fi estimata dintr-un set de date de lungime n. Pentru aceasta se considera estimatorul de medie. Rezultatul classic afirma ca pentru n suficient de mare, media esantionului asculta de o distribuite normala. Media

estimatorului de medie este iar dispersia , unde este dispersia variabilei X. in

cazul in care X prezinta o dependenta cu raza lunga, media experimentala este asimptotic

20

normal distribuita catre media . Dispersia este data insa de unde

si sunt parametrii care desciu o dependenta de raza lunga. Aceasta expresie arata ca dispersia estimatorului de medie descreste cu marimea esantionului n cu o rata de descrestere mai mica decat cea clasica. Astfel, stabilirea unor intervale de incredere pe baza unor premise statistice clasice duce la erori serioase, neluandu-se in discutie dependenta de raza lunga.

3.2 Avantajele metodelor bazate pe waveletFolosirea metodelor de analiza wavelet pentru detectia, identificare a si masurarea scalarii este avantajoasa deoarece acestea poseda un grad de invarianta la scalare, spre deosebire de alte metode. Un avantaj cheie este acela ca tipuri destul de diferite de scalare pot fi analizate cu aceeasi tehnica si cu acelasi set de simulari. Estimatorii semiparametrici ai parametrilor de scalare care rezulta din aceast metoda au propietati excelente- medie neglijabila si dispersie mica- si in multe cazuri ofera rezultate mai bune prin comparatie cu solutiile parametrice. Avantajele computationale bazate pe folosirea transformatei wavelet discrete (DWT) sunt substantiale si permit analiza de date de dimensiune variabila nu in ultimul rand exista si avantaje legate de robustetea metodei. Un alt aspect important legat de studiile de modelare si performanta vizeaza generarea seriilor temporale folosite pentru utilizarea acestora in simulari. Asemenea simulari pot fi mari consumatoare de timp pentru procese cu memorie semnificativa unde istoria exercita o influenta puternica asupra prezentului, anuland valabilitatea aproximarilor simple bazate pe trunchiere. Din acest punct de vedere, utilizarea wavelets pentru generarea datelor ofera avantaje clare.

3.3 Ce este wavelet?3.3.1 Transformarea wavelet in continuuDescompunerea wavelet in continuu consta dintr-o colectie de coeficienti:

(32)ce compara (prin intermediul produselor interne) semnalul X ce se doreste a fi analizat cu un set de functii analizoare:

(33)

Acest set de functii analizoare se construieste pornind de la un pattern de referinta care poarta denumirea de wavelet mama, prin actiunea unui operator de shiftare in timp

precum si un operator de dilatare (de schimbare de scala)

.

este ales astfel incat domeniul sau este limitat atat in timp cat si in frecventa. consista dintr-o mica unda definita pe un suport care e aproape limitat in timp si are majoritatea energieisale concentrate intr-o banda limitata de frecventa. Deoarece atat suportul in timp cat si banda de frecventa nu pot si ambele finite, se fixeaza un interval in care acestea sunt efectiv limitate. Operatorul de shiftare in timp face posibila selectarea momentului de timp in jurul caruia se doreste a fi analizat semnalul. Operatorul de

21

dilatare defineste scara de timp (sau in mod corespunzator gama de frecvente) in care sa se faca observarea. Marimea se numeste scalograma si se interpreteaza ca continutul de energie al lui X in jurul momentului de timp t intr-o gama data de frecvente controlata de a. In afara bunei localizari atat in timp cat si in frecventa, waveletul mama trebuie sa satisfaca conditia de admisibilitate a carei forma slaba este:

(34)Care arata ca este o functie oscilatoare trece banda, adica un wavelet.Waveleturile folosite in general in practica sunt Haar, Daubeechies si Meyer. Pe baza conditiei de admisibilitate, transformarea este inversabila:

(35)

Unde este o constanta ce depinde de . Aceasta formula de reconstructie in termenii unei integrale ponderate de waveleturi (care se comporta ca atomi elementari) localizati in jurul anumitor momente de timp si in jurul anumitor frecvente, constituind deci o cuanta de informatie in planul timp-frecventa. Deoarece transformarea wavelet reprezinta intr-un plan (spatiu 2D) informatia continuta intr-un semnal (spatiu 1D), este o transformare redundanta ceea ce inseamna ca coeficienti invecinati in planul timp au in comun o anumita cantitate de informatie. Teoria matematica analiza multi-rezolutie (MRA) dovedeste ca este posibil sa se esantioneze la limita planul timp, adica sa se pastreze din setul

doar un set discret de coeficienti si in paralel sa se retina intreaga informatie a lui X. Aceasta procedura defineste transformarea wavelet discreta (DWT).

3.3.2 Analiza multirezolutie si transformarea wavelet discretaAnaliza multirezolutie consta dintr-o colectie de subspatii incluse unul in celalalt care satisfac urmatoarele proprietati:

Setul de functii de scalare shiftate formeaza o baza Riesz, adica sunt liniar independente in V0 dar nu sunt neaparat ortogonale si nici nu sunt neaparat d lungime unitate.Analiza multirezolutie implica proiectarea succesiva a semnalului X pentru a fi studiat in fiecare din subspatiile Vj.

(36)Datorita proprietatii 2, approxj este o aproximatie mai slaba a lui X decat approxj-1. Pentru , toata informatia este extrasa din semnal.

22

Idea MRA-ului este deci de a studia un semnal prin examinarea aproximatiilor sale de diverse grade si rezolutii, prin anularea din ce in ce a mai multor frecvente inalte sau detalii din el.Informatia care este extrasa la trecerea intre aproximatii se numeste detaliu:

(37)

MRA arata ca semnalele detaliu pot fi obtinute direct din proiectii ale lui X pe o colectie de subspatii numite subspatii wavelet. Exceptand cazul in care X apartine lui V0,

selectarea spatiului V0 implica o pierdere inevitabila de informatie. Acest lucru este echivalent cu criteriul lui Nyquist pentru respectarea caruia trebuie facuta o filtare trece-jos. Prin varierea lui j se decide daca mai multa sau mai putina informatie se insereaza in detalii. Functia wavelet mama trebuie sa satisfaca relatia :

Dandu-se o functie de scalare si un wavelet mama , transformarea discreta wavelet (DWT) consta din colectia de coeficienti :

(38)Acesti coeficienti se definesc prin intermediul produselor interne ale lui X cu doua seturi de functii :

(39)

In studiul proceselor de scalare, urmatoarele doua caracteristici ale transformarii wavelet joaca un rol cheie :1. baza wavelet este construita din operatorul de dilatare , astfel incat familia analizatoare prezinta prezinta o invarianta la scalare.2. are un numar de de momente de anulare.

k=0,1,2,…N-1.Valoarea lui N poate fi aleasa prin selectarea waveletului mama corespunzator. Transformata Fourier a lui satisface , .Pentru calculul transformarii wavelet discrete se foloseste algoritmul piramidal rapid. Acest algoritm are o complexitate mai mica decat cele folosite pentru calculul FFT, o complexitate liniara. Acest algoritm este usor de implementat on-line si in timp real in retelele de mare viteza si astfel o estimare a parametrului de scalare bazata pe wavelet online este foarte usor de facut si eficienta.

3.4 Transformarea wavelet a proceselor de scalare Comportamentul de invarianta la scalare poate fi definit prin faptul ca toate scarile de timp au aceeasi importanta. Teoria wavelet a fost dezvoltata initial pentru procese de tip determinist cu energie finita, insa s-a demonstrat ca aceasta transformare poate fi aplicata si proceselor stochastice.Pentru procesele de ordinul doi care ne intereseaza aici, se stie ca transformarea wavelet este un camp aleator de ordinul 2 cu conditia ca functia de scalare si functia mama sa

23

satisfaca anumite conditii legate de structura de covariatie. Se presupune ca functiile de scalare si waveleturile descresc cel putin exponential in domeniul timp astfel incat statistica de ordinul doi a transformarii wavelet sa existe pentru procesele aleatoare discutate aici.Exponenti multipli, procese multifractale. Exista clase de procese de scalare care nu pot fi descrise de catre un singur exponent de scalare si care necesita o colectie sau chiar un numar infinit de exponenti.Se presupune un proces ale carui proprietati de scalare locale nu sunt descrise statistic de catre un parametru h. Daca procesul este auto-similar in mod determinist, acest parametru este constant. Pentru procesele multifractale, h este dependent de timp. Una din consecinte este aceea ca regularitatea locala nu mai este uniforma ci depinde de timp. In cazul miscarii browniene multifractale, h este o functie continua de t. Flandrin si Goncalves au aratat ca evolutia in timp a lui h poate fi descrisa prin analiza coeficientilor transformatei wavelet continue la scari mici : . (40)O alta clasa de procese de scalare cu natura multifractala este aceea pentru care h depinde nu numai de timp ci si de , unde reprezinta un element al spatiulu de probabilitati care caracterizeaza procesul. Deoarece variatia in timp a lui h devine prea complicat de urmarit, se prefera investigarea statistica a lui h. Acest lucru se poate face prin intermediul spectrului multifractal Hausdorff D(h) care consista din dimensiunea Hausdorff a setului de puncte pentru care . Acelasi spectru multifractal se obtine pentru toate realizarile lui astfel incat este un invariant folositor in descrierea proprietatilor de scalare ale procesului. Legatura intre multifractali sau waveleturi este aceea ca incrementii implicati in studiul regularitatii locale al unei traiectorii oarecare pot fi vazuti ca exemple simple de coeficienti wavelet. Astfel s- a propus inlocuirea acestora cu coeficienti wavelet in functiile de partitie : . 3.4.1 Estimarea scalarii3.4.1.1 GeneralitatiUn instrument de analiza il constituie diagrama logscale. Prin contrast fata de problematicul comportament statistic in domeniul timp, datorat dependentei de raza lunga a nestationaritatii sau fractalitatii procesului original X(t), in domeniul wavelet avem de a face doar cu procesele stationare, cu dependenta de raza scurta, pentru fiecare j. Datorita conditiei de admisibilitate a waveletului mama, aceste procese au toate media nula. Stationaritatea permite posibilitatea medierii in timp in cadrul fiecarui proces pentru reducerea variabilitatii. Dependenta de raza scurta face ca aceste statistici sa aiba dispersie mica.

(41)

Unde nj este numarul de coeficienti la octava j disponibili pentru analiza. Variabila aleatoare este un estimator neparametric, nedeplasat al dispersiei procesului .

Din cauza dependentei de raza curta, descreste cu si este eficienta asimptotic (de

dispersie minima). Variabila poate fi gandita ca un mod aproape optimal de a concentra grosul comportamentului de ordinal doi al lui X la octava j. Pentru a analiza

24

dependenta de ordinal doi a lui X(t), trebuie studiata dependenta lui in functie de j. exista o dependenta de tip putere intre dispersia proceselor la fiecare scala si j, fiind estimatele acestei functii. Astfel, exponentul de scalare poate fi extras din panta graficului in functie de j. Definitie: diagrama logscale (de ordinul 2) consista din dependenta in functie de j, impreuna cu intervalele de confidenta ale lui yj.

Figura 8. Exemplu de diagrama logscale.

Pot fi definite si generalizari de ordinul q ale diagramelor logscale, q>0, unde momentul de ordinul doi al detaliilor din ecuatia (41) este inlocuit prin momentul de ordinul q. Diagrama logscale poate fi folosita pentru procesele cu dependenta de raza lunga, pentru procesele de tip 1/f, pentru cele gaussiene si pentru cele auto-similare. Ca orice abordare de ordinul doi, este insuficienta pentru procesele ale caror momente de ordinul doi nu determina toate proprietatile de interes. Comportamentul de scalare nu este presupus ci se detecteaza cu ajutorul regiunilor de aliniere, daca acestea exista pe graficul logscale. Prin regiune de aliniere se intelege o gama de scari pentru care, in afara unei variatii statistice, valorile yj sunt distribuite dupa o linie dreapta. Estimarea parametrilor de scalare, daca este relevanta, poate fi efectuata eficient prin regresie liniara ponderata aplicata regiunilor. Identificarea tipului de scalare prin interpretarea valorii estimate in contextul gamei observate.

3.4.1.2 Detectia scalariiA priori, nu se cunoaste la ce scari, daca exista, poate exista o proprietate invarianta la scalare. Prin detectia scalarii in diagrama logscale se intelege identificarea regiunilor de aliniere si identificarea octavelor inferioare si superioare care marginesc regiunea, j1 si j2, care vor corespunde regimurilor de scalare. In esenta, aceasta este o problema nerezolvabila deoarece de cele mai multe ori scalarea se produce exponential sau are o definitie asimptotica fara vreo maniera clara de a defini unde incepe si unde se termina scalarea. Totusi, experimental se arata ca este posibil sa se obtina estimati buni. Trebuie facuta diferenta intre regiune de scalare- un concept teoretic care defineste o regiune in care se manifesta scalarea- si regiune de aliniere-un concept de estimare care corespunde datelor observate in diagrama logscale pentru un anumit set de date dat.

25

Prima idee esentiala este aceea ca conceptul de aliniere este relativ in raport cu intervalele de confidenta ale lui yj si nu in raport cu o aliniere stransa a datelor yj. O aranjare exagerata a estimatilor yj indica o corelatie puternica intre ei, o trasatura extrem de nedorita a acestui tip de depndente. Dupa cum s-a mentionat mai devreme, si deci yj sunt slab dependente. Folosirea regresiei ponderate incorporeaza intervalele de confidenta variabile in faza de estimare ; totusi selectia gamei de scari ce defineste regiunea de aliniere se face inainte si deci trebuie facuta decizia corecta. Pentru ca regresia sa fie bine definita se cer cel putin doua scari, pentru un test de concordanta statistica de tip Hi patrat, 3 scari, iar in practica se fac necesare cel putin 4 scari pentru a putea lua in considerare estimatii deoarece este mult mai usor ca 3 puncte sa se alinieze daca intervalele de confidenta nu sunt prea mici. O conditie buna pentru selectia unei game este ca linia de regresie sa taie pe cat posibil toate intervalele de confidenta din gama respectiva. Aceasta ajuta la evitarea erorilor de tipul : 1. nedetectarea unei regiuni de aliniere datorita variatiilor mari ale lui yj desi de fapt in cadrul intervalelor de confidenta alinierea este buna. 2. includerea eronata a mai multor scari la stanga regiunii de aliniere deoarece la prima vedere par a fi pe aceeasi dreapta insa daca se iau intervalle de confidenta mici se constata ca aceste puncte se abat foarte mult de la dreapta. Pentru a stabili care puncte pot face parte din aceeasi dreapta se poate aplica un test de concordanta Hi patrat. Problemele se ridica in special la capetele de interval.

3.4.1.3 Interpretarea scalariiPrin interpretarea scalarii se intelege identificarea tipului de fenomen de scalare- LRD, H-ss si asa mai departe- fenomen care genereaza tipul de aliniere in diagrama logscale. Sarcina este interpretarea plauzibila a parametrului estimat in contextul unei game de scari ce definesc regiunea de aliniere, insotita acolo unde este posibil de catre alte informatii stiute sau presupuse despre seriile de timp, cum ar fi stationaritatea. De fapt este o chestiune de alegerea modelului iar solutia poate sa nu fie unica. Daca se gaseste un estimat al exponentului de scalare in intervalul (0,1), iar gama de scari porneste de la o valoare initiala j1 pana la cea mai mare din setul de date disponibil, atunci scalarea corespunde unei dependente de raza lunga cu un exponent de scalare care este exponentul masurat. O valoare a lui mai mare ca 1 poate indica necesitatea unui model auto-similar sau asimptotic auto-similar ceea ce sugereaza ca datele sunt nestationare. Exponentul se va

reexprima cu ajutorul parametrului Hurst . Concluziile trebuie comparate cu o

ipoteza stabilita a priori. Daca scalarea este concentrata la cele mai mici scari (frecvente inalte), adica j1=1 si j2 fiind marginea superioara, atunci scalarea poate fi inteleasa ca indicand natura fractala a

unei anumite traiectorii a sistemului. Astfel se exprima mai bine sub forma , h

fiind parametrul de regularitate locala. Daca scalarea cu la toate sau aproape toate scarile din date, atunci autosimilaritatea exacta poate fi aleasa ca model, exponentul lui Hurst fiind exponentul relevant. Totusi se poate folosi si exponentul h cu explicatia ca comportamentul fractal la scari mici este constant in timp si se extinde pana la cele mai mari scari ale datelor.

26

In cadrul unei diagrame logscale este posibil sa existe mai mult de o regiune de aliniere. Fenomenul poarta numele de biscalare. Se pot imagina de exemplu caracteristici fractale care duc la o aliniere la scari mici cu un exponent si o dependenta de raza lunga ce duce la aliniere la scari mari cu un exponent de scalare separat. 3.4.1.4 Estimarea in cadrul diagramei logscale. Masurarea lui se reduce la determinarea pantei regiunii de aliniere in diagrama logscale. O maniera naturala de a obtine acest lucru in contextul unei estimari statistice este prin intermediul regresiei liniare. Ipoteza de definire a regresiei liniare este unde a este o constanta reala. Deoarece, in general, , aceasta conditie nu este satisfacuta exact. De aceea se introduc mici factori deterministi cu rol de corectie, g(j), si se redefineste yj ca fiind astfel incat prin definitie. Orice tip de regresie liniara aplicata asupra lui yj, este un estimator deplasat al lui deoarece deplasamentul nu cere decorelarea intre valorile lui yj sau sa se stie dispersiile si distributiile lor. O regresie ponderata in care ponderile sunt legate de este de preferat. Imbunatatirea este semnificativa deoarece se stie ca nu sunt egale. Pentru a exploata optimalitatea, factorii de corelatie si g(j) si dispersiile trebuie calculate, ceea ce este dificil. Ei pot fi aproximati in prezenta unor proprietati idealizatoare. Idealizarea presupune decorelarea totala. Estimatorul al lui este panta unei regresii liniare ponderate a lui yj in functie de j data de :

(42)

unde , si .

Dispersia acestui estimator este data de :

(43)

Exponentul de scalare este un parametru adimensional care caracterizeaza din punct de vedere calitativ fenomenul de scalare. Definirea lui nu este suficienta pentru caracterizarea completa a unui anumit fenomen de scalare si deci nu este suficient pentru caracterizarea efectelor pe care scalarea le poate avea asupra distributiilor diverselor statistici sau asupra performantelor diverselor aplicatii. Este necesara existenta unui al doilea parametru care sa descrie cantitativ aspectul scalarii, adica o magniudine sau un volum al parametrului de scalare.

Pentru exemplificare se considera deci o pereche de estimatori sau estimator reunit a

dependentei de raza lunga. este independent de forma waveletului mama depinzand doar de coeficientii regresiei liniare si de cantitatea de date nj la fiecare scara. Astfel se poate obtine o expresie pentru dispersia sa care sa fie independenta de baza de coeficienti wavelet.

27

Parametrul de magnitudine cf este proportional cu dar de fapt se foloseste pentru estimare o cantitate adimensionala care depinde de wavelet. Se defineste deci

estimatorul lui cf ca fiind unde este un estimator al .

Poate fi aratat ca are dispersie mica astfel incat proprietatile lui pot fi

caracterizate exclusiv de catre acelea ale lui .

este de forma unde p este un factor independent de wavelet folosit pentru

corectia deplasamentului.

Estimatorul este asimptotic nedeplasat si eficient si distribuit aproximativ lognormal.

3.4.1.5 Comparatie cu alti estimatoriIn evaluarea unui estimator trebuie luat in calcul aspecte legate atat statistice cat si computationale. Estimatorii bazati pe diagrama logscale sunt optimali din punct de vedere computational, complexitatea fiind de ordinal O(n). Alti estimatori cum ar fi, variograma au de asemenea avantaje computationale dar din punct de vedere statistic sunt deplasati si au dispersie mare. Din punct de vedere statistic, cei mai buni estimatori sunt cei parametrici, fiind nedeplasati si avand dispersie optima atat timp cat datele se potrivesc cu modelul ales. Trebuie insa sa se ajunga la un compromis intre performantele estimatorului si complexitatea computationala. De aceea se dezvolta variante ale acestor instrumente, variante care sa retina cat mai mult posibil din caracteristicile principale. Metodele de tip Whittle, Whittle agregat si Whittle local ofera cele mai bune performante din punct de vedere statistic prin comparative cu metodele de tipul valoare absoluta, dispersie absoluta, dispersia reziduurilor, metoda R/S, periodgrama. Asemenea estimatori, fiind parametrici, folosesc la maximum datele si deci sun calitativi superiori diagramei logscale (ca estimator) care este constransa sa foloseasca doar acele scari unde este prezenta scalarea. Insa costurile computationale ale algoritmului logscale sunt foarte ridicate. Un avantaj al logscale este acela ca poate fi folosit atat pentru forme de scalare stationare cat si nestationare. In multe situatii de interes practic, presupunerea ca datele sunt descrise in mod absolut de catre model –fie el auto-similar, fractal sau LRD- este mult prea restrictiva si nerealista. Acest lucru este valabil mai ales in cazul in care seriile temporale observate sunt rezultatul unei contaminari prin aditie a unui proces de scalare X(t) cu o contributie T(t), rezultand Y(t)=X(t)+T(t). Nu se va comenta cazul in care T(t) este un zgomot aleator ci doar cazul in care acesta este determinist si poate fi vazut ca o tendinta.Un model simplu pentru o tendinta consta din alegerea unui polinom de ordinul p pentru T(t). Daca aceasta tendinta nu se ia in considerare la analiza procesului de scalare, se pot scapa din vedere trasaturi importante si de interes cum ar fi stationaritatea incrementilor. Tendintele ce asculta de o lege de tip putere pot mima corelatii de tip dependenta de raza lunga atunci cand sunt adunate la procese stationare de raza scurta, ducand la concluzii

28

gresite. Se doreste deci, ca inaintea efectuarii unei analize sa se elimine eventualele tendinte sau cel putin sa se poata face o evaluare a acestora si sa se poata controla efectele lor asupra estimatilor finali. Din acest punct de vedere, teoria wavelet se dovedeste a fi inca o data robusta. Pentru a intelege de ce transformarea wavelet este eficiente in eleminarea trendurilor se pleaca de la conditia de admisibilitate satisfacuta de catre waveletul care afirma ca waveletul are media 0 ceea ce este echivalent cu a spune ca este ortogonal si deci orb la valorile de medie diferita de zero. Eliminarea trendului polinomial de ordinul p este garantata de un wavelet cu , unde N reprezinta numarul de momente de anulare. In cazul in care p este necunoscut, eliminarea trendului presupune analiza datelor cu waveleturi diferite astfel incat N sa varieze. Pana este atinsa valoarea efectiva N=p+1, analiza este guvernata de catre tendinta si da rezultate dependente de N. Odata ce

se obtin rezultate stabilizate care scot in evidenta caracteristicile datelor. Rezultate de acuratete se obtin in cazul trendurilor polinomiale dar procedura ramane eficienta si in cazul trendurilor nepolinomiale, inclusiv pentru trendurile caracterizate de lege de tip putere sau oscilatoare. Performanta estimatorilor de tip Whittle este sever afectata de catre trenduri.

3.5 ConcluziiS-a aratat ca waveleturile prezinta numeroase avantaje in ceea ce priveste fenomenul de scalare. Cu toate ce scalarea se refera la diverse modele (auto-similare, fractale, LRD), depinzand de gama de scari pe parcursul carora se observa acest fenomen si de exponentii de scalare, waveleturile ofera o abordare unitara care se plica la fel de bine pentru oricare din aceste modele. Waveleturile permit impartirea controlata a procesului analizat intr-un numar de sub-procese la diferite scari, fiecare din aceste procese fiind mai usor de analizat decat procesul mare. Acest lucru se aplica in special dependentei de raza lunga, un fenomen care interzice folosirea instrumentelor statistice clasice. Daca se face translatarea in domeniul wavelet, situatia devine mult mai simpla, cu dependente de raza scurta la fiecare scara, permitand astfel design-ul de estimatori simpli si eficienti bazati pe obisnuitii estimati empirici de dispersie. Multirezolutia permite waveleturilor sa fie un instrument natural pentru procesele de scalare. Directiile de cercetare in acest domeniu vizeaza detectia obiectiva si automata a gamei de scari pentru un anumit fenomen de scalare dat, distingerea unui exponent de scalare daca este sau nu constant in timp si posibilitatea de a genera cu acuratete intr-un mediu wavelet a unor clase mai flexibile de procese de scalare.

4. Investigarea cozilor. Formarea cozilor in cazul unui trafic brownian fractional

4.1 IntroducereCeea ce intereseaza sunt proprietatile procesului de ocupare a capacitatii buffer-ului atunci cand la intrarea sa se afla trafic brownian fractional, un proces Gaussian auto-similar. Acest model, care se numeste stocare browniana fractionara, este din punct de vedere logic cel mai simplu sistem de stocare cu dependenta de raza lunga al carui input prezinta

29

variatie strict auto-similara. Impactul parametrului H de auto-similaritate poate fi clar ilustrat in cazul acestui model. Toate formulele folosite pentru marimile de genul distributia ocuparii spatiului de stocare sunt doar rezultate obtinute la limita. Acest model poate fi justificat prin teoreme limita riguroase, dar trebuie precizat ca aceasta implica nu numai teorema limita centrala, argument al repartitiei normale, dar si o limitare a traficului intens. Dintr-un punct de vedere mai putin riguros, cel practic, se poate spune ca stocarea browniana fractionara da rezultate utilizabile atunci cand, la scari relevante pentru fenomenul de aglomerare in coada (queing), traficul consista din streamuri (fluxuri) independente astfel incat multe dintre ele sunt simultan active si ipoteza auto-similaritatii de ordinul doi ramane valabila. Auto-similaritatea de ordinul doi nu spune nimic despre comportamentul de queing de sine statatoare doar daca variatia traficului nu poate fi considerata gaussiana. Daca proprietatea de gaussianitate este satisfacuta suficient dar auto-similaritatea de ordinul doi se manifesta doar asimptotic, numite tehnici pot fi aplicate doar daca sunt usor modificate. In afara utosimilaritatii, metodele generale disponibile pentru stocarea browniana fractionara provin din literatura despre procese gaussiene.

4.2 Input, output, procese de stocareSe considera in timp continuu, un stocaj fluid nelimitat la intrarea caruia se afla trafic Brownian fractionar si care este golit la o rata de service constanta c.

4.2.1 Procesul de intrare, trafic Brownian fractionarInputul fluid in intervalul de timp (s,t] este dat de A(s,t) si are forma:

(44)Unde m si sunt parametrii nenegativi, m<c, iar procesul este miscare browniana fractionara normalizata (FBM), definita ca un process Gaussian centrat cu incrementi stationari, traiectorii continue si dispersie . Z este un process auto-similar:

(45)

pentru fiecare , unde semnifica ca procesele au aceleasi distributii dimensionale finite. H este parametrul de auto-similaritate si apartine intervalului (0, 1). Astfel, modelul traficului are trei parametrii – m, si H- iar modelul pentru stocare are additional inca un parametru –c. Parametrul m reprezinta rata medie de input iar este dispersia traficului intr-o unitate de timp. Este utila relatia :

(46)unde a este indexul dispersiei la unitatea de timp. Rolul folosirii lui ma in loc de este ca variatia lui m poate fi interpretata ca varierea doar a numarului de surse de trafic, fara a le schimba caracteristicile.

Parametrul H caracterizeaza dependentele in procesul de input. Pentru , toate

variabilele aleatoare A(s,t) cu s<t sunt strict pozitiv corelate. Pentru H=0.5, procesul de input este o miscare browniana si modelul de stocare este o aproximare clasica a difuziei

30

pentru un process de queing. Pentru , inputurile pe intervale disjuncte sunt

negativ corelate. pentru

pentru (47)Atunci .Acest model este o modalitate simpla de a include trasaturile de auto-similaritate ale traficului observate in analiza matematica a performantei.

4.2.2 Procesul de stocareProcesul de ocupare a spatiului de stocare ce are ca input trafic Brownian fractionar se defineste prin formula lui Reich:

(48)Daca , bufferul contine la momentul t cel putin diferenta. Totusi, nu contine mai mult decat valoarea maxima a acestor diferente pe parcursul lui s.Deoarece Z are incrementi stationari, V este un proces stationar, Z este inversabil in timp deci V0 este distribuit ca . Conform criteriului de continuitate

Kolmogorov cu probabilitatea 1. Deoarece s-a presupus ca m<c, rezulta

ca V0 este finit. V este nenegativ desi procesul de intrare are si incrementi negativi. Neuniformitatea traiectoriei browniene fractionare implica o proprietate paradoxala a lui V: spatiul de stocare este aproape intotdeauna negol. Se poate arata ca maximul lui Vt este pozitiv cu probabilitate 1 si datorita stationaritatii, pozitivitatea trebuie sa se pastreze pentru aproape orice valoare a timpului si pentru aproape fiecare realizare particulara a procesului. Setul de timpi t cu Vt=0, este nenumarabil, aproape fiecare punct fiind un punct de acumulare, astfel incat intre oricare doua perioade ocupate exista un numar infinit de perioade ocupate minuscule. Aceasta este o anomalie doar in cazul modelului in timp continuu. Aceasta este o trasatura naturala a procesului limita a traficului intens.

4.2.3 Procesul de outputEste natural sa se defineasca outputul in intervalul (s,t] ca :

pentru (49)Se obtine din (47) si (48):

astfel incat U este diferenta a doua procese crescatoare si deci are traiectorii care sunt diferentiabile aproape in fiecare punct. Astfel comportamentul la microscala al procesului de output este total diferit fata de cel al procesului de input. Aceasta caracteristica este inca o anomalie neplacuta a modelului.Deoarece spatiul de stocare este aproape intotdeauna negol, outputul se genereaza mereu cu rata completa c. Totusi, outputul pe parcursul unei durate unde spatiul de stocare este gol, este negativ iar rata medie este tot m.

31

Proprietatea de auto-similaritate permite obtinerea unor relatii importante, cum ar fi formulele de de calcul al ocuparii spatiului de stocare, al distributiei ocuparii in spatial de stocare, lungimea perioadei ocupate, formula dimensionarii bufferului.Daca parametrul Hurst este fix, si procesul de ocupare a spatiului de stocare brownian fractionar cu parametrii m, c, este .

unde (50)

Distributia ocuparii spatiului de scalare asculta de legea :

(51)

fiind lungimea perioadei ocupate ce contine originea timpului, distributia sa asculta de legea :

(52)Conditia reprezinta formula de dimensionare a bufferului. Unde reprezinta un numar mic si este probabilitatea de depasire a unui anumit nivel de stocare x.Comportamentul cozii P(V>x) a fost identificat cu mai multa acuratete. Massoulie si Simonian au aplicat teoria valorilor extreme ale proceselor gaussiene si au descoperit ca :

(53)

Unde si K este o constanta independenta de x.

Ocuparea cu trafic fractionar brownian ofera multe posibilitati de cercetare : cazul bufferului finit, formarea cozilor prioritare, dependenta intre perioadele ocupate.

5. Controlul traficului. Proiectarea pentru asigurarea calitatii serviciilor

5.1 IntroducereRolul proiectarii traficului este de a asigura ca reteaua are suficienta capacitate pentru a face fata cererilor cu o calitate adecvata a serviciilor. In acest sens trebuie inteleasa relatia intre cerere, capacitate si performanta, fiecare dintre acestea fiind evaluate conform unor unitati. Gradul in care acestea sunt satisfacute este incert in primul rand datorita naturii autosimilare a traficului de retea si in al doilea rand datorita dificultatii de a modela traficul de retea. Calitatea serviciilor intr-o retea de tip multiservicii depinde esential de doi factori: modelul serviciilor care identifica diferite clase de servicii si specifica cum sunt impartite resursele de retea si procedurile de proiectare a traficului folosite pentru a determina capacitatea acestor resurse. In timp ce modelul serviciilor de sine statator poate oferi nivele diferentiale de servicii ce asigura servicii mai bune anumitor utilizatori (in general celor care platesc mai mult) , oferirea acestei calitati pentru o populatie predefinita de utilizatori se bazeaza pe alocarea a priori a unei capacitati suficiente pentru a raspunde la cererile lor.

32

Este important in definirea modelului de serviciu de a identifica corect entitatea careia i se aplica controalele de trafic. Intr-o retea fara conexiune, unde entitatea este o datagrama, nu se poate spera la a se oferi mai mult decat angajamente de calitate a serviciilor de tip “cele mai bune eforturi” la nivele inalte. La celalalt capat, retelele ce au de a face in special cu agregate de trafic auto-similar, cum ar fi toate pachetele care se transmit dintr-o retea LAN in alta, nu pot oferi garantii de performanta decat daca forma traficului este ajustata in prealabil conform unei anvelope. Prin alocarea resurselor la nivelul flux, sau mai exact prin respingerea fluxurilor nou sosite atunci cand capacitatea disponibila este epuizata, aprovizionarea cu calitate a serviciilor este descompusa in doua parti: mecanisme de serviciu si protocoale de control care asigura ca calitatea serviciilor a fluxurilor acceptate este satisfacatoare. Proiectarea traficului este aplicata pentru dimensionarea elementelor de retea, astfel incat probabilitatea de rejectie ramane rezonabil de mica.

5.2 Natura traficului multiserviciuEste posibil sa se identifice un numar nedefinit de categorii de servicii de telecomunicatii, fiecare avand caracteristicile sale particulare de trafic si de cerinte de performanta. De multe ori, totusi, serviciile sunt adaptabile si nu este nevoie ca o retea sa ofere clase de servicii multiple, fiecare destinata unei aplicatii specifice. Se pot distinge trei tipuri de masuri de calitate a serviciilor: transparenta, accesibilitatea si throughput (cantitatea de date in unitatea de timp, transferata de la un nod al retelei la altul). Transparenta se refera la intengritatea semantica si in timp a datelor transferate. Pentru traficul in timp real, intarzierea ar trebui sa fie neglijabila, in timp ce un anumit grad de pierdere de date este tolerabil. Pentr transferul de date, integritatea semantica se cere in general dar intarzierea per pachet nu este importanta.Accesibilitatea se refera la probabilitatea de refuz a admiterii si de intarziere pentru setup in cazul unui blocaj. Probabilitatea de blocaj este un parametru cheie folosit in dimensionarea retelelor de telefonie. In internet nu exista control al admisiei si toate cererile noi sunt tratate prin reducerea cantitatii de banda alocata transferurilor in derulare. Accesibilitatea devine o chestiune, totusi, daca se considera necesar ca transferele sa fie realizate cu un throughtput minim acceptabil. Throughput-ul realizat pentru transferul documentelor cum ar fi fisiere sau pagini web, constituie calitatea principala a masurilor de servicii pentru retelele de date. Un throughput de 100kbps asigura transferul majoritatii paginilor web aproape instantaneu (in mai putin de o secunda). Pentru a intruni caracteristicile de transparenta, reteaua trebuie sa implementeze un model de serviciu adecvat proiectat. Cerintele de accesibilitate trebuie satisfacute prin stabilirea marimii retelei luand in considerare natura aleatoare a cererii utilizatorilor. Throughputul realizat este determinat atat de cantitatea de capacitate care oferita cat si de cum modelul serviciilor imparte aceasta capacitate intre fluxuri diferite. In acest context se face distinctia intre doua clase de trafic: fluxuri si elastic.

5.3 Trafic in fluxuriEntitatile de trafic in fluxuri sunt fluxuri ce au o durata si o rata intrinseci (rata este in general variabila) ale caror integritati in timp trebuie mai mult sau mai putin pastrate de

33

catre retea. Un astfel de trafic este generat de aplicatii ca serviciile de telefonie si de video interactiv, cum ar fi videoconferintele in cazul carora o intarziere semnificativa ar fi inacceptabila din punctul de vedere al degradarii. Un serviciu de retea ce ofera integritate in timp pentru semnalele video este de asemenea folositor pentru transferul secventelor video inregistrate in prealabil si desi intarzierea neglijabila in retea nu este in general o cerinta aici, consideram acest gen de aplicatii ca fiind un generator de de trafic in fluxuri.In acest fel, rata fluxurilor variaza si acest lucru este important pentru proiectarea controalelor de trafic. Semnalele de voce prezinta in general variatii mai complexe ale ratelor la scari de timp multiple. Important pentru proiectarea traficului este ca rata de bit a secventelor video lungi prezinta dependenta de raza lunga, o explicatie plauzibila pentru acest fenomen fiind ca durata scenelor in secventa are o distributie de probabilitate ce asculta de o lege cu coada lunga. Numarul de fluxuri pe o anumita legatura este un proces aleator ce variaza pe masura ce comunicatiile incep si se sfarsesc. Intensitatea sosirilor variza in general in functie de momentul zilei. Intr-o retea multiserviciu, este natural sa se identifice perioadele ocupate (ex: perioada de o ora cu cea mai mare cerere de trafic) si sa se modeleze sosirile in acea perioada ca procese stochastice stationare (eg. Procese Poisson). Cererea de trafic poate fi exprimata ca estimatul ratei combinate a tuturor fluxurilor active : produsul ratei sosirilor, durata medie si rata medie a unui flux. Durata convorbirilor telefonice se cunoaste ca avand distributie cu coada-lunga si acest model se poate potrivi si pentru alte fluxuri sugerand ca numarul de fluxuri in progres si rata lor combinata sunt procese auto-similare.

5.4 Traficul elasticAl doilea tip de trafic este traficul elastic. Se considera ca acest trafic este format din obiecte digitale sau documente care trebuie transferate dintr-un loc in altul. Aceste documente pot fi fisiere de date, texte, poze, sau secvente de poze transferate pentru stocare locala inaintea vizualizarii. Acest trafic este elastic in sensul ca rata fluxului poate varia datorita cauzelor externe (ex. banda disponibila) fara a fi in detrimentul calitatii serviciilor.Utilizatorii pot sau nu avea cerinte cu privire la calitatea serviciilor in cazul throughput. Ei au pentru sesiunile de oferire a informatiilor in timp real, unde este important ca documentele sa apara rapid pe ecranul utilizatorului si nu au pentru e-mailuri sau transfere de fisiere unde o mica intarziere este tolerabila. Caracteristicile esentiale ale traficului elastic sunt procesul de sosire a cererilor de transfer si distributia marimilor obiectelor. Observatiile asupra traficului web ofera indicatori folositori ai naturii acestor caracteristici. Intensitatea medie a sosirilor cererilor de transfer variaza depinzand de patternul activitatii userului respectiv. Ca si pentru traficul in streamuri, este posibil sa se identifice perioadele ocupate representative cand procesele de sosire pot fi considerate a fi stationare. Masuratorile pe site-uri web sugereaza posibilitatea modelarii sosirilor ca un proces Poisson. Un proces Poisson rezulta in mod natural in momentul in care membrii unei populatii foarte mari de utilizatori fac independent cereri relativ dispersate. Insa conform unor masuratori mai recente se pare ca modelul Poisson nu ar fi chiar adecvat. Statisticile cu privire la marimea obiectelor web scot in evidenta ca sunt extrem de variabile, si ca

34

prezinta distributie de probabilitate de tip coada-lunga. Majoritatea obiectelor sunt foarte mici: masuratorile asupra marimilor documentelor web raportate de catre Arlitt si Williamson scot in evidenta ca 70% sunt mai mici de 1kB si doar 5% depasesc 10kB. Prezenta acestor putine obiecte de dimensiuni mari are un impact important asupra volumului traficului global. Este posibil sa se defineasca o notiune a cererii de traffic pentru fluxuri elastice in analogie cu definitia data pentru traficul in fluxuri ca produsul dintre rata medie de sosire intr-o perioada ocupata reprezentativa si o marime medie a obiectului.

5.5 Agregari de traficAlta categorie de trafic se naste atunci cand fluxurile si tranzactiile individuale sunt grupate impreuna intr-un flux agregat de trafic. Acest fenomen survine frecvent de exemplu atunci cand fluxul intre doua retele LAN distantate unele fata de altele trebuie tratat ca o entitate de trafic de catre o retea WAN. Evolutiile propuse pentru modelarile serviciilor de internet cum ar fi serviciile diferentiate si shiftarea etichetelor multiprotocol (MPLS) se bazeaza puternic pe notiunea agregarilor de trafic. Prin agregare, cerintele de calitate a serviciilor sunt satisfacute intr-un proces in doua etape: reteaua garanteaza ca un agregat are acces la o banda data intre doua puncte stabilite; aceasta banda este impartita de catre fluxurile din agregat conform unor mecanisme. In mod tipic, providerul de retea are sarcina simpla de management al traficului de retea de a rezerva banda garantata in timp ce responsabilitatea pentru impartirea acestei intre streamuri si fluxuri elastice decurge catre client. Aceasta diviziune a responsabilitatilor usureaza problema scalabilitatii, in cazul careia capacitatea elementelor de retea de a mentine starea fluxurilor individuale nu poate tine pasul cu cresterea in trafic. Situatia ar fi clara daca garantia oferita de retea clientului ar fi pentru ar fi pentru o banda fixa, constanta pe parcursul unui interval de timp definit. In practica, deoarece traficul agregat este in general extrem de variabil si chiar auto-similar, o rata constanta nu este in general adecvata cerintelor utilizatorului. Existenta rafalelor poate fi explicata cu ajutorul descriptorului de trafic de tip leaky bucket, desi aceasta nu este cea mai buna solutie, in special pentru traficul auto-similar. In retele ATM si frame-relay se practica a se rezerva in avans capacitate considerabila (suma ratelor garantate poate fi de cateva ori mai mare decat capacitatea disponibila), contand pe faptul ca nu toti utlizatorii nu au toti nevoie de banda garantata in acelasi timp. Aceasta permite o descrestere proportionata in incarcarea benzii, dar nu mai exista garantii reale. Mai mult decat atat, in aceste retele, utilizatorilor li se permite in general sa emita trafic la o rata mai mare sau mai mica decat banda lor garantata. Acest trafic in exces, etichetat ca dispensabil in conditii de congestie, este folosit pe principiul celui mai bun efort folosind capacitatea disponibila momentan. Combinatia de overbooking si etichetare conduce la o oferta comerciala care este atractiva multor clienti. Conduce totusi la o imprecizie in natura serviciilor oferite si in ceea ce priveste incarcarea ceea ce s-ar putea dovedi inacceptabil pe masura ce piata retelelor multiserviciu ajunge la maturitate. Aceasta conduce la ignorarea avantajelor oferite de considerarea unui agregat ca o simpla entitate de trafic si de a considera fluxurile individuale si fluxurile elastice in scopul controlului acceptarii si al rutarii. Cu alte cuvinte, transparenta, throughput si

35

accesibilitatea sunt garantate pe baza unor fluxuri individuale nu pentru un agregat. Binenteles, este folositor si in cazul traficului agregat in retea si fluxuri cu asemenea caracteristici pot partaja buffere si legaturi fara a fi nevoite sa mentina informatii detaliate cu privire la stare.

5.6 Controlul in bucla deschisaSe considera controlul in bucla deschisa sau controlul traficului in paradigma preventiva, bazata pe notiunea de contract de trafic: utilizatorul cere o comunicare descrisa in termenii unui set de parametrii de trafic si reteaua executa controlul acceptarii, acceptand comunicarea numai daca cerintele de calitate a serviciilor pot fi satisfacute. Indiferent daca se practica politica de acces sau de imbunatatire a ratei de acces prin programare in nodurile retelei, este necesar a se evita degradarea performantei datorata fluxurilor care nu se conformeaza descriptorului de trafic aferent.

5.6.1 Multiplexarea performanteiEficienta controlului in bucla deschisa depinde de acuratetea cu care este posibil sa se prezica performanta in conditiile unor caracteristici date ale unor fluxuri cu rata variabila. Pentru a discuta optiunile de multiplexare, se face presupunerea simplificatoare ca fluxurile au rate definite neambiguu, fluxurile sunt asimilate ca fluide, legaturile cu tevi si bufferele cu rezervoare. Se presupune de asemenea ca procesele rata sunt stationare. Se disting doua forme de multiplexare statistica: multiplexare fara buffer si multiplexare cu buffer. In modelul fluid, multiplexarea statistica este posibila fara buffere daca rata combinata de intrare este mentinuta mai mica decat capacitatea legaturii. Pe masura ce tot traficul in

exces este pierdut, rata globala de pierderi devine unde este procesul

ratei de intrare iar c este capacitatea liniei. Este important de remarcat ca rata pierderilor depinde doar de distributia stationara a lui si nu de proprietatile sale care depind de timp, intre acestea aflandu-se si auto-similaritatea. Acestea sunt importante si influenteaza alte aspecte ale performantei cum ar fi durata supraincarcarilor dar aceasta durata poate fi neglijata atunci cand rata pierderilor este suficient de mica. Masura in care utilizarea unei legaturi este compatibila cu o anumita rata de pierderi poate fi crescut prin folosirea unui buffer care sa absoarba din excesul ratei de intrare. Rata de pierderi in cazul unei dimensiuni date a bufferului si a capacitatii legaturii depinde intr-o maniera complicata de natura traficului oferit. In particular, performantele de pierderi si intarziere sunt foarte greu de prezis cand procesul de intrare are dependenta de raza lunga. Modelele sunt in general capabile doar sa prezica comportamentul asimptotic al cozii pentru clase particulare de trafic cu dependenta de raza lunga.O alternativa la multiplexarea statistica este de a oferi garantii deterministe de performanta. Garantiile deterministe sunt posibile daca cantitatea de date A(t) generate de un flux intr-un interval de lungime t satisface o constrangere de tipul: . Daca legatura deserveste acest flux la o rata cel putin egala cu , atunci continutul maxim al bufferului de la ecest flux este . Pierderea poate fi deci complet evitata si intarzierea legata de oferirea unui buffer de marime si de implementarea unei discipline de programare care asigura rata de serviciu . Aceasta constrangere asupra ratei de intrare poate fi imbunatatita prin folosirea unui leaky bucket.

36

5.6.2 Descriptorul de trafic leaky bucketControlul in bucla-deschisa se bazeaza atat in retele de tip ATM cat si in modele de serviciu pentru internet se bazeaza pe descriptorul de tip galeata cu scurgeri pentru a descrie fluxurile de trafic. In pofida convergentei aparente, raman dubii serioase cu privire la eficacitatea acestei alegeri. Se considera galeata cu scurgeri ca fiind un rezervor de capacitate care se goleste la o rata si se umple datorita fluxului de intrare controlat. Traficul asculta de descriptorul leaky bucket daca satisface inegalitatea . Galeata cu scurgeri a fost aleasa in principal deoarece simplifica problema controlarii conformitatii inputului. Eficacitatea sa depinde aditional de capabilitatea de a alege valorile adecvate ale parametrilor pentru un flux dat si apoi de a putea garanta eficient calitatea serviciilor cu ajutorul controlului acceptarii. Galeata cu scurgeri poate fi privita fie ca un descriptor statistic care aproximeaza rata medie si rafalele unui flux dat (sau mai exact ofera limite superioare stricte) sau ca o definitie a unei anvelope in care trebuie sa incapa traficul ca forma. Grosolan vorbind, prima abordare este adecvata pentru traficul in fluxuri pentru care intarzierile excesive sunt inacceptabile in timp ce a doua se aplica traficului elastic si al agregatelor de trafic elastic. Traficul in fluxuri ar trbui sa treaca transparent fara a i se da o forma, alegand o rata destul de mare a galetii si parametrii adecvati pentru capacitate. Experientele cu video-ul arata ca este foarte dificil de a se gasi o solutie de mijloc intre o rata de scurgereapropiata de medie cu o capacitate excesiv de mare si o rata de scurgere apropiata de varf cu o capacitate moderata. In primul caz, desi rata medie globala este prezisa cu acuratete, nu este o caracteristica folositoare a traficului deoarece rata mediata pe cateva perioade ce dureaza cateva secunde poate diferi semnificativ. In ultimul caz, informatia ratei este insuficienta pentru a permite castiguri semnificative prin multiplexare statistica. Pentru fluxuri elastice, este prin definitie posibil sa se formeze o forma a traficului pentru a se conforma parametrilor unei galeti cu scurgeri. Daca traficul are dependenta de raza lunga, ca in cazul unor agregate de fluxuri, modelele de performanta indica ca comportamentul de formare a cozilor este sever. Pentru orice alegere a ratei de scurgere

mai mica dacat rata de varf, si o capacitate a galetii care nu este impractic de mare, majoritatea traficului va fi filtrat si admis in retea la rata . Valoarea adaugata a unei capacitati a galetii diferita de zero este deci extrem de limitata pentru un asemenea trafic. Se poate concluziona ca, pentru traficul in fluxuri si pentru traficul elastic, galeata cu scurgeri constituie un descriptor extrem de inadecvat a variabilitatii traficului.

5.6.3 Controlul acceptarii (admission control)Pentru a face controlul acceptarii bazat doar pe parametrii unei galeti cu scurgeri implica presupuneri nerealiste ale traficului in cele mai rele conditii si conduce la ineficienta datorita alocarii unor resurse considerabile. Pentru multiplexarea statistica, se presupune ca fluxurile emit independent rafale cu rate de varf maxime periodice separate de intervale de liniste minime compatibile cu parametrii galetii cu scurgeri. Marginile intarzierilor deterministe sunt retinute doar daca fluxurile emit rafalele cu rata de varf de valoare maxima simultan. Dupa cum s-a discutat mai sus, presupunerile legate de cel mai

37

rau caz, nu sunt legate de caracterisiticile reale ale traficului si duc la utilizarea extreme de ineficienta a resurselor de retea. O alternativa este de a se baza pe datele istorice pentru a prezice caracteristicile statistice ale tipurilor de flux cunoscute. Acest lucru este posibil pentru aplicatii de tipul telefonului, unde un estimat al ratei medii de activitate este suficient pentru a prezice performanta cand un set de conversatii impart aceeasi linie folosind multiplexarea fara buffer. Este mai putin evident in cazul traficului multiserviciu, unde nu exista in general metode de a identifica natura unei aplicatii dintr-un anumit flux.Cea mai promitatoare abordare a controlului acceptarii este folosirea masuratorilor pentru a estima capacitatea disponibila la momentul curent si de a admite un nou flux doar daca calitatea serviciilor ramane satisfacatoare presupunand ca fluxul ar genera trafic in cele mai rele conditii compatibil cu descriptorul sau de trafic. Aceasta abordare este fezabila in cazul multiplexarii fara buffer. Singurul descriptor necesar ar fi rata de varf cu masuratori effectuate in timp real pentru a estima rata ceruta de fluxurile existente. Un nivel suficient de mare al utilizarii este compatibil cu o probabilitate neglijabila a supraincarcarii, cu conditia ca rata de varf a fluxurilor individuale este o mica fractiune din rata legaturii. Ultima conditie asigura ca variatiile din rata de input combinata sunt de amplitudine relativ mica, limitand riscul erorilor de estimare sicerand doar o mica margine de securitate care sa fie suficienta in cazul celor mai nefavorabile coincidente posibile in activitatile fluxurilor. Pentru multiplexarea cu buffere, data fiind dependenta intarzierii si a performantei pierderilor de caracteristicile complexe ale fluxului de trafic, proiectarea unui control eficient al acceptarii ramane o problema deschisa. Este de preferat sa se evite acest tip de multiplexare si sa foloseascacontrolul reactiv pentru traficul elastic.

5.7 Controlul in bucla inchisa pentru trafic elasticControlul traficului in bucla inchisa, sau reactiv, este adecvat pentru fluxuri elastice, care isi pot ajusta rata conform nivelelor curente ale traficului. Acesta este principiul TCP in internet si al ABR in ATM. Amandoua protocoalele doresc a exploata la maxim banda disponibila in retea concomitent cu atingerea unor partajari egale intre fluxurile concurente. Se obisnuieste a considera impartirea benzii sub presupunerea ca numarul fluxurilor conxurente ramane fix (sau se modifica incremental, cand se considera studierea proprietatilor de convergenta). Obiectivul partajarii este unul al echitabilitatii: o singura legatura izolata impartita de n fluxuri ar trebui sa aloce 1/n din banda sa fiecarui flux. Acest obiectiv poate fi generalizat prin atribuirea unei ponderi pentru fiecare flux i iar

banda alocata fiecarui flux i sa fie proportionala cu poate avea

legatura cu diferite optiuni ale tarifului.Intr-o retea, generalizarea notiunii simple de echitabilitate este o echitabilitate de tipul min-max. Ratele alocate sunt pe cat posibil egale, supuse numai constrangerilor impuse de capacitatea legaturilor retelei si de limitarea ratei de varf proprie fluxului. Alocarea echitabila max-min a fluxului este unica astfel incat nici o rata a fluxului sa fie crescuta fara a fi necesar sa se scada cea a unui alt flux a carui alocare este deja mai mica sau egala cu .

38

Echitabilitatea max-min poate fi atinsa prin algoritmi centrali sau distribuiti, care calculeaza in mod explicit rata fiecarui flux. Totusi, majoritatea algoritmilor practici sacrifica obiectivul ideal in favoarea simplitatii implementarii. Cei mai simpli algoritmi de partajare a ratei se bazeaza pe fluxuri individuale ce reactioneaza la semnale binare de congestie. Partajarea echitabila a unei singure legaturi poate fi obtinuta permitand ratelor sa creasca liniar in absenta congestiei si sa descreasca exponential pe masura ce apare congestia. S-a subliniat de asemenea ca echitabilitatea max-min nu este neaparat un obiectiv desirabil al partajarii ratei si ca se doreste mai degraba sa se maximizeze utilitatea globala, unde utilitatea fiecarui flux este o functie nedescrescatoare de rata alocata lui. Algoritmii distribuiti de partajare a benzii si mecanismele asociate trebuie sa fie robuse la un comportament necooperativ al userului. O solutie promitatoare este de a efectua partajarea benzii prin implementarea fenomenului de formare a cozii echitabil si per flux. Alegerea adecvata a pachetelor care sa fie rejectate in cazul congestiei imbunatateste considerabil atat echitabilitatea cat si eficienta.

5.7.1 Traficul variabil aleatorEchitabilitatea nu este un substituent satisfacator al calitatii serviciilor deoarece utilizatorii nu au mijloace de a verifica ca primesc o parte echitabila. Throughput-ul perceput depinde atat de numarul de fluxuri aflate in desfasurare cat si de modul in care banda este partajata intre ele. Acest numar nu este fix dar variaza aleator pe masura ce incep noi transferuri si se termina cele curente.Un punct de start rezonabil pentru a evalua impactul traficului aleator este de a considera o legatura izolata si de a presupune ca noi fluxuri sosesc conform unei distributii Poisson. Presupunand ca controlul in bucla inchisa aloca parti echitabile pe masura ce numarul de fluxuri se schimba, sistemul constituie un procesor M/G/1 de coada de partajare. Capacitatea legaturii este c si incarcarea sa (rata sosirilor x marime medie/c) . Daca , numarul de transferuri in desfasurare Nt este distribuit geometric, iar throughputul mediu al oricarui flux este egal cu . Aceste rezultate nu depind de distributia marimii documentelor. Timpul de raspuns estimat este finit pentru , chiar daca distribuita marimii documentelor este de tip coada lunga. Aceasta este in contrast cu cazul cozii M/G/1- primul venit primul servit- unde o distributie in timp a serviciilor de tip coada lunga, cu dispersie infinita conduce la o intarziere estimata infinita pentru orice incarcare pozitiva. Cu alte cuvinte, pentru modelul presupus al traficului auto-similar, controlul in bucla inchisa evita problemele de congestie severa asociate cu controlul in bucla deschisa. Daca se considera ca fluxurile au ponderile , generalizarea corespunzatoare a modelului de mai sus face o partajare discriminativa. Performanta acestui model de coada depinde de distributia marimii documentelor. Fie R(p) timpul estimat pentru transferul unui document de marime p. Figura 9 prezinta timpul de raspuns normalizat R(p)/p ca functie de p pentru un sistem de partajare cu discriminare in doua clase ce are urmatorii parametrii : c=1, capacitatea liniei egala cu unitatea, amandoua clasele au medie egala cu unitatea, distributie a marimii exponentiala si rata sosirilor egala cu 1/3. Fluxurile din clasa i au parametrul de partajare , unde .

39

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.

40

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 elasticControlul acceptarii prin limitarea numarului de fluxuri ce folosesc o legatura data, asigura ca throughputul nu descreste niciodata sub un nivel minim acceptabil pentru

41

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 serviciiSe 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

42

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 incarcariiDin 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.

43

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

5.7.3.3 Dimensionarea reteleiProiectarea 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 pi. 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 ei este astfel incat probabilitatea pierderii de date este neglijabila (mai mica decat o valoare propusa ca ideal) atat timp cat unde ni 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 ni 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 pi cand c este mare in raport cu ei 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,

44

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 elasticUrmand 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 Be 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

45

elastic : o legatura de capacitate c poate manipula un volum de trafic elastic Ae (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. ConcluziiS-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.

46

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.

47

[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.

48