Si chiamano Markoviani i sistemi a coda in cui processo di arrivo e processo di servizio sono entrambi senza memoria. Grazie al capitolo 4 sappiamo che essi sono processi di nascita e morte, e che quindi le probabilità di stato si ottengono in forma chiusa. Non resta che specificare, caso per caso, le frequenze λk e μk.
Le slide organizzano la trattazione in due grandi famiglie, con motivazioni applicative diverse:
| Famiglia | Caratteristiche | Modelli tipici per |
|---|---|---|
| Caso generale con servitori multipli | molteplicità di risorse disponibili, possibilità di servire più utenti contemporaneamente, con o senza spazio di attesa | reti a commutazione di circuito; sistemi con allocazione statica della banda; centralini telefonici e call center |
| Caso particolare a singolo servitore | un solo servitore con spazio di attesa, infinito o finito | multiplatore statistico, cioè l'interfaccia di uscita di un router |
Questo capitolo copre i sistemi senza spazio di attesa, cioè puramente a perdita; il capitolo 6 quelli con attesa. La divisione non è casuale: sono due mondi con due domande diverse. Nei sistemi a perdita si chiede «quanti utenti rifiuto?»; in quelli con attesa «quanto fanno aspettare?».
Il primo modello è il sistema ideale senza spazio di attesa, cioè M/M/∞: un sistema a risorse infinite, in cui il servizio è immediatamente disponibile per ogni utente e lo spazio di attesa non viene mai usato.
Le frequenze di transizione sono λk = λ per ogni k (gli arrivi non dipendono dallo stato) e μk = kμ, perché nello stato k ci sono esattamente k servitori occupati. Applicando la formula del processo di nascita e morte si ottengono le probabilità di stato:
Pₖ = (A₀ᵏ / k!) e⁻᳐₀ con A₀ = λ&thetas;̄ = λ/μIl numero di utenti nel sistema è dunque distribuito secondo una legge di Poisson di media A0. Ne discendono tre conseguenze immediate:
λp = 0, λs = λ, As = A0;η̄ = 0, δ̄ = &thetas;̄, Aq = 0 e quindi A = As = A0.In un sistema del genere non c'è mai congestione. Può però essere utile conoscere la probabilità di avere almeno m utenti nel sistema: è la domanda «quante risorse dovrei avere per non rifiutare quasi mai nessuno?». La risposta è la formula A di Erlang:
A(m, A₀) = ∑ₖ₀ᶜₘ∞ (A₀ᵏ / k!) e⁻᳐₀ = Prob{ k ≥ m }La formula A si usa come stima ottimistica del dimensionamento: dice quanto spesso un sistema con risorse illimitate supererebbe la soglia m. Non è la probabilità di blocco di un sistema reale, perché in un sistema reale gli stati oltre m non esistono e la probabilità che vi cadeva si redistribuisce sugli stati ammessi. Confrontare A(m,A0) con B(m,A0) sullo stesso A0 è un buon modo per capire l'effetto del troncamento.
Il sistema reale senza spazio di attesa è M/M/m/0: risorse limitate a m servitori, servizio immediatamente disponibile per l'utente che trova almeno un servitore libero, nessuno spazio di attesa. È quindi un sistema a perdita: chi trova tutto occupato se ne va.
Le frequenze di transizione sono le stesse del caso ideale, ma la catena si ferma a m: λk = λ per k < m e zero da lì in poi, μk = kμ. Le probabilità di stato sono la troncatura normalizzata della Poisson:
Pₖ = (A₀ᵏ / k!) / ∑⫺₀ᶜᵐ (A₀⫺ / j!) k = 0, 1, …, mIl sistema è sempre stabile, qualunque sia A0: essendoci un numero finito di stati, non c'è nulla che possa divergere. La probabilità di blocco è la probabilità dello stato in cui tutti i servitori sono occupati, cioè Pm, ed è la celebre formula B di Erlang:
(A₀ᵐ / m!)
B(m, A₀) = ——————————————
∑⫺₀ᶜᵐ (A₀⫺ / j!)Dalla probabilità di blocco discende tutto il resto del bilancio del sistema:
πₚ = B(m, A₀)
λₛ = λ (1 − πₚ) Aₛ = A₀ (1 − πₚ) Aₚ = A₀ πₚ
assenza di attesa ⇒ η̄ = 0, δ̄ = &thetas;̄, A = Aₛ
utilizzazione: ρ = Aₛ/m = A₀(1 − πₚ) / mLa sequenza da avere in automatico: A0 → B(m,A0) → As → ρ. Nelle prove scritte i valori di B non si calcolano, si leggono nelle tabelle allegate, arrotondando il traffico come indicato dal testo (a volte alla prima cifra decimale, a volte all'intero superiore). Il verso dell'arrotondamento cambia il risultato: leggi sempre con attenzione la consegna.
La formula B ha un problema numerico evidente: contiene fattoriali di m, che per m di qualche decina esplodono. Per questo la si calcola in forma ricorsiva, partendo dal caso banale di un solo servitore e salendo:
B(0, A₀) = 1
A₀ ⋅ B(m−1, A₀)
B(m, A₀) = —————————————————
m + A₀ ⋅ B(m−1, A₀)Non compaiono più fattoriali né potenze: solo una moltiplicazione e una divisione per ogni passo. È la forma con cui la funzione viene effettivamente implementata, ed è anche quella che permette di dimensionare il sistema: dato un certo valore di traffico e una probabilità di blocco desiderata, si aumenta m di uno alla volta finché la condizione non è soddisfatta, e si prende il primo m che ci riesce.
È esattamente il procedimento richiesto dagli esercizi: «determinare il numero minimo di linee tale che B(m, A0) ≤ π0».
La ricorsione ha anche una lettura fisica. Il denominatore m + A0B(m−1,A0) dice che aggiungere l'm-esimo servitore riduce la probabilità di blocco tanto più quanto più m è grande rispetto al traffico che ancora sfugge. È la forma matematica del rendimento decrescente: i primi servitori servono moltissimo, gli ultimi quasi a nulla.
Le slide dedicano diverse figure a un unico messaggio, che è forse il più importante del capitolo dal punto di vista progettuale.
A parità di probabilità di blocco garantita, i sistemi più grandi, soggetti a maggior traffico, raggiungono una utilizzazione maggiore dei servitori.
Il fenomeno si osserva su due grafici complementari. Il primo riporta l'utilizzazione ρ in funzione di A0, scegliendo per ogni valore di traffico il numero m minimo che garantisce la probabilità di blocco fissata: la curva sale. Il secondo riporta il numero minimo di servitori m necessario in funzione di A0: la curva cresce, ma meno rapidamente di A0. Raddoppiare il traffico non richiede di raddoppiare le risorse.
Le slide non si fermano all'elogio dell'aggregazione, e aggiungono l'avvertenza che rende il ragionamento onesto:
I sistemi più grandi sono più sensibili alle fluttuazioni di traffico. Avere servitori maggiormente utilizzati significa avere a disposizione meno risorse pronte a smaltire eventuale traffico in eccesso.
È lo stesso compromesso che ricomparirà, in altra forma, nel controllo di congestione TCP: un sistema che lavora vicino alla saturazione è efficiente ma fragile, perché non ha margine. Un centralino con undici linee e utilizzazione del 45% assorbe senza accorgersene un picco del 20%; uno con utilizzazione dell'85% lo trasforma immediatamente in chiamate perdute.
La sensibilità si quantifica facilmente con la formula B: basta ricalcolare B(m, 1.1⋅A0) a parità di m. Nell'esercizio 10, un incremento del traffico del solo 10% fa salire la probabilità di blocco da 8.29⋅10−3 a 1.44⋅10−2: un incremento relativo di circa il 74%, benché in termini assoluti si resti nell'ordine del punto percentuale.
Finora si è assunto, come da ipotesi generale del capitolo 3, che l'utente scelga a caso uno dei servitori liberi: il carico si distribuisce quindi uniformemente e tutti i servitori hanno la stessa utilizzazione ρ. Le slide osservano allora lo stesso sistema M/M/m/0 sotto una ipotesi di lavoro diversa, detta call packing:
Il carico non è più uniformemente distribuito. Per calcolare quanto lavora il singolo servitore i si usa un artificio elegante: si confrontano due sistemi immaginari, uno con i−1 servitori e uno con i. Il traffico perduto considerando solo i primi i−1 servitori vale A0B(i−1, A0); aggiungendo anche il servitore i il traffico perduto scende a A0B(i, A0). La differenza è precisamente il traffico che il servitore i riesce a recuperare, cioè il traffico da lui smaltito e quindi la sua utilizzazione:
ρᵢ = A₀ [ B(i−1, A₀) − B(i, A₀) ]Il risultato mostrato a lezione è netto: l'ultimo servitore è utilizzato per una frazione di tempo pari a qualche punto percentuale. Il primo servitore lavora quasi sempre, l'ultimo quasi mai, ed è la stessa cosa vista dalla ricorsione: gli ultimi servitori esistono solo per assorbire la coda estrema della distribuzione.
L'ultimo risultato della sezione a perdita è il più sorprendente, e va imparato come enunciato.
Si può dimostrare che la formula B di Erlang non dipende dalla distribuzione del tempo di servizio, ma solo dal suo valor medio. Di conseguenza B(m, A0) è la probabilità di blocco di un sistema M/G/m/0, non soltanto di un M/M/m/0.
È una proprietà detta di insensibilità, ed è una fortuna enorme dal punto di vista applicativo: significa che si può dimensionare un centralino, o un gruppo di circuiti, senza conoscere nulla della forma della distribuzione delle durate delle chiamate. Basta la media.
Le slide precisano anche dove la distribuzione conta invece davvero: essa influisce, attraverso il suo valore quadratico medio, soltanto sul tempo medio di servizio residuo, che però mostra i suoi effetti solo in presenza di uno spazio di attesa. Il che è perfettamente coerente: se nessuno aspetta, a nessuno importa quanto manchi alla fine del servizio in corso. È il capitolo 7 a raccogliere questa osservazione e a farne la formula di Pollaczek–Khinchine.
Il centralino (PABX) di un'azienda fornisce accesso a 100 utenti con un traffico offerto stimato per utente pari a A0u = 0.05 E. Il centralino non offre funzionalità di messa in attesa e opera a commutazione di circuito: se tutte le linee sono occupate la chiamata in ingresso viene bloccata. Obiettivo: πp ≤ 1%.
Passo 1 — traffico offerto complessivo. I traffici dei singoli utenti si sommano:
A₀ = 0.05 ⋅ 100 = 5 EPasso 2 — numero minimo di linee. Assumendo che le chiamate nel loro complesso si comportino come un processo di Poisson, la probabilità di blocco è data dalla formula B. Si procede in maniera iterativa:
B(8, 5) = 7.01 ⋅ 10⁻²
B(9, 5) = 3.75 ⋅ 10⁻²
B(10, 5) = 1.84 ⋅ 10⁻²
B(11, 5) = 8.29 ⋅ 10⁻³ ≤ 0.01 ✓
⇒ m = 11 lineePasso 3 — utilizzazione. Con m = 11 il traffico smaltito e l'utilizzazione valgono:
Aₛ = A₀(1 − πₚ) ≈ 4.96 E
ρ = Aₛ/m ≈ 0.45Per valori relativamente piccoli di A0 e m l'utilizzazione media dei servitori risulta piuttosto bassa, in questo caso inferiore al 50%. È il rovescio dell'efficienza di aggregazione, visto dal lato dei sistemi piccoli.
Passo 4 — guasto di una linea. Se una linea va fuori servizio si scende a m = 10:
π′ₚ = B(10, 5) = 1.84 ⋅ 10⁻² ρ′ = A₀(1 − π′ₚ)/10 = 0.49La probabilità di blocco è di poco superiore al limite prefissato, e l'utilizzazione è leggermente migliore ma ancora bassa.
Passo 5 — crescita del traffico del 10%. Con m = 11 e A0 = 5.5 E:
B(11, 5.5) = 1.44 ⋅ 10⁻²Un incremento relativo della probabilità di blocco di circa il 74%, che però in termini assoluti resta nell'ordine di un punto percentuale. È il numero che quantifica l'avvertenza della sezione 6.
Gli esercizi 11 e 12 dello stesso foglio estendono il metodo: il primo alla pianificazione pluriennale di gruppi di circuiti fra due centrali (si ricalcola A0 anno per anno con un tasso di crescita e si ridimensiona m), il secondo al caso di una chiamata che attraversa due collegamenti in cascata, per cui la probabilità di blocco complessiva si compone a partire da quelle dei due tratti. Il tema del compito d'esame numero 2 e numero 3 è esattamente questo.
Secondo una legge di Poisson di media A0: Pk = (A0k/k!)e−A0. Si ricava dal processo di nascita e morte con λk = λ e μk = kμ. Il sistema è sempre stabile, non ha perdite (As = A0) e non ha attesa (δ̄ = &thetas;̄, A = A0).
La probabilità di avere almeno m utenti in un sistema a risorse infinite: A(m,A0) = ∑k≥m(A0k/k!)e−A0. Non è una probabilità di blocco, perché in un M/M/∞ non c'è mai congestione; è la coda della distribuzione di Poisson oltre la soglia m.
B(m,A0) = (A0m/m!) / ∑j=0m(A0j/j!). È la probabilità dello stato in cui tutti gli m servitori sono occupati in un sistema M/M/m/0, e quindi la probabilità di blocco di una chiamata in arrivo. Le probabilità di stato sono la troncatura normalizzata della Poisson del sistema ideale.
Per la proprietà PASTA del capitolo 4: con arrivi di Poisson, call congestion e time congestion coincidono. Senza arrivi di Poisson le due grandezze differirebbero, come mostra il controesempio del sistema con popolazione finita p = m, in cui la time congestion è positiva ma la call congestion è nulla.
B(0,A0) = 1 e B(m,A0) = A0B(m−1,A0) / [m + A0B(m−1,A0)]. Si usa perché elimina i fattoriali e le potenze, che per m di qualche decina causano overflow numerico, e perché rende immediato il dimensionamento: si incrementa m finché la probabilità di blocco non scende sotto la soglia richiesta.
As = A0(1 − πp) e ρ = As/m = A0(1 − πp)/m. Il traffico perduto è Ap = A0πp. Poiché non c'è attesa, vale anche δ̄ = &thetas;̄ e A = As.
A parità di probabilità di blocco garantita, i sistemi più grandi soggetti a maggior traffico raggiungono una utilizzazione maggiore: il numero minimo di servitori cresce meno rapidamente del traffico offerto. Il prezzo è che i sistemi grandi sono più sensibili alle fluttuazioni: servitori più utilizzati significa meno risorse pronte ad assorbire traffico in eccesso.
È l'ipotesi per cui i servitori sono ordinati da 1 a m, un nuovo utente viene sempre servito dal servitore libero di indice minore, e quando un servizio termina gli altri utenti scalano verso gli indici inferiori. Il carico non è più uniformemente distribuito: l'utilizzazione del servitore i vale ρi = A0[B(i−1,A0) − B(i,A0)], e l'ultimo servitore risulta utilizzato per qualche punto percentuale soltanto. La somma resta comunque pari al traffico smaltito.
No: si può dimostrare che dipende solo dal valor medio del tempo di servizio. Perciò B(m,A0) è la probabilità di blocco di un sistema M/G/m/0 qualunque. La distribuzione influisce, attraverso il valore quadratico medio, soltanto sul tempo medio di servizio residuo, che però ha effetto solo in presenza di spazio di attesa.
A0u = 0.05 E ciascuno. Quante linee servono per πp ≤ 1%?Traffico complessivo A0 = 0.05 ⋅ 100 = 5 E. Iterando la formula B: B(10,5) = 1.84⋅10−2 è ancora troppo, B(11,5) = 8.29⋅10−3 ≤ 0.01. Servono 11 linee, con As ≈ 4.96 E e ρ ≈ 0.45.
Con m = 11 invariato e A0 = 5.5 E si ottiene B(11, 5.5) = 1.44⋅10−2: un incremento relativo di circa il 74% della probabilità di blocco, che in termini assoluti resta però nell'ordine del punto percentuale. È l'esempio numerico della sensibilità alle fluttuazioni.
δ̄ = &thetas;̄?Perché non c'è spazio di attesa: chi entra viene servito immediatamente, chi non può essere servito viene rifiutato e non entra affatto. Il tempo di permanenza coincide quindi con il tempo di servizio, il tempo di attesa è nullo e il numero medio di utenti in coda è zero, per cui A = As.