Esercizio - linea condivisa da dieci sessioni, commutazione di pacchetto e di circuito

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

Testo. Una linea di trasmissione ha bit-rate costante $R_b=50$ kbit/s. Su di essa si vuole inviare il traffico di $10$ sessioni a commutazione di pacchetto, ciascuna delle quali genera pacchetti secondo un processo di Poisson con $150$ pacchetti al minuto in media. I pacchetti hanno lunghezza $L$ esponenziale di media $1000$ bit. Che sistema a coda è? Che sistema sarebbe se i pacchetti fossero lunghi esattamente $1000$ bit? Quali metriche di prestazione si possono usare e che cosa rappresentano? Che cosa succede se si usa la commutazione di circuito? Come cambiano le prestazioni?

Teoria usata: 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 →, 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 →, Introduzione alle reti di telecomunicazioneUn servizio di telecomunicazione porta informazione da un trasmettitore a un ricevitore attraverso un canale. Le comunicazioni si classificano per destinatari (unicast, broadcast, multicast, anycast, multi-point) e per direzione (unidirezionali, bidirezionali; canali half-duplex e full-duplex); la rete è un grafo (nodi e archi) con topologie stella, mesh, albero, anello, bus, e una parte di accesso e una di core. Le risorse si danno con la commutazione di circuito (riservate) o di pacchetto (condivise, datagramma o circuito virtuale). Il controllo è diviso in livelli con protocolli, primitive, PDU/SDU/PCI e incapsulamento $PDU_N=PCI_N+SDU_N$; il modello ISO/OSI ha 7 livelli.Introduzione alle reti di telecomunicazione →.

Parametri del sistema

Arrivi. Ogni sessione: $150$ pacchetti/min $=2{,}5$ pacchetti/s. Le $10$ sessioni sono indipendenti: per la sovrapposizione il flusso totale è ancora di Poisson con $$\lambda=10\cdot2{,}5=25\ \text{pacchetti/s}$$ (cioè $1500$ pacchetti/min).

Servizio. Il tempo di servizio è il tempo di trasmissione del pacchetto, $y=\frac L{R_b}$; la media è $E[y]=\frac{\bar L}{R_b}=\frac{1000}{50\,000}=0{,}02$ s, e $\mu=\frac1{E[y]}=50$ pacchetti/s. Il carico è $\rho=\frac\lambda\mu=\frac{25}{50}=0{,}5<1$: stabile.

Lunghezza esponenziale: M/M/1

Se $L$ è esponenziale, anche $y=\frac L{R_b}$ lo è; arrivi di Poisson, servizio esponenziale, un servitore (la linea), coda infinita: M/M/1. Metriche di occupazione: $$E[x]=\frac\rho{1-\rho}=1,\qquad E[z]=\rho=0{,}5,\qquad E[q]=\frac{\rho^2}{1-\rho}=0{,}5\ \text{pacchetti};$$ metriche temporali (con Little): $$E[y]=0{,}02\ \text{s},\qquad E[s]=\frac{E[x]}\lambda=\frac1{\mu-\lambda}=0{,}04\ \text{s},\qquad E[w]=E[s]-E[y]=0{,}02\ \text{s}.$$

Lunghezza costante: M/D/1

Se i pacchetti sono tutti di $1000$ bit il tempo di servizio è costante, $y=0{,}02$ s: M/D/1. Con Pollaczek-Khinchin ($E[y^2]=\frac1{\mu^2}$): $$E[w]=\frac\rho{2\mu(1-\rho)}=\frac{0{,}5}{2\cdot50\cdot0{,}5}=0{,}01\ \text{s},\quad E[s]=E[w]+E[y]=0{,}03\ \text{s},$$ $$E[x]=\lambda E[s]=0{,}75,\qquad E[q]=\lambda E[w]=0{,}25,\qquad E[z]=0{,}5\ \text{pacchetti}.$$ Con servizio costante l'attesa in coda è la metà di quella dell'M/M/1 ($0{,}01$ contro $0{,}02$ s): la variabilità della lunghezza dei pacchetti allunga i ritardi.

Metriche di prestazione

• Occupazione: $E[x]$ pacchetti presenti (memoria di buffer necessaria, in media); $E[q]$ in coda; $E[z]$ in servizio, uguale a $\rho$: frazione di tempo in cui la linea trasmette.
• Tempi: $E[w]$ ritardo di accodamento, $E[y]$ tempo di trasmissione, $E[s]$ ritardo totale (senza propagazione).
• Traffico: $\rho$ (carico) e throughput $\eta=\lambda=25$ pacchetti/s ($25\cdot1000=25$ kbit/s utili: la metà della capacità).

Commutazione di circuito

Con la commutazione di circuito la capacità è divisa tra le $10$ sessioni in modo fisso (per esempio TDMA o FDMA): ogni sessione ha $\frac{R_b}{10}=5$ kbit/s, quindi un servitore con $\mu_1=\frac{5000}{1000}=5$ pacchetti/s, ed è una coda separata con arrivi $\lambda_1=2{,}5$ pacchetti/s. Ciascuna sessione è un sistema M/M/1 (o M/D/1) indipendente, con $$\rho_1=\frac{2{,}5}{5}=0{,}5\quad(\text{lo stesso carico}).$$ Le metriche di occupazione di ogni coda sono quelle di prima ($E[x_1]=1$ per M/M/1, $0{,}75$ per M/D/1: ma ora ci sono $10$ code, quindi dieci volte più pacchetti totali). I tempi invece si dilatano di un fattore $10$: il tempo di servizio di un pacchetto diventa $E[y_1]=\frac{1000}{5000}=0{,}2$ s e $$\text{M/M/1: }E[s_1]=\frac1{\mu_1-\lambda_1}=\frac1{5-2{,}5}=0{,}4\ \text{s},\ E[w_1]=0{,}2\ \text{s};\qquad\text{M/D/1: }E[s_1]=0{,}3\ \text{s},\ E[w_1]=0{,}1\ \text{s}.$$

Conclusione. A parità di carico e di capacità totale, la linea condivisa (commutazione di pacchetto, una sola coda) dà un ritardo dieci volte minore: un pacchetto di una sessione può usare l'intera capacità quando le altre sono inattive, mentre in un circuito la capacità inutilizzata di una sessione non può essere usata dalle altre. Il prezzo è che il ritardo non è garantito. (È lo stesso risultato "CC meglio di PC" del confronto tra M/M/$m$ e $m$ code M/M/1: 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 →, §5.)