Esercizio - carico di un collegamento con pacchetti di lunghezza fissa

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (esempio numerico dagli appunti di Bressanone). Su un collegamento con bit-rate $R_b=1$ Mbit/s arrivano $\lambda=50$ pacchetti/s, tutti di lunghezza $L=10\,000$ bit. Si calcolino la capacità del sistema in pacchetti/s, si verifichi la stabilità, si calcolino il fattore di carico, il traffico offerto e il throughput; poi, supponendo arrivi di Poisson, il numero medio di pacchetti nel sistema e il ritardo medio; infine che cosa cambia se $\lambda$ sale a $95$ e a $120$ pacchetti/s.

Teoria usata: 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 →, 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 →.

Capacità e stabilità

Il tempo per trasmettere un pacchetto è $t_p=\frac L{R_b}=\frac{10^4}{10^6}=10$ ms: il servizio è costante. Il tasso di servizio è $$\mu=\frac1{t_p}=\frac{R_b}L=\frac{10^6}{10^4}=100\ \text{pacchetti/s}$$ (è il solito cambio di unità da bit/s a pacchetti/s). Con un solo servitore (la linea), la condizione di stabilità $\lambda<\mu$ è soddisfatta: $50<100$. Fattore di carico e traffico offerto coincidono (un servitore): $\rho=G=\frac\lambda\mu=\frac{50}{100}=0{,}5$. Il sistema è stabile quindi il throughput è $\eta=\lambda=50$ pacchetti/s (cioè $500$ kbit/s, metà della capacità) e il throughput normalizzato è $S=\frac\eta\mu=0{,}5=G$.

Ritardo con arrivi di Poisson (M/D/1)

Se gli arrivi sono di Poisson il sistema è M/D/1 ($E[y]=t_p=\frac1\mu$, $E[y^2]=\frac1{\mu^2}$). Con Pollaczek-Khinchin: $$E[w]=\frac{\rho}{2\mu(1-\rho)}=\frac{0{,}5}{2\cdot100\cdot0{,}5}=5\ \text{ms},\quad E[s]=E[w]+t_p=15\ \text{ms},\quad E[x]=\lambda E[s]=0{,}75\ \text{pacchetti}$$ (e $E[x]=\rho+\frac{\rho^2}{2(1-\rho)}=0{,}5+0{,}25=0{,}75$ ✓). Se invece gli arrivi fossero a intervalli costanti di $20$ ms (processo di arrivo deterministico, G/D/1 con $\rho=0{,}5$) nessun pacchetto aspetterebbe: ogni pacchetto trova il collegamento libero e $E[w]=0$, $E[s]=10$ ms: l'attesa è dovuta soltanto all'irregolarità degli arrivi.

Che cosa succede al crescere del carico

Con $\lambda=95$ ($\rho=0{,}95$) il ritardo è $19$ volte quello a $\rho=0{,}5$ (da $5$ a $95$ ms di attesa): il collegamento è stabile ma molto vicino al limite. Con $\lambda=120$ pacchetti/s $\rho=1{,}2>1$: il sistema è instabile; la linea lavora sempre al massimo ($S=1$, $\eta=\mu=100$ pacchetti/s) e la coda cresce di $\lambda-\mu=20$ pacchetti al secondo, senza regime stazionario.