Capitolo 4 - Modelli a rete di code

Capitolo 4 - Modelli a rete di code

In questo capitolo viene presentata la classe dei modelli a rete di code che permettono una rappresentazione più dettagliata dei sistemi composti da un insieme di risorse interconnesse. Particolare attenzione è dedicata alla classe di modelli a rete di code in forma prodotto, per la quale nel prossimo capitolo presentiamo i principali algoritmi risolutivi. Tale classe di modelli riveste un ruolo fondamentale nell’applicazione di modelli stocastici per la valutazione delle prestazioni di sistemi sia per la bassa complessità computazionale di soluzione, e sia per l’ampio uso di tali modelli anche nello studio di sistemi complessi tramite metodi approssimati e/o modelli a sviluppo gerarchico.

4.1 Introduzione ai modelli a rete di code

Nel capitolo precedente abbiamo visto esempi di sistemi in cui ogni utente richiede un singolo servizio e tali sistemi vengono rappresentati da modelli a coda singola. La rappresentazione del sistema in tal caso avviene con una unica risorsa.

Quando invece il sistema è formato da un insieme di risorse a cui ogni utente può chiedere servizio una o più volte si possono utilizzare i modelli a rete di code. In tal caso la rappresentazione del sistema avviene con una rete di risorse.

Un modello a rete di code è costituito da un insieme di centri di servizio o nodi e ogni centro di servizio è formato da una coda e uno o più serventi. In Fig. 4.1, ad esempio, è illustrato un modello a rete di code composto da una sola coda ed m serventi che corrisponde al modello di sistema a coda singola, introdotto nel capitolo 3.

I modelli a rete sono classificati come:

• aperti: se sono ammessi arrivi ed uscite da/verso l’esterno, ovvero la popolazione nella rete non è costante

1 2

m coda

serventi utenti

Fig. 4.1 - Modello a coda singola ed m serventi -

• chiusi: se è costante il numero di utenti che circolano nella rete e non vi sono né ingressi né uscite dal sistema

• misti: se per alcuni utenti la rete è aperta e per altri è chiusa.

Nel caso di reti aperte e miste gli utenti che arrivano dall’esterno entrano nel sistema in un centro di servizio qualsiasi dove si accodano e ricevono servizio, al termine del quale escono dal centro, si dirigono verso un altro centro, o rientrano nello stesso centro o escono dalla rete. Nelle reti chiuse, invece, gli utenti rimangono indefinitamente nel sistema, essi sono costantemente in coda o in servizio presso un centro. Si assume che tutte le transizioni di utenti fra nodi siano istantanee.

Consideriamo l’applicazione dei modelli a rete di code per rappresentare un sistema, le sue componenti ed interazioni in accordo al livello di astrazione fissato nel processo di creazione del modello e agli obbiettivi dello studio, secondo lo schema introdotto nel capitolo 1. dove il nostro obbiettivo è la valutazione delle prestazioni del sistema.

Un modello a rete di code è definito da un insieme di centri di servizio, un insieme di utenti ed una struttura di interconnessione o topologia.

Dei centri di servizio (detti anche nodi, o stazioni) che rappresentano le componenti del sistema, si specifica:

• il numero

• le seguenti caratteristiche di ogni centro:

disciplina di coda ovvero di servizio numero di serventi

velocità del servente espressa in unità di servizio/unità di tempo.

Degli utenti che, ad esempio, rappresentano job, task in un sistema di elaborazione o pacchetti in un sistema di comunicazione, si specifica:

• il loro numero per reti chiuse e miste

• il processo di arrivo ad ogni centro per reti aperte e miste

• la domanda di servizio degli utenti ad ogni centro, espressa in unità di servizio

• le classi di utenti che individuano sottoinsiemi di utenti con le stesse caratteristiche.

La struttura di interconnessione fra i nodi o topologia rappresenta le possibili transizioni degli utenti fra i nodi e il comportamento, stocastico o deterministico, individuale e/o per classi di utente.

Nel seguito assumiamo che il modello abbia topologia probabilistica, considerando che quella deterministica è un caso particolare. In altri termini un utente si muove fra i nodi in accordo ad una distribuzione di probabilità.

Numeriamo i nodi della rete da 1 ad M. Un utente che ha completato il servizio al nodo i, si dirige (immediatamente) al nodo j, con probabilità pij ed esce dalla rete con probabilità pi0. Tali probabilità devono soddisfare la seguente relazione:

p_ij

j=1

∑

M ^{+pi0 =1 1≤i≤M.}

P = [pij], 1≤i,j≤M, è la matrice delle probabilità di diramazione (routing).

2 3 M

λ 1

…

(a)

λ 1

2

A

B

C

D A+1

p 12

p 1A

p 2B p

2A+1

p AC

p AD

(b)

1

2

3 4

5

6 λ2

λ3

λ4

λ6 λ1

(c)

Fig. 4.2 - Topologie di modelli a rete di code: (a) tandem ad M nodi, (b) struttura ad albero, (c) struttura a grafo aciclico -

Un modello a rete di code può essere rappresentato come un grafo orientato ed etichettato dove i nodi sono i centri di servizio e gli archi le possibili transizioni degli utenti fra i nodi e le etichette degli archi definiscono le probabilità di diramazione.

Esempio. In Fig. 4.2 sono rappresentate tre topologie di modelli a rete di code: (a) rete tandem ad M nodi, (b) rete con struttura ad albero, (c) rete aciclica.

Un modello a rete ha topologia aciclica se il grafo associato è aciclico.

Numerando opportunamente i nodi, la matrice di diramazione P è triangolare superiore.

Gli indici di prestazione del sistema valutati sulla base del modello a rete di code si distinguono in locali ad una risorsa e globali, ovvero relativi ad un insieme di risorse. Le Tabelle I e II mostrano le notazioni e le definizioni di alcuni indici di prestazione rispettivamente locali ad un nodo i e globali.

Indice Notazione

numero di utenti nel sistema ni

distribuzione di probabilità di ni Prob{ni=k}=πi(k), k≥0

valor medio di ni Ni= E[ni]

numero di utenti in coda wi

tempo di risposta tqi

valor medio di qi Ri= E[tqi]

tempo di attesa twi

utilizzazione (frazione di tempo in cui i serventi sono occupati)

Ui

throughput (numero medio di utenti serviti per unità di tempo)

Xi

Tabella I. Indici di prestazione locali al nodo i.

Indice Notazione

valor medio del numero di utenti nella rete N valor medio del tempo di risposta globale R tempo di passaggio dal nodo i al nodo j t(i,j)

utilizzazione totale U

throughput totale X

Tabella II. Indici di prestazione globali.

Notare che nel caso di reti aperte o miste o sottoreti di reti chiuse il numero totale di utenti nella rete è una variabile casuale, mentre in reti chiuse tale indice è costante ed è tipicamente un parametro.

Con l’uso di questa notazione il teorema di Little applicato all’intera rete viene espresso dalla equazione N=X R, mentre applicato ad un singolo nodo diviene Ni=XiRi.

4.2 Modelli a rete di code Markoviane

Definendo opportunamente lo stato della rete, è possibile associare, sotto particolari ipotesi, un processo stocastico Markoviano all’evoluzione temporale della rete. Un modello a rete di code si dice Markoviano se è rappresentabile da un processo stocastico di Markov. In tal caso l’analisi del modello può essere ricondotta a quella del processo associato. Il processo associato al modello è Markoviano se è soddisfatta la condizione di assenza di memoria del sistema, ovvero se è possibile definire uno stato del modello che raccoglie in sè tutta la storia passata. Il processo è a tempo continuo se la distribuzione del tempo di permanenza nello stato del modello è esponenziale, mentre è a tempo discreto se tale distribuzione è geometrica. Ciò spesso si riconduce nel modello di code ad assunzioni di esponenzialità sulla distribuzione dei tempi di arrivo e di servizio degli utenti.

Consideriamo un modello a rete di code rappresentabile da una catena di Markov (spazio degli stati discreto) a tempo continuo. Sia Q il generatore infinitesimale del processo e π il vettore delle probabilità stazionarie di stato, che, in condizioni di stazionarietà, si ottiene come soluzione del seguente sistema di equazioni di bilanciamento globale con la condizione di normalizzazione (si veda la sezione 2.3.2)

π Q = 0 π 1T = 1 (4.1).

Tipicamente lo stato del modello include il numero di utenti in ogni nodo. Dalla distribuzione stazionaria delle probabilità di stato è possibile derivare altri indici di prestazione del sistema.

Tuttavia è necessario considerare che, per modelli a rete di code anche molto semplici, lo spazio degli stati cresce in modo esponenziale con le dimensioni del modello (numero di nodi, di utenti e classi di utenti) rendendo questo metodo di analisi spesso intrattabile da un punto di vista computazionale. Inoltre anche le caratteristiche di topologia, discipline di servizio e distribuzioni di probabilità dei tempi di servizio possono portare ad una più complessa notazione di stato e di conseguenza aumentare ulteriormente la complessità della soluzione.

λ µ₁ µ₂

Fig. 4.3 - Modello a rete di code aperto a due nodi -

Nel caso di reti aperte, poi, lo spazio degli stati è infinito.

Si può quindi concludere che il metodo di analisi del modello a rete di code basato sul processo Markoviano sottostante è applicabile in pochi casi pratici, perché difficile dal punto di vista computazionale.

Tuttavia esiste una classe di modelli per la quale è possibile definire efficienti algoritmi risolutivi. Questi modelli vengono detti a rete di code in forma prodotto (o separabili) perché π è esprimibile con una forma chiusa come prodotto di funzioni degli stati dei singoli nodi.

Esempio. Consideriamo un modello a rete di code aperto illustrato in Fig.

4.3 con due nodi, topologia tandem, processo di arrivo di Poisson di parametro λ, tempo di servizio ai due nodi indipendenti distribuito esponenzialmente, rispettivamente con tassi µ1 e µ 2, e discipline di servizio FIFO.

Sotto queste ipotesi definiamo lo stato del sistema come (n1, n2) quando vi sono n 1 utenti nel nodo 1 ed n2 utenti nel nodo 2. Questo stato definisce il processo Markoviano associato {(n1(t), n2(t)) | t∈R0+}con spazio degli stati E = {(n1, n2) | ni≥0}e distribuzione stazionaria di stato è π(n1, n2). Lo spazio E e quindi il sistema (4.1) è infinito. Il diagramma degli stati del processo Markoviano associato è qui illustrato nella porzione iniziale:

0,0

1,0

2,0

0,1

1,1 0,2

λ

λ

λ λ λ

µ1

µ1 µ1

... ... ...

µ2

µ2 µ2

Per le ipotesi di indipendenza, il nodo 1 può essere analizzato indipendentemente dal nodo 2 ed è un sistema M/M/1 con parametri λ e µ 1, per cui, se è soddisfatta la condizione di stazionarietà, ρ1 = λ / µ 1 <1, possiamo scrivere

Prob{n1 = k } = ρ1k (1-ρ1) k≥0.

Consideriamo ora il nodo 2. Il processo di arrivo a tale nodo può essere caratterizzato sulla base del seguente teorema, illustrato in Fig. 4.4.

Teorema di Burke

Dato un sistema M/M/1 stabile con processo di arrivo di Poisson di parametro λ, il processo di partenza (di uscita) è anch’esso un processo di Poisson di parametro λ.

λ

Poisson ( ) exp Poisson ( )λ

Fig. 4.4 - Teorema di Burke -

La dimostrazione si basa sull’ipotesi di indipendenza dei processi di arrivo e di servizio [KAN 92].

In altre parole il processo di uscita ha le stesse caratteristiche del processo di arrivo.

E’ importante sottolineare che tale proprietà vale anche per sistemi M/M/m e M/G/∞.

Applicando tale teorema alla rete tandem, si osserva che anche il nodo 2 può essere analizzato isolatamente come un sistema M/M/1 con parametri λ e µ2, per cui possiamo scrivere:

Prob{n2 = k } = ρ2k (1-ρ2) k≥0, se ρ2 = λ / µ2 <1.

Inoltre, per la proprietà di indipendenza la probabilità congiunta di stato della rete si esprime come il prodotto delle probabilità marginali, ovvero:

π(i, j) = Prob{n1 = i } Prob{n2 = j } ∀(i, j)∈E con λ < min {µ1 µ2 }

È facile verificare che questa espressione soddisfa le equazioni di bilanciamento globale del processo date dalla formula (4.1).

Applicando il teorema di Burke e la proprietà di composizione e decomposizione di processi Poissoniani indipendenti (si veda la sezione 2.2) si ricava immediatamente la soluzione in forma chiusa per la classe di modelli a rete di code aperte con nodi con tempo di servizio esponenziale, servizi indipendenti, arrivi Poissoniani e topologia aciclica probabilistica. Notare che la topologia aciclica è necessaria per mantenere la proprietà di indipendenza necessaria nella composizione dei processi di Poisson.

Consideriamo una rete aciclica con M nodi. Sia γi il parametro del processo di Poisson di arrivo dall’esterno al nodo i, il parametro del processo di Poisson totale in ingresso al nodo i (1≤i≤M) può essere ottenuto risolvendo il sistema

λ_i = γ_i +

∑

j = 1 i-1

λ_j p

ji 1≤i≤M (4.2).

λ µ ^p

1-p

Fig. 4.5 - Sistema di coda con feedback -

Sotto le ipotesi date definendo n = (n 1, n2,…, nM) lo stato del sistema si associa alla rete un processo stocastico Markoviano con spazio degli stati E = { (n1, n2,…, nM) | ni≥0} e distribuzione stazionaria di stato π(n1, n2,…, nM). Se vale la condizione di stazionarietà, possiamo scrivere:

π (n₁, n₂, …, n_M) =

∏

i = 1 M

Prob_i {n_i} (4.3)

dove Probi{ni} = ρini (1-ρi) ni≥0, ρi = λi / µi <1, 1≤i≤M.

Questa classe di reti è un primo esempio di modelli di reti in forma prodotto.

La distribuzione congiunta π(n1, n2,…, nM) è esprimibile come prodotto delle distribuzioni relative ai singoli nodi analizzati come sistemi isolati di tipo M/M/1, dove il nodo i è un sistema M/M/1 con parametri λi e µi.

Dalla distribuzione di stato π si ricavano gli altri indici di prestazione, locali e globali, illustrati nelle Tabelle I e II.

Questo risultato si estende a modelli a rete con centri di servizio esponenziali e serventi multipli, analizzando ogni centro come un sistema M/M/m isolato, con parametri λi e µi.

Quando viene a cadere l’ipotesi di indipendenza dei processi, il teorema di Burke non si applica. Un esempio è il modello di rete con feedback, illustrato in Fig. 4.5. In tal caso, infatti, non vi è indipendenza nel sistema fra arrivi e servizi.

Esempio. Consideriamo la rete tandem con feedback illustrata in Fig. 4.6, con processo di arrivo di Poisson di parametro λ, nodi a servizio esponenziale rispettivamente di parametro µ1 e µ2. Un utente che esce dal nodo 2 lascia il sistema con probabilità p e con probabilità 1-p ritorna la nodo 1. (n1, n2) rappresenta lo stato del sistema ed E = { (n1, n2) | ni≥0} lo spazio degli stati e π(n1, n2) è la distribuzione stazionaria di stato.

λ µ₁ µ₂ ^p

1-p

Fig. 4.6 - Rete tandem con feedback -

La porzione iniziale del diagramma degli stati del processo Markoviano associato è il seguente:

0,0

1,0

2,0

0,1

1,1 0,2

λ

λ

λ λ λ

µ1

µ1 µ1

µ2p

µ2p µ2p

*

* *

* = µ2(1-p)

λ

Il numero medio di visite ad ogni nodo si può calcolare come: V1=V2= 1/p.

Ponendo ρi =Vi λ /µi, i=1,2 se ρi < 1 allora è ancora valida la soluzione espressa dalla formula (4.3) per la rete tandem senza feedback, ovvero:

π(n1, n2) = Prob1{n1} Prob2{n2} ∀(n1, n2)∈E Probi{ni} = ρini (1-ρi) i = 1, 2

È facile verificare che tale soluzione soddisfa le equazioni di bilanciamento globale (4.1) del processo. La soluzione è ottenibile come se il sistema fosse formato da due code M/M/1 indipendenti con parametri Vi λ e µi i=1, 2, mentre, in realtà, ciò è falso.

L'esempio illustra gli elementi chiave che portano alla definizione della classe delle reti in forma prodotto che introduciamo nel seguente paragrafo.

4.3Modelli a rete di code in forma prodotto

La classe dei modelli in forma prodotto è stata originariamente definita per reti aperte a classe singola con il teorema di Jackson [JAC 65] e per reti chiuse a classe singola con il teorema di Gordon-Newell [GN 67]. Tale risultato è stato successivamente esteso a reti aperte, chiuse, miste multiclasse dal teorema BCMP [BCM 75]. Introduciamo ora i tre teoremi.

4.3.1 Reti di Jackson

La classe dei modelli a rete di code di Jackson è formata da reti aperte, con centri di servizio esponenziali, arrivi Poissoniani e topologia probabilistica arbitraria indipendente dallo stato della rete [JAC 63].

Siano M i nodi della rete, dove il nodo i è composto da mi serventi con tempo di servizio esponenziale con parametro µi e disciplina di servizio FIFO. Il processo di arrivo dall’esterno al nodo i è di Poisson di parametro γi.

P = [pij] 1 ≤ i, j ≤ M è la matrice delle probabilità di diramazione fra i nodi, e pi0 = 1-

Σ

j pij la probabilità di completamento del servizio, ovvero la probabilità con cui un utente che ha completato il servizio al nodo i esce dalla rete.

Sia λi il tasso medio di arrivo totale al nodo i che si ottiene dalle seguenti equazioni di bilanciamento del traffico:

λ_i = γ_i +

∑

j = 1 M

λ_j p

ji 1≤i≤M (4.4).

Sia n = (n1, n2,…, nM) lo stato del sistema, E = NM lo spazio degli stati e π(n1, n2,…, nM) la distribuzione stazionaria di stato ottenibile, sotto ipotesi di stazionarietà, dalla soluzione delle equazioni (4.1) del processo Markoviano associato. Tuttavia non è necessario ricorrere a tale soluzione del processo in quanto si applica il seguente teorema:

Teorema di Jackson [JAC 63]

Se è soddisfatta la condizione di stazionarietà ρi = λi / mi µi <1 1≤i≤M

allora la distribuzione stazionaria di stato di una rete di Jackson si esprime come:

π (n₁, n

2, …, n

M) =

∏

i = 1 M

π_i (n

i) (4.5)

dove

πi(n) = πi(0) (mi ρi )n /n! 1≤n≤mi πi(n) = πi(0) mimi ρin /mi! n>mi e πi(0) è ottenuto dalla condizione di normalizzazione

Σ

n πi(n)=1.

La dimostrazione si ottiene per sostituzione dell’espressione (4.5) nelle equazioni di bilanciamento globale del processo Markoviano associato [JAC 63].

Sia ei = (0, 0,…, 1,…,0) il vettore unitario con tutte le componenti nulle eccetto l’i-esima componente a valore 1, δ(n) la funzione indicatrice così definita: δ(n) = 0 se

n=0, e δ(n) = 1 altrimenti, e ai(n) = min{n, mi}, 1≤i≤M. L’equazione di bilanciamento globale del processo Markoviano associato per lo stato n è definita come:

π(n) (

∑

i = 1 M

γ_i +

∑

i = 1 M

δ(n_i) µ_i a_i(n_i) ) =

∑

i = 1 M

δ(n_i) γ_i π(n - e_i) +

+

∑

i = 1 M

µi a_i⁽n_i+1) p

i0 π(n + e_i) + +

∑

i = 1 M

∑

j = 1 M

δ(n_j) µ_i a_i(n_i+1) p_ij π(n + e_i - e_j)

Sostituendo l’espressione (4.5) in tale equazione si verifica l’uguaglianza.

Notiamo che la rete si comporta come se fosse composta da nodi di tipo M/M/m indipendenti. La funzione πi è la soluzione del nodo i analizzato come un M/M/mi con parametri λi e µi. Tuttavia i nodi non sono indipendenti ovvero il teorema di Burke non si estende. La topologia di una rete di Jackson può contenere cicli ed il sistema di equazioni di traffico (4.4) è una estensione del sistema (4.2) introdotto per le reti acicliche, che ne diventa un caso particolare.

Notiamo che λi ottenuto come soluzione del sistema (4.4) è anche il throughput del nodo i.

Riassumendo l’algoritmo di analisi di un modello a rete di Jackson è schematizzato come segue:

1. soluzione dei sistemi di equazioni di traffico (4.4) per determinare λi 1≤i≤M;

2. valutazione di πi dalle formule del sistema M/M/mi per ogni nodo i, 1≤i≤M e valutazione di π sulla base della formula (4.5).

Notiamo che la soluzione dipende solo dai parametri medi del modello, tasso di arrivo e di servizio di ogni nodo: γi e µi e della topologia P.

Sono state proposte alcune estensioni delle reti di Jackson. Fra le più significative ricordiamo le seguenti [BCM 75, LAV 83, LAV 89, KAN 92] :

• Velocità di servizio dipendenti dallo stato, il tasso di servizio del nodo i può essere una funzione del numero di utenti del nodo stesso, ovvero µi(ni), ni ≥0, 1≤i≤M.

In tal caso la funzione µ ini nella formula (4.5) è sostituita dalla espressione

Π

1≤k≤N µi(k).

• Tasso di arrivo totale dipendente dalla popolazione della rete, si assume che tale funzione sia esprimibile come il prodotto di una funzione globale γ(N) dipendente dal numero totale di utenti nella rete N =

Σ

i ni

γi(N) = γ(N) p0i con

Σ

i p0i =1.

Nella forma prodotto per π si aggiunge la seguente produttoria:

Π

1≤k≤N γ(k).

• Una semplice forma di routing dipendente dallo stato ovvero una semplice forma di blocco. Assumiamo che il nodo i abbia capacità massima Bi (memoria finita), ovvero il numero di utenti sia limitato superiormente (n i ≤ Bi). Quando un job in arrivo al nodo i trova il nodo alla massima capacità (ni = Bi) prosegue immediatamente verso un altro nodo j, secondo le probabilità di routing pij. Lo spazio degli stati è modificato ed è ottenuto troncando lo spazio del modello senza vincoli; sul nuovo spazio si applica ancora la formula (4.4).

• Tasso di arrivo dipendente dallo stato per garantire una popolazione minima. Tale modello può rappresentare una forma di routing dipendente dallo stato.

Se la popolazione totale raggiunge una soglia minima N=N*, allora il movimento degli utenti viene modificato come segue:

P + [p10…pM0]^T[p01…p0M]

Lo spazio degli stati è definito come: E={(n1, n2,…, nM) | ni∈N, N*≤Σi ni}. La soluzione si ottiene come:

π(n₁,…,n

M) = C 1

∏

n = N * N - 1

γ(n)

∏

i = 1 M

gi(n

i)

dove N =

Σ

i ni, g_i(n) = e_iⁿ

/ ∏

s = 1 n

µi(s) , e_i = p_0i +

∑

j = 1 M

e_j p_ji 1≤i≤M e C è una costante di normalizzazione che garantisce

Σ

n∈E π(n) = 1.

4.3.2 Reti di Gordon-Newell

La reti di Gordon-Newell sono chiuse, con centri di servizio esponenziali, topologia probabilistica arbitraria indipendente dallo stato della rete [GN 67].

Siano M i nodi di tipo ./M/mi, dove il nodo i ha distribuzione di servizio esponenziale di parametro µi, mi serventi e disciplina di servizio FIFO. K utenti circolano costantemente nella rete in accordo alla matrice di diramazione P = [pij], 1≤i,j≤M tale che

Σ

j pij =1. Sia ei il tasso medio relativo di arrivo totale al nodo i, 1≤i≤M, ovvero la frequenza di visita, o throughput relativo del nodo i che si ottiene dalle seguenti equazioni di bilanciamento del traffico:

ei =

∑

j = 1 M

ej p

ji 1≤i≤M (4.6).

Tale sistema è non determinato, ovvero ha infinite soluzioni, per cui la sua soluzione porta all’introduzione di un fattore arbitrario.

Sia n = (n 1, n2,…, nM) lo stato del modello ed E={(n1, n2,…, nM) | 0≤ni≤K, 1≤i≤M,

Σ

i ni = K} lo spazio degli stati. La probabilità stazionaria di stato è espressa in forma prodotto nel seguente teorema.

Teorema di Gordon-Newell [GN 67]

La distribuzione stazionaria di stato per reti di Gordon-Newell si può esprimere come:

π(n₁,…,n

M) = C(K)

1

∏

i = 1 M

gi(n

i) (4.7)

dove gi(n) è la soluzione non normalizzata del nodo i risolto come un sistema M/M/mi, con parametri ei, µi definita come:

gi(n) = (miρi)n/ n! se 0≤n≤mi, gi(n) = min ρik /mi! se n>mi e C(K) è una costante di normalizzazione sulle probabilità data da:

C (K) =

∑

n ∈ Ε

∏

i = 1 M

g_i(n_i) (4.8).

La dimostrazione si ottiene per sostituzione della formula (4.7) nelle equazioni di bilanciamento globale (4.1) del processo Markoviano associato. L’equazione del processo per lo stato n ∈ E è così definita:

π(n)

∑

= 1 M

δ(n_i) µ

i a _i(n_i) =

∑

i = 1 M

∑

j = 1 M

π(n + e_i - e

j) δ(n_j) µ

i a

i(n

i+1) p

ij i

dove le funzioni δ e ai sono definite nella sezione 4.3.2. La costante C(K) è introdotta per eliminare il fattore arbitrario introdotto nella soluzione del sistema (4.6).

Notiamo che una rete di Gordon-Newell con tassi di servizio µi, 1≤i≤M e a topologia arbitraria è equivalente, dal punto di vista della distribuzione di probabilità di stato ad una rete con topologia ciclica con tassi di servizio µ' i = µiei, 1≤i≤M.

Esempio. Consideriamo la rete ciclica esponenziale con serventi singoli illustrata in Fig. 4.7. Essa costituisce un modello basilare per reti di comunicazione per rappresentare protocolli di tipo store and forward [SCH 87]. Supponiamo che i nodi abbiano tassi di servizio µ1,...,µM con distribuzione esponenziale e servente singolo. Consideriamo la soluzione del sistema (4.6) ei = 1, 1≤i≤M. Le funzioni gi si semplificano come segue:

gi(n) = (1/µi)n n≥0, 1≤i≤M.

Dalle formule (4.7) e (4.8) calcoliamo la distribuzione congiunta delle lunghezze di coda, π(n,) da cui si possono ricavare altri indici di prestazione quali ad esempio, throughput, numero medio di job nella rete, tempi medi di risposta e tempo medio di ciclo.

Altri esempi classici di reti chiuse esponenziali sono costituiti dal modello machine-repair e dal modello a servente centrale illustrati rispettivamente nelle Figure 4.8 e 4.9.

1 2

...

M

Fig. 4.7 - Rete ciclica -

1

K nodo 1

nodo 2

Fig. 4.8. - Modello machine-repair -

Nel modello machine-repair circolano K utenti, il nodo 1 ha K serventi e il nodo 2 un singolo servente. Assumiamo che entrambi i nodi abbiano distribuzione del tempo di servizio esponenziale. Il nodo 1 può essere anche visto come un nodo con infiniti serventi (si veda la sezione 3.2) poichè non si forma mai coda. Il nodo 2 ha disciplina di servizio FIFO. Sotto queste ipotesi il modello è una rete di Gordon e Newell e si applica il teorema.

Abbiamo già introdotto informalmente questo modello nell’esempio di valutazione di un sistema di elaborazione nel capitolo 1, Fig. 1.5.

Ad esempio un sistema di elaborazione di tipo time-sharing può essere rappresentato da questo modello. Il nodo 1 rappresenta un insieme di K terminali e il nodo 2 rappresenta il sistema che fornisce l’elaborazione. Il teorema di Gordon- Newell si applica anche se il nodo 2 ha distribuzione del tempo di servizio più generale (Coxiana, si veda la sezione 4.3.3) e disciplina di servizio PS, che permette di modellare la disciplina di tipo round robin basata su quanti di tempo. La valutazione del sistema sulla base del modello può essere utilizzata ad esempio per determinare il numero ottimo di terminali da collegare al sistema per garantire determinate prestazioni del sistema, ad esempio in termini di tempo medio di risposta.

Tale modello è utile anche per rappresentare un insieme di K macchine che operano indipendentemente e in parallelo, soggette a guasto e una sola persona (o macchina) per ripararle. Ogni macchina può essere

(i) in esecuzione

(ii) guasta ed in attesa di riparazione (iii) in riparazione.

Una macchina nel modello è rappresentata da un utente. Lo stato (i) è rappresentato dal servizio al nodo 1, lo stato (ii) corrisponde alla coda del nodo 2 e lo stato (iii) al servizio al nodo 2. In questo caso il modello a rete di code può essere applicato anche per valutare l'affidabilità del sistema, ad esempio in termini di tempo medio di

1

2

M p2

pM

p1

Fig. 4.9. - Modello a servente centrale -

riparazione (tempo medio di risposta del nodo 2), percentuale di utilizzo del riparatore (utilizzazione del nodo 2) e percentuale di macchine funzionanti (rapporto fra numero medio di utenti nel nodo 1 e numero totale di utenti).

Il modello a servente centrale è illustrato in Fig. 4.9. Nella rete circolano K utenti, i nodi hanno servente singolo, distribuzione del tempo di servizio esponenziale e disciplina di servizio FIFO. Il modello è una rete di Gordon e Newell.

Tale modello è stato introdotto per rappresentare la competizione dei programmi per il processore e per periferiche di I/O in un sistema di calcolo multiprogrammato [LAV 83]. I programmi sono rappresentato dagli utenti e K è il livello di multiprogrammazione. L'esecuzione di un programma sul processore è rappresentata dal servizio al nodo 1, mentre l’attività sulle periferiche è modellata dal servizio negli altri nodi. In particolare si assume quindi che l'esecuzione del programma sia costituita da una successione di segmenti di esecuzioni sul processore e sulle periferiche. Assumendo che il livello di multiprogrammazione sia costante e che vi siano sempre nuovi programmi da elaborare, la terminazione di un programma non cambia il modello se si ipotizza che immediatamente un nuovo programma inizi il suo ciclo di elaborazione.

Applicando il teorema per analizzare il modello possiamo valutare ad esempio l'utilizzazione delle componenti del sistema ed il tempo medio di risposta di un programma. Su tale base si può ad esempio determinare il livello di multiprogrammazione ottimo.

4.3.3 Reti BCMP

La classe dei modelli a rete di code BCMP [BCM 75] è una estensione delle due classi introdotte (Jackson e Gordon-Newell) ed è costituita da reti aperte, chiuse e

miste, multiclasse, con topologia probabilistica arbitraria e con centri di servizio del tipo illustrato in Tabella III.

Tabella III. Tipi di nodi di una rete BCMP.

La distribuzione di tipo Coxiana è definita come una arbitraria (generale) distribuzione con trasformata di Laplace razionale, rappresentabile con una rete di stadi esponenziali [KLE 75]. Esempi di distribuzioni rappresentabili con una Coxiana sono le distribuzioni esponenziale, iperesponenziale ed Erlagiana. Inoltre osserviamo che anche una distribuzione con trasformata di Laplace non razionale può essere rappresentata in modo approssimato con errore controllabile da una distribuzione Coxiana.

Consideriamo una rete formata da M nodi ed R tipi di utente.

Un tipo di utente caratterizza un insieme di utenti. Ogni tipo o catena è composto da un insieme di classi di utente. Ogni classe appartiene ad un nodo. Una classe consiste nella specifica del tempo di servizio e movimento degli utenti. L’insieme delle classi è partizionato in catene e Cr denota l’insieme delle classi della catena r.

Ogni utente di tipo r si muove nella rete fra le classi di Cr, 1≤r≤R. Con Cir si denota l’insieme di classi della catena r appartenenti al nodo i, e Cr = C1r ∪ C2r ∪…∪ CMr.

Un utente che ha completato il servizio al nodo i, in classe c si dirige al nodo j, classe d con probabilità pic;jd(r); oppure esce dalla rete con probabilità pic;0(r). La matrice delle probabilità di diramazione è definita per ogni catena r, 1≤r≤R, come:

P(r) = [ pic;jd(r) ] 1≤i,j≤M, c∈Cir d∈Cjr .

L’introduzione delle classi permette di realizzare forme di dipendenza del movimento degli utenti dal comportamento passato.

Tipo Disciplina di servizio Distribuzione del tempo di servizio

(1) FIFO esponenziale

(2) PS (Processor Sharing) Coxiana

(3) IS (Infiniti Serventi) Coxiana

(4) LIFOPr (LIFO con Prelazione)

Coxiana

µic(r) denota il tasso di servizio degli utenti al nodo i classe c della catena r. Per nodi di tipo (1) si assume che µic(r) = µ i ∀ c∈Cir, 1≤r≤R.

γic(r) denota il tasso di arrivo dall’esterno al nodo i classe c, catena r. Se γic(r) > 0 per qualche c∈Cir, 1≤i≤M, allora r è aperta. Se γic(r) = 0, ∀ c∈Cir, 1≤i≤M, la catena r è chiusa.

Una rete si dice aperta (o chiusa) se tutte le sue catene sono aperte (o chiuse). Una rete si dice mista se esistono sia catene aperte che chiuse.

In una catena r chiusa circolano Kr utenti.

Il tasso di arrivo dall’esterno al nodo i della classe c è esprimibile come:

γic(r)=γpic;0(r) dove γ è il tasso di arrivo totale dall’esterno alla rete e pic;0(r) è la proporzione degli arrivi verso il nodo i, classe c.

Il tasso medio relativo di arrivo totale al nodo i, 1≤i≤M, per utenti della classe c nella catena R è denotato eic(r), c∈Cir, 1≤i≤M, 1≤r≤R e si ottiene dal seguente sistema delle equazioni di traffico:

e^(r)_ic = p_0;ic^(r) +

∑

j = 1 M

∑

d ∈ Cjr

e_jd^(r) p_jd;ic^(r)

Lo stato del modello è molto più dettagliato rispetto ai precedenti modelli ed include il numero di utenti in ogni nodo e classe, lo stadio esponenziale delle distribuzioni Coxiane e l’ordine nella coda degli utenti.

Per risolvere la rete è necessario calcolare la distribuzione stazionaria della probabilità di stato, la distribuzione marginale del numero di utenti ai nodi e ai nodi per catena.

Consideriamo lo stato aggregato n = (n1, n2,…, nM), dove ni= (ni1, ni2,…, niR), nir è il numero di utenti nel nodo i, catena r e ni=

Σ

1≤r≤R nir, 1≤i≤M. Sia n(r)=

Σ

1≤r≤Mnir il numero totale di utenti nella catena r, dove per catene chiuse n(r)=Kr, 1≤r≤R.

Lo spazio degli stati è formato da E={n | nir≥0 se r è aperta, 0≤nir≤Kr, Σ1≤r≤M nir =Kr se r è chiusa, 1≤i≤M}.

Il tasso di arrivo γ può dipendere dal numero totale di utenti nella rete o per catena: γ(n), n = Σ1≤r≤M ni oppure γr(n(r)) 1≤r≤R.

Per questa classe di modelli vale il seguente teorema.

Teorema BCMP [BCM 75]

La distribuzione stazionaria di stato per reti BCMP si può esprimere come:

π(n₁, …, n_M) = G

1 d(n)

∏

i = 1 M

f_i(n_i) (4.9)

dove G è la costante di normalizzazione definita come:

G =

∑

n ∈ E

∏

i = 1 M

f_i (n_i) (4.10)

le funzioni d(n) possono essere scritte come d(n) =

∏

k = 0 n - 1

γ(k) oppure

d(n) =

∏

r = 1 R

∏

k = 0 n(r)

-1

γ_r(k) , per reti aperte e miste a seconda della funzione di arrivo

alla rete, e d(n) = 1 per reti chiuse,

le funzioni fi(ni) possono essere calcolate nel modo seguente:

f_i (n_i) = n_i!

∏

^ρir

r = 1

R n

ir

nir! se il nodo i è di tipo (1), (2), e (4) (4.11)

f_i (n_i) =

∏

^ρir

r = 1

R n

ir

nir! se il nodo i è di tipo (3) con ρir = eir / µir 1≤i≤M, 1≤r≤R

eir = Σc∈Cir eic(r) µir = Σc∈Cir eic(r) µir) /eir.

La dimostrazione, che omettiamo, si ottiene per sostituzione della espressione (4.9) nelle equazioni di bilanciamento globale del processo Markoviano associato alla rete [BCM 75].

Notare che per reti chiuse se la matrice P è irriducibile, la soluzione (4.9) esiste sempre, mentre per reti aperte e miste condizione sufficiente per la stazionarietà è

G< ∞ .

Sono state proposte diverse estensioni delle reti BCMP, di cui citiamo le due seguenti:

• Se il tasso è dipendente dallo stato locale: µir(nir), nella formula (4.11) µirnir è

sostituita dalla produttoria

∏

k = 1 nir

µ_ir(k) . Notare che per nodi di tipo (1) si può avere solo dipendenza da ni: µi(ni). In generale non si può avere dipendenza dall’intero stato n.

• Se il tasso è dipendente dallo stato totale di una sottorete I, {1,2,…,M} ⊇ I e nI =

Σ

i∈I ni, allora nella formula (4.8)

∏

i ∈ ^I fi (n

i) è sostituita da

∏

i ∈ ^I fi (n

i)

/ ∏

k = 1 nI

ZI (k) dove ZI(k) è un fattore moltiplicativo per µir, se nI=k, per i∈I, 1≤r≤R.

Altre estensioni includono diverse discipline di servizio, forme particolari di routing dipendente dallo stato, forme di blocco sull’intera popolazione e sullo stato locale.

Riassumendo, i modelli a rete di code appartengono alla classe di modelli in forma prodotto quando valgono determinate assunzioni su: tipi di nodi ovvero vincoli sulle discipline e distribuzioni del tempo di servizio, omogeneità del routing (indipendenza dallo stato totale), omogeneità del tempo di servizio, omogeneità degli arrivi esterni, singole richieste di servizio degli utenti alle risorse, serventi sempre attivi o disponibili (assenza di blocco) ed indipendenza degli utenti (assenza di sincronizzazioni).

Tali assunzioni costituiscono il principale limite di tale classe di modelli.

D’altra parte i vantaggi legati ai modelli a rete di code in forma prodotto sono molteplici e i principali consistono in:

• semplicità di definizione

• semplicità di analisi

• efficienza di analisi, ovvero bassa complessità computazionale di soluzione

• robustezza dei modelli rispetto ad alcune violazioni delle assunzioni

• applicazione per l’analisi previsionale delle prestazioni, per progetti di sistemi, al variare dei parametri

• base per i modelli più complessi.

È poi da notare la proprietà di insensibilità della soluzione di modelli a rete in forma prodotto rispetto a variazioni della matrice delle probabilità di diramazione (P), a cui corrisponda lo stesso numero medio di visite (e) e rispetto a distribuzioni del tempo di servizio per nodi con disciplina di servizio immediata, per i nodi di tipo (2), (3) e (4), aventi la stessa media.

Per quanto riguarda i modelli multiclasse occorre notare che se da un lato tali modelli permettono una maggiore rappresentatività dei sistemi, dall’altra il costo computazionale di analisi e valutazione degli indici aumenta esponenzialmente con il numero di catene, applicando i classici algoritmi di analisi (si veda il prossimo capitolo). Inoltre occorre considerare che vi è anche un aumento del numero di parametri per ogni classe nella fase di definizione del modello, che diventa quindi più complessa nel caso in cui si basi su stime o misure di carico per sistemi esistenti.