Lezione 14Algoritmi di instradamento - link state e distance vector

Data: mercoledì 26 marzo 2025 · Fonte: slide del corso Internet, UniPD (algoritmi di instradamento)

Argomenti trattati

1. Instradamento e grafo: rete come grafo pesato, percorso e albero di costo minimo, instradamento e capacità, metriche di costo (salti, ritardo, perdite, throughput), instradamento statico e dinamico.
2. Le tre famiglie: link state (Dijkstra), distance vector (Bellman-Ford), path vector; confronto.
3. Link state: HELLO, ECHO, LSP e flooding; algoritmo di Dijkstra (stati permanente e temporaneo, pseudocodice) con l'esempio a 6 nodi e con la rete $A$-$G$.
4. Distance vector: vettori delle distanze, scambio periodico (25-35 s, scadenza 180 s, garbage collection 120 s), aggiornamento di Bellman-Ford, esempio di convergenza.
5. Guasto di un collegamento e conteggio all'infinito: ciclo a due salti, infinito limitato a 16, hold down, aggiornamenti immediati, split horizon e poison reverse.
6. Confronto distance vector e link state (RIP e OSPF).

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 →

Collegamenti

• Gli stessi algoritmi nei protocolli: Protocolli di instradamento - RIP, OSPF e BGPIn Internet l'instradamento non si può fare con un solo protocollo, per scalabilità (tabelle troppo grandi) e per autonomia amministrativa: ogni ISP è un sistema autonomo (AS) con il proprio algoritmo. All'interno di un AS si usano i protocolli IGP: RIP (distance vector, numero di salti, massimo 15, aggiornamenti ogni circa 30 s, su UDP porta 520) e OSPF (link state con Dijkstra, aree collegate all'area 0, cinque tipi di LSA, messaggi direttamente in IP). Tra AS si usa BGP4 (path vector, su TCP porta 179, eBGP tra AS e iBGP dentro l'AS, scelta del percorso per politica: preferenza locale, AS-PATH più corto, origine; i cicli si evitano scartando i cammini che contengono già il proprio AS; quattro messaggi: Open, Keepalive, Notification, Update).Protocolli di instradamento - RIP, OSPF e BGP →
• Le tabelle calcolate si usano nell'inoltro: 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 →

Lezione precedente: Lezione 12 · DHCP e protocollo IP · Lezione successiva: Lezione 15 · Path vector, inoltro e correttezza di Dijkstra e Bellman-Ford