Il sistema con spazio di attesa infinito M/M/m ha risorse limitate a m servitori, ma chi li trova tutti occupati non viene rifiutato: va in coda. Essendo lo spazio di attesa infinito non si ha mai perdita, quindi λp = 0 e λs = λ.
Le frequenze di transizione differiscono da quelle del capitolo 5 in un solo punto, ma decisivo: superato lo stato m, la frequenza di servizio smette di crescere, perché i servitori sono finiti.
Le probabilità di stato si ottengono al solito dal processo di nascita e morte:
Pₖ = (A₀ᵏ / k!) ⋅ P₀ k ≤ m
Pₖ = A₀ᵏ / (m! ⋅ mᵏ⁻ᵐ) ⋅ P₀ k > m
con P₀ determinato dalla normalizzazione ∑ₖ Pₖ = 1Il sistema è stabile solo se A0 < m, cioè ρ = A0/m < 1. È la prima volta nel corso che la stabilità va verificata: nel capitolo 5 i sistemi erano sempre stabili perché la catena era finita. Qui la catena è infinita, e se il traffico offerto supera la capacità la serie che definisce P0 non converge. Negli esercizi questa verifica va fatta per prima.
Qui la congestione non è più un rifiuto ma un'attesa: si definisce probabilità di congestione la probabilità di essere in uno stato in cui tutti i servitori sono occupati e l'utente deve quindi fare attesa. È la formula C di Erlang:
C(m, A₀) = Prob{ k ≥ m } = ∑ₖ₀ᶜₘ∞ PₖLa formula C si può calcolare anche tramite la formula B, e questa è la via che si segue in pratica perché consente di riutilizzare le tabelle e la ricorsione del capitolo 5:
m ⋅ B(m, A₀)
C(m, A₀) = ——————————————————————
m − A₀ [ 1 − B(m, A₀) ]Le due formule rispondono a due domande diverse, e confonderle è l'errore più costoso della prova scritta. B è la probabilità che una chiamata venga persa (sistema senza coda). C è la probabilità che una chiamata debba attendere (sistema con coda). A parità di m e A0 vale sempre C > B, perché nel sistema con coda gli stati oltre m esistono e portano via probabilità agli stati bassi.
Nota C, tutto il resto discende dal teorema di Little e dalla struttura del sistema. Vale la pena imparare queste cinque righe come un blocco unico:
numero medio di utenti in coda Aₜ = C ⋅ A₀ / (m − A₀)
traffico medio nel sistema A = A₀ + Aₜ
tempo medio di attesa in coda
di un utente generico η̄ = Aₜ/λ = C ⋅ &thetas;̄ / (m − A₀)
tempo medio di attesa in coda
per chi va effettivamente in coda ε̄ = η̄/C = &thetas;̄ / (m − A₀)
tempo medio di permanenza δ̄ = &thetas;̄ + η̄La distinzione fra η̄ e ε̄ è quella che negli esercizi separa la risposta giusta da quella sbagliata. η̄ media su tutti gli utenti, compresi quelli che non aspettano affatto e contribuiscono con uno zero; ε̄ media solo su chi ha effettivamente atteso. Il legame è semplice: η̄ = C ⋅ ε̄, cioè il tempo medio complessivo è il tempo di chi aspetta pesato dalla probabilità di aspettare.
Un'ultima osservazione delle slide, tutt'altro che secondaria: questi valori medi sono validi per qualunque disciplina di servizio. FIFO, LIFO o scelta casuale danno esattamente gli stessi valori medi; cambiano solo le distribuzioni. È la stessa idea che nel capitolo 7 diventerà la legge di conservazione di Kleinrock.
Come nel capitolo 5 si dimensionava m imponendo una probabilità di blocco, qui lo si dimensiona imponendo un tempo di attesa. Le slide distinguono due criteri, che corrispondono alle due medie appena viste:
| Criterio | Condizione | Interpretazione |
|---|---|---|
| sul tempo medio di attesa di un utente generico | numero minimo di m tale che η̄ ≤ η0 |
obiettivo sulla qualità media complessiva del servizio |
| sul tempo medio di attesa di chi va in coda | numero minimo di m tale che ε̄ ≤ ε0 |
obiettivo sull'esperienza di chi è effettivamente costretto ad aspettare |
Il secondo criterio è più severo del primo, ed è quello che si usa quando la promessa contrattuale riguarda l'utente insoddisfatto: «nessuno aspetterà più di tre minuti» è un'affermazione su ε, non su η.
Sotto l'ipotesi aggiuntiva di disciplina di coda FIFO, si può fare un passo oltre le medie e ricavare la distribuzione del tempo di attesa. Il risultato è di rara eleganza: entrambe le distribuzioni sono esponenziali, con lo stesso esponente.
utente che va in coda: Fᵩ(ε₀) = 1 − e⁻⁽ᵐᵐ₋ᵏ⁾ᵩ₀
utente generico: Fᵗ(η₀) = 1 − C ⋅ e⁻⁽ᵐᵐ₋ᵏ⁾ᵗ₀La grandezza mμ − λ è la capacità di smaltimento residua del sistema quando tutti i servitori sono occupati: quanto più margine resta, tanto più rapidamente la coda si scarica. Le due espressioni differiscono solo per il fattore C, che è la probabilità di dover aspettare: l'utente generico ha una probabilità 1 − C di attendere zero.
Da qui discende il criterio di dimensionamento più fine, quello sulla distribuzione: il numero minimo di servitori tale che il tempo di attesa in coda sia inferiore a un certo valore con una certa probabilità minima. Imponendo Fε(ε0) ≥ π0 si ricava, come mostrato nell'esercizio 13:
1 − e⁻⁽ᵐᵐ₋ᵏ⁾ᵩ₀ ≥ π₀
⇒ mμ − λ ≥ −ln(1 − π₀) / ε₀
⇒ m ≥ (1/μ) [ λ − ln(1 − π₀)/ε₀ ]Questa formula chiusa è una scorciatoia preziosa: dà m senza iterare sulle tabelle. Nell'esercizio del call center universitario permette di passare, in una riga, da «60 operatori distribuiti» a «23 operatori centralizzati». Ed è particolarmente istruttivo il fatto che il criterio sulla distribuzione di ε non dipenda dalla formula C: dipende solo da λ, μ e dal margine mμ − λ.
Il caso m = 1 merita un trattamento a parte, non perché sia più semplice ma perché è il modello del multiplatore statistico, cioè dell'interfaccia di uscita di un router. È il sistema che comparirà in ogni esercizio sulle reti a pacchetto.
Con un solo servitore le frequenze sono λk = λ e μk = μ, costanti. Il traffico offerto coincide con l'utilizzazione, e le probabilità di stato diventano una geometrica:
A₀ = λ/μ = ρ
Pₖ = (1 − ρ) ρᵏ
stabile solo se ρ < 1La probabilità di congestione è la probabilità che il servitore sia occupato, cioè che l'utente che arriva debba fare attesa:
πᵣ = Prob{ k ≥ 1 } = 1 − P₀ = ρ che corrisponde a C(1, A₀)Gli indici medi si ottengono dalle formule generali dell'M/M/m ponendo m = 1, oppure direttamente dalla geometrica:
Aₜ = ρ² / (1 − ρ) numero medio di utenti in coda
A = ρ / (1 − ρ) traffico medio nel sistema
δ̄ = &thetas;̄ / (1 − ρ) = 1/(μ − λ) tempo medio di permanenza
η̄ = ρ &thetas;̄ / (1 − ρ) attesa media di un utente generico
ε̄ = &thetas;̄ / (1 − ρ) attesa media per chi va in codaSi noti che ε̄ = δ̄: chi trova il servitore occupato aspetta in media quanto un utente generico passa complessivamente nel sistema. È una coincidenza numerica specifica dell'M/M/1, dovuta all'assenza di memoria del servizio in corso.
Sotto ipotesi FIFO si ricavano anche le distribuzioni, ancora una volta esponenziali:
Fδ(t) = 1 − e⁻⁽ᵐ₋ᵏ⁾ᵗ Fᵗ(t) = 1 − ρ e⁻⁽ᵐ₋ᵏ⁾ᵗ1 − ρ è la sola ragione di questa forma: quando l'utilizzazione si avvicina a uno, il margine di smaltimento si annulla e ogni grandezza media diverge.Il risultato P0 = 1 − ρ è stato ricavato per l'M/M/1, ma le slide dimostrano che vale in generale per qualunque sistema a coda ergodico a singolo servitore in cui il tempo medio interarrivo e il tempo medio di servizio siano finiti. La dimostrazione è un piccolo capolavoro di contabilità, e vale la pena seguirla per intero.
Si osservi il sistema per un tempo T e si definiscano:
B(T) + I(T) = T;Per un sistema ergodico il servitore è libero esattamente per la frazione di tempo P0, e le partenze si contano dividendo il tempo di lavoro per il tempo medio di servizio:
B(T) = T (1 − P₀) I(T) = T P₀
d(T) = B(T)/E[&thetas;] = T (1 − P₀) μ
a(T) = λT
equilibrio statistico: d(T) = a(T)
⇒ T (1 − P₀) μ = λT ⇒ P₀ = 1 − λ/μ = 1 − ρNessuna ipotesi di Poisson, nessuna ipotesi di esponenzialità: solo ergodicità e medie finite. È lo stesso stile di ragionamento del teorema di Little, e la conclusione è altrettanto robusta. In pratica: su un singolo servitore, la frazione di tempo in cui è occupato è sempre ρ, quale che sia la statistica del traffico. Questo risultato verrà usato senza esitazione nel capitolo 7 per l'M/G/1.
Fin qui abbiamo studiato un nodo isolato. Ma una rete è fatta di nodi in cascata, e la domanda naturale è: che cosa esce da una coda? Se l'uscita di un nodo alimenta il nodo successivo, occorre sapere che tipo di processo essa sia.
Le slide ragionano sul tempo che intercorre fra due partenze successive, distinguendo due casi:
1 − ρ), la partenza successiva ci sarà dopo un tempo interarrivo seguito da un tempo di servizio, cioè τ + &thetas;.La densità di probabilità del tempo tra due partenze successive è quindi la miscela pesata delle due, e il calcolo porta a un risultato notevole, il teorema di Burke (valido anche per m > 1):
Il processo delle partenze da un sistema con coda infinita è un processo di Poisson simile a quello degli arrivi.
La conseguenza pratica è enorme: si può studiare una catena di nodi trattandoli uno per uno, perché ciascuno riceve in ingresso un processo di Poisson. È esattamente ciò che si fa nell'esercizio 18, in cui il sistema di monitoraggio a valle dei concentratori IoT viene studiato come un M/M/1 «facendo uso del teorema di Burke».
Le slide aggiungono un'osservazione che vale la pena non dimenticare: anche se vale il teorema di Burke, a valle di una coda a singolo servitore cade l'ipotesi di tempi di servizio indipendenti dagli arrivi. La coda a singolo servitore «serializza» gli utenti in ingresso: un pacchetto lungo occupa a lungo il servitore, e quindi il pacchetto che lo segue arriva al nodo successivo dopo un intervallo correlato alla propria dimensione. L'approssimazione torna buona quando il secondo nodo raccoglie traffico da molte sorgenti indipendenti.
Le slide propongono un confronto a parità di carico e di capacità totale, in tre configurazioni. È l'equivalente, nel mondo con attesa, dell'efficienza di aggregazione del capitolo 5.
| # | Configurazione | Traffico offerto |
|---|---|---|
| 1 | m sistemi M/M/1 separati, ciascuno con frequenza di servizio μ0 e arrivi λ0 | A0 = ρ0 = λ0/μ0 per ciascuno |
| 2 | unico sistema M/M/m, con frequenza di servizio μ0 per servitore e arrivi mλ0 |
A0 = mλ0/μ0 = mρ0 |
| 3 | unico sistema M/M/1 con frequenza di servizio mμ0 e arrivi mλ0 |
A0 = mλ0/(mμ0) = ρ0 |
Tutte e tre hanno la stessa utilizzazione ρ0 e la stessa capacità complessiva, ma prestazioni molto diverse. La configurazione 3, cioè il servitore unico più veloce, è la migliore: un solo pacchetto per volta ma servito m volte più in fretta, e nessuna possibilità che una coda sia piena mentre un altro servitore è inattivo. La configurazione 2 sta in mezzo: condivide la coda, quindi non spreca servitori, ma ogni singolo servizio resta lento. La configurazione 1 è la peggiore: m code separate che non possono aiutarsi a vicenda.
Questo confronto compare quasi letteralmente nell'ultimo punto del quesito sul load balancing di un router: «confrontare i valori ottenuti con quelli che si otterrebbero se il router fosse dotato di un'unica interfaccia di uscita di capacità pari alla somma delle capacità delle tre interfacce». La risposta attesa è la configurazione 3, e va motivata, non solo calcolata.
Ultimo modello del capitolo, e il più realistico per un router: un singolo servitore con spazio di attesa finito pari a L posti. L'utente che trova il servitore occupato va in coda; l'utente che trova anche la coda piena viene bloccato.
Gli stati vanno da 0 a L+1 (i posti di attesa più quello in servizio), e le probabilità di stato sono una geometrica troncata e normalizzata:
Pₖ = A₀ᵏ (1 − A₀) / (1 − A₀ᴴ⁺²) A₀ ≠ 1
probabilità di blocco: πₚ = Pᴴ⁺₁
probabilità di congestione: πᵣ = 1 − P₀Il sistema è sempre stabile, perché gli stati sono in numero finito: non c'è più bisogno di imporre ρ < 1. Ma questa apparente comodità nasconde il risultato più importante della sezione, sottolineato esplicitamente a lezione:
Per A0 > 1 non è possibile dimensionare L per ottenere una probabilità di blocco piccola a piacere. Aggiungendo memoria si riduce la perdita solo fino a un certo punto: se il traffico offerto eccede la capacità di smaltimento, una frazione irriducibile del traffico dovrà comunque essere scartata. La memoria non crea capacità.
È la traduzione quantitativa di ciò che il capitolo 1 aveva anticipato a parole: buffer grandi non risolvono la congestione, la trasformano in ritardo, e oltre un certo punto neppure quello. Il rimedio non può stare nel nodo, deve stare nella sorgente: è il controllo di congestione della Parte III.
Un'università fornisce informazioni agli studenti tramite call center. L'ateneo ha 12 facoltà: 6 «grandi» con circa 10 000 studenti ciascuna e 6 «medie» con circa 6 000. Il call center opera 5 ore al giorno per 25 giorni al mese; le chiamate arrivano secondo un processo di Poisson e hanno durata esponenziale con media &thetas;̄ = 3 min; ogni studente chiama in media una volta al mese con probabilità 0.5. Si confrontano tre scelte progettuali.
Traffico offerto per facoltà.
facoltà medie: λᵐ = 6000 ⋅ 0.5 / (25 ⋅ 5) = 24 ch/h = 0.4 ch/min
A₀ᵐ = λᵐ &thetas;̄ = 1.2 E
facoltà grandi: λₗ = 10000 ⋅ 0.5 / (25 ⋅ 5) = 40 ch/h = 0.667 ch/min
A₀ₗ = λₗ &thetas;̄ = 2 EUn call center per facoltà, senza spazio di attesa, con obiettivo πp ≤ 5%. Si applica la formula B di Erlang cercando il minimo m:
medie: B(3, 1.2) = 0.09 B(4, 1.2) = 0.026 → mᵐ = 4
grandi: B(4, 2) = 0.095 B(5, 2) = 0.037 → mₗ = 5
totale ateneo: 6 ⋅ 4 + 6 ⋅ 5 = 54 operatoriUn call center per facoltà, con spazio di attesa praticamente illimitato gestito FIFO, con obiettivo: chi fa effettivamente attesa deve aspettare ε ≤ ε0 = 3 min con probabilità π0 ≥ 95%. Si applica la distribuzione del tempo di attesa:
Fᵩ(ε₀) = 1 − e⁻⁽ᵐᵐ₋ᵏ⁾ᵩ₀ ≥ π₀
⇒ m ≥ (1/μ) [ λ − ln(1 − π₀)/ε₀ ]
medie: mᵐ ≥ 4.196 → mᵐ = 5
grandi: mₗ ≥ 4.996 → mₗ = 5
totale ateneo: 60 operatoriPoche unità in più rispetto al caso senza attesa, ma con il grosso vantaggio che quasi nessun utente resta senza servizio. Le probabilità di dover attendere sono infatti bassissime: C(5, 1.2) = 8.21⋅10−3 e C(5, 2) = 5.97⋅10−2. Il sistema è dimensionato in modo molto conservativo, come mostrano le utilizzazioni: ρm = 1.2/5 = 0.24 e ρl = 2/5 = 0.4.
Un unico call center centralizzato per l'intero ateneo, con lo stesso requisito di qualità del caso 2. Serve che ogni operatore sappia rispondere su tutte le facoltà, ma concentrando gli sforzi si ottengono prestazioni simili con molte meno risorse:
λ = 6λᵐ + 6λₗ = 6.4 ch/min
A₀ = 6A₀ᵐ + 6A₀ₗ = 19.2 E
stessa formula: m ≥ 22.196 → m = 23 operatori
C(23, 19.2) = 0.31 ρ = 19.2/23 = 0.835Meno della metà del totale ottenuto con i call center dedicati. Il prezzo è però visibile: molti più utenti finiscono in attesa (il 31% contro pochi punti percentuali), anche se con la stessa probabilità di aspettare più di tre minuti. È l'efficienza di aggregazione con il suo conto esatto: utilizzazione dal 24–40% all'83.5%, e margine per i picchi drasticamente ridotto.
Due LAN in sedi diverse sono collegate da terminali VPN con capacità garantita C = C0 = 100 Mbit/s. La capacità interna alle LAN è molto maggiore, per cui l'accodamento si verifica solo in uscita dal router verso il collegamento VPN. I pacchetti arrivano secondo Poisson con λ = 5000 pacchetti/s e hanno lunghezza esponenziale di media D = 800 byte.
&thetas;̄ = D/C₀ = 8 ⋅ 800 / (100 ⋅ 10⁶) = 64 µs
ρ = λ&thetas;̄ = 5000 ⋅ 64⋅10⁻⁶ = 0.32
ε̄ = &thetas;̄/(1 − ρ) = 94 µs (attesa per chi va in coda)Con una crescita del traffico del 40% annuo si ha λ(1) = 7000 e λ(2) = 9800 pacchetti/s. Imponendo di mantenere lo stesso livello di prestazioni, cioè ε̄ ≤ ε0 = 100 µs, si ricava in forma chiusa la capacità necessaria:
&thetas;̄ D/C
———— = ——————— ≤ ε₀ ⇒ C ≥ (D/ε₀)(1 + λε₀)
1 − ρ 1 − λD/C
C(1) = 108.8 Mbit/s C(2) = 126.7 Mbit/sPoiché la capacità si acquisisce solo in multipli di C0, il collegamento va dimensionato con C = 2C0 già all'istante t = 0, dato che C0 non basterebbe a coprire nemmeno il primo anno. Si verifica poi che 2C0 è sufficiente anche per tutto il secondo anno.
Questo è il modello di quesito più ricorrente del compito d'esame: si costruisce un M/M/1 dall'interfaccia di un router, si impone un requisito di qualità sul tempo di attesa, si inverte la formula rispetto a C e si arrotonda ai tagli di capacità commercialmente disponibili. Il passaggio delicato è ricordare che &thetas;̄ dipende da C, quindi C compare sia al numeratore sia al denominatore e va isolata con attenzione.
A0 < m, cioè ρ = A0/m < 1. Nel capitolo 5 la catena era finita (troncata a m), quindi la somma di normalizzazione era sempre una somma finita e il sistema era sempre stabile. Qui la catena è infinita: se il traffico offerto supera la capacità di smaltimento la serie non converge e la coda cresce indefinitamente.
La probabilità che un utente in arrivo debba fare attesa, cioè che tutti gli m servitori siano occupati in un sistema con coda: C(m,A0) = Prob{k ≥ m}. Si calcola con C(m,A0) = mB(m,A0) / [m − A0(1 − B(m,A0))]. A parità di m e A0 vale sempre C > B.
η̄ è il tempo medio di attesa di un utente generico, mediato anche su chi non aspetta affatto: η̄ = C&thetas;̄/(m − A0). ε̄ è il tempo medio di attesa per chi va effettivamente in coda: ε̄ = &thetas;̄/(m − A0). Sono legate da η̄ = C ⋅ ε̄.
Entrambi esponenzialmente, con esponente mμ − λ, cioè la capacità di smaltimento residua quando tutti i servitori sono occupati. Per chi va in coda: Fε(t) = 1 − e−(mμ−λ)t. Per l'utente generico: Fη(t) = 1 − C e−(mμ−λ)t, dove il fattore C tiene conto della probabilità 1 − C di non aspettare affatto.
Si impone 1 − e−(mμ−λ)ε0 ≥ π0, da cui mμ − λ ≥ −ln(1−π0)/ε0 e quindi m ≥ (1/μ)[λ − ln(1−π0)/ε0]. È una formula chiusa: non richiede di iterare sulle tabelle di Erlang.
Pk = (1−ρ)ρk, stabile per ρ < 1. Indici: A = ρ/(1−ρ), Aq = ρ²/(1−ρ), δ̄ = &thetas;̄/(1−ρ) = 1/(μ−λ), η̄ = ρ&thetas;̄/(1−ρ), ε̄ = &thetas;̄/(1−ρ). La probabilità di congestione, cioè di dover attendere, è semplicemente ρ.
P0 = 1 − ρ per un qualunque sistema a coda ergodico a singolo servitore.Si osserva il sistema per un tempo T. Il servitore è occupato per B(T) = T(1−P0) e libero per I(T) = TP0. Le partenze sono d(T) = B(T)/E[&thetas;] = T(1−P0)μ e gli arrivi a(T) = λT. In equilibrio statistico d(T) = a(T), quindi T(1−P0)μ = λT e P0 = 1 − λ/μ = 1 − ρ. Non servono ipotesi di Poisson né di esponenzialità: solo ergodicità e medie finite.
Il processo delle partenze da un sistema con coda infinita è un processo di Poisson simile a quello degli arrivi, e il risultato vale anche per m > 1. L'avvertenza: anche se Burke vale, a valle di una coda a singolo servitore cade l'ipotesi di tempi di servizio indipendenti dagli arrivi, perché la coda serializza gli utenti legando la lunghezza di un pacchetto all'intervallo che lo separa dal successivo. L'approssimazione torna buona se il nodo a valle raccoglie traffico da molte sorgenti indipendenti.
Il migliore è il terzo, l'M/M/1 con servitore m volte più veloce: serve un utente per volta ma in un tempo m volte inferiore, e ha traffico offerto ρ0 invece di mρ0. Il secondo (M/M/m) è intermedio: condivide la coda e quindi nessun servitore resta inattivo mentre qualcuno aspetta, ma ogni servizio resta lento. Il peggiore è il primo, perché m code separate non possono aiutarsi a vicenda: una può essere satura mentre un'altra è vuota.
A0 > 1?Perché la memoria non crea capacità di smaltimento. Se il traffico offerto eccede la capacità del servitore, in media arriva più di quanto possa uscire, e nessuna dimensione di L può assorbire uno squilibrio permanente: si riesce solo a ritardare le perdite, non a evitarle. Aumentare L abbassa la probabilità di blocco fino a un asintoto positivo, non a zero.
λ = 5000 pacchetti/s e pacchetti esponenziali di media 800 byte. Quanto attende chi va in coda?&thetas;̄ = 8⋅800/(100⋅106) = 64 µs, quindi ρ = λ&thetas;̄ = 0.32. L'attesa per chi effettivamente va in coda è ε̄ = &thetas;̄/(1−ρ) = 64/0.68 ≈ 94 µs. Nota che la probabilità di doverci andare è ρ = 32%, quindi l'attesa media di un pacchetto generico è η̄ = ρε̄ ≈ 30 µs.
Perché il criterio di qualità riguarda la durata dell'attesa, non la sua probabilità. Nel caso dell'esercizio 13 si passa da 60 operatori distribuiti a 23 centralizzati mantenendo lo stesso requisito su Prob{ε ≤ 3 min}, ma l'utilizzazione sale dal 24–40% all'83.5% e la probabilità di attendere passa da qualche punto percentuale al 31%. Si aspetta più spesso, ma non più a lungo.