Teoria delle code applicata alle Reti di Telecomunicazione

7HRULD GHOOH FRGH DSSOLFDWD DOOH 5HWL GL
7HOHFRPXQLFD]LRQH
In questo capitolo, vedremo di analizzare in modo quantitativo e qualitativo gli elementi
di ritardo presenti in una rete di telecomunicazione. I parametri che vedremo di valutare
sono il ritardo medio che un pacchetto sperimenta nell’andare da una data sorgente ad una
destinazione, ed il volume di traffico che la rete riesce a smaltire nell’unità di tempo
(WKURXJKSXW).
La teoria delle code è uno strumento essenziale per:
•
caratterizzare le prestazioni di una rete di comunicazione;
•
dimensionare una rete o un apparato di comunicazione in modo da garantire le
prestazioni desiderate.
1.1 Elementi di Ritardo in una Rete di Telecomunicazione
Il ritardo che subirà un generico pacchetto sarà dovuto alla somma dei ritardi accumulati
su ogni link attraversato [4]. Il ritardo associato ad ogni link, è costituito da quattro
componenti:
1. 3URFHVVLQJ'HOD\: Tempo che trascorre tra quando il pacchetto è correttamente
ricevuto al nodo di testa del link e quando esso viene assegnato alla coda di
trasmissione di un link d’uscita.
69
2. 4XHXHLQJ'HOD\: tempo che trascorre tra l’istante in cui il pacchetto è assegnato
ad una coda per la trasmissione e l’istante in cui il pacchetto inizia ad essere
trasmesso.
3. 7UDQVPLVVLRQ'HOD\: tempo che trascorre tra l’istante in cui il primo e l’ultimo
bit del pacchetto sono spediti.
4. 3URSDJDWLRQ'HOD\: tempo che trascorre tra l’istante in cui l’ultimo bit è spedito
dal nodo di testa del link e l’istante in cui esso è ricevuto dal nodo di coda del
link. Questo tempo dipende dalle caratteristiche del mezzo trasmissivo, ed è
proporzionale alla distanza che separa il VHQGHU dal UHFHLYHU. Si ha ancora che tale
ritardo risulta essere molto piccolo a meno del caso delle trasmissioni via
satellite.
Da quanto detto sin ora, il nodo potrebbe essere schematizzato come in Fig. 3.1, dal
quale si deduce che il SURFHVVLQJGHOD\non è altro che la somma del tempo di attesa nella
coda d’ingresso più il tempo di processamento nel server S1, il TXHXHLQJGHOD\è il tempo di
attesa nella coda d’uscita, mentre il WUDQVPLVVLRQ GHOD\ non è altro che il tempo di
processamento o di servizio nel server corrispondente alla coda d’uscita.
)LJ: Schematizzazione delle code presenti nel generico nodo di una rete.
Quanto detto sin ora trascura la possibilità che un pacchetto debba essere ritrasmesso a
causa di un errore o per qualche altra causa.
In seguito, nel modellare il generico nodo, trascureremo sia il SURSDJDWLRQGHOD\, che il
SURFHVVLQJGHOD\, in quanto il primo dipende dalle caratteristiche del mezzo e dalla distanza
dei nodi connessi dal link, ma è del tutto indipendente dal traffico presente nella rete. Il
processing delay, nelle reti a banda stretta, può essere trascurato poiché incide poco sul
ritardo totale. Esso rappresenta il tempo di lettura e di processamento del dato da parte del
70
nodo di commutazione. Quest’ultima assunzione ha l’effetto di far sparire la coda
d’ingresso ed il relativo servente dalla Fig. 3.1.
5LWDUGRGL7UDVPLVVLRQHSHU7UDIILFR0XOWLSOH[DWR
Abbiamo visto nel paragrafo precedente che uno degli addendi del ritardo di un
pacchetto è costituito dal ritardo di trasmissione (WUDQVPLVVLRQ GHOD\). Vedremo ora di
valutare questo termine nel caso in cui la tecnica di multiplexing sia 7'0, )'0 o
6WDWLVWLFDO 0XOWLSOH[LQJ. Nel link possono essere trasmessi un certo numero di bit al
secondo e questo valore, indicato tipicamente con & ed espresso in bps (bit/s), dipende sia
dalle caratteristiche del mezzo fisico di cui il link è costituito, che dalle interfacce usate per
la comunicazione.
6WDWLVWLFDO0XOWLSOH[LQJ
In questo caso i pacchetti che arrivano dalle varie sorgenti sono posti in un’unica coda e
vengono serviti con una politica di tipo FIFO. / bits sia la OXQJKH]]D GL XQ JHQHULFR
SDFFKHWWR e & bps la FDSDFLWj GHO FDQDOH; poiché la risorsa trasmissiva è allocata
interamente ad un singolo pacchetto alla volta si ha:
WG
/&
(1)
)UHTXHQF\'LYLVLRQ0XOWLSOH[LQJ
Supponiamo di avere P sorgenti di traffico, le quali devono essere multiplexate mediante
FDM sul nostro link. In tal caso, detta : la banda passante del canale, ad ogni stream di
traffico verrà associato un canale avente banda circa pari a :P. Detta & bps la capacità
trasmissiva del canale, all’i-esimo traffic stream sarà associato un canale di &P bps circa.
Quindi, il tempo necessario a trasmettere un pacchetto lungo / bits è pari a:
WG
P/&
(2)
Osserviamo come questo tempo sia P volte più grande rispetto a quello relativo allo
statistical multiplexing.
71
7LPH'LYLVLRQ0XOWLSOH[LQJ
Supponendo di avere sempre P stream di traffico, dobbiamo distinguere il caso in cui la
dimensione delle slots è piccola rispetto alla lunghezza del pacchetto, dal caso in cui slot e
pacchetto hanno la stessa dimensione.
Nel primo caso, per trasmettere un pacchetto lungo / bits, si ha lo stesso tempo di
trasmissione dato dalla (2), infatti anche in questo caso è come se ogni stream avesse
associato un canale di capacità &P.
Nel caso in cui la dimensione del pacchetto e quella della slot coincidono vale la
relazione (1) ma bisogna aspettare un tempo pari a:
P− 1)/ &
prima di poter trasmettere un altro pacchetto appartenente allo stesso stream.
Dalle relazioni ricavate sin ora si nota che lo VWDWLVWLFDO PXOWLSOH[LQJ è quello che
garantisce il trasmission delay più piccolo. Ciò è dovuto al fatto che le risorse allocate ai
clienti dagli schemi di multiplazione TDM ed FDM vengono sprecate nel caso in cui una
sorgente non ha nulla da spedire.
Ci resta adesso da calcolare il 4XHXHLQJ 'HOD\. Questa grandezza è più difficile da
calcolare poiché è un parametro statistico e per il suo studio faremo uso della teoria delle
code.
1.2 Sistemi a Coda
Un sistema a coda [4] si può genericamente definire come un sistema in cui vi sono degli
utenti (FOLHQWL) che arrivano e che vogliono utilizzare una risorsa finita (VHUYHQWH). I clienti
(FXVWRPHUV) richiedenti un dato servizio, sono generati nel tempo da una VRUJHQWH. Questi
clienti entrando nel TXHXHLQJV\VWHP e formano una coda. A certi istanti, un membro della
coda viene scelto come prossimo cliente da servire, secondo una certa politica nota come
GLVFLSOLQD GHOOD FRGD (per esempio la disciplina potrebbe essere FIFO, LIFO, etc.). Il
servizio richiesto dal cliente viene quindi svolto dal VHUYHQWH e il FXVWRPHU può uscire dal
sistema a coda. Questo processo è rappresentato in Fig. 3.2.
72
)LJ: Schema di un sistema a coda.
Possono essere fatte diverse assunzioni sui vari elementi che costituiscono il queueing
system. In generale, per caratterizzare un sistema a coda, deve essere specificata la VWDWLVWLFD
GHL WHPSLGLLQWHUDUULYR, la VWDWLVWLFD GHL WHPSL GL VHUYL]LR, nonché la GLVFLSOLQD XVDWD SHU
JHVWLUHODFRGD.
In una rete di telecomunicazione i FXVWRPHUV sono rappresentati dai pacchetti che
arrivano e vengono assegnati ad un link per la trasmissione, mentre il VHUYHU è rappresentato
dalla linea di comunicazione. La FRGD corrisponde, invece, al buffer associato al link
uscente dal nodo, tramite cui il pacchetto deve essere spedito.
Date le distribuzioni di probabilità dei tempi di interarrivo e dei tempi di servizio, il
nostro obiettivo sarà quello di determinare le seguenti quantità:
•
il numero medio di clienti nel sistema;
•
il ritardo medio del generico cliente.
Per numero di clienti nel sistema si intende il numero di utenti presenti nella coda più il
numero dei clienti che stanno usufruendo del servizio offerto dal sistema. Il ritardo di un
cliente è costituito dal tempo di attesa in coda più il tempo di servizio.
Detta:
SQW= Probabilità che all'istante W vi siano Q clienti nel sistema,
supposte note le informazioni statistiche necessarie per la determinazione delle probabilità
SQW, per ogni t, definito:
N(t) = Numero medio di clienti nel sistema al tempo W,
si ha
({1 (W )} = 1 (W ) = ∑ Q ⋅ S Q (W )
+∞
(3)
Q =0
Osserviamo che sia SQW che (^1W` dipendono dal tempo e dalla distribuzione delle
probabilità al tempo W 0, ossia, {p0(0), p1(0), p2(0), ..., pn(0), ...}.
73
I sistemi con cui avremo a che fare saranno caratterizzati dal fatto di raggiungere una
condizione di equilibrio, nel senso che:
lim S Q (W ) = S Q
W →∞
1 = ∑ QS Q = lim 1 (W )
+∞
(4)
W →∞
Q =0
dove SQ e 1 sono indipendenti dalla distribuzione delle probabilità iniziale.
Potrebbe anche risultare 1 = ∞ nonostante il sistema sia stazionario, ciò accade per
esempio nel caso in cui la velocità con cui arrivano i clienti è superiore rispetto a quella con
cui il sistema riesce a servirli.
Detta 1Wuna funzione di campionamento del numero dei clienti nel sistema, definiamo
media temporale di tale funzione nell’intervallo [0,t] la grandezza:
1 =
1
1 (τ )Gτ
W ∫0
(5)
lim 1 = lim 1 (W ) = 1
(6)
W
W
Si definisce HUJRGLFR, un sistema per cui la relazione:
W
W
→∞
W
→∞
vale con probabilità uno. Notiamo che se un sistema è ergodico, la media statistica e quella
temporale coincidono.
Consideriamo ora il ritardo medio del generico cliente. Supposta nota la distribuzione di
probabilità di ritardo di ciascun cliente, siamo in grado di calcolare il ritardo medio di ogni
cliente. Sia (^7N` il ritardo medio del k-esimo cliente.
Nel caso in cui il sistema converge ad un valore stazionario per N → +∞, si ha che il
ritardo medio del generico cliente sarà:
7 = lim 7 N
(7)
N →∞
(Anche in questo caso è possibile che risulti T = ∞).
Se il sistema è ergodico si ha che:
7 = lim 7 = lim
N
→∞
N
N
1
∑=1 7
→∞ N
N
L
(8)
L
dove Ti rappresenta il ritardo dell’i-esimo cliente.
$SSOLFD]LRQHGHL6LVWHPLD&RGDQHOOH5HWL
74
I sistemi a coda possono essere usati per modellare sia le reti a commutazione di
pacchetto che le reti a commutazione di circuito. Nelle reti a commutazione di pacchetto i
FOLHQWL sono i pacchetti da trasmettere. Supponendo che i pacchetti abbiano dimensione
variabile con media di L bit e che il canale trasmissivo abbia capacità di trasmissione pari a
C bit/s, il tempo medio di trasmissione di un pacchetto è dato da:
1 /
=
µ &
(9)
Dove µ (rate medio di servizio espresso in pacchetti/secondo) è il numero medio di
pacchetti trasmessi dal servente in un secondo. Detto λ il numero medio di arrivi in un
secondo, si definisce IDWWRUHGLXWLOL]]D]LRQH:
λ
µ
(10)
λ⋅/
&
(11)
ρ=
e sostituendo nella (10) la (9) si ha:
ρ=
Il numeratore della (11) rappresenta il carico medio nella rete (λ⋅L [bit/s]), mentre il
denominatore rappresenta la capacità di trasmissione della rete [bit/s]. Dunque il parametro
ρ fornisce quantitativamente la misura di TXDQWRqFDULFDWRLOVLVWHPD. Se tale parametro è
maggiore di 1, il sistema non riesce a smaltire il carico poiché il numero medio di arrivi è
superiore al numero medio di partenze.
7HRUHPDGL/LWWOH
75
Il teorema di Little [5] stabilisce che tra 1 e 7 intercorre una dipendenza lineare. Detta λ
la costante di proporzionalità risulta:
N = λT
dove:
(12)
λ = UDWHPHGLRGHJOLDUULYL
ed è dato dalla relazione:
YDORUH DWWHVR DUULYL LQ
→∞
W
λ = lim
W
[0, W ]
(13)
Definiamo rispettivamente:
•
α(t) = Numero degli arrivi nell’intervallo [0, t],
•
β(t) = Numero delle partenze nell’intervallo [0, t].
Supposto 1 0, dalla definizione di DWe EWrisulta chiaramente:
1W β(t) −α(τ)
(14)
dove 1W indica il numero di clienti presenti nel sistema all’istante t. Indichiamo con ti
l’istante in cui l’i-esimo utente arriva nel sistema, mentre con Ti il tempo speso nel sistema
dall’i-esimo utente.
Consideriamo ora un istante t, l’area racchiusa tra le due curve di Fig. 3.3, in virtù della
(14), è pari a:
∫ 1 (τ )Gτ
W
R
Ma d’altro canto risulta:
∫ 1 (τ )Gτ = ∑ 7 +
β (W )
W
L
R
=1
∑ (W − W )
α (W )
L
L
(15)
L
= β (W )+1
Dividendo ambo i membri della (15) per t si ottiene:
1
α (W )
1 (τ )Gτ =
∫
W
W
W
R
∑7 +
β (W )
L
=1
∑ (W − W )
α (W )
L
= β (W )+1
α (W )
L
L
(16)
76
)LJ: Schematizzazione degli arrivi e delle partenze in un sistema.
Osserviamo che il primo membro della (16) non è altro che la media temporale in [0, t]
del numero di clienti presente nel sistema (vedi (5)). D’altro canto si ha che:
α (W )
=λ
W
W
dove λt rappresenta la media temporale del rate degli arrivi nell’intervallo [0, t]. Infine
notiamo che risulta:
∑7
β (W )
L
=1
L
∑ (W − W )
α (W )
+
= β (W )+1
L
α (W )
L
=7
W
dove Tt rappresenta la media temporale del tempo che un cliente spende nel sistema
nell’intervallo [0, t]. In virtù di queste osservazioni possiamo scrivere:
Nt = λtTt
(17)
Se supponiamo che si abbia:
77
lim 1 = 1
W
→∞
W
lim λ = λ
lim 7 = 7
segue subito la formula di Little 1 λ7.
W
→∞
W
W
→∞
W
È importante notare che Tt include il tempo speso nel sistema da tutti i clienti arrivati tra
1 e βW), ma tralascia il tempo speso dai clienti ancora nel sistema all’istante t. Se si suppone
che 1W → 1 ∞, (il che implica che tutti i clienti sono serviti in un tempo finito) l’effetto
dovuto ai clienti presenti nel sistema all’istante W diviene via via trascurabile, ed al crescere
di t, Tt può effettivamente essere interpretato come la media temporale del tempo di
sistema.
L’importanza del teorema di Little deriva dalla sua generalità. Esso può essere applicato
ad un qualsiasi sistema a coda che raggiunga una condizione di equilibrio statistico. La cosa
importante nell’applicare il teorema di Little è quella di interpretare nel modo appropriato
N, λ e T.
Prendiamo in esame la coda del Queueing System; detta λ la frequenza di arrivo dei
clienti, la lunghezza media coda è data dalla relazione:
NQ = λW
(18)
Dove : è il tempo medio di attesa in coda. Analogamente, applicando il teorema di
Little nella parte di uscita del sistema a coda, si ha che il numero medio di pacchetti in
trasmissione ρ è dato dalla frequenza di arrivo dei pacchetti λ per il tempo medio di
trasmissione ( ; ):
; = Tempo medio di trasmissione =
ρ = λ;
(19)
1
µ
Il parametro ρ è chiamato IDWWRUHGLXWLOL]]D]LRQHdella linea, perché è definito come il
numero medio di pacchetti entranti nel servente per il tempo medio di trasmissione, ovvero
rappresenta la porzione di tempo per la quale la linea è occupata nella trasmissione di un
pacchetto.
Gli DVSHWWLFDUDWWHUL]]DQWL di un sistema a coda si possono riassumere nei seguenti:
78
•
GLVWULEX]LRQH VWDWLVWLFD R GHWHUPLQLVWLFD GHO SURFHVVR GL DUULYR GHOOH ULFKLHVWH
Si utilizza spesso anche la distribuzione del tempo che intercorre tra gli arrivi di
richieste successive. Il numero medio o WDVVR GL DUULYR GHOOH ULFKLHVWH in un
secondo è generalmente indicato con λ,
•
•
GLVWULEX]LRQHGHOODGXUDWDROXQJKH]]DGLXQDUULYR,
FDSDFLWj GHO EXIIHU SHU OD PHPRUL]]D]LRQH GHOOH ULFKLHVWH in attesa di servizio
ovvero capacità della coda,
•
•
FDSDFLWjGLIRUQLUHLOVHUYL]LR ovvero QXPHURGLVHUYHQWL,
WHPSR GL VHUYL]LR: tempo che occorre al servente per soddisfare la richiesta in
servizio.Può essere fisso o caratterizzato statisticamente,
•
GLVFLSOLQDGLFRGD. La disciplina con cui si regola l’accesso al servizio può avere
varie modalità:
o disciplina ),)2 (First In First Out): la prima richiesta che raggiunge il
sistema è la prima ad essere servita;
o disciplina /,)2 (Last In First Out): l’ultima richiesta arrivata è la prima
ad essere servita;
o disciplina 5DQGRP: le richieste sono servite in modo casuale con
distribuzione uniforme;
o disciplina con SULRULWj In questo caso si possono adottare due strategie:
Œ
SULRULWjFRQLQWHUUX]LRQHGL VHUYL]LR: all’arrivo di una richiesta
con priorità maggiore rispetto a quella della richiesta attualmente
servita, il servizio viene concesso immediatamente, togliendolo a
Œ
quella che ne usufruiva.
SULRULWjVHQ]DLQWHUUX]LRQHGLVHUYL]LR: all’arrivo di una richiesta
con priorità maggiore rispetto a quella della richiesta attualmente
servita, il sistema termina il servizio in atto e successivamente
serve la richiesta con priorità maggiore.
I parametri più importanti per lo studio e la valutazione della bontà di un sistema a coda
sono:
•
WHPSRGLDWWHVDLQFRGD: tempo che intercorre da quando una richiesta entra in
coda a quando viene servita. Questo parametro è ovviamente influenzato dal
79
tempo medio di servizio di ciascuna richiesta, dalla frequenza degli arrivi delle
richieste e dalla lunghezza della coda;
•
WHPSR WUDVFRUVR QHO VLVWHPD somma del tempo trascorso dalla richiesta
all’interno della coda e del tempo di servizio a questa dedicato;
•
QXPHURGLULFKLHVWHDOO¶LQWHUQRGHOVLVWHPD: costituto dalla somma del numero
delle richieste presenti in coda e all’interno del/dei servente/i;
•
WHPSR GL RFFXSDWROLEHUR GL RJQL VHUYHQWH È intuitivo che aumentando il
numero di serventi, diminuisce il numero di richieste presenti in coda. Ogni
servente implica, però, una spesa che deve essere ripagata da un suo utilizzo
efficiente e continuativo. Un numero troppo elevato di serventi utilizzati per una
piccola frazione del tempo complessivo, può diminuire molto i tempi di coda ma
aumentare considerevolmente i costi diminuendo, inoltre, l’efficienza del
sistema.
1RPHQFODWXUD SHU L VLVWHPL D FRGD
QRWD]LRQHGL.HQGDOO
La nomenclatura, introdotta da Kendall per identificare i vari tipi di sistemi a coda fa uso
di 5 simboli.
1. La SULPDOHWWHUDindica la natura del processo degli arrivi. I valori tipici sono:
a. M: PHPRU\OHVV, indica che il processo degli arrivi è un processo di
Poisson (distribuzione di probabilità esponenziale).
b. G: JHQHUDO, indica che il processo degli arrivi è caratterizzato da una
distribuzione di probabilità generale. In questo caso non si conosce
l’andamento della funzione distribuzione di probabilità degli arrivi, ma si
conoscono solamente i momenti del 1° e del 2° ordine.
c. D: GHWHUPLQLVWLF, indica che il processo degli arrivi è caratterizzato da una
distribuzione di probabilità deterministica. Cioè i tempi di servizio sono
costanti.
80
2. La VHFRQGDOHWWHUDindica la natura della distribuzione di probabilità dei WHPSLGL
VHUYL]LR. I valori possibili, anche in questo caso, sono M, G, D e il significato è
uguale a quello spiegato precedentemente con l’unica differenza che tali simboli
si riferiscono alla distribuzione di probabilità del processo delle partenze.
3. Il terzo simbolo indica il numero di serventi del sistema a coda.
4. Il TXDUWR VLPEROR indica il QXPHUR PDVVLPR GL FOLHQWL QHO VLVWHPD. Questo
simbolo potrebbe non essere presente e per default è infinito.
5. Il TXLQWR VLPEROR indica il QXPHUR PDVVLPR GL VRUJHQWL DWWLYH. Anche questo
simbolo potrebbe non essere presente e per default è infinito. Ogni sorgente (nel
nostro caso sorgente di pacchetti) può immettere un solo pacchetto alla volta, e
potrà produrne un altro solo quando il precedente è stato spedito. Limitando il
numero sorgenti attive si può imporre un throughput massimo al sistema.
Un sistema a coda di tipo M/M/1 è dunque caratterizzato da un solo servente (terzo
simbolo), i clienti arrivano secondo un processo di Poisson con frequenza λ e la
distribuzione dei tempi di servizio è esponenziale con valor medio 1/µ sec.. Il numero
massimo di clienti nel sistema e il numero massimo di sorgenti attive nel sistema è infinito.
I sistemi caratterizzati da processo di arrivo e processo delle partenze poissoniano sono i
più semplici da studiare e anche i più conservativi. Essi, infatti, tendono a
sovradimensionare il sistema, assicurando dunque le performance richieste.
I sistemi M/M/N possono essere studiati e risolti con la teoria delle FDWHQHGL0DUNRY. È
possibile, in particolare, calcolare la probabilità SQ che nel sistema vi siano Q utenti e
tramite essa è possibile ricavare il QXPHURPHGLRGLXWHQWLnel sistema (1). Si ha infatti che:
1 = ∑ Q ⋅ SQ
∞
(20)
Q =0
Sfruttando il teorema di Little è facile ricavare anche il WHPSR PHGLR WUDVFRUVR GD XQ
XWHQWH nel sistema (T):
T=
1
λ
(21)
In modo analogo è possibile ricavare il numero medio di utenti in coda (NQ) ed il tempo
medio di attesa in coda di un utente (W).
81
Nel nostro lavoro di tesi ci siamo occupati di un sistema M/G/1 per cui, per brevità,
analizzeremo più in dettaglio i sistemi M/M/1 (caso particolare dei sistemi M/G/1)
tralasciando l’analisi dei sistemi M/M/N, M/M/∞, M/M/1/N e M/M/N/N.
&DWHQHGL0DUNRY
I processi di Markov [4] rivestono una particolare importanza nella teoria delle reti di
telecomunicazione. In questo paragrafo sono elencate le proprietà generali delle catene di
Markov. Consideriamo, per questo, lo stato ;W di un sistema ad un certo istante W e
supponiamo che [Wpossa assumere valori discreti da un insieme numerabile {a1, a2, …}.
L’occupazione degli stati nel tempo è un processo aleatorio che è molto importante per
valutare il comportamento di un sistema di comunicazione.
I processi di Markov possono essere divisi in due classi:
1. Processi di Markov a tempo discreto.
2. Processi di Markov a tempo continuo.
4.1 Catene di Markov tempo discrete
Il processo N(t) (utenti nel sistema all’istante W) può essere studiato facendo uso delle
catene di Markov tempo continue, dove la variabile W assume valori continui. È sufficiente
comunque per i nostri scopi utilizzare la teoria (più semplice) delle catene di Markov tempo
discrete (la variabile W è discreta) utilizzando questo semplice artificio: consideriamo gli
istanti di tempo
0, δ, 2δ, .... , kδ, ....
dove δ è un numero positivo SLFFROo. Indichiamo con:
Nk = numero di utenti nel sistema all’istante kδ = N(kδ)
Poiché 1Wè una catena di Markov tempo continua e Nk
N(kδ), si vede che:
{ Nk | k = 0,1,2,....}
è una catena di Markov tempo discreta.
82
Detto questo, diamo una definizione più rigorosa alle catene di Markov tempo discrete.
Sia { Xn | n = 0,1,... } un processo stocastico tempo discreto che assume valori interi non
negativi. Gli stati in cui il processo può trovarsi sono: L 0, 1, ...
Il processo è una FDWHQD GL0DUNRY se, c’è una probabilità fissa 3LM che il processo si
troverà prossimamente nello stato j supponendo che si trovi nello stato i e tale probabilità è
indipendente dalla storia che ha portato il processo nello stato i. Tale concetto è riassunto
nelle equazioni sottostanti:
Pij = P{Xn+1 = j | Xn = in, Xn-1 = in-1,…, X0 = i0} = P{Xn+1 = j | Xn = i}
(22)
∀n > 0, in-1,…, i0, i, j
Le 3LM così definite sono dette SUREDELOLWj GL WUDQVL]LRQH dallo stato i allo stato j.
Ovviamente, essendo probabilità risulterà che:
Pij≥ 0,
∑3
∞
LM
M
L = 0,1,….
= 1,
=0
(23)
Si definisce matrice delle probabilità di transizione :
 300
3
3 =  10
 ....

30
301
311
....
31
L
L
302
312
....
32
L
....
....
....

....
Possono essere definite anche le probabilità di transizione ad n passi:
3 = 3{;
Q
LM
Q
+P
= M | ; = L},
P
n ≥ 0, i ≥ 0, j ≥ 0
e può essere calcolata la matrice di transizione ad n passi Pn.
Date le probabilità di transizione ad n passi vale l’equazione di &KDSPDQ.ROPRJRURY:
3
Q
LM
+P
QP ≥ 0,
= ∑3 ⋅3 ,
∞
Q
LN
N
P
NM
=0
LM ≥ 0
(24)
Introduciamo adesso alcune definizioni.
Si dice che due stati L e M FRPXQLFDQRtra loro se esistono due indici Q e Q tali che:
3 >0
Q
3
LM
1
Q
ML
>0
Se tutti gli stati comunicano fra loro, la catena di Markov si dice LUULGXFLELOH.
83
Una catena di Markov si dice DSHULRGLFDse per qualunque stato i, non esiste un numero
intero d ≥ 2 tale che Pij con Q multiplo di d. Cioè una catena di Markov è detta SHULRGLFD
se esiste uno stato in cui è possibile ritornare solo in un numero di passi multiplo di d.
Una distribuzione di probabilità {pj | j ≥ 0} si dice essere una GLVWULEX]LRQHVWD]LRQDULD
per la catena di Markov se:
S = ∑ S ⋅3 ,
∞
M
L
L
j≥0
LM
(25)
=0
Per catene di Markov LUULGXFLELOLe DSHULRGLFKHsi ha che:
S = lim 3 , j ≥ 0
Q
M
Q
(26)
LM
→∞
pj rappresenta la probabilità, a regime, che il sistema si trovi in quello stato; essa
rappresenta dunque anche la porzione di tempo in cui il processo YLVLWDin media lo stato j;
1/pj è il WHPSR PHGLR GL ULFRUUHQ]D, ovvero il numero atteso di transizioni tra due
successive visite dello stato j (se pj = 0, il tempo medio di ricorrenza è infinito).
Si può inoltre dimostrare che in una catena di Markov irriducibile e aperiodica possono
verificarsi due possibilità:
1. pj = 0 per tutti gli stati j ≥ 0. In questo caso la catena di Markov QRQ KD
distribuzione stazionaria (è il caso di un sistema M/M/1 in cui l > m).
2. pj > 0 per tutti gli stati j ≥ 0. In questo caso la distribuzione di probabilità:
S = ∑ S ⋅3 ,
∞
M
L
L
j≥0
LM
=0
è l¶XQLFDdistribuzione stazionaria della catena.
La distribuzione stazionaria di una catena di Markov, se esiste, può essere calcolata
attraverso le HTXD]LRQL GL ELODQFLDPHQWR JOREDOH. Esse derivano dalla (23). Si ha infatti
che:
∑3
∞
ML
L
=0
=3 +
∑3
∞
MM
ML
L
=0L ≠ M
∑3
∞
=1⇒
ML
L
=0 L ≠ M
= 1− 3
MM
moltiplicando ambo i membri per pj si ha:
S ⋅
∑3
∞
M
ML
L
=0 L ≠ M
= S − S ⋅3
M
M
MM
Sfruttando la (25) si ha che:
84
S ⋅
∑3 = ∑ S ⋅3 − S ⋅3 ⇒ S ⋅
∞
M
∞
ML
L
=0L ≠ M
L
L
LM
M
MM
M
=0
∑ 3 = ∑ S ⋅ 3 − (S ⋅ 3
∞
∞
ML
L
L
= 0L ≠ M
L
LM
L
LM
=0
)
L
=M
da cui si ottiene:
S ⋅
∑3
∞
M
L
=0 L ≠ M
∑S
∞
=
ML
L
L
= 0L ≠ M
⋅3
LM
(27)
La (27) indica che in condizioni di equilibrio, la probabilità di una transizione in
partenza da j eguaglia la probabilità di una transizione in arrivo a j.
Generalizzando il discorso ad un insieme di stati 6 si ha:
∑ S M ∑ 3ML =∑ SL ∑ 3LM
∞
M∈6
∞
L∉6
L∉6
(28)
M∈6
La (28) indica che la probabilità che si abbia una transizione in partenza da S è pari alla
probabilità che si abbia una transizione verso S.
4.2 Processi di Nascita e Morte
I processi di nascita e morte sono catene di Markov in cui due stati successivi
differiscono solo di una unità, le transizioni dal generico stato k sono permesse solo verso
gli stati adiacenti k+1 e k−1.
Tali processi sono ideali per caratterizzare l’evolvere di una coda. In essa, infatti, gli
utenti arrivano uno alla volta e si accodano per ricevere il servizio.
Condizione necessaria e sufficiente affinché la catena sia irriducibile è che:
3LL ! e 3LL ! per ogni L
Considerando l’insieme di stati S = {0, 1, 2, ..., n}, le equazioni di bilanciamento parziali
(28) danno:
SQ 3QQ SQ3QQ Q .....
(29)
ovvero, la probabilità di una transizione dallo stato n allo stato n + 1 è pari alla probabilità
di una transizione dallo stato n + 1 allo stato n.
Generalizzando la (29) si ottengono le HTXD]LRQLGLELODQFLDPHQWRGHWWDJOLDWH:
pj⋅Pji = pi⋅Pij
LM ≥ 0
(30)
Queste equazioni permettono di calcolare facilmente la distribuzione stazionaria {pj
| j ≥ 0 }.
85
Osserviamo che QRQ VHPSUHvalgono le equazioni di bilanciamento dettagliate per una
data catena di Markov irriducibile e aperiodica. Un modo per verificare la loro validità è
ipotizzare la validità e tentare di risolvere il sistema che ne viene fuori per ottenere le
probabilità pj con la condizione al contorno che:
∑
S =1
M
M
Esistono due possibilità:
1. l’assunzione non è vera, ed il sistema di equazioni è inconsistente;
2. l’assunto è vero, e la distribuzione di probabilità {pj | j ≥ 0} trovata è l’unica
distribuzione stazionaria del sistema (sicuramente essa soddisfa anche le
equazioni di bilanciamento globali).
Alcune catene di Markov (irriducibili e aperiodiche) hanno la proprietà che la loro
distribuzione {pj | j ≥ 0} soddisfa un insieme di equazioni che è intermedio tra quello di
bilanciamento globale e quelle di bilanciamento dettagliate.
Per ogni stato j, si consideri una partizione 6 1 , 6 2 ,…, 6
M
Valgono le equazioni:
SM ∑ 3ML =
L∈6 PM
∑S
L∈6 PM
L
⋅ 3ML ,
M
N
M
di stati complementari.
m = 1,2,…,k
(31)
Le (31) vengono dette HTXD]LRQLGLELODQFLDPHQWRSDU]LDOL. Si può dimostrare che se la
{pj | j ≥ 0} risolve un insieme di equazioni di bilanciamento parziali, allora risolve anche le
equazioni di bilanciamento globali, e quindi è l’unica distribuzione stazionaria della catena
di Markov irriducibile e aperiodica.
È quindi importante individuare il giusto insieme di equazioni parziali soddisfatte dalla
distribuzione stazionaria per calcolare quest’ultima nel modo più semplice possibile.
4.3 Sistemi M/M/1
86
I sistemi M/M/1 sono, come preannunciato, i sistemi a coda più semplici da studiare.
Essi sono caratterizzati dal processo {N(t) | t ≥ 0} (numero di clienti nel sistema all’istante
t) in cui i tempi di interarrivo e di servizio sono distribuiti esponenzialmente. Abbiamo
visto, nel paragrafo precedente, come tale processo continuo può essere studiato tramite una
catena di Markov tempo discreta (1N
1(kδ). {Nk | k = 0,1,2,....} è dunque una catena di
Markov tempo discreta).
Nella Fig. 3.4 è rappresentato in forma grafica il sistema M/M/1, in cui gli archi sono
etichettati con le probabilità di transizione da uno stato all’altro.
)LJ: Rappresentazione in forma grafica di un sistema M/M/1.
5HOD]LRQHWUDFDULFRHWKURXJKSXWLQVLVWHPLVLQJOHVHUYHU
Per un sistema single-server il WKURXJKSXW (volume di traffico nell’unità di tempo) γ si
può calcolare come WUDIILFRVPDOWLWROsserviamo che il throughput sarebbe uguale al rate
medio di servizio (µ) se la coda non fosse mai vuota, per cui si ha che:
γ
µ − S
(32)
Il termine (1 − p0) rappresenta infatti la probabilità che il servente sia occupato.
Nel caso ideale di sistema M/M/1, sostituendo a p0 il valore ottenuto precedentemente si ha
che:
γ
µ − − ρ µ ρ λ
Per sistemi con buffer infinito, infatti, tutti i clienti che entrano nel sistema, prima o poi
verranno serviti, dunque il throughput è uguale alla frequenza degli arrivi. Il WKURXJKSXW
QRUPDOL]]DWR γ µ è il IDWWRUHGLXWLOL]]D]LRQH ρ (ρ<1).
4.4 Sistemi M/G/1
87
I sistemi M/G/1 sono sistemi a singolo servente in cui i clienti arrivano secondo un
processo di Poisson con frequenza λ e i tempi di servizio seguono una distribuzione
generica (non necessariamente esponenziale come accadeva nei sistemi M/M/1).
Supponiamo che i clienti siano serviti secondo una politica FIFO e sia Xi il tempo di
servizio dell’i-esimo cliente. Assumiamo che le variabili casuali (X1, X2, ...) siano
identicamente distribuite e indipendenti dai tempi di interarrivo.
Indichiamo con:
; = ({; } =
1
µ
il WHPSRGLVHUYL]LRPHGLR(momento del primo ordine) e con:
;2 =( ;2
{ }
il PRPHQWRGHOVHFRQGRRUGLQHdel tempo di servizio.
Si può dimostrare che, per i sistemi M/G/1 vale la IRUPXOD GL3ROODF]HN.KLQWFKLQH:
: =
λ⋅;2
2(1 − ρ )
(33)
dove : è il tempo medio di attesa in coda, mentre risulta:
ρ=
λ
=λ⋅;
µ
Il tempo medio di attesa nel sistema sarà pari alla somma del tempo medio speso nel
servente più il tempo medio di attesa in coda dato dalla (33), dunque:
7=;+
λ⋅;2
2(1 − ρ )
(34)
È facile adesso calcolare il numero medio di clienti in attesa in coda e nel sistema,
applicando il teorema di Little, si ottiene che:
14 =
λ2 ⋅ ; 2
2(1 − ρ )
1=ρ+
λ2 ⋅ ; 2
2(1 − ρ )
Adesso proviamo a calcolare il tempo medio di attesa in coda per sistemi M/M/1 come
caso particolare della formula (33). Ricordiamo che il momento del secondo ordine (o
valore quadratico medio) è dato dalla somma della varianza più il valor medio al quadrato:
88
; 2 =σ 2 + ;
2
In una distribuzione esponenziale σ2 = 1/µ2, dove µ è il valore medio, quindi:
;2 =
1
1
2
+ 2 = 2
2
µ
µ
µ
Sostituendo tale valore nella (33) si ha:
: =
ρ
ρ
=
µ ⋅ (1 − ρ ) µ − ρ
(35)
Questo risultato indica che la formula (33) per i sistemi M/G/1 vale anche per i sistemi
M/M/1, che in fondo sono un caso particolare di sistema M/G/1.
Analizziamo adesso un altro sottocaso dei sistemi M/G/1, i sistemi 0'. In tali sistemi
il tempo di servizio è GHWHUPLQLVWLFR. Un riscontro pratico a questi tipi di sistemi può essere
fatto con reti in cui la lunghezza dei pacchetti è costante, quindi il tempo di servizio è
costante per tutti i pacchetti. La varianza del tempo di servizio è dunque nulla (σ2 = 0),
quindi:
;2 =0+
1
1
= 2
2
µ
µ
Dalla formula (33) si ottiene:
: =
ρ
2 µ ⋅ (1 − ρ )
(36)
Nel caso M/D/1, si ha il valore minimo del momento del secondo ordine, e quindi anche
W, T, NQ, e N hanno il valore minimo. In particolare, W e NQ sono la metà dei
corrispondenti valori per sistemi M/M/1 con uguale rate di servizio e di arrivo.
I valori di 7 e 1 per i sistemi M/D/1 sono la metà dei corrispondenti in M/M/1 se ρ ≅ 1 e
sono uguali ai corrispondenti in M/M/1 per ρ piccolo. Ciò accade perché il tempo di
servizio è circa lo stesso nei due casi e, per ρ piccolo, il tempo che incide di più è quello di
servizio, mentre per ρ grande il termine più pesante è il tempo di attesa.
In genere, i valori di T e N per sistemi M/G/1 sono intermedi tra quelli per l’M/D/1 (che
corrispondono al caso migliore) e quelli per l’M/M/1 (che corrispondono al caso peggiore).
Come conseguenza di quanto ricavato, osserviamo che, usare il multiplexing statistico
suddividendo l’asse temporale in slots (in cui la durata della slot coincide con il tempo di
89
trasmissione di un pacchetto), implica il minimo tempo medio di attesa dei pacchetti in
coda.
Inoltre, bisogna evidenziare anche che, se per un dato sistema non è possibile conoscere
il momento del primo e del secondo ordine del tempo di servizio, è giustificato l’utilizzo di
un sistema M/M/1 come modello analitico del sistema in esame, in quanto esso porta
eventualmente al sovra-dimensionamento del sistema.
Dimostriamo adesso la formula di 3ROODF]HN.KLQWFKLQH (P-K). Tale dimostrazione farà
riferimento alla definizione del WHPSRUHVLGXRGLVHUYL]LR.
Def:
6L GHILQLVFH WHPSR UHVLGXR GL VHUYL]LR UHODWLYDPHQWH DOO¶LHVLPR FOLHQWH LO WHPSR
QHFHVVDULRDIILQFKpO¶XWHQWHVRWWRVHUYL]LRDOO¶DUULYRGHOFOLHQWHLHVLPRHVDXULVFDLO
VHUYL]LRVWHVVR
Siano:
Wi : Tempo di attesa in coda dell’i-esimo cliente.
Ri : Tempo di servizio residuo visto dall’i-esimo cliente. Cioè, se nel servente è
presente il cliente j-esimo quando il cliente i arriva, con Ri indichiamo il tempo
rimanente affinché il cliente M completi il servizio. Se non vi sono clienti nel
sistema quando L arriva (cioè il sistema è vuoto), Ri sarà zero.
Xi : Tempo di servizio dell’i-esimo cliente.
Ni : Numero di clienti trovati in attesa in coda all’arrivo dell’i-esimo cliente.
Si ha che il tempo di attesa in coda per l’i-esimo cliente è pari al tempo di servizio
residuo (del cliente già nel sevente quando L arriva) più la somma dei tempi di servizio degli
Ni utenti in coda prima dell’arrivo di L:
: L = 5L +
∑;M
M L 1
L −1
=−
M
Essendo le variabili Ni, Xi-1, .... , Xi-Ni indipendenti, si ha che:
 L −1

( {:L } = ({5L } + (  ∑ ( {; M | 1 L } = ({5L } + ; ⋅ ({1 L }
 M =L − 1

L
Facendo il limite per L che tende a infinito si ha:
: = 5+
1
14
µ
(37)
90
dove R è il WHPSRUHVLGXRPHGLRed è definito come:
5 = lim({5L }
L→∞
Usando la formula di Little, si ha che: NQ = λ W, sostituendo nella (37) si ha:
: = 5+
1
⋅ λ ⋅ : ⇒ : ⋅ (1 − ρ ) = 5
µ
da cui:
: =
5
1− ρ
(38)
Per ottenere dunque il tempo medio di attesa in coda bisogna trovare il tempo residuo
medio e sostituirlo nella (38).
Consideriamo un istante t in cui UW = 0. Si ha che:
W
1
1 0 (W ) 1 2
(
)
⋅ U τ ⋅ Gτ = ∑ ; L
W ∫0
W L =1 2
dove 0Wè il numero di servizi completati in [0,t], e ; è il tempo di servizio dell’i-esimo
L
cliente.
Moltiplicando e dividendo il secondo membro per 0Wsi ha:
0 (W ) 2
W
1
1 0 (W ) ∑L =1 ; L
⋅ U (τ ) ⋅ Gτ = ⋅
⋅
W ∫0
2 W
0 (W )
Effettuando il limite per t tendente ad infinito (supponendo che tale limite esista), si ha:
5=
1
⋅λ ⋅ ; 2
2
Sostituendo dunque nella (38) si ha:
: =
λ⋅;2
2(1 − ρ )
che è proprio la IRUPXODGL3ROODF]HN.KLQWFKLQH3..
Si noti che un sistema M/G/1 con ρ < 1 può presentare tempi di attesa infiniti se il
momento del secondo ordine tende ad infinito. Quello che succede in questo caso è che una
piccola quantità di utenti hanno un tempo di servizio molto lungo. Durante questo ampio
intervallo di tempo, un numero molto elevato di clienti arrivano nel sistema e vengono
accodati subendo dunque un lungo ritardo.
91
4.5 Sistemi a coda con priorità
Consideriamo un sistema M/G/1 in cui i clienti sono divisi in classi di priorità
decrescente [5].
Supponiamo inoltre che le priorità vengano gestite senza SUHHPSWLRQ. Cioè al cliente
sotto servizio è permesso di completare il servizio senza interruzione anche se arriva un
cliente a più alta priorità. Una coda separata è mantenuta per ogni classe di priorità. Quando
un server diventa disponibile, viene servito il primo cliente in attesa nella coda non vuota a
più alta priorità. Indichiamo con:
λk il rate di arrivo degli utenti di classe k,
;. =
1
= il momento del primo ordine del tempo di servizio relativo alla classe k,
µN
; N2 il momento del secondo ordine del tempo di servizio relativo alla classe k.
Calcoleremo adesso il tempo medio di attesa in coda per le varie classi di priorità.
Indichiamo con:
1 4(N ) : il numero medio di utenti nella coda di priorità k,
: : il tempo medio di attesa nella coda con priorità k,
N
rk = λk / µk : l’utilizzazione del sistema per la priorità k,
5 : il tempo residuo di servizio medio. Tale parametro non dipende da k perché
stiamo supponendo che non ci sia preemption.
Per la classe di priorità più alta si ha che (dalla (37)):
:1 = 5 +
Ed usando il teorema di Little si ha:
:1 =
1 (1)
14
µ1
5
1 − ρ1
Per la seconda classe di priorità si ha:
:2 = 5 +
1 (1) 1 (2 ) 1
14 +
14 +
⋅ λ1 ⋅ : 2
µ1
µ2
µ1
92
dove il quarto addendo del secondo termine rappresenta il ritardo aggiuntivo causato dai
clienti con priorità più alta che arrivano quando il customer con priorità 2 è già in attesa in
coda.
:2 = 5 + ρ1 ⋅ :1 + ρ 2 ⋅ : 2 + ρ1 ⋅ :2
:2 =
5 + ρ1 ⋅ :1
5
=
1 − ρ1 − ρ 2 (1 − ρ1 )(1 − ρ1 − ρ 2 )
Analogamente si trova che:
:N =
5
(1 − ρ1 − .... − ρ N −1 )(1 − ρ1 − ....)
(39)
Con un procedimento analogo al precedente si trova che:
5=
1
1 

⋅ λ ⋅ ; 2 = ⋅∑λ  ⋅ ; 2
2
2  =1 
Q
L
L
dove ; 2 è il momento del secondo ordine mediato su tutte le classi di priorità:
;2 =
; 12 +
λ1
Q
∑λ
L
=1
; 22 + .... +
λ2
Q
∑λ
L
L
=1
L
λ
; 21
Q
Q
Q
∑λ
L
=1
L
Sostituendo nella (39) si ottiene:


∑λ  ⋅ ; 2
 =1 
: =
2 ⋅ (1 − ρ1 − .... − ρ −1 ) ⋅ (1 − ρ1 − .... − ρ
Q
L
L
N
N
7N =
1
+ :N
µN
N
)
(40)
(41)
Tali valori dipendono fortemente dalle distribuzioni dei tempi di servizio delle varie
classi.
Si può facilmente dimostrare che il ritardo medio per cliente tende a ridursi quando si
attribuisce priorità più alta ai clienti con tempi di servizio più brevi. Questo si traduce nelle
reti a commutazione di pacchetto nell’attribuire priorità maggiore ai pacchetti di controllo
che solitamente sono molto più brevi rispetto ai pacchetti dati.
7HRULDGHO7UDIILFR
93
In questo paragrafo concentreremo le nostre attenzioni sul dimensionamento e
sull’analisi delle reti di telecomunicazione.
5.1 Intensità del Traffico
L’intensità del traffico si definisce come la quantità media di unità di lavoro che viene
offerta al sistema (o viene smaltita dal sistema) nell’unità di tempo.
Pur essendo un numero puro, l’unità di misura attribuita convenzionalmente a tale
grandezza è l¶(UODQJ e la lettera usata per indicarla è la lettera $.
Viene definito dunque il 7UDIILFRRIIHUWR:
$2 =
λ
µ
il quale rappresenta, l’utilizzazione del sistema.
Si definisce 7UDIILFRVPDOWLWR:
$6 =
γ
µ
Nel caso di reti a commutazione di circuito, la grandezza che indica quanto impegno le
risorse della rete è:
 FKLDPDWH

 WHPSR × WHPSR GL FKLDPDWD


Nel caso di reti a commutazione di pacchetto, si ha:
 PHVVDJJL

 WHPSR × WHPSR GL WUDVPLVVLRQH


L’intensità di traffico dà anche:
•
il numero medio di sorgenti contemporaneamente attive (traffico offerto) Cioè da
una misura del carico che bisogna prevedere per dimensionare il sistema;
•
il numero medio di risorse (serventi) contemporaneamente occupate (traffico
smaltito). Mi dà una misura della capacità di smaltimento di traffico del sistema.
Si definisce, 7UDIILFRSHUVR:
$3 =
λ ⋅ 3%
µ
94
In equilibrio statistico ho che AO = AS + AP.
Il fattore di utilizzazione ρ indica l’intensità di traffico smaltita dal singolo servente:
ρ=
$
λ
= 6 <1
1 ⋅µ
1
(42)
In condizione di stabilità ρ deve essere minore di 1, dunque AS deve essere minore di N.
Dalla (42) si ricava che AS = ρ⋅N.
Per questo motivo, a volte con l’unità Erlang si indica la frazione di tempo per la quale
una linea è impiegata, moltiplicata per il numero di linee in uscita al sistema.
5.2 Dimensionamento
ed
Analisi
delle
Reti
di
Telecomunicazione
I passi da effettuare per realizzare e gestire una rete di telecomunicazione sono:
1. dimensionare gli apparati all’interno della rete (in fase di realizzazione);
2. gestire la rete di telecomunicazione, cioè decidere se accettare o meno le
chiamate di richiesta di trasmissione. La decisione è presa cercando di garantire
la qualità di servizio (QoS), note le caratteristiche delle sorgenti di traffico.
La QoS (4XDOLW\RI6HUYLFH) [Rif. Par. 1.2, Capitolo 1] si caratterizza con dei parametri,
quali:
•
•
•
/RVV 3UREDELOLW\(probabilità di perdita).
'HOD\(ritardo).
'HOD\-LWWHU(variazione del ritardo intorno la media).
Per quanto riguarda la probabilità di perdita, essa è particolarmente importante per
traffici tempo reale [Rif. Par. 2.4, Capitolo 2] in cui le Unità Informative (8,) hanno una
certa CDT (&HOO'HOD\7ROHUDQFH), mentre per traffici non tempo reale la Loss Probability è
di scarsa rilevanza se non per mostrare i pacchetti scartati a causa dei buffers colmi. La
trattazione che segue farà riferimento a reti a pacchetto di tipo ATM.
Le fasi della progettazione di una rete possono essere così classificate:
1. &DUDWWHUL]]D]LRQHGHOOH6RUJHQWL.
2. 0RGHOOL]]D]LRQHGHOOH6RUJHQWL.
95
3. 0RGHOOL]]D]LRQHGHOODUHWH.
4. 9DOXWD]LRQHGHOOHSUHVWD]LRQL.
5.3 Caratterizzazione e Modellizzazione delle Sorgenti
Caratterizzare una sorgente significa capire statisticamente il comportamento della
sorgente di traffico.
Ci sono 4 grosse famiglie di sorgenti di traffico:
•
•
•
•
6RUJHQWL $XGLR.
6RUJHQWL 9LGHR.
6RUJHQWL 'DWL.
6RUJHQWL 0XOWLPHGLDOL. Esse sono un aggregato delle sorgenti precedentemente
elencate, le quali risultano correlate fra loro. Ad esempio il movimento delle
labbra di un parlatore è fortemente correlato con i dati audio, relativi alla voce
dello speaker stesso.
Una prima classificazione delle sorgenti di traffico può essere effettuata in base alla
modalità con cui i dati vengono emessi dal codificatore di sorgente.
In particolare distinguiamo &RQVWDQW %LW 5DWH &%5 e 9DULDEOH %LW 5DWH 9%5; nel
primo caso la sorgente emette a bit-rate costante, nel secondo a bit-rate variabile. Il PCM è
di tipo CBR perché codifica la voce con bit/rate costante (64 Kbit/s). Esso però è poco
efficiente in quanto trasmette anche quando si ha silenzio. Trasmettere con bit rate costante
è spesso poco conveniente, per cui si preferisce usare usualmente la tecnica VBR.
Caratterizziamo adesso le sorgenti.
7UDIILFRYRFDOH
Il traffico vocale è prodotto campionando ad intervalli regolari, e poi comprimendo, il
segnale proveniente da una sorgente vocale. I metodi di compressione sono tali che il
messaggio vocale ricostruito al ricevitore non risente di problemi di qualità. Inoltre, a
seconda del tipo di codifica usata, le perdite di celle possono essere compensate oppure no.
96
La perdita di un certo numero di celle può causare a destinazione periodi di silenzio o
troncamento del segnale ricostruito.
Come già detto, a seconda del tipo di codifica usata dalle sorgenti vocali, il traffico
generato può essere &%5 o 9%5. Se è stato usato un FRGLILFDWRUH 3&0 (Pulse Code
Modulation) a 64 Kbit/s, il traffico generato è &%5. Se invece la codifica si basa sull’uso
delle tecniche 6SHHFK $FWLYLW\ 'HWHFWRU 6$' e 'LJLWDO 6SHHFK ,QWHUSRODWLRQ '6,, il
traffico risultante è di tipo VBR. Queste tecniche sfruttano la ridondanza intrinseca in un
segnale vocale ed eliminano la non necessaria trasmissione degli intervalli di silenzio
durante una chiamata. In letteratura [15] è stato proposto un modello che assume una
sorgente vocale come un processo ON-OFF, cioè un processo di rinnovamento UHQHZDO
SURFHVV che può assumere due stati: uno stato di attività (talkspurt o ON) e uno stato di
inattività (silenzio o OFF). Ogni volta che il processo cambia stato si ha un rinnovamento,
cioè viene dimenticata la storia passata.
Le sorgenti vocali che emettono questo tipo di traffico sono dette EXUVW\ed il periodo in
cui la sorgente emette è detto EXUVW. Generalmente il EXUVW ha una durata relativamente
limitata nel tempo, ma è caratterizzato da un bit-rate molto elevato. A tal proposito, si
definisce una quantità detta EXUVWLQHVV, data dal rapporto tra la banda di picco e la banda
media della sorgente. Essa è un indice della sua attività; infatti, maggiore è questa quantità,
più la sorgente si discosta dall’essere di tipo &%5 (per le sorgenti &%5 la EXUVWLQHVV è
unitaria).
)LJ: Comportamento di una sorgente vocale.
Il tipico comportamento di una sorgente vocale bursty è illustrato in Fig. 3.5: una
sorgente vocale è attiva quando il talker parla, mentre è inattiva e non genera pacchetti
durante i periodi in cui il talker è in silenzio. Come conseguenza, il numero di celle in
97
trasmissione nella rete si riduce del 35-40% rispetto al caso in cui la sorgente venisse
codificata non considerando i periodi di silenzio.
Inoltre, il tempo di interarrivo dei pacchetti nei periodi di attività coincide con il periodo
di pacchettizzazione. Assumiamo che i periodi di talkspurt e i periodi di silenzio
costituiscano un processo di rinnovamento alternante (DOWHUQDWLQJ UHQHZDO SURFHVV) e che
questi intervalli temporali siano indipendenti tra di loro. Sia 7
2))
la durata di ciascun
periodo di silenzio, 5 il numero di celle nel periodo di talkspurt; se 7 rappresenta il periodo
di pacchettizzazione di ciascuna cella, la durata temporale del talkspurt è 7
21
= 57. Si è
osservato che il numero 5 di pacchetti in un talkspurt è una variabile aleatoria distribuita
geometricamente sugli interi positivi, cioè la durata temporale dei periodi di talkspurt è una
variabile aleatoria distribuita esponenzialmente. In una normale conversazione la
distribuzione esponenziale si adatta bene alla durata dei periodi di attività, mentre la durata
dei periodi di inattività è approssimata meno bene da questa distribuzione. Per facilitare
l’analisi si assume comunque che entrambi i periodi siano distribuiti esponenzialmente con
medie pari a 721 per il periodo di talkspurt e 72)) per il periodo di silenzio. Valori tipici di
questi parametri sono 721 ≅ 350 PVe 72)) ≅ 650 Ps.
Il processo vocale è dunque un processo ON-OFF caratterizzato dai parametri 721
e
72)) e dalla banda di picco P = 1 / T, cioè dalla frequenza di arrivo delle celle nei periodi
di ON. In funzione di questi parametri la EXUVWLQHVVE può essere calcolata come segue:
E=
72)) + 721
721
(43)
La distribuzione di probabilità del tempo di interarrivo delle celle è data da:

7
) (W ) = 1 −
 721
−1

 7 
−72)) (W −7 ) 
+
1
−
H


8 (W − 7 )
 7 


21

(44)
dove U (t − T) rappresenta la funzione gradino unitario definita come:
1....W ≥ 7
U (t - Τ) = 
0....W < 7
La funzione densità di probabilità è la derivata di F(t) , cioè:
98
 1
1 −72)) −1 (W −7 ) 
I (W ) = 
7
H

7
7
2))
 21

(45)
Se indichiamo con F(s) la funzione generatrice dei momenti, cioè la trasformata di
Laplace della distribuzione di probabilità del tempo di interarrivo delle celle, F(t), da essa
possiamo ricavare il valore medio del tempo di interarrivo:
µ =−
 7
G) (V )
= 1 + 2))
GV V =0 
721

7


(46)
Il coefficiente di variazione (ovvero il rapporto tra la varianza e il quadrato del valor
medio) del tempo d’interarrivo, è dato da:
F=
2721 7 − 721 7
−1
(7
21
−1
+ 72))
−2
−1
)7
(47)
0RGHOORWHPSRGLVFUHWR,%3
Poiché nelle reti ATM le celle hanno lunghezza costante, il tempo può essere visto come
“slottizzato” e ciascuna slot ha una durata pari al tempo di trasmissione di una cella.
Quindi, la modellizzazione delle reti ATM è preferibile che avvenga nel dominio tempodiscreto. I modelli tempo-discreto sono particolarmente adatti per la valutazione delle
prestazioni dei nodi di rete, dal momento che le operazioni all’interno di un nodo sono
sincronizzate sulle slots. Per cogliere la natura bursty del traffico vocale, sono stati proposti
diversi modelli.
)LJ: Modello IBP (Interrupted Bernoulli Process).
L¶,QWHUUXSWHG %HUQRXOOL 3URFHVV ,%3 è uno di questi ed è tale cui una sorgente è
caratterizzata da due stati (0 e 1), come mostrato in Fig. 3.6.
99
Se il processo in una slot è nello stato 0, durante la slot successiva esso rimane nello
stato 0 con probabilità 1− S, o transita nello stato 1 con probabilità S Analogamente,
quando il processo è nello stato 1, esso vi rimane con probabilità 1− T, o transita nello stato
0 con probabilità T. Quindi, i tempi di soggiorno in ciascuno stato sono distribuiti
geometricamente con parametri 1− S e 1− T rispettivamente. Non si hanno arrivi quando il
processo è nello stato 0. Nello stato 1 si hanno gli arrivi secondo un processo di Bernoulli,
cioè per ogni slot in cui il processo è nello stato 1, si ha un arrivo con probabilità B, oppure
la slot rimane vuota con probabilità 1− B. Questo processo di emissione viene interrotto
quando la catena di Markov sottostante passa nello stato 0 La matrice delle probabilità di
transizione della catena di Markov sottostante è data da:
S 
1 − S
4=
1 − T 
 T
(48)
Le probabilità di stato si possono ricavare risolvendo il sistema:
π ⋅ 4 = π

∑L π L = 1
(49)
dove, se 6(n) rappresenta lo stato della catena sottostante, π è il vettore riga il cui generico
elemento è πi = lim Prob {S(n) = L}, con L ∈ {0,1}.
Q →∞
Risolvendo il sistema (7.3-13), si trova:
π0 =
T
S+T
π1 =
S
S+T
(50)
I parametri del modello ,%3 possono essere ricavati conoscendo le durate medie dei
periodi di ON e di OFF e la bit-rate di picco P:
S=
∆
72))
T=
∆
721
γ1 = ∆ ⋅ 3
(51)
dove ∆ è la durata temporale della slot.
7UDIILFRYLGHR
100
La codifica del segnale video può richiedere parecchi megabit al secondo ed è quindi di
gran lunga superiore ai 64 kbit/sec richiesti dal segnale vocale codificato PCM; inoltre la
variabilità del bit-rate di un segnale video è molto più alta di quella di un segnale vocale e
pertanto un semplice modello, come quello ON-OFF usato per i segnali vocali, non è adatto
per i segnali video. Inoltre, in base al tipo di video, si ha una notevole ridondanza di dati,
che deriva da un’alta correlazione LQWUDIUDPH e LQWHUIUDPH.
Sono dunque necessarie delle codifiche particolari. La codifica JPEG è molto diffusa per
le immagini fisse perché riesce a caratterizzare molto bene la correlazione intraframe.
Viceversa lo standard MPEG, è molto usato per codificare le sorgenti video in quanto tiene
contro anche della correlazione interframe (tra frames diversi). Con l’MPEG [10] si
suddivide il filmato in *23(*URXSRI3LFWXUH), che è costituito da un insieme di frames
consecutivi. Secondo lo standard PAL si trasmettono 25 immagini al secondo. Il GOP ha
questa struttura:
,%%3%%3%%3%%
Il frame I viene codificato per intero con tecnica JPEG. I frames P vengono codificati
secondo una codifica differenziale rispetto al frame I e ai frames P nello stesso GOP. Infine
i frames B vengono codificati esaminando il frame I precedente e quello successivo e anche
il frame P precedente e successivo appartenente allo stesso GOP.
I frames I contengono la maggiore informazione e sono i più pesanti da trasmettere.
Viceversa i frames B sono i più leggeri e i più poveri di contenuto informativo.
Caratterizzare le sorgenti MPEG non è affatto semplice, in quanto bisogna caratterizzare
statisticamente i frames I, B e P. Sono in corso delle ricerche per capire qual è il numero
minimo di parametri per caratterizzare tali sorgenti [11].
Il video (es. videoconferenza), come già detto nel Capitolo 2 rientra nella classe rt-VBR.
Secondo [12], ogni sorgente VBR può essere modellata con un processo tempo discreto
di arrivi di Markov a gruppi ('LVFUHWH WLPH %DWFK 0DUNRY $UULYDO 3URFHVV). Per un tale
processo consideriamo la slot come l’unità di tempo.
Il
carico
di
traffico
prodotto
da
una
sorgente
di
videoconferenza
può
approssimativamente essere emulato tramite la somma di M sorgenti equivalenti ON/OFF,
che sono chiamate minisources. Ogni minisource in stato ON produce le slots con rate fisso
A, mentre nella condizione OFF nessuna slot è generata. Il tempo di interarrivo fra due
101
arrivi per ogni minisource è d = C/A, dove la C è la capacità di canale. Per ogni minisource,
p è la lunghezza media del periodo ON e q è la lunghezza media del periodo OFF (p = 1 −
q). Un minisource DWWLYR diventa SDVVLYR la prossima volta con probabilità β=1/p
(transizione ON-OFF). Un minisource SDVVLYR diventa DWWLYR la prossima volta con
probabilità α=1/q (transizione OFF-ON). Abbiamo supposto che durante un’unità di tempo
soltanto un minisource può cambiare la relativa condizione cioè, da ON a OFF o viceversa.
Questo significa che non ci sono cambiamenti improvvisi nel carico di traffico. Questo
presupposto permette l’uso d’un processo di nascita-morte di Markov e descrivere la
somma di M minisources. La Fig. 3.7 descrive lo schema di probabilità di M = 10
minisources usando un processo di nascita-morte di Markov. Quando il sistema è nello
stato m, le slots sono create secondo le funzioni di distribuzione di probabilità:
5P
IFNP_N dove la FNP è la probabilità di avere N arrivi durante il periodo di slot in cui P minisources
sono attivi (ON-state).
 P  1   G − 1 
F N (P ) =    

 N  G   G 
N
P−N
I parametri (STG) sono ottenuti calcolando la media, la varianza e l’autocovarianza del
processo definito prima con le corrispondenti statistiche dei dati misurati. Otteniamo:
S
[0ELW / V]
S+T
ST
[0ELW / V ]2
σ 2 = 0$ 2
2
( S + T)
−  1 + 1 τ
ST
T
 S
[0ELW / V ]2
& (τ ) = 0$ 2
H
2
( S + T)
µ 1 = 0$
Così: FP PG e F PG I valori dei parametri S, T, $ e G seguono le seguenti
equazioni:
A=
1µ σ 2
+
[ELW / V]
µ
M
d=C/A
T=
1  0σ 2 
1 +

α 
1µ 2 
S=
1µ 2 
1
1 +

α  0σ 2 
Tipicamente 5 ≤ M/N ≤ 10; noi abbiamo preso N=1 (modello analitico per una singola
sorgente video VBR) e M=10 (10 identici indipendenti ON-OFF sources o minisources).
102
Nelle equazioni precedenti µ è il rate medio della trasmissione e σ2 è lo scarto quadratico
medio.
)LJ: Il modello di nascita-morte di Markov per 10 minisources.
Secondo il processo precedentemente definito di nascita-morte di Markov, per descrivere
ogni sorgente VBR, bisogna usare undici stati (M + 1).
7UDIILFRGDWL
Sebbene ci si aspetti che il traffico dati sia il tipo di traffico più semplice da modellare,
ciò in realtà non è vero. Ciò è dovuto alla varietà dei tipi di traffico dati. I processi di arrivo
dei pacchetti sono stati analizzati, ma non è ancora stato identificato un modello adatto in
ambiente ATM.
La natura del traffico dati è, spesso a sproposito, considerata di tipo poissoniana oppure
geometrica [44]. Come tale, questo tipo di traffico può essere semplicemente incorporato
nei modelli esistenti del traffico bursty.
Secondo le specifiche del documento UMTS [13] il modello per servizi non real-time, ad
esempio WWW browsing, consiste di più VHVVLRQL. In ogni sessione è presente una
sequenza di SDFNHW FDOO durante le quali vengono generati datagrammi che sono
frammentati in pacchetti. In una sessione WWW browsing, una packet call corrisponde al
download di un documento WWW, ed è anche possibile che una sessione sia costituita da
una sola packet call, come nel caso del File Transfert (FTP). Ogni SDFNHWFDOO contiene un
numero casuale di datagrammi (messaggi) che sono di lunghezza variabile in bytes in
accordo con una distribuzione di Pareto troncata così definita:
103

α ⋅ Nα
(
)
,[ ≥ N
=
I
[
[

α +1
[

α
 ) ([ ) = 1 −  N  , [ ≥ N
 
[

 [

Nα

µ=
,α > 1

α −1
 2
N 2 ⋅α
,α > 2
σ =
(α − 2 ) ⋅ (α − 1)2

La lunghezza del messaggio in bytes è definita dalla seguente formula:
lunghezza del messaggio in bytes = min(P, m)
dove P è la distribuzione di Pareto (a = 1,1; k = 81.5 bytes) e m = 66666 bytes è la massima
lunghezza del messaggio.
La PDF della lunghezza del messaggio è dunque:
α ⋅ N α

I [ ([ ) =  [ α +1 , N ≤ [ ≤ P

β,[ = P
dove β è la probabilità che sia x > m ed è facilmente calcolabile da:
N
β = ∫ I [ ([ )G[ =   ,α > 1
P
α
La lunghezza media del messaggio µ è 480 bytes e si può ricavare facilmente da:
N
αN − P 
α
α
α ⋅N
N
P
µ = ∫ [ α +1 G[ + P  =
α −1
[
 P
α
Quando un documento è arrivato completamente al terminale, viene spesa una certa
quantità di tempo per elaborare l’informazione in esso contenuta,LOUHDGLQJWLPH. Un certo
tempo intercorre anche nella trasmissione tra un pacchetto e l’altro. Il processo di arrivo
delle sessioni è modellato con Poisson e rappresenta l’istante in cui il servizio inizia.
Il numero di packet call per sessione e il numero di datagrammi per packet call sono
modellati con una distribuzione geometrica rispettivamente con media 5 e 25. Il reading
time e il tempo di interarrivo dei datagrammi in una packet call sono modellate con
distribuzioni esponenziali aventi media 412 sec. e 0,5 sec. rispettivamente.
In questo modo il modello si riconduce ad un processo a due stati (Fig. 3.8).
104
)LJ: Modello a due stati per traffico dati.
7UDIILFRPXOWLPHGLDOH
Una sorgente multimediale è la composizione di più sorgenti monomediali correlate tra
di loro. Per la definizione di un modello di sorgente multimediale non solo si devono
modellare le singole sorgenti monomediali, come illustrato nei paragrafi precedenti, ma
devono essere definite in maniera analitica anche le correlazioni che intercorrono tra queste.
105