Lezione 5Code M-M-1, M-M-m e M-D-1

Fonte: appunti a mano tlc_05 e slide TLC4 (sistema instabile, probabilità di accodamento di Erlang, confronto M/M/1 e M/M/m), corso Telecommunications, UniPD.

Argomenti trattati

1. M/M/1: eventi in $[0,h]$; processo di partenze "virtuale" e assenza di memoria; $x(t)$ come statistica sufficiente; catena di Markov di nascita e morte; teorema della probabilità totale per $P(x(t+h)=k)$.
2. Regime stazionario e stabilità: probabilità asintotiche $\pi_k$, bilancio di flusso $\lambda\pi_{k-1}=\mu\pi_k$, $\pi_k=(1-\rho)\rho^k$ con $\rho<1$; media e varianza di $x$, $E[z]=\rho$, $E[q]=\frac{\rho^2}{1-\rho}$.
3. Tempi in M/M/1: tempo di sistema condizionato ($k$ clienti trovati) di Erlang-$(k+1)$; proprietà PASTA; $s$ esponenziale di tasso $\mu-\lambda$; teorema di Burke e code in cascata.
4. M/M/m: minimo di esponenziali (partenze a tasso $k_s\mu$); bilanci di flusso e probabilità $\pi_k$; stabilità $\lambda<m\mu$; probabilità di accodamento (Erlang C) $C$; $E[z]=G$, $E[q]=\frac{CG}{m-G}$, $E[w]=\frac C{m\mu-\lambda}$; grafico di $C(m,G)$.
5. Cenni a M/G/1 e M/D/1 (servizio costante: $E[q]=\frac{\rho^2}{2(1-\rho)}$).
6. Confronto tra architetture: un server veloce (M/M/1), $m$ server in parallelo con coda comune (M/M/m) e $m$ code separate: "meglio un singolo server veloce che tanti lenti".

Teoria

• Sistemi a coda M-M-1 e M-M-mIn un sistema M/M/m (arrivi di Poisson $\lambda$, servizi esponenziali $\mu$, $m$ servitori) il numero di clienti $x(t)$ è una catena di Markov di nascita e morte con tassi di nascita $\lambda$ e di morte $\min(k,m)\mu$. A regime il bilancio di flusso $\lambda\pi_{k-1}=\min(k,m)\mu,\pi_k$ dà per M/M/1 $\pi_k=(1-\rho)\rho^k$ ($\rho=\frac\lambda\mu<1$), $E[x]=\frac\rho{1-\rho}$, $E[s]=\frac1{\mu-\lambda}$ (esponenziale), e per M/M/m la probabilità di accodamento di Erlang C, $C=P[x\ge m]$, con $E[q]=\frac{C,G}{m-G}$, $E[w]=\frac C{m\mu-\lambda}$, $E[s]=E[w]+\frac1\mu$ ($G=\frac\lambda\mu$, $\rho=\frac Gm<1$).Sistemi a coda M-M-1 e M-M-m → — catena di Markov, M/M/1, M/M/m, Erlang C, confronto, M/M/$\infty$ e M/M/1/$K$
• 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 → — M/D/1 e Pollaczek-Khinchin

Esercizi

• Esercizio - sistema M-M-infinito — la distribuzione stazionaria di Poisson
• Esercizio - processori manager-worker, coda M-M-2 e compressione del registro — M/M/2 e codifica di sorgente

Lezione precedente: Lezione 4 · Sistemi a coda, stabilità e formula di Little · Lezione successiva: Lezione 6 · Esercizi sulle code e il meteorologo