Sistemi a coda M/M/1 e M/M/m

I sistemi markoviani sono quelli in cui sia gli arrivi sia i servizi sono senza memoria: arrivi di Poisson (Processi di arrivo e processo di PoissonUn sistema a coda ha clienti che arrivano, un'area di attesa e $m$ servitori. Il processo di arrivo è un processo di punto con tempi di interarrivo $\tau_n=t_n-t_{n-1}$ e tasso $\lambda=\frac1{E[\tau]}$. Nel processo di Poisson omogeneo gli arrivi in intervalli disgiunti sono indipendenti e di Poisson con media $\lambda T$, gli interarrivi sono esponenziali $\lambda e^{-\lambda a}$ e senza memoria; somma di processi di Poisson è Poisson (tassi che si sommano), il diradamento con probabilità $p$ dà Poisson di tasso $p\lambda$; in $[0,h]$ c'è un arrivo con probabilità $\lambda h+o(h)$. Servizio con tasso $\mu=\frac1{E[y]}$; notazione di Kendall $A/B/m/K/N-S$.Processi di arrivo e processo di Poisson →) e tempi di servizio esponenziali. Per loro lo stato del sistema ("quanti clienti ci sono") basta a predire l'evoluzione futura e si arriva a formule chiuse. Qui si ricavano le formule dell'M/M/1 e dell'M/M/m, e di alcuni modelli collegati (M/M/$\infty$, M/M/1/$K$). Il caso con servizio generale è in Sistemi a coda M-G-1 e formula di LittleMisure di un sistema a coda: occupazione $x=q+z$, tempi $s=w+y$, traffico offerto $G=\frac\lambda\mu$, fattore di carico $\rho=\frac\lambda{m\mu}$, throughput $\eta$ e throughput normalizzato $S=\frac\eta\mu$. Il sistema senza blocco è stabile se $\rho<1$ e allora $\eta=\lambda$, altrimenti $\eta=m\mu$. La formula di Little $E[x]=\lambda E[s]$ vale sempre (anche per la sola coda, $E[q]=\lambda E[w]$, e per il servizio, $E[z]=\lambda E[y]$). Per arrivi di Poisson e servizio generale (M/G/1) la formula di Pollaczek-Khinchin dà $E[w]=\frac{\lambda E[y^2]}{2(1-\rho)}$: con servizio esponenziale si ritrova l'M/M/1, con servizio costante (M/D/1) l'attesa si dimezza, $E[w]=\frac{\rho}{2\mu(1-\rho)}$.Sistemi a coda M-G-1 e formula di Little →, dove si definiscono anche le misure di prestazione usate qui ($x,q,z$, $s,w,y$, $\rho$, $G$, throughput) e si dimostra la formula di Little, che sotto è usata.

1. Il modello M/M/1 come catena di Markov

Il sistema M/M/1 ha arrivi di Poisson di tasso $\lambda$, servizi i.i.d. esponenziali di tasso $\mu$ (media $\frac1\mu$), un servitore, coda infinita, FCFS. Sia $x(t)$ il numero di clienti nel sistema (in coda più in servizio). Si studia che cosa può succedere in un intervallo piccolissimo $[t,t+h]$.

Arrivi. Come visto: $P[1\ \text{arrivo}]=\lambda h+o(h)$, $P[0]=1-\lambda h+o(h)$, $P[\ge2]=o(h)$ (e non dipendono dalla storia).

Partenze. Se il servitore è occupato, il tempo di servizio è esponenziale: per l'assenza di memoria il tempo residuo del cliente in servizio è ancora esponenziale di tasso $\mu$, qualunque sia il tempo già speso. Quindi, se $x(t)>0$, $P[1\ \text{partenza}]=\mu h+o(h)$ e $P[0]=1-\mu h+o(h)$. Se $x(t)=0$ non possono esserci partenze. (Equivalentemente si può pensare a un processo di partenze "virtuale" di Poisson di tasso $\mu$ che "scarta" i servizi quando il sistema è vuoto.)

Eventi simultanei. Un arrivo e una partenza nello stesso $h$ hanno probabilità $o(h)$ (prodotto di due quantità $O(h)$): si trascurano.

Ne segue che in $[t,t+h]$ lo stato cambia al più di $\pm1$: $$x\to x+1\ \text{con prob. }\lambda h,\qquad x\to x-1\ \text{con prob. }\mu h\ (x>0),\qquad x\to x\ \text{altrimenti.}$$ E la probabilità futura dipende solo dallo stato presente: $x(t)$ è una catena di Markov (processo di nascita e morte: le transizioni sono tra stati adiacenti; "nascita" = arrivo, "morte" = partenza).

        λ       λ       λ       λ
   0  ────→  1  ────→  2  ────→  3  ────→  …
      ←────    ←────    ←────    ←────
        μ       μ       μ       μ

2. Equazioni di equilibrio

Sia $p_k(t)=P[x(t)=k]$. Con il teorema della probabilità totale su $x(t)$, per $k\ge1$: $$p_k(t+h)=p_{k-1}(t)\,\lambda h+p_{k+1}(t)\,\mu h+p_k(t)\,\bigl(1-\lambda h-\mu h\bigr)+o(h),$$ (si arriva in $k$ da $k-1$ con una nascita, da $k+1$ con una morte, oppure si resta), e per $k=0$: $p_0(t+h)=p_0(t)(1-\lambda h)+p_1(t)\mu h+o(h)$. Si porta $p_k(t)$ a sinistra, si divide per $h$ e si fa $h\to0$: $$\frac{dp_k}{dt}=\lambda p_{k-1}+\mu p_{k+1}-(\lambda+\mu)p_k\ \ (k\ge1),\qquad\frac{dp_0}{dt}=\mu p_1-\lambda p_0.$$ Se il sistema è stabile esiste il limite $\pi_k=\lim_{t\to\infty}p_k(t)$ (probabilità stazionarie, indipendenti dallo stato iniziale), e a regime le derivate sono nulle: $$\lambda\pi_{k-1}+\mu\pi_{k+1}=(\lambda+\mu)\pi_k,\qquad\lambda\pi_0=\mu\pi_1.$$ Dalla seconda e dalla prima per $k=1$: $\mu\pi_2=(\lambda+\mu)\pi_1-\lambda\pi_0=\lambda\pi_1+(\mu\pi_1-\lambda\pi_0)=\lambda\pi_1$, e per induzione $$\boxed{\lambda\pi_{k-1}=\mu\pi_k\quad\forall k\ge1}$$ Sono i bilanci di flusso (flow balance, equilibri di taglio): a regime il numero di transizioni al secondo da $k-1$ a $k$ ($\lambda\pi_{k-1}$: "sono nello stato $k-1$ e arriva un cliente") eguaglia quello da $k$ a $k-1$ ($\mu\pi_k$: "sono in $k$ e ne parte uno"); se non fosse così la distribuzione continuerebbe a cambiare.

3. Soluzione dell'M/M/1

Dal bilancio $\pi_k=\rho\,\pi_{k-1}$ con $\rho=\frac\lambda\mu$, quindi $\pi_k=\rho^k\pi_0$. Le probabilità devono sommare a 1: $\sum_{k\ge0}\rho^k\pi_0=\frac{\pi_0}{1-\rho}=1$ (serie geometrica, Serie notevoli - geometrica, telescopica, armonicaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica →), che converge solo se $\rho<1$: è la condizione di stabilità, $\lambda<\mu$. Quindi $$\boxed{\pi_k=(1-\rho)\rho^k,\quad k=0,1,2,\dots}$$ (distribuzione geometrica, Distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →), con $\pi_0=1-\rho$ probabilità di sistema vuoto. Da qui:

Il numero di clienti in servizio è $E[z]=\rho$: per un servitore solo, $\rho$ è la frazione di tempo in cui è occupato. Il tempo di sistema è il tempo di servizio $\frac1\mu$ diviso per $(1-\rho)$: esplode per $\rho\to1$.

Esempio. Un collegamento da $1$ Mbit/s con pacchetti di lunghezza esponenziale di media $1000$ bit ha $\mu=\frac{10^6}{1000}=1000$ pacchetti/s. Con $\lambda=800$ pacchetti/s: $\rho=0{,}8$, $E[x]=\frac{0{,}8}{0{,}2}=4$, $E[q]=\frac{0{,}64}{0{,}2}=3{,}2$, $E[z]=0{,}8$ ($3{,}2+0{,}8=4$ ✓); $E[s]=\frac1{1000-800}=5$ ms (Little: $800\cdot0{,}005=4$ ✓), $E[w]=\frac{0{,}8}{200}=4$ ms ($=5-1$ ✓); $P[x\ge5]=0{,}8^5=0{,}328$; sistema vuoto con probabilità $0{,}2$. Se il carico sale a $\rho=0{,}95$ ($\lambda=950$): $E[s]=\frac1{50}=20$ ms, quattro volte di più.

Esempio (instabile). Con $\lambda=1{,}01$ s$^{-1}$ e $\mu=1$ s$^{-1}$ ($\rho=1{,}01$, il $1\%$ oltre il limite) $x(t)$ cresce senza limite: i clienti si accumulano in media al ritmo $\lambda-\mu=0{,}01$ al secondo e non esiste distribuzione stazionaria. Se $\lambda=\mu$ il sistema è marginalmente instabile: la coda non cresce linearmente ma non ha regime ($\pi_k=0$ per ogni $k$).

4. La distribuzione del tempo di sistema

Un cliente ("Leo") arriva e trova $k$ clienti: uno in servizio e $k-1$ in attesa. Il suo tempo di sistema $s$ è la somma del residuo del servizio in corso (ancora esponenziale di tasso $\mu$, per l'assenza di memoria), dei $k-1$ servizi dei clienti in attesa e del proprio servizio: $k+1$ esponenziali i.i.d. di tasso $\mu$, cioè una variabile di Erlang-$(k+1)$: $$p_{s|k}(a)=\frac{\mu(\mu a)^k}{k!}e^{-\mu a},\ a\ge0.$$ Con che probabilità trova $k$ clienti? Per la proprietà PASTA (Poisson Arrivals See Time Averages): gli arrivi di Poisson vedono il sistema nello stato $k$ con la probabilità media di quello stato, $\pi_k$ (perché l'arrivo è indipendente dallo stato passato: non "si sceglie" i momenti). Quindi $$p_s(a)=\sum_{k\ge0}(1-\rho)\rho^k\frac{\mu(\mu a)^k}{k!}e^{-\mu a}=(1-\rho)\mu e^{-\mu a}\sum_{k\ge0}\frac{(\rho\mu a)^k}{k!}=(1-\rho)\mu e^{-\mu a}e^{\rho\mu a}.$$ Ricordando $\mu(1-\rho)=\mu-\lambda$: $$\boxed{p_s(a)=(\mu-\lambda)e^{-(\mu-\lambda)a},\qquad P[s>t]=e^{-(\mu-\lambda)t}}$$ Il tempo di sistema è esponenziale con tasso $\mu-\lambda$ (media $\frac1{\mu-\lambda}$, come da Little). Per l'attesa in coda: $w=0$ se il cliente trova il sistema vuoto (probabilità $1-\rho$); altrimenti il suo tempo è somma di $k$ servizi con $k\ge1$ e si ottiene $P[w>t]=\rho\,e^{-(\mu-\lambda)t}$.

Esempio. Nell'esempio sopra ($\mu-\lambda=200$ s$^{-1}$): $P[s>10\ \text{ms}]=e^{-2}=0{,}135$ e $P[w>5\ \text{ms}]=0{,}8e^{-1}=0{,}294$. Se Leo trova $k=2$ clienti il suo tempo medio è $\frac{3}{\mu}=3$ ms.

Teorema di Burke. Il processo delle partenze di un'M/M/1 stabile è di Poisson con lo stesso tasso $\lambda$ degli arrivi. Conseguenza: se l'uscita di una coda alimenta una seconda coda (code in cascata), anche questa riceve arrivi di Poisson e, se il suo servizio è esponenziale, si può studiare come M/M/1 isolata.

5. Il modello M/M/m

Con $m$ servitori identici in parallelo, ciascuno con servizi esponenziali di tasso $\mu$, se $k_s=\min(x,m)$ servitori sono occupati il primo che finisce lo fa dopo il minimo di $k_s$ esponenziali indipendenti. Il minimo di $k_s$ esponenziali di tasso $\mu$ è esponenziale di tasso $k_s\mu$: infatti $P[\min>t]=\prod P[y_i>t]=e^{-k_s\mu t}$. Quindi la "morte" avviene con tasso dipendente dallo stato: $$\text{tasso di partenza dallo stato }k=\min(k,m)\,\mu.$$ La catena è ancora di nascita e morte e i bilanci di flusso diventano $$\lambda\pi_{k-1}=k\mu\,\pi_k\ \ (1\le k\le m),\qquad\lambda\pi_{k-1}=m\mu\,\pi_k\ \ (k\ge m).$$ Posto $G=\frac\lambda\mu$ (traffico offerto: numero medio di servitori richiesti) e $\rho=\frac G m=\frac\lambda{m\mu}$ (fattore di carico), si ricava ricorsivamente $$\pi_k=\frac{G^k}{k!}\pi_0\ \ (0\le k\le m),\qquad\pi_k=\frac{G^m}{m!}\rho^{\,k-m}\pi_0\ \ (k\ge m).$$ Per $k\le m$ si ha $\pi_k=\frac{\lambda}{k\mu}\pi_{k-1}$, cioè un fattore $\frac Gk$ a ogni passo; per $k>m$ il fattore è $\frac{G}{m}=\rho$. Normalizzando ($\sum\pi_k=1$): $$\pi_0=\left[\sum_{k=0}^{m-1}\frac{G^k}{k!}+\frac{G^m}{m!}\cdot\frac1{1-\rho}\right]^{-1}.$$ La seconda somma (serie geometrica di ragione $\rho$) converge se e solo se $\rho<1$, cioè $\lambda<m\mu$: condizione di stabilità per $m$ servitori.

Formula di Erlang C. La probabilità che un cliente che arriva trovi tutti i servitori occupati (e debba attendere) è, per PASTA, $$C=P[x\ge m]=\sum_{k\ge m}\pi_k=\frac{\pi_m}{1-\rho}=\frac{G^m}{m!\,(1-\rho)}\,\pi_0.$$

Misure di prestazione. I clienti in servizio sono in media quanti i servitori occupati: $E[z]=G$ (ogni servitore è occupato con frazione $\rho$, $m\rho=G$; è anche Little: $E[z]=\lambda E[y]=\frac\lambda\mu$). In coda: $E[q]=\sum_{k\ge m}(k-m)\pi_k=\pi_m\sum_{j\ge0}j\rho^j=\pi_m\frac\rho{(1-\rho)^2}=\frac{C\rho}{1-\rho}$. Poi, con Little: $$E[q]=\frac{C\,G}{m-G},\qquad E[x]=G+\frac{C\,G}{m-G},\qquad E[w]=\frac{E[q]}\lambda=\frac C{m\mu-\lambda},\qquad E[s]=E[w]+\frac1\mu.$$ L'attesa in coda ha distribuzione: $P[w>t]=C\,e^{-(m\mu-\lambda)t}$ (con probabilità $1-C$ non si aspetta; altrimenti si attendono $k-m+1$ partenze a tasso $m\mu$ e, con $k-m$ geometrico di ragione $\rho$, la mistura è esponenziale di tasso $m\mu(1-\rho)=m\mu-\lambda$). Per $m=1$: $C=\rho$ e si ritrovano le formule M/M/1.

Esempio. $m=2$, $\mu=1$ s$^{-1}$, $\lambda=1{,}6$ s$^{-1}$: $G=1{,}6$, $\rho=0{,}8$. $\pi_0=\left[1+1{,}6+\frac{1{,}6^2}{2}\cdot\frac1{0{,}2}\right]^{-1}=\frac1{9}=0{,}1111$; $C=\frac{G^2}{2(1-\rho)}\pi_0=\frac{1{,}28}{0{,}2}\cdot\frac19=0{,}711$. $E[q]=\frac{0{,}711\cdot1{,}6}{0{,}4}=2{,}844$; $E[x]=4{,}444$; $E[w]=\frac{0{,}711}{2-1{,}6}=1{,}778$ s; $E[s]=2{,}778$ s. (Una simulazione con $3\cdot10^5$ clienti dà $E[w]=1{,}75$ e $E[s]=2{,}75$.)

Per $m=2$ si semplifica: $C=\frac{2\rho^2}{1+\rho}=\frac{G^2}{2+G}$, $E[s]=\frac1\mu\cdot\frac{4}{4-G^2}$ (con $\mu=1$ e $G=\lambda$: $\frac{4}{4-\lambda^2}$).

Un server veloce o tanti lenti?

Si confrontano tre architetture con la stessa capacità totale: (a) un'M/M/1 con un solo servitore di tasso $m\mu_0$ (canale unico, SC); (b) un'M/M/$m$ con $m$ servitori di tasso $\mu_0$ (canale comune, CC); (c) $m$ code M/M/1 separate, ciascuna con un servitore di tasso $\mu_0$ e arrivi $\frac\lambda m$ (canali paralleli, PC). Con $m=2$ e $\mu_0=1$, il tempo di sistema in funzione di $\lambda$ è

$$\text{(a)}\ \frac1{2-\lambda},\qquad\text{(b)}\ \frac4{4-\lambda^2},\qquad\text{(c)}\ \frac2{2-\lambda}.$$

Per $\lambda=0{,}2$: $0{,}556\ /\ 1{,}010\ /\ 1{,}111$; per $\lambda=1{,}6$: $2{,}5\ /\ 2{,}78\ /\ 5$. Conclusione: (a) $\le$ (b) $\le$ (c): "meglio un servitore veloce che tanti lenti", e la coda condivisa (b) è molto meglio di code separate (c). A carico basso un servitore doppio dimezza il tempo di servizio ($0{,}5$ contro $1$); a carico alto (b) si avvicina ad (a). Lo svantaggio di (b) e (c) è che con meno clienti di servitori alcuni servitori restano inattivi.

6. Altri modelli di nascita e morte

M/M/$\infty$ (infiniti servitori, nessuna coda). Ogni cliente ha subito un servitore: la morte da $k$ avviene a tasso $k\mu$. Bilancio $\lambda\pi_{k-1}=k\mu\pi_k$, quindi $\pi_k=\frac{G^k}{k!}\pi_0$ per ogni $k$, e $\pi_0=\left[\sum_k\frac{G^k}{k!}\right]^{-1}=e^{-G}$: $$\pi_k=\frac{G^k}{k!}e^{-G}\quad\text{(Poisson di parametro }G=\tfrac\lambda\mu),\qquad E[x]=G.$$ È sempre stabile, per qualsiasi $\lambda,\mu$ (dimostrazione alternativa con il conteggio degli arrivi in Esercizio - sistema M-M-infinito). Esempio. $\lambda=3$ chiamate/min, durata media $0{,}5$ min: $G=1{,}5$ e $\pi_0=e^{-1{,}5}=0{,}223$.

M/M/1/$K$ (buffer finito, capacità del sistema $K$). Gli stati sono $0,\dots,K$ e i bilanci sono quelli dell'M/M/1: $\pi_k=\pi_0\rho^k$ per $k\le K$; la somma è finita, quindi non serve $\rho<1$ (il sistema è sempre stabile): $\pi_k=\frac{(1-\rho)\rho^k}{1-\rho^{K+1}}$. Un cliente è perso se trova il sistema pieno; per PASTA $P_{BLK}=\pi_K=\frac{(1-\rho)\rho^K}{1-\rho^{K+1}}$ (per $\rho=1$: $\frac1{K+1}$). Esempio. $\rho=0{,}8$, $K=5$: $P_{BLK}=\frac{0{,}2\cdot0{,}8^5}{1-0{,}8^6}=0{,}0888$; con $K=10$: $0{,}0235$. Il throughput è $\lambda(1-P_{BLK})$ e, per Little, $E[s]=\frac{E[x]}{\lambda(1-P_{BLK})}$ (si usa il tasso dei clienti accettati).

Errori comuni

• Applicare le formule con $\rho\ge1$ (non c'è regime stazionario) o dimenticare che per $m$ servitori la condizione è $\lambda<m\mu$, cioè $\rho=\frac{\lambda}{m\mu}<1$ (non $\frac\lambda\mu<1$).
• Usare $E[w]=\frac\rho{1-\rho}\cdot\frac1\mu$ come tempo nel sistema: è l'attesa in coda; il tempo nel sistema include il servizio: $E[s]=E[w]+\frac1\mu=\frac{1/\mu}{1-\rho}$.
• Calcolare $\mu=\frac{R_b}{\bar L}$ con $R_b$ in bit/s e $\bar L$ in bit, e $\lambda$ nelle stesse unità di tempo di $\mu$.
• Dimenticare di usare il tasso accettato $\lambda(1-P_{BLK})$ in Little per i sistemi con blocco.
• Confondere $P[x\ge m]$ (Erlang C, probabilità di aspettare) con $P[x=m]$ o con $\rho$.
• Pensare che i tempi siano geometrici: il numero di clienti è geometrico, il tempo di sistema è esponenziale.