Sistemi a coda M/G/1 e formula di Little

Il modello è quello di 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 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 →. Qui si definiscono le misure di prestazione di un sistema a coda qualsiasi, si dimostra la formula di Little (che vale senza ipotesi sulle distribuzioni) e si calcola il ritardo del sistema M/G/1, in cui il servizio ha distribuzione qualunque, per esempio costante (pacchetti tutti uguali). Vedi anche Introduzione alla teoria delle codeUn sistema a coda (QS) è fatto da un processo di arrivi (di Poisson, tasso $\lambda$), una coda e uno o più servitori con tasso di servizio $\mu$. Carico offerto $G=\lambda/\mu$, fattore di carico $\rho=\lambda/(m\mu)$: il sistema è stabile solo se $\rho<1$, e allora il throughput è $\lambda$ (altrimenti è $m\mu$). Legge di Little: $E[x]=\lambda E[s]$, valida per qualsiasi disciplina. Coda M/M/1: $E[x]=\frac{\rho}{1-\rho}$, $E[s]=\frac{1/\mu}{1-\rho}$, $E[w]=\frac{\rho/\mu}{1-\rho}$. Con servizio deterministico (M/D/1, caso particolare di Pollaczek-Khinchin): $E[w]=\frac{\rho}{2\mu(1-\rho)}$. Il ritardo cresce senza limite quando $\rho\to1$.Introduzione alla teoria delle code → (corso di Internet).

1. Le misure di un sistema a coda

Occupazione. All'istante $t$: $q(t)$ clienti nell'area di attesa, $z(t)$ clienti in servizio (al più $m$) e $x(t)=q(t)+z(t)$ nell'intero sistema. Con $A(t)$ e $D(t)$ arrivi e partenze fino a $t$ vale anche $x(t)=A(t)-D(t)$. Le medie sono $E[q],E[z],E[x]$.

Tempi. Per il cliente $C_n$: $w_n$ tempo di attesa in coda, $y_n$ tempo di servizio, $s_n=w_n+y_n$ tempo di sistema, e l'istante di uscita è $d_n=t_n+w_n+y_n=t_n+s_n$. Medie: $E[w],E[y]=\frac1\mu,E[s]$.

Traffico. Con $\lambda$ il tasso di arrivo e $\mu$ il tasso di servizio di un servitore:

• traffico offerto $G=\frac\lambda\mu=\lambda E[y]$: numero medio di arrivi durante un tempo di servizio, cioè quanti servitori "servirebbero" in media;
• fattore di carico (utilizzazione, intensità di traffico) con $m$ servitori: $\rho=\frac{\lambda}{m\mu}=\frac Gm$;
• throughput $\eta=\frac1{E[r]}$ (clienti/s): numero medio di clienti serviti e usciti per unità di tempo, con $r_n=d_n-d_{n-1}$ tempo di interpartenza;
• throughput normalizzato $S=\frac\eta\mu=\eta E[y]$ (numero puro): numero medio di servitori attivi. Il traffico offerto è quanti servitori i clienti richiedono, il throughput normalizzato quanti ne vengono davvero usati.

Esempio. Un collegamento da $1$ Mbit/s trasmette pacchetti da $1000$ bit: $\mu=1000$ pacchetti/s. Con $\lambda=800$ pacchetti/s: $G=\rho=0{,}8$.

2. Stabilità e throughput

Definizione (stabilità). Un sistema è stabile se $\lim_{t\to\infty}P[x(t)=k]=\pi_k$ esiste, con $\sum_k\pi_k=1$, e non dipende dallo stato iniziale $x(0)$. Se $x(t)\to\infty$ le $\pi_k$ sono tutte $0$ e il sistema è esplosivo (instabile).

Condizione di stabilità (Loynes). Un sistema senza blocco (G/G/$m$, con arrivi e servizi i.i.d. indipendenti) è stabile se e solo se $$\lambda<m\mu\quad\Longleftrightarrow\quad\rho<1.$$ I sistemi con blocco ($K$ finito) sono sempre stabili, perché il numero di clienti non supera $K$.

Se $\lambda>m\mu$ i clienti arrivano più in fretta di come si servono: si accumulano in media a $\lambda-m\mu$ al secondo. Se $\lambda=m\mu$ il sistema è marginalmente instabile (nessun regime). Un sistema stabile e senza blocco deve far uscire in media quello che entra, altrimenti ci sarebbe accumulo; se è instabile i servitori lavorano sempre al massimo: $$\eta=\begin{cases}\lambda&\rho<1\\m\mu&\rho\ge1\end{cases}=\min\{\lambda,m\mu\},\qquad S=\min\{G,m\},\qquad S=G\ \ (\rho<1).$$ Per un sistema con blocco il throughput è $\eta=\lambda(1-P_{BLK})$.

Esempio. Con $\mu=1000$ pacchetti/s: se $\lambda=800$, $\rho=0{,}8<1$, $\eta=800$ pacchetti/s e $S=0{,}8$ (il servitore è occupato l'80% del tempo). Se $\lambda=1200$, $\rho=1{,}2$: instabile, escono solo $\eta=1000$ pacchetti/s ($S=1$) e la coda cresce di $200$ pacchetti al secondo.

Esempio (pacchetti di lunghezza fissa). $\lambda=50$ pacchetti/s su una linea con $R_b=1$ Mbit/s e pacchetti di $L=10\,000$ bit: $\mu=\frac{R_b}L=\frac{10^6}{10^4}=100$ pacchetti/s, $\lambda<\mu$ quindi stabile, $\rho=\frac{50}{100}=0{,}5$. Il servizio è costante: è un sistema G/D/1 (M/D/1 se gli arrivi sono di Poisson).

3. La formula di Little

Teorema (formula di Little). In una struttura "conservativa" (che non crea né distrugge clienti), se i valori medi esistono, il numero medio di clienti presenti è uguale al tasso di ingresso per il tempo medio di permanenza: $$\boxed{E[x]=\lambda\,E[s].}$$ Non fa ipotesi sulla distribuzione di arrivi e servizi, sulla disciplina (anche non FIFO), sul numero di servitori, né sulla dipendenza tra arrivi e servizio. Vale se i processi sono ergodici, in modo che le medie temporali coincidano con quelle statistiche.

Dimostrazione (ingegneristica). Si conta in due modi il "tempo-cliente" totale accumulato fino al tempo $t$, cioè la somma dei secondi passati nel sistema da tutti i clienti.

1. Per istante. All'istante $u$ ci sono $x(u)=A(u)-D(u)$ clienti, ognuno dei quali "consuma" un secondo-cliente per secondo: il totale è l'area sotto la curva $x(u)$, $\int_0^tx(u)\,du$.
2. Per cliente. Il cliente $C_n$ resta $s_n$ secondi, e il totale è $\sum_{n=1}^{A(t)}s_n$. Le due quantità coincidono a meno dei clienti ancora presenti a $t$, che per $t\to\infty$ in un sistema stabile pesano sempre meno.

Dividendo per $t$ e moltiplicando e dividendo per $A(t)$: $$\frac1t\int_0^tx(u)\,du=\frac{A(t)}t\cdot\frac1{A(t)}\sum_{n=1}^{A(t)}s_n.$$ Per $t\to\infty$ il membro di sinistra tende a $E[x]$ (media temporale di $x$, ergodicità); $\frac{A(t)}t\to\lambda$; l'ultimo fattore è la media degli $s_n$, cioè $E[s]$. Quindi $E[x]=\lambda E[s]$. $\square$

La struttura a cui si applica si sceglie a piacere, purché sia conservativa:

Per un sistema G/G/1 stabile $z\in\{0,1\}$, quindi $E[z]=P[z=1]$ e allora $P[\text{servitore occupato}]=\lambda E[y]=\rho$: l'utilizzazione è la frazione di tempo in cui il servitore lavora, qualunque sia la distribuzione. Con $m$ servitori $E[z]=G$.

Esempio. In un router entrano $\lambda=500$ pacchetti/s e in media se ne trovano $E[x]=10$ nel sistema: ogni pacchetto resta in media $E[s]=\frac{10}{500}=20$ ms. Se la trasmissione di un pacchetto dura $\frac1\mu=1$ ms, ne aspetta $E[w]=20-1=19$ ms in coda, e in coda ci sono $E[q]=500\cdot0{,}019=9{,}5$ pacchetti; il servitore è occupato per $E[z]=500\cdot0{,}001=0{,}5$ del tempo ($9{,}5+0{,}5=10$ ✓). Little non dice com'è fatto il sistema: lega solo le tre medie.

4. La coda M/G/1 e la formula di Pollaczek-Khinchin

Arrivi di Poisson di tasso $\lambda$, un servitore, tempi di servizio i.i.d. con distribuzione qualsiasi, media $E[y]=\frac1\mu$ e secondo momento $E[y^2]$; $\rho=\lambda E[y]<1$. Il numero di clienti non è più una catena di Markov (il servizio non è senza memoria) ma si può comunque trovare l'attesa media.

Formula di Pollaczek-Khinchin. $$\boxed{E[w]=\frac{\lambda\,E[y^2]}{2(1-\rho)}}$$

Derivazione (analisi del valore medio). Un cliente che arriva deve aspettare: (i) il tempo residuo del servizio in corso, se il servitore è occupato; (ii) i servizi dei clienti già in coda, in numero medio $E[q]$. Gli arrivi di Poisson vedono il sistema nello stato medio (PASTA): il servitore è occupato con probabilità $\rho$. Quindi $$E[w]=\rho\,E[y_{res}]+E[q]\,E[y],\qquad E[y_{res}]=\frac{E[y^2]}{2E[y]}.$$ Il residuo medio si ottiene così: il servizio "in corso" in un istante qualsiasi ha lunghezza $y$ con probabilità proporzionale a $y\,p_y(y)$ (i servizi lunghi occupano più tempo, quindi è più facile capitare dentro uno di essi: paradosso dell'ispezione), cioè con densità $\frac{y\,p_y(y)}{E[y]}$, e il tempo residuo in un servizio di lunghezza $y$ è uniforme in $[0,y]$, di media $\frac y2$. Allora $E[y_{res}]=\int\frac{y\,p_y(y)}{E[y]}\cdot\frac y2\,dy=\frac{E[y^2]}{2E[y]}$. Si usa poi Little per la coda, $E[q]=\lambda E[w]$: $$E[w]=\rho\frac{E[y^2]}{2E[y]}+\lambda E[w]E[y]=\rho\frac{E[y^2]}{2E[y]}+\rho E[w]\ \Rightarrow\ E[w](1-\rho)=\frac{\rho}{E[y]}\cdot\frac{E[y^2]}2=\frac{\lambda E[y^2]}2,$$ perché $\frac\rho{E[y]}=\lambda$. $\square$ Poi, con Little: $$E[s]=E[w]+\frac1\mu,\qquad E[x]=\lambda E[s]=\rho+\frac{\lambda^2E[y^2]}{2(1-\rho)},\qquad E[q]=\lambda E[w].$$ L'attesa dipende dal secondo momento del servizio: a parità di media, un servizio più variabile fa aspettare di più. Con il coefficiente di variazione quadratico $c^2=\frac{\operatorname{Var}(y)}{E[y]^2}$ si ha $E[y^2]=\frac{1+c^2}{\mu^2}$ e $$E[w]=\frac{1+c^2}2\cdot\frac{\rho}{\mu(1-\rho)}.$$

Casi particolari.

• Servizio esponenziale (M/M/1). $E[y^2]=\frac2{\mu^2}$ ($c^2=1$): $E[w]=\frac{\lambda\cdot2/\mu^2}{2(1-\rho)}=\frac{\rho/\mu}{1-\rho}$, il risultato dell'M/M/1.
• Servizio costante (M/D/1), pacchetti tutti uguali: $E[y^2]=\frac1{\mu^2}$ ($c^2=0$): $$E[w]=\frac{\rho}{2\mu(1-\rho)},\quad E[s]=\frac1\mu\left(1+\frac\rho{2(1-\rho)}\right)=\frac{2-\rho}{2\mu(1-\rho)},\quad E[x]=\rho+\frac{\rho^2}{2(1-\rho)}=\frac{\rho(2-\rho)}{2(1-\rho)},\quad E[q]=\frac{\rho^2}{2(1-\rho)}.$$ A parità di $\rho$ l'attesa del servizio costante è la metà di quella esponenziale.
• Servizio Erlang-$k$: $c^2=\frac1k$, attesa $\frac{1+1/k}2$ volte quella dell'M/M/1.

Esempio. Collegamento da $1$ Mbit/s, $\lambda=800$ pacchetti/s, pacchetti da $1000$ bit ($\mu=1000$ pacchetti/s, $\rho=0{,}8$). M/D/1 (lunghezza fissa): $E[w]=\frac{0{,}8}{2\cdot1000\cdot0{,}2}=2$ ms, $E[s]=3$ ms, $E[x]=0{,}8+\frac{0{,}64}{0{,}4}=2{,}4$ pacchetti (Little: $800\cdot0{,}003=2{,}4$ ✓). M/M/1 (lunghezza esponenziale di media $1000$ bit): $E[w]=4$ ms, $E[s]=5$ ms, $E[x]=4$. Con servizio uniforme in $[0,2/\mu]$ ($E[y^2]=\frac4{3\mu^2}$, $c^2=\frac13$): $E[w]=\frac{1+1/3}2\cdot4=2{,}67$ ms (una simulazione con $6\cdot10^5$ clienti dà $2{,}66$). Altro esempio, pacchetti fissi con $\lambda=50$ pacchetti/s e $\mu=100$ ($\rho=0{,}5$): $E[w]=\frac{0{,}5}{2\cdot100\cdot0{,}5}=5$ ms, $E[s]=15$ ms, $E[x]=0{,}5+\frac{0{,}25}{1}=0{,}75$.

Perché gli arrivi di Poisson sono "cattivi". Anche a servizio costante l'attesa non è nulla, perché gli arrivi sono irregolari: si formano "grappoli" di clienti. Con arrivi deterministici e servizio costante con $\rho<1$ non si accumulerebbe mai nessuno ($E[w]=0$).

5. Che cosa si fa nel progetto di una rete

• Si dimensiona il collegamento perché lavori lontano da $\rho=1$: fino a $\rho=0{,}5$ il ritardo è meno del doppio del tempo di servizio, poi sale ripidamente (grafico).
• Per sistemi con servizio costante (frame tutti uguali, sistemi TDMA) si usano le formule M/D/1; per quelle con lunghezza variabile l'M/M/1 è un buon modello prudente.
• Per più utenti con la stessa linea conviene condividerla (una sola coda): a parità di capacità i ritardi sono minori di quelli di canali dedicati per ogni utente (Esercizio - linea condivisa da dieci sessioni, commutazione di pacchetto e di circuito).
• I protocolli di accesso e di ritrasmissione usano questi risultati (Tecniche ARQ e loro prestazioniARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore risponde a ogni pacchetto con ACK (corretto) o NACK (errato), e il trasmettitore ritrasmette. Con probabilità di pacchetto errato $p$, $t_{RTT}=t_P+t_A+2\tau_P$ e coda sempre piena, il throughput massimo (frazione di tempo d'aria) è: Stop-and-Wait $S=\frac{t_P(1-p)}{t_{RTT}}$; Go-Back-N con $N=t_{RTT}/t_P$ $S=\frac{1-p}{(N-1)p+1}$; Selective Repeat $S=1-p$. Il ritardo medio è $m_{delay}=t_P+\tau_P+\frac p{1-p}t_{RTT}$ (a coda vuota). Sono solo valori massimi: la coda ARQ è stabile solo se $\lambda$ è minore della velocità di servizio, $\lambda<1/m_y$; altrimenti il throughput è $\min(\lambda,\mu)$. L'efficienza (payload) è $\eta=S,L_D/L$.Tecniche ARQ e loro prestazioni →, Accesso al mezzo - ALOHA, CSMA e protocolli deterministiciQuando più nodi condividono il canale serve un protocollo di accesso (MAC): deterministico (TDMA, FDMA, SDMA, CDMA), a richiesta (polling, token) o casuale (ALOHA, CSMA). Con $N_u$ utenti, arrivi di Poisson $\lambda$ ciascuno e pacchetti da $t_P=L/R_b$: TDMA stabile se $N_u\lambda t_P<1$, $m_{delay}=\frac{N_ut_P}{2(1-\rho)}+t_P+\tau_P$; FDMA ha ritardo maggiore di $t_P(N_u/2-1)$. ALOHA puro: intervallo di vulnerabilità $2t_P$, $S=Ge^{-2G}$, $S_{max}=1/(2e)\simeq0{,}18$ per $G=1/2$; slotted ALOHA: vulnerabilità $t_P$, $S=Ge^{-G}$, $S_{max}=1/e\simeq0{,}37$. ALOHA è intrinsecamente instabile (oltre il massimo il throughput va a $0$). Il carrier sense riduce la vulnerabilità a $\tau_P$ (CSMA), CD interrompe le collisioni, CA (RTS/CTS) è per il wireless; la persistenza (1-, non-, $p$-persistente) può portare il throughput verso il $100,%$.Accesso al mezzo - ALOHA, CSMA e protocolli deterministici →).

Errori comuni

• Applicare le formule con $\rho\ge1$, o usare $E[w]$ al posto di $E[s]$ (manca il tempo di servizio).
• Usare il tasso $\lambda$ totale nella Little di un sistema con blocco: serve il tasso dei clienti accettati $\lambda(1-P_{BLK})$.
• Applicare le formule dell'M/M/1 a un servizio costante, o viceversa: a parità di $\rho$ l'attesa differisce di un fattore 2.
• Dimenticare che Pollaczek-Khinchin usa $E[y^2]$ (e non solo la media): per l'esponenziale $E[y^2]=\frac2{\mu^2}$, per il costante $\frac1{\mu^2}$.
• Confondere traffico offerto $G=\frac\lambda\mu$ (può superare 1 con $m>1$) e fattore di carico $\rho=\frac Gm$ (deve essere $<1$).