AUTOSIMILARITATEA TRAFICULUI IN INTERNET



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 developate[1]).

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

[pic]

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 ([pic]). 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 [pic] si se constituie dintr-un numar infinit de bucatele separate de spatii libere de diferite dimensiuni.

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.

[pic]

[pic][pic]

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 :

[pic] (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.

[pic]

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

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.

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

[pic] (2)

[pic]reprezinta numarul universal al lui Feigenbaum.

1.2 Dimensiunile fractalilor auto-similari

Notiunea 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 [pic].

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.

[pic] (3)

[pic]

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 similaritatii

Fractalii 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 este exponentul definit de relatia [pic] unde m este numarul de copii iar r factorul de micsorare. Echivalent,

[pic] (4)

Dimensiunea curbei Koch este de [pic]

Dimensiunea capacitatii (dimensiunea fractala)

Dimensiunea capacitatii in sensul dimensiunii patrat se refera la aproximarea unui set cu o multime de patrate de dimensiune [pic] cat mai mica. Pentru o linie, numarul de patrate necesare pentru aproximarea liniei cu acestea este de : [pic] , unde L este lungimea liniei. Pentru o forma bidimensionala, [pic] , unde A este aria formei.

Se poate deduce ca [pic].

Astfel dimensiunea capacitatii d este data de

[pic]. (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 corelatiei

Metoda 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 [pic] variabila dar mica si centrat in x. [pic] este numarul de puncte din cerc. Pe masura ce se mareste [pic], numarul de puncte din cerc creste exponential dupa legea [pic]

Pentru evaluarea corecta a dimensiunii fractalului, se face o estimare a lui [pic] luand in considerare mai multi x.

Rezultatul obtinut, [pic] va fi [pic]unde d este dimensiunea corelatiei.

[pic] (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 [pic] desi sunt foarte apropiate ca valoare.

1.3 Multifractalii

Fractalii rudimentari de genul setului Cantor pot fi caracterizati complet prin dimensiunea lor. Pentru fractalii complicati, caracterizarea lor prin intermediul dimensiunii devine 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 internet

2.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 internet

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

[pic]

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 lunga

2.3.1 Auto-similaritatea de ordinul 2 si stationaritatea

Se considera un proces stochastic de ordinul 2 in timp discret sau o serie de timp X(t), [pic] , 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 [pic]si [pic]. 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 [pic]. 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:

[pic] (8)

iar conditia de invarianta la translatie se defineste ca [pic]pentru toti [pic]. Momentul de ordinul 1 si doi exista si sunt finite.

Pentru toti [pic]:

-media: [pic] (9)

-dispersia: [pic]. (10)

Se presupune ca [pic]. Data fiind proprietatea de stationaritate, [pic]astfel incat se noteaza auto-covarianta cu [pic]

Pentru a defini invarianta in functie de scala, se defineste mai intai procesul agregat X(m) al lui X la nivelul de agregare m.

[pic]. (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 [pic] 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 ([pic]) daca

[pic] pentru toti [pic]. (12)

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

[pic] (13)

Auto-similaritatea in sens strict implica

[pic]pentru toti [pic] (14)

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 [pic] 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 distributionala

Se 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 (00 sunt constante.

Al doilea termen al ecuatiei (26) se calculeaza astfel :

[pic]. (27)

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

In cazul distributiilor cu coada lunga,

[pic]. (28)

[pic]pe masura ce [pic].

Astfel ca pe masura ce perioada de observabilitate a conexiunii creste, cu atat mai probabil este ca aceasta sa persiste.

Se defineste persistenta activitatii [pic] in unitati de timp.

[pic] (29)

In cazul unei distributii cu coada lunga, [pic]are un comportament asimptotic dupa legea [pic].

[pic]astfel incat predictibilitatea este sensibila exponential la intervalul [pic]. Pentru orice [pic], 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 lunga

Distributiile 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 implicate in control de tip feedback si impart resurse commune in routere de tip bottleneck.

Miscarea browniana fractionara (FBM): Y(t), [pic]poarta denumirea de miscare browniana fractionara cu parametrul H, 00 este o constanta. In ceea ce priveste [pic], 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

[pic] (31)

pentru T, N mari unde [pic] si BH(t) este FBM cu parametrul H iar C>0 este o cantitate care depinde doar de distributiile [pic] si [pic].

YN(Tt) se comporta asimptotic deci ca o miscare browniana fractionara ce fluctueaza in jurul [pic] atunci cand este normalizata in mod corespunzator. Acesta prezinta dependenta de raza lunga ([pic]) daca [pic], adica daca distributia lui [pic] este de tip coada lunga. Daca niciuna din distributiile variabilelor [pic] sau [pic] este de tip coada lunga, atunci YN(Tt) prezinta dependenta de tip coada scurta. Chiar daca [pic] este distribuita dupa o lege de tip coada lunga, dar [pic] 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 [pic]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 [pic]ii asociem un interval de timp [pic], [pic], unde Xi(t)=1 daca [pic]si 0 in rest. Se presupune ca, [pic]sunt i.i.d si ti este determinat de catre un proces Poisson[pic]care indica cate conexiuni noi ajung la momentul t.

[pic] 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/[pic].

O coada de tip M/G/[pic]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 timpii de deservire distribuiti i.i.d sunt dati de [pic], [pic], atunci se poate observa ca procesul server ocupat din coada M/G/[pic] corespunde ratei de trafic agregat X(t) din modelul Poisson cu o singura perioada on.

Daca [pic]este distribuit cu coada lunga cu indexul cozii [pic], atunci X(t), [pic]este asimptotic auto-similar de ordinul doi cu parametrul [pic].

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/[pic]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 cercetare

Cercetarile 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).

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.

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. [pic] aproape de 1 inseamna dependenta de raza-lunga puternica iar[pic]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.

[pic]

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.

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

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

3.1 Introducere

Una 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 [pic] 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[pic] iar dispersia [pic], unde [pic] este dispersia variabilei X. in cazul in care X prezinta o dependenta cu raza lunga, media experimentala este asimptotic normal distribuita catre media [pic]. Dispersia este data insa de [pic]unde [pic]si [pic] 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 wavelet

Folosirea 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 continuu

Descompunerea wavelet in continuu consta dintr-o colectie de coeficienti:

[pic] (32)

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

[pic] (33)

Acest set de functii analizoare se construieste pornind de la un pattern de referinta [pic] care poarta denumirea de wavelet mama, prin actiunea unui operator de shiftare in timp [pic]precum si un operator de dilatare (de schimbare de scala) [pic].

[pic]este ales astfel incat domeniul sau este limitat atat in timp cat si in frecventa. [pic]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 dilatare defineste scara de timp (sau in mod corespunzator gama de frecvente) in care sa se faca observarea.

Marimea [pic]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:

[pic] (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:

[pic] (35)

Unde [pic]este o constanta ce depinde de [pic]. 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 [pic] 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 discreta

Analiza multirezolutie consta dintr-o colectie de subspatii incluse unul in celalalt[pic] care satisfac urmatoarele proprietati:

[pic]

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.

[pic] (36)

Datorita proprietatii 2, approxj este o aproximatie mai slaba a lui X decat approxj-1. Pentru [pic], toata informatia este extrasa din semnal.

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:

[pic] (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 :

[pic]

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

[pic] (38)

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

[pic] (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. [pic] are un numar de [pic] de momente de anulare.

[pic] k=0,1,2,…N-1.

Valoarea lui N poate fi aleasa prin selectarea waveletului mama [pic]corespunzator. Transformata Fourier [pic] a lui [pic] satisface [pic], [pic].

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 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 : [pic] . (40)

O alta clasa de procese de scalare cu natura multifractala este aceea pentru care h depinde nu numai de timp ci si de [pic], unde [pic] 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 [pic]. Acelasi spectru multifractal se obtine pentru toate realizarile lui [pic] 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 : [pic].

3.4.1 Estimarea scalarii

3.4.1.1 Generalitati

Un 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, [pic] 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.

[pic] (41)

Unde nj este numarul de coeficienti la octava j disponibili pentru analiza. Variabila aleatoare [pic] este un estimator neparametric, nedeplasat al dispersiei procesului [pic]. Din cauza dependentei de raza curta, [pic]descreste cu [pic] si este eficienta asimptotic (de dispersie minima). Variabila [pic]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 dependenta de ordinal doi a lui X(t), trebuie studiata dependenta lui [pic] in functie de j. exista o dependenta de tip putere intre dispersia proceselor la fiecare scala si j, [pic]fiind estimatele acestei functii. Astfel, exponentul de scalare [pic]poate fi extras din panta graficului [pic]in functie de j. [pic]

Definitie: diagrama logscale (de ordinul 2) consista din dependenta [pic] in functie de j, impreuna cu intervalele de confidenta ale lui yj.

[pic]

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 scalarii

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

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, [pic]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 scalarii

Prin 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 [pic]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 [pic] 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 [pic] masurat.

O valoare a lui [pic] mai mare ca 1 poate indica necesitatea unui model auto-similar sau asimptotic auto-similar ceea ce sugereaza ca datele sunt nestationare. Exponentul [pic]se va reexprima cu ajutorul parametrului Hurst [pic]. 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 [pic]se exprima mai bine sub forma [pic], h fiind parametrul de regularitate locala.

Daca scalarea cu[pic]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.

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 [pic]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 [pic]unde a este o constanta reala. Deoarece, in general, [pic], 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 [pic]astfel incat [pic] prin definitie. Orice tip de regresie liniara aplicata asupra lui yj, este un estimator deplasat al lui [pic]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 [pic]este de preferat. Imbunatatirea este semnificativa deoarece se stie ca [pic]nu sunt egale. Pentru a exploata optimalitatea, factorii de corelatie si g(j) si dispersiile [pic]trebuie calculate, ceea ce este dificil. Ei pot fi aproximati in prezenta unor proprietati idealizatoare. Idealizarea presupune decorelarea totala.

Estimatorul [pic]al lui [pic] este panta unei regresii liniare ponderate a lui yj in functie de j data de :

[pic] (42)

unde [pic] , [pic]si [pic].

Dispersia acestui estimator este data de :

[pic] (43)

Exponentul de scalare [pic]este un parametru adimensional care caracterizeaza din punct de vedere calitativ fenomenul de scalare. Definirea lui [pic]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 [pic]a dependentei de raza lunga. [pic] 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.

Parametrul de magnitudine cf este proportional cu [pic] dar de fapt se foloseste pentru estimare o cantitate adimensionala [pic]care depinde de wavelet. Se defineste deci estimatorul lui cf ca fiind [pic] unde [pic] este un estimator al [pic].

Poate fi aratat ca [pic] are dispersie mica astfel incat proprietatile lui [pic]pot fi caracterizate exclusiv de catre acelea ale lui [pic] .

[pic]este de forma [pic]unde p este un factor independent de wavelet folosit pentru corectia deplasamentului.

Estimatorul [pic]este asimptotic nedeplasat si eficient si distribuit aproximativ lognormal.

3.4.1.5 Comparatie cu alti estimatori

In 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 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 [pic]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 [pic], 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 [pic]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 Concluzii

S-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 Introducere

Ceea 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 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 stocare

Se 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 fractionar

Inputul fluid in intervalul de timp (s,t] este dat de A(s,t) si are forma:

[pic] [pic] (44)

Unde m si [pic]sunt parametrii nenegativi, m ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download