Introduzione
5
La presenza di self-similarity ha fatto si che gli effetti del burstiness sugli elementi
di rete come i buffer nei terminali riceventi o trasmittenti, siano deleteri per le
performance dei parametri di qualit� se non si interviene con adeguate politiche di
traffic management.
Questa tematica divenuta punto focale di tutte le tecnologie di rete di ultima
generazione, e nasce proprio dalla necessit� di trasmettere flussi di traffico che hanno
esigenze in termini di throughput e di ritardi end-to-end; in particolare, ci si riferisce
a quelle categorie di applicazioni con elevato grado di interattivit�. Ovviamente,
l�attenzione ricade sul WEB, forza trainante della crescita di Internet.
Ecco, il motivo di avere modelli analitici che riassumono le propriet� del traffico
cui si � interessati.
Un �buon modello� deve seguire due criteri:
1) Deve poter rappresentare le propriet� statistiche rilevanti del traffico
reale
2) Deve essere uno strumento usato per studiare ed analizzare il
comportamento del traffico dati in rete
Qui verr� presentato un generatore di traffico Web con caratteristiche self-similar,
il quale si basa su una particolare categoria di processi, che riesce a trovare un
compromesso tra la fedelt� all�osservazione reale e la semplicit� degli algoritmi da
implementare. I processi utilizzati in questo progetto sono i processi Sup-FRP
(Superposition of Fractal Renewal Point). Tali processi hanno il vantaggio, rispetto
agli altri di essere trattabili da un punto di vista analitico in quanto alla base c�� la
teoria del rinnovamento che � di particolare importanza nello studio delle reti di
comunicazione.
La presente opera � suddivisa in cinque capitoli:
™ Il primo capitolo � dedicato alla self-similarity alle sue caratteristiche
principali e alle sue propriet�.
™ Nel secondo capitolo si affronta lo stato dell�arte riguardo alla modellazione
delle diverse tipologie di traffico presenti nelle reti dati moderne.
™ Il terzo capitolo � dedicato ai processi chiamati Fractal Point Process (FPP),
di cui i processi Sup-FRP fanno parte.
™ Nel quarto capitolo viene descritto il generatore.
™ Il quinto ed ultimo capitolo � dedicato alla fase di test e convalida del
generatore.
Capitolo 1 - Traffico Self-Similar
6
Capitolo 1
TRAFFICO SELF- SIMILAR
1.1 La Self Similarity nel Traffico di rete
1.2 Definizione di Self Similarit�
1.3 Caratteristiche della Self Similarit�
1.4 Stima del parametro di Hurst
Capitolo 1 - Traffico Self-Similar
7
Un evento rivoluzionario nel campo della modellazione e delle performance delle
reti � sicuramente la scoperta del comportamento self-similar (frattale) del traffico
dati. L�articolo �On the Self-Similar Nature of Ethernet Traffic di W.E. Leland et
al�[5], riporta i risultati di un massiccio studio effettuato su traffico Ethernet
dimostrando l�esistenza di una caratteristica self-similar (frattale), ovvero il traffico
Ethernet ha propriet� statistiche simili su diverse scale temporali: millisecondi,
secondi, minuti, ore. Un'altra conseguenza � che il traffico aggregato non ha un
andamento regolare, cio� i flussi di dati non regolari (�bursty�) tendono a produrre un
flusso aggregato irregolare (�bursty�). Tutto ci� porta alla conclusione che il traffico
di rete non sempre obbedisce alle assunzioni di Poisson adottate nell�analisi delle
code, ma ha una caratteristica self-similar (frattale) che ora ci accingeremo a trattare
dettagliatamente.
Capitolo 1 - Traffico Self-Similar
8
1.1 La Self Similarity nel Traffico di rete
Utilizzando trace di traffico reale ed analisi fatte su reti a commutazione di
pacchetto, si � potuto giungere a delle considerazioni statistiche, che erano state
ignorate dalla teoria classica sulle reti di dati.
Si � osservato che le propriet� essenziali del traffico di rete si distaccano
notevolmente da quelle che caratterizzavano i modelli Markoviani.
La caratteristica pi� appariscente del traffico di rete che � stata riscontrata � la
Long-Range Dependence (LRD), ossia la correlazione tra i campioni di una sequenza
decade molto lentamente al crescere della distanza temporale. Ci� implica una
dipendenza tra l�evoluzione futura della sequenza e la storia passata della stessa.
I modelli tradizionali, invece, possiedono correlazioni significative solo a breve
termine (processi short Range Dependence o SRD). Ne sono un tipico esempio i
processi Markoviani caratterizzati da una funzione di autocorrelazione decrescente in
modo esponenziale, rendendo cos� un campione della sequenza dipendente soltanto
da uno o comunque pochi predecessori.
La pi� significativa caratteristica della self-similarity, dal punto di vista delle
performance delle reti, � la persistenza del clustering sul lungo periodo (grandi scale
temporali), detta anche burstiness. Con i modelli tradizionali, il clustering si notava
solo sul breve periodo (piccole scale temporali).
Inoltre, � risultato che il traffico misurato possiede in molti casi una distribuzione
marginale dei tempi d�interarrivo lentamente decrescente in modo iperbolico (perci�
denominata distribuzione di tipo Heavy Tailed). Questo fenomeno evidenzia una
forte probabilit� del verificarsi l�arrivo di pacchetti entro intervalli temporali molto
grandi, creando cos� la possibilit� di ottenere zone ad altissima concentrazione
d�arrivo rispetto a periodi meno �affollati�, il che conferma la natura a burst del
traffico in questione.
Risultati sperimentali hanno mostrato che sistemi a coda, il cui traffico d�input
possieda la propriet� LRD, tendono a produrre ritardi medi ed overflow del buffer
molto alti se paragonati a quelli auspicati dalla teoria tradizionale. In particolare il
rapporto tra l�overflow e la lunghezza del buffer segue una legge polinomiale anzich�
esponenziale. Cos� la scelta di aumentare la dimensione dei buffer � di scarsa utilit�
se non si utilizza un adeguato meccanismo d�allocazione dinamica della banda.
La misura del burstiness diviene un indicatore fondamentale per molti tipi di
traffico. Le statistiche semplici del primo ordine tendono a variare in funzione
dell�intervallo d�osservazione considerato, perdendo validit�. Di conseguenza ci�
comporta l�uso di nuovi tipi d�indici, tra cui il parametro di Hurst e l�Index of
Dispersion for Counts (IDC).
Un modello per essere efficiente deve rispettare i seguenti punti:
⌢ Modellare la propriet� di Long-Range Dependece.
⌢ Riprodurre il fenomeno del burstiness su varie scale temporali.
⌢ Essere un modello facile dal punto di vista della complessit� di
rappresentazione.
Capitolo 1 - Traffico Self-Similar
9
1.2 Definizione di Self Similarity
La Self Similarity �, in generale, una propriet� che concerne tutti gli oggetti del
mondo reale in cui una parte qualsiasi opportunamente �scalata� nelle dimensioni
mantiene la stessa forma del tutto.[1] Esempi concreti sono le coste dei mari, le
nuvole ecc..
Tutto questo vale anche per i processi stocastici monodimensionali, in particolare
quelli che rappresentano il traffico osservato su una rete di calcolatori. Si pu�
affermare che:
Il traffico di rete � Self Similar quando differenti statistiche, risultano simili al
variare della scala temporale.
Figura 1.1.1 (a) Processo self-similar , (b) processo Non-self-similar
La figura 1.1.1 a � un esempio di un processo self-similar. Si noti che la funzione
non � esattamente riprodotta su differenti scale temporali, ma l�andamento �
comunque simile, ci� � in contrasto con la figura 1.1.1 b, che mostra un esempio di
un tipico processo non self-similar. Si pu� facilmente vedere che, aumentando la
scala temporale, il segnale esibisce una minore fluttuazione diventando sempre pi�
regolare.
Diamo ora alcune definizioni di processo stocastico self-similar.
⌢ Definizione di Parametro di Hurst
Il parametro di Hurst H o parametro di self-similarity, � un parametro
chiave che indica la misura di self-similarity del processo in questione. H �
la misura della persistenza di un fenomeno statistico ed � una misura della
Long-Range Dependence di un processo stocastico. H=0.5 indica l�assenza
a
b
Capitolo 1 - Traffico Self-Similar
10
di self-similarity, Pi� vicino � H ad 1, maggiore � il grado di persistenza o
Long-Range Dependence.
⌢ Definizione di self-similarity nel Tempo Continuo.
Un processo stocastico X(t) � statisticamente self-similar con parametro di
Hurst H ( 15.0 ≤≤ H ) se per ogni numero reale a>0, il processo a
-H
X(at) ha
le stesse propriet� statistiche di X(t). Questa relazione pu� essere espressa
dalle seguenti tre relazioni:
E[X(t)]=E[X(at)]/a
H
Valor medio
Var[X(t)]=Var [X(at)]/a
2H
Varianza
R
x
(t,s)=R
x
(at,as)/a
2H
Autocorrelazione
⌢ Definizione di self-similarity nel Tempo Discreto
Per una serie temporale stazionaria x, si definisce la serie m-aggregata
x
(m)
={x
k
(m)
, k=0,1,2,�} i cui campioni sono ottenuti effettuando la
seguente sommatoria:
∑
−−=
=
km
mkmi
i
m
k
XmX
)1(
)(
/1 k = 0,1,2, �
su finestre temporali disgiunte di dimensione m .Un modo di vedere la serie
aggregata � quella di considerare una compressione della scala temporale;
se la statistica del processo (valor medio, varianza, autocorrelazione, ecc...)
rimane immutata dalla compressione della scala temporale allora ci si trova
di fronte ad un processo self-similar.
Un processo X � detto Self Similar in maniera esatta con parametro di
Hurst H = 1- β /2 (0<β <1) se il processo aggregato
)(m
X verifica le
seguenti relazioni per ogni m intero positivo:
)()(
)(
kRkR
m
= ∀ m (k = 1,2,3,�) Autocorrelazione
Var(X
(m)
)=Var(X)/m
β
Varianza
Quindi, X � esattamente Self-Similar se i processi aggregati
)( m
X sono
indistinguibili da X rispetto alle propriet� statistiche del secondo ordine.
Il processo X � detto Self-Similar in maniera asintotica con parametro di
Hurst H se, per k sufficientemente grande
Capitolo 1 - Traffico Self-Similar
11
)()(
)(
kRkR
X
X
m
→ per ∞→m Autocorrelazione
Var(X
(m)
)=Var(X)/m
β
Varianza
La Self Similarity asintotica � una propriet� meno forte rispetto a
quell�esatta, ci� � dovuto al numero di campioni in nostro possesso, infatti,
in questo caso si deve avere un numero estremamente grande di campioni
per ottenere medie temporali che abbiano un�autocorrelazione prossima a
quella del processo dato.
Un�interessante caratteristica che si pu� notare � che l�autocorrelazione del
processo aggregato self-similar non tende a zero al tendere di m ad infinito;
ci� � interessante perch� contrasta con i processi stocastici tradizionali usati
in precedenza per modellare il traffico di dati, che presentavano invece la
seguente relazione:
0)(
)(
→τ
m
R per ∞→m
Altra interessante caratteristica � che la varianza di X
(m)
decresce
proporzionalmente a 1/m
β
, nei modelli di traffico markoviani la varianza
decresce,invece, secondo 1/m per ∞→m quindi, molto pi� velocemente.
12
1.3 Caratteristiche della Self Similarity
La self-similarity implica le caratteristiche di Long-Range Dependence, Densit�
spettrale che decresce per 1/f e distribuzione heavy-tailed.
1.3.1 Long-Range Dependence
Un processo si dice long-range dependent (LRD) se � caratterizzato da una
autocovarianza che decade in modo iperbolico quando si incrementa l�intervallo:
C(k)∼ |k|
-β
con |k|→∞ e 0<β <1.
In generale un processo LRD implica che
∑
∞
=
+∞=
0
)(
k
kCov .
Questa divergenza della somma cattura l�intuizione di base della long-range
dependence: le correlazioni su grandi intervalli sono tutte individualmente piccole ma
il loro effetto cumulativo � rilevante e d� risalto alle caratteristiche che risultano
essere drasticamente differenti da quelle dei pi� convenzionali processi, come i
processi short-range dependent (SRD).
I processi SRD sono, invece, caratterizzati da decadimento esponenziale della
funzione di autocovarianza
k
akCov ≈)( per ∞→k (con a costante positiva 0 < a <1),
e risulta, perci�, che:
∑
∞
=
+∞<
0
)(
k
kCov .
1.3.2 Densit� spettrale
Passando al dominio della frequenza,la long-range dependence si manifesta come
1/f-noise che � il termine usato per riferirci ad una divergenza nello spettro della
frequenza vicino all�origine.[22] L�esatta definizione per 1/f �noise � la seguente:
Il processo X � detto esibire 1/f-noise se lo spettro di potenza S(.) � della forma
γ
ω
ωω
1
)/1()( BS =
per 0→ω , 0<γ <1 con γ =1-β e β =2(H-1)
Dove B(.) varia lentamente al tendere di ω ad infinito.
� perci� illimitato alle basse frequenze ( S(0) = +∞ ).
Ci� � in contrasto con i processi SRD caratterizzati da una densit� spettrale che
rimane finita per 0→ω .
1.3.3 Distribuzione Heavy-tailed
Un�ulteriore caratteristica relativa ai processi Self Similar riguarda la distribuzione
marginale del processo X che � di tipo heavy-tailed.
Una variabile aleatoria ha una distribuzione di tipo heavy-tailed se � del tipo:
α−
≈> xxXP )(
per ∞→x ed 0<α
13
In generale, una variabile aleatoria con distribuzione di tipo heavy-tailed esibisce
valori di varianza molto alti e pu� persino esibire una varianza infinita.
Una semplice distribuzione di tipo heavy-tailed � quella di Pareto (figura 1.3.3.1)
con parametro k e α (k, α >0), con densit� e funzione di distribuzione:
f(x)=F(x)=0 (x=<k)
f(x)=
1+
α
α
x
k
k
F(x)=1-
α
x
k
(x>k, α >0)
e valor medio pari a :
E[X]= k
1−α
α
(α >1)
Il parametro k specifica il pi� piccolo valore che la variabile aleatoria pu�
assumere. Il parametro α determina il valor medio e la varianza della variabile
aleatoria.
Se α =<2 la distribuzione ha varianza infinita; se invece α =<1 la distribuzione ha
media e varianza infinite.
Pareto (k=1, α =0.3) Pareto (k=1, α =2.0)
Figura 1.3.3.1 Due esempi di Distribuzioni di Pareto
14
1.4 Stima del parametro di Hurst
Vediamo come determinare se un processo � self-similar e, in caso affermativo,
stimare il parametro di Hurst.
⌢ Rapporto tra velocit� di picco e velocit� media. Questo rapporto ci d� una
definizione del burstiness di una sorgente; pi� alto sar� il valore (>>1) pi� alto
� il grado di variabilit� nel pattern di arrivo. Questa definizione trascura molti
aspetti importanti del flusso di traffico; per esempio, non tiene conto della
lunghezza dei periodi di ON di una sorgente ON-OFF. Un altro problema �
come definire la velocit� di picco se non viene definito nessun intervallo in cui
valutare tale velocit�.
⌢ Indice di dispersione, ci sono due modi equivalenti di analizzare un processo:
dare statistiche sui tempi di interarrivo (index of dispersion for intervals IDI),
oppure, sul numero di eventi in un fissato intervallo temporale (Index of
dispersion for counts IDC).
1. Index of Dispersion for Intervals (IDI) : sia X
i
la successione degli intervalli tra
i punti di un processo punto non necessariamente i.i.d., la somma di n
successivi X
i
ha una media ed una varianza definita, indipendente dal
considerare l�istante di tempo i. La varianza della somma degli X
i
�:
Var
∑∑∑
−
==
+
=
+
+=
1
111
],var[2][][
n
j
j
k
kjj
n
k
ki
XXCoXnVarX
Dove la Covar[X
j
,X
j+k
] � la covarianza di X
j
ed X
j+k
; cos� che la varianza
dipende dalla correlazione tra successivi intervalli di tempo,una versione
normalizzata di ci� � chiamata IDI, data da:
J
n
=
][
][
2
1
XnE
XVar
n
k
ki∑
=
+
con n=1,2,�.
Da notare che l�indice di dispersione � una funzione di n. La normalizzazione �
scelta in questa forma in modo che per un processo di Poisson, l�indice di
dispersione per gli intervalli risulti pari ad uno; infatti se il processo � un
processo di Poisson si ha che la varianza �: Var ][][][
2
1
XnEXnVarX
n
k
ki
==
∑
=
+
2. Index of Dispersion for Counts (IDC). Per un dato intervallo di tempo di
lunghezza t, l�IDC � definito come la varianza del numero N
t
di arrivi durante
l�intervallo di lunghezza t diviso il numero medio di arrivi:
IDC=
][
][
t
t
NE
NVar
Nel caso di modelli di traffico convenzionali come il processo di Poisson,
l�IDC � costante o converge ad un fissato valore molto rapidamente. In
opposizione, modelli di traffico self-similar mostrano facilmente di produrre
15
un incremento monotonico dell�IDC. Se diagrammiamo il log(IDC(t)) rispetto
al log(t), questa propriet� � raffigurata da una linea retta con pendenza 2H-1.
Si pu� provare che il limite dell� IDI per ∞→n , ed il limite dell� IDC per
∞→t sono uguali:
+==
∑
∞
=
∞→∞→
1
][
)(
21
][
)(limlim
i
t
n
n
XVar
iC
X
XVar
tIJ
Dove i C(i) sono le autocovarianze dei tempi di interarrivo
⌢ Variance-time plot. Il �Variance-time plot� � un metodo usato per stimare il
valore del parametro di Hurst. Si ricordi che per una serie aggregata x
(m)
di un
processo self-similar, la varianza obbedisce alla seguente relazione per grandi
valori di m:
var(x
(m)
)≈ Var(x)/m
β
con H=1-β /2.
La relazione pu� essere riscritta nel seguente modo:
Log[Var(x
(m)
]≈ log[Var(x)]-
β *log(m)
Siccome Log[Var(x
(m)
] � una costante indipendente da m, se si diagramma
Var(x
(m)
) rispetto ad m su un diagramma logaritmico il risultato dovrebbe
essere una retta con pendenza -β . Il grafico � facilmente realizzabile da una
serie di dati x(t), basta infatti generare il processo aggregato su differenti livelli
di aggregazione calcolandone la varianza.
⌢ R/S plot. Un altro metodo usato per stimare il parametro di Hurst � l� �R/S
plot�. Per un processo stocastico x(t) definito in istanze tempo discreto {x
t
,
t=0,1,2,�}, il �rescaled range� di x(t) su un intervallo di tempo N � definito
come il rapporto R/S:
()()
()
∑
∑∑
=
=
≤≤
=
≤≤
−
−−
−
=
N
j
k
j
k
k
Nj
j
k
k
Nj
NMX
N
NMXNMX
S
R
1
2
1
1
1
1
)(
1
)(min)(max
Con M(N) si � indicato il valor medio del campione sopra un periodo di tempo
N:
M(N)=
∑
=
N
j
j
X
N
1
1
Il numeratore nel rapporto R/S � una misura del range del processo ed il
denominatore � la deviazione standard. Per un processo self-similar, il
rapporto R/S ha le seguenti caratteristiche per grandi valori di N:
R/S≈ (N/2)
H
con H>0,5
Quest�ultima relazione la si pu� riscrivere nel seguente modo:
log[R/S] ≈ H*log(N)-H*log(2)
Diagrammando il log[R/S] in funzione di N su un diagramma logaritmico, il
risultato � una linea con pendenza H.
Capitolo2 - Modellazione del traffico
16
Capitolo 2 MODELLAZIONE DEL TRAFFICO
2.1 Traffico aggregato
2.2 Traffico Ethernet
2.3 Sessione di videoconferenza
2.4 Traffico video
2.5 Traffico http
Capitolo2 - Modellazione del traffico
17
I modelli del traffico sono usati per predire le performance delle reti e valutare gli
schemi per il controllo della congestione, variano per strutture di correlazione e
distribuzioni marginali. I modelli che non catturano le caratteristiche statistiche del
traffico reale risultano insufficienti per analizzare le performance di rete perch� o le
sopravalutano o sottovalutano; inoltre devono possedere un certo numero di
parametri facilmente gestibili e la stima di questi parametri deve essere semplice. I
modelli del traffico che non sono trattabili dal punto di vista analitico possono essere
usati per la generazione di trace sintetici di traffico.
I modelli si possono suddividere in stazionari e non stazionari; a loro volta i
modelli stazionari possono essere classificati in due classi: short-range dipendent
basati su processi markoviani e long-range dependent aventi caratteristiche self-
similar.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
