Capitolo 5 - Algoritmi per modelli a reti di code

Capitolo 5 - Algoritmi per modelli a reti di code

In questo capitolo presentiamo i principali algoritmi di analisi di modelli a rete di code. Presentiamo inizialmente il metodo di analisi operazionale che costituisce uno strumento semplice e generale di analisi di modelli, applicabile non soltanto a reti di code. Con tale metodo si ricavano delle semplici relazioni ed intervalli per gli indici di prestazione del sistema. Nella seconda sezione presentiamo i due algoritmi più utilizzati per l'analisi di reti chiuse in forma prodotto, ovvero per il calcolo della probabilità stazionaria di stato e degli indici di prestazione. Nella terza sezione presentiamo i metodi di aggregazione e decomposizione sia per modelli di code che per la classe di modelli stocastici basati su processi Markoviani.

5.1 Analisi Operazionale

Un semplice metodo di analisi dei modelli a rete di code è l’analisi operazionale che si basa sull’osservazione di un sistema in un intervallo di tempo finito e permette di derivare alcune semplici relazioni deterministiche. Per la sua semplicità tale metodo è applicabile ad una ampia classe di modelli che include le reti di code, ed è particolarmente utile in fase di progetto del sistema [LAV 89, LZG 84, FSZ 83, JAI 90, KAN 92].

Consideriamo un sistema aperto generico come illustrato in Fig. 2.1. In un intervallo di osservazione [0,t] definiamo

A(t)∈Ν numero totale di arrivi al sistema in [0, t]

C(t) numero totale di completamenti di servizio in [0, t]

da cui

λ(t) = A(t)/t tasso di arrivo al sistema in [0, t]

X(t) = C(t)/t throughput del sistema in [0, t]

dove A(t), C(t)∈Ν e λ(t), X(t)∈R0+. Definiamo inoltre

O(t) tempo di occupazione del sistema in [0, t]

da cui

U(t) = O(t)/t utilizzazione del sistema in [0, t]

S(t) = O(t)/C(t) servizio medio per utente in [0, t]

dove O(t)∈[0, t], U(t)∈[0, 1] e S(t)∈R0+.

Per sostituzione immediatamente possiamo scrivere:

U(t) = X(t) S(t)

relazione detta legge di utilizzazione che lega l’utilizzazione del sistema al throughput e tempo medio del singolo servizio in un intervallo di tempo.

Consideriamo ora il numero di utenti nel sistema al tempo t dato da [A(t) - C(t)], che evolve come ad esempio mostrato in Fig. 5.1. Definiamo W(t) il lavoro totale accumulato in [0, t] come segue:

W(t) = (A(τ) - C(τ)) dτ

0

∫t

da cui ricaviamo

N(t) = W(t)/t numero medio di utenti in [0, t]

R(t) = W(t)/C(t) tempo medio di risposta in [0, t]

dove N(t)∈N, R(t)∈R0+. Per definizione e sostituzione otteniamo la legge di Little che lega numero medio di utenti, throughput e tempo medio di risposta in un intervallo di tempo:

N(t) = X(t) R(t).

t A(t)

C(t)

Fig. 5.1 - Numero di utenti nel sistema aperto -

Tale relazione che abbiamo già introdotto nel capitolo 3 per i modelli basilari di code è di applicazione generale e nella forma qui introdotta non richiede particolari assunzioni se non che esistano le grandezze fra loro in relazione.

La legge di Little può essere applicata a qualsiasi sistema, definendo opportunamente le tre grandezze.

Nei modelli a rete di code possiamo quindi applicarla:

• a livello di singolo servente di un centro di servizio,

• a livello di un centro di servizio, per cui ritroviamo le formule (3.5) o (3.6) a seconda che consideriamo incluso nel sistema il servente o meno,

• a livello di sottorete, ovvero definendo come sistema un sottoinsieme dei nodi della rete,

• a livello di intero modello a rete di code.

Notiamo che la legge di utilizzazione può essere vista come un caso particolare della legge di Little, se applicata al singolo servente, ovvero ad un sistema che ammette al più un utente.

Quando consideriamo un sistema in condizioni di equilibrio la legge di Little viene riformulata come segue.

Teorema di Little

Sia ri il tempo speso nel sistema dall’i-esimo utente. Se esistono e sono finiti i limiti λ = lim t→ ∞ A(t)

t = lim t→ ∞λ(t)

N = lim t → ∞N(t)

R= limk→ ∞ 1 kΣik=1

ri

allora

N = λ R.

Osserviamo che quando il sistema raggiunge una condizione di equilibrio si ha una relazione di bilanciamento del flusso, ovvero non vi sono nel sistema nè perdite nè ingressi, il throughput uguaglia la velocità di arrivo: X = _, quindi il teorema di Little afferma che

N = X R.

Se consideriamo un modello di sistema costituito da M risorse possiamo estendere l’analisi introdotta considerando le seguenti grandezze ed indici di prestazione per ogni risorsa 1≤i≤M in un intervallo di osservazione [0, t]:

Ai(t) numero totale di arrivi ad i in [0, t]

Ci(t) numero totale di completamenti di servizio da i in [0, t]

_i(t) = Ai(t)/t tasso di arrivo ad i in [0, t]

Xi(t) = Ci(t)/t throughput di i in [0, t]

Oi(t) tempo di occupazione di i in [0, t]

Ui(t) = Oi(t)/t utilizzazione di i in [0, t]

Si(t) = Oi(t)/Ci(t)servizio medio per utente di i in [0, t]

da cui

Vi(t) = Ci(t)/C(t) numero medio ovvero frequenza di visite ad i in [0, t]

Di(t) = Vi(t) S(t) domanda totale di servizio ad i in [0, t].

Per definizione e sostituzione possiamo scrivere la seguente relazione fra il throughput locale e globale, nota come legge del flusso forzato:

Xi(t) = Vi(t) X(t)

da cui deriva la relazione di proporzionalità fra throughput locali e frequenze di visita:

Vi(t) / Vj(t) = Xi(t) / Xj(t) per 1≤i,j≤M.

Infine, dalla legge di utilizzazione applicata alla singola risorsa e dalla legge del flusso forzato, otteniamo la seguente relazione fra utilizzazione e domanda di servizio per ogni risorsa i, 1≤i≤M:

Ui(t) = Xi(t) Si(t) = X(t) Vi(t) Si(t) = X(t) Di(t).

5.1.1 Analisi asintotica dei limiti delle prestazioni di sistema

Le semplici relazioni dell’analisi operazionale, valide sotto assunzioni generali permettono di derivare semplici limiti superiori ed inferiori alle

prestazioni del sistema in funzione del carico. Si parla di analisi asintotica poichè si considerano

condizioni estreme del carico. In particolare consideriamo la valutazione di

• throughput X

• tempo di risposta R

in funzione di

• numero di utenti N (sistema chiuso)

• tasso di arrivo _(sistema aperto).

Fra i vantaggi di tale metodo vi è la semplicità della computazione, basata su semplici formule. E’ possibile valutare sistemi in fase di progetto, non completamente definiti, così come sistemi in fase di dimensionamento, confrontando insiemi di configurazioni alternative.

Con l’analisi asintotica possiamo individuare fattori critici del sistema. In particolare possiamo identificare i colli di bottiglia e valutarne quantitativamente l’impatto sulle prestazioni del sistema. Lo studio della rimozione dei colli di bottiglia può portare alla identificazione di altri colli di bottiglia, detti secondari, che si manifestano quando i primi sono stati rimossi. Il procedimento di analisi e rimozione dei colli di bottiglia è iterativo e porta ad un sistema bilanciato [KLE 75, FSZ 81, LZG 84, JAI 90, KAN 92].

Lo studio congiunto di insiemi di configurazioni alternative di sistemi può essere effettuato in modo gerarchico e strutturato. Una semplice condizione per definire un insieme di configurazioni da analizzare è l’identificazione della o delle stesse risorse critiche.

Notiamo inoltre che con tale analisi possiamo valutare semplicemente modifiche ed estensioni di configurazioni di sistemi, identificandone i massimi livelli prestazionali raggiungibili in funzione delle risorse critiche.

Consideriamo un sistema formato da M risorse ed un insieme di utenti che chiedono servizio al sistema. Di è la domanda complessiva di servizio alla risorsa i, 1≤i≤M. Definiamo:

Dmax = max 1≤i≤M Di

Calcoliamo gli estremi inferiori e superiori per throughput e tempo medio di risposta denotati da:

X(N) e R(N) per un sistema chiuso X(_) e R(_) per un sistema aperto.

Si avranno i limiti ottimistici se consideriamo l’estremo superiore ad X ed inferiore ad R, pessimistici nel caso opposto.

Dalle relazioni su X ed R possiamo ricavare estremi inferiori e superiori anche per altri indici di prestazione del sistema, sulla base delle relazioni sopra definite, ed in particolare per l’utilizzazione e il throughput locale dalle seguenti equazioni, per 1≤i≤M:

Ui (N) =X(N) Di Xi (N) =X(N) Vi.

Il metodo che presentiamo si applica a modelli molto generali di cui i modelli a rete di code sono un caso particolare. Unica assunzione è che la domanda di servizio di ogni utente non dipenda dagli altri utenti presenti nel sistema, nè per il numero, nè per la loro dislocazione.

Distinguiamo i due casi di sistema aperto e chiuso.

Sistema aperto

Consideriamo il sistema aperto di Fig. 2.1. Sia λ il tasso di arrivo al sistema.

Determiniamo il massimo carico che il sistema può sostenere (λmax) senza raggiungere la condizione di saturazione. Un sistema si dice saturo se il tempo di risposta non è limitato superiormente. Un sistema è saturo se contiene almeno una risorsa satura. Una risorsa i è satura se Ui = 1. Per la legge di utilizzazione e per la relazione Xi = λ Vi possiamo scrivere Ui = λ Vi Si = λ Di. Dalla condizione Ui = λDi

≤1 deriviamo che il massimo carico che il sistema può sostenere è λmax = 1/ Dmax.

Il nodo saturo è il collo di bottiglia del sistema.

Finché il tasso di arrivo è λ < λmax allora il sistema è stabile e vale la condizione di bilanciamento, X = λ. Quando λ ≥ λmax il sistema è instabile ed i tempi di attesa e risposta tendono a crescere senza limite finito.

Per il sistema aperto abbiamo quindi i seguenti limiti ottimistici alle prestazioni:

X(λ) ≤ λmax = 1/ Dmax R(λ) ≥ D.

Il tempo di risposta nel caso migliore è infatti dato dalla somma dei tempi di servizio complessivi a tutte le risorse, quando non vi è mai competizione e quindi attesa per l’uso delle risorse.

Per il sistema aperto non possiamo derivare i limiti pessimistici alle prestazioni. E’

facile verificare infatti che se, per assurdo, Rmax è un limite superiore al tempo di risposta del sistema con tasso di arrivo λ qualsiasi, se consideriamo ad esempio arrivi a gruppi di n utenti ogni n/λ unità di tempo, scegliendo n>(Rmax / D) osserviamo un tempo di risposta superiore ad Rmax.

Sistema chiuso

Consideriamo il sistema chiuso con K utenti che vi circolano costantemente.

Determiniamo il massimo carico che il sistema può sostenere senza saturarsi.

Analogamente al caso di sistema aperto otteniamo che X(Κ) ≤ 1/ Dmax

ed il massimo corrisponde al collo di bottiglia del sistema.

Sotto ipotesi di carico leggero possiamo invece scrivere quando nel sistema vi è un solo utente R(1)=D e X(1)=1/D. Considerando K utenti nel caso migliore ogni utente non sperimenta mai attesa e quindi R(K) ≥ D e X(K) ≤ K/D, mentre nel caso peggiore avrà ad ogni risorsa tutti gli altri utenti davanti a sè, per cui R(K) ≤ KDmax e X(K) ≥ 1/D. Considerando l’unione di queste condizioni si ottengono i seguenti limiti ottimistici e pessimistici alle prestazioni del sistema chiuso per il throughput:

1/D ≤ X(Κ) ≤ min { 1/ Dmax, K/D}

K X(K)

K*

Fig. 5.2 - Limiti al throughput in un sistema chiuso -

K R(K)

K*

Fig. 5.3 - Limiti al tempo di risposta in un sistema chiuso - e per il tempo di risposta:

max { D, KDmax } ≤ R(K) ≤ KD.

I limiti sono illustrati nelle Fig. 5.2 e 5.3. Notiamo che K*=D/ Dmax rappresenta la soglia del carico oltre la quale il comportamento del sistema è limitato dalle funzioni ricavate sotto ipotesi di carico “pesante”. Ciò significa che oltre K* un incremento del carico ha un impatto più limitato se non negativo sulle prestazioni del sistema. Il throughput è infatti limitato dall’asintoto 1/Dmax e il tempo di risposta tende a crescere almeno linearmente con il carico. K≤K* rappresenta quindi un possibile criterio da adottare per garantire prestazioni accettabili del sistema. Per una discussione approfondita si veda [FSZ 81, LZG 84, JAI 90, KAN 92].

Si consideri un sistema interattivo, come ad esempio illustrato in Fig. 1.6, in cui Rterm denota il tempo di reazione (di risposta) ai terminali (rappresentato dal nodo terminali nel modello), ovvero il tempo che intercorre fra l’istante in cui l’utente riceve la risposta dal sistema e l’istante in cui lancia una nuova richiesta (comando). I limiti alle prestazioni del sistema, illustrati nelle Fig. 5.4 e 5.5, possono essere riscritti come segue [LZG 84]:

K / [K/D + Rterm] ≤ X(Κ) ≤ min { 1/ Dmax, K / [D + Rterm]}

max { D, KDmax - Rterm} ≤ R(K) ≤ KD.

La soglia K* = [D + Rterm] / Dmax ha il significato sopra illustrato e può essere utilizzata in questo caso, ad esempio, per determinare il numero di terminali da collegare al sistema in modo da mantenere un buon livello prestazionale.

K X(K)

K*

Fig. 5.4 - Limiti al throughput in un sistema interattivo -

K R(K)

K*

Fig. 5.5 - Limiti al tempo di risposta in un sistema interattivo -

Il metodo di analisi asintotica è semplice ed utile per una prima valutazione di sistemi, mentre risultati più accurati possono essere ottenuti con i modelli a rete di code ed i metodi di analisi che introduciamo ora.

5.2 Algoritmi per modelli di code in forma prodotto

I due principali algoritmi per modelli a rete di code chiuse in forma prodotto sono:

l’algoritmo di Convoluzione [BUZ 73] e l’algoritmo MVA (Mean Value Analysis) [RL 80]. Dal punto di vista della complessità computazionale i due algoritmi sono equivalenti e richiedono tempo e spazio di ordine polinomiale nelle componenti della rete, ovvero nel numero di nodi e di utenti. Concettualmente i due algoritmi si basano su una relazione ricorsiva rispettivamente sul numero di nodi e sul numero di utenti.

Non si può affermare che un algoritmo sia migliore dell’altro in assoluto, in quanto oltre alla complessità computazionale occorre considerare altri fattori, quali, ad

esempio, il tipo di rete e di nodi nella rete, lo sforzo di programmazione e i problemi di instabilità numerica. In generale si può affermare che MVA è da preferire per reti costituite da nodi a capacità fissa e nodi di tipo (3) (si veda sezione 4.3.3) ovvero con infiniti serventi (IS). Per modelli a rete formate da nodi a capacità dipendente dal carico la versione originale dell’algoritmo MVA può essere numericamente instabile.

E’ stata proposta una versione modificata (MMVA) [REI 81] numericamente stabile ma che comporta un aumento della complessità computazionale in termini di spazio e tempo molto elevato. L’algoritmo di convoluzione [BUZ 73] è basato sul calcolo della costante di normalizzazione G e può dar luogo a problemi di instabilità numerica sia dovuti ad overflow/underflow e sia dovuto ad errori di troncamento ed arrotondamento. Tale algoritmo ha una complessità computazionale paragonabile a quella dell’algoritmo MVA non modificato.

Per quanto riguarda i modelli a rete in forma prodotto multicatene gli algoritmi di Convoluzione ed MVA richiedono una complessità computazionale che è ancora polinomiale nel numero di nodi ed utenti, ma esponenziale nel numero di catene. Per tali modelli sono stati proposti in letteratura altri algoritmi basati su espressioni ricorsive sul numero di catene, la cui complessità computazionale è polinomiale nel numero di catene, ma esponenziale nel numero di nodi o nel numero di utenti. Fra questi ricordiamo gli algoritmi Recursion by Chains (RECAL) [CON 89], Mean Value Analysis by Chains (MVAC) [CSL 89], rispettivamente basati sull’operazione di convoluzione e di MVA, e l’algoritmo Distribution Analysis by Chain (DAC) [DSL 89] che permette di calcolare soltanto alcuni indici di prestazione globali del modello [LAV 89].

Infine per modelli cosiddetti sparsi in cui gli utenti di ogni catena visitano pochi nodi può essere molto efficiente applicare algoritmi strutturati ad albero, sia di tipo convoluzione [LL83] che MVA [TS 85].

In questa sezione presentiamo i due algoritmi di Convoluzione ed MVA per modelli a rete di code chiuse con catena singola.

Consideriamo una rete BCMP chiusa con M nodi, K utenti dello stesso tipo (R=1, catena singola), matrice delle probabilità di diramazione P, vettore dei throughput relativi e (e = e P), con componenti ejc c∈Cj per ogni classe c del nodo j, 1≤j≤M ed ej=Σc∈Cejc throughput relativo del nodo j.

Siano µj il tasso di servizio del nodo j, 1≤j≤M, ρi = ej /µj, n = (n1,…,nM) lo stato della rete ed E = { n | 0≤nj≤K, Σ1≤i≤Mj ni = K } lo spazio degli stati.

In accordo al teorema BCMP, la probabilità stazionaria di stato π(n), n∈E, può essere espressa come

π(n) = G 1

∏

j = 1 M

f (n )_{j j}

dove la funzione fj(nj) per nodi con singolo servente ed a velocità costante è definita come segue per 1≤j≤M, nj>0,

fj(nj) = ρjnj /nj! se il nodo j è di tipo (3), ovvero con disciplina di servizio IS, fj(nj) = ρjnj altrimenti.

Se il nodo i ha velocità dipendente dallo stato espressa da µi(ni), 0≤ni≤K, l’espressione µ ini nella definizione della funzione fi(ni) è sostituita dalla produttoria

∏

µi(k) .

Se il nodo i ha mj serventi ognuno a velocità ßi(k) quando vi sono k utenti nel nodo i, poniamo µi(k)=min{k,mi}ßi(k).

Gli algoritmi di Convoluzione ed MVA che descriviamo qui di seguito calcolano gli indici di prestazione locali ai nodi, ed in particolare, per ogni nodo i, 1≤i≤M:

• throughput Xi(K)

• utilizzazione Ui(K)

• lunghezza media di coda Ni(K)

• distribuzione della lunghezza di coda πi(k), 0≤k≤K

• tempo medio di risposta Ri(K).

5.2.1 Algoritmo di Convoluzione

Presentiamo qui di seguito l’algoritmo di Convoluzione per modelli a rete di code chiuse a catena singola. Esso è basato sul calcolo esplicito della costante di normalizzazione G definita come

G =

∑

n ∈ E

∏

i = 1 M

fi (n

i) (5.1)

ottenuto attraverso la convoluzione dei fattori fi(ni). L’algoritmo si basa su una doppia iterazione sui nodi e sugli utenti della rete. La complessità computazionale è quindi dell’ordine del prodotto del numero di nodi per il numero di utenti, cioè

O(MK). Tale algoritmo è semplice ed è efficiente computazionalmente. Tuttavia si possono manifestare problemi di instabilità numerica.

Sia Gj(k) la costante di normalizzazione della rete con i primi j nodi e con k utenti, 1≤j≤M, 0≤k≤K, definita come

G_j(k) =

∑

n ∈ E(j,k)

∏

i = 1 j

f_i(n_i)

dove E(j,k) denota lo spazio degli stati di tale rete. Allora la costante di normalizzazione dell’intera rete G espressa dalla formula (5.1) è G = GM(K).

Sia Gj = ( Gj(0) Gj(1)… Gj(K) ).

Per j>1, 0≤k≤K, possiamo scrivere

Gj(k) =

∑

n = 0 k

fj(n) G

j-1(k-n) (5.2)

ovvero il vettore Gj si può ottenere per convoluzione dei vettori Gj-1 ed il vettore (fj(0)…fj(K)). Per definizione possiamo scrivere

per k=0 Gj(0)=1 1≤j≤M

G0(0)=1

per j=0 G0(k)=0 0<k≤K

per j=1 G1(k)=f1(k) 0≤k≤K.

Sulla base di queste condizioni iniziali e della formula ricorsiva (5.2) di convoluzione possiamo definire un algoritmo per il calcolo della costante G, date le funzioni fj(k), 1≤j≤M, 0≤k≤K. Scegliendo un opportuno ordinamento dei nodi possiamo semplificare l’algoritmo come segue.

Siano i nodi numerati da 1 ad M' di tipo (3), ovvero con disciplina IS, i nodi da M'+1 ad M" a velocità costante non IS e i nodi da M"+1 ad M a velocità dipendente dal carico.

Per i primi M' nodi IS possiamo scrivere direttamente la costante di normalizzazione GM'(k), per 0≤k≤K, come

G_M'(k) =

∑

j = 1 M'

ρ_j

k

k!

1

(5.3).

Per i nodi a velocità costante, poichè fj(k)=ρjk, l’operazione di convoluzione data dalla formula (5.2) si semplifica come

Gj(k) = Gj-1(k) + ρj Gj(k-1) (5.4) 0≤k≤K, M'+1≤j≤M".

Infine per i restanti nodi a velocità variabile il vettore Gj è calcolato applicando la formula generale (5.2), M"+1≤j≤M.

Riassumendo, la costante G=GM(K) viene calcolata a partire dalle condizioni iniziali applicando le formule (5.3), (5.4) e (5.2).

Inoltre dall’ultimo vettore GM possiamo ricavare direttamente anche gli indici di prestazione locali al nodo j, 0≤j≤M.

La distribuzione di probabilità marginale della lunghezza di coda è data da

π_j(k) = f_j(k)

G_M(K) GM - {j}(K-k)

(5.5) per 0≤k≤K, dove GM-{j}(k) è la costante di normalizzazione della rete con k utenti e tutti i nodi eccetto il nodo j, 1≤j≤M. Notiamo che se j=M allora GM-{j}= GM-1.

Per nodi a velocità costante, utilizzando la relazione (5.4) fra GM-1 e GM, l’espressione (5.5) si semplifica nella seguente

π_j(k) = ρ_j ^k

{

M(K-k-1)

}

Per definizione, si ricava la seguente espressione per il throughput del nodo j, 1≤j≤M:

X_j(K) = e_j

G_M(K) GM(K-1)

(5.7) e dell’utilizzazione

Uj(K) = 0 1≤j≤M' per j nodo IS

Uj(K) = Xj(K) / µj mj M'+1≤j≤M" per j nodo a velocità costante con mj serventi

Uj(K) =

∑

k = 1 K

min{k,m

j} π_j(k) / m

j

M"+1≤j≤M per j nodo a velocità dipendente dal carico.

La lunghezza media di coda è data da

Nj(K) = Xj(K) / µj 1≤j≤M' per j nodo IS N_j(K) =

∑

k = 1 K

ρ ^k_j

G_M(K) GM(K-k)

M'+1≤j≤M" per j nodo a velocità costante

Nj(K) =

∑

k = 1 K

k π_j(k) (5.8)

M"+1≤j≤M per j nodo a velocità dipendente dal carico.

Inoltre notiamo che da queste espressioni per un nodo j a velocità costante possiamo scrivere la seguente relazione ricorsiva per la lunghezza media di coda, per K>1

Nj(K) = Uj(K) [ 1 + Nj(K-1) ] (5.9).

Il tempo medio di risposta si ottiene immediatamente applicando il teorema di Little per ogni nodo j, 1≤j≤M

Rj(K) = Nj(K) / Xj(K).

Dagli indici di prestazione locali al nodo j e dal numero medio di visite per nodo e classe possiamo ricavare anche gli indici di prestazione locali alla classe c del nodo j, c∈Cj, 1≤j≤M, come segue

• throughput Xjc(K) = Xj(K) ejc / ej

• utilizzazione Ujc(K) = Uj(K) µ j / µjc

• lunghezza media di coda Njc(K) = Nj(K) µ j / µjc

• tempo medio di risposta Rjc(K) = Njc(K) / Xjc(K).

Algoritmo di Convoluzione {Inizio calcolo costanti, nodi IS};

If M' =0 Then G = (1 0 0 0 ... 0);

t:=0;

For j:=1 to M' do t:= t + ej / µj;

G(0) :=1;

For k:= 1 to K do G(k):= G(k-1) t / k;

{nodi a velocità fissa};

For j:=M'+1 to M" do begin

T:= G;

For k:=1 to K do G(k):= T(k) + (ej / µj) G(k-1);

end;

{altri centri di servizio};

For j:=M"+1 to M do begin T:= G;

GM-(j):=G;

Xj(0):=1;

For k:=1 to K do begin G(k):=0;

Xj(k):=Xj(k-1) (ej / µj(k));

For i:=1 to k do G(k):=G(k) +Xj(i) T(k-i); {Convoluzione}

end;

end;

{Fine del calcolo delle costanti di normalizzazione};

{Calcolo degli indici di prestazione};

For j:=1 to M do Xj:= ej (G(K-1)/G(K));

For j:=1 to M' do begin Uj:=0;

Nj:=Xj / µj;

Rj:= 1 / µj;

end;

For j:=M'+1 to M" do begin

Uj:=Xj / µj;

Nj:=0;

For k:=1 to K do

Nj:= Nj + (ej / µj)k (G(N-k);

Nj:=Nj / G(K);

Rj:= Nj / Xj;

end;

For j:=M"+1 to M do begin Uj:=0;

For k:=1 to K do Uj:= Uj + min (k, mj)Xj(k) GM-(j) (K-k);

Uj:=Uj/ (G(K) mj);

Nj:=0;

For k:=1 to K do Nj:= Nj + Xj GM-(j) (K-k);

Nj:=Nj /G(K);

Rj:=Nj / Xj;

end;

{Fine algoritmo di Convoluzione}.

Fig. 5.6 - Algoritmo di Convoluzione -

La Fig. 5.6 mostra la versione Pascal-like dell’algoritmo di Convoluzione assumendo che le distribuzioni delle lunghezze di coda siano calcolate solo se necessarie per derivare gli indici medi di prestazione, ovvero solo per i nodi a velocità variabile. Si assume inoltre che sia dato il vettore e dei throughput relativi. La versione dell’algoritmo presentata minimizza la complessità computazionale a scapito della complessità di spazio di memoria.

5.2.2 Algoritmo di Mean Value Analysis

Presentiamo ora l’algoritmo di MVA (Mean Value Analysis) per modelli a rete di code chiuse a catena singola.

L’algoritmo MVA è basato sul teorema degli arrivi [SM 81, RL 80], che permette di derivare una relazione ricorsiva per il tempo medio di risposta per un utente attraverso un nodo, in funzione del numero totale di utenti nella rete. In tal modo, contrariamente all’algoritmo di Convoluzione, l’algoritmo MVA calcola gli indici medi di prestazione del modello evitando il calcolo esplicito della costante di normalizzazione G, eliminandone i relativi problemi di instabilità numerica.

Riportiamo l’enunciato del teorema degli arrivi per la classe di reti BCMP chiuse.

Teorema degli arrivi [SM 81, RL 80]

In una rete chiusa BCMP la probabilità stazionaria di stato al tempo di arrivo di un utente ad un nodo è identica alla probabilità stazionaria di stato a tempo arbitrario della stessa rete con l’utente rimosso.

Da tale teorema deriva la seguente espressione ricorsiva per il tempo medio di risposta di un utente al nodo j quando nella rete vi sono K utenti, in funzione della lunghezza media di coda dello stesso nodo j quando nella rete vi è un utente in meno:

R_j(K) = µ_j

1 ( 1 + N_j(K-1) ) (5.10)

se il nodo j ha velocità di servizio costante µj.

Inoltre possiamo scrivere la seguente relazione ricorsiva della probabilità marginale dello stato n del nodo j dati K utenti nella rete, in funzione della probabilità dello stato n-1 del nodo j quando nella rete vi è un utente in meno:

π_j(n | K) = µ_j(n) Xj(K)

π_j(n-1 | K-1) (5.11)

per 1≤n≤K, K>1.

Sulla base della relazione ricorsiva (5.10) e del teorema di Little definiamo lo schema ricorsivo per calcolare gli indici medi di prestazione del modello formato da nodi di tipo (3), ovvero con disciplina di servizio IS, e nodi con velocità di servizio costante.

Assumiamo che i nodi siano numerati in modo che i primi M' nodi siano di tipo IS, i nodi da M'+1 a M"=M siano a velocità costante.

1. Rj(K) = 1 / µj 1≤j≤M', nodo IS R_j(K) =

µ_j

1 ( 1 + N_j(K-1) ) M'+1≤j≤M", nodi a tasso costante

2. X

j(K) =

∑

e_j ei

R_i(K)

K ∀j (5.12)

3. Nj(K) = Xj(K) Rj(K) ∀j (5.13)

Il primo passo si basa sul teorema degli arrivi, mentre il secondo ed il terzo derivano dalla applicazione della legge di Little, rispettivamente nel secondo all’intera rete considerando il tempo medio di ciclo ed il throughput relativamente al nodo j e nel terzo al solo nodo j, 1≤j≤M.

L’algoritmo MVA è costituito da questo schema ricorsivo sul numero di utenti, con la condizione iniziale

Nj(0) = 0 ∀j.

Se nella rete sono presenti nodi con velocità di servizio dipendente dal carico occorre calcolare ricorsivamente anche le probabilità marginali per tali nodi applicando la formula (5.11). Assumiamo che i nodi da M"+1 ad M siano a velocità dipendente dal carico. In tal caso lo schema ricorsivo dell’algoritmo MVA viene modificato come segue:

1. come nel caso precedente per i nodi j, 1≤j≤M"

Rj(K) =

∑

n = 1 K

µ

j(n)

n π_j(n-1 | K-1) K>0 per M"+1≤j≤M (5.14)

2. come nel caso precedente per tutti i nodi j, 1≤j≤M 3. come nel caso precedente per i nodi j, 1≤j≤M"

calcolo della probabilità marginale del nodo j, per M"+1≤j≤M π_j(n | K) =

µj(n) X_j(K)

π_j(n-1 | K-1) 1≤n≤K , K>1 (5.15)

π_j(0 | K) = 1 -

∑

n = 1 K

π_j(n | K) (5.16)

calcolo del valor medio Nj(K) dalla definizione (5.8).

Al terzo passo la probabilità che il nodo j sia vuoto viene calcolata dalla formula (5.16) applicando la condizione di normalizzazione sulle probabilità. Alle condizioni iniziali si aggiunge la seguente

πj(0|0) = 1, M"+1≤j≤M.

Le formule ricorsive (5.15) e (5.16) si possono applicare anche per calcolare la distribuzione della lunghezza di coda di ogni nodo j, 1≤j≤M.

E’ interessante osservare che la formula ricorsiva basilare dell’algoritmo, definita al primo passo dello schema, può essere ricavata anche dalla formula (5.9) ottenuta dalla definizione dell’algoritmo di Convoluzione.

L’algoritmo MVA offre come principale vantaggio rispetto all’algoritmo di Convoluzione il calcolo diretto degli indici di prestazione senza ricorrere esplicitamente alla costante di normalizzazione G. Tuttavia anche l’algoritmo MVA può dar luogo a problemi di instabilità numerica quando la probabilità πj(0|K) che il nodo j sia vuoto tende a zero. In tal caso errori di arrotondamento nella implementazione della formula (5.16) possono portare a valori negativi. Anche nel caso in cui si cerchi di ovviare tale inconveniente imponendo πj(0|K)=0, tale errore si propagherebbe comunque ai passi successivi su altri valori della probabilità applicando la formula (5.15). Questo problema di instabilità numerica è risolvibile considerando la seguente diversa espressione ricorsiva per la probabilità che il nodo j sia vuoto quando nella rete vi sono K utenti:

π_j(0 | K ) = π_j(0 | K-1)

X_i^{M - {j}}(K) Xi(K)

(5.17)

dove XiM-{j}(K) è il throughput di un nodo i≠j nella rete ottenuta dalla rete originale ma con il nodo j rimosso.

Algoritmo MVA {Inizializzazione};

For j:=M'+1 to M" do Nj:=0;

For j:=M"+1 to M do Pj(0):=1;

{Inizio ciclo sul numero di utenti};

For k:=1 to K do

{calcolo del tempo medio di risposta};

begin T:=0;

For j:=1 to M' do begin Rj:=1 / µj;

T:=T + ej Rj;

end;

For j:=M'+1 to M’’ do begin

Rj:= (1 / µj) (1 + Nj);

T:=T+ ej Rj;

end;

For j:=M"+1 to M do begin

Rj:=0;

For i:=1 to k do Rj:= Rj+i (Pj(i-1) / µj(i));

Rj:=Rj / µj;

T:=T+ ej Rj;

end;

{calcolo del throughput};

T:=k/T;

For j:=1 to M do Xj:= ejT;

{calcolo della lunghezza media di alcune code};

For j:=M'+1 to M’" do Nj:=Xj Rj;

For j:=M"+1 to M do begin

For i:=k downto 1 do Pj(i):=Xj (Pj(i-1) / µj(i));

Pj(0):=Pj(0) X1 / X1 M-(j) (k);

end;

{Fine ciclo utenti};

{Calcolo delle rimanenti lunghezze medie di coda};

For j:=1 to M', M" to M do Nj:=Xj Rj;

{Utilizzazione};

For j:=1 to M' do Uj:=0;

For j:=M'+1 to M" do Uj:=Xj / µj;

For J:=M" +1 to M do begin Uj:=0;

For k:=1 to K do Uj:= Uj + min(k, mj) Pj(k);

Uj:= Uj / mj end;

{Fine MVA}.

Fig. 5.7 - Algoritmo MVA -

Sostituendo la formula (5.16) con la formula (5.17) nello schema ricorsivo si definisce l’algoritmo MVA modificato (MMVA).

Questo algoritmo fornisce maggiore stabilità numerica dell’algoritmo MVA a scapito di una maggiore complessità computazionale. Applicando l’algoritmo MMVA ad una rete con J nodi a velocità di servizio dipendente dal carico occorre risolvere 2J-1 reti diverse per ottenere i throughput addizionali utilizzati nella formula (5.17).

La Fig. 5.7 mostra la versione Pascal-like dell’algoritmo MMVA, dati i throughput addizionali X1M-(j)(k) (1≤k≤K) per ogni nodo j a velocità di servizio dipendente dal carico, M"+1≤j≤M.

5.3Metodi di aggregazione e decomposizione

I modelli di sistemi di grandi dimensioni difficilmente possono essere analizzati tramite metodologie dirette di analisi a causa dell’elevata complessità computazionale richiesta. Una più appropriata analisi del sistema si basa su un approccio di modellamento gerarchico, introdotto nel capitolo 1, sezione 4, che consiste in un insieme di modelli del sistema definiti a diversi livelli di astrazione, in relazione gerarchica fra loro in termini di componenti del modello. Tale approccio modellistico permette sia di ridurre la complessità computazionale dell’analisi del modello, grazie alla riduzione delle dimensioni dello stesso, sia l’applicazione di diverse metodologie di analisi dei modelli ai diversi livelli di astrazione. La catena gerarchica dei modelli è definita sulla base del principio di decomposizione ed aggregazione, che si basa sull’applicazione del naturale principio del “divide et impera”.

Un metodo di decomposizione e aggregazione (DA) si articola in tre passi, secondo lo schema seguente:

1. decomposizione del modello del sistema in modelli di sottosistemi, detti sottomodelli; analisi separata dei sottomodelli;

2. aggregazione: costruzione del modello aggregato ottenuto dal modello originale sostituendo ogni sottomodello con un’unica componente aggregata;

3. analisi del modello aggregato.

Il passo di decomposizione consiste nella identificazione di una partizione del modello del sistema. Tale partizione può essere guidata da una particolare struttura del sistema o può basarsi su criteri di efficienza di analisi dei sottomodelli. Il problema del partizionamento ottimo è, come noto, un problema intrinsecamente

determinazione di appropriate partizioni, basati su diversi fattori [MIR 94]. Fra i fattori più importanti è da citare la proprietà di decomponibilità del sistema. Un sistema si dice decomponibile o quasi-completamente-decomponibile, se è possibile identificare una partizione in sottosistemi tali che le interazioni interne sono molto più forti rispetto alle interazioni fra i sottosistemi. Le interazioni fra i sottosistemi, seppur esistenti, sono trascurabili, ovvero inferiori di almeno un ordine di grandezza, rispetto a quelle interne. Questa proprietà è verificata da una classe molto ampia di sistemi, sia naturali che artificiali [COU 77].

Il passo di aggregazione si basa sulla sostituzione dei sottomodelli con un’unica componente aggregata. Informalmente, il modello aggregato così ottenuto è detto equivalente al modello originale se il loro comportamento è coerente. Più precisamente, i due modelli sono equivalenti rispetto a determinati indici di prestazione, se per essi si ricavano gli stessi risultati dalla analisi dei due modelli. Se il modello aggregato è equivalente al modello originale, si dice che il metodo di aggregazione è esatto, altrimenti si dice approssimato. Per un metodo di aggregazione approssimato può essere nota una soglia all’errore introdotto. Sono stati proposti metodi di aggregazione approssimata a precisione nota che forniscono risultati accettabili specialmente per sistemi quasi completamente decomponibili. Un’altra categoria dei metodi di aggregazione è costituito dai metodi bound, che forniscono un risultato non puntale, ma in termini di intervallo che contiene il risultato esatto.

I metodi di aggregazione sono di utile applicazione quando si vuole effettuare una analisi parametrica del sistema modellato. In tal caso soltanto il sottoinsieme invariante può essere aggregato in un’unica componente ottenendo un modello aggregato di ridotta dimensione sul quale effettuare l’analisi parametrica.

Lo schema basilare del metodo DA può essere applicato a più livelli di gerarchia riapplicando il metodo DA all’analisi dei sottomodelli al passo 1. Consideriamo metodi DA esatti, approssimati e bound alle due seguenti categorie di modelli:

• processi stocastici

• modelli a rete di code.

In particolare definiamo un metodo di aggregazione esatto per i processi Markoviani e uno per la classe di modelli a rete di code in forma prodotto. E’

interessante notare che gli algoritmi di analisi delle reti in forma prodotto (ed esempio Convoluzione ed MVA) possono essere visti a loro volta come metodi di aggregazione esatta.

5.3.1 Metodi di aggregazione su processi stocastici

Consideriamo la classe dei processi stocastici Markoviani omogenei a tempo continuo

e spazio discreto, introdotti nel capitolo 2. I processi a tempo discreto possono essere trattati in modo simile.

Sia E lo spazio degli stati del processo, n la sua cardinalità e Q il generatore infinitesimale. Assumiamo che E sia partizionato in N sottoinsiemi S(I), 1≤I≤N, dove S(I) è formato da n(I) stati, Σ1≤I≤N n(I)=n. In accordo a tale partizione di E la matrice Q può essere scritta come segue

Q=

Q₁₁ L Q1N

M O M Q_N1 L QNN

















Il vettore delle probabilità stazionarie di stato π è partizionato in N sottovettori πI 1≤I≤N, dove πI è relativo al sottoinsieme S(I) e πI(i) indica l’i-esima componente, 1≤i≤n(I). Sia XI la probabilità aggregata del sottoinsieme S(I), ovvero XI = || πI ||1.

Sia πIC la probabilità condizionata del sottoinsieme S(I), ovvero πIC = πI / || πI ||.

Per definizione possiamo scrivere

πI= XI πIC (5.18)

per 1≤I≤N.

Aggregazione esatta

Il metodo di aggregazione esatta sul processo Markoviano si basa sulla valutazione della distribuzione π tramite la formula (5.18) considerando separatamente XI e πIC. Riordinando righe e colonne di Q in modo che gli stati del sottoinsieme S(I) siano i primi, possiamo scrivere la matrice Q come segue

Q= ^S(I) {

E−S(I) {

Q_II E_I F_I G_I



 



  (5.19).

Si può dimostrare che πIC è soluzione del seguente sistema lineare:

πIC Q(I) = 0 (5.20)

con la condizione di normalizzazione || πIC ||1=1 e dove

Q(I) = QII - EI GI-1 FI (5.21).

La probabilità aggregata X=(X1 … XN) è soluzione del seguente sistema lineare

dove QA = [qijA], con

q_ij^A = π_I^C Q_IJ 1^T = π_I^C(i)

i=1

n(I)∑ ^{QIJ(i, j)}

j=1 n(J)∑

e QIJ (i,j) denota l’elemento della riga i e colonna j della sottomatrice QIJ, i∈S(I), j∈S(J).

Il modello aggregato è il processo Markoviano omogeneo a tempo continuo con spazio degli stati {1,…, N} e generatore infinitesimale QA.

La dimostrazione di correttezza di questo metodo di aggregazione si ottiene considerando il sistema lineare π Q= 0 che per la formula (5.19) può essere riscritto come:

π_IQ_II+π ˆ _IE_I=0 π_IF_I +π ˆ _IG_I=0

 



dove ˆ π _I è ottenuto dal vettore π eliminando il sottovettore πI. Per sostituzione si ottiene immediatamente la formula (5.20) per la probabilità condizionata πIC.

Utilizzando questo risultato nella definizione dalla matrice aggregata QA si ricava qijA=(πI / XI) QIJ 1T, che rende il sistema (5.22) verificato.

Le formule (5.20) e (5.22) definiscono l’aggregazione esatta per processi Markoviani. Occorre notare che la soluzione del sistema lineare (5.20) richiede il calcolo della matrice Q(I) dalla formula (5.21), in cui compare l’inversa di GI. Tale matrice ha ordine |E-S(I)|= n-n(I) che è paragonabile all’ordine |E|=n dell’intera matrice Q.

Ne consegue che, anche se l’aggregazione esatta del processo riduce la soluzione di un sistema lineare di ordine n alla soluzione di N sistemi lineari di ordine n(I)<<n, 1≤I≤N, ed un sistema di ordine N. Tuttavia, sfortunatamente il calcolo della matrice GI porta ad un aumento della complessità computazionale che rende di fatto il metodo non vantaggioso. E’ spesso necessario ricorrere quindi ai metodi approssimati.

Aggregazione approssimata e bound

I metodi di aggregazione approssimata si basano su una valutazione approssimata della distribuzione πIC. Un semplice metodo si ottiene approssimando la matrice Q(I), 1≤I≤N, nel sistema (5.20) come segue

Q(I) = QII.

Di conseguenza dal sistema (5.20) si ottiene una approssimazione di πIC, da cui si ricava QA, la soluzione X del sistema (5.22) e la soluzione approssimata dell’intero modello dalla formula (5.18).

Per sistemi quasi-completamente-decomponibili si può dimostrare che l’errore di approssimazione introdotto da tale metodo è di O(ε), dove ε è detto massimo grado di accoppiamento fra sottosistemi ed è dato da

ε =max_{i∈S(I),j∈S(J)}

J=1,J≠I

∑N ^{QIJ(i, j)} j=1

n(J)∑ ^.

ε rappresenta una misura della massima interazione fra sottosistemi [COU 77].

A titolo di esempio riportiamo il metodo di DA di Takahashi.

Data una approssimazione iniziale πIC(0), 1≤I≤N, poniamo m=1. Il metodo è iterativo e si articola su tre passi.

1. Definizione di QA(m) = [qijA(m) ], qijA(m-1)= π_I^C(m-1) Q_IJ 1^T 1≤I,J≤N.

2. Calcolo di X(m-1) dal sistema lineare X(m-1) QA(m-1) = 0 . 3. Calcolo di πIC(m) dagli N sistemi lineari

z_I^(m)=z_I^(m)Q_II + X_J

J∑<I ^{(m−1)πIC(m)QJI+ XJ} J>I

∑ ^{(m−1)πIC(m−1)QJI}

π_I^C(m)=z_I^(m) z_I^(m)

1 1≤I≤N



 

 

Questo schema iterativo è applicato su m utilizzando un criterio di terminazione basato su un test di convergenza. Al termine si ottiene la soluzione approssimata

πI= XI(m-1) πIC(m)

per 1≤I≤N, il cui errore di approssimazione è ridotto di un fattore δ ad ogni iterazione, dove assumiamo ||QII||1=O(1), ||QIJ||1=O(δ), I≠J, 1≤I,J≤N.

Questi metodi sono applicabili anche a sistemi che non godono della proprietà di decomponibilità, ma per questi forniscono risultati più accurati ed una veloce convergenza.

Sono inoltre stati proposti metodi che permettono di ottenere una soluzione in termini di intervallo, detti anche metodi bound applicabili sotto ipotesi generali a processi Markoviani omogenei [CS 84].

5.3.2 Metodi di aggregazione per modelli di code

Consideriamo la classe dei modelli a rete di code introdotta nel capitolo 4. I metodi di aggregazione si basano sul teorema del flusso equivalente o teorema di Norton che fornisce risultati esatti per la classe di reti in forma prodotto. Per le reti non in forma prodotto l’applicazione diretta del metodo basato sul teorema di Norton produce una aggregazione approssimata.

Consideriamo un modello a rete di code di tipo BCMP chiusa e classe singola definita nel capitolo precedente, con M nodi, K utenti, matrice delle probabilità di diramazione P, vettore dei throughput relativi e e velocità di servizio µ j per il nodo j, 1≤j≤M. La distribuzione di stato stazionaria è esprimibile in forma prodotto.

Aggregazione esatta

Assumiamo di partizionare la rete in due sottoinsiemi, considerando la seguente partizione dei nodi: S = {1,…, m} S' = {m+1,…, M}. La matrice delle probabilità di diramazione fra i nodi può essere riscritta come segue

P= ^S{

S'{

A B

C D



 



  (5.23)

Il metodo di aggregazione definisce un nuovo modello a rete di code chiuso formato da m+1 centri di servizio, ottenuto dal modello originale aggregando la sottorete S' in un unico nodo denominato C. La nuova rete aggregata è costituita dai nodi S∪{C}={1,…,m,C}, K utenti ed ha matrice di routing PA. I nodi di S sono definiti come nella rete originale. Il nodo C è definito come un nodo BCMP, per esempio di tipo (1), ovvero con disciplina di servizio FIFO e distribuzione del tempo di servizio esponenziale a velocità dipendente dallo stato µj(k), 1≤k≤K.

Definiamo la matrice PA = [pijA] , i,j∈S∪{C} come segue:

pijA= pij 1≤i,j≤m

p_iC^A = p_ij

j=m+1

∑M 1≤i≤m

p_{C i}^A =

e_jp_ji

j=m+1

∑M

e_jp_js

j=m+1

∑M s=1

∑m 1≤i≤m

(5.24)

p_CCA= 0

Il modello aggregato ha distribuzione di probabilità di stato πA espressa dalla seguente forma prodotto

π^A(n) = 1

G^A f_i(n_i)

i=1

∏m ^fC(nC)

dove le funzioni fj(n) per i nodi, 1≤j≤m, n>0, sono definite come per la rete originale e la funzione f_C(n) = (e_C / µ_C)n, n>0.

Il metodo di aggregazione esatta si basa sul seguente teorema stabilisce l’equivalenza fra il modello originale ed il modello aggregato [CHW 75, BI 82]. I due modelli sono equivalenti se hanno la stessa probabilità di stato dei nodi della sottorete S. Di conseguenza i modelli sono equivalenti anche in termini di indici medi di prestazione. Il seguente teorema, di cui omettiamo la dimostrazione, è noto come teorema di Norton, per analogia con il teorema di Norton per reti elettriche, o teorema del flusso equivalente e si applica alla classe di reti in forma prodotto.

Teorema di Norton

Sia dato un modello a rete di code in forma prodotto partizionato nelle due sottoreti S ed S' con matrice delle probabilità di diramazione P, funzioni dei nodi fj(n) per ogni nodo j e probabilità di stato π. Si consideri il modello aggregato ottenuto dal modello originale sostituendo la sottorete S' con un unico nodo C con disciplina di servizio FIFO e distribuzione del tempo di servizio esponenziale con tasso dipendente dal carico µ_C(n) definito come segue

µ_C(n) = X_j(n)

j∈∑S' ^pji i∈∑S

dove Xj(n) denota il throughput del nodo j∈S, quando nella rete circolano n utenti, la matrice delle probabilità di transizione P' è definita dalla formula (5.24) e le funzioni dei nodi di S sono definite come nella rete originale. Sia πA la probabilità di stato.

Allora i due modelli sono equivalenti, ovvero

π^A(n₁,..., n_m, n_C)= π(n) n: n_j

j∈S'

∑

∑

Aggregazione approssimata e bound

I metodi di aggregazione approssimata proposti in letteratura per i modelli a rete di code non in forma prodotto sono prevalentemente a precisione ignota. Sono stati proposti numerosi algoritmi approssimati convalidati tramite simulazione o sulla base di un confronto sperimentale con risultati esatti [BD 93, CS 78, MAR 79, KAN 92, JAI 90, LAV 83, SC 79, LZG 84]. Fra questi ampia applicazione ha avuto il metodo iterativo proposto da Marie [MAR 79]. La maggior parte di tali algoritmi si basa sulla applicazione forzata del teorema di Norton e sono caratterizzati da una bassa complessità computazionale, tuttavia senza informazione sull’errore introdotto.

Un diverso approccio è quello dei metodi bound [CS 84, STE 83] che forniscono un intervallo per i parametri della rete aggregata per una classe di modelli a rete di code Markoviane. Scegliendo un valore dei parametri del modello aggregato in tale intervallo si può definire un metodo di aggregazione approssimata ad errore noto.

Un algoritmo iterativo recentemente proposto [BUC 94] utilizza la struttura inerentemente gerarchica di alcuni sistemi per definire modelli di code strutturati ad albero in cui sottomodelli hanno comportamenti quasi indipendenti.