Modellazione di reti di telecomunicazioni: reti tandem con utenti negativi, perdite e bloccaggio.

utente positivo. In tal caso, l’utente negativo cancella un utente positivo.
Se il sistema è vuoto, l’utente negativo lascia il sistema. Un utente negativo
può eliminare o l’ultimo utente in coda o l’utente che sta ricevendo servizio.
Intuitivamente, la presenza degli utenti negativi fornisce un meccanismo di
controllo della congestione della rete. Utenti negativi possono modellare,
ad esempio, comandi che cancellano alcune transizioni in sistemi di com-
puter distribuiti o in databases, in cui alcuni tasks diventano impossibili
per bloccaggio di dati. Nelle reti neurali, gli utenti negativi e positivi rap-
presentano, rispettivamente, segnali inibitori e eccitatori per un neurone.
In questo contesto, si inserisce il lavoro di tesi che ha come obiettivo l’analisi
di una rete di code tandem caratterizzata da utenti negativi e feedback, con
disciplina di perdita e di bloccaggio.
La tesi è organizzata come segue.
Nella prima parte vengono richiamati concetti relativi ai processi stocastici,
in particolare a quelli markoviani. Si analizzano i sistemi a coda e le reti
di code aperte e chiuse, focalizzando l’attenzione sulle reti di code esponen-
ziali.
Nella seconda parte viene accuratamente descritta la rete di code tandem
con utenti negativi, perdite e bloccaggio. Per entrambe le discipline ven-
gono ricavate le equazioni di equilibrio, calcolate le probabilità stazionarie
e alcuni utili indici di prestazione.
Nella terza parte si analizzano le condizioni di ergodicità per la rete tandem e
vengono presentati risultati numerici. Infine, viene analizzata un’applicazione
ingegneristica del modello a code analizzato.
2
Parte I
Richiami
3
Capitolo 1
Processi stocastici e generalità
sui sistemi a coda
1.1 Processi stocastici
1.1.1 Catene di Markov
Definiamo processo stocastico una famiglia di variabili aleatorie {X (t)} che
sono definite su uno stesso spazio degli stati E,cont parametro a valori in
un sottoinsieme T ⊂ R
+
, detto insieme dei tempi.
Possiamo classificare quattro tipi di processi stocastici, a seconda delle carat-
teristiche di E e T :
• processo stocastico con stati discreti e con parametro tempo discreto:
T ⊆ N;
• processo stocastico con stati discreti e con parametro tempo continuo:
T ⊆ R;
• processo stocastico con stati continui e con parametro tempo discreto:
T ⊆ N;
4
• processo stocastico con stati continui e con parametro tempo continuo:
T ⊆ R.
Una sequenza di variabili aleatorie {X
n
: n=0, 1, 2, ...., X
n
∈ E} forma
una catena di Markov con spazio del tempo discreto se, per ogni n eper
ogni insieme {x
0,
x
1
, ..., x
n
} ⊂ E,risulta
P (X
n
= x
n
|X
n−1
= x
n−1
, ..., X
0
= x
0
)=P (X
n
= x
n
|X
n−1
= x
n−1
) .
Per definire completamente una catena di Markov, è necessario assegnare
un insieme p
jk
di probabilità condizionate (ovvero probabilità di transizione
del sistema dallo stato j allo stato k, essendo j lo stato attuale) e il vettore
di probabilità iniziale {a
k
}, che assegna la distribuzione di probabilità della
variabile aleatoria X
0
(a
k
indica la probabilità che il sistema sia inizialmente
nello stato k).
Le probabilità p
jk
possono dipendere dall’istante di osservazione n,ovvero
p
jk
= p
jk
(n) oppure essere costanti. In quest’ultimo caso, la catena è detta
omogenea.
Indichiamo con P =(p
jk
) lamatriceaventecomeelementilegeneriche
probabilità p
jk
.Pèdettamatrice di transizione ed è caratterizzata dalle
seguenti proprietà:
• p
jk
≥ 0: tali probabilità rappresentano le probabilità di transizione;
•
P
k
p
jk
=1, ∀j: questa sommatoria rappresenta la condizione di nor-
malizzazione sulla probabilità di transizione tra gli stati dello spazio
E.
5
Per le proprietà appena elencate, la matrice P è stocastica
1
.
E’ possibile, inoltre, definire le probabilità di transizione in m passi, sulla
base della definizione data per le probabilità di transizione in un solo passo.
Si può porre
P (X
n+m
= j|X
n
= i)=p
(m)
ij
,conm>0,
dove p
ij
= p
(1)
ij
,esiponep
(0)
ij
= δ
ij
,doveδ
ij
èilsimbolodiKronecker.
Teorema 1.1 .1 La probabilità p
(m)
ij
di passare dallo stato i allo stato j in m
passi è espressa dalla somma su tutti i possibili stati r ∈ E della probabilità
di passare in m−1 passi dallo stato iniziale i allo stato intermedio r edallo
stato r allo stato finale j:
p
(m)
ij
=
X
r∈E
p
(m−1)
ir
p
rj
.
In generale, spezzando il percorso in un punto qualsiasi k, con 0 ≤ k ≤ m,
si ottiene l’identità di Chapman Kolmogorov:
p
(m)
ij
=
X
r∈E
p
(m−k)
ir
p
(k)
rj
.
In notazione matriciale, l’identità di Chapman Kolmogorov si scrive nella
forma:
P
(m)
= P
(m−k)
·P
(k)
.
1
Una matrice quadrata P =(p
ij
) èdettamatrice stocastica se ciascuna delle sue righe
è un vettore di probabilità, ovvero se:
• ciascun elemento della matrice è non negativo;
• la somma degli elementi di ciascuna riga è pari ad uno.
6
Ponendo k = m− 1, si ottiene
P
(m)
= P ·P
(m−1)
,
da cui iterando, si ha
P
(m)
= P ·P ·P ···P = P
m
.
La probabilità condizionata di essere nello stato j al passo n viene indicata
come
P (X
n
= j)=p
(n)
j
,
e quindi la distribuzione iniziale delle probabilità sarà indicata con p
(0)
j
.
Chiamato p
(m)
il vettore riga
n
p
(m)
j
o
, è semplice osservare che
p
(m)
= p
(m−1)
·P,
da cui, per iterazione, è possibile concludere che
p
(m)
= p
(1)
·P
m
.
Ques’ultima espressione permette di esprimere il vettore di probabilità di
transizione in m passi in funzione della probabilità p
(1)
di transizione in un
singolo passo.
In forma ancora più generale, si può scrivere
p
(n+m)
= p
(n)
·P
m
Dalle ultime tre relazioni, che evidenziano i legami tra le probabilità di
transizione in più passi, è possibile concludere che, in genere, una catena
di Markov è non stazionaria anche quando è omogenea; in altri termini,
l’omogeneità è solo una condizione necessaria per la stazionarietà. Tuttavia,
7
se la distribuzione di partenza è la soluzione π, supposta esistente, del
sistema omogeneo
π = π ·P,
soddisfacente i vincoli
π
i
≥ 0;
X
i
π
i
=1,
allora la distribuzione degli stati non varierà nel tempo e quindi la catena è
stazionaria. Il vettore π definisce la distribuzione stazionaria della catena.
1.1.2 Processi di Markov
Dato il processo stocastico {X (t),t≥ 0} con valori nello spazio E discreto
e parametro tempo continuo, si possono introdurre le seguenti notazioni:
p
j
(t)=P (X (t)=j)
che indica la probabilità che il processo, all’istante t, si trovi nello stato j;
p
ij
(t
1
,t
2
)=P (X (t
2
)=j|X (t
1
)=i)
la probabilità di transizione dallo stato i all’istante t
1
allo stato j all’istante
t
2
>t
1
.
Si può anche fare riferimento alla probabilità
p
ij
(t)=P (X (t+ s)=j|X (s)=i) ,
ovvero alla probabilità di transitare dallo stato i allo stato j nell’intervallo
t.
Il processo {X (t),t≥ 0} viene detto processo di Markov tempo continuo
8
se, assegnati gli istanti temporali t
1
,t
2
, ..., t
n+1
, tali che
0 ≤ t
1
<t
2
< .... < t
n+1
,
risulta:
P {X (t
n+1
)=j|X (t
1
)=i
1
,X(t
2
)=i
2
, ...,X(t
n
)=i
n
} =
= P {X (t
n+1
)=j|X (t
n
)=i
n
} .
Si considerino gli stati del processo in tre istanti di tempo consecutivi 0 ≤
s<t<u: X (u)=j, X (s)=i. In tal caso, risulta valida l’identità di
Chapman-Kolmogorov estesa al caso tempo-continuo:
p
ij
(s, u)=
X
r∈E
p
ir
(s, t) p
rj
(t, u) , ∀t ∈ (s, u) .
In forma matriciale, si ha
P (s, u)=P (s, t) ·P (t, u) .
Se le probabilità di transizione p
ij
(s, u) dipendono solo dalla differenza
∆t = u − s, il processo è detto omogeneo e le probabilità vengono indi-
cate semplicemente con p
ij
(∆t) .
La distribuzione iniziale delle probabilità verrà indicata con p
j
(0). Detto
p (t)={p
j
(t)} il vettore riga di componenti p
j
(t),sihache
p (t+∆t)=p (t) ·P (∆t) .
Sottraendo p (t) ad entrambi i membri di quest’espressione, e dividendo per
∆t,siottiene
p (t+∆t)− p (t)
∆t
= p (t) ·
(P (∆t)− I)
∆t
.
9
Facendo tendere ∆t a zero, e ponendo
Q = lim
∆t→0
(P (∆t)− I)
∆t
,
si ottiene
p
0
(t)=p (t) ·Q. (1.1)
La matriceQ è degenere e la somma degli elementi di una sua riga è zero. Gli
elementi q
ij
della matrice intensità Q vengono dette frequenze di transizione
dallo stato i allo stato j.Talielementisonoparia
q
ij
=





lim
∆t→0
p
ij
(∆t)
∆t
,i6= j
lim
∆t→0
p
ij
(∆t)− 1
∆t
,i= j
;
per un generico elemento fuori dalla diagonale, si ha che
p
ij
(∆t)=q
ij
·∆t+ o (∆t),i6= j.
Da questa relazione, appare evidente che una transizione da uno stato i ad
uno stato j avviene in un tempo distribuito esponenzialmente con frequenza
media q
ij
,ilchenegiustifica il nome.
In generale, una rappresentazione semplice ed intuitiva dei processi di Markov
è fornita dai diagrammi delle frequenze di transizione.
Un esempio di diagramma delle frequenze di transizione è riportato nella
figura che segue.
10
Figura 1-1.
1.1.3 Asintoticità dei processi di Markov continui
Per quanto riguarda i processi di Markov tempo continui, dire che esiste
una distribuzione stazionaria di probabilità significa che la variazione delle
probabilità dei vari stati, dopo che è trascorso un tempo estremamente
lungo, è nulla. Quindi, la distribuzione stazionaria di probabilità, se esiste,
deve soddisfare la condizione
p
0
(t)=0.
Imponendo tale condizione nella (1.1), si ottiene che la distribuzione di
probabilità stazionaria, indicata con il vettore riga π, è soluzione del sistema
lineare omogeneo
π ·Q =0. (1.2)
Poichè la matrice Q è singolare, il sistema (1.2) risulta indeterminato. Di
conseguenza, per trovare una soluzione unica, bisogna aggiungere la con-
dizione di normalizzazione
X
j∈E
π
j
=1. (1.3)
I concetti di stazionarietà e regime validi per le catene di Markov a para-
metro tempo discreto restano validi per le catene a parametro tempo con-
11
tinuo, con la sola differenza che l’indice discreto n va sostituito con la va-
riabile continua t.
La determinazione diretta dell’esistenza di una condizione limite (o di regime)
risulta, in questo caso, più complessa, dal momento che comporta la risoluzione
del sistema di equazioni differenziali (1.1) e poi il controllo dell’esistenza
del lim
t→∞
p (t). Una volta che si è accertata l’esistenza di questo limite, la
distribuzione limite risulterebbe comunque uguale a quella ricavata dalla
risoluzione del sistema (1.2).
La ricerca dell’esistenza di una distribuzione limite attraverso le succes-
sive moltiplicazioni della matrice P, nel caso discreto, o con la soluzione di
un sistema di equazioni differenziali, nel caso continuo, è sicuramente un
procedimento complesso. Una volta nota l’esistenza, l’individuazione della
distribuzione limite risulta, invece, molto più semplice, visto che comporta
solo la soluzione di un sistema di equazioni. Appare, quindi, conveniente,
trovare delle tecniche alternative per accertare l’esistenza della distribuzione
limite.
1.1.4 Bilancio dei flussi
Un metodo veloce per ottenere direttamente le equazioni necessarie per de-
terminare la distribuzione di probabilità stazionaria di una catena di Markov
a tempo continuo consiste nell’usare il concetto di flussi di probabilità.
Si definisce flusso di probabilità in uscita da uno stato la somma (su tutti
i possibili stati destinazione) dei prodotti della probabilità stazionaria di
essere in tale stato origine per la frequenza totale con cui tale stato viene
abbandonato; analogamente, si definisce flusso di probabilità in ingresso in
uno stato la somma (su tutti i possibili stati origine) dei prodotti della pro-
babilità di essere in uno stato da cui è permessa la transizione allo stato
destinazione in esame per la frequenza con cui la transizione avviene. Con
12
riferimento al diagramma delle frequenze di transizione in Figura 1-2, ed in
particolare allo stato i,iflussi uscenti sono dati da
φ
u
= π
i
(λ
i
+ µ
i
)
mentre i flussi entranti sono definiti come
φ
e
= π
i−1
λ
i−1
+ π
i+1
µ
i+1
.
Figura 1-2.
La condizione di equilibrio statistico è espressa dall’uguaglianza di tali flussi.
Si noti che tale condizione è una diretta conseguenza della soluzione del si-
stema (1.2). Consideriamo, infatti, la j−sima equazione, esplicitando il
termine j−simo, ovvero
X
i6=j
π
i
q
ij
+ π
j
q
jj
=0.
Ricordando che la matrice Q harigheasommanulla,sihache
q
jj
= −
X
i6=j
q
ij
13
e sostituendo nell’espressione precedente, si ottiene
X
i6=j
π
j
q
ji
=
X
i6=j
π
i
q
ij
. (1.4)
Tale relazione esprime il bilancio tra il flusso in ingresso nello stato i eil
flusso in uscita dallo stesso stato.
Se si aggiunge ad entrambi i membri dell’equazione (1.4) il termine π
j
q
jj
,
si ottiene una maniera alternativa per scrivere l’equazione di bilancio dei
flussi, ovvero
X
i
π
j
q
ji
=
X
i
π
i
q
ij
. (1.5)
L’equazione di bilancio può essere ancora riformulata, selezionando sottoin-
siemidistati.ChiamatoA ⊂ E un sottoinsieme dell’insieme degli stati, se
si sommano le equazioni (1.5) prendendo tutti i nodi j ∈ A, si ottiene
X
j∈A
X
i
π
j
q
ji
=
X
j∈A
X
i
π
i
q
ij
e dividendo la sommatoria su i in due parti, una contenente gli stati interni
ad A e l’altra quelli esterni, si ottiene
X
j∈A
X
i∈A
π
j
q
ji
+
X
j∈A
X
i/∈A
π
j
q
ji
=
X
j∈A
X
i∈A
π
i
q
ij
+
X
j∈A
X
i/∈A
π
i
q
ij
.
Scambiando il nome degli indici nella prima sommatoria del primo mem-
bro, si nota che essa è uguale alla prima del secondo membro. Quindi,
semplificando, si ottiene
X
j∈A
X
i/∈A
π
j
q
ji
=
X
j∈A
X
i/∈A
π
i
q
ij
, (1.6)
che esprime il bilancio dei flussi in ingresso e uscita da un insieme di stati
A all’equilibrio statistico.
Quindi, se nel diagramma delle frequenze di transizione viene tracciata una
14
qualunque curva che delimita un insieme A di stati o che, comunque, divide il
diagramma in due regioni, una indicata con A el’altraconA
c
(complemento
di A), è possibile applicare il principio di conservazione dei flussi anche
lungo questa curva, purchè il sistema sia in equilibrio.
Le equazioni di bilancio, qui dimostrate in maniera diretta, verranno riprese
con riferimento ai sistemi a coda, ed in particolare quando saranno studiare
nel dettaglio le reti di code tandem.
1.1.5 Ergodicità dei processi Markoviani
Gli stati i e j sono detti stati comunicanti se esistono t
1
> 0 e t
2
> 0 tali
che p
ij
(t
1
) > 0 e p
ji
(t
2
) > 0.Glistatii e j sono comunicanti se e solo se
p
ij
(t) > 0 e p
ji
(t) > 0 per ogni t>0.
Il processo di Markov {X (t) ,t≥ 0} èdettoirriducibile se tutti i suoi stati
sono comunicanti. Il processo di Markov è irriducibile se e solo se è tale la
catena di Markov ad esso associata.
Il processo di Markov {X (t) ,t≥ 0} èdettoergodico se esiste una distri-
buzione di probabilità {p
i
,i∈ E},p
i
> 0,i∈ E, tale che le probabilità di
transizione p
ji
(t) soddisfano la relazione limite
p
ji
(t) −→
t→∞
p
i
,i,j∈ E.
La distribuzione {p
i
,i∈ E} èdettadistribuzione limite (finale) del processo
{X (t) ,t≥ 0}.
L’ergodicità del processo di Markov, così come quella della catena, dipende
sostanzialmente dalle caratteristiche dell’insieme degli stati E, che può es-
sere finito o numerabile.
Esponiamo alcuni teoremi sull’ergodicità.
15