User Tools

Site Tools


wip:approxqnblocking:start

Soluzione numerica approssimata di reti di code multiclasse con blocco

Scopo

Scopo di questo lavoro è di verificare l'algoritmo proposto da Luigi Bovino per la soluzione numerica approssimata di reti di code aperte multiclasse con blocco (l'algoritmo è descritto nella sezione 10.2 della sua tesi di laurea). L'algoritmo rappresenta una estensione di quello per reti analoghe, pero' a singola classe, di Lee, Bouhchouch, Dallery e Frein (Performance Evaluation of open queueing networks with arbitrary configuration and finite buffers) [1].

L'idea è di reimplementare l'algoritmo di Luigi utilizzando un apposito linguaggio per computazioni numeriche (ad esempio GNU Octave) confrontando i risultati con quelli ottenuti su una analoga rete mediante simulazione.

Dove si trova il codice

L'implementazione Octave dell'algoritmo di Lee et al. (versione a classe singola) fa parte del queueing toolbox (nella directory ./devel). Al momento l'implementazione non produce i risultati corretti in tutti i test, e ovviamente non implementa le estensioni di Luigi Bovino per il caso multiclasse.

L'implementazione Java dell'algoritmo multiclasse (realizzata dallo stesso Luigi Bovino) si trova nella directory libcppsim/qn/java di libcppsim.tar.gz. Il resto di quella directory contiene il (vecchio) codice della libreria libcppsim, all'interno della quale c'e' una bozza di implementazione di simulatore di reti di code multiclasse con blocco che avrebbe dovuto essere utilizzata per validare l'algoritmo di Bovino. Prima di rimettere mano al simulatore è opportuno verificare che quel particolare tipo di reti di code non possa già essere analizzato con JMT.

Come testare l'implementazione

È necessario procurarsi una versione recente di GNU Octave. Fare riferimento a questa pagina per ottenere i binari per la propria piattaforma (Linux/Windows/MacOSX).

L'algoritmo originale di Lee et al. è contenuto nel file lee_et_al_98.m che si trova nella directory ./broken. Il contenuto del file dovrebbe essere sufficientemente autoesplicativo, con le funzioni adeguatamente commentate. Molte (ma non tutte) delle funzioni contengono gia' dei piccoli test per verificarne la correttezza su alcuni semplici esempi. Per eseguire questi test, dal prompt di Octave è necessario dare i comandi:

source "lee_et_al_98.m"
test "lee_et_al_98.m"

Se tutto funziona correttamente, a video dovrebbe comparire qualcosa come:

PASSES 12 out of 12 tests

Nel file sono anche contenuti una serie di demo. Le demo consistono nel calcolare le probabilità di stato di alcune reti di code analizzate negli articoli di Lee e Pollock [2] e Lee et al. [1], al fine di confrontare il risultato calcolato dall'implementazione Octave con il risultato approssimato fornito dagli stessi autori. Per eseguire le demo è necessario dare i comandi:

source "lee_et_al_98.m"
demo "lee_et_al_98.m"

L'output di questi comandi assomiglierà al seguente:

Table V Lee, Pollock [2]
Converged in 8 iterations
     Param      Exact    This  Err%     Paper  Err%  Res
    P_1(0)      0.156   0.196  25.8     0.152  -2.8 FAIL
    P_1(1)      0.130   0.158  21.9     0.129  -0.8 FAIL
    P_1(2)      0.108   0.127  17.5     0.109   0.6 FAIL
    P_1(3)      0.091   0.103  12.4     0.093   1.3 FAIL
    P_1(4)      0.077   0.083   7.2     0.079   1.8 FAIL
    P_1(5)      0.065   0.067   2.0     0.067   1.8 PASS
...

L'intestazione indica che si tratta dei risultati relativi all'esempio descritto nella Tabella V di [2]. L'algoritmo converge dopo 8 iterazioni e fornisce i risultati descritti sotto. La colonna Param indica il parametro da valutare; in generale P_i(n) indica la probabilità che nel centro di servizio Si ci siano esattamente n utenti, con n variabile tra 0 e la capacità di Si.

La colonna Exact indica il valore “esatto” per quel parametro, calcolato dagli autori dell'articolo mediante simulazione.

La colonna This indica il valore approssimato calcolato dalla nostra implementazione Octave. La colonna Err% indica l'errore percentuale della stima calcolata dalla nostra implementazione.

Infine, la colonna Paper indica il valore approssimato calcolato dagli autori (si presume con la loro implementazione dell'algoritmo numerico). La colonna Err% indica l'errore percentuale della loro stima.

Ovviamente, se tutto funzionasse correttamente si dovrebbe avere che This == Paper, nel senso che la nostra implementazione dell'algoritmo dovrebbe fornire esattamente gli stessi risultati (approssimati, naturalmente) forniti nel paper. Purtroppo, per i parametri la cui ultima colonna riporta FAIL ciò non è vero: la nostra implementazione fornisce un risultato diverso almeno fino alle terza cifra decimale.

Riferimenti

  1. H.S. Lee, A. Bouhchouch, Y. Dallery and Y. Frein, Performance evaluation of open queueing networks with arbitrary configuration and finite buffers, Annals of Operations Research, 79(1998) 181–206
  2. Hyo-Seong Lee, Stephen M. Pollock, Approximation Analysis of Open Acyclic Exponential Queueing Networks with Blocking, Operations Research, vol. 38, n. 6 (nov-dec 1990), pp. 1123-1134
  3. Luigi Bovino, Modelli a rete di code multiclasse, Laurea triennale in Informatica, Università Ca' Foscari di Venezia
wip/approxqnblocking/start.txt · Last modified: 2012/06/21 12:32 by moreno