Introduzione alla teoria delle code

Perché serve

Nell'Analisi delle prestazioni di reteLe prestazioni di una rete si misurano con tre famiglie di metriche: traffico (bitrate $R_0$ massimo del collegamento, throughput $S\le R_0$ dati consegnati con successo, goodput al livello applicazione), ritardo (end-to-end $d_{tot}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$ con $d_{trans}=L/R$ e $d_{prop}=d/v$; jitter; RTT) e capacità del tubo (BDP $=R\cdot$ ritardo, bit che riempiono il collegamento), più l'affidabilità (PER, PDR, PLR). Il throughput di un percorso è quello del collegamento collo di bottiglia, $\min$ dei bitrate, ricordando che i collegamenti condivisi dividono la capacità.Analisi delle prestazioni di rete → il ritardo di accodamento $d_{queue}$ era stato lasciato da parte: dipende dall'intensità del traffico, non solo dalle caratteristiche dei collegamenti. Per calcolarlo, e per stimare il ritardo dei protocolli di accesso al mezzo (Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMACon arrivi di Poisson, la probabilità di successo di un frame è la probabilità che nessun altro frame arrivi nel tempo vulnerabile: ALOHA puro $P_S=e^{-2G}$, throughput $S=Ge^{-2G}$ con massimo $1/(2e)\approx0{,}18$ in $G=1/2$; slotted ALOHA $S=Ge^{-G}$ con massimo $1/e\approx0{,}37$ in $G=1$. CSMA non persistente con $a=\tau_p/t_F$: $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, che tende a 1 per $a\to0$ ma crolla per $a$ grande, dove lo slotted ALOHA è migliore. Per TDMA ($M/D/1$) $E[T]=t_F\left(\frac{N_u}2+\frac{SN_u}{2(1-S)}+1+a\right)$ e per FDMA $E[T]=t_F\left(N_u+\frac{SN_u}{2(1-S)}+a\right)$: FDMA è più lento di $t_F(N_u/2-1)$.Prestazioni dei protocolli di accesso - ALOHA, CSMA, TDMA e FDMA →) o il jitter, si modella il collegamento come un sistema a coda (queueing system, QS).

Il corso la presenta in tre parti: (1) notazione e definizione di un sistema a coda, (2) metriche di prestazione, (3) risultati scelti (legge di Little, coda M/M/1, coda M/G/1), senza dimostrazioni tranne quella della legge di Little. Qui, per non lasciare passaggi nascosti, si aggiungono anche le derivazioni delle formule della M/M/1 e della M/D/1 (servono solo la probabilità e la 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 →). La stessa teoria, vista dai sistemi di telecomunicazione, è in Sistemi a coda - processo di Poisson, M/M/1 e formula di LittleUn sistema a coda ha arrivi (di pacchetti, file) e un servitore (il collegamento). Con arrivi di Poisson di intensità $\lambda$ e tempi di servizio esponenziali di media $\frac1\mu$ (coda M/M/1) e $\rho=\frac\lambda\mu<1$: $P[N=n]=(1-\rho)\rho^n$, numero medio nel sistema $\bar N=\frac\rho{1-\rho}$, tempo medio di permanenza $\bar W=\frac1{\mu-\lambda}$, attesa in coda $\bar W_q=\frac\rho{\mu-\lambda}$. La formula di Little $\bar N=\lambda\bar W$ vale in generale. Con buffer finito (M/M/1/K) i pacchetti sono persi con $P_K=\frac{(1-\rho)\rho^K}{1-\rho^{K+1}}$.Sistemi a coda - processo di Poisson, M/M/1 e formula di Little →.

Parte 1: il modello

Definizione (sistema a coda). Una popolazione di clienti (nelle reti: pacchetti dati; ma anche viaggiatori in fila al check-in, persone alla posta) arriva a un sistema formato da una coda (buffer, sala d'attesa) e da una struttura di servizio con $m$ servitori. I clienti escono dopo il servizio (processo di partenza).

Il processo degli arrivi

I clienti arrivano secondo un processo aleatorio. Si assume una popolazione infinita: i nuovi arrivi non sono influenzati da quelli passati (assenza di memoria). Il cliente $C_n$ è l'$n$-esimo:

• istante di arrivo di $C_n$: $t_n$;
• tempo di interarrivo tra $C_{n-1}$ e $C_n$: $\tau_n=t_n-t_{n-1}$;
• ipotesi: i $\tau_n$ sono indipendenti e identicamente distribuiti (i.i.d.) con funzione di distribuzione comune $P_\tau(a)=P[\tau_n\le a]$, $a\ge0$.

Il processo di conteggio degli arrivi $A(t)$ dice quanti clienti sono arrivati fino al tempo $t$: $$A(t)=\int_0^t\sum_{n=1}^{+\infty}\delta(u-t_n)\,du,$$ dove $\delta$ è la delta di Dirac (Delta di Dirac e derivate generalizzateLa delta di Dirac $\delta(t)$ è l'impulso ideale: area 1 concentrata in un punto, definita dalla proprietà rivelatrice $\int x(t)\delta(t-t_0)dt = x(t_0)$. Nel discreto la delta di Kronecker vale 1 in $n=0$. La derivata (generalizzata) di un salto di ampiezza $\Delta$ contiene una delta di area $\Delta$; così si derivano i segnali a tratti.Delta di Dirac e derivate generalizzate →: l'integrale di una delta in $t_n$ vale $1$ se $t_n$ cade nell'intervallo, quindi ogni arrivo fa saltare $A(t)$ di uno). Se gli interarrivi sono i.i.d. il processo si dice omogeneo, e con $E[\tau]$ tempo medio di interarrivo il tasso di arrivo è $$\lambda\triangleq\frac1{E[\tau]}\quad[\text{clienti/s}].$$

Arrivi di Poisson. Si considera solo il processo di Poisson omogeneo di tasso $\lambda$ (Somma di Poisson indipendenti e processo di PoissonSe X ~ Po(λ) e Y ~ Po(μ) sono indipendenti, X + Y ~ Po(λ + μ). Un processo di Poisson di intensità λ (eventi per unità di tempo) è una famiglia {Xₜ} in cui Xₜ ~ Po(λt) conta gli eventi in [0, t], gli incrementi X_{t+τ} − Xₜ ~ Po(λτ) dipendono solo dalla lunghezza τ dell'intervallo, e incrementi su intervalli disgiunti sono indipendenti. Quindi il numero di eventi in un intervallo non dipende da quanti ne sono avvenuti prima; la probabilità di nessun evento in un tempo τ è e^{−λτ}.Somma di Poisson indipendenti e processo di Poisson →). Il numero di arrivi in un intervallo di durata $\tau$ è una variabile di Poisson di parametro $\lambda\tau$ (Distribuzione di PoissonPoi(λ) conta eventi rari: P(X = k) = e^(−λ) λ^k / k! per k = 0, 1, 2, …, con media e varianza entrambe uguali a λ; approssima la binomiale Bin(n, p) quando n è grande e p piccolo, con λ = np.Distribuzione di Poisson →); da qui si ricava il tempo di interarrivo: l'evento «il prossimo arrivo avviene dopo più di $a$ secondi» coincide con «in $a$ secondi non arriva nessun cliente», che ha probabilità $e^{-\lambda a}$ (Poisson con $k=0$). Quindi $P[\tau>a]=e^{-\lambda a}$ e $P_\tau(a)=1-e^{-\lambda a}$: il tempo di interarrivo è esponenziale (Distribuzioni uniforme continua ed esponenzialeU(a, b) ha densità costante 1/(b − a) su [a, b], media (a + b)/2 e varianza (b − a)²/12; Exp(λ) ha densità λe^(−λx) per x ≥ 0, FdD 1 − e^(−λx), P(X > t) = e^(−λt), media 1/λ, varianza 1/λ², ed è l'unica legge continua senza memoria (versione continua della geometrica).Distribuzioni uniforme continua ed esponenziale →, con media $1/\lambda$): $$p_\tau(a)=\lambda e^{-\lambda a},\qquad P_\tau(a)=\int_0^ap_\tau(x)\,dx=1-e^{-\lambda a},\qquad a\ge0.$$ La probabilità che in un intervallo di durata $\tau$ arrivino esattamente $k$ clienti è $$P(k,\tau)\triangleq\frac{e^{-\lambda\tau}(\lambda\tau)^k}{k!}.$$

Esempio. Pacchetti con $\lambda=2$ al secondo: il tempo medio di interarrivo è $E[\tau]=1/2=0{,}5$ s. In un intervallo $\tau=1{,}5$ s il numero medio di arrivi è $\lambda\tau=2\cdot1{,}5=3$, e si applica $P(k,\tau)=e^{-3}3^k/k!$ con $e^{-3}=0{,}0498$: nessun arrivo ($k=0$, $0!=1$) $e^{-3}=0{,}0498$; esattamente $1$: $3e^{-3}=0{,}1494$; esattamente $2$: $\frac{3^2}{2!}e^{-3}=\frac{9}{2}e^{-3}=0{,}2240$; esattamente $3$: $\frac{3^3}{3!}e^{-3}=\frac{27}{6}e^{-3}=0{,}2240$ (uguale al caso $k=2$ perché $9/2=27/6$). Proprio la formula con $k=0$ è quella che dà la probabilità di successo di ALOHA ($e^{-2G}$, $e^{-G}$): si chiede che non arrivi nessun altro frame nel tempo vulnerabile.

La densità è massima in $a=0$: gli interarrivi brevi sono i più probabili, anche se la media è $0{,}5$ s; la media $1/\lambda$ è il baricentro della coda lunga, non il valore più frequente.

Il processo di servizio

La struttura di servizio ha uno o più servitori che lavorano in parallelo e indipendentemente. Per il cliente $C_n$ il tempo di servizio è il tempo $y_n$ che passa nella struttura di servizio; i tempi di servizio sono variabili aleatorie i.i.d., indipendenti dal processo degli arrivi, con densità $p_y(a)$, $a\ge0$. Il tasso di servizio di un singolo servitore è il numero di clienti che serve nell'unità di tempo, $$\mu\triangleq\frac1{E[y]}\quad[\text{clienti/s}],$$ e con $m$ servitori in parallelo è $m\mu$.

Le distribuzioni più comuni del tempo di servizio:

• deterministico: tempo costante, uguale a $1/\mu$; $p_y(a)=\delta(a-1/\mu)$ e la distribuzione cumulativa è un gradino, $P_y(a)=\mathbf 1(a-1/\mu)$. È il caso di un collegamento che trasmette pacchetti tutti della stessa lunghezza: $1/\mu=t_F=F/R$;
• esponenziale: $p_y(a)=\mu e^{-\mu a}$, $P_y(a)=1-e^{-\mu a}$ (pacchetti di lunghezza esponenziale). Ha media $E[y]=1/\mu$ e secondo momento $E[y^2]=2/\mu^2$ (quindi varianza $1/\mu^2$: Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →), valori che servono per la formula di Pollaczek-Khinchin.

La struttura della coda

• Capacità della coda $Q$: il massimo numero di clienti che si possono accumulare in coda (per i pacchetti: quelli memorizzabili nel buffer).
• Capacità di immagazzinamento del sistema $K$: il massimo numero di clienti nel sistema (in coda o in servizio): $$K=m+Q.$$
• Sistemi con blocco (blocking): se $K$ è finito, i clienti che trovano il sistema pieno non entrano (probabilità di blocco $P_{blk}$). Il tasso dei clienti accettati e quello dei clienti scartati sono $$\lambda_a=\lambda(1-P_{blk}),\qquad\lambda_d=\lambda-\lambda_a=\lambda P_{blk}.$$
• Sistemi senza blocco (non-blocking): buffer infinito. Esempio: un servitore e coda infinita.

Disciplina di servizio: l'ordine con cui i clienti sono presi dalla coda. Le più comuni sono FCFS (First Come First Served, detta anche FIFO, quella usata nell'analisi matematica), LCFS (Last Come First Served, LIFO) e la coda con priorità.

Notazione di Kendall. Un sistema a coda si descrive con $$A\,/\,B\,/\,C\,/\,K\,/\,N\,-\,S$$ dove $A$ è il modello statistico degli interarrivi, $B$ quello del servizio, $C$ il numero di servitori, $K$ la capacità del sistema, $N$ la dimensione della popolazione e $S$ la disciplina. $K$, $N$, $S$ sono opzionali: se mancano si assume $K$ ed $N$ infiniti e disciplina FCFS. $A$ e $B$ valgono tipicamente M (markoviano, cioè esponenziale/Poisson), D (deterministico), G (generico).

Esempio. M/M/1: arrivi di Poisson, servizio esponenziale, un servitore, coda infinita, FCFS. M/D/1: arrivi di Poisson, servizio deterministico. M/G/1: arrivi di Poisson, servizio con distribuzione qualsiasi.

Misure di occupazione

Al tempo $t$ si definiscono: $q(t)$ numero di clienti nella coda d'attesa; $z(t)$ numero di clienti in servizio; $x(t)$ numero di clienti nell'intero sistema. Naturalmente $$x(t)=q(t)+z(t).$$ Inoltre $x(t)=A(t)-D(t)$ (arrivi meno partenze fino a $t$).

Definizione (stabilità). Un QS è stabile se ammette una distribuzione asintotica propria $p_x(n)$, $n=0,1,2,\dots$, per $x(t)$, indipendente dallo stato iniziale $x(0)$. Se la distribuzione asintotica è identicamente nulla o dipende dallo stato iniziale, il QS è instabile.

Parte 2: le metriche

Stabilità per i sistemi senza blocco. I clienti devono arrivare, in media, a un tasso minore di quello a cui possono essere serviti: $$\lambda<m\mu.$$ Se $\lambda>m\mu$ la coda cresce indefinitamente, perché i clienti arrivano più in fretta di come possono essere serviti: si accumulano in coda al tasso medio $\lambda-m\mu$. Nelle slide la simulazione di una M/M/1 con $\lambda$ solo l'$1\%$ maggiore di $\mu$ mostra il numero di clienti $x(t)$ che cresce senza limite. I sistemi con blocco sono sempre stabili, perché il numero di clienti è limitato da $K$.

Misure di tempo

• $w_n$: tempo di attesa (di accodamento) di $C_n$, cioè il tempo passato nel buffer prima di entrare in servizio;
• $y_n$: tempo di servizio;
• $s_n$: tempo di sistema, il tempo totale che $C_n$ passa nel sistema dall'arrivo alla partenza.

Con $d_n$ istante di partenza: $$s_n=d_n-t_n,\qquad s_n=w_n+y_n.$$

Misure di traffico

• Tasso di arrivo $\lambda$: numero medio di arrivi per unità di tempo.
• Traffico offerto $G$: numero medio di arrivi durante il tempo medio di servizio,

  $$G=\frac\lambda\mu=\lambda E[y].$$

• Throughput $\eta$ (tasso di uscita): numero medio di clienti che lasciano il sistema per unità di tempo. Con $r_n=d_n-d_{n-1}$ tempo di interpartenza, $\eta=1/E[r]$.
• Traffico utile $S$: numero medio di partenze durante il tempo medio di servizio, cioè il throughput normalizzato al tasso di servizio: $$S=\frac\eta\mu=\eta E[y]=\frac{E[y]}{E[r]}\qquad(S\in[0,1]\text{ per un solo servitore}).$$
• Fattore di carico (o fattore di utilizzazione, o intensità di traffico) $\rho$, con $m$ servitori:

  $$\rho=\frac{E[y]}{mE[\tau]}=\frac\lambda{m\mu}=\frac Gm.$$

La condizione di stabilità $\lambda<m\mu$ equivale a $\rho<1$. Per un sistema stabile e senza blocco il tasso di uscita deve essere uguale al tasso di ingresso (altrimenti i clienti si accumulerebbero), quindi: $$\eta=\begin{cases}\lambda&\rho<1\ \text{(stabile)}\\ m\mu&\rho\ge1\ \text{(instabile: i servitori lavorano al massimo)}\end{cases}\qquad S=\begin{cases}G&\rho<1\\ m&\rho\ge1\end{cases}$$

Esempio. Un collegamento da $1$ Mbit/s trasmette pacchetti da $1000$ bit: $\mu=1000$ pacchetti/s ($E[y]=t_F=1$ ms). Se arrivano $\lambda=800$ pacchetti/s: $G=\rho=0{,}8$, throughput $\eta=800$ pacchetti/s (tutto quello che arriva esce), traffico utile $S=0{,}8$. Se arrivassero $\lambda=1200$ pacchetti/s: $\rho=1{,}2\ge1$, instabile; escono solo $\eta=\mu=1000$ pacchetti/s ($S=1$) e la coda cresce di $200$ pacchetti al secondo.

Parte 3: la legge di Little

Teorema (legge di Little). Il numero medio di clienti $E[x]$ in una struttura che conserva il flusso è uguale al tasso di arrivo dei clienti alla struttura per il tempo medio che un cliente vi trascorre: $$E[x]=\lambda\,E[s].$$

È un risultato fondamentale perché non fa nessuna ipotesi sui processi di arrivo e di partenza (basta che esistano i valori a regime), né sulla disciplina di servizio (vale anche con scheduling non FIFO), né sulla dipendenza tra arrivi e servizio, né sul numero di servitori.

Dimostrazione. Si conta in due modi il «tempo-cliente» totale accumulato fino al tempo $t$, cioè la somma dei secondi passati nella struttura da tutti i clienti.

1. Per istante. All'istante $u$ ci sono $x(u)=A(u)-D(u)$ clienti (arrivi meno partenze); ciascuno «consuma» un secondo-cliente per ogni secondo, quindi il tempo-cliente è l'area sotto la curva $x(u)$: $$\int_0^t x(u)\,du.$$
2. Per cliente. Il cliente $C_n$ resta nella struttura $s_n$ secondi, quindi il totale è $\sum_{n=1}^{A(t)}s_n$. I due totali coincidono a meno dei clienti ancora presenti al tempo $t$ (di cui si conta solo una parte): un errore che, in un sistema stabile, diventa trascurabile rispetto al totale quando $t\to\infty$.

Si uguagliano e si divide per $t$, moltiplicando e dividendo per $A(t)$ il membro dei clienti: $$\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$: a sinistra c'è il numero medio di clienti $E[x]$ (media temporale di $x$); $A(t)/t\to\lambda$ (tasso medio di arrivo); l'ultimo fattore è la media degli $s_n$, cioè $E[s]$. Si ottiene $E[x]=\lambda E[s]$. Non si è mai usata la distribuzione degli arrivi né l'ordine di servizio, ed è per questo che il risultato è così generale.

Applicazioni. Scegliendo la struttura:

L'ultima riga dice che il numero medio di clienti in servizio è proprio l'utilizzazione: per un servitore solo, $\rho$ è la frazione di tempo in cui è occupato.

Parte 3: la coda M/M/1

Arrivi di Poisson (tasso $\lambda$), servizio esponenziale (tasso $\mu$), un servitore, buffer infinito. Fattore di carico $$\rho=\frac\lambda\mu,\qquad\text{stabilità: }\rho<1.$$

Formula (distribuzione e numero medio nel sistema, M/M/1). Il numero di clienti nel sistema ha 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 →): $$p_x(n)=(1-\rho)\rho^{\,n},\qquad n=0,1,2,\dots$$ $$E[x]=\frac\rho{1-\rho},\qquad\mathrm{Var}(x)=\frac\rho{(1-\rho)^2}.$$

Verifica: $p_x(0)=1-\rho$ è la probabilità che il sistema sia vuoto, cioè il complemento dell'utilizzazione, come deve essere.

Da dove vengono queste formule. Con arrivi di Poisson e servizio esponenziale (entrambi senza memoria) il sistema cambia stato solo di $\pm1$: da $n$ a $n+1$ per un arrivo (tasso $\lambda$), da $n+1$ a $n$ per una partenza (tasso $\mu$). A regime il numero di passaggi al secondo da $n$ a $n+1$ e da $n+1$ a $n$ deve essere lo stesso, altrimenti la distribuzione cambierebbe nel tempo: $$\lambda\,p_x(n)=\mu\,p_x(n+1)\ \Rightarrow\ p_x(n+1)=\rho\,p_x(n)\ \Rightarrow\ p_x(n)=\rho^{\,n}p_x(0).$$ (Il primo membro è «sono nello stato $n$ e arriva un cliente», il secondo «sono nello stato $n+1$ e ne parte uno».) Le probabilità devono sommare a $1$; la somma $\sum_{n\ge0}\rho^n=\frac1{1-\rho}$ è la 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 →) e converge solo se $\rho<1$, che è proprio la condizione di stabilità: $$p_x(0)\sum_{n=0}^{\infty}\rho^n=\frac{p_x(0)}{1-\rho}=1\ \Rightarrow\ p_x(0)=1-\rho.$$ Per il valore medio (Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →) si usa la derivata della serie geometrica, $\sum_{n\ge1}n\rho^{n-1}=\frac{d}{d\rho}\frac1{1-\rho}=\frac1{(1-\rho)^2}$ (Regole di derivazioneDerivate delle funzioni elementari e delle loro inverse (arcsin, arctan, settcosh...) e regole di calcolo: linearità, prodotto (Leibniz), quoziente, funzione composta (regola della catena), funzione inversa, f(x)^g(x).Regole di derivazione →): $$E[x]=\sum_{n=0}^{\infty}n(1-\rho)\rho^n=(1-\rho)\,\rho\sum_{n=1}^{\infty}n\rho^{n-1}=(1-\rho)\,\rho\cdot\frac1{(1-\rho)^2}=\frac\rho{1-\rho}.$$ Per la varianza (Varianza e momentiI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti →) si calcola prima $E[x(x-1)]$, con $\sum_{n\ge2}n(n-1)\rho^{n-2}=\frac{d^2}{d\rho^2}\frac1{1-\rho}=\frac2{(1-\rho)^3}$: $$E[x(x-1)]=(1-\rho)\rho^2\cdot\frac2{(1-\rho)^3}=\frac{2\rho^2}{(1-\rho)^2},\qquad E[x^2]=E[x(x-1)]+E[x]=\frac{2\rho^2}{(1-\rho)^2}+\frac\rho{1-\rho},$$ $$\mathrm{Var}(x)=E[x^2]-E[x]^2=\frac{\rho^2}{(1-\rho)^2}+\frac\rho{1-\rho}=\frac{\rho^2+\rho(1-\rho)}{(1-\rho)^2}=\frac\rho{(1-\rho)^2}.$$ Anche la coda lunga ha una formula: $P[x\ge n]=\sum_{k\ge n}(1-\rho)\rho^k=(1-\rho)\rho^n\frac1{1-\rho}=\rho^{\,n}$.

Formula (coda e tempi, M/M/1). Dal numero medio nel sistema togliendo quello in servizio ($\rho$): $$E[q]=E[x]-\rho=\frac{\rho^2}{1-\rho}.$$ Con Little: $$E[s]=\frac{E[x]}\lambda=\frac{1/\mu}{1-\rho},\qquad E[w]=E[s]-\frac1\mu=\frac{\rho/\mu}{1-\rho}.$$

Il tempo medio di sistema è il tempo di servizio $1/\mu$ diviso per $(1-\rho)$: quando $\rho\to1$ il ritardo cresce senza limite.

Esempio. Il collegamento da $1$ Mbit/s con pacchetti da $1000$ bit, $\mu=1000$ pacchetti/s, e $\lambda=800$ pacchetti/s ($\rho=0{,}8$), con pacchetti di lunghezza esponenziale (M/M/1):

• $E[x]=0{,}8/0{,}2=4$ pacchetti nel sistema;
• $E[q]=0{,}8^2/0{,}2=3{,}2$ pacchetti in coda; $E[z]=0{,}8$ in servizio, e $3{,}2+0{,}8=4$;
• $E[s]=(1/1000)/0{,}2=5$ ms; Little: $\lambda E[s]=800\cdot0{,}005=4$ ✓;
• $E[w]=0{,}8\cdot(1/1000)/0{,}2=4$ ms, e $4+1=5$ ms ✓;
• il sistema è vuoto con probabilità $1-\rho=0{,}2$ e ha almeno $5$ pacchetti con probabilità $P[x\ge5]=\rho^5=0{,}8^5=0{,}328$ (formula della coda lunga ricavata sopra).

Se il carico sale a $\rho=0{,}95$: $E[s]=1/(1000\cdot0{,}05)=20$ ms, quattro volte di più: la coda è molto sensibile al carico vicino a $1$.

Parte 3: la coda M/G/1

Arrivi di Poisson, servizio con distribuzione generale, un servitore. Con $\rho=\lambda/\mu<1$, la formula di Pollaczek-Khinchin dà il tempo medio di attesa in coda in funzione del secondo momento del servizio: $$E[w]=\frac{\lambda E[y^2]}{2(1-\rho)}.$$ Nelle slide compaiono le espressioni del caso in cui il tempo di servizio è costante ($E[y^2]=1/\mu^2$, cioè M/D/1; è il caso dei pacchetti tutti uguali), che sono quelle usate poi in TDMA e FDMA. Si ricavano così: si sostituisce $E[y^2]=1/\mu^2$ in Pollaczek-Khinchin e si usa $\lambda/\mu=\rho$, $$E[w]=\frac{\lambda\cdot\frac1{\mu^2}}{2(1-\rho)}=\frac{\lambda/\mu}{2\mu(1-\rho)}=\frac{\rho}{2\mu(1-\rho)};$$ poi $E[s]=E[w]+E[y]=\frac1\mu+\frac{\rho}{2\mu(1-\rho)}$ e, con Little, $E[x]=\lambda E[s]=\rho+\frac{\lambda\rho}{2\mu(1-\rho)}=\rho+\frac{\rho^2}{2(1-\rho)}$ (ancora $\lambda/\mu=\rho$):

Formula (M/G/1 con servizio costante, usata nelle slide). $$E[x]=\rho+\frac{\rho^2}{2(1-\rho)},\qquad E[w]=\frac{\rho}{2\mu(1-\rho)},\qquad E[s]=\frac{E[x]}\lambda=\frac1\mu\left(1+\frac{\rho}{2(1-\rho)}\right).$$ Il tempo medio di servizio si ritrova per differenza: $E[y]=E[s]-E[w]=1/\mu$.

Con servizio esponenziale $E[y^2]=2/\mu^2$ e la formula di Pollaczek-Khinchin restituisce $E[w]=\frac{\lambda\cdot2/\mu^2}{2(1-\rho)}=\frac{\lambda/\mu}{\mu(1-\rho)}=\frac{\rho/\mu}{1-\rho}$, cioè il risultato M/M/1. In generale, $E[y^2]$ cresce con la variabilità del servizio: un servizio costante dimezza l'attesa rispetto a quello esponenziale a parità di $\rho$.

Esempio. Stessi dati ($\mu=1000$, $\lambda=800$, $\rho=0{,}8$) ma pacchetti tutti da $1000$ bit (servizio costante, M/D/1): $E[w]=\dfrac{0{,}8}{2\cdot1000\cdot0{,}2}=2$ ms (contro $4$ ms della M/M/1), $E[s]=2+1=3$ ms, $E[x]=0{,}8+\dfrac{0{,}64}{0{,}4}=2{,}4$ pacchetti (Little: $800\cdot0{,}003=2{,}4$ ✓).

Il grafico mostra quanto è nociva la saturazione: fino a $\rho\approx0{,}5$ il ritardo è meno del doppio del tempo di servizio, poi sale ripidamente. Un collegamento va dimensionato in modo da lavorare lontano da $\rho=1$.