S. Balsamo - 62 -

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 -

S. Balsamo - 63 -

• 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à.

S. Balsamo - 64 -

Numeriamo i nodi della rete da 1 ad M. Un utente che ha completato il servizio alnodo i, si dirige (immediatamente) al nodo j, con probabilità pij ed esce dalla rete con

probabilità pi0. Tali probabilità devono soddisfare la seguente relazione:

pijj=1

M

∑ + pi0 = 1 1≤i≤M.

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

2 3 M1λ …

(a)

1λ

2

A

B

C

D

A+1

p12

p1A

p2B

p2A+1

pAC

pAD

(b)

1

2

3 4

56

λ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.

S. Balsamo - 65 -

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

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.

S. Balsamo - 66 -

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 divieneNi=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.

λ µ µ1 2

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

S. Balsamo - 67 -

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 diparametro λ, tempo di servizio ai due nodi indipendenti distribuitoesponenzialmente, rispettivamente con tassi µ1 e µ 2, e discipline di servizioFIFO.Sotto queste ipotesi definiamo lo stato del sistema come (n1, n2) quando visono n1 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 deglistati E = {(n1, n2) | ni≥0}e distribuzione stazionaria di stato è π(n1, n2). Lospazio E e quindi il sistema (4.1) è infinito. Il diagramma degli stati delprocesso 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 analizzatoindipendentemente 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ò esserecaratterizzato sulla base del seguente teorema, illustrato in Fig. 4.4.

Teorema di Burke

S. Balsamo - 68 -

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

λPoisson ( ) λPoisson ( )exp

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 statodella rete si esprime come il prodotto delle probabilità marginali, ovvero:

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

È facile verificare che questa espressione soddisfa le equazioni dibilanciamento 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 pji 1≤i≤M (4.2).

S. Balsamo - 69 -

λ µ p

1-p

Fig. 4.5 - Sistema di coda con feedback -

Sotto le ipotesi date definendo n = (n1, 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:

π (n1 , n2, …, nM) = ∏i = 1

M

Prob i {ni} (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, conparametri λ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 servizioesponenziale rispettivamente di parametro µ1 e µ2. Un utente che esce dalnodo 2 lascia il sistema con probabilità p e con probabilità 1-p ritorna lanodo 1. (n1, n2) rappresenta lo stato del sistema ed E = { (n1, n2) | ni≥0} lospazio degli stati e π(n1, n2) è la distribuzione stazionaria di stato.

λ µ µ1 2p

1-p

Fig. 4.6 - Rete tandem con feedback -

S. Balsamo - 70 -

La porzione iniziale del diagramma degli stati del processo Markovianoassociato è 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 soluzioneespressa 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 bilanciamentoglobale (4.1) del processo. La soluzione è ottenibile come se il sistema fosseformato 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.

S. Balsamo - 71 -

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 pji 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:

π (n1 , n2, …, nM) = ∏i = 1

M

π i (ni) (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

S. Balsamo - 72 -

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

δ(ni) µ i ai(ni) ) = ∑i = 1

M

δ(ni) γi π(n - e i) +

+ ∑i = 1

M

µ i ai (ni+1) p i0 π(n + ei) +

+ ∑i = 1

M

∑j = 1

M

δ(nj) µ i ai(ni+1) pij π(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/mindipendenti. La funzione πi è la soluzione del nodo i analizzato come un M/M/micon 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 diarrivo 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ò essereuna funzione del numero di utenti del nodo stesso, ovvero µi(ni), ni ≥0, 1≤i≤M.

S. Balsamo - 73 -

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 formadi blocco. Assumiamo che il nodo i abbia capacità massima Bi (memoria finita),

ovvero il numero di utenti sia limitato superiormente (ni ≤ 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:

π(n1 ,…,nM) = C1

∏n = N *

N - 1

γ(n) ∏i = 1

M

gi(ni)

dove N = Σi ni, gi(n) = ei n / ∏

s = 1

n

µ i(s) , ei = p0i + ∑j = 1

M

ej pji 1≤i≤M e C è

una costante di normalizzazione che garantisce Σn∈E π(n) = 1.

S. Balsamo - 74 -

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 pji 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 = (n1, 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:

π(n1 ,…,nM) = C(K) 1

∏i = 1

M

gi(ni) (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:

S. Balsamo - 75 -

C (K) = ∑n ∈ Ε

∏i = 1

M

gi(ni) (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

δ(ni) µ i a i(ni) = ∑i = 1

M

∑j = 1

M

π(n + ei - ej) δ(nj) µ i ai(ni+1) piji

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 singoliillustrata in Fig. 4.7. Essa costituisce un modello basilare per reti dicomunicazione per rappresentare protocolli di tipo store and forward [SCH87]. Supponiamo che i nodi abbiano tassi di servizio µ1,...,µM condistribuzione esponenziale e servente singolo. Consideriamo la soluzionedel 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 dellelunghezze di coda, π(n,) da cui si possono ricavare altri indici di prestazionequali ad esempio, throughput, numero medio di job nella rete, tempi medi dirisposta 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 -

S. Balsamo - 76 -

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

S. Balsamo - 77 -

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

S. Balsamo - 78 -

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’insiemedelle 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 diservizio

(1) FIFO esponenziale

(2) PS (Processor Sharing) Coxiana

(3) IS (Infiniti Serventi) Coxiana

(4) LIFOPr (LIFO con

Prelazione)

Coxiana

S. Balsamo - 79 -

µ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 cnella catena R è denotato eic(r), c∈Cir, 1≤i≤M, 1≤r≤R e si ottiene dal seguente

sistema delle equazioni di traffico:

eic(r)

= p0;ic(r)

+ ∑j = 1

M

∑d ∈ Cjr

ejd(r)

pjd;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≤Mnir =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:

S. Balsamo - 80 -

π(n1, …, nM) = G1

d(n) ∏i = 1

M

fi(ni) (4.9)

dove G è la costante di normalizzazione definita come:

G = ∑n ∈ E

∏i = 1

M

fi (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:

fi (ni) = ni! ∏ ρir

r = 1

R

nir

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

(4.11)

fi (ni) =

∏ ρir

r = 1

R

nir

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:

S. Balsamo - 81 -

• 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.

S. Balsamo - 82 -

È 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.