Computer Engineering - Fondamenti di Internet e Reti

Esercizi instradamento

Divided by topic

Fondamenti di Internet e Reti 097246 Esercizi 1 4c. Esercizi sul livello di Rete – Instradamento in Internet 4c-1 Esercizio Si consideri la rete in figura. Si rappresenti, mediante un grafo, la rete per il calcolo dei cammini minimi (solo i nodi e gli archi – no reti). Si calcoli il cammino minimo tra R1 e tutti gli altri nodi mediante l’algoritmo di Dijkstra supponendo che ciascun arco abbia peso unitario. Si ripeta il calcolo assegnando a ciascun arco un peso pari a 100/C dove C è la velocità del link in Mb/s. Soluzione 1-Il grafo che rappresenta la rete sopra è il seguente, rappresentando, come richiesto nel testo, solo router e collegamenti. La tabella seguente mostra l’evoluzione dell’algoritmo di Dijkstra. Lo Step 0 si riferisce all’inizializzazione. Ad ogni passo (step) sono indicate le etichette rese permanenti (in rosso) ed i router che non vengono considerati al passo specifico (#); si ricorda che ad ogni passo, possono essere modificate le etichette dei soli nodi che sono vicini di nodi già parte dell’albero dei cammini minimi (nodi con etichetta rossa al passo precedente). R1 R2 R3 R4 R5 R6 R7 Step 0 (-,0) (-,inf) (-,inf) (-,inf) (-,inf) (-,inf) (-,inf) Step 1 (1,R1) # # (1,R1) # # Step 2 (2,R2) # (1,R1) (2,R2) # Step 3 (2,R2) # (2,R2) (2,R5) Step 4 (2,R2) (3,R7) (2,R2) Step 5 (2,R2) (3,R7) Step 6 (3,R7) L’albero dei cammini minimi sarà il seguente: R2131.175.15.0/24 –10 Mb/sR1R3R4R5R6R7131.175.21.0/24 –100 Mb/s131.175.70.0/24 –100 Mb/s131.175.158.0/24 –10 Mb/s131.175.130.0/24100 Mb/sR1R2R3R4R5R7R6 Fondamenti di Internet e Reti 097246 Esercizi 2 2-Applicando l’algoritmo di Dijkstra con la nuova metrica 100/C, si ottiene il seguente albero dei cammini minimi: R1 R2 R3 R4 R5 R6 R7 Step 0 (-,0) (-,inf) (-,inf) (-,inf) (-,inf) (-,inf) (-,inf) Step 1 (20,R1) # # (100,R1) # # Step 2 (30,R2) # (100,R1) (30,R2) # Step 3 (31,R3) (100,R1) (30,R2) # Step 4 (31,R3) (100,R1) # Step 5 (100,R1) (81,R4) Step 6 (82,R7) La figura seguente mostra l’albero dei cammini minimi. R1R2R3R4R5R7R6(-,0)(R1,1)(R1,1)(R2,2)(R2,2)(R2,2)(R7,3)(R1,1)(R5,2)(R2,2)(R2,2)(R2,2)(R7,3)(R7,3)R1R2R3R4R5R7R6(-,0)(R1,20)(R1,100)(R2,30)(R2,30)(R3,31)2010010015011010101(R4,81)(R1,100)(R1,100)(R2,30)(R1,100)(R3,31)(R1,100)(R7,82) Fondamenti di Internet e Reti 097246 Esercizi 3 4c-2 Esercizio Data la rete rappresenta in figura (in cui su ogni link è riportato il costo) si trovi l’albero dei cammini minimi del nodo B. Si riporti nella tabella seguente ad ogni passo e per ogni nodo x l’etichetta: (Dx, px), dove px è il nodo precedente di x nel percorso e Dx è la distanza al passo corrente del nodo x dal nodo radice. Soluzione La tabella con l’evoluzione dell’algoritmo di Dijkstra è riportata qui di seguito. La notazione è la stessa dell’esercizio precedente; lo Step 0 si riferisce all’inizializzazione. Ad ogni passo (step) sono indicate le etichette rese permanenti (in rosso) ed i router che non vengono considerati al passo specifico (#); si ricorda che ad ogni passo, possono essere modificate le etichette dei soli nodi che sono vicini di nodi già parte dell’albero dei cammini minimi (nodi con etichetta rossa al passo precedente). A B C D E F G H Step 0 (inf,-) (0,-) (inf,-) (inf,-) (inf,-) (inf,-) (inf,-) (inf,-) Step 1 (6,B) (8,B) (7,B) # # # (5,B) Step 2 (6,B) (8,B) (7,B) (9,H) (10,H) (7,H) Step 3 (8,B) (7,B) (8,A) (10,H) (7,H) Step 4 (8,B) (8,A) (9.5, D) (7,H) Step 5 (7.5, G) (8,A) (9,G) Step 6 (8,A) (9,G) Step 7 (9,G) A H B E D G C F 9 2 5 4 7 6 0.5 8 5 4 2.5 2 2 1 11 A H B E D G C F 9 2 5 4 7 6 0.5 8 5 4 2.5 2 2 1 11 Fondamenti di Internet e Reti 097246 Esercizi 4 4c-3 Esercizio Sia data la seguente rete, dove per ogni link è indicata la coppia (W,C), con W peso della metrica di routing e C capacità del link. Si presti attenzione alla presenza di link monodirezionali per cui è indicato il verso di percorrenza Si chiede di: a. Calcolare l’albero dei cammini minimi da tutti i nodi al nodo A (attenzione al verso di percorrenza dei link) con l’algoritmo più efficiente. E’ necessario mostrare il processo di aggiornamento delle etichette b. Calcolare l’albero dei cammini minimi da tutti i nodi al nodo C e al nodo F con il vincolo che i percorsi non possano passare attraverso link con capacità inferiore a 5 Soluzione a) Il link B-D ha peso negativo, quindi dobbiamo usare l’algoritmo di Bellman-Ford. La tabella seguente riporta l’evoluzione dell’algoritmo. A B C D E F Step 0 (0,-) (inf,-) (inf,-) (inf,-) (inf,-) (inf,-) Step 1 (5,A) (1,A) (3,A) (inf,-) (inf,-) Step 2 (-2,D) (1,A) (3,A) (7,B) (4,C) Step 3 (-2,D) (1,A) (3,A) (0,B) (4,C) Step 4 (-2,D) (1,A) (3,A) (0,B) (4,C) Step 5 (-2,D) (1,A) (3,A) (0,B) (4,C) Fondamenti di Internet e Reti 097246 Esercizi 5 b) Eliminando gli archi con capacità CB A=>C A=>E Net 1 inf 2 2 Net 2 1 1 1 Net 3 inf 3 3 Net 4 inf 7 7 ABECD12110284Net1Net2Net4Net31118