Sistemi a coda - processo di Poisson, MᐟMᐟ1 e formula di Little

Perché servono

In una rete i pacchetti arrivano in modo irregolare a un nodo (un router, il buffermemoria in cui i pacchetti attendono di essere serviti di un trasmettitore) che li serve a ritmo finito, quello del collegamento in uscita (Sistemi di telecomunicazioni e modello ISO-OSIUn servizio di telecomunicazioni porta informazione da una sorgente a una destinazione lontana attraverso trasmettitore, canale e ricevitore. Le comunicazioni si classificano per destinatari (unicast, broadcast, multicast) e per direzione (simplex, half-duplex, full-duplex); le reti hanno una topologia (stella, mesh, albero, anello, bus) e usano commutazione di circuito o di pacchetto. Le funzioni di rete sono divise in strati: nel modello ISO-OSI sono 7 e questo corso studia quasi solo lo strato fisico.Sistemi di telecomunicazioni e modello ISO-OSI →, Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMAQuando più nodi condividono un mezzo serve un protocollo di accesso (MAC). Accesso deterministico: FDMA (una banda per utente) e TDMA (uno slot per utente in una trama): nessuna collisione, a ogni utente $\frac{R_b}N$ meno le perdite di sincronismo. Accesso aleatorio: ALOHA puro ($S=Ge^{-2G}$, massimo $\frac1{2e}=0{,}184$ in $G=0{,}5$), slotted ALOHA ($S=Ge^{-G}$, massimo $\frac1e=0{,}368$ in $G=1$), CSMA (si ascolta prima di trasmettere: nel non persistente $S=\frac{Ge^{-aG}}{G(1+2a)+e^{-aG}}$, con $a=\frac{\tau_P}{t_P}$ piccolo si arriva a $\approx0{,}8$-$0{,}9$).Metodi di accesso al mezzo - FDMA, TDMA, ALOHA e CSMA →). Quando ne arrivano più di quanti se ne servono, si accodano: la coda introduce un ritardo e, se il buffer è finito, perdite. La teoria delle code lega ritardo e perdite al traffico offerto e alla capacità.

Processo di arrivo e tempo di servizio

• Arrivi di Poissonarrivi indipendenti e casuali con un tasso medio costante con intensità $\lambda$tasso medio di arrivo, in arrivi al secondo (arrivi al secondo): il numero di arrivi in un intervallo $t$ è di Poisson di media $\lambda t$ (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 →); gli intervalli tra arrivi consecutivi sono indipendenti ed esponenzialicon densità $\lambda e^{-\lambda t}$ per $t\ge0$ di media $\frac1\lambda$ (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 →). Il modello va bene per sorgenti numerose e indipendenti.
• Tempi di servizio esponenziali di media $\frac1\mu$ ($\mu$tasso di servizio, in servizi al secondo: inverso della durata media del servizio servizi al secondo). Per un pacchetto di lunghezza $\ell$ (esponenziale di media $\bar\ell$ bit) su un collegamento di bit-rate $R$ il tempo di servizio è $\frac\ell R$, con media $\frac{\bar\ell}R$, quindi $\mu=\frac R{\bar\ell}$ ($\mu$ è la capacità in pacchetti al secondo).
• Proprietà senza memoriail tempo ancora da aspettare non dipende da quanto si è già aspettato dell'esponenziale: il tempo residuo dipende solo dallo stato attuale, per cui il numero di clienti nel sistema è una catena di Markovprocesso in cui lo stato futuro dipende solo da quello presente (un processo di nascita e morte con nascita a tasso $\lambda$ e morte a tasso $\mu$ se $n>0$).

Intensità di trafficorapporto $\rho=\frac\lambda\mu$ tra ritmo di arrivo e di servizio: frazione di tempo in cui il servitore è occupato $\rho=\frac\lambda\mu$ (adimensionale): frazione di tempo in cui il servitore è occupato. Se $\rho\ge1$ la coda cresce senza limite.

La coda M/M/1

Notazione di Kendallsigla A/B/c: tipo di arrivi, tipo di servizio, numero di servitori: M/M/1 = arrivi markoviani (Poisson) / servizio markoviano (esponenziale) / $1$ servitore, buffer infinito, disciplina FIFOfirst in first out: si serve per primo chi è arrivato per primo. Per $\rho<1$ la distribuzione stazionariaprobabilità del numero di clienti quando il sistema ha raggiunto il regime del numero $N$ di clienti nel sistema (in coda più in servizio) si trova imponendo l'equilibrio tra "salite" e "discese" ($\lambda P_n=\mu P_{n+1}$): $$P[N=n]=(1-\rho)\rho^n,\qquad n=0,1,2,\dots\ \ (\text{geometrica}).$$ Da questa:

Il tempo medio $\bar W=\frac{1/\mu}{1-\rho}$ esplode per $\rho\to1$: con $\rho=0{,}5$ il ritardo è il doppio del tempo di servizio, con $\rho=0{,}9$ è dieci volte, con $\rho=0{,}99$ cento volte. Per questo le reti non vengono caricate oltre $60$-$80\%$.

Formula di Little

Per qualunque sistema stazionario, con $\lambda$ il tasso medio di arrivo (e di uscita), $\bar N$numero medio di clienti nel sistema il numero medio di clienti nel sistema e $\bar W$tempo medio di permanenza nel sistema, attesa più servizio il tempo medio di permanenza: $$\boxed{\bar N=\lambda\,\bar W.}$$ (Vale anche per la sola coda: $\bar N_q=\lambda\bar W_q$.) Verifica per M/M/1: $\lambda\cdot\frac1{\mu-\lambda}=\frac{\lambda/\mu}{1-\lambda/\mu}=\frac\rho{1-\rho}$ ✓.

Esempio numerico (simulato)

Un server riceve file con intervalli esponenziali di media $10$ ms ($\lambda=100$ file/s) e lunghezze esponenziali di media $40$ kbit, e li invia su un collegamento a $R=5$ Mbit/s. Allora $\mu=\frac R{\bar\ell}=\frac{5\cdot10^6}{40\cdot10^3}=125$ file/s e $\rho=0{,}8$. La coda M/M/1 dà:

• $\bar N=\frac{0{,}8}{0{,}2}=4$ file nel sistema, $\bar N_q=3{,}2$ in coda;
• $\bar W=\frac1{125-100}=40$ ms, di cui $\bar W_q=32$ ms in attesa e $8$ ms di servizio; Little: $\bar N=100\cdot0{,}04=4$ ✓;
• $P[N\ge5]=0{,}8^5=0{,}328$; $P[W>100\ \text{ms}]=e^{-25\cdot0{,}1}=0{,}082$.

Una simulazione ($2\cdot10^6$ file, ricorsione di Lindley $W_{n+1}=\max(0,W_n+S_n-A_{n+1})$) dà $\bar W_q=32{,}3$ ms, $\bar W=40{,}3$ ms, $P[W>100\ \text{ms}]=0{,}083$: coerente. (Il bit-rate medio di arrivo è $\frac{\bar\ell}{1/\lambda}=\frac{40\ \text{kbit}}{10\ \text{ms}}=4$ Mbit/s, e il collegamento da $5$ Mbit/s è caricato all'$80\%$: Esercizio 28 · codifica a correzione d'errore e ARQ selective repeat per un server (tema d'esame luglio 2021).)

Buffer finito: M/M/1/K

Se il sistema può contenere al più $K$ clienti (compreso quello in servizio), gli arrivi che trovano il sistema pieno sono persi. La distribuzione è $P_n=\frac{(1-\rho)\rho^n}{1-\rho^{K+1}}$, $n=0,\dots,K$, e la probabilità di perditaprobabilità che un arrivo trovi il buffer pieno e venga scartato è quella di trovare il sistema pieno (PASTAPoisson arrivals see time averages: un arrivo di Poisson trova il sistema nello stato con la probabilità media di quello stato: gli arrivi di Poisson vedono lo stato medio): $$P_{perdita}=P_K=\frac{(1-\rho)\rho^K}{1-\rho^{K+1}}.$$ Esempio: $\rho=0{,}8$, $K=5$: $P_5=\frac{0{,}2\cdot0{,}8^5}{1-0{,}8^6}=0{,}0888$ (simulazione: $0{,}0894$). Raddoppiare il buffer ($K=10$) la porta a $0{,}0345$ ($\frac{0{,}2\cdot0{,}8^{10}}{1-0{,}8^{11}}$): aumentare il buffer riduce le perdite ma allunga il ritardo.

Errori comuni

• Usare $\bar W=\frac{\rho}{1-\rho}\cdot\frac1\mu$ per il tempo nel sistema: è l'attesa in coda $\bar W_q$; il tempo nel sistema è $\frac{1/\mu}{1-\rho}$ (include il servizio).
• Dimenticare di calcolare $\mu=\frac R{\bar\ell}$ con $R$ in bit/s e $\bar\ell$ in bit.
• Applicare le formule con $\rho\ge1$: non esiste regime stazionario.
• Confondere $\lambda$ (arrivi al secondo) con l'intervallo medio $\frac1\lambda$.