Algoritmi di instradamento - link state e distance vector

Il livello di rete (Livello di rete e indirizzamento IPIl livello di rete (network layer) porta i datagrammi da host a host attraverso i router: incapsula (framing), sceglie il percorso (routing) e sposta il pacchetto da un ingresso a un'uscita del router (forwarding); in Internet lascia ai livelli superiori controllo d'errore, di flusso e di congestione. Un indirizzo IPv4 è di 32 bit, diviso in prefisso (rete, $n$ bit) e suffisso (host, $32-n$ bit). L'indirizzamento a classi (A, B, C, D, E) è obsoleto; oggi si usa quello senza classi (CIDR): data una notazione $a.b.c.d/n$ si ricavano $N=2^{32-n}$ indirizzi, indirizzo di rete (suffisso tutto 0) e di broadcast (suffisso tutto 1), oppure con la netmask: rete $=$ indirizzo AND maschera, broadcast $=$ indirizzo OR (NOT maschera).Livello di rete e indirizzamento IP →) ha due compiti distinti: l'instradamento (routing), cioè calcolare quale strada seguire, e l'inoltro (forwarding), cioè spostare ogni pacchetto verso l'interfaccia di uscita indicata dalla tabella (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 →). Questa nota tratta il primo: come i router riempiono le loro tabelle. I protocolli veri e propri che usano questi algoritmi (RIP, OSPF, BGP) sono in 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 →.

Il problema: trovare il percorso migliore

Definizione (instradamento). L'insieme delle procedure che permettono di determinare un percorso da un punto a un altro. È possibile solo se ogni router ha una tabella di inoltro per mandare il datagramma al nodo successivo (next hop) sulla strada verso la destinazione.

Perché il percorso conta: instradamento e capacità

In una rete a maglia la quantità di traffico consegnabile dipende da come i flussi sono instradati, non solo dalla capacità dei collegamenti. Si abbiano due flussi $S_1\to D_1$ e $S_2\to D_2$ e collegamenti tutti di capacità $C$:

• se i due flussi usano gli stessi collegamenti, condividono la capacità e il traffico massimo consegnato in totale è $C$;
• se i flussi sono distribuiti su percorsi diversi (nell'esempio delle slide ci sono tre collegamenti utilizzabili in parallelo), il traffico massimo sale a $3C$.

Un buon algoritmo di instradamento non cerca soltanto "una strada" ma una strada che usi bene la rete.

La rete come grafo pesato

Per trovare il percorso migliore un insieme di reti interconnesse (internet) si modella come grafo pesato (nodi, archi, cammini e connessione sono definiti in Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →): ogni router è un nodo, ogni rete tra due router è un arco, e a ogni arco è associato un costo. Se tra due nodi non c'è un arco il costo è $\infty$. Il significato del costo cambia da protocollo a protocollo.

Definizione (percorso di costo minimo). Dato un grafo connesso $G=(V,E)$ e una funzione di costo additiva (il costo di un cammino è la somma dei costi degli archi), il percorso di costo minimo (least-cost route, LCR) da una sorgente $s$ a un nodo $v$ è la sequenza di nodi connessi, da $s$ a $v$, con somma dei costi minima fra tutti i cammini possibili.

Ogni router deve trovare il percorso di costo minimo verso tutti gli altri router: con $N$ router sono $N-1$ percorsi per ciascuno, cioè $N(N-1)$ percorsi in tutta la rete. Conviene raccoglierli in un albero di costo minimo (least-cost tree): un albero che ha il router sorgente come radice, tocca tutti gli altri nodi e in cui il cammino dalla radice a ogni nodo è quello minimo. Si ha così un solo albero per sorgente, quindi $N$ alberi per tutta la rete.

Quale costo? Le metriche

"Migliore" non ha un'unica risposta: minimo numero di salti, minimo ritardo end-to-end, minima probabilità di perdita, massimo throughput a lungo termine. Per far calcolare a Dijkstra o a Bellman-Ford il percorso desiderato basta scegliere bene il costo $c_{i,j}$ di ogni coppia di nodi collegati:

Esempio (ritardo). Pacchetto di $L=1500$ byte $=12\,000$ bit su un collegamento da $R=10$ Mbit/s con propagazione $t_p=2$ ms: $c=12\,000/10^7\ \text{s}+2\ \text{ms}=1{,}2+2=3{,}2$ ms.

Esempio (perdite). Due collegamenti con $P_{ok}=0{,}9$ e $0{,}8$: la probabilità di successo sul cammino è $0{,}9\cdot0{,}8=0{,}72$. Con i costi logaritmici si ottiene la stessa informazione per somma: $-\ln0{,}9-\ln0{,}8=0{,}1054+0{,}2231=0{,}3285=-\ln0{,}72$. Minimizzare la somma dei costi equivale quindi a massimizzare la probabilità di successo. I passaggi: (1) la probabilità di successo di un cammino è il prodotto $P=\prod P_{ok}(i,j)$ (i collegamenti perdono in modo indipendente: Indipendenza di eventiA e B sono indipendenti se P(A ∩ B) = P(A) P(B), cioè se sapere che uno si è verificato non cambia la probabilità dell'altro; l'indipendenza passa ai complementari, non va confusa con l'incompatibilità, e per più eventi va richiesta su ogni sottofamiglia.Indipendenza di eventi →); (2) il logaritmo trasforma il prodotto in somma, $\ln(ab)=\ln a+\ln b$; (3) poiché $0<P_{ok}\le1$ si ha $\ln P_{ok}\le0$, e il segno meno rende ogni costo $c\ge0$, come richiede Dijkstra; (4) il logaritmo è crescente, quindi $P$ massima equivale a $\ln P$ massimo, cioè $-\ln P=\sum c_{i,j}$ minimo.

Perché per il throughput serve un trucco. Il throughput a lungo termine di un cammino è il minimo dei bitrate lungo il cammino (il collo di bottiglia), non la loro somma: la condizione di additività richiesta da Dijkstra non vale e il massimo throughput non si può riprodurre esattamente. Si può però approssimare con $c=1/R^n$ e $n$ grande: elevando alla $n$ si amplifica il peso del collegamento più lento, così che il cammino più corto sia quasi sempre quello con il collo di bottiglia migliore.

Esempio. Un cammino $P$ di 10 collegamenti da 100 Mbit/s (collo di bottiglia 100) e un cammino $Q$ di due collegamenti da 50 e 100 Mbit/s (collo di bottiglia 50). Con $n=1$: $P=10/100=0{,}1$, $Q=1/50+1/100=0{,}03$: vince $Q$, sbagliando. Con $n=3$: $P=10^{-5}$, $Q=9\cdot10^{-6}$, ancora $Q$. Con $n=6$: $P=10\cdot100^{-6}=10^{-11}$, $Q=50^{-6}+100^{-6}=6{,}5\cdot10^{-11}$: vince $P$, correttamente.

Instradamento statico e dinamico

• Statico (reti piccole): le tabelle sono compilate a mano; non reagiscono a guasti o cambi di topologia. Si possono definire più cammini statici tra due nodi per avere un po' di resilienza.
• Dinamico (reti grandi): un protocollo aggiorna da solo le tabelle quando cambiano carico o topologia. Costo: i protocolli generano traffico di controllo, e durante i transitori le tabelle dei nodi possono non essere coerenti (rischio di instabilità).

Le tre famiglie di algoritmi

Link state

Ogni nodo deve prima conoscere i vicini e identificarli (pacchetti HELLO), poi calcolare il costo dei collegamenti diretti, i costi locali (per esempio con pacchetti ECHO per misurare il ritardo). Con queste informazioni crea un pacchetto, il Link State Packet (LSP), e lo diffonde a tutti gli altri router con un flooding (una specie di broadcast multi-salto), da ripetere dopo ogni cambiamento dello stato di un collegamento. Quando un router ha ricevuto l'LSP di ogni nodo, ha l'intero grafo e applica Dijkstra per ottenere il percorso minimo verso ogni altro nodo.

Formato dell'LSP: nome della sorgente seguito da coppie (vicino, costo).

Esempio. Rete con sette router $A,\dots,G$ e archi $A\!-\!B=4$, $A\!-\!F=1$, $B\!-\!C=2$, $B\!-\!G=1$, $C\!-\!D=3$, $C\!-\!G=4$, $D\!-\!E=6$, $E\!-\!F=3$, $F\!-\!G=1$.

Ogni router ha ricevuto questi sette LSP:

Leggendo la tabella un nodo qualsiasi ricostruisce il grafo della figura (ogni arco compare due volte, una per estremo). Su questo grafo applica Dijkstra.

L'algoritmo di Dijkstra

(L'algoritmo è presentato anche come problema sui grafi in Cammini minimi e algoritmo di DijkstraGrafi pesati, lunghezza di un cammino e distanza; sottocammini di un cammino minimo; problema SSSP; algoritmo di Dijkstra con cloud e priority queue, rilassamento degli archi, esempio svolto; correttezza (due lemmi) e complessità O(min(n^2, (n+m) log n)) con lista non ordinata o heap; pesi non negativi.Cammini minimi e algoritmo di Dijkstra →; qui è letto dal punto di vista del router.) L'obiettivo è trovare il percorso più breve da un nodo di partenza $s$ (starting node) a tutti gli altri (one-to-all). L'algoritmo parte con valori iniziali per la distanza da $s$ e a ogni passo li migliora, determinando a ogni passo la distanza minima di un nodo.

Definizione (stato di un nodo in Dijkstra). Ogni nodo $\ell$ ha uno stato $(d_\ell,\ p\text{ oppure }t)$:

• $d_\ell$ è la stima corrente della distanza da $s$ (il costo accumulato);
• l'etichetta è permanente ($p$) se $d_\ell$ è già la distanza minima da $s$, temporanea ($t$) altrimenti.

A ogni passo un nodo è il nodo corrente.

Passi:

1. Inizializzazione. Lo stato di $s$ è $(0,p)$ e $s$ è il nodo corrente. Ogni altro nodo ha stato $(\infty,t)$.
2. Rilassamento. Per ogni vicino $v$ del nodo corrente $u$ non ancora permanente si calcola $d_v=\min\{d_v,\ d_u+c_{u,v}\}$; se il minimo è la seconda quantità, si aggiorna anche il predecessore di $v$ (puntatore a $u$).
3. Scelta. Tra i nodi temporanei si sceglie quello con $d$ minima: diventa permanente e nodo corrente. Si torna al passo 2 finché non restano nodi temporanei raggiungibili. Perché quel nodo è definitivo: qualunque altra strada verso di lui dovrebbe passare per un altro nodo temporaneo, che ha già una stima almeno uguale, e da lì i costi (non negativi) possono solo aumentare; la dimostrazione precisa è nella sezione sulla correttezza.
4. Dai predecessori ai cammini. Per conoscere il cammino da $s$ a $v$ si segue la catena dei predecessori da $v$ a $s$ e la si legge al contrario.

Pseudocodice (con dist e prev):

Dijkstra(Graph, source):
   per ogni vertice v: dist[v] = INFINITO; prev[v] = NON DEFINITO; v entra in Q
   dist[source] = 0
   finche' Q non e' vuoto:
       u = vertice di Q con dist minima; togli u da Q
       per ogni vicino v di u ancora in Q:
           alt = dist[u] + length(u, v)
           se alt < dist[v]:  dist[v] = alt;  prev[v] = u
   restituisci dist[], prev[]

Esempio 1 (grafo a 6 nodi, sorgente 1). Archi: $1\!-\!2=7$, $1\!-\!3=9$, $1\!-\!6=14$, $2\!-\!3=10$, $2\!-\!4=15$, $3\!-\!4=11$, $3\!-\!6=2$, $4\!-\!5=6$, $5\!-\!6=9$.

Distanze da 1: $d_2=7$, $d_3=9$, $d_6=11$, $d_4=20$, $d_5=20$. Cammino da 1 a 5: predecessore di 5 è 6, di 6 è 3, di 3 è 1: leggendo al contrario $1\to3\to6\to5$, costo $9+2+9=20$. Cammino da 1 a 4: predecessore di 4 è 3: $1\to3\to4$, costo $9+11=20$.

Esempio 2 (il grafo $A,\dots,G$, sorgente $A$). Ogni riga è lo stato dopo che il nodo indicato è diventato permanente; in ogni cella: distanza e predecessore.

Spiegazione dei passi cruciali: al passo 1 da $F$ si raggiunge $G$ con $1+1=2$ e $E$ con $1+3=4$; al passo 2 da $G$ si migliora $B$ ($2+1=3<4$) e si trova $C$ ($2+4=6$); al passo 3 da $B$ si migliora $C$ ($3+2=5<6$); al passo 4 $E$ (distanza 4, minore di 5) fa raggiungere $D$ con $4+6=10$; al passo 5 $C$ migliora $D$ ($5+3=8<10$).

Albero di costo minimo di $A$ (archi in colore): $A\!-\!F$, $F\!-\!G$, $G\!-\!B$, $B\!-\!C$, $C\!-\!D$, $F\!-\!E$.

(le etichette sugli archi dell'albero sono le distanze da $A$, non i costi degli archi; i tratteggi sono archi che esistono ma non fanno parte dell'albero.)

Dall'albero alla tabella di $A$. Il next hop verso ogni destinazione è il primo nodo del cammino: verso $G$, $B$, $C$, $D$, $E$ e $F$ si passa tutti da $F$ (per $B$: $A\to F\to G\to B$).

Ogni router esegue Dijkstra per conto proprio, con sé stesso come sorgente, ottenendo il proprio albero e la propria tabella.

Complessità. Con la scelta del minimo tra i nodi temporanei fatta scorrendo l'elenco si fanno $n$ scelte di costo $O(n)$ ciascuna, quindi $O(n^2)$ (Notazione asintoticaDefinizioni di O, Omega, Theta e o piccolo con le costanti c ed n0; esempi con costanti esplicite; proprietà (polinomi, esponenziali, logaritmi, somme, implicazioni tra notazioni); sommatorie notevoli; terminologia (logaritmica, lineare, polinomiale, esponenziale).Notazione asintotica →: il numero di operazioni cresce come il quadrato di $n$); con una coda con prioritàstruttura dati che restituisce l'elemento di chiave minima in tempo logaritmicoCode con priorità → si arriva a $O((n+m)\log n)$, con $m$ numero di archi. Conti: ogni nodo diventa permanente una volta ($n$ volte la ricerca del minimo, $O(n)$ ciascuna, quindi $n\cdot n$), e ogni arco viene rilassato al più una volta per estremo ($O(m)$ rilassamenti); con la coda ogni estrazione o aggiornamento costa $O(\log n)$.

Distance vector

Qui nessun nodo conosce la topologia. Ogni nodo parte conoscendo solo i vicini (con i pacchetti HELLO e ECHO come sopra) e costruisce un vettore delle distanze (distance vector, DV): per ogni destinazione, la distanza e il next hop del percorso minimo attualmente noto.

Esempio (DV di $A$ all'inizio).

Questi vettori rudimentali non bastano a inoltrare bene i pacchetti: sono i percorsi minimi con le informazioni limitate che un nodo ha. Per migliorarli i nodi devono aiutarsi: periodicamente (a intervalli casuali tra 25 e 35 s) oppure quando il proprio DV cambia, ogni nodo manda il suo DV ai vicini. Quando un nodo riceve il DV di un vicino, aggiorna il proprio con un algoritmo distribuito (Bellman-Ford). Dopo un transitorio i DV convergono ai veri percorsi minimi. Se una riga non viene aggiornata entro un certo tempo (expiration timer, 180 s) il costo verso quella destinazione diventa infinito; dopo altri 120 s (garbage collection) la riga è cancellata.

Formula (aggiornamento di Bellman-Ford). Il nodo $A$ riceve dal vicino $Y$ il DV con le stime $d_{Y,w}$ del costo da $Y$ a ogni destinazione $w$. Per ogni $w$: $$D_{A,w}=\min\{\,D_{A,w},\ D_{A,Y}+d_{Y,w}\,\}.$$ Se il valore passando per $Y$ è minore, si mettono nella riga $w$ il nuovo costo e next hop $=Y$.

Qui $D_{A,Y}$ è il costo immediato del collegamento $A\to Y$ e $d_{Y,w}$ è il costo minimo stimato da $Y$ a $w$ (che può passare per più salti).

Esempio. $A$ riceve da $B$ il primo DV di $B$, che dice $d_{B,A}=4$, $d_{B,C}=2$, $d_{B,G}=1$ e $\infty$ per $D$, $E$, $F$. Con $D_{A,B}=4$: per $C$, $\min\{\infty,\,4+2\}=6$ (next hop $B$); per $G$, $\min\{\infty,\,4+1\}=5$ (next hop $B$); per $D$, $\min\{\infty,\,4+\infty\}=\infty$ (nessun miglioramento: $B$ non conosce ancora $D$). Poi arriva il DV di $F$ (con $d_{F,G}=1$, $d_{F,E}=3$) e $A$ calcola, con $D_{A,F}=1$: per $G$, $\min\{5,\,1+1\}=2$ (next hop $F$); per $E$, $\min\{\infty,\,1+3\}=4$ (next hop $F$).

Convergenza: giro per giro

Se tutti i nodi scambiano i DV in giri sincroni, il vettore di $A$ nella rete $A,\dots,G$ evolve così (ogni giro tutti i nodi usano i DV del giro precedente):

Il giro 5 non cambia più niente: l'algoritmo è a regime. Il giro $k$ ha trovato i cammini minimi con al più $k+1$ archi; il cammino $A\to D$ ottimo ($A\!-\!F\!-\!G\!-\!B\!-\!C\!-\!D$, costo 8) ha 5 archi, quindi serve il giro 4 (dimostrazione sotto). I risultati coincidono con Dijkstra (stessa tabella di $A$). Le tabelle a regime (destinazione, distanza, next hop) per $A$, $B$ e $C$ sono:

Guasto di un collegamento

Se il collegamento $B\!-\!G$ si rompe: $B$ non riceve più HELLO da $G$; scaduto il timeout $B$ toglie $G$ dai vicini e cancella dalla tabella tutte le righe che hanno $G$ come next hop, poi manda il nuovo DV ai suoi vicini (e $G$ fa lo stesso). L'aggiornamento si propaga e a regime le tabelle sono quelle dell'albero senza $B\!-\!G$: ad esempio $B$ raggiunge $G$ con costo $2+4=6$ passando per $C$ ($B\to C\to G$) e $A$ raggiunge $D$ con costo $4+2+3=9$ passando per $B$. In generale, un nodo che rileva un guasto o una variazione di costo manda subito il proprio DV ai vicini e riavvia il processo distribuito.

Il problema del conteggio all'infinito

Nella rete senza $B\!-\!G$ si rompe anche il collegamento $C\!-\!D$. Prima del guasto $B$ raggiunge $D$ con costo $5$ passando per $C$. Succede questo:

1. $C$ cancella la riga verso $D$ ma, prima di mandare il suo DV, riceve il DV di $B$ che dice "raggiungo $D$ con 5". $C$ calcola $2+5=7$ e aggiorna: $D$ a costo 7 con next hop $B$.
2. $C$ manda il DV a $B$: $B$ vede che il percorso verso $D$ (già via $C$) è cambiato e calcola $2+7=9$.
3. $B$ manda il DV a $C$: $C$ calcola $2+9=11$. E così via.

Costo di $D$ visto da $C$ e da $B$: $7, 9, 11, 13, 15, 17, \dots$: cresce di 2 a ogni messaggio, cioè di 4 a ogni scambio completo ($B\to C$ e $C\to B$), perché ogni nodo somma il costo $2$ del collegamento $B\!-\!C$ alla stima del vicino (dopo $k$ messaggi la stima vale $5+2k$). Cresce fino all'infinito, ma lentamente. Nel frattempo i pacchetti per $D$ rimbalzano tra $B$ e $C$ (problema del ciclo a due salti, two-hop loop), perché il percorso verso $D$ non esiste più.

La stima supera la soglia $16$ al sesto messaggio ($5+2\cdot6=17>16$; il quinto dà $15<16$): lì il costo viene considerato infinito e il conteggio si ferma.

Soluzioni:

• Infinito limitato (limited infinity): una distanza maggiore di 16 è considerata infinita. Funziona solo in reti con distanza massima tra due nodi inferiore a 16. Nell'esempio il conteggio si ferma quando si arriva a $\ge16$ (dopo pochi scambi: $7, 9, 11, 13, 15, 17\to16=\infty$).
• Hold down: quando un router viene informato che una destinazione non è raggiungibile ignora per 60 s ogni aggiornamento per quella destinazione, evitando che informazioni obsolete siano prese per valide (a prezzo di reagire più lentamente ai cambi di topologia).
• Aggiornamento immediato (triggered update): i cambi di topologia sono notificati con priorità, senza aspettare il timer: convergenza più rapida e guasti scoperti prima.
• Split horizon: a ciascun vicino $Y$ si inviano solo le righe del DV che non hanno $Y$ come next hop. Nell'esempio $B$ non manda a $C$ la riga di $D$ (perché $B$ raggiunge $D$ proprio attraverso $C$): il ciclo non nasce.
• Poison reverse: lo split horizon ha un difetto: se $B$ omette la riga di $D$, $C$ non sa se è perché $B$ applica lo split horizon o perché non conosce davvero $D$. Con il poison reverse il nodo manda tutte le destinazioni ma mette $\infty$ per quelle raggiungibili attraverso il collegamento su cui sta inviando: $B$ dice a $C$ "per $D$ il costo è $+\infty$": "non usare questo valore, quello che so su questa strada viene da te".

Nota. Split horizon e poison reverse eliminano i cicli a due salti ma non tutti i cicli (con tre o più nodi in cerchio il conteggio all'infinito può ancora presentarsi): per questo sono combinati con l'infinito limitato.

Confronto tra distance vector e link state

Path vector

I costi non permettono a chi invia di imporre politiche sul percorso del pacchetto: con il percorso di costo minimo la strada la decide la metrica. Nel path vector il percorso migliore è scelto dalla sorgente in base alla politica che le interessa, quindi la sorgente può controllare la strada. L'obiettivo non è minimizzare un costo ma la raggiungibilità: far arrivare il pacchetto a destinazione in modo conveniente, senza assegnare costi ai cammini.

L'albero che ne esce è un albero di copertura (spanning tree) ma non è l'albero di costo minimo: è quello determinato dalla politica della sorgente. Una sorgente può applicare più politiche insieme, per esempio "usa il minor numero di nodi" (simile al costo minimo) oppure "evita certi nodi come nodi intermedi". Come il distance vector, l'algoritmo è asincrono e distribuito:

1. un nodo all'avvio crea un vettore dei cammini con le informazioni sui vicini immediati (invia messaggi di saluto, HELLO + ECHO, per raccoglierle);
2. lo manda a tutti i vicini;
3. quando riceve il vettore di un vicino $v$ lo combina col proprio con una regola simile a Bellman-Ford, ma applicando la propria politica invece del costo minimo: $$\text{Path}(x,y)=\text{best}\{\,\text{Path}(x,y),\ x+\text{Path}(v,y)\,\},\qquad \forall v\ne x,$$ dove $x+\text{Path}(v,y)$ è il cammino ottenuto anteponendo $x$ al cammino annunciato da $v$ verso $y$.

Rilevamento dei cicli. Ogni annuncio contiene l'intero cammino. Un nodo che riceve un cammino in cui compare già sé stesso lo scarta: i cammini sono privi di cicli e il problema del conteggio all'infinito non esiste (è quanto fa BGP, con i numeri di AS al posto dei router).

Esempio. Rete con archi $A\!-\!B$, $B\!-\!C$, $A\!-\!D$, $D\!-\!C$, $C\!-\!E$ e destinazione $E$. $A$ riceve da $B$ l'annuncio "per $E$: $B\,C\,E$" e da $D$ l'annuncio "per $E$: $D\,C\,E$". Con la politica "non attraversare $D$" $A$ sceglie $A\,B\,C\,E$ anche se, per costi dei collegamenti, passare da $D$ fosse più economico. Se invece $C$ riannunciasse a $B$ un cammino che contiene $B$, $B$ lo scarta.

L'esito di un algoritmo di instradamento è una tabella di instradamento (routing table), con (1) l'indirizzo della rete di destinazione, (2) il router a cui inoltrare il pacchetto (next hop), (3) il costo per raggiungere la destinazione; il formato dei pacchetti scambiati è fissato dal protocollo di instradamento. Come si usa la tabella è in 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 →.

Dimostrazioni di correttezza

Notazione: $\delta(s,v)$ è il costo minimo (vero) da $s$ a $v$; $c(u,v)\ge0$ il costo dell'arco.

Proprietà (sottostruttura ottima). Se $s=v_0,v_1,\dots,v_k=v$ è un cammino minimo da $s$ a $v$, ogni suo tratto $v_i,\dots,v_j$ è un cammino minimo da $v_i$ a $v_j$. Di conseguenza $\delta(s,v)=\min_{u}\{\delta(s,u)+c(u,v)\}$ al variare dei vicini $u$ di $v$ (equazione di Bellman).

Dimostrazione. Se per assurdo il tratto $v_i\to v_j$ avesse un'alternativa di costo minore, sostituendola si otterrebbe un cammino $s\to v$ di costo minore di $\delta(s,v)$: assurdo. L'equazione di Bellman segue perché l'ultimo arco di un cammino minimo è $(u,v)$ per qualche vicino $u$ e il tratto $s\to u$ è minimo. $\square$

Correttezza di Dijkstra (costi non negativi)

Proprietà (invariante di Dijkstra). Quando un nodo $u$ diventa permanente, $d_u=\delta(s,u)$. Inoltre per ogni nodo $v$ non permanente $d_v$ è la lunghezza del cammino minimo da $s$ a $v$ che usa come nodi intermedi soli nodi permanenti.

Dimostrazione per induzione sull'ordine con cui i nodi diventano permanenti.

• Base. Il primo nodo permanente è $s$ con $d_s=0=\delta(s,s)$ (i costi sono $\ge0$, nessun cammino può costare meno).
• Passo. Sia $P$ l'insieme dei nodi permanenti e valga l'invariante per tutti i nodi in $P$. Sia $u\notin P$ il nodo con $d_u$ minima tra i temporanei: l'algoritmo lo rende permanente. Supponiamo per assurdo che esista un cammino $\Pi$ da $s$ a $u$ di costo $<d_u$. Poiché $s\in P$ e $u\notin P$, $\Pi$ esce da $P$: sia $(x,y)$ il primo arco con $x\in P$, $y\notin P$ (può essere $y=u$). Quando $x$ è diventato permanente l'algoritmo ha rilassato $(x,y)$, quindi $$d_y\;\le\;d_x+c(x,y)\;=\;\delta(s,x)+c(x,y)\;\le\;\text{costo del tratto di }\Pi\text{ da }s\text{ a }y\;\le\;\text{costo}(\Pi)\;<\;d_u .$$ Il primo passaggio è il rilassamento dell'arco $(x,y)$; l'uguaglianza è l'ipotesi induttiva su $x\in P$; il terzo passaggio dice che il tratto di $\Pi$ fino a $x$ costa almeno $\delta(s,x)$ (per definizione di costo minimo); l'ultimo usa $c\ge0$: il resto di $\Pi$ da $y$ a $u$ non può avere costo negativo. Ma allora $y$ è temporaneo con $d_y<d_u$, contro la scelta di $u$ come minimo. Quindi nessun cammino costa meno di $d_u$ e $d_u=\delta(s,u)$.
• Seconda parte. Rendere permanente $u$ e rilassare i suoi archi mantiene l'invariante, perché i nuovi cammini candidati sono quelli che passano per $u$ come ultimo nodo permanente. $\square$

Dove serve $c\ge0$. Con un costo negativo il passaggio "il resto di $\Pi$ non costa meno di zero" cade. Controesempio: archi $s\!\to\! a$ di costo 2, $s\!\to\! b$ di costo 3, $b\!\to\! a$ di costo $-2$. Dijkstra rende permanente $a$ con $d_a=2$ (minimo tra 2 e 3), ma il cammino $s\to b\to a$ costa $1<2$. In una rete di router i costi sono sempre positivi (ritardi, numeri di salti), quindi Dijkstra si può usare.

Correttezza di Bellman-Ford (e del distance vector)

Sia $D^{k}(A,w)$ la stima di $A$ per $w$ dopo $k$ giri sincroni, con $D^{0}(A,w)=c(A,w)$ se $A$ e $w$ sono vicini, $0$ se $A=w$, $\infty$ altrimenti. Il giro $k+1$ applica la regola dell'algoritmo: $$D^{k+1}(A,w)=\min\Big\{D^{k}(A,w),\ \min_{Y\ \text{vicino di }A}\big(c(A,Y)+D^{k}(Y,w)\big)\Big\}.$$

Proprietà (invariante di Bellman-Ford). $D^{k}(A,w)$ è il costo minimo tra i cammini da $A$ a $w$ con al più $k+1$ archi.

Dimostrazione per induzione su $k$.

• Base ($k=0$). I cammini con al più un arco sono il cammino vuoto ($A=w$) e i collegamenti diretti: è esattamente $D^0$.
• Passo. Un cammino da $A$ a $w$ con al più $k+2$ archi o ha al più $k+1$ archi (e il minimo di questi è $D^{k}(A,w)$ per ipotesi), oppure ha esattamente $k+2$ archi: il primo è $(A,Y)$ per un vicino $Y$, e il resto è un cammino da $Y$ a $w$ con $k+1$ archi, quindi il minimo è $c(A,Y)+D^{k}(Y,w)$. Il minimo tra tutte queste alternative è $D^{k+1}(A,w)$. $\square$

Conseguenza (convergenza). Se la rete non ha cicli di costo negativo (e con costi $\ge0$ non ne ha), un cammino minimo è semplice, cioè non ripete nodi, e ha quindi al più $n-1$ archi. Dopo $n-2$ giri (in pratica $n-1$) tutte le stime sono i veri costi minimi e un ulteriore giro non cambia niente: è la condizione di regime vista nella tabella dei giri. Nell'esempio, il cammino minimo $A\to D$ ha 5 archi, quindi $D^{4}(A,D)=8$ è il primo valore esatto: lo conferma la tabella dei giri.

Versione asincrona. Nella rete vera i DV non sono scambiati a giri sincroni, ma vale lo stesso: (1) le stime non scendono mai sotto il valore vero, perché ogni stima è il costo di un cammino realmente esistente; (2) per induzione sul numero di archi del cammino minimo, quando $A$ riceve i DV già esatti dei vicini la sua stima diventa esatta e resta tale. Dopo al più $n-1$ periodi di aggiornamento senza altri cambiamenti di topologia le stime sono esatte.

Perché allora il conteggio all'infinito? La prima proprietà ("ogni stima è il costo di un cammino realmente esistente") vale solo se la topologia non cambia. Se un collegamento si rompe, alcune stime descrivono cammini che non esistono più: sono più basse del vero costo (che ora è $\infty$ o più alto) e continuano a circolare tra i nodi, come nel ciclo $B\leftrightarrow C$ dell'esempio, finché il costo non cresce abbastanza. Per questo servono i rimedi della sezione precedente. Dijkstra, che lavora su una fotografia completa del grafo, non ha questo problema.