Attività Formativa
Simulazione di una rete di
code aperta in ipotesi non
poissoniana
Gennaio 2008
Sommario
1
• Introduzione
2
• Ipotesi Poissoniana
3
• Modellizzazione
4
• Simulazione
5
• Risultati e conclusioni
Il sistema di servizio
Il processo degli arrivi
La coda
La distribuzione degli arrivi
Poisson
P( N (t )  k )  e
 t
Il servente
Il processo delle partenze
La distribuzione del tempo di servizio
( t ) k
k!
Esponenziale
f (t )  e t
t 0
Una rete di code è l’interconnessione di n sistemi di servizio
ciascuno costituito da uno o più serventi e da una coda
Arrivi dall’esterno
i
i
Pij
• Ogni nodo ha un tasso di arrivi dall’esterno (che in genere può
essere controllato o deciso) ed in più riceve i clienti che escono
dal servizio degli altri nodi.
• Il numero di clienti che effettivamente giungono al nodo i in un
intervallo di tempo dipende quindi dalla distribuzione del tempo
di servizio presso gli altri nodi.
• La rete si dice aperta se i clienti hanno una probabilità non nulla
di uscire definitivamente dal sistema, viceversa si dice chiusa.
Le reti di code aperte che hanno arrivi dall'esterno e tempi di
servizio poissoniani si dicono reti di Jackson.
Teorema di Burke: In una coda
con arrivi e tempi di servizio
poissoniani il processo delle
Gli arrivi effettivi a ciascun nodo partenze
sono è poissoniano con lo
poissoniani e si possono determinare in stesso
formaparametro di quello
arrivi
chiusa tutte le grandezze di interesse degli
per la
rete di code in condizioni stazionarie
Idea: ricondurre una rete generica ad una rete di Jackson per
avere una misura del comportamento in condizioni stazionarie
In tutti i casi in cui una rete di code NON è una rete di Jackson , per un
generico nodo i della rete di code non è possibile determinare la
distribuzione stazionaria  i
F
ˆi
i
i
P
i
ˆi
è la distribuzione approssimata sul nodo
P è un flusso poissoniano a tasso costante pari al tasso medio del flusso F
L’ipotesi poissoniana afferma che
ˆi   i
• L’ipotesi
poissoniana non è mai “letteralmente” vera ma vale
solo se si prende una sorta di limite termodinamico con un
gran numero di nodi
• La PH può essere provata per delle classi di distribuzioni dei
tempi di servizio che hanno dei momenti esponenziali finiti. In
pratica tali distribuzioni devono andare a zero almeno in modo
esponenziale
• Se le distribuzioni dei tempi di servizio non godono di tale
proprietà, allora la PH può essere provata solo per particolari
configurazioni iniziali della rete
La rete per rispettare la PH deve perdere la
sincronizzazione del dato iniziale
Possiamo rivedere il problema dell’esistenza di una distribuzione stazionaria
per una rete di code pensandola come un processo di Markov non lineare
Processo lineare a stati
finiti: catene di Markov
Associamo una
mappa P affine
coincidente con la
matrice di transizione
delle probabilità
Associamo un sistema dinamico
Processo non lineare
tempo continuo
d
 (t )  X (  (t ), b(  (t )))
dt
Punto fisso
P(  )  
La PH afferma
che il sistema
dinamico ha una
famiglia ad una
parametro di
punti fissi
dipendente da N
Tempo medio di servizio 1 sec
Alta probabilità che il tempo di
servizio > 1 min
Dopo un certo intervallo quasi
tutti i clienti saranno in attesa di
essere serviti dai nodi rossi
Alta probabilità che il tempo di
servizio
1h
PULSA RIMANENDO BLOCCATA
IN>MANIERA
CASUALE
LA RETE
Sbloccata la congestione sui nodi
E NON PREVEDIBILE SU ALCUNI NODI
rossi ci sarà un nuovo stallo su
quelli verdi
Perché si può presentare una situazione come quella prima descritta?
Intuitivamente il problema risiede nella distribuzione dei tempi di
servizio. In particolare se le distribuzioni hanno code “pesanti”
all’infinito c’è una probabilità non trascurabile che il tempo di servizio
assuma valori molto grandi creando congestione
Per distribuzioni
del tempo di
servizio del tipo
f (t ) 
1
N
n

t
 n
n 0
La PH è in generale violata
In verde si presenta l’andamento di una distribuzione di tipo esponenziale, in
rosso l’andamento di una distribuzione critica per il tempo di servizio
Se siamo di nuovo interessati a vedere il problema dal punto di vista della
stabilità del sistema dinamico, la violazione della PH comporta che nel sistema
prima descritto non esistano le seguenti quantità
La funzione di tasso di ingresso
(= funzione di tasso di uscita)
non ha limite
Lo stato non ha limite
lim
t 
lim
B , (t )
t
t 
Complessivamente quindi il sistema dinamico non ha una configurazione di
equilibrio per ogni stato iniziale
Al fine di costruire una rete che viola la PH in modo che sia evidente il
caratteristico pulsare della rete è quindi necessario
• Imporre che i nodi abbiamo una distribuzione del tempo di servizio con una
coda pesante all’infinito, come ad esempio l’inverso di un polinomio
• Fare in modo che la rete sia poco caricata dal traffico proveniente dall’esterno,
cioè che il fattore di utilizzazione sia piuttosto piccolo. Se la rete è di per sé troppo
carica si congestiona mascherando quindi l’effetto dovuto ai tempi di servizio
• Attendere un tempo di rilassamento che occorre alla rete per stabilizzarsi
• Considerare come pulsazioni attendibili solo quelle corrispondenti a grandi
congestioni, infatti piccole fluttuazioni sono presenti anche in reti rispettanti la PH
Obiettivo
• Creare una rete di code aperta che violi l’ipotesi poissoniana
• Evidenziare i meccanismi di congestione
tasso arrivi
SCEGLIERE
• non troppo elevato
• tale che ρ < 1.
Tipo di connessione
Numero Nodi
• sufficientemente grande da
permettere l’instaurazione di
una congestione
• rete totalmente /
parzialmente connessa
Obiettivo
• Creare una rete di code aperta che violi l’ipotesi poissoniana
• Evidenziare i meccanismi di congestione
tasso arrivi
SCEGLIERE
• λ = 0.0015
Tipo di connessione
Numero Nodi
• M = 20
• rete totalmente
connessa
Informazione servente
nodo.stato_servente: [M x 1 double]
Lunghezza coda
nodo.coda: [M x 1 double]
Lunghezza servizio
nodo.tempo_servizio: [M x 1 double]
Fine del servizio
nodo.fine_servizio: [M x 1 double]
M nodi
λ
Array di nodi
λ
Memorizzazione
dello stato della
rete ad ogni
istante di tempo
t.
Lunghezza code
Stato serventi e tempi di servizio
N
Numero nodi
• N = 20
Tasso arrivi esterni
• λ = 0.0015
Tempo di simulazione
• T = 20000
Tipo di rete
• Aperta interamente connessa
Indice di congestione
• Ic = 3
Inizializzazione rete
M = 20; T = 20000; λ = 0.0015;
nodo = zeros (M,1);
Ciclo temporale
for t = 1 : T
popolazione in ingresso
N = P(λ, M, 1)
Congestione
coda > Ic × CodaMedia
gestione ingressi
servente
libero
NO
• aggiornamento coda
SI
• aggiornamento coda
• calcolo tempo servizio
uscita
gestione termine servizio
t > fine_serv
servente occ.
SI
coda > 0
NO
• destinazione
• aggiornamento coda
SI
• calcolo tempo servizio
• destinazione
• aggiornamento coda
• servente libero
Visualizzazione
dinamica
Modellizzazione rete
• Codice flessibile
Pulsazione della rete
• visual.m Visualizzazione dinamica della rete
Risultati teorici e sperimentali
• Risultati sperimentali in accordo con gli studi
teorici presentati