4
lunghezza delle trame nei servizi senza connessione sono variabili e, a volte, consistenti ,
mentre ATM utilizza celle corte e di lunghezza fissa.
Per vincere questa sfida, oltre ad una adeguata progettazione dei sistemi, occorre anche
conoscere profondamente il traffico, sul quale questi sistemi andranno a lavorare: nel
mondo vi Ł un costante interesse verso il traffico offerto da piø LAN interconnesse, perchØ
questo presenta caratteristiche di autosimilitudine che ha notevoli implicazioni sulle
prestazioni dei servers di rete. Questo ci ha spinto ad intraprendere una campagna di
misure di traffico LAN che ci consentisse una valutazione realistica delle prestazioni
attraverso le simulazioni e di avere a disposizione una quantit di dati sufficientemente
ampia, per la modellizzazione del traffico stesso.
Questo lavoro Ł cosi organizzato: nel primo capitolo viene data una descrizione dei
processi autosimili; nel capitolo due discuteremo delle caratteristiche statistiche delle
misure di traffico effettuate nel Dipartimento di Ingegneria dell Informazione; nel capitolo
tre si dar una panoramica sulle soluzioni per l interconnessione di reti connectionless su
ATM; infine nel capitolo quattro si far uno studio simulativo in presenza di traffico reale.
5
Capitolo 1
Processi Autosimili
1.1 Introduzione ai Processi Autosimili
Negli ultimi anni sono state effettuate campagne di misurazione del traffico Ethernet,
principalmente presso il Bellcore Morristown Research and Engineering Center, che hanno
rivelato la natura frattale del traffico generato da piø LAN interconnesse. Alla luce di
queste nuove conoscenze, i tradizionali modelli si sono rivelati inadatti a descrivere
accuratamente le caratteristiche statistiche del traffico reale. Piø recentemente, misure
effettuate su traffico video VBR (Variable Bit Rate), hanno evidenziato, anche in questo
caso, una nature autosimile, indipendentemente dal tipo di scena e dal tipo di codifica
utilizzato. Una caratteristica fondamentale dei processi autosimili Ł la Long Range
Dependence (LRD), cioŁ la loro funzione di autocorrelazione decade con velocit inferiore
a quella esponenziale; questo in netto contrasto con gli usuali modelli di traffico (come
6
quello Poissoniano), in cui la funzione di autocorrelazione decade con velocit almeno
esponenziale.
In questo capitolo verranno descritte le principali caratteristiche statistiche dei processi
autosimili e illustreremo alcuni procedimenti di tipo grafico per la stima del parametro di
Hurst che, come vedremo, d una misura del grado di autosimiltudine di un processo.
1.2 Caratteristiche di un processo autosimile
Le figure 1.1, 1.2, 1.3 mostrano il processo conteggio dei pacchetti in una fissata unit di
tempo (rispettivamente 0.1, 1, 10 secondi) ricavati dalle misure Ethernet effettuate nel
dipartimento di Ingegneria dell Informazione.
Fig 1.1 Grafico del numero di arrivi su 0.1 secondi
7
Fig 1.2 Grafico del numero di arrivi su 1 secondo
Fig 1.3 Grafico del numero di arrivi su 10 secondi
8
Da queste figure si pu vedere come ogni realizzazione sia s imile (in senso
distribuzionale) a ciascun altra: ci viene cosi data un idea della natura autosimile o frattale
del traffico, dato che il processo osservato appare invariante rispetto alla scala temporale
scelta per rappresentarlo. Un altra caratteristica che pu essere osservata Ł che il processo
non ha una lunghezza caratteristica dei suoi bursts, cioŁ degli intervalli di tempo durante i
quali il numero dei pacchetti arrivati si scosta in modo significativo dal valor medio: in
altre parole i burts consistono in sottoperiodi molto bursty separati l uno dall altro da
sottoperiodi meno bursty. Questa autosimilitudine del traffico Ethernet Ł drasticamente
differente sia dai modelli utilizzati per descrivere il traffico telefonico, sia dai modelli di
traffico a pacchetto usualmente considerati. Quest ult imi producono realizzazione del
processo conteggio dei pacchetti che sono indistinguibili dal rumore bianco, dopo aver
aggregato su centinaia di millisecondi. Quest esempio grafico della natura autosimile del
traffico Ethernet, suggerisce che il traffico su una data scala di tempo Ł statisticamente
identico a quello su una differente scelta dell intervallo tempo rale di osservazione.
La nozione di autosimiltudine, chiaramente, non Ł una semplice intuizione grafica, ma un
preciso concetto matematico.
Sia X= {X
i
: i=1, 2, 3, ... } un processo stocastico stazionario in senso lato, cioŁ con media
costante µ =E[X
i
], varianza finita σ
2
=E[ (X
i
-µ )
2
] e funzione di autocovarianza normalizzata
r(k)=E[ (X
i
-µ ) (X
i+k
-µ ) ] / E[ (X
i
-µ )
2
], con k=0, 1, 2, ... che dipende solo da k. Si assuma
inoltre che r(k) sia della forma:
∞→≈
−
kper )()(
1
kLkkr
β
(1.2.1)
9
in cui 0 < β < 1 e L
1
Ł una funzione che varia lentamente all infinito, cioŁ
lim
()
()
t
Ltx
Lx
→∞
=
1
1
1
per tutti gli x>0.
Si consideri quindi la serie temporale
{
}
X X k = 1, 2 ,3 ...
(m)
k
(m)
= :
ottenuta mediando la
serie originale X su blocchi di dimensione m, con m=1, 2, 3 nel modo seguente:
X
m
XX
k
m
km m km
()
( ... )=+
−+
1
1
con k=1, 2, 3 ... (1.2.2)
La generica serie temporale X
(m)
Ł detta processo aggregato di ordine m ed Ł anch essa
stazionaria in senso lato.
Si indichi con r
(m)
(k) la funzione di autocovarianza normalizzata del processo X
(m)
.
Se vale la relazione:
r
(m)
(k)=r(k) per tutti gli m=1, 2, ... e con k=1, 2, ... (1.2.3)
allora il processo Ł detto esattamente autosimile del secondo ordine con parametro di Hurst
H=1 -β /2 (1.2.4)
(come si vedr meglio in seguito H Ł un parametro che consente di quantificare il grado di
autosimilitudine di un processo). In altre parole Ł esattamente autosimile se i processi
10
aggregati X
(m)
sono indistinguibili da X almeno per quanto riguarda le propriet delle
statistiche del secondo ordine. Invece X Ł detto asintoticamente autosimile del secondo
ordine, con parametro di Hurst H=1-β /2, se sono verificate le seguenti relazioni:
12)(
1)(
−→
−∞→ βmm
kr
per k=1, 2, 3, ... (1.2.5)
)(
2
1
)(
22)( β
δ
−∞→
→ kkr
mm
in cui δ
2
(f(k))=f(k+1)-2f(k)+f(k-1). Dalle relazioni precedenti si deduce che un processo
asintoticamente autosimile ha la propriet che, per grandi valori di m, la funzione di
autocovarianza normalizzata corrispondente al processo aggregato di ordine m dipende
solo da β che da solo, quindi, descrive completamente la funzione di autocorrelazione del
processo.
Da quanto sopra risulta quindi evidente una delle propriet piø rilevanti dei processi
autosimili, cioŁ che la funzione di autocorrelazione dei processi aggregati di ordine m
mantiene una struttura simile a quella del processo X, contrariamente a quanto accade nei
tradizionali modelli di traffico di tipo SRD (Short Range Dependence) per i quali si
verifica che i processi aggregati di ordine m tendono ad assumere caratteristiche di rumore
al crescere di m, cioŁ:
0)(
)(
→
∞→mm
kr per k=1, 2, ... (1.2.6)
11
Tale propriet viene indicata come Long Range Dependence ed Ł diretta conseguenza del
fatto che un processo autosimile presenta un decadimento iperbolico della sua funzione di
autocorrelazione.
In figura 1.4 Ł illustrata la differenza tra la funzione di autocorrelazione di una traccia
prelevata attraverso le misure da noi effettuate e una traccia sintetica di tipo Poissoniano
avente la stessa media della prima
Fig 1.4 Funzione di autocorrelazione di una traccia Poissoniana ed una reale con caratteristica di
autosimilitudine
Dalla figura si pu notare come la funzione di autocorrelazione relativa alla traccia
autosimile decada in maniera molto piø lenta rispetto a quella Poissoniana, la quale, gi
dopo circa cinque passi, Ł praticamente nulla.
12
1.3 Il parametro di Hurst come descrittore del traffico
Un processo autosimile soddisfa alla propriet di Long Range Dependence, la quale
implica che l andamento della funzione di autocorrelazione dipende solamente dal
parametro β . Spesso si preferisce riferirsi ad un altro parametro H, legato a β dalla
relazione (1.2.4), chiamato parametro di Hurst ed esprimere il comportamento statistico dei
processi osservati valutando il valore di questo parametro.
In particolare un processo che possiede un parametro di Hurst compreso tra 0.5 e 1 gode
della propriet di LRD.
Si osserva che aumentando il valore di H, il processo tende ad essere piø correlato e
contemporaneamente, riferendosi ai processi di traffico esaminati, le sue realizzazioni
tendono a presentare un andamento con la presenza di una maggiore burstiness .
Questo comportamento deriva dal fatto che, essendo il processo fortemente correlato, una
volta che esso assume un valore che si discosta in modo significativo dal suo valor medio,
tende a rimanere vicino a questo valore anche negli istanti successivi, creando un burst che
pu mantenersi per un tempo notevolmente lungo, confermando la natura autosimile del
traffico. Sperimentalmente si osserva che all aumentare del carico di una rete, il traffico
risultante tende a presentare piø bursts ed il parametro di Hurst tende ad aumentare.
Questo Ł ancora una volta in forte contrasto con i tradizionali modelli di sorgente che
vengono usati nell analisi simulativa per reti a larga banda, per i quali, aumentando il
numero di sorgenti che trasmettono, la burstiness tende a diminuire.
Dal punto di vista della modellizzazione del traffico, quindi, si fa sempre riferimento al
parametro di Hurst come descrittore della burstiness del traffico, anzichØ far riferimento ad
13
altri indici come il rapporto picco/valor medio, usati in molte applicazioni per definire le
propriet statistiche dei processi reali.
1.4 Metodi di analisi statistica mirati alla valutazione
del parametro di Hurst
In questo paragrafo verranno analizzati alcuni metodi di analisi statistica che consentono di
stabilire se la traccia analizzata Ł di tipo autosimile ed in particolare consentono di
effettuare una stima del parametro di Hurst del processo analizzato.
In particolare verranno illustrati oltre al procedimento numerico da seguire per realizzare
tali analisi, i principi fondamentali del funzionamento dei metodi stessi.
Nel dettaglio presenteremo due metodi di stima di tipo grafico: la valutazione della
statistica R/S e la grandezza Variance-Time della traccia analizzata.
1.4.1 Stima del parametro di Hurst col metodo del R/S
Come gi detto i processi autosimili sono caratteri zzati da una funzione di autocorrelazione
del tipo (1.2.1), il cui decadimento Ł di tipo iperbolico al crescere di k; per questo motivo
tali processi sono comunemente detti Long Range Dependent. Accanto a questa
caratteristica vi sono altre particolarit che distinguono i processi autosimili, in particolare
Ł stato osservato che questi processi presentano un fenomeno noto come effetto Hurst per
il quale la statistica R/S, che illustreremo tra breve, di un processo LRD risulta essere
differente rispetto a quella di uno SRD. L origine del nome dell effetto (Hurst), che sta alla
base del metodo di analisi in questione, Ł dovuta all idrologo Hurst il quale propose tale
14
metodo per lo studio del livello di riempimento di un bacino idrico. Utilizzando le
notazioni proposte da Hurst si consideri di voler studiare l andamento del livello di
riempimento di un bacino nell intervallo temporale (t, t+k); per semplicit si assume che il
tempo sia discreto e che non vi siano perdite nel bacino. Si ipotizza inoltre che il flusso
d uscita del bacino sia uniforme e che il bacino abbia livelli di riempimento coincidenti
all istante iniziale e finale di analisi. Indichiamo allora con X
i
il flusso d ingresso
all istante i-esimo e con:
i
j
i
j
XY
∑
=
=
1
(1.4.1)
il flusso di ingresso totale fino al generico istante j. Si pu dimostrare che la capacit
risulta essere pari a:
−−−−
−−−=
++
≤≤
++
≤≤
)( min)(max ),(
0ki0
tkttit
ki
tkttit
YY
k
i
YYYY
k
i
YYktR
(1.4.2)
R(t,k) Ł noto come adjusted range. Per poter studiare la propriet della grandezza
considerata indipendentemente dalla scala considerata si normalizza R(t,k) con la seguente
quantit :
)
(
Stk
k
XX
i
tk
it
tk
(, )
,
=−
=+
+
∑
1 2
1
(1.4.3)
15
con
X
k
X
tk
i
it
tk
,
=
=+
+
∑
1
1
(1.4.4)
Il rapporto R/S Ł indicato con il nome di Rescaled Adjusted Range e se graficato in scala
logaritmica in funzione del valore di k ha il seguente andamento:
()
log log E
R
S
aH k
≈+ ⋅
(1.4.5)
Quest espressione della statistica R/S Ł propria dei processi autosimili; al contrario i
processi di tipo SRD presentano una statistica R/S siffatta :
()
log log E
R
S
bk
≈+ ⋅
1
2
(1.4.6)
Questa discrepanza prende il nome di effetto Hurst.
In base a quanto detto la statistica R/S di una generica realizzazione di un processo pu
essere valutata in questo modo. Si supponga di avere una traccia suddivisa in numero di
blocchi non sovrapposti pari a k, ognuno dei quali contiene un numero di campioni n=L/K
(si noti che il generico campione del processo rappresenta il numero di arrivi nell unit di
tempo). Per ognuno dei blocchi si valuta la seguente quantit :
16
()
WXX XkXn
k
=+++−
12
... ( )
con k=1, 2, ..., n (1.4.7)
nella precedente relazione la grandezza
()
Xn rappresenta la media campionaria fra i
campioni del generico blocco. Una volta valutati i valori della grandezza W
k
per valori
crescenti dell indice k si costruisce la quantit R(k) nel modo cosi indicato :
Rk WW WW
kk
( ) max( , , ..., ) min( , , ..., )=−00
11
(1.4.8)
Si costruisce quindi la quantit S(k) che viene definita come segue:
()
Sk
k
X
j
j
k
()=−
=
∑
1
2
0
η
(1.4.9)
Nella precedente relazione η rappresenta il valor medio dei campioni del processo in
analisi contenuti nel generico blocco. Una volta valutate le due quantit R(k) e S(k) per
ogni blocco si pu valutare il rapporto R(k)/S(k) per valori di k che vanno da 1 a k.
Valutate quindi le varie grandezze indicate nelle precedenti formule e valutati i vari
rapporti tra tali grandezze per ogni blocco in cui Ł suddivisa la traccia in esame si procede
andando a determinare il valor medio delle statistiche relative ai singoli blocchi:
n ..., 2, 1,=k
)(
)(
kS
kR
E
(1.4.10)
17
E quindi possibile stimare il parametro di Hurst della traccia analizzata in maniera grafica.
Tenendo infatti conto che per un processo autosimile vale la relazione:
E
Rn
Sn
()
()
∝→∞cn n
H
(1.4.11)
si ha che rappresentando le grandezze indicate nelle due formule precedenti, in scala
doppiamente logaritmica, essa ha un andamento, per valori di n sufficientemente grandi,
asintoticamente lineare la cui pendenza Ł pari al valore del parametro di Hurst.
In figura 1.5 Ł mostrato il grafico risultante dalla valutazione della stima R/S applicata alla
traccia del 19 gennaio prelevata nelle nostre campagne di misura.
Fig 1.5 Statistica R/S
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
