Auto-similaritatea traficului in internet

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 y_j 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, j₁ si j₂, 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 y_j si nu in raport cu o aliniere stransa a datelor y_j. O aranjare exagerata a estimatilor y_j 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 y_j 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 y_j 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 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 j₁ 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 j₁=1 si j₂ 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 cula 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 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 y_j ca fiind astfel incat prin definitie. Orice tip de regresie liniara aplicata asupra lui y_j, este un estimator deplasat al lui deoarece deplasamentul nu cere decorelarea intre valorile lui y_j 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 y_j 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 n_j la fiecare scara. Astfel se poate obtine o expresie pentru dispersia sa care sa fie independenta de baza de coeficienti wavelet.

Parametrul de magnitudine c_f este proportional cu dar de fapt se foloseste pentru estimare o cantitate adimensionala care depinde de wavelet. Se defineste deci estimatorul lui c_f 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 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 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 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:

(44)

Unde m si sunt parametrii nenegativi, m 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 , 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 stocare

Procesul 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 V₀ este distribuit ca . Conform criteriului de continuitate Kolmogorov cu probabilitatea 1. Deoarece s-a presupus ca m0 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 V_t 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 V_t=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 output

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