Reti di code con struttura ad albero, teoria algoritmi e codice per la risoluzione

Introduzione
L’oggetto di questa tesi e` lo studio di una classe di modelli di sistemi dinamici ad
eventi discreti : le reti di code. Tali modelli rivestono una notevole importanza
in svariati campi applicativi che vanno dall’informatica, all’industria manufattu-
riera, alle comunicazioni, per la lora rapidita` e semplicta` di utilizzo che li rende
competitivi con i modelli simulativi piu` precisi ma piu` complicati e lenti. In que-
sto lavoro si e` analizzata una particolare classe di reti di code : le reti di code con
struttura ad albero a collegamenti bidirezionali. Lo studio e` stato svolto anche nel
caso in cui le stazioni siano a capacita` limitata. Per le reti di code con struttura a
stella composta e` stato sviluppato un codice che calcola le distribuzioni marginali
di tutte le code e la costante di normalizzazione.
Il primo modello di reti di code fu proposto da Jacskson [6], dove si analizzano
reti di code aperte a buffer illimitato, in cui gli utenti arrivano dall’esterno secondo
processi di Poisson, e i tempi di servizio sono distribuiti esponenzialmente.
Gordon e Newell in [3] estesero i risultati di Jackson considerando reti di code
chiuse . Sono state fatte varie estensioni di queste modelli, in particolare le code a
buffer limitato sono state studiate da Hordijk - Van Dijf [5] e da Yao - Buzacott in
[17]. Il concetto di reversibilita` fu introdotto da Kelly, che lo studio` diffusamente
in [7]. Kingman in [10] introdusse i processi migratori reversibili, ripresi da Pollet
in [13]. Il concetto di quasi reversibilita` fu introdotto algebricamente da Muntz in
[12] e probabilisticamente da Kelly in [7]. In letteratura non si trova uno studio
analitico generale di reti di code a capacita` limitata con truttura ad albero. Yao
- Buzacott [15] trattano le reti di code (a capacita` limitata) cosiddette a stella
semplice (albero a due livelli).
In questa tesi si considera il caso piu` generale di rete a capacita` limitata con
struttura ad albero qualsiasi. Se ne dimostra la reversibilita` e la forma prodotto
INTRODUZIONE
della distribuzione all’equilibrio, sotto di modellabilita` mediante catene di Mar-
kov, collegamenti bidirezionali, inoltre per reti aperte si suppone che gli utenti
possano entrare (dall’esterno) o uscire (verso l’esterno) attraverso una sola coda.
Nel capitolo 1 viene data una sintesi delle catene di Markov limitatamente a
quanti interessa i capitoli successivi e vengono introdotte le code e le reti di code.
Nel capitolo 2 viene studiata la reversibilita` e vengono forniti criteri di neces-
sita` e sufficienza.
Nel capitolo 3 viene esaminata la proprieta` di quasi reversibilita` e si prende
in considerazione il collegamento di reti di code quasi reversibili studiandone la
reversibilita` e la forma prodotto della distribuzione all’equilibrio.
Nel capitolo 4 si prendono in considerazione le reti di code a capacita` limitata
con struttura da albero.
Nel capitolo 5 viene studiato una particolare classe di catene di Markov : i
processi migratori. Viene ampiamente discussa la tecnica di interconnesione di
catene di Markov reversibili. Si dimostra la reversibilita` e la forma prodotto delle
reti con struttura a stella composta utilizzando anche il teorema di Pollet.
Nel capitolo 6 viene esposto un algoritmo che permette il calcolo della costante
di normalizzazione per reti di code a capacita` limitata.
In appendice si riporta il codice sviluppato per il calcolo delle distribuzioni
di probabilita` marginali e della costante di normalizzazione per reti a struttura
stellare composta.
Capitolo 1
PROCESSI DI MARKOV
1.1 Introduzione ai processi di Markov
Si consideri un processo aleatorio x(t) che assume valori in un insieme X per
t ∈ T . Si dice che x(t) e` un un processo aleatorio di Markov se ∀t, s ∈ T e
∀A ⊂ X gode dell proprieta` :
P [(x(s) : s ≥ t) ∈ A|x(s) : s ≤ t] = P [(x(s) : s ≥ t) ∈ A|x(t)] (1.1)
In un processo di Markov la probabilita` di un evento futuro, condizionato
dagli eventi passati e dal presente e` indipendente dagli eventi passati e dipende
solamente dall’evento presente. In altri termini lo stato presente, x(t), contine
tutta l’informazione riguardante la passata evoluzione del processo, che risulta
necessaria per prevedere la sua evoluzione futura.
In particolare, se X (insieme deli stati) e` numerabile , x(t) assume il nome di
catena di Markov, a tempo continuo se t ∈ T ⊆ < (insieme dei numeri reali), a
tempo discreto se t ∈ T ⊆ Z (insieme dei numeri interi).
Definizione : Una catena di Markov a tempo continuo si dice stazionaria in
distribuzione di ordine n se ∀t
1
, ...., t
n
, τ ∈ < e j
1
, ...., j
n
∈ X si ha:
P [x(t
1
) = j
1
, ...., x(t
n
) = j
n
] = P [x(t
1
+ τ) = j
1
, ...., x(t
n
+ τ) = j
n
] (1.2)
In particolare se una catena di Markov a tempo continuo e` stazionaria in di-
stribuzione di ordine n si ha che ∀j, k ∈ X e ∀t, τ ∈ < : P [x(t+ τ) = j|x(t) = k]
e` indipendente da t e dipende solamente da τ ( stazionarieta` in distribuzione di
CAPITOLO1.PROCESSIDIMARKOV
ordine due).
Definizione : Una catena di Markov, a tempo continuo, si dice omogenea se
∀t, τ ∈ <, τ ≥ 0 e ∀j, k ∈ X si ha che : P [x(t + τ) = j|x(t) = k] e` indipendente
da t.
Definizione : Data una catena di Markov, a tempo continuo,omogenea si
definisce tasso di transizione la seguente quantita` :
q(i, j) = lim
τ→0
+
P [x(t+ τ) = j|x(t) = i]
τ
(1.3)
∀i 6 =j ∈ X e ∀t, τ ∈ <
Si pone inoltre q(j) = 0 ∀j ∈ X e si impone che il limite dell’equazione (1.3)
sia finito. Si noti che la definizione di tasso di transizione e´ indipendente da t
poiche´ il processo e´ omogeneo.
Definizione : Data una catena di Markov, a tempo continuo, ed omogenea
si definisce rate matrix Q la matrice che ha per componenti i tassi di transizione
q(i, j). La rate matrix Q e` definibile poiche´ l’insieme degli stati X e` numerabile .
1.2 Evoluzione di una catena di Markov
Sia X un insieme numerabile, Q una rate matrix su X e pi
0
(i) ∈ X la probabilita`
che x(0) = i. La catena di Markov associata a Q inizialmente (t = 0) assume
valore x(0) = i con probabilia` pi
0
(i). Dopodiche` x(t) mantiene quel valore per un
tempo τ distribuito esponenzialmente con parametro q(i) =
∑
j∈X
q(i, j) (somma
della riga i-esima della matrice Q). All’istante τ il processo passa nello stato x(τ)
con probabilita` :
p(i, j) =
q(i, j)
q(i)
=
q(i, j)
∑
j∈X
q(i, j)
1(i 6 =j)
Le p(i, j) sono dette probabilita` di transizione mentre la funzione 1(C) vale
uno se C e` vera, zero altrimenti. A questo punto l’evoluzione ricomincia da
x(τ) indipendentemente da quanto successo prima (cioe` come se τ fosse l’istante
iniziale).
1.3.DISTRIBUZIONEINVARIANTE,LIMITEEALL’EQUILIBRIO
Il processo cos`ı definito e` una catena di Markov omogenea. La verifica si
ottiene direttamente sfruttando la cosiddetta mancanza di memoria della variabile
aleatoria esponenziale unilatera , e dal fatto che ,in ogni istante di transizione
, il nuovo valore viene scelto con una probabilita` che dipende solo dallo stato
precedente.
Si puo` dimostrare (Grimmett-Stirzaker) [4] che, data una catena di Markov
con rate matrix Q su X , la sua evoluzione e` quella precedentemente descritta.
1.3 Distribuzione invariante, limite e all’equili-
brio
Definizione : Una catena di Markov, a tempo continuo, si dice regolare se compie
un numero finito di transizioni in un tempo finito.
L’ipotesi di regolarita` e` necessaria per stabilire una corrispondenza biunivoca
tra la catena di Markov a tempo continuo e la sua rate matrix. Nel caso infatti
di infinite transizioni in un tempo finito la catena potrebbe essere reinizializzata
in un qualunque modo.
Definizione : Si definiscono inoltre le probabilita` :
P
t
(i, j) = P [x(t) = j|x(0) = i] ; ∀t > 0,∀i, j ∈ X
pi
t
(i) = P [x(t) = i] ; ∀i ∈ X
La probabilita` pi
t
(i) e` detta distribuzione invariante se e`indipendente dalla varia-
bile temporale t.
Il seguente teorema permette di calcolare il vettore riga pi
t
:
TEOREMA (1.1)
Siano (P
t
: t ≥ 0) le probabilita` di transizione di una catena di Markov a tempo
continuo regolare con rate matrix Q, si hanno i seguenti risultati :
a) P
t+s
= P
t
P
s
∀s, t ≥ 0
CAPITOLO1.PROCESSIDIMARKOV
b) d(P
t
)/dt = QP
t
= P
t
Q ∀t ≥ 0
c) Se Q e´ uniforme :
P
t
= e
Qt
=
+∞
∑
n=0
Q
n
t
n
n!
t ≥ 0
d) La distribuzione di probabilita` pi
t
non dipende da t se e solo se pi
0
e´ soluzione
delle equazioni piQ = 0, cioe` se e solo se ∀i ∈ X si ha :
pi(i)
∑
j∈X
q(i, j) =
∑
j∈X
q(j, i)
dimostrazione :
Si considera per semplicita` il caso in cui X sia un insieme finito.
a):
P [x
t+s
= j|x
0
= i] =
∑
k
P [x
t+s
= j, x
t
= k|x
0
= i] =
=
∑
k
P [x
t+s
= j|x
t
= k, x
0
= i]P [x
t
= k|x
0
= i] =
=
∑
k
P [x
t+s
= j|x
t
= k]P [x
t
= k|x
0
= i] =
=
∑
k
P [x
s
= j|x
t
= k]P [x
t
= k|x
0
= i] =
=
∑
k
P
s
(k, j)P
t
(i, k)
Quindi P
t+s
= P
t
P
s
.
b):
Si verifica inizialmente che d(P
t
)/dt = Q per t = 0. Assumendo che τ sia il primo
istante di transizione si ha :
P [x
t
= j|x
0
= i] = P [τ ≤ t|x
0
= i]P [x
τ
= j|x
0
= i] =
= (1− e
−t
∑
k
q(i,k)
)
q(i, j)
∑
k
q(i, k)
=
sviluppando in serie di e
−
∑
k
q(i,k)
e indicando con σ(t) una funzione infinitesima
per t −→ 0 con ordine di infinitesimo superiore al primo :
= q((i, j)t+ σ(t)
1.3.DISTRIBUZIONEINVARIANTE,LIMITEEALL’EQUILIBRIO
Quindi q(i, j) = d(P
0
(i, j))/dt. In base a quanto visto q(i, j)t e` a meno di infi-
nitesimi di ordine superiore, la probabilita` di passare da i a j in un tempo t, e
1 −
∑
k
q(i, j) e` la probabilita` di essere rimasti nello stato i dopo un tempo t (a
parte infinitesimi di ordine superiore). si ha quindi ( I matrice identita` ) :
P
t+²
= P
t
P
²
= P
t
[I +Q²+ σ(²)] == P
²
P
t
= [I +Q+ σ(²)]P
t
da cui, sottraendo P
t
e dividendo per ² si ottiene quanto si vuole dimostrare :
dP
t
dt
= QP
t
= P
t
Q
facendo tendere ² a zero.
c):
La si puo` verificare derivando il suo termine destro e vedendo che risolve l’equa-
zione del punto b). L’ipotesi di uniformita´ della matrice Q serve a garantire la
convergenza della serie.
d):
Se pi
0
Q = 0 , allora , poiche´ :
pi
t
= pi
0
P
t
pi
0
∞
∑
n=0
Q
n
t
n
n!
per il teorema della probabilita` totale , si ha che pi
t
= pi
0
.
Viceversa si suppone che pi
t
= pi
0
P
t
= pi
0
, allora derivando per t = 0 si ha proprio
la pi
0
Q = 0.
Si verifica per ultimo la stazionarieta` di x(t).
Per ogni insieme di realizzazioni A , abbiamo:
P [(x
t+s
: s ≥ 0) ∈ A] =
∑
i
P [x
t
= i]P [(x
t+s
: s ≥ 0) ∈ A|x
t
= i]
∑
i
pi
t
(i)P [(x
s
: s ≥ 0) ∈ A|x
0
= i]
Dunque se pi
t
= pi
0
, abbiamo che P [(x
t+s
: s ≥ 0) ∈ A] non dipende da t , dunque
la stazionarieta` . ( fine dimostrazione)
CAPITOLO1.PROCESSIDIMARKOV
Definizione : una catena di Markov a tempo continuo si dice irriducibile su
X (spazio degli stati) quando ∀t ∈ < ; j, k ∈ X esiste τ ∈ < tale che:
P [x
t+τ
= k|x
t
= j] 6 =0
cioe` quando ogni stato comunica direttamente o inderettamente con tutti gli altri
in un tempo finito.
Definizione : si dice distribuzione limite di una catena di Markov a tempo
continuo la quantita` :
lim
t→∞
P
t
(i, j) ; i, j ∈ X
TEOREMA (1.2):
Se una catena di Markov a tempo continuo regolare e irriducibile allora ha , se
esiste , una sola istribuzione invariante. In caso di esistenza tale distribuzione
coincide con la distribuzione limite cioe` :
lim
t→∞
P
t
(i, j) = pi
t
(j) ; i, j ∈ X
Definizione : si dice distribuzione all’eqilibrio di una catena di Markov , a
tempo , continuo un insieme di numeri positivi {pi(i)i ∈ X} che soddisfano alle
seguenti proprieta` :
pi(i) > 0 ∀i ∈ X
∑
i∈X
pi(i) = 1
pi(i)
∑
j∈X
q(i, j) =
∑
j∈X
pi(j)q(j, i) ∀i ∈ X (1.4)
L’equazione (1.4) e` detta equazione di bilancio all’equilibrio e stabilisce che il
flusso di tutte le transizioni entranti in i e` uguale al flusso di tutte le transizione
uscenti da i. Dalla definizione di distribuzione all’ equilibrio si deduce che se
esiste essa e` unica, dal teorema (1.1) (se la catena di Markov e` regolare) si deduce
che, sempre se esiste, essa coincide con la distribuzione invariante ( da cui la
stazionarieta` ).
1.4.CODASINGOL
Per il teorema (1.2) (sotto ipotesi di regolarita` e irriducibilita` ) la distribuzione
invariante coincide con la distribuzione limite. Quindi per catene di Markov a
tempo continuo regolari irriducibili se esiste la distribuzione all’ equilibrio essa e`
anche la distribuzione invariante e limite.
Nel corso della tesi si considereranno solo catene di Markov a tempo continuo
regolari irriducibili.
Le catene di Markov sono utilizzate per modellare , sotto opportune ipotesi,
sistemi dinamici come le code singole e le reti di code. Nei prossimi paragrafi si
introdurranno tali sistemi dinamici.
1.4 Coda singola
Si parla di coda singola ogni qualvolta si e` in presenza di utenti (possono essere
anche oggetti) richiedenti un servizio, erogato da una stazione fornitrice di tale
servizio. Se l’utente che si presenta alla stazione la trova occupata , si mette in
coda e attende che il servizio si liberi. Una volta completato il proprio servizio
l’utente esce dalla stazione di servizio.
Una coda e` formalmente definita quando si specificano :
- il processo degli arrivi ( la statistica secondo cui gli utenti giungono alla stazione
erogatrice di servizio)
- la distribuzione di probabilita` dei tempi di servizio (statistica secondo cui gli
utenti escono dalla stazione servente).
- disciplina di servizio (priorita` seguita)
Si e` soliti rappresentare una coda con la notazione :
A-B-s-disciplina
dove :