Esercizi – Teoria dei protocolli

A – Collegamenti punto-punto

Esercizio 3.1.
Due stazioni A e B sono collegate da un sistema di trasmissione dati bidirezionale il cui protocollo di linea ARQ sia caratterizzato dai seguenti parametri:
• dimensione fissa delle UI, il cui header si considera trascurabile, ,
• dimensione fissa dei riscontri, ,
• tempo di elaborazione di UI e di riscontro trascurabile, .
La trasmissione dati tra le due stazioni è realizzata mediante un sistema radio che rende disponibile un canale di comunicazione così caratterizzato:
• distanza tra le due stazioni, ,
• capacità del collegamento, .
Si considera la trasmissione da A a B di un segmento dati di lunghezza . Si chiede di valutare il tempo totale di trasferimento del segmento dati e il throughput conseguito con il protocollo stop and wait in assenza di errori di trasmissione.

Esercizio 3.4.
Due stazioni A e B sono collegate da un sistema di trasmissione dati bidirezionale il cui protocollo di linea ARQ sia caratterizzato dai seguenti parametri:
• dimensione fissa delle UI, il cui header si considera trascurabile, ,
• dimensione fissa dei riscontri, ,
• tempo di elaborazione di UI e di riscontro trascurabile.
La trasmissione dati tra le due stazioni è realizzata mediante un sistema radio che rende disponibile un canale di comunicazione così caratterizzato:
• distanza tra le due stazioni, ,
• capacità del collegamento, . Sia inoltre operante un meccanismo di controllo di flusso a finestra con parametri:
• apertura della finestra di trasmissione, ,
• finestra di ricezione di apertura arbitrariamente grande,
• time-out per inizio di ritrasmissione, .
Se si adotta il protocollo go-back-n, si vuole valutare in assenza di errori di trasmissione il tempo totale di trasferimento da A a B di un segmento dati di lunghezza , il throughput realizzato e l’efficienza di utilizzazione del collegamento conseguita.

Dato che ogni UI può contenere fino a \, \mathrm{byte}, il numero delle UI da trasmettere è dato da

   

Si determinano prima di tutto i valori numerici dei tempi di trasmissione e di propagazione delle UI

   

   

   

così che il tempo richiesto per ricevere un riscontro è . Dato che , risulta e quindi l’ampiezza della finestra strozza la trasmissione. Considerando che dopo ogni evento di interruzione di trasmissione dovuto alla finestra saranno state trasmesse 20 UI, ne deriva che

   

   

   

Esercizio 3.6.
Due stazioni terrestri A e B sono connesse tramite una coppia di collegamenti ponte-radio simplex così caratterizzati: (i) collegamento diretto A-B di lunghezza e capacità ; (ii) collegamento B-A costituito da due tratte connesse tramite un riflettore radio R con lunghezza di ciascuna tratta e capacità del collegamento .
Il protocollo che controlla la trasmissione delle UI su questo collegamento sia di tipo ARQ così caratterizzato:
• dimensione variabile delle UI, che dipende della dimensione del pacchetto trasportato, fino ad una lunghezza massima , dei quali costituiscono l’header,
• dimensione fissa dei riscontri, ,
• tempo di elaborazione trascurabile nelle stazioni A e B per UI e riscontri.
Si utilizza il protocollo selective repeat con time-out e uguale apertura delle finestre di trasmissione e di ricezione . Si vuole trasferire da A a B un segmento di dati di lunghezza D = 3355 byte, imponendo che le UI utilizzate abbiano lunghezza massima ad eccezione eventualmente dell’ultima. Si chiede di calcolare in assenza di errori sul collegamento il tempo di trasferimento TSR del segmento di dati e il throughput dati effettivo della connessione , misurato in [bit/s], e quanto questo vale in percentuale rispetto al massimo throughput raggiungibile in teoria sul canale A -> B (efficienza ). Si determini anche la dimensione ottima della finestra di trasmissione che massimizza il throughput di questo collegamento.

Occorre preliminarmente calcolare i parametri base che determinano il tempo di trasferimento del blocco di dati. Dato che ogni UI può contenere fino a , il numero delle UI di lunghezza massima da trasmettere è dato da

   

Occorre quindi trasmettere anche un’ultima UI di payload per una lunghezza complessiva . Si determinano quindi i valori numerici dei tempi di trasmissione e di propagazione delle UI, considerando la configurazione della due tratte di comunicazione rappresentata in Figura E3.1:

Figura E3.1 Configurazione delle tratte trasmissive secondo l’Esercizio 3.6.

   

   

   

   

   

Si ricavano dunque i valori numerici e . Poiché , l’apertura della finestra rende discontinuo il flusso delle UI emesse dalla stazione A, come mostrato in Figura E3.2. Infatti la stazione A deve interrompere la propria trasmissione dopo avere inviato la terza UI avendo inviato tutte le UI consentite dall’apertura W_s = 3 della finestra di trasmissione. All’arrivo di ogni riscontro l’apertura della finestra di trasmissione “ruota” autorizzando l’invio di una nuova UI. Il tempo totale richiesto per trasferire il segmento di dati è allora espresso da

   

Figura E3.2 Trasmissione di UI in assenza di errore secondo l’Esercizio 3.6.

Il throughput è calcolato come

   

   

L’apertura della finestra che massimizza il throughput sul collegamento si ricava facilmente come

   

Esercizio 3.11.
Due stazioni A e B sono in comunicazione attraverso un collegamento dati su cavo di lunghezza e capacità . Il protocollo che regola il trasferimento dei dati sul collegamento è di tipo ARQ go-back-n con UI di lunghezza fissa e riscontri di lunghezza . Si assume che il flusso informativo di UI sia unidirezionale dalla stazione A alla stazione B, con riscontri positivi o negativi inviati in direzione opposta. Al tempo la stazione A inizia la trasmissione senza interruzione di UI, mentre la stazione B invia riscontri, che possono essere sia positivi che negativi, con inizio trasmissione agli istanti . Le UI sono numerate con un modulo di numerazione il più piccolo possibile. Sapendo che il collegamento è soggetto a errori che possono colpire solo le UI ma non i riscontri, si chiede di identificare le UI e i riscontri avendo numerato la prima UI trasmessa con il numero 2 e di identificare l’apertura minima della finestra in trasmissione Wsmin compatibile con questo scambio di UI.

I dati forniti consentono di calcolare i tempi di trasmissione delle UI e dei riscontri nonché i tempi di propagazione lungo il collegamento, e cioè

   

   

   

Considerati i tempi di inizio trasmissione delle diverse UI, lo scambio di UI e riscontri è rappresentato in Figura E3.3a. La successione delle trasmissioni mostra che la terza UI, cioè la numero 4, non dà luogo a riscontro, mentre quella successiva sì. Se ne deduce che la UI numero 4 è andata persa e il successivo riscontro è un NACK 4, dato che la successiva UI numero 5 viene ricevuta correttamente ma fuori sequenza. Data la natura del protocollo GBN, che definisce un’apertura unitaria della finestra in ricezione Wr, la UI numero 5 viene scartata in quanto solo la numero 4 può essere accettata. La stazione A prosegue nella trasmissione di nuove UI, tutte scartate nella stazione B, anche se corrette, in quanto fuori sequenza. A ogni UI scartata corrisponde nella stazione B la trasmissione del ricontro positivo dell’ultima UI accettata, cioè ACK 3. Alla ricezione del riscontro negativo, la stazione A provvede a ritrasmettere la UI numero 4 richiesta, seguita dalla trasmissione delle successive UI, ognuna delle quali viene regolarmente riscontrata. Dato che la stazione A trasmette 4 UI consecutive, cioè dalla numero 4 alla numero 7, in attesa di riscontro, ne consegue che , per definizione e quindi le UI sono numerate modulo 8, dovendo assumere b = 3. La numerazione delle UI e dei riscontri è mostrata in Figura E3.3b.

Figura E3.3 Scambio di UI (a) con il protocollo GBN secondo l’Esercizio 3.11 e loro identificazione (b).

B – Reti multipunto

Esercizio 3.17.
Si determini l’espressione del throughput massimo di un protocollo a prenotazione con tutte le stazioni attive, trame a lunghezza fissa con una trasmissione per ciclo e una fase di prenotazione in cui le N stazioni accedono ad un solo minislot utilizzando lo stesso meccanismo a contesa del protocollo slotted ALOHA; si ipotizza che una stazione centralizzata riscontri le prenotazioni ricevute con successo (senza collisioni) in un tempo trascurabile su un canale di ritorno dedicato.

Il throughput massimo del protocollo a prenotazione è conseguito quando si ottiene il massimo tasso di successo nella fase di prenotazione. Questo è dato dall’Equazione 3.37, cioè che implica un numero di tentativi (cicli) richiesti per avere successo nella prenotazione. Ne consegue che il throughput massimo con tutte le stazioni attive diventa

   

in cui indica il rapporto tra durata di un minislot e tempo di trasmissione della UI.

Esercizio 3.20.
Determinare la minima estensione di una rete ad anello con trasferimento di permesso (token) per un mezzo trasmissivo in rame con le seguenti caratteristiche:
• velocità sull’anello, ,
• numero di stazioni uniformemente distribuite lungo l’anello, ,
• lunghezza minima dell’unità informativa, ,
• latenza di stazione,

La latenza totale di una rete ad anello è data dall’espressione in cui indica il ritardo di propagazione sul solo mezzo trasmissivo lungo l’anello. La condizione affinché la rete possa operare correttamente è che il tempo di trasmissione di una UI a lunghezza minima non sia superiore alla latenza totale di anello. Se ciò non fosse vero, allora una stazione riceverebbe il primo bit della UI in trasmissione prima che questa sia stata completamente trasmessa, creando una collisione di segnali. Quindi la condizione

   

fornisce direttamente il valore minimo del tempo di propagazione sul mezzo trasmissivo compatibile con i dati del problema. Ricaviamo quindi

   

Assumendo quindi una velocità di propagazione v = 200000 km/s per il mezzo trasmissivo, la minima lunghezza dell’anello è

   

Esercizio 3.23.
Si generi un grafico analogo a quello di Figura 3.50 per il protocollo non-persistent CSMA per i tre valori di in figura ().

Figura 3.50 Throughput con protocollo slotted non-persistent CSMA (Esercizio 3.23).

Il grafico si ottiene utilizzando la funzione

   

che dà luogo alla Figura E3.4.

Figura E3.4 Throughput con protocollo non-persistent CSMA secondo l’Esercizio 3.23.

Esercizio 3.24.
Si determini analiticamente il valore del throughput massimo e il corrispondente valore del traffico offerto per il protocollo non-persistent CSMA per .

Come per i protocolli ALOHA il throughput massimo si ottiene a partire dall’espressione del throughput S in funzione del traffico offerto G

   

Il valore massimo della funzione si ottiene uguagliando a zero la derivata prima di questa funzione, che fornisce

   

La soluzione in forma numerica di questa equazione fornisce il valore del traffico offerto G cui corrisponde il throughput massimo, come riportato nella Tabella E3.1.

Tabella E3.1 Throughput massimo con protocollo non-persistent CSMA secondo l’Esercizio 3.24.

Esercizio 3.31.
Esprimere il valore del minimo tempo di ritardo richiesto per trasferire una UI mono-frammento nel protocollo CSMA/CA.

Il minimo tempo di trasferimento si ricava con lo stesso ragionamento che ha permesso di ricavare il massimo throughput del protocollo come rapporto tra tempo speso in trasmissione di dati di utente e tempo medio impiegato per completare la trasmissione (Equazione 3.49). Il calcolo del tempo minimo di ritardo ipotizza che il canale sia catturato al primo slot di contesa e quindi

   

Infatti il completamento della trasmissione con successo dell’unico frammento richiede che la stazione attenda DIFS () prima di iniziare la contesa, che si assume di durata nulla. La stazione invia allora la trama RTS e attende la risposta CTS, cosa che richiede complessivamente la trasmissione di due trame di controllo () e due intervalli SIFS (). Dopo il tempo di trasmissione del frammento () e un tempo di propagazione () ha luogo la trasmissione del riscontro che richiede un tempo di trasmissione () e un ultimo tempo di propagazione ().

C – Protocolli di instradamento

Esercizio 3.35.
Si chiede di determinare la tabella di instradamento dei nodi B e F della rete a sei nodi e nove rami di Figura 3.60 per i primi quattro passi di aggiornamento dell’algoritmo distance vector, assumendo che i vettori delle distanze siano trasmessi tra nodi negli stessi istanti e che l’aggiornamento in ogni nodo avvenga una volta sola per passo considerando i vettori di tutti i nodi adiacenti.

Figura 3.60 Topologia di rete (Esercizio 3.35).

L’applicazione dell’algoritmo di instradamento distance vector dà luogo all’evoluzione della tabella di instradamento nei nodi B e F mostrata nella Figura E3.5.

Figura E3.5 Tabelle di instradamento dei nodi B e F secondo l’Esercizio 3.35.

Esercizio 3.38.
Si consideri una rete a sei nodi i cui LSP emessi, mostrati nella Figura 3.68, vengono ricevuti nel nodo B nell’ordine dai nodi E, D, A, F, C. Si vuole ricavare l’albero dei cammini minimi del nodo B.

Figura 3.68 Link state packet emessi dai 6 nodi di rete (Esercizio 3.38).

A partire dai link state packet forniti che vengono via via ricevuti, il nodo B determina l’albero dei cammini minimi, come mostrato in Figura E3.6. La conoscenza iniziale della rete da parte del nodo B è determinata dai suoi vicini (Figura E3.6a). Il LSP ricevuto dal nodo E completa la conoscenza in B dei nodi della rete, aggiornandone la topologia corrente (Figura E3.6b). La ricezione del LSP dai nodi D e A completa la conoscenza della topologia della rete (Figura E3.6c e Figura E3.6d). I successivi LSP ricevuti dai nodi F e C non aggiungono altra informazione. L’applicazione dell’algoritmo di Dijkstra alla topologia appena ricavata è mostrata nella Tabella E3.2 in cui a parità di distanza dall’albero corrente M dei nodi A, F al passo 0 e dei nodi C, E al passo 2, sono stati selezionati per primi i nodi F e C, rispettivamente. Da questa tabella, utilizzando l’informazione sul nodo predecessore di ogni nodo di rete, si ricava l’albero dei cammini minimi (SPT) del nodo B riportato in Figura E3.7.

Figura E3.6 Topologia di rete nel nodo B in base ai LSP ricevuti secondo l’Esercizio 3.38.

Tabella E3.2 Applicazione dell’algoritmo di Dijkstra per il nodo B secondo l’Esercizio 3.38.

Figura E3.7 SPT del nodo B secondo l’Esercizio 3.38.

Esercizio 3.39.
Per la topologia di rete ricavata nell’Esercizio 3.38 si chiede di applicare l’algoritmo di Dijkstra ricavando la tabella di instradamento del nodo B.

La successione dei passi dell’algoritmo di Dijkstra è mostrata in Figura E3.8. Si osserva che l’applicazione dell’algoritmo fa sì che il nodo B determini instradamenti migliori man mano che l’albero corrente aggrega nuovi nodi. In particolare, l’algoritmo determina il miglior instradamento verso il nodo D solo all’ultimo passo quando anche il nodo E viene incluso nell’insieme M.

Figura E3.8 Tabella di instradamento del nodo B costruita con l’algoritmo di Dijkstra secondo l’Esercizio 3.39.

Esercizio 3.41.
Si consideri una rete a 9 nodi (A, B, C, D, E, F, G, H, I) e 17 rami i cui costi sono:
costo | rami
1 | F-G, F-I, G-H
2 | A-B, B-D
3 | B-C, C-D, E-F
4 | A-H, D-E, E-I
5 | D-I
6 | A-G, H-I
7 | D-H, G-I
8 | B-H
Si chiede di applicare l’algoritmo di Dijkstra ricavando l’albero dei cammini minimi per il nodo H.

La Figura E3.9a mostra la rete assegnata. L’applicazione dell’algoritmo di Dijkstra determina l’albero mostrato con tratto spesso in Figura E3.9b, dove si mostra accanto a ogni nodo raggiunto dall’albero il costo dalla radice (nodo H).

Figura E3.9 Rete a nove nodi secondo l’Esercizio 3.41.

D – Controllo di flusso e di congestione

Esercizio 3.43.
Si consideri una rete a 6 nodi, etichettati A, B, C, D, E, F, e 8 rami di lunghezza 20 km per A-B, 12 km per B-C, 10 km per C-D, 40 km per D-E, 10 km per E-F, 5 km per F-A, 35 km per A-C, 40 km per B-F. Tutti i collegamenti sono in fibra ottica e hanno capacità . I nodi della rete si comportano come commutatori di tipo store and forward ideali: ogni ritardo di elaborazione e accodamento è trascurabile, e un pacchetto in transito viene ritrasmesso solo dopo averlo interamente ricevuto. Sulla rete agisce un meccanismo di controllo di flusso di tipo isaritmico, che opera tra i nodi di accesso. L’ingresso in rete di un pacchetto “consuma” un permesso nel nodo di ingresso. L’uscita dalla rete di un pacchetto genera nel nodo di uscita un nuovo permesso che viene ritrasmesso a ritroso al nodo di ingresso lungo lo stesso percorso utilizzato dal pacchetto. In assenza di permessi, il nodo di ingresso mantiene i pacchetti ricevuti dalla sorgente in un buffer in attesa di avere a disposizione nuovi permessi. Si assume che:
• i pacchetti che vengono immessi in rete sono tutti di uguale lunghezza () e hanno payload di , cui viene aggiunto un overhead ;
• i permessi vengono trasportati da pacchetti di controllo che hanno lunghezza La con .
Sono attivi due circuiti virtuali, il primo dal nodo C al nodo B e il secondo dal nodo C al nodo A che vengono instradati lungo la via più corta. Si consideri il caso in cui C riceva dalle sorgenti dei due circuiti virtuali la seguente sequenza contigua di pacchetti informativi: due per B, tre per A, tre per B. Al tempo t = 0 il nodo C ha ricevuto interamente dalle sorgenti tutti i pacchetti che devono essere trasmessi; inoltre al tempo t = 0 in C sono presenti N = 4 permessi. Si chiede di determinare il tempo complessivo di trasferimento dei pacchetti dal nodo C alle rispettive destinazioni.

La topologia di rete assegnata è rappresentata in Figura E3.13. Occorre preliminarmente calcolare i tempi di trasferimento delle unità informative, e cioè i pacchetti informativi e i pacchetti di controllo. Date le distanze tra nodi, un instradamento a minima distanza fa sì che i pacchetti da C a B seguano il collegamento diretto, mentre quelli da C ad A vengano instradati attraverso il nodo B. Considerando la capacità dei collegamenti e la loro tipologia si ricavano facilmente i tempi di trasmissione e dei pacchetti informativi e di controllo, nonché i tempi di propagazione .

Figura E3.13 Topologia di rete secondo l’Esercizio 3.43.

   

   

   

   

La Figura E3.14 mostra la successione degli eventi di trasmissione e propagazione per il trasferimento dei pacchetti informativi e di controllo. Si osservi come, nonostante il numero N = 4 di permessi inizialmente disponibili, il nodo C possa effettuare sei trasmissioni consecutive, dato che prima che i permessi siano esauriti, due permessi vengono ricevuti. Ciò implica che ognuno dei due successivi pacchetti, indirizzati al nodo B, possa essere trasmesso solo al ricevimento di un permesso, rendendo quindi discontinua la trasmissione dal nodo C. Attraverso la Figura E3.14 si può ricavare la successione degli intervalli temporali che non sono sovrapposti. Il tempo totale di trasferimento dei pacchetti è quindi dato da

   

Figura E3.14 Controllo di flusso con tecnica isaritmica secondo l’Esercizio 3.43.

Esercizio 3.45.
Si consideri una sorgente VBR periodica, la cui attività per un periodo di 3 s sia così caratterizzata:
• frequenza di picco della sorgente, ,
• periodi di attività e inattività a durata costante, e , con inizio attività al tempo ,
• UI emesse dalla sorgente a lunghezza fissa, .
Si chiede di ricavare l’andamento del flusso in uscita da un leaky bucket e da un token bucket in modalità store and forward (S&F) con le seguenti caratteristiche:
• frequenza in uscita dal bucket, ,
• frequenza di arrivo dei permessi,,
• istante di primo arrivo del permesso, ,
• capacità del cestino nel leaky bucket, W = 10 UI,
• capacità del cestino nel token bucket, W = 10 permessi.

Il profilo di traffico emesso dalla sorgente è riportato nella Figura E3.15. La capacità massima di accesso alla rete è e la consistenza di ogni pacchetto determina il tempo di trasmissione in uscita dal bucket . L’andamento della trasmissione dei pacchetti in uscita dal leaky bucket e dal token bucket è riportato in Figura E3.16, osservando che non si ha mai saturazione del cestino delle UI e di quello dei permessi.

Figura E3.15 Attività di una sorgente VBR secondo l’Esercizio 3.45.

Figura E3.16 Frequenza in uscita dal leaky bucket (a) e dal token bucket (b) secondo l’Esercizio 3.45.

Esercizio 3.50.
Si consideri una sorgente non periodica, la cui frequenza (costante) di emissione delle UI PS è così caratterizzata: per , per , per , per , frequenza linearmente decrescente da a per . La sorgente alimenta un dispositivo di controllo di flusso di tipo leaky bucket con tempo di interarrivo dei permessi a patire da t = 0 e dimensione della memoria (buffer) delle unità informative W = 300 UI. Si chiede di ricavare il diagramma temporale che rappresenta la frequenza in uscita dal dispositivo, il livello di riempimento della memoria , nonché il numero delle UI perse, assumendo che il dispositivo non aggiunga overhead.

Il diagramma temporale dell frequenza di ingresso al leaky bucket è rappresentato in Figura E3.17. Il tempo di interarrivo dei permessi determina una frequenza (massima) in uscita = 100 UI/s. Quindi le UI ricevute in eccesso nell’intervallo 2-4 s entrano nel buffer che quindi satura, con la conseguenza che le UI ricevute nell’intervallo 4-5 s in eccesso rispetto a vengono perse, e cioè = 200 UI. Per il primo periodo di attività della sorgente quindi il flusso in uscita dura 2 s oltre la fine di attività della sorgente in quanto si svuota il buffer. Nel secondo periodo di attività della sorgente si ricevono in eccesso 100 UI rispetto alla frequenza nell’intervallo 10-12 s. Queste entrano nel buffer e vengono trasmesse quando la frequenza di ingresso scende al di sotto della frequenza . Il livello di riempimento del buffer in questo caso si determina come l’area sottesa tra la curva che specifica la frequenza di ingresso e il livello = 100. Le due curve sono mostrate in Figura E3.18.

Figura E3.17 Frequenza di emissione di UI dalla sorgente secondo l’l’Esercizio 3.50.

Figura E3.18 Frequenza in uscita dal leaky bucket (a) e riempimento del buffer (b) secondo l’Esercizio 3.50.