Lezione 6Esercizi sulle code e il meteorologo

Fonte: appunti a mano tlc_06, svolgimento della scheda di esercizi n. 2 ("Queueing systems") e dell'esercizio del meteorologo, corso Telecommunications, UniPD; più l'approfondimento sulla teoria delle code.

Argomenti trattati

1. Esercizio 1 (M/M/1 con $\mu=10$ clienti/s e servitore occupato al $90\%$): $\lambda=9$ clienti/s, $m_q=8{,}1$ e discussione, $P[q>9{,}72]=\rho^{11}=0{,}314$, $P[s>2]=e^{-2}$.
2. Esercizio 2 (SMS dei gol): sovrapposizione di $8$ processi di Poisson ($\lambda=\frac14$ min$^{-1}$), servizio esponenziale di media $3$ min, M/M/1 con $\rho=0{,}75$, $P[x\ge2]=\frac9{16}$.
3. Esercizio 3 (linea da $50$ kbit/s con $10$ sessioni): M/M/1 con lunghezza esponenziale, M/D/1 con lunghezza fissa, metriche di occupazione e tempo, commutazione di circuito (tempi dieci volte maggiori).
4. Esercizio del meteorologo: probabilità congiunta e marginali, $H(X)$, $H(Y)$, $H(X,Y)$, limiti notevoli, $p_{X|Y}$, $H(X|Y)$, significato fisico; la proposta della previsione costante.
5. Approfondimento: M/M/$\infty$, call center (stabilità e sostenibilità economica), architettura manager-workers con M/M/2.

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 →
• 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 →
• Informazione, entropia e informazione mutuaL'informazione di un evento di probabilità $P$ è $i=\log_2\frac1P$ bit; l'entropia $H(x)=\sum p\log_2\frac1p$ è l'informazione media e misura l'incertezza: $0\le H\le\log_2M$, massimo se i simboli sono equiprobabili. Per due variabili: $\max{H(x),H(y)}\le H(x,y)\le H(x)+H(y)$, $H(x|y)=H(x,y)-H(y)$ e l'informazione mutua $I(x;y)=H(x)-H(x|y)=H(x)+H(y)-H(x,y)\ge0$ (zero se e solo se indipendenti). Per una sorgente di $F_s$ simboli/s: rate di informazione $F_sH_s$, rate nominale $F_s\log_2M$, efficienza $\eta=\frac{H_s}{\log_2M}$.Informazione, entropia e informazione mutua →

Esercizi

• Esercizio - coda M-M-1 con servitore occupato al 90 per cento — esercizio 1
• Esercizio - SMS dei gol e coda M-M-1 — esercizio 2
• Esercizio - linea condivisa da dieci sessioni, commutazione di pacchetto e di circuito — esercizio 3
• Esercizio - il meteorologo, entropia e informazione mutua
• Esercizio - call center, stabilità e sostenibilità economica — approfondimento
• Esercizio - sistema M-M-infinito — approfondimento
• Esercizio - processori manager-worker, coda M-M-2 e compressione del registro — approfondimento

Lezione precedente: Lezione 5 · Code M-M-1, M-M-m e M-D-1