Lezione 15Path vector, inoltro e correttezza di Dijkstra e Bellman-Ford

Data: giovedì 27 marzo 2025 · Fonte: slide del corso Internet, UniPD (algoritmi path vector e inoltro)

Argomenti trattati

1. Path vector: instradamento per politica invece che per costo, vettore dei cammini, rilevamento dei cicli.
2. Inoltro (forwarding): inoltro diretto e indiretto, default gateway, configurazione delle interfacce con IP e netmask, condizione di inoltro diretto con l'AND, tabella di instradamento e longest prefix match, default route, esempi con tabelle e destinazioni diverse, aggregazione delle rotte, inoltro con etichette (MPLS).
3. Dimostrazioni di correttezza: sottostruttura ottima dei cammini minimi; correttezza di Dijkstra (invariante, ruolo dei costi non negativi, controesempio con costi negativi); correttezza di Bellman-Ford e del distance vector (cammini con al più $k+1$ archi dopo $k$ giri, convergenza in al più $n-1$ giri).

Teoria

• Algoritmi di instradamento - link state e distance vectorL'instradamento (routing) trova il percorso di costo minimo in un grafo pesato in cui i router sono nodi e le reti tra due router sono archi. Link state: ogni router diffonde con un flooding i pacchetti LSP sui propri collegamenti, ricostruisce tutto il grafo e applica Dijkstra (nodi con stato (distanza, permanente o temporaneo)). Distance vector: ogni router conosce solo i vicini e scambia con loro il proprio vettore delle distanze, aggiornato con Bellman-Ford $D_{A,w}=\min{D_{A,w},,D_{A,Y}+d_{Y,w}}$; converge in al più $n-1$ giri ma può soffrire del conteggio all'infinito (limite a 16, hold down, aggiornamenti immediati, split horizon con poison reverse). Path vector: ogni annuncio porta l'intero cammino, si sceglie per politica e non per costo, e i cicli si scoprono trovando sé stessi nel cammino. Dijkstra è corretto se i costi sono non negativi (invariante: un nodo permanente ha già la distanza vera); Bellman-Ford è corretto perché dopo $k$ giri conosce i cammini minimi con al più $k+1$ archi.Algoritmi di instradamento - link state e distance vector → — path vector e dimostrazioni
• Instradamento e inoltroL'inoltro (forwarding) mette il pacchetto sulla strada verso la destinazione, un salto alla volta (hop by hop). Se la destinazione è nella stessa rete del mittente l'inoltro è diretto (si usa l'ARP per il MAC del destinatario), altrimenti è indiretto: il pacchetto va al router successivo (next hop) indicato dalla tabella di instradamento, o al default gateway. Con le netmask: l'inoltro è diretto attraverso l'interfaccia $x$ se $\text{IP(dst)}\ \text{AND}\ \text{NM}(x)=\text{IP}(x)\ \text{AND}\ \text{NM}(x)$; altrimenti si scorre la tabella dalla maschera più lunga (longest prefix match) e si usa il primo match. La riga con rete $0.0.0.0$ e maschera $0.0.0.0$ (default route) corrisponde sempre. L'aggregazione di rotte (route aggregation) riduce la tabella, e nell'inoltro con etichette (MPLS) la tabella si consulta per indice.Instradamento e inoltro → — inoltro diretto e indiretto, longest prefix match, aggregazione

Esercizi

• Esercizio - tabella di instradamento del router R1 e inoltro di due pacchetti — esercizi 13 e 14
• Esercizio - tabelle di inoltro e instradamento dei router A e B — esercizio 18
• Esercizio - pacchetti ARP e IP con router e con switch — esercizi 19 e 20 (indirizzi MAC e IP a ogni salto)

Lezione precedente: Lezione 14 · Algoritmi di instradamento - link state e distance vector · Lezione successiva: Lezione 17 · Protocolli di instradamento e ICMP