Lezione 4Sistemi a coda, stabilità e formula di Little

Fonte: appunti a mano tlc_04 (con le slide sui sistemi a coda), corso Telecommunications, UniPD.

Argomenti trattati

1. Il sistema a coda: clienti, area di accodamento, $m$ servitori; ipotesi (clienti identici, servitori identici, servizio instancabile).
2. Processo degli arrivi e processo di conteggio $A(t)$ (e delle partenze, $D(t)$); interarrivi $\tau_j=t_j-t_{j-1}$ e tasso $\lambda=\frac1{E[\tau]}$; arrivi di Poisson, deterministici e di Erlang (confronto Poisson/deterministico).
3. Processo di servizio (deterministico, esponenziale, Erlang), tasso $\mu=\frac1{m_y}$, tasso globale $m\mu$ per servitori multipli; sistemi a commutazione di pacchetto ($\lambda=\frac{R_b}L$, $\mu=\frac{R_b}L$).
4. Capacità e struttura: $K=m+Q$, sistemi bloccanti ($\lambda(1-P_{BLK})$), disciplina; notazione di Kendall.
5. Metriche: tempi ($w$, $y$, $s$, $d_n=t_n+w_n+y_n$) e occupazione ($x=z+q$, $x=A-D$).
6. Stabilità ($\sum_k\pi_k=1$, indipendenza dallo stato iniziale), sistemi esplosivi e marginalmente stabili (esempio: $\lambda=1{,}01$ e $\mu=1$ s$^{-1}$), condizione $\lambda<m\mu$, fattore di carico $\rho$, traffico offerto $G$, throughput $\eta=\min\{\lambda,m\mu\}$ e throughput normalizzato $S=\min\{G,m\}$.
7. Formula di Little $E[x]=\lambda E[s]$: dimostrazione ingegneristica (area dell'integrale di $x(t)$), validità per sistemi G/G/1 e G/G/$m$, applicazioni a sistema, coda e servizio; per G/G/1 $E[z]=\rho$.
8. Sistemi di Markov: probabilità in un intervallo infinitesimo ($\lambda h+o(h)$, trascurabilità di eventi multipli, anche arrivo e partenza insieme).

Teoria

• 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 → — arrivi, servizio, Kendall, probabilità in $[0,h]$
• 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 → — metriche, stabilità, throughput, Little

Esercizi

• Esercizio - carico di un collegamento con pacchetti di lunghezza fissa — capacità, carico e stabilità di un collegamento con $\lambda=50$ pacchetti/s

Lezione precedente: Lezione 3 · Esercizi su quantizzazione e codifica di sorgente · Lezione successiva: Lezione 5 · Code M-M-1, M-M-m e M-D-1