Routing distribuito: reti, alberi e grafi

Reti come grafi

In una rete informatica la topologia può essere rappresentata con un grafo. I suoi elementi principali sono:

• Nodi: router o PC.
• Archi: cavi o link wireless.
• Costo: peso o metrica che descrive ritardo, distanza o banda.

Se il grafo contiene cicli, i pacchetti possono circolare senza fine generando un loop di routing. Per evitarlo i router ragionano su un albero: un grafo che collega tutti i nodi senza cicli e con un solo percorso tra due nodi. L'albero che copre l'intera rete è lo Spanning Tree. Il costo di un percorso è la somma dei costi degli archi attraversati: $C = \sum_{i=1}^{n} c_i$.

Routing distribuito

Nel routing distribuito non c'è un controllo centrale: ogni router scopre la mappa parlando con i vicini, invia aggiornamenti, aggiorna la tabella e inoltra le informazioni. Quando tutti condividono la stessa mappa si raggiunge la convergenza. Due approcci sono Distance Vector, in cui ogni router comunica distanze ai vicini e si affida a loro (es. RIP), e Link State, in cui ogni router diffonde i propri collegamenti e ricostruisce l'intero grafo (es. OSPF). L'obiettivo resta scegliere il percorso di costo minore.