Instradamento: Dijkstra, Bellman-Ford, OSPF e BGP
La rete come grafo pesato, algoritmo di Dijkstra con dimostrazione della correttezza, OSPF, equazione di Bellman-Ford e vettori di distanze, conteggio all'infinito, sistemi autonomi e BGP, RPKI.
Un router deve sapere, per ogni destinazione, a quale vicino passare un pacchetto. Le tabelle non le scrive nessuno a mano: le calcolano i router stessi, scambiandosi informazioni con i protocolli di instradamento. Dietro ci sono due algoritmi classici sui grafi. In questa lezione vediamo l’algoritmo di Dijkstra con la dimostrazione della sua correttezza, i protocolli a stato del collegamento come OSPF, l’algoritmo di Bellman-Ford e i protocolli a vettore di distanze con il problema del conteggio all’infinito, e il BGP, che tiene insieme le reti di Internet.
La rete come grafo
La rete si rappresenta come un grafo: i router sono i nodi, i collegamenti gli archi, ciascuno con un costo positivo scelto dall’amministratore (spesso inversamente proporzionale alla velocità del collegamento). Il cammino migliore tra due nodi è quello di costo totale minimo.
L’algoritmo di Dijkstra
Nei protocolli a stato del collegamento ogni router diffonde a tutti gli altri l’elenco dei propri vicini e dei costi. Alla fine ogni router conosce l’intero grafo e calcola da solo i cammini minimi verso tutte le destinazioni con l’algoritmo di Dijkstra (1959):
- il nodo sorgente ha distanza 0, tutti gli altri distanza infinita; nessun nodo è “definitivo”;
- si sceglie, tra i nodi non definitivi, quello con la distanza provvisoria minima, e lo si rende definitivo;
- per ogni suo vicino
si controlla se passare da lui accorcia la strada: se 
, si aggiorna 
e si ricorda che il predecessore di è 
; - si torna al passo 2 finché tutti i nodi sono definitivi.
Teorema. Se tutti i costi sono non negativi, quando un nodo viene reso definitivo la sua distanza provvisoria è la distanza minima dalla sorgente.
Dimostrazione. Per assurdo, sia il primo nodo reso definitivo con una distanza 
maggiore della vera distanza minima 
. Si consideri un cammino minimo dalla sorgente a . Parte da un nodo definitivo (la sorgente) e arriva a , non ancora definitivo: lungo il cammino c’è quindi un primo nodo non definitivo 
, preceduto da un nodo definitivo 
. Quando è stato reso definitivo, la sua distanza era giusta ( è il primo errore), e il passo 3 ha posto 
, cioè 
. Poiché i costi sono non negativi, 
, essendo su un cammino minimo verso . Quindi 
: l’algoritmo avrebbe dovuto scegliere prima di , contro l’ipotesi. ∎
Con i costi negativi il ragionamento cade, ma nelle reti i costi sono sempre positivi. I predecessori formano l’albero dei cammini minimi: il router ne ricava, per ogni destinazione, il primo salto da usare. OSPF (Open Shortest Path First), il protocollo a stato del collegamento più diffuso dentro le reti aziendali e degli operatori, fa esattamente questo, e ricalcola l’albero in millisecondi quando un collegamento cambia stato.
Bellman-Ford e i vettori di distanze
L’alternativa non richiede di conoscere tutto il grafo. Ogni router conosce solo i costi verso i vicini e i vettori di distanze che i vicini gli inviano periodicamente, e applica l’equazione di Bellman-Ford:
![\[ d_x(y) = \min_{v\ \text{vicino di}\ x}\big(c(x, v) + d_v(y)\big) \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-04656b96e9a9efb707d7cbf27ab4cb03_l3.png "Rendered by QuickLaTeX.com")
cioè: la mia distanza da è la migliore tra “costo per arrivare al vicino più la distanza dichiarata dal vicino”. Ripetendo gli scambi, le stime convergono alle distanze vere. È il principio del RIP, uno dei protocolli più antichi, semplice ma lento.
Il conteggio all’infinito. Le cattive notizie viaggiano male. Si prendano tre router in fila, A, B e C, con costi 1. A dista 2 da C passando per B. Se il collegamento B-C si guasta, B cerca un’alternativa e trova che A dichiara distanza 2 da C: pensa allora di poter passare per A con costo 3, senza sapere che il cammino di A passa proprio per B. A riceve il nuovo vettore di B e porta la propria stima a 4, B a 5, e così via: le distanze crescono di uno a ogni scambio, mentre i pacchetti per C rimbalzano tra A e B. RIP limita il danno fissando l’infinito a 16 salti; tecniche come l’orizzonte diviso con avvelenamento (A dichiara a B distanza infinita verso le destinazioni che raggiunge tramite B) risolvono i casi semplici ma non tutti.
Il BGP e Internet
Internet è formata da circa 75 000 sistemi autonomi (AS): reti di operatori, università, aziende, ciascuna con una propria politica. Dentro un AS si usa OSPF o un protocollo simile; tra AS diversi si usa il BGP (Border Gateway Protocol). Il BGP è un protocollo a vettore di cammini: un annuncio non porta solo una distanza, ma l’elenco degli AS da attraversare per raggiungere un prefisso. Questo elimina gli anelli (un AS scarta gli annunci che contengono già sé stesso) e permette le politiche: un operatore può preferire un cammino più lungo ma più economico, o rifiutarsi di trasportare il traffico tra due concorrenti.
Il BGP si basa sulla fiducia negli annunci, e qui sta la sua debolezza: un AS che annuncia per errore o per malizia un prefisso non suo può attirare il traffico destinato a qualcun altro. Episodi del genere hanno reso irraggiungibili servizi globali per ore. La contromisura in corso di diffusione è l’RPKI, che firma crittograficamente quali AS sono autorizzati ad annunciare quali prefissi.
