Eserciziario di Reti di Calcolatori

Capitolo 3

Esercizio # 3.1

Testo:
Usando la rete di esempio fornita nella figura sottostante, individuate le tabelle dei circuiti virtuali per tutti i commutatori dopo che ciascuna delle seguenti connessioni a stata instaurata. Ipotizzate che la sequenza di connessioni sia cumulativa, cioè la prima connessione e ancora attiva quando si instaura la seconda, e così. via. Ipotizzate anche che l'assegnamento del valore di VCI scelga sempre il valore minimo tra quelli inutilizzati su ciascuna linea, iniziando dal valore 0.

a)L'host A si connette all'host B.
b)L'host C si connette all'host G.
c)L'host E si connette all'host I.
d)L'host D si connette all'host B.
e)L'host F si connette all'host J.
f)L'host H si connette all'host A.

Soluzione:

		Input		Output
Domanda	Switch	Porta	VCI	Porta	Vci
a) A-->B	1	2		1	0
	2	3	0	0	0
	3	0	0	3	0
b) C-->G	1	3	0	1	1
	2	3	1	1	0
	4	3	0	1	0
c) E-->I	2	2	0	0	1
	3	0	1	2	0
d) D-->B	1	0	0	1	0
	2	3	0	0	0
	3	0	0	3	0

Da sottolineare che dopo il passaggio per lo Switch 2,
la connessione d) utilizza lo stesso canale instaurato per la connessione a)

		Input		Output
Domanda	Switch	Porta	VCI	Porta	Vci
e) F-->J	4	2	0	3	0
	2	1	0	0	2
	3	0	2	1	0
f) H-->A	4	0	0	3	1
	2	1	1	3	0
	1	1	0	2	0

ˆtop

Esercizio # 3.3

Testo:
Per la rete della Figura sottostante, fornite per ciascun nodo la tabella di inoltro datagram. Le linee sono etichettate con it relativo costo: le tabelle devono inoltrare ciascun pacchetto verso la sua destinazione usando it percorso di costo minimo.

Soluzione:
Usando l'algoritmo di Kruskal per l'albero di costo minimo, si ottiene il seguente grafo:

Seguono, quindi, le tabelle di inoltro:

A		B		C		D		E		F
Dest	Port	Dest	Port	Dest	Port	Dest	Port	Dest	Port	Dest	Port
B	1	A	1	A	3	A	2	A	3	A	1
C	1	C	1	B	2	B	2	B	2	B	1
D	1	D	1	D	2	C	2	C	3	C	1
E	1	E	1	E	2	E	2	D	1	D	1
F	1	F	1	F	1	F	2	F	3	E	1

ˆtop

Esercizio # 3.4

Testo:
Scrivete le tabelle di inoltro per gli switch S1, S2, S3 e S4 della Figura 3.35. Ciascuno switch deve avere un' instradamento di "default", scelto per inoltrare verso OUT i pacchetti con indirizzo di destinazione non riconosciuto. Devono, quindi, essere eliminate dalla tabella eventuali informazioni che duplichino quella di default.

Soluzione:
L'esercizio può essere risolto in 2 fasi. nella prima fase OUT verrà trattato come un qualsiasi altro nodo.
Tabelle di inoltro:

Switch S1		Switch S2		Switch S3		Switch S4
A	1	A	1	A	1	A	1
B	2	B	1	B	1	B	1
C	3	C	3	C	2	C	1
D	3	D	3	D	3	D	2
OUT	3	OUT	2	OUT	1	OUT	1

Nella seconda fase si eliminano dalle tabelle le righe che hanno la stessa porta di uscita di OUT. OUT assume il significato di "tutte le altre destinazioni".
Le tabelle risultanti saranno:

Switch S1		Switch S2		Switch S3		Switch S4
A	1	A	1	C	2	D	2
B	2	B	1	D	3	OUT	1
OUT	3	C	3	OUT	1
		D	3
		OUT	2

Nota: la tabella di S2 rimane invariata, come si poteva prevedere.

ˆtop

Esercizio # 3.5

Testo:
Considerate gli switch a circuito virtuale della figura sottostante.
La tabella sottostante elenca, per ciascuno switch, quali coppie (porta, VCI) (oppure (VCI, interfaccia)) sono connesse a quali altre. Le connessioni sono bidirezionali. Fate un elenco di tutte le connessioni da un estremo all'altro.

Soluzione:

Switch S1				Switch S2				Switch S3
Porta VCI		Porta VCI		Porta VCI		Porta VCI		Porta VCI		Porta VCI
1	2	3	1	1	1	3	3	1	3	2	1
1	1	2	3	1	2	3	2	1	2	3	1
2	1	3	2

Soluzione:

		Input		Output
Collegamento	Switch	Porta	VCI	Porta	VCI
A - B	1	1	1	2	3
A - C	1	1	2	3	1
	2	1	NO	2	NO
A - D	1	1	2	3	1
	2	1	1	3	3
	3	1	3	2	1
B - C	1	2	1	3	2
	2	1	NO	2	NO
B - D	1	2	1	3	2
	2	1	2	3	2
	3	1	NO	2	1
B - E	1	2	1	3	2
	2	1	2	3	2
	3	1	2	3	1
C - D	2	2	NO	3	NO
	3	1	3	2	1
C- E	2	2	NO	3	NO
	3	1	2	3	1
D - E	3	2	NO	3	NO

I collegamenti bidirezionali possibili, quindi, sono:

A - B, A - D, B - D, B - E.

ˆtop

Esercizio # 3.7

Testo:
Proponete un meccanismo che possa essere usato dagli switch a circuito virtuale in modo che, se uno switch perde la propria memorizzazione dello stato di tutte le connessioni, una sorgente che invia pacchetti lungo un percorso che attraversa tale switch venga informata del guasto.

Soluzione:
Lo switch che ha perso la propria memorizzazione dello stato dei VC potrebbe inviare un messaggio di errore ogni volta che riceve un pacchetto dati.
Il messaggio di errore dovrà contenere un codice che identifica l’errore stesso (che potremmo chiamare “VCI error”) e il numero di VCI contenuto nell’header del pacchetto dati ricevuto (e un identificativo del pacchetto stesso, nel caso vengano utilizzate strategie di invio dei pacchetti che permettano di rimanere “fuori” con più pacchetti, come con sliding windows). Questo messaggio d’errore dovrà essere inoltrato a monte attraverso la porta da cui è stato ricevuto il pacchetto dati. L’idea è quella di far percorrere al messaggio di errore il percorso inverso del pacchetto dati, fino a giungere all’host sender, con un meccanismo simile a quello eseguito durante l’invio dei dati, ma nel verso opposto. Uno switch che riceve il messaggio di errore consulta la propria tabella dei VC e identifica la riga corrispondente alla connessione: essa avrà il valore “VCI out” pari al valore di VCI contenuto nel messaggio d’errore e il numero di “porta in uscita” pari al numero di porta da cui ha ricevuto il messaggio. Lo switch a questo punto sostituisce il valore di VCI nel messaggio d’errore con il valore di “VCI in” contenuto nella riga identificata e lo inoltra alla relativa porta in ingresso. Questo meccanismo verrà iterato finché il messaggio di errore non giungerà all’host sender, che agirà di conseguenza. Ad esempio potrebbe decidere di instaurare una nuova connessione. In questo caso è opportuno che gli switch eliminino la riga relativa alla connessione subito dopo aver inoltrato il messaggio di errore, in quanto quella connessione non sarà più usata.
Esempio: si faccia riferimento alla figura sottostante, in cui l’host A invia un pacchetto all’host B.

Le tabelle dei VC sono rappresentate dalla tabella sottostante:

interfaccia d'ingresso	VCI d'ingresso	Interfaccia d'uscita	VCI d'uscita
Switch 1:
2	5	1	11
Switch 2:
3	11	2	7
Switch 3:
0	7	1	4

Supponiamo che lo switch 3 abbia perso la propria memorizzazione dello stato dei VC. S3 riceve un pacchetto dati con valore di VC pari a 7 dalla porta 0. Lo switch genera un messaggio di errore e lo inoltra con valore di VC pari a 7. S2 riceve il messaggio di errore, consulta la tabella dei VC e trova la seguente riga:

Porta d'ingresso	VCI in	Porta di uscita	VCI out
3	11	2	7

Sostituisce il numero di VC con 11 e inoltra il messaggio di errore alla porta 3. Il messaggio di errore arriva a S1 che identifica la seguente riga:

Porta d'ingresso	VCI in	Porta di uscita	VCI out
2	5	1	11

A questo punto S1 inoltra il messaggio di errore all’host A, con valore di VC pari a 5.

ˆtop

Esercizio # 3.8

Testo:
Proponete un meccanismo che possa essere usato dagli switch datagram in modo che, se uno switch perde interamente o in parte la propria tabella di inoltro, le sorgenti coinvolte vengano informate del guasto.

Soluzione:
Se uno switch datagram perde interamente o in parte la propria tabella di inoltro, non è più in grado di inoltrare correttamente tutti o alcuni pacchetti.
Un possibile meccanismo per informare gli altri switch della rete, potrebbe essere l'invio a tutte le destinazioni di un pacchetto speciale che fa aggiornare ogni tabella di inoltro, rimuovendo tutte le destinazioni che coinvolgono lo switch guasto. Questo malfunzionamento potrebbe, infine, non comportare ulteriori problemi sulle comunicazioni di rete, se è possibile trovare un percorso alternativo che aggiri il guasto.

ˆtop

Esercizio # 3.10

Testo:
Supponete che nella Figura sottostante venga aggiunta una nuova linea di collegamento che connetta la porta 1 dello switch 3 (dove ora si trova G) e la porta 0 dello switch 1 (dove ora si trova D); nessuno switch è “a conoscenza” di tale linea. Inoltre, lo switch 3 pensa, erroneamente, che l’host B sia raggiungibile tramite la porta 1.

a)Cosa accade se l’host A tenta di inviare dati all’host B, usando l'inoltro di datagrammi?
b)Cosa accade se l’host A tenta di inviare dati all’host B, usando il meccanismo di instaurazione di circuiti virtuali discusso nel testo?

Soluzione:
a)
S1 non è a conoscenza della nuova linea di collegamento. Di conseguenza inoltrerà i pacchetti destinati a B per la porta 1.
A spedisce un pacchetto a B. il pacchetto da A passa a S1 che lo inoltra per la porta 1. da qui arriva a S2 che lo inoltra per la porta 0. Il pacchetto arriva a S3. S3 erroneamente inoltra il pacchetto per la porta 1. il pacchetto torna quindi a S1. S1 inoltrerà il pacchetto nuovamente per la porta 1 e così via: il pacchetto continuerà a girare per la rete senza arrivare mai a destinazione.
b)
Non sarà possibile instaurare il circuito virtuale tra A e B , in quanto la richiesta non arriverà mai a B e quindi nessun nodo potrà mandare la conferma dell’instaurazione della connessione e completare la propria tabella dei VC. Anzi, ogni volta che la richiesta compie un giro, gli switch crederanno di essere di fronte a una nuova richiesta di connessione, e attribuiranno ad essa un nuovo VCI. Questo accadrà finché uno switch non avrà finito i valori di VCI disponibili, rifiutando la connessione.

ˆtop

Esercizio # 3.11

Testo:
Fornite un esempio di un circuito virtuale funzionante il cui percorso attraversa alcune linee due volte. Nonostante ciò, i pacchetti inviati lungo tale percorso non devono viaggiare indefinitamente.

Soluzione:

Consideriamo di voler trasmettere da A a B secondo la figura sovrastante.
Il percorso più naturale è

A –> S1 –> S2 –> S3 –> B

e, di conseguenza, instuariamo questo circuito virtuale. Supponiamo che, quando un certo pacchetto pn viene inviato da S2 verso S3, il collegamento tra S3 e B si interrompa per una causa esterna. Ne consegue l'aggiornamento dello stato della connessione in S3: poichè è possibile raggiungere B attraverso un percorso alternativo, viene instaurato un nuovo circuito virtuale

S3 –> S4 –> S1 –> S2 –> S5 –> S6 –> B

La linea che collega S1 e S2, viene, quindi, attraversata due volte da tutti i pacchetti inviati dopo pn-1, perchè il circuito virtuale risultante è

A –> S1 –> S2 –> S3 –> S4 –> S1 –> S2 –> S5 –> S6 –> B

I metodi di scelta di un canale alternativo verranno esaminati con maggiore dettaglio successivamente nei capitoli 5 e 6.

ˆtop

Esercizio # 3.2

Testo:
Usando la rete di esempio fornita in figura, individuate le tabelle dei circuiti virtuali per tutti i commutatori dopo che ciascuna delle seguenti connessioni a stata instaurata. Ipotizzate che la sequenza di connessioni sia cumulativa, cioe la prima connessione a ancora attiva quando si instaura la seconda, e cosi via. Ipotizzate anche che l'assegnamento del valore di VCI scelga sempre it valore minimo tra quelli inutilizzati su ciascuna linea, iniziando dal valore 0.

a)L'host D si connette all'host H.
b)L'host B si connette all'host G.
c)L'host F si connette all'host A.
d)L'host H si connette all'host C.
e)L'host I si connette all'host E.
f)L'host H si connette all'host J.

Soluzione:

		Input		Output
Domanda	Switch	Porta	VCI	Porta	Vci
a) D-->H	1	0	0	1	0
	2	3	0	1	0
	4	3	0	0	0
b) B-->G	3	3	0	0	0
	2	0	0	1	1
	4	3	1	1	0
c) F-->A	4	2	0	3	0
	2	1	0	3	0
	1	1	0	2	0
d) H-->C	4	0	0	3	1
	2	1	1	3	1
	1	1	1	3	0
e) I-->E	3	2	0	0	1
	2	0	1	2	0
f) H-->J	4	2	1	3	2
	2	1	2	0	0
	3	0	0	1	0

ˆtop

Esercizio # 3.6

Testo:
Nell’esempio di Source Routing della Sezione 3.1.3 l’indirizzo ricevuto da B non è reversibile e non aiuta B a sapere come raggiungere A: proponete una modifica al meccanismo di consegna che consenta la reversibilità. Il meccanismo non deve richiedere l’assegnazione di un nome globalmente univoco a tutti gli switch.

Soluzione:
Una possibile soluzione è raddoppiare l’informazione dell’indirizzo, trasmettendo nell’intestazione del pacchetto inviato anche la porta d’entrata ad ogni switch. Nella trasmissione da A a B, anche l’informazione sulle porte d’entrata ruoterà assieme all’informazione sulle porte d’uscita. Alla fine l’host B riceverà la sequenza delle porte nello stesso ordine in cui le avrà inviate A. A questo punto, basterà che B inverta l’informazione sulle porte d’uscita e rifaccia tutto il procedimento.
Esempio:
La seguente figura mostra la non reversibilità:

Se pensiamo di trasferire anche i dati sulle porte d’entrata, avremo il seguente caso:

Dopo lo switch 3, l’host B riceve la stessa sequenza partita da A, quindi otterrà l’informazione seguente:

Dopo lo switch 3, l’host B riceve la stessa sequenza partita da A, quindi otterrà l’informazione seguente:

ˆtop

Esercizio # 3.9

Testo:
Il meccanismo di circuito virtuale descritto nella Sezione 3.1.2 ipotizza che tutte le linee di collegamento siano punto-punto. Estendete l'algoritmo di inoltro in modo che funzioni anche nel caso in cui le linee siano connessioni a mezzo fisico condiviso, ad esempio, Ethernet.

Soluzione:
Nel caso le connessioni siano linee a mezzo fisico condiviso (es. Ethernet), il problema che possiamo incontrare sta appunto in queste parti della rete e non nel collegamento tra gli switch.
Una possibile estensione consiste nel creare, per ogni switch, una tabella che colleghi le porte con gli host delle reti raggiungibili. Cosi' facendo, posso creare un canale dedicato per ogni host.

ˆtop

Esercizio # 3.12

Testo:
Nella Sezione 3.1.2 ciascuno switch sceglieva il valore di VCI per la linea d'ingresso. Dimostrate che e' anche possibile che ciascuno switch scelga il valore di VCI per la linea d'uscita, e che entrambi gli approcci scelgano i medesimi valori di VCI. Se ciascuno switch sceglie il valore di VCI uscente, e' ancora necessario attendere un tempo uguale a RTT prima di inviare i dati?

Soluzione:
E' possibile che lo switch scelga il VCI per la linea di uscita, a seconda dell'host sorgente e dell'host destinazione: cosi' facendo, se un host A vuole trasmettere ad un host B, verra' scelto il primo VCI libero del primo switch; nel caso l'host A voglia trasmettere ad un host C, lo switch scegliera' un diverso VCI.
In questo modo, si dovrebbero ottenere i medesimi valori di VCI.
Scegliendo fin dall'inizio i valori di VCI di uscita, si puo' inviare da subito i dati, perche' non occorre aspettare un RTT di attesa dell'informazione dall'host Receiver.

ˆtop

Esercizio # 3.13

Testo:
Nel caso della rete locale estesa di figura, indicate quali porte non vengono selezionate dall'algoritmo a spanning tree.

Soluzione:
Le porte non selezionate sono state indicate in figura:

In particolare il bridge B5 viene completamente escluso.

ˆtop

Esercizio # 3.15

Testo:
Considerate la disposizione di bridge ad apprendimento mostrata nella figura sottostante. Ipotizzando che inizialmente siano tutte vuote, identificate le tabelle di inoltro per i bridge B1, B2, B3 e B4 dopo le trasmissioni seguenti:
- A invia a C
- C invia ad A
- D invia a C
Identificate le porte usando come etichetta il nome dell'unico vicino raggiungibile direttamente dalla porta stessa; ad esempio, le porte di B l devono essere etichettate con "A" e "B2"

Soluzione:
A –> C
Poiché inizialmente le tabelle di inoltro sono vuote tutti i bridge vedono i pacchetti. Ne consegue il seguente aggiornamento delle tabelle di inoltro:

host	porta su B1	porta su B2	porta su B3	porta su B4
A	"A"	"B1"	"B2"	"B2"

C –> A
La destinazione A è presente in tutte le tabelle di inoltro dei Bridge, di conseguenza solo B3, B2, B1 vedono i pacchetti. Ne consegue il seguente aggiornamento delle tabelle di inoltro:

host	porta su B1	porta su B2	porta su B3	porta su B4
A	"A"	"B1"	"B2"	"B2"
C	"B2"	"B3"	"C"	NON PRESENTE

D –> C
La destinazione C è presente nelle tabelle di inoltro dei Bridge, di conseguenza solo B4, B2, B3 vedono i pacchetti. Ne consegue il seguente aggiornamento delle tabelle di inoltro:

host	porta su B1	porta su B2	porta su B3	porta su B4
A	"A"	"B1"	"B2"	"B2"
C	"B2"	"B3"	"C"	NON PRESENTE
D	NON PRESENTE	"B4"	"B2"	"D"

ˆtop

Esercizio # 3.18

Testo:
Tracciate lo spanning tree generato per la rete locale estesa mostrata in Figura e descrivete come vengono risolte le situazioni di pareggio.

Soluzione:
Per semplicità, chiamiamo le quattro reti A, B, C, D, partendo da quella in alto e proseguendo in senso orario. Lo spanning tree generato per la rete locale estesa avrà B1 come radice. Tutte le sue porte saranno pertanto attive. Inoltre B1 sarà il bridge designato per le reti A e C. B2 sarà il bridge designato per la rete D e B3 lo sarà per la rete B. Pertanto le porte da B2 a D e da B3 a B saranno attive. Infine è indifferente con quale delle due porte rimanenti i bridge B2 e B3 si collegheranno al resto della rete. L’importante è che non siano entrambe attive, per evitare che si formino cicli.ˆtop

Esercizio # 3.19

Testo:
Supponete che due bridge ad apprendimento, B1e B2, formino un anello come mostrato nella figura sottostante e che non implementino l'algoritmo a spanning tree. Ciascun bridge gestisce una tabella di coppie (indirizzo, interfaccia).
a)Cosa accade se M invia un pacchetto a L?
b)Supponete che dopo poco L risponda a M. Identificate la sequenza di eventi che porta alla situazione in cui un pacchetto proveniente da M e un pacchetto proveniente da L circolano nell'anello in direzioni opposte.

Soluzione:
a) M –> L
Se supponiamo che entrambe le tabelle di inoltro siano vuote i pacchetti che arrivano a ciascun bridge vengono inoltrati in tutte le direzioni. Di conseguenza, finché i bridge non riceveranno una comunicazione a M (e aggiorneranno la tabelle di inoltro), i pacchetti continueranno a circolare (sia sopra che sotto) nel loop B1 –> B2 –> B1...
Però, una volta aggiornata la tabella, comunque i pacchetti continueranno a rimbalzare da B1 e B2, poiché tutti i pacchetti che inoltrati verso L, vengono visti dall'altro bridge che a sua volta lo inoltra nuovamente.

host	porta su B1	porta su B2
M	"M"	"M"

Invece, se supponiamo che prima che inizi la trasmissione, L sia presente nelle tabelle di inoltro, i pacchetti che arrivano a ciascun bridge vengono inoltrati sulla linea verso L (sopra). Di conseguenza a L arriverà due volte lo stesso pacchetto.

host	porta su B1	porta su B2
M	"M"	"M"
L	"L"	"L"

b) M –> L –> M
Affinché questo possa avvenire, dobbiamo supporre che la tabella di inoltro di un bridge sia aggiornata e quella dell'altro vuota. Per semplicità, consideriamo che la tabella su B1 sia aggiornata e quella di B2 sia vuota.
La sequenza che crea la situazione richiesta è la seguente:
M invia un pacchetto, B1 e B2 ricevono il pacchetto, B1 lo inoltra “solo sopra” (perché conosce L) mentre B2 lo inoltra “sia sopra che sotto” (perché non conosce L) . Ora abbiamo un pacchetto che viaggia da B2 a B1 sulla linea “sotto”...
Uno dei due pacchetti partiti dai bridge arriva ad L che risponde in entrambe le direzioni. Nel frattempo il che viaggiava da B2 a B1, arriva a destinazione e viene inoltrato “solo sopra”.
Questa è la situazione richiesta, abbiamo un pacchetto che viaggia da L verso B1 e uno che viaggia in direzione opposta (da B1 verso L).

ˆtop

Esercizio # 3.21

Testo:
Considerate la LAN estesa di figura sottostante. Cosa accade nell'algoritmo a spanning tree se it bridge B1 non partecipa e:
a) inoltra semplicemente tutti i messaggi relativi all'algoritmo a spanning tree?
b) ignora ed elimina tutti i messaggi relativi all'algoritmo a spanning tree?

Soluzione:
a) si formerà uno spanning tree con B2 come radice. B1 parteciperà allo spanning tree e sarà il bridge designato per le reti D, F, G, H.
b) si formeranno due reti estese che non possono comunicare tra loro. La prima sarà formata dalle reti A, B, C, D, E, F, K e dai bridge B2 (che sarà la radice dello spanning tree ), B3, B5, B7. La seconda sarà formata dalle reti G, H, I, J e dai bridge B4 (che sarà la radice dello spanning tree ) e B6. E’ come se B1 non esistesse affatto.

ˆtop

Esercizio # 3.22

Testo:
Supponete di connettere ad anello alcuni ripetitori (hub), anzichè bridge.
a)Cosa succede quando qualcuno trasmette?
b)Perchè sarebbe difficile o impossibile implementare il meccanismo a spanning tree per i ripetitori?
c)Proponete un meccanismo mediante it quale i ripetitori possano individuare gli anelli e chiudere alcune porte per interromperli. Non e richiesto che la vostra soluzione sia funzionante per it l00% del tempo.

Soluzione:
a) Quando un host trasmette ciascun ripetitore inoltra ad ogni sua porta il messaggio ricevuto.
b) È difficile implementare il meccanismo a spanning tree per i ripetitori perchè i messaggi vengono inoltrati in tutte le direzioni e rimbalzano da un ripetitore all'altro
c) Vedi topic sul forum

ˆtop

Esercizio # 3.34

Testo:
Supponete che uno switch sia in grado di inoltrare pacchetti al ritmo di 100000 al secondo, indipendentemente dalla loro dimensione (entro limiti determinati). Usando una workstation con i parametri descritti nell'esercizio precedente, per quale dimensione dei pacchetti l'ampiezza di banda del bus diventa il fattore limitante?

Soluzione:
Il collo di bottiglia è la velocità del bus di I/O, dato che è inferiore all’ampiezza di banda della memoria. L’ampiezza di banda che il bus di I/O è effettivamente in grado di fornire è

1000/2 = 500 Mbps

perché ogni pacchetto attraversa il bus due volte. Pertanto l’ampiezza di banda diventa il fattore limitante per dimensioni di pacchetto superiori a

500Mbps / 100000pps = 5000 bit.

ˆtop

Esercizio # 3.35

Testo:
Supponete che uno switch sia progettato per usare code FIFO per la memorizzazione, sia in ingresso sia in uscita. Quando i pacchetti arrivano ad una porta d' ingresso vengono inseriti alla fine della coda FIFO, successivamente lo switch tenta di inoltrare verso la fine della coda FIFO dell'uscita appropriata i pacchetti che si trovano all'inizio di ciascuna coda FIFO.
a)Spiegate quali sono le circostanze in cui tale switch può perdere un pacchetto destinato ad una porta d'uscita la cui coda FIFO è vuota.
b)Come viene chiamato questo comportamento?
c)Nell'ipotesi che la memoria destinata alle code FIFO possa essere redistribuita liberamente, suggerite un metodo per rimescolare i buffer che elimini il problema precedente, e spiegate come vi riesce.

Soluzione:
a) Uno switch può perdere un pacchetto destinato ad una porta d'uscita la cui coda FIFO è vuota, se la coda della porta d'ingresso è piena.
b) Head-of-line blocking (blocco della posizione frontale)
c) Avendo a disposizione buffer di lunghezza variabile, è possibile accetare pacchetti fin quando c'è memoria disponibile. Di conseguenza il problema dell'head-of-line blocking viene risolto: se la coda della porta d'entrata è piena, viene estesa in modo da accettare ulteriori pacchetti. La memoria necessaria per questa operzione può essere presa, per esempio, dalla memoria asseguata alla coda più libera.

ˆtop

Esercizio 3 tema d'esame del 20/07/04

Testo:
Si consideri la rete nella figura sottostante.

Per ciascuno degli switch indicati, comporre le tabelle con i circuiti virtuali costruiti per supportare le seguenti connessioni, nell’ordine assegnato ed in modo cumulativo:
a)host F connesso a host A;
b)host E connesso a host H;
c)host B connesso a host C;
d)host G connesso a host D.
Si assuma che gli identificatori VCI assegnati siano scelti da ciascun switch a partire da 0 ed in modo incrementale.

Soluzione:
Di seguito la tabella generale:

		Input		Output
Domanda	Switch	Porta	VCI	Porta	Vci
a) F-->A	2	1	0	3	0
	1	1	0	2	0
b) E-->H	3	0	0	2	0
	2	2	0	0	0
c) B-->C	3	3	0	2	1
	2	2	1	3	1
	1	1	1	3	0
d) G-->D	3	1	0	2	2
	2	2	2	3	2
	1	1	2	0	0

Di seguito la tabella particolare per ogni switch:
Domanda a)
SWITCH 1

Input		Output
Porta	VCI	Porta	VCI
1	0	2	0

SWITCH 2

Input		Output
Porta	VCI	Porta	VCI
1	0	3	0

SWITCH 3

Input		Output
Porta	VCI	Porta	VCI

Domanda b)
SWITCH 1

Input		Output
Porta	VCI	Porta	VCI
1	0	2	0

SWITCH 2

Input		Output
Porta	VCI	Porta	VCI
1	0	3	0
2	0	0	0

SWITCH 3

Input		Output
Porta	VCI	Porta	VCI
0	0	2	0

Domanda c)
SWITCH 1

Input		Output
Porta	VCI	Porta	VCI
1	0	2	0
1	1	3	0

SWITCH 2

Input		Output
Porta	VCI	Porta	VCI
1	0	3	0
2	0	0	0
2	1	3	1

SWITCH 3

Input		Output
Porta	VCI	Porta	VCI
0	0	2	0
3	0	2	1

Domanda d)
SWITCH 1

Input		Output
Porta	VCI	Porta	VCI
1	0	2	0
1	1	3	0
1	2	0	0

SWITCH 2

Input		Output
Porta	VCI	Porta	VCI
1	0	3	0
2	0	0	0
2	1	3	1
2	2	3	2

SWITCH 3

Input		Output
Porta	VCI	Porta	VCI
0	0	2	0
3	0	2	1

ˆtop

Esercizio # 3.17

Testo:
Considerate gli host X, Y, Z e W e i bridge ad apprendimento B1, B2 e B3, con tabelle di inoltro inizialmente vuote, come nella seguente figura.

a)Supponete che X trasmetta un pacchetto verso Z. Quali bridge apprendono la posizione di X? L'interfaccia di rete di Y vede tale pacchetto?
b)Supponete ora che Z trasmetta un pacchetto verso X. Quali bridge apprendono la posizione di Z? L'interfaccia di rete di Y vede tale pacchetto?
c)Supponete ora che Y trasmetta un pacchetto verso X. Quali bridge apprendono la posizione di Y? L'interfaccia di rete di Z vede tale pacchetto?
d)Supponete ora che Z trasmetta un pacchetto verso Y. Quali bridge apprendono la posizione di Z? L'interfaccia di rete di W vede tale pacchetto?

Soluzione:
X ---> Z : In questa trasmissione, tutti gli host (compreso Y) ricevono il pacchetto. I seguenti bridge apprendono la posizione di X:
B1: <X, B1.X>
B2: <X, B2.B1>
B3: <X, B3.B2>
Z ---> X: Solo X riceve il pacchetto. Y non ha possibilità di vederlo. I seguenti bridge apprendono la posizione di Z:
B1: <Z, B1.B2>
B2: <Z, B2.B3>
B3: <Z, B3.Z>
Y ---> X: Solo X riceve il pacchetto. Z non vede il pacchetto. I seguenti bridge apprendono la posizione di Y:
B1: <Y, B1.B2>
B2: <Y, B2.Y>
Z ---> Y: B3 inoltra a tutte le reti perche' non ha informazione su Y. Quindi W puo' vedere il pacchetto. B2 pero' successivamente inoltra correttamente e X non vedrà nulla.
Non vengono modificate le tabelle di inoltro, perché le informazioni sono già presenti.

ˆtop

Esercizio # 3.20

Testo:
Supponete che, nella seguente figura, M invii un pacchetto a se stesso (cosa che normalmente non avviene mai). Dite che cosa accadrebbe, nell'ipotesi che:

a)l'algoritmo di apprendimento dei bridge inserisca (o aggiorni) le coppie di informazioni <indirizzo sorgente, interfaccia> prima di cercare l'indirizzo di destinazione della tabella;
b)l'indirizzo della nuova sorgente venga inserito dopo la ricerca dell'indirizzo di destinazione.

Soluzione:
Caso a)
M invia il pacchetto sia verso il bridge B1 che verso B2. In entrambi vengono modificate le tabelle riguardanti M nel seguente modo:
B1: <M, B1.M>
B2: <M, B2.M>
Successivamente, entrambi i bridge cercano nella propria tabella l'indirizzo di destinazione di M e percio' inoltrano sullo stesso canale da cui hanno ricevuto la trasmissione.
Caso b)
M invia il pacchetto sia verso il bridge B1 che verso B2, che lo inoltrano a tutti, avendo la propria tabella vuota. Nelle tabelle di B1 e B2 compariranno quindi le seguenti entry:
B1: <M, B1.M>
B2: <M, B2.M>
L'host L dunque potra' vedere i pacchetti inviati da entrambi i bridge.
Anche B1 vedra' il pacchetto inviato da B2 e B2 quello inviato da B1.
Entrambi i bridge inoltreranno correttamente verso M.

ˆtop

Esercizio # 3.23

Testo:
Supponete che un bridge abbia due porte sulla stessa rete. Come se ne puo' accorgere e come puo' rimediare?

Soluzione:
Se un bridge ha due porte su una stessa rete, per ogni messaggio che inviera' a tutti gli host di quella rete ne ricevera' uno uguale.
A questo punto puo' disabilitare una delle due porte oppure adibire una porta per il traffico in entrata e l'altra per il traffico in uscita su quella rete.

ˆtop

Esercizio # 3.32

Testo:
Supponete che una workstation abbia un bus di I/O a 800 Mbps ed una memoria con ampiezza di banda di 2 Gbps. Usando il DMA per le comunicazioni con la memoria in entrambe le direzioni, un commutatore costruito con questa workstation quante interfacce verso linee T3 a 45 Mbps sarebbe in grado di gestire?

Soluzione:
l collo di bottiglia e' la velocita' del bus di I/O. L'ampiezza di banda che il bus e' effettivamente in grado di fornire e' 800/2 Mbps, perche' ogni pacchetto attraversa il bus 2 volte. Quindi il numero di interfacce e'

ˆtop

© 2005 Studenti del corso di Reti di Calcolatori tenuto dal professor Satta