ρ = 1− p0. (1.2.24)
Dimostrazione: Moltiplicando ambo i membri della (1.2.21) per λ si ha λT = λTq+ λ/µ,
che per le relazioni fondamentali equivale a
N = Nq+ ρ. (1.2.25)
Ora sostituendo il valore di Nq dato dalla (1.2.23) nella (1.2.25) si ottiene la (1.2.24).
La relazione (1.2.24) ha una interpretazione immediata; infatti, poich´e p0 `e la probabilit`a che nel sistema non vi siano utenti e che quindi il servente `e inoperoso, il complemento ad 1 di p0 rappresenta l’operosit`a del servente.
Questi risultati, ed in particolare la formula di Little hanno una interpretazione immediata in riferimento a casi molto semplici; ad esempio, il traffico cittadino nelle ore di punta si muove pi`u lentamente (ovvero T `e grande) e le strade sono pi`u affollate (ovvero N `e grande). Analogamente in un fast–food, (ovvero in un sistema con T piccolo) le sale possono essere pi`u piccole (ovvero N `e piccolo) di quelle di un ristorante tradizionale a parit`a di frequenza di arrivo dei clienti.
Esempio 1.2.5 Consideriamo un sistema di controllo di flusso di dati su rete che deve inviare pacchetti supponendo che il tempo dell’acnowledgement sia trascurabile. Sulla rete devono trovarsi N pacchetti quindi non appena il pacchetto i `e arrivato a destinazione, il pacchetto i + N `e immediatamento introdotto nella rete. Poich´e il numero di pacchetti nel sistema `e sempre N la formula di Little ci permette di affermare che la frequenza di arrivo dei pacchetti nel sistema λ e il tempo medio di permanenza di un pacchetto nella rete sono collegati dalla relazione N = λT . Quindi se nella rete c’`e congestione e T aumenta, λ deve diminuire. Inoltre se la rete `e congestionata e in grado di consegnare solo λ pacchetti per unit`a di tempo, aumentando N avrebbe come risultato solamente un aumento del tempo di permanenza nella rete T .
Si deve comunque prestare molta attenzione nell’applicare la formula di Little ad alcuni casi particolari, alla luce di quanto riportato nella Osservazione 1.2.2.
Riportiamo di seguito un esempio in cui il sistema non raggiunge l’equilibrio.
Esempio 1.2.6 Un pacchetto arriva su un linea di trasmissione ogni k secondi (il primo pac-chetto arriva al tempo 0). Tutti i pacchetti hanno stessa lunghezza e richiedono αk secondi per la trasmissione con α < 1. Il tempo affinch´e un pacchetto arrivi a destinazione `e pari a p secondi. La frequenza di arrivo `e λ = 1/k e poich´e i pacchetti arrivano ad intervalli regolari, non c’`e tempo di attesa in coda quindi il tempo T che un pacchetto rimane nel sistema `e T = αk + p.
Applicando la formula di Little si ottiene N = λT = α + p/k.
Questo esempio necessita di una corretta interpretazione in quanto nel sistema descritto n(t) `e una funzione deterministica del tempo t e non converge a nessun valore, quindi non si raggiunge la condizione di equilibrio. Tuttavia, la formula di Little pu`o avere una valida interpretazione anche in questo caso, nel senso che N non pu`o essere inteso come nella (1.2.5), ma solamente come media temporale su tempi lunghi ovvero N = lim
t→∞
∫t
0n(τ )dτ
t .
Concludiamo questo paragrafo soffermandoci sull’importanza di disporre dei va-lori della probabilit`a pk per effettuare l’analisi di un sistema a coda. Infatti, Importante
conoscere pk
conoscendo pk utilizzando le (1.2.1), (1.2.2), il Teorema di Little (1.2.14), la (1.2.20) e la (1.2.21) si possono determinare tutte le grandezze che sono le misure di prestazione del sistema.
1.3 MODELLI STOCASTICI DEI PROCESSI DI ARRIVO E DI SERVIZIO
Da quanto visto nei precedenti paragrafi, emerge chiaramente come un sistema di code sia caratterizzato fondamentalmente da due processi stocastici : il processo degli arrivi caratterizzato dalla distribuzione di probabilit`a dei tempi di interar-rivo e il processo di servizio caratterizzato dalla distribuzione di probabilit`a dei tempi di servizio.
Per definire un sistema di code `e necessario specificare entrambe le distribuzioni ora menzionate. In un sistema reale queste distribuzioni possono assumere qual-siasi forma e per formulare un modello basato su un sistema di code che rappre-senti un sistema reale `e necessario che le distribuzioni di probabilit`a assunte nella costruzione del modello siano quanto pi`u possibile realistiche. Al tempo stesso esse devono essere sufficientemente semplici e matematicamente trattabili. Sulla base di queste considerazioni la distribuzione di probabilit`a che maggiormente viene presa in considerazione nella teoria delle code `e la distribuzione esponen-ziale. Cercheremo di chiarire i motivi di questa scelta attraverso l’illustrazione delle propriet`a di cui questa distribuzione gode. La principale riguarda la cosid-detta “assenza di memoria”. Formalizzeremo questa propriet`a mostrando anche che la distribuzione esponenziale `e l’unica distribuzione che gode di questa pro-priet`a. Per quanto riguarda l’applicazione alla teoria delle code, tale propriet`a `e molto utile perch´e un arrivo in un sistema di code non `e influenzato da quando si
`
e verificato l’ultimo arrivo e cos`ı anche per il tempo di servizio, il tempo mancante al completamento pu`o essere indipendente da quando il servizio `e iniziato.
Infine introdurremo il processo di Poisson, di fondamentale importanza per rap-presentare il processo degli arrivi, descrivendo le sue propriet`a fondamentali.
1.3.1 La distribuzione esponenziale e le sue propriet`a
Ricordiamo innanzitutto che una variabile aleatoria continua X ha una distribu-zione esponenziale con parametro α se la sua densit`a di probabilit`a fX(t) `e data da
fX(t) =
{αe−αt per t≥ 0 0 per t < 0.
La funzione di distribuzione `e FX(t) = P (X ≤ t) =
{1− e−αt per t≥ 0
0 per t < 0
e valore atteso e varianza sono date da E(X) = 1
α, V ar(X) = 1
α2.
Per comprendere bene quali implicazioni ha su un modello di code l’assunzione che le distribuzioni dei tempi sono esponenziali, riportiamo alcune ben note
pro-priet`a fondamentali della distribuzione esponenziale. Sia quindi X una variabile aleatoria avente distribuzione esponenziale ed fX(t) la corrispondente densit`a di probabilit`a.
Propriet`a E1: La densit`a di probabilit`a fX(t) `e una funzione strettamente decrescente di t (t≥ 0)
Questa propriet`a discende immediatamente dalla definizione della fX(t). Una immediata conseguenza di questa propriet`a `e che, per ogni ∆t > 0 e t > 0 risulta P (0≤ X ≤ ∆t) > P (t ≤ X ≤ t + ∆t) . (1.3.1) Questa conseguenza si ottiene ricordando che P (a ≤ X ≤ b) =
∫ b
a
fX(x)dx rappresenta l’area racchiusa tra l’asse delle ascisse e il grafico della fX(t).
La (1.3.1) pu`o essere interpretata nel senso che `e maggiore la probabilit`a che la X assuma valori prossimi allo zero. In un modello di code, se X rappresenta il tempo di servizio, il fatto che questa propriet`a sia ragionevole dipende molto dalla tipologia del servizio stesso. In alcuni casi, pu`o essere vero che il tempo del servizio `e di solito molto breve con pochi casi in cui il servizio `e pi`u lungo.
Propriet`a E2: Assenza di memoria. Per ogni t > 0 e s > 0, vale la Questa propriet`a pu`o essere interpretata come assenza di memoria nel senso che se, ad esempio, il tempo di durata di un’apparecchiatura `e distribuito esponen-zialmente, allora un apparecchiatura che `e gi`a in uso da un certo numero di ore
`
e “buona” tanto quanto una nuova in termini di tempo totale di durata prima della sua rottura, ovvero l’apparecchiatura “non ricorda” di essere stata gi`a in uso per un certo numero di ore.
Nell’ambito della teoria delle code, questa propriet`a si pu`o interpretare nel seguen-te modo: la distribuzione di probabilit`a del tempo che rimane fino ad un evento (arrivo o completamento del servizio) `e sempre la stessa indipendentemente da quanto tempo `e trascorso, ovvero il processo “dimentica” il passato. Per quanto riguarda gli intertempi di arrivo, questa propriet`a descrive la situazione comune in cui il tempo fino al prossimo arrivo non `e assolutamente influenzato da quando si `e verificato l’ultimo arrivo. Per quanto riguarda i tempi di servizio questa pro-priet`a pu`o essere interpretata nel senso che il tempo mancante al completamento di un servizio pu`o essere indipendente da quando il servizio `e iniziato.
E importante notare che la distribuzione esponenziale `` e l’unica distribuzione con-tinua che gode della Propriet`a E2. Questo si dimostra facilmente nel seguente modo: vogliamo far vedere che se X `e una variabile aleatoria per la quale vale la Propriet`a E2, allora X `e distribuita esponenzialmente. Innanzitutto osserviamo che la relazione di assenza di memoria (1.3.2) per la (1.3.3) pu`o essere riscritta
P (X > s + t) = P (X > s)P (X > t). (1.3.4) Se ora introduciamo la funzione S(x) = P (X > x) = 1−FX(x), la (1.3.4) equivale a scrivere
S(s + t) = S(s)S(t), ovvero S(x) soddisfa l’equazione funzionale
g(x + y) = g(x)g(y). (1.3.5)
Poich´e `e noto che l’equazione (1.3.5) ammette come unica soluzione continua da destra g(x) = e−αx, la dimostrazione `e completata. Infatti risulta S(x) = e−αx ovvero
FX(t) = 1− e−αt e quindi X `e distribuita esponenzialmente.
Propriet`a E3: Siano X1, X2, . . . , Xn variabili aleatorie indipendenti di-stribuite esponenzialmente con parametri α1, α2, . . . , αn. Sia U la variabile aleatoria definita da U = min{X1, X2, . . . , Xn}. U `e distribuita esponenzial-mente con parametro α =
∑n i=1
αi.
Questa propriet`a discende immediatamente dal fatto che per l’indipendenza vale
P (U > t) = P (X1 > t, X2 > t, . . . , Xn> t)
= P (X1 > t)P (X2 > t)· · · P (Xn> t)
= e−α1te−α2t· · · e−αnt
= e−∑ni=1αit.
Si noti che se Xirappresenta il tempo mancante fino a che accada un certo evento, U rappresenta il tempo fino a che il primo degli eventi accada.
La Propriet`a E3 ha una importante interpretazione per quanto riguarda i tempi di servizio. Supponiamo infatti di avere s serventi in parallelo ciascuno dei quali ha tempi di servizio distribuiti esponenzialmente con lo stesso parametro µ. In questo caso, sia r ≤ s il numero dei serventi che stanno attualmente fornendo il servizio, e Xi il tempo che rimane per il completamento del servizio da parte di ciascun servente (i = 1, . . . , r). Si ha che Xi, per la Propriet`a E2 `e dis-tribuita esponenzialmente con parametro αi = µ e U che rappresenta il tempo fino al prossimo completamento di un servizio ha distribuzione esponenziale con parametro rµ. Ci`o significa che un sistema di code con pi`u serventi in paral-lelo che stanno attualmente operando (continuously busy servers), ciascuno con tempo di servizio distribuito esponenzialmente di parametro µ, si comporta come un sistema a singolo servente con tempo di servizio distribuito esponenzialmente con parametro rµ.
Propriet`a E4: Sia X una variabile aleatoria distribuita esponenzialmente di parametro α. Per ogni t > 0 vale
P (
X≤ t + ∆t X > t)
= α∆t + o(∆t) dove o(∆t) indica un infinitesimo di ordine superiore a ∆t.
Questa proposizione si ottiene facilmente dal fatto che per ogni t≥ 0 risulta P (X ≤ t + ∆t|X > t) = 1 − P (X > t + ∆t|X > t) = 1 − P (X > ∆t) =
= P (X ≤ ∆t) = 1 − e−α∆t e utilizzando lo sviluppo in serie dell’esponenziale si ha
P (X ≤ t + ∆t|X > t) = 1 − 1 + α∆t + o(∆t) = α∆t + o(∆t).
Quindi, in virt`u di questa propriet`a, per piccoli valori di ∆t, si ha P
(
X≤ t + ∆t X > t)
≈ α∆t.
Interpretando X come tempo dall’ultimo evento (arrivo o completamento del servizio) fino al prossimo evento, supponiamo che un tempo t sia gi`a passato senza che l’evento sia accaduto. Dalla Propriet`a E2 sappiamo che la probabilit`a che l’evento accadr`a entro il prossimo intervallo di tempo di lunghezza fissata
∆t `e una costante indipendentemente dal valore di t. La Propriet`a E4 afferma inoltre che quando il valore di ∆t `e piccolo, questa probabilit`a costante pu`o essere approssimata da α∆t, ovvero questa probabilit`a `e proporzionale a ∆t di un fattore α.
Propriet`a E5: Siano date k variabili aleatorie X1, X2, . . . , Xk indipendenti aventi identica distribuzione esponenziale di parametro α. Allora la loro somma
Sk = X1+ X2+· · · + Xk
ha la seguente densit`a di probabilit`a fSk(t) = αk
(k− 1)!e−αttk−1.
La dimostrazione di questa propriet`a pu`o essere fatta per induzione. Infatti essa
`
e banalmente vera per k = 1. Supponiamo quindi che sia vera per k− 1, ovvero che
fX1+···+Xk−1(t) = αk−1
(k− 2)!e−αttk−2 = αe−αt (αt)k−2 (k− 2)!
e dimostriamo che vale per k. Infatti si ha fSk(t) = fX1+···+Xk−1+Tk(t) =
Per quanto riguarda un sistema di code, la Propriet`a E5 pu`o essere interpretata nel senso che se il servizio richiesto da un cliente richiede l’impiego di k serventi in serie i cui tempi di servizio sono identicamente distribuiti esponenzialmente con parametro α (oppure l’impiego dello stesso servente k volte), il tempo di servizio totale seguir`a la distribuzione della somma dei tempi servizio.
La distribuzione di probabilit`a avente per densit`a di probabilit`a la fSk si chiama distribuzione di Erlang di parametri α e k che, ad eccezione della restrizione dell’interezza di k, coincide con la distribuzione Gamma.
1.3.2 Il processo di Poisson
In questo paragrafo introduciamo il processo di Poisson che ha, in generale, una grande importanza per due aspetti fondamentali: innanzitutto molti fenomeni fisici possono essere rappresentati attraverso tale processo; inoltre, il processo di Poisson gode di interessanti ed utili propriet`a che consentono numerose semplifi-cazioni nella trattazione analitica. In riferimento alla teoria delle code, il processo di Poisson `e un importante strumento per la modellizzazione dei processi di ar-rivo. Prima di definire un processo di Poisson, introduciamo un concetto che risulter`a molto utile nel seguito.
Definizione 1.3.1 Un processo stocastico {X(t), t ≥ 0} `e detto processo di conteggio (counting process) se X(t) rappresenta il numero totale di eventi che accadono fino all’istante t.
E un processo che “conta” il numero totale di aventi accaduti fino al tempo t. Si` tratta di un processo stocastico a tempo continuo e a stati discreti. Esempi di processi di conteggio sono:
a) il numero delle persone entrate in un supermercato fino al tempo t b) il numero di persone nate fino al tempo t
c) il numero di goal realizzati da un giocatore nella sua carriera fino al tempo t Non `e invece un processo di conteggio il numero delle persone presenti in un supermercato al tempo t.
Si verifica immediatamente che per un processo di conteggio valgono le seguenti propriet`a:
1. X(t)≥ 0 per ogni t ≥ 0 2. X(t) `e a valori interi 3. se s≤ t allora X(s) ≤ X(t)
4. per s < t, X(t)−X(s) `e il numero degli eventi che sono accaduti nell’intervallo (s, t).
Riportiamo, di seguito, due definizioni che introducono due concetti caratteriz-zanti un processo di conteggio.
Definizione 1.3.2 Un processo di conteggio ha incrementi indipendenti se