Auto-similaritatea 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¹).

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.


Figura 1. Setul Cantor unidimensional.
Se considera un interval inchis S₀ =[0,1]. Pentru constructia intervalului S₁ se imparte S₀ in trei parti egale si se anuleaza cea de-a doua treime, adica valorile din intervalul (). Rezulta ca setul S₁ va fi format din reuniunea celor doua intervale ca in figura de mai sus. Cele doua intervale din setul S₁ vor fi fiecare impartite in trei intervale egale din care se vor elimina valorile din intervalul din mijloc. Se va obtine astfel setul S₂ 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.

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 S₁ si se mareste de trei ori se obtine setul S₀. in mod asemanator se poate obtine S₀ din S₂ prin scalarea setului S₂ 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.

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 r_n acea valoare a lui r pentru care apare primul ciclu perioada 2ⁿ, Feigenbaum a urmarit evolutia acestor valori ale parametrului r.

Se demonstreaza ca r_n 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-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 S₀. Pentru a genera S₁, se elimina treimea din mijloc a segmentului S₀ si se inlocuieste cu doua din laturile unui triunghi echilateral. Seturile urmatoare se construiesc dupa acelasi principiu, astfel ca S_n se obtine inlocuind treimea din mijloc a fiecarui segment din setul S_n-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 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 r² patrate componente. Daca in loc de patrat se considera un cub, vor fi necesare r³ 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 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 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 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 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.

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), , 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(t₁), X(t₂),…X(t_n)) si (X(t₁+k), X(t₂+k), …..X(t_n+k)) poseda aceeasi distributie oricare ar fi si . In contextul procesului shiftat cu k sau al unei serii de timp X_k, X si X_k 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)

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 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 (0