Vai al contenuto
Reti di Telecomunicazione

Teoria delle code: legge di Little, coda M/M/1 e multiplazione statistica

Utilizzazione, legge di Little con dimostrazione, coda M/M/1 con distribuzione e ritardo dimostrati, crescita del ritardo con il carico, esempio numerico, vantaggio della multiplazione statistica dimostrato.

4 min di lettura 0 commenti

In una rete a pacchetti i ritardi più grandi e più variabili nascono nelle code: un router riceve pacchetti da molte direzioni e li deve trasmettere uno alla volta. Quanto si aspetta in media? Quanto si può caricare un collegamento prima che i ritardi esplodano? La teoria delle code risponde con formule semplici e sorprendentemente utili. In questa lezione vediamo la legge di Little con la sua dimostrazione, la coda M/M/1 con la dimostrazione della distribuzione del numero di pacchetti, la crescita del ritardo con il carico, e il vantaggio della multiplazione statistica dimostrato.

Il modello

Una coda è descritta da come arrivano i clienti (i pacchetti), da quanto dura il servizio (la trasmissione) e da quanti serventi ci sono. Si indicano con \lambda il tasso di arrivo (pacchetti al secondo) e con \mu il tasso di servizio (pacchetti al secondo che il collegamento trasmette quando è occupato). Il rapporto

    \[ \rho = \frac{\lambda}{\mu} \]

è l’utilizzazione: la frazione di tempo in cui il collegamento è occupato. Perché la coda non cresca all’infinito serve \rho \lt 1.

La legge di Little

Teorema (Little). In un sistema in equilibrio, il numero medio di clienti presenti E[N], il tasso di arrivo \lambda e il tempo medio trascorso nel sistema E[T] sono legati da

    \[ E[N] = \lambda\,E[T] \]

Dimostrazione (idea). Si osserva il sistema per un tempo lungo \tau. Si disegna il numero di clienti presenti in funzione del tempo e se ne calcola l’area sotto la curva. La si può calcolare in due modi: integrando il numero di presenti nel tempo, \int_0^\tau N(t)dt = \tau\,E[N]; oppure sommando il tempo che ciascun cliente ha trascorso nel sistema, perché ognuno contribuisce all’area con una striscia di altezza 1 e lunghezza pari alla sua permanenza. Nel tempo \tau arrivano circa \lambda\tau clienti, con permanenza media E[T], per un’area \lambda\tau\,E[T]. Uguagliando e dividendo per \tau si ottiene la legge. ∎

Vale per qualsiasi distribuzione degli arrivi e dei servizi, e per qualsiasi parte del sistema: la sola coda, il solo servente, una rete intera. Se in un router ci sono in media 50 pacchetti e ne arrivano 10 000 al secondo, ciascuno ci resta in media 5 ms.

La coda M/M/1

Il modello più semplice ha arrivi di Poisson (indipendenti, con tempi tra un arrivo e l’altro esponenziali), tempi di servizio esponenziali e un solo servente: si scrive M/M/1. Lo stato è il numero n di pacchetti presenti.

Teorema. In equilibrio la probabilità di trovare n pacchetti è p_n = (1 - \rho)\rho^n, e

    \[ E[N] = \frac{\rho}{1 - \rho},\qquad E[T] = \frac{1}{\mu - \lambda} \]

Dimostrazione. Lo stato passa da n a n + 1 con un arrivo, a tasso \lambda, e da n + 1 a n con una partenza, a tasso \mu. In equilibrio il flusso di probabilità tra due stati adiacenti si bilancia: \lambda p_n = \mu p_{n+1}, cioè p_{n+1} = \rho\,p_n, da cui p_n = \rho^n p_0. La somma delle probabilità deve valere 1: p_0\sum\rho^n = p_0/(1 - \rho) = 1, quindi p_0 = 1 - \rho. La media di una distribuzione geometrica di questo tipo è \sum n(1-\rho)\rho^n = \rho/(1 - \rho). Infine, per la legge di Little, E[T] = E[N]/\lambda = \frac{\rho}{\lambda(1-\rho)} = \frac{1}{\mu - \lambda}. ∎

Ritardo medio nella coda M/M/1 in funzione dell'utilizzazione
Il tempo medio nel sistema, misurato in tempi di servizio, vale 2 con il collegamento occupato al 50 %, 5 all’80 % e 10 al 90 %, e cresce senza limiti avvicinandosi al 100 %.

La lezione del grafico

Il ritardo, misurato in tempi di servizio 1/\mu, vale 1/(1 - \rho): 2 al 50 % di utilizzazione, 5 all’80 %, 10 al 90 %, 100 al 99 %. La crescita è dolce fino a metà carico e violenta oltre l’80 %.

Esempio. Un collegamento da 10 Mb/s con pacchetti da 1000 byte ha \mu = 1250 pacchetti al secondo, cioè 0,8 ms per pacchetto. Con \lambda = 1000 pacchetti al secondo (\rho = 0{,}8) il tempo medio nel sistema è 1/(1250 - 1000) = 4 ms: cinque volte il tempo di trasmissione. Per questo i gestori di rete aggiungono capacità ben prima che i collegamenti siano saturi, e per questo una rete “lenta” spesso non è lenta ma carica.

Il traffico reale non è esattamente di Poisson: è più a raffiche, e i ritardi a parità di carico sono maggiori. Ma la forma della curva, con l’esplosione vicino a \rho = 1, resta.

La multiplazione statistica

Teorema. Un unico collegamento di capacità C condiviso da N flussi ciascuno di tasso \lambda dà un ritardo medio N volte minore di N collegamenti separati di capacità C/N, ciascuno dedicato a un flusso.

Dimostrazione. Con collegamenti separati, ciascuno ha tasso di servizio \mu/N (dove \mu corrisponde alla capacità C) e arrivi \lambda: E[T] = 1/(\mu/N - \lambda) = N/(\mu - N\lambda). Con il collegamento condiviso il servizio è \mu e gli arrivi N\lambda: E[T] = 1/(\mu - N\lambda). Il rapporto è N. L’utilizzazione è la stessa nei due casi. ∎

È la giustificazione quantitativa della commutazione di pacchetto (lezione sull’architettura): mettere in comune le risorse riduce le attese, perché un flusso può usare la capacità lasciata libera dagli altri. Lo stesso principio, mettere in comune le risorse, spiega perché in un supermercato una coda unica che serve più casse funziona meglio di code separate.

Articoli correlati

Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
0
Would love your thoughts, please comment.x
()
x