Processi di arrivo e processo di Poisson

La teoria delle code risponde a una domanda semplice: se i clienti (pacchetti, chiamate, job) arrivano a caso e il servitore (il collegamento, un processore) lavora a ritmo finito, quanto aspettano e quanti se ne accumulano? Prima di calcolare bisogna descrivere come arrivano i clienti e come vengono serviti. Questa nota costruisce il modello e studia in dettaglio il caso fondamentale, gli arrivi di Poisson; le formule delle code sono nelle note successive (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 →). 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) e, per la versione di Ing. Elettronica, 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 →. Prerequisiti: 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 →, 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 →, 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 →, 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 →.

1. Il sistema a coda

Definizione (sistema a coda, queueing system). È un sistema fatto da clienti che arrivano, un'area di accodamento (queue, buffer) dove attendono e un servizio fornito da $m$ servitori (servers) in parallelo. Si assume che i clienti siano identici, i servitori identici e il servizio instancabile (un servitore libero serve sempre il cliente seguente).

Esempio. Un router riceve pacchetti: i pacchetti sono i clienti, il buffer di uscita è la coda, il collegamento in uscita è un servitore ($m=1$) che "serve" un pacchetto per il tempo che serve a trasmetterlo. Una centrale con $m$ operatori è un sistema a $m$ servitori.

Si studiano: il processo degli arrivi, il processo di servizio, la struttura della coda (capacità, disciplina), e se ne ricavano misure di prestazione. I clienti escono dopo il servizio: c'è anche un processo di partenza, di cui $D(t)$ è il conteggio.

2. Il processo degli arrivi

Definizione (processo di arrivo). Il $n$-esimo cliente $C_n$ arriva all'istante $t_n$ ($t_0$ è l'istante di riferimento). Il tempo di interarrivo è $\tau_n=t_n-t_{n-1}$. Il processo di punto è la successione (aleatoria) degli istanti $t_n$, cioè una sequenza di impulsi di Dirac in $t_n$; il processo di conteggio $A(t)$ è il numero di arrivi in $[0,t]$ (una funzione a gradini che sale di 1 a ogni arrivo, il cui "derivato" è il processo di punto: $A(t)=\int_0^t\sum_n\delta(u-t_n)\,du$, 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 →).

Si suppone una popolazione infinita e arrivi senza memoria: i $\tau_n$ sono indipendenti e identicamente distribuiti (i.i.d.) con la stessa funzione di distribuzione. Se i $\tau_n$ hanno media $E[\tau]=m_\tau$ finita e il processo è ergodico (Segnali, potenza e decibelRichiami che servono in tutto il corso. Unità SI e prefissi (kilo = $10^3$, bit e non byte); decibel $[x]{dB}=10\log{10}x$ per le potenze e $20\log_{10}$ per le ampiezze (prodotti = somme); banda di un segnale (primo zero, a $\alpha$ dB, di energia) e banda pratica; energia, potenza e teorema di Parseval; processi aleatori: media, potenza, autocorrelazione, stazionarietà (WSS), ergodicità, densità spettrale di potenza $\mathcal P_x(f)$ e filtraggio $\mathcal P_y=\lvert G\rvert^2\mathcal P_x$.Segnali, potenza e decibel →, §6), il tasso di arrivo è $$\boxed{\lambda=\frac1{m_\tau}}\qquad[\text{clienti/s}],$$ il numero medio di arrivi per unità di tempo. Se $\lambda(t)=\lambda$ è costante il processo è omogeneo; in generale $\lambda(t)=\frac{d\,m_A(t)}{dt}$ con $m_A(t)=E[A(t)]$, la "densità" di arrivi in un tempo infinitesimo.

Esempio. Pacchetti con $m_\tau=0{,}5$ s: $\lambda=2$ pacchetti/s. Se arrivano $90$ clienti all'ora $\lambda=\frac{90}{3600}=0{,}025$ s$^{-1}$, e $m_\tau=40$ s.

Tre scelte per la distribuzione degli interarrivi:

• Poisson (interarrivi esponenziali): arrivi "a caso", senza memoria, il modello standard;
• deterministico: $\tau_n=m_\tau$ sempre (arrivi equispaziati; per esempio una linea sempre piena di pacchetti di lunghezza $L$ uno dopo l'altro a bit-rate $R_b$ ha $\lambda=\frac{R_b}L$);
• Erlang-$k$: $\tau_n$ somma di $k$ esponenziali indipendenti; è più regolare dell'esponenziale e tende al deterministico per $k\to\infty$.

Per un Erlang-$k$ in cui ogni esponenziale ha tasso $k\lambda$ la media è $k\cdot\frac1{k\lambda}=\frac1\lambda$ e la varianza $k\cdot\frac1{k^2\lambda^2}=\frac1{k\lambda^2}$ (le medie e le varianze si sommano: Somma di variabili aleatorie indipendentiSe X e Y sono indipendenti, la legge di Z = X + Y è la convoluzione: p_Z(n) = Σ_k p_X(k) p_Y(n − k) nel discreto, f_Z(z) = ∫ f_X(z − y) f_Y(y) dy nel continuo. Casi notevoli: Bin(n,p) + Bin(m,p) = Bin(n+m,p), Poi(λ) + Poi(μ) = Poi(λ+μ), Geo + Geo con densità (n−1)p²(1−p)^(n−2), Exp(λ) + Exp(λ) = Γ(2,λ), gaussiane indipendenti sommano medie e varianze.Somma di variabili aleatorie indipendenti →); la densità è $p(a)=\frac{(k\lambda)^ka^{k-1}e^{-k\lambda a}}{(k-1)!}$.

3. Il processo di Poisson

Definizione (processo di Poisson). Un processo di conteggio $A(t)$ è di Poisson se il numero di arrivi in intervalli disgiunti è (1) indipendente e (2) di Poisson con parametro $\int_{\mathcal J}\lambda(t)\,dt$ per l'intervallo $\mathcal J$. È omogeneo se $\lambda(t)=\lambda$. In un intervallo di durata $T$ vale $$P[k\text{ arrivi in }T]=\frac{(\lambda T)^k}{k!}e^{-\lambda T},\qquad E=\operatorname{Var}=\lambda T.$$

Esempio. $\lambda=2$ s$^{-1}$ e $T=1{,}5$ s: la media è $\lambda T=3$ e $P[k]=\frac{3^k}{k!}e^{-3}$, con $e^{-3}=0{,}0498$: $P[0]=0{,}0498$, $P[1]=0{,}1494$, $P[2]=P[3]=0{,}2240$, $P[4]=0{,}1680$. Il caso $k=0$, $e^{-\lambda T}$, è quello che compare nei protocolli ALOHA (nessun altro pacchetto nell'intervallo di vulnerabilità, 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 →).

3.1 Interarrivi esponenziali

Teorema. Gli interarrivi di un processo di Poisson omogeneo di tasso $\lambda$ sono i.i.d. con densità esponenziale $p_\tau(a)=\lambda e^{-\lambda a}\mathbb 1(a)$, funzione di distribuzione $P_\tau(a)=1-e^{-\lambda a}$ e media $E[\tau]=\frac1\lambda$.

Dimostrazione. L'evento "$\tau_n>a$" significa che dopo l'arrivo $t_{n-1}$ non ne avviene nessuno per $a$ secondi, cioè $A$ non aumenta in $[t_{n-1},t_{n-1}+a]$. Per la definizione, il numero di arrivi in un intervallo di durata $a$ è Poisson di media $\lambda a$ e indipendente da quello che è accaduto prima (in particolare da $t_{n-1},t_{n-2},\dots$): $P[\text{nessun arrivo in }a]=e^{-\lambda a}$. Allora $$P[\tau_n\le a\mid t_{n-1},t_{n-2},\dots]=1-e^{-\lambda a},\qquad a\ge0,$$ che non dipende dal passato: gli interarrivi sono indipendenti e tutti con la stessa distribuzione. Derivando $p_\tau(a)=\lambda e^{-\lambda a}$, e $E[\tau]=\int_0^\infty a\lambda e^{-\lambda a}da=\frac1\lambda$ (per parti). $\square$

Quindi il tasso del processo coincide con $\frac1{E[\tau]}$, come deve essere. Densità e media: la densità è massima in $a=0$ (gli interarrivi brevi sono i più probabili) pur con media $\frac1\lambda$: la media è il baricentro di una coda lunga, non il valore più frequente.

3.2 Assenza di memoria

Proprietà (memoryless). Per un interarrivo esponenziale $P[\tau\le a\mid\tau\ge s]=P[\tau\le a-s]$ per $a>s$: l'attesa residua ha la stessa distribuzione, traslata, indipendentemente da quanto si è già aspettato.

Dimostrazione. $P[\tau\le a\mid\tau\ge s]=\frac{P[s\le\tau\le a]}{P[\tau\ge s]}=\frac{e^{-\lambda s}-e^{-\lambda a}}{e^{-\lambda s}}=1-e^{-\lambda(a-s)}=P[\tau\le a-s].\ \square$

Nel calcolo non si è mai usato che $t_{n-1}$ fosse un istante di arrivo: vale per qualsiasi istante di partenza (se arrivo in coda alle 10:00 o sono qui da un'ora, il tempo che manca al prossimo arrivo ha sempre la stessa distribuzione). Questa proprietà rende "Markoviano" il sistema (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 →). L'esponenziale è l'unica distribuzione continua con questa proprietà.

Esempio. $\lambda=2$ s$^{-1}$. Probabilità che l'attesa superi 1,5 s dato che è già durata 1 s: $P[\tau>1{,}5\mid\tau>1]=\frac{e^{-3}}{e^{-2}}=e^{-1}=0{,}368=P[\tau>0{,}5]$.

3.3 Probabilità in un intervallo infinitesimo

Per un intervallo breve $h$, dalla distribuzione di Poisson e dallo sviluppo di Taylor $e^{-x}=1-x+\frac{x^2}2-\dots$: $$P[A(h)=0]=e^{-\lambda h}=1-\lambda h+o(h),\qquad P[A(h)=1]=\lambda he^{-\lambda h}=\lambda h+o(h),$$ $$P[A(h)\ge2]=1-e^{-\lambda h}(1+\lambda h)=\frac{(\lambda h)^2}2+\dots=o(h),$$ dove $o(h)$ indica un termine che diviso per $h$ tende a $0$ quando $h\to0$. In parole: in un tempo brevissimo c'è al massimo un arrivo, con probabilità $\lambda h$; due arrivi (o un arrivo e una partenza insieme) sono trascurabili. (Un'altra via, dalle slide: $P[A(h)\ge2]=P[\tau_1+\tau_2<h]\le P[\tau_1\le h]P[\tau_2\le h]=(\lambda h+o(h))^2=o(h)$.) Sono le formule da cui si ricavano le equazioni delle catene di Markov.

Esempio. $\lambda=50$ pacchetti/s e $h=1$ ms: $P[A(h)=1]\approx0{,}05$ (esatto $0{,}04756$) e $P[A(h)\ge2]=0{,}0012$: trascurabile rispetto a $0{,}05$.

3.4 Proprietà del processo di Poisson

Sovrapposizione (superposition). La somma di processi di Poisson indipendenti è un processo di Poisson con tasso uguale alla somma dei tassi, perché la somma di variabili di Poisson indipendenti è di Poisson con parametro la somma dei parametri (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 →). Esempio. $8$ partite di calcio, ciascuna con $3$ gol in $96$ minuti distribuiti uniformemente: ogni partita è Poisson di tasso $\lambda_0=\frac3{96}=\frac1{32}$ min$^{-1}$ e il flusso totale dei gol ha $\lambda=8\lambda_0=\frac14$ min$^{-1}$ (un gol ogni 4 minuti). Così $10$ sessioni da $150$ pacchetti/minuto danno $1500$ pacchetti/minuto $=25$ pacchetti/s.

Diradamento (thinning, splitting). Se ogni arrivo di un processo di Poisson di tasso $\lambda$ viene tenuto con probabilità $p$ (indipendentemente dagli altri) e scartato con probabilità $1-p$, il processo dei tenuti è di Poisson con tasso $p\lambda$ (e quello degli scartati, indipendente, con $(1-p)\lambda$). Dimostrazione: il numero $K$ di tenuti in $T$, condizionato a $N$ arrivi, è binomiale$(N,p)$, e $$P[K=k]=\sum_{n\ge k}e^{-\lambda T}\frac{(\lambda T)^n}{n!}\binom nkp^k(1-p)^{n-k}=e^{-\lambda T}\frac{(\lambda pT)^k}{k!}\sum_{j\ge0}\frac{(\lambda(1-p)T)^j}{j!}=e^{-\lambda pT}\frac{(\lambda pT)^k}{k!}$$ (con $j=n-k$ e la serie esponenziale che somma $e^{\lambda(1-p)T}$). $\square$ Esempio. Pacchetti con $\lambda=10$ s$^{-1}$, ciascuno danneggiato con $p=0{,}1$: i pacchetti danneggiati sono un processo di Poisson con tasso $1$ s$^{-1}$.

Legge degli eventi rari. Una binomiale di $n$ prove con probabilità $p$ piccola e $np=\lambda T$ fisso tende a una Poisson di parametro $\lambda T$ (Variabile di Poisson e approssimazione della binomialeX ~ Po(λ), λ > 0, assume i valori 0, 1, 2, … con P(X = k) = e^{−λ} λᵏ/k!; λ è il numero medio di eventi. Nasce come limite della binomiale: se Xₙ ~ B(n, λ/n) allora P(Xₙ = k) → e^{−λ}λᵏ/k!. In pratica B(n,p) ≈ Po(np) se n è grande e p piccolo (regole del corso: n ≥ 20, p ≤ 0.05, p ≤ 10/n). Modella conteggi di eventi rari in un intervallo di tempo o spazio: telefonate, arrivi, terremoti, difetti, vincite.Variabile di Poisson e approssimazione della binomiale →): è il motivo per cui il processo di Poisson descrive bene tante sorgenti indipendenti e rare. Esempio. $n=1000$, $p=0{,}002$: $P[k=2]=\binom{1000}2\,0{,}002^2\,0{,}998^{998}=0{,}2709$, contro $\frac{2^2}{2!}e^{-2}=0{,}2707$ della Poisson.

Esempio (Poisson contro deterministico). A parità di tasso $\lambda=1$ s$^{-1}$, gli arrivi deterministici sono uno al secondo; con arrivi di Poisson in un secondo si hanno $0$ arrivi con probabilità $e^{-1}=0{,}368$ e $2$ o più con probabilità $1-e^{-1}(1+1)=0{,}264$: la sequenza è irregolare, con "grappoli" e "buchi", ed è per questo che la coda con arrivi di Poisson ha ritardi maggiori (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 →).

4. Il processo di servizio

Definizione (processo di servizio). Il cliente $C_n$ occupa un servitore per un tempo di servizio $y_n$. Si suppone che i $y_n$ siano i.i.d., con densità $p_y$ e funzione di distribuzione $P_y$, indipendenti dagli arrivi. Il tasso di servizio di un servitore è $$\mu=\frac1{E[y]}=\frac1{m_y}\quad[\text{clienti/s}],$$ il numero di clienti che servirebbe al secondo se avesse sempre da lavorare. Con $m$ servitori in parallelo il tasso massimo è $m\mu$.

Distribuzioni tipiche del servizio: deterministico ($y=\frac1\mu$ sempre, $p_y(a)=\delta\left(a-\frac1\mu\right)$), esponenziale ($p_y(a)=\mu e^{-\mu a}$, con $E[y]=\frac1\mu$ e $E[y^2]=\frac2{\mu^2}$), Erlang. Se i servizi sono esponenziali anche il tasso a cui un servitore impegnato completa un servizio nell'unità di tempo è senza memoria: in $[0,h]$ finisce con probabilità $\mu h+o(h)$.

Sistemi a commutazione di pacchetto. I clienti sono pacchetti (si misurano in pacchetti/s). Se il collegamento ha bit-rate $R_b$ e i pacchetti sono lunghi $L$ bit, il tempo di servizio è $y=\frac L{R_b}$: se $L$ è costante $y$ è deterministico e $\mu=\frac{R_b}L$ (un semplice cambio di unità, da bit/s a pacchetti/s); se $L$ è esponenziale con media $\bar L$ anche $y$ lo è e $\mu=\frac{R_b}{\bar L}$.

Esempio. $R_b=50$ kbit/s e pacchetti di $1000$ bit: $\mu=\frac{50\,000}{1000}=50$ pacchetti/s, tempo di servizio $20$ ms.

5. La struttura della coda e la notazione di Kendall

• Capacità della coda $Q$: il massimo numero di clienti in attesa; capacità del sistema $K=m+Q$ (in coda più in servizio).
• Sistema bloccante (blocking): se $K$ è finito i clienti che trovano il sistema pieno non entrano. Se $P_{BLK}$ è la probabilità di blocco, il tasso dei clienti accettati è $\lambda_a=\lambda(1-P_{BLK})$ e quello dei persi $\lambda_d=\lambda P_{BLK}$. Un sistema bloccante è sempre stabile. Non bloccante: $K=\infty$.
• Disciplina: l'ordine con cui si prende dalla coda: FCFS/FIFO (first come first served, usata se non detto altrimenti), LCFS/LIFO, con priorità.

Notazione di Kendall. $A/B/m/K/N-S$: $A$ processo di arrivo, $B$ processo di servizio, $m$ servitori, $K$ capacità, $N$ popolazione, $S$ disciplina. $K$, $N$ e $S$ sono opzionali (default: $K=N=\infty$, FCFS). $A,B\in\{$M (markoviano: Poisson/esponenziale), D (deterministico), G (generale)$\}$.

Esempio. M/M/1: arrivi di Poisson, servizio esponenziale, un servitore, buffer infinito. M/D/1: servizio costante (pacchetti tutti uguali). M/M/m: $m$ servitori. M/M/1/K: buffer finito. M/G/1: servizio qualsiasi. Una linea con $10$ sessioni di pacchetti di lunghezza esponenziale è una M/M/1 (arrivi sovrapposti Poisson); con pacchetti di lunghezza fissa è una M/D/1.

Errori comuni

• Confondere il tasso $\lambda$ (arrivi al secondo) con il tempo medio di interarrivo $\frac1\lambda$.
• Dimenticare che la somma di processi di Poisson indipendenti si fa sommando i tassi, ma la somma dei tempi di interarrivo (Erlang) non è Poisson.
• Pensare che "senza memoria" significhi che l'attesa media residua sia zero: è $\frac1\lambda$ qualunque sia il tempo già trascorso.
• Convertire male $\mu$: per un collegamento è $\mu=\frac{R_b}{\bar L}$ con $R_b$ in bit/s e $\bar L$ in bit.
• Usare $P[A(h)=1]\approx\lambda h$ per $h$ non piccolo.