07S - Reti di Code

Corso di Laurea Triennale in INGEGNERIA GESTIONALE
Anno Accademico 2012/13
MODELLI E METODI PER L’AUTOMAZIONE
Prof. Davide GIGLIO
RETI DI CODE
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
1
INDICE
RETI DI CODE MARKOVIANE APERTE
★ Modello di Jackson
RETI DI CODE MARKOVIANE CHIUSE
★ Modello di Gordon e Newell
★ Metodo di Denning e Buzen
METODI APPROSSIMATI PER RETI DI CODE NON MARKOVIANE
★ Mean Value Analysis (MVA)
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
2
RETI DI CODE MARKOVIANE
★ Le reti di code markoviane sono sistemi costituiti da più sistemi coda,
ciascuno di essi caratterizzato da servitori con tempi di servizio con
distribuzione esponenziale
★ Nelle reti di code aperte sono consentiti arrivi dall’esterno: in questo
caso i tempi di interarrivo dei clienti (dall’esterno) sono supposti
caratterizzati da una distribuzione esponenziale
★ Nelle reti di code chiuse non sono consentiti arrivi dall’esterno (vi è un
numero costante di clienti che circola nel sistema)
★ I modelli di reti di code markoviane più utilizzati sono
• modello di Jackson (modello di rete aperta)
• modello di Gordon-Newell (modello di rete chiusa)
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
3
RETI DI CODE MARKOVIANE
★ L’ipotesi di markovianità è in realtà troppo restrittiva e rende di fatto
poco realistica l’applicazione delle reti di code markoviane (e dei
risultati ad esse relativi) in diversi ambiti applicativi come, ad esempio,
quello dei processi manifatturieri
★ Tuttavia questi modelli, anche se non completamente congruenti con le
caratteristiche di un sistema reale, possono essere utilizzati in una prima
fase di progetto per il dimensionamento di massima del sistema,
sfruttando l’efficienza computazionale che li contraddistingue (se
paragonati all’impiego di tecniche basate sulla simulazione)
★ Una volta determinato, di regola dopo una serie di tentativi, tale
dimensionamento, deve comunque essere effettuata una verifica di tipo
simulativo, tenendo presenti tutte le caratteristiche del sistema reale
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
4
MODELLO DI JACKSON
Il modello di Jackson di rete di code aperta è definito nel modo seguente
1. I clienti appartengono tutti alla stessa classe
2. La rete di code è composta da N nodi ciascuno corrispondente ad una
singola coda con un insieme di servitori identici in parallelo
Sia mi il numero di servitori del nodo (macchina) i -esimo
3. Il tempo di servizio di ciascuno dei servitori del nodo i -esimo è una
variabile aleatoria distribuita in modo esponenziale
(con parametro µi )
4. In un certo numero di nodi della rete ha luogo il processo di arrivo dei
clienti dall’esterno; ciascuno di tali processi è un processo di Poisson
Sia
i
il parametro che caratterizza il processo degli arrivi al nodo i
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
5
MODELLO DI JACKSON
5. Dopo aver completato il servizio presso il nodo i-esimo, ciascun cliente può:
• essere trasferito ad un altro nodo j (eventualmente j = i ), con
tempo di trasferimento nullo, con probabilità ri,j
• uscire dal sistema, con probabilità ri,0
E’ così definito il processo di instradamento. Naturalmente deve essere
ri,0 +
N
X
ri,j = 1
i = 1, . . . , N
j=1
6. I buffer delle linee di attesa ad ogni nodo hanno dimensione infinita
7. Tutti i processi stocastici (di arrivo, di servizio, di instradamento)
corrispondono a sequenze di variabili aleatorie indipendenti e
identicamente distribuite (i.i.d.); i processi stocastici suddetti sono
inoltre a due a due mutuamente indipendenti
8. La popolazione complessiva dei clienti è infinita
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
6
MODELLO DI JACKSON
★ Nel modello di Jackson, il processo complessivo degli arrivi al nodo
i -esimo (comprendendo quindi gli arrivi provenienti dall’esterno e quelli
provenienti dall’interno) è un processo stocastico caratterizzato da un
rate di arrivi medio dato da
⇤i =
i
+
N
X
j=1
ej
rj,i ⇤
e j il rate di uscite medio dal nodo j
essendo ⇤
★ In condizioni di equilibrio stocastico, il rate di arrivi medio in ingresso
e quello in uscita saranno uguali per ogni nodo
ei
⇤i = ⇤
i = 1, . . . , N
★ Si ha pertanto l’equazione di bilancio dei flussi
⇤i =
i
+
N
X
rj,i ⇤j
j=1
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
7
MODELLO DI JACKSON
★ L’equazione di bilancio dei flussi
⇤i =
i
+
N
X
rj,i ⇤j
j=1
scritta per ogni nodo i , costituisce un sistema lineare di N equazioni in
N incognite
★ Tale sistema può essere risolto allo scopo di determinare il rate di arrivo
medio (complessivo) di ogni nodo
★ In tutti i nodi in cui non vi sono arrivi dall’esterno si avrà
i
=0
★ Inoltre, è evidente che, in condizioni di equilibrio stocastico, il rate di
arrivo medio coinciderà con il flusso medio dei clienti, per il nodo
considerato
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
8
TEOREMA DI JACKSON
✹ TEOREMA ✹
Sia data una rete di code aperta corrispondente al modello di Jackson. Si
risolva allora il sistema costituito dalle equazioni di bilancio dei flussi,
determinando le quantità ⇤i , i = 1, . . . , N . Se risulta
⇤i
mi µi
<1
8 i = 1, . . . , N
allora il sistema può essere rappresentato con una CTMC irriducibile
con tutti gli stati ricorrenti positivi
La distribuzione di probabilità a regime dello stato è data da
⇡(n1 , n2 , . . . , nN ) = Pr{L1 = n1 , L2 = n2 , . . . , LN = nN } =
= ⇡1 (n1 ) · ⇡2 (n2 ) · . . . · ⇡N (nN )}
• Li è il numero di clienti presenti nel nodo i -esimo
• ⇡i (ni ) è identica alla distribuzione di probabilità dello stato a regime di
una coda M/M/mi , caratterizzata dai parametri ⇤i , µi e mi
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
9
TEOREMA DI JACKSON
Pertanto
⇡i (0) = "
⇡i (ni ) =
essendo ⇢i =
RETI DI CODE
1
1+
m
1
i
X
ni =1
(mi ⇢i )ni
ni !
8
ni
(m
⇢
)
i i
>
>
⇡ (0)
>
< i
ni !
mi
>
>
m
>
i
: ⇡i (0) i ⇢n
mi ! i
+
(mi ⇢i )mi
mi !
·
1
1
⇢i
#
ni = 1, 2, . . . , mi
ni
1
mi
⇤i
mi µi
MODELLI E METODI
PER L’AUTOMAZIONE
10
TEOREMA DI JACKSON
Il teorema di Jackson ha il seguente importante significato
★ In una rete di code aperta corrispondente al modello di Jackson, purché
sia soddisfatta la condizione di stabilità ⇢i = ⇤i /mi µi < 1 , il
sistema raggiunge una condizione di equilibrio stocastico in cui la
distribuzione di probabilità congiunta è caratterizzata da una “struttura
prodotto”, cioè da una struttura tale da risultare il prodotto di
distribuzioni di probabilità marginali (cioè relative ad un’unica variabile)
★ Inoltre, come si è visto, ciascuna di tali distribuzioni di probabilità
marginali corrisponde semplicemente alla distribuzione di probabilità a
regime di una coda M/M/mi
★ La possibilità di determinare la probabilità congiunta consente la
determinazione di diversi indici di prestazione caratterizzanti il
comportamento della rete di code aperta
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
11
MODELLO DI GORDON-NEWELL
Il modello di Gordon-Newell è identico al modello di Jackson,
se non per le ipotesi seguenti
1.
= 0 8 i , cioè non vi è alcun processo di arrivo dei clienti dall’esterno
(gli arrivi provengono tutti dai nodi della rete); inoltre ri,0 = 0 8 i , cioè i
clienti non possono lasciare il sistema una volta completato il servizio
su un certo nodo della rete
i
Ciò vuol dire che vi è un numero costante di clienti nel sistema (dal punto
di vista pratico, quando un cliente completa il suo ciclo complessivo di
servizi, esso viene sostituito da un altro cliente che invece deve ancora
iniziare il suo ciclo)
2. La matrice di routing, il cui generico elemento è ri,j , non può essere
trasformata, attraverso semplici
permutazioni di riga e di colonna, in una

A | 0
matrice avente la struttura B
,
con
A e C sottomatrici quadrate
| C
Ciò vuol dire che non è possibile isolare una parte del sistema in cui i
clienti possono solo entrare, senza potere più uscire
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
12
TEOREMA DI GORDON-NEWELL
✹ TEOREMA ✹
Sia data una rete di code chiusa corrispondente al modello di GordonNewell. Il sistema può essere rappresentato con una CTMC irriducibile
con spazio degli stati finito. La cardinalità di tale spazio è
|S| =
✓
N +K
K
◆
1
=
✓
N +K 1
N
1
◆
dove K è il numero costante di clienti nella rete di code chiusa
Esiste pertanto una distribuzione di probabilità dello stato a regime che è
data da
N
Y
xi ni
⇡(n1 , n2 , . . . , nN ) = C
(ni )
i=1 i
essendo le funzioni i (ni ) date da
⇢
ni !
ni = 1, 2, . . . , mi
i (ni ) =
mi
i
mi ! mn
ni
mi
i
RETI DI CODE
1
i = 1, . . . , N
MODELLI E METODI
PER L’AUTOMAZIONE
13
TEOREMA DI GORDON-NEWELL
✹ TEOREMA ✹ (continuazione)
Le costanti xi sono determinate risolvendo (a meno di una costante
arbitraria) il sistema lineare omogeneo
µi xi =
N
X
i = 1, . . . , N
rj,i µj xj
j=1
La costante C è una costante di normalizzazione determinata come
1
C=
X
n2S
N
Y
i=1
xi ni
i (ni )
!
dove n = col(n1 , n2 , . . . , nN )
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
14
TEOREMA DI GORDON-NEWELL
★ La costante di normalizzazione ha la funzione di imporre che sia
X
⇡(n1 , n2 , . . . , nN ) = 1
n2S
indipendentemente dalla indeterminazione che caratterizza la risoluzione
del sistema lineare omogeneo che fornisce le
★ La determinazione della costante di normalizzazione richiede purtroppo la
determinazione completa dello spazio degli stati S , la cui cardinalità
può essere piuttosto elevata, anche per N e K non elevati
★ La distribuzione di probabilità congiunta fornita dal teorema di GordonNewell è ancora espressa in forma prodotto
★ Questa volta però i singoli fattori non sono distribuzioni di probabilità
marginali, in quanto le variabili aleatorie n1 , n2 , . . . , nN non possono
più essere considerate come variabili aleatorie indipendenti
(principalmente per il fatto che si ha un numero fisso di clienti)
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
15
TEOREMA DI GORDON-NEWELL
★ La probabilità marginale ⇡i (ni ) può comunque essere calcolata dalla
probabilità congiunta ⇡(n1 , n2 , . . . , nN )
⇡i (s) =
X
⇡(n)
n2⌘ i (s)
con
⌘ i (s) =
⇢
(n1 , n2 , . . . , nN ) :
N
X
ni = K , ni = s
i=1
★ Una volta determinate le probabilità marginali è possibile calcolare gli
indici di prestazione di interesse
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
16
MODELLO DI GORDON-NEWELL
★ La lunghezza di coda media del nodo i -esimo è data da
Lq i =
K
X
s ⇡i (s)
s=1
★ Il coefficiente di carico relativo al nodo i -esimo è sempre ⇢i =
⇤i
mi µi
che però non può essere calcolato direttamente non essendo disponibili
le quantità ⇤i (flussi in ingresso/uscita delle singole code)
★ Il coefficiente di carico corrisponde però a 1 ⇡
˜ i (0) , dove ⇡
˜ i (0) è la
probabilità che un generico servitore nel nodo i -esimo sia inattivo in
un istante selezionato a caso (in condizioni di equilibrio stocastico)
★ La quantità ⇡
˜ i (0) può sempre essere ricavata dalla distribuzione
marginale ⇡i (ni )
˜ i (0) = ⇡i (0)
• se mi = 1 si ha ⇡
˜ i (0) = ⇡i (0) + 1/2 · ⇡i (1)
• se mi = 2 si ha ⇡
˜ i (0) = ⇡i (0) + 2/3 · ⇡i (1) + 1/3 · ⇡i (2)
• se mi = 3 si ha ⇡
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
17
MODELLO DI GORDON-NEWELL
★ Una volta note le quantità ⇡
˜ i (0) è possibile calcolare i coefficienti di
˜ i (0) e quindi i flussi ⇤i
carico ⇢i = 1 ⇡
★ Dal punto di vista pratico è sufficiente determinare una sola delle quantità
⇤i , i = 1, . . . , N , per determinarle tutte sulla base della risoluzione del
sistema lineare omogeneo
N
X
⇤i =
rj,i ⇤j
i = 1, . . . , N
j=1
che è risolubile a meno di una costante arbitraria
★ Una volta determinato l’insieme delle ⇤i , i = 1, . . . , N , è immediato
calcolare il throughput dell’intero sistema. Esso infatti deve essere
inteso come il flusso in uscita dal sistema dei clienti per cui è stato
completato il ciclo dei servizi ovvero il flusso in uscita dalle macchine che
generano prodotti finiti
★ Essendo noto e costante il numero di clienti nel sistema, una volta
calcolato il throughput è immediato ottenere, con la legge di Little, il
tempo medio di permanenza nel sistema del generico cliente
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
18
METODO DI DENNING E BUZEN
★ Il bisogno di considerare l’intero spazio degli stati e i conseguenti
problemi computazionali nascono dalla necessità di calcolare la
costante di normalizzazione C
★ Il metodo di Denning e Buzen fornisce un modo operativo più efficiente
per il calcolo della costante di normalizzazione
★ Si consideri una rete di code markoviane chiusa che soddisfa il modello
di Gordon-Newell composta da risorse tutte monoserver
mi = 1
8 i = 1, . . . , N
★ E’ banale verificare che in questo caso risulta
i (ni )
=1
8 i = 1, . . . , N
★ Pertanto, la distribuzione di probabilità congiunta fornita dal teorema di
Gordon-Newell può essere scritta come
⇡(n1 , n2 , . . . , nN ) = C
N
Y
xi ni
i=1
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
19
METODO DI DENNING E BUZEN
★ Le costanti xi possono essere calcolate risolvendo (a meno di una
costante arbitraria) il sistema lineare omogeneo
N
X
µi xi =
rj,i µj xj
i = 1, . . . , N
j=1
(come specificato dal teorema di Gordon-Newell)
★ Tale sistema è analogo a quello che fornisce (per le reti di code chiuse e
sempre a meno di una costante arbitraria) i flussi ⇤i in ingresso ai vari
nodi della rete. Si può pertanto porre µi xi = ⇤i e quindi
xi =
⇤i
µi
i = 1, . . . , N
da cui
⇡(n1 , n2 , . . . , nN ) = C
N
Y
i=1
RETI DI CODE
✓
⇤i
µi
◆ni
MODELLI E METODI
PER L’AUTOMAZIONE
20
METODO DI DENNING E BUZEN
★ Per superare l’indeterminatezza dovuta alla risoluzione di sistemi lineari
omogenei, si consideri, tra le risorse del sistema quella che rappresenta la
macchina di carico/scarico
Si noti che se tale risorsa non è formalmente presente nel sistema, si può sempre
considerare una risorsa fittizia, con tempo di servizio nullo, che assume il ruolo
di macchina di carico/scarico
★ Per semplificare la notazione, sia la macchina di carico/scarico
rappresentata dal nodo “ 0 ” (a prescindere se corrisponde ad una
risorsa fisica o ad una risorsa fittizia) e siano le altre risorse del sistema
rappresentate, come prima, dai nodi da “ 1” a “N ”
Seguendo questa notazione, il numero di risorse complessive è quindi N + 1. Il
nodo “0” può corrispondere o meno ad una risorsa reale
★ Per come è stata definita, la macchina di carico/scarico è tale che tutti
i clienti passano una e una sola volta da essa
★ Inoltre, il flusso ⇤0 che attraversa tale macchina corrisponde al
throughput del sistema
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
21
METODO DI DENNING E BUZEN
★ Si considerino le equazioni di conservazione dei flussi, che possono
essere risolte a meno di una costante arbitraria
N
X
⇤i =
rj,i ⇤j
i = 0, 1, . . . , N
j=0
e si risolvano considerando il throughput ⇤0 come costante arbitraria
★ Tutti gli altri flussi nel sistema possono pertanto essere espressi come
⇤i = Vi ⇤0
i = 0, 1, . . . , N
dove il coefficiente Vi (“visit count”) è il valor medio della variabile
aleatoria “numero di passaggi di un cliente generico attraverso il
nodo i ”
Generalmente Vi assume valori positivi (sia minori che maggiori di 1); non è
esclusa la possibilità che Vi sia nullo
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
22
METODO DI DENNING E BUZEN
★ I visit count possono essere determinati a priori
★ Sulla base di quanto visto, dividendo l’equazione di conservazione dei
flussi per il throughput ⇤0 e considerando il fatto che dalla macchina di
carico/scarico i clienti passano una e una sola volta, si ottiene il seguente
sistema lineare non omogeneo
8
V0 = 1
>
>
<
N
X
>
rj,i Vj
>
: Vi =
i = 1, . . . , N
j=0
★ Si ha inoltre
xi =
Vi
µi
⇤0
i = 0, . . . , N
(se la macchina di carico/scarico è fittizia risulta x0 = 0 )
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
23
METODO DI DENNING E BUZEN
★ La distribuzione di probabilità congiunta diventa (considerando il nuovo
formalismo che include il nodo “0”)
⇡(n0 , n1 , . . . , nN ) = C
◆ni
N ✓
Y
Vi
i=0
µi
⇤0 ni = C ·
◆ni
N ✓
Y
Vi
i=0
µi
·
N ✓
i Y
Vi
n0
n1
nN
= C · ⇤0 · ⇤0 · . . . · ⇤0
·
µi
i=0
◆ni
N ✓
Y
Vi
K
= C ⇤0 ·
µi
i=0
h
N
Y
⇤0 ni =
i=0
◆ni
=
che può essere scritta come
⇡(n0 , n1 , . . . , nN ) = G(N, K) ·
N
Y
i=0
✓
Vi
µi
◆ni
in cui la costante G(N, K) è indipendente da (n0 , n1 , . . . , nN )
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
24
TEOREMA DI DENNING E BUZEN
✹ TEOREMA ✹
Con riferimento ad una rete di code chiusa, corrispondente al modello di
Gordon-Newell, in cui mi = 1 8 i = 0, . . . , N , la distribuzione congiunta
di probabilità dello stato a regime ⇡(n0 , n1 , . . . , nN ) può essere
espressa come
◆ni
N ✓
Y
Vi
⇡(n0 , n1 , . . . , nN ) = G(N, K) ·
µi
i=0
dove la costante G(N, K) può essere determinata attraverso il
procedimento ricorsivo
G(i, j) = G(i
1, j) +
Vi
µi
· G(i, j
1)
i = 1, . . . , N
j = 1, . . . , K
arrestato naturalmente ai valori i = N e j = K e inizializzato con
G(0, j) =
RETI DI CODE
✓
V0
µ0
◆j
8 j = 0, . . . , K
G(i, 0) = 1 8 i = 0, . . . , N
MODELLI E METODI
PER L’AUTOMAZIONE
25
TEOREMA DI DENNING E BUZEN
★ Il teorema di Denning e Buzen fornisce un metodo computazionalmente
assai efficiente per la determinazione della costante di normalizzazione
G(N, K)
HHH
★ La complessità della procedura iterativa che fornisce G(N, K) è
polinomiale
★ Non è più necessario determinare tutti gli stati del sistema per
ottenere la probabilità congiunta relativa ad un certo stato
★ La determinazione di G(N, K) richiede la preventiva determinazione
delle costanti Vi che dipendono da µi e da ri,j . Pertanto, è evidente
come la costante di normalizzazione dipenda da tali valori che
caratterizzano il sistema
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
26
METODO DI DENNING E BUZEN
★ Il throughput del sistema può essere espresso come
⇤0 =
G(N, K
1)
G(N, K)
★ La probabilità che nel nodo N vi siano h clienti è
⇡N (h) = Pr nN = h =
✓
VN
µN
◆h
·
G(N
1, K
h)
G(N, K)
Se si vuole conoscere la probabilità ⇡j (h) di avere h clienti in un altro
nodo j della rete, bisogna ricalcolare la costante G(N, K) considerando
il nodo j come ultimo nodo della rete (ovvero come “nodo N ”)
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
27
METODO DI DENNING E BUZEN
★ Il numero medio di clienti nel nodo i è
Lq i =
K
X
h ⇡i (h)
h=0
★ Il tempo medio di permanenza nel nodo i è
Tqi =
Lq i
⇤i
con ⇤i = Vi ⇤0
★ Il nodo “bottleneck” è il nodo i? per cui
µi?
Vi?
RETI DI CODE
=
min
i=0,...,N
⇢
µi
Vi
MODELLI E METODI
PER L’AUTOMAZIONE
28
METODO DI DENNING E BUZEN
Λ0 (K)
min
i=1,...,N
!
µi
Vi
"
K
THROUGHPUT IN FUNZIONE DEL NUMERO DI CLIENTI NEL SISTEMA
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
29
MEAN VALUE ANALYSIS (MVA)
★ E’ un metodo di analisi approssimato applicabile a reti di code chiuse
non markoviane
Essendo un metodo approssimato viene bene per effettuare un’analisi preliminare
delle prestazioni del sistema. I risultati dovranno poi essere validati attraverso
esperimenti simulativi
★ La mean-value-analysis (nella versione di Schweitzewr-Bard) si basa sulla
stima (approssimata) del tempo medio di attesa del cliente generico
al nodo i-esimo
★ Nell’ipotesi che tutti i nodi siano mono-server, tale tempo di attesa viene
stimato come pari a
Twi =
1
K
K
Lq i T s i
i = 1, . . . , N
in cui K è il numero complessivo (costante) di clienti nel sistema
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
30
MEAN VALUE ANALYSIS (MVA)
★ La scelta di questa stima è motivata dall’assunzione che il termine
(K 1)/K serva a “ridurre” la lunghezza di coda media Lq i del
fattore sufficiente ad impedire che si tenga conto dell’attesa del
servitore da parte del generico cliente (di cui si vuole stimare il tempo
medio di attesa) in una coda di cui esso fa parte
Questa approssimazione è totalmente euristica e non può essere in alcun modo
giustificata dal punto di vista analitico
★ Se si accetta questa approssimazione, diventa possibile stimare il tempo
medio complessivo di permanenza nel nodo i -esimo come
Tqi = Twi + Tsi
RETI DI CODE

K
= Tsi 1 +
1
K
Lq i
i = 1, . . . , N
MODELLI E METODI
PER L’AUTOMAZIONE
31
MEAN VALUE ANALYSIS (MVA)
★ Se si considerano i visit count, forniti dalla risoluzione del sistema
8
V
=
1
0
>
>
<
N
X
>
rj,i Vj
>
: Vi =
i = 1, . . . , N
j=0
(come nel metodo di Denning e Buzen), il tempo complessivo di
permanenza nel sistema può essere valutato come
⌧ =
N
X
Vi T q i
i=1
★ Ne consegue che, usando la legge di Little, il throughput del sistema
può essere calcolato come
⇤0 = K/⌧
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
32
MEAN VALUE ANALYSIS (MVA)
★ Noto ⇤0 possono essere determinati i flussi
⇤i = Vi ⇤0
i = 1, . . . , N
e quindi, sempre applicando la legge di Little, si possono ottenere le code
medie
Lq i = Vi T q i
i = 1, . . . , N
★ Si noti che la prima formula vista (stima del tempo medio di attesa nel
buffer) presupponeva la conoscenza della lunghezza di coda media Lq i ,
che però viene calcolata solo alla fine con l’ultima formula vista
★ Si può pertanto predisporre un algoritmo iterativo per l’analisi
(approssimata) delle prestazioni di una rete di code chiusa
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
33
MEAN VALUE ANALYSIS (MVA)
✹ALGORITMO✹ (Mean-Value-Analysis secondo Schweitzer-Bard)
STEP 1
Si inizializzano le code medie con i valori Lq i , i = 1, . . . , N
STEP 2
Si calcolano i tempi medi T q i , i = 1, . . . , N , sulla base delle Lq i , (per
mezzo della formula vista in precedenza)
STEP 3
Si calcola il throughput ⇤0 (facendo uso dei visit count, come visto in
precedenza)
STEP 4
Si calcolano nuove stime delle code
new
Lq i
= ⇤0 Vi T q i , i = 1, . . . , N
STEP 5
new
Lq i < ✏ , 8 i = 1, . . . , N , allora stop. Altrimenti
Se Lq i
new
Lq i
Lq i , i = 1, . . . , N , e si ritorna al passo 2
RETI DI CODE
si pone
MODELLI E METODI
PER L’AUTOMAZIONE
34
MEAN VALUE ANALYSIS (MVA)
★ Non vi è alcuna garanzia a priori sulla convergenza dell’algoritmo, né
sul livello di approssimazione della stima degli indici di prestazione
ottenuta in convergenza
★ Tuttavia, in letteratura sono riportate numerose applicazioni dell’algoritmo
nelle quali la convergenza si raggiunge abbastanza rapidamente
★ Inoltre, il livello di approssimazione delle stime ottenute è generalmente
buono rispetto alle stime accurate ottenibili mediante esperimenti
simulativi (l’errore di approssimazione è inferiore al 20%-30%)
RETI DI CODE
MODELLI E METODI
PER L’AUTOMAZIONE
35