Esercizi instradamento

Page 1

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: R2 131.175.15.0/24 –10 Mb/s R1 R3 R4R5 R6 R7 131.175.21.0/24 –100 Mb/s 131.175.70.0/24 –100 Mb/s 131.175.158.0/24 –10 Mb/s 131.175.130.0/24100 Mb/s R1 R2 R3 R4 R5 R7 R6 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)…