Lezione InternetWorking: protocolli di Routing

Quando ci si pone la domanda: cosa sono i protocolli di routing ci si deve focalizzare sul fatto che si tratta di protocolli

a livello 3 del modello OSI al fine di consentirel'instradamento dei pacchetti verso la giusta destinazione.

Il ricorso ai protocolli di routing per la costruzione automatica e dinamica delletabelle di routing negli apparati

Router diventa necessario quando il numero di sottoreti interconnesse è elevato (come nel caso della rete Internet) in

sostituzione alla consueta creazione statica da parte dell'amministratore di rete nelle reti locali.

In Internet, visto il gran numero di reti interconnesse, dal punto di vista dell'instradamento è comodo intendere la

rete come un insieme di sistemi autonomi (AS – Autonomous Sytems), ognuno dei quali si occupa

di gestire autonomamente e uniformemente il routing interno alla propria rete con un medesimo protocollo dirouting

e l'interconnessione solo con gli altri AS direttamente connessi. I protocolli usati sono diversi a seconda che si tratti

di router all'interno di uno stesso AS (IGP - Interior Gateway Protocol), oppure di router che collegano tra loro più

AS (EGP - Exterior Gateway Protocol).

Per quanto riguarda la prima categoria, i protocolli possono essere suddivisi in dueclassi principali: distance vector e

link state. Quelli distance vector ricevono e mandano informazioni riguardo ai collegamenti solamente ai router

adiacenti mentre i link state le mandano a tutti i router del proprio sistema autonomo.

Protocolli di routing distance vector

L'instradamento distance vector, noto anche come routing di Bellman-Ford perché basato sull'omonimo algoritmo, è un

tipo di algoritmo di routing dinamico che tiene conto del carico istantaneo della rete.

Mentre gli algoritmi di tipo link state prevedono che ogni router sia informato deicambiamenti occorsi nell'intera

topologia della rete, i protocolli basati su distance vector sono invece più leggeri: ogni router misura la distanza

(secondo una metrica che può includere vari fattori) che lo separa dai nodi adiacenti ricevendo i dati dai router vicini.

A partire da tali dati, utilizzando l'algoritmo di Bellman-Ford, il router costruisce una tabella che associa ad ogni

destinazione conosciuta:

la distanza che lo separa dalla destinazione (metrica)

il primo passo del percorso calcolato (next-hop)

Periodicamente il router aggiorna le misure di distanza dai router adiacenti e comunica la propria tabella ai vicini. Dopo

sufficienti scambi di informazioni, ciascun router potrà avere una riga per ogni altro nodo nella rete.

Un protocollo di routing distance vector è RIP (Routing Information Protocol), che impiega il numero di hop come

metrica. RIP evita i routing loop (un circolo vizioso che si viene a formare quando le informazioni di routing

continuano a girare tra gli stessi router) adottando un limite massimo di hop dalla sorgente verso la destinazione (pari a

15). Questo numero di hop limita in ogni caso il diametro della rete consentito da RIP: infatti, un numero di hop

equivalente a 16 viene considerato come metrica infinita per indicare le rotte inaccessibili che non verranno installate in

tabella di routing. Anche EIGRP/IGRP (Enhanced/ Interior Gateway Routing Protocol) sono annoverati tra i protocolli

di routing distance vector, ma trattasi di protocolli proprietari Cisco. Nella maggior parte degli scenari attuali, i

protocolli dirouting distance vector non vengono utilizzati perché convergenza (il fatto che tutti i router del sistema

autonomo siano allineati in termini di topologia dopo un cambiamento all’interno della rete) e scalabilità (la possibilità

di aggiungere router all’interno del sistema autonomo) sono qualitativamente inferiori rispetto ai protocolli link state.

Protocolli di routing link state

Un protocollo di routing link state (routing basato sullo stato del collegamento) è un tipo di algoritmo in cui la topologia

dell'intera rete e tutti i costi dei collegamenti sono noti a tutti i router di un certo sistema autonomo.

In un protocollo link state ogni nodo della rete acquisisce informazioni sullo stato dei collegamenti adiacenti ed inoltra

queste informazioni a tutti gli altri nodi della rete tramite un link state packet (LSP). Ogni nodo memorizza i pacchetti

ricevuti e costruisce una mappa completa e aggiornata della rete: il link state database (LSD), ottenendo così gli stessi

risultati.

Quando il database è aggiornato, ogni nodo esegue in maniera indipendente un algoritmo (generalmente una variante

dell'Algoritmo di Dijkstra) per determinare il cammino minimo per raggiungere ogni nodo della rete ponendosi come

radice dell'albero dei cammini minimi. Al termine dell’elaborazione, è dunque possibile per il router costruire la tabella

di routing.L'utilizzo di un algoritmo di routing link state, presenta diversi vantaggi:

può gestire reti composte da un gran numero di nodi;

converge rapidamente al cammino minimo;

difficilmente genera cammini ciclici;

è facile da comprendere poiché ogni nodo ha la mappa della rete;

Il principale svantaggio di un algoritmo link state è

la complessità di realizzazione, anche dovuta alla notevole capacità di memoria

elaborazione richiesti dai router stessi.

Il protocollo link state maggiormente utilizzato nelle grandi reti è OSPF (Open Shortest Path First), dove ogni router

conosce l’esatta topologia della rete (a differenza di RIP dove ogni router è "miope", nel senso che conosce solo il

prossimo hop per una destinazione). Inoltre, nel calcolo dei cammini minimi, OSFP tiene conto anche delle bandwidth

dei link di interconnessione tra gli apparati, non fermandosi quindi a valutare (come fa RIP) solamente la distanza

“fisica” dalla destinazione. Ad esempio, si supponga che per raggiungere una destinazione si hanno due percorsi: il

primo attraversa due router con link FastEthernet, il secondo attraversa tre router con link Gigabit Ethernet, molto

presumibilmente l’algoritmo per il calcolo del cammino minimo sceglierà il secondo percorso.

OSPF utilizza il concetto di gerarchia, per cui permette di gestire reti di dimensioni notevoli. Un AS viene suddiviso in

aree, le quali contengono un gruppo di reti contigue, in modo tale che il routing venga gestito indipendentemente dalle

singole aree e poi interconnesso tra un’area e l’altra attraverso i router che si trovano al confine (virtuale) delle due aree.

Per questo motivo, OSPF è un protocollo adatto a reti estese e scalabili, dove i limiti dei protocolli distance vector

rendono improponibile utilizzarli, sia in termini di metriche non basate sulla larghezza di banda che per la lenta

convergenza del protocollo (in reti estese RIP può avere la convergenza di alcuni minuti).Un altro protocollo link state è

IS-IS (Intermediate System to Intermediate System), concettualmente simile a OSPF ma che non utilizza il protocollo IP

per trasportare le informazioni di routing e, per questo motivo, caduto in disuso.

BGP e MPLS

ll BGP (Border Gateway Protocol) è un protocollo di routing usato per connettere tra loro più router che

appartengono a sistemi autonomi distinti (trattandosi di un protocollo della famiglia EGP). È quindi un protocollo

di routing inter-AS, nonostante possa essere utilizzato anche tra router appartenenti allo stesso AS (nel qual caso è

indicato con il nome di iBGP, Interior Border Gateway Protocol), o tra router connessi tramite un ulteriore AS che li

separa (che viene definito di transito).

Il BGP è anche detto il protocollo di Internet perché è il protocollo di routing utilizzato all’interno della rete Internet e

che ci permette di “navigarvi”. Le sue decisioni di routing per scegliere le rotte migliori da installare nella tabella di

routing possono arrivare ad essere molto complesse ed essere dipendenti da una serie notevole di attributi; questa

complessità ne favorisce la flessibilità e lo rende il protocollo più adatto alla gestione delle rotte in ingresso e in uscita

dagli Internet Service Provider (ISP), dotati, come immaginabile, di reti molto complesse.

All’interno della rete dei Provider, sopra il livello di rete che permette, attraverso i protocolli di routing analizzati,

di costruire una “mappa” dei nodi e delle reti che costituiscono un’infrastruttura anche molto complessa,

viene eseguito il protocollo MPLS (Multi Protocol Label Switching): questo protocollo ha sostanzialmente lo scopo

di rendere il più veloce possibile l’instradamento dei pacchetti all’interno della rete del Provider, garantendo allo

stesso tempo sicurezza mantenendo separate le tabelle di routing relative ai diversi Clienti che si attestano su tale rete.

Infatti, MPLS aggiunge un'etichetta (label) ai pacchetti IP da instradare nel momento in cui questi giungono al “bordo

interno” della rete del Provider: questa operazione è svolta dai router di confine (da un lato sono connessi verso la rete

del Cliente e dall’altra verso la rete del Provider). A questo punto, il pacchetto viene instradato all’interno della rete

dove i router prenderanno le decisioni di routing esclusivamente basandosi sull’etichetta MPLS, che viene commutata

di router in router a seconda dello step successivo (router) verso la destinazione prefissata. Infine, quando il pacchetto

raggiunge il “bordo esterno” della rete, il router di confine compie l’operazione inversa, cioè rimuove l’etichetta MPLS

in modo che il pacchetto torni ad essere IP “puro”.

La commutazione interna su una tabella di associazione acchetto/etichetta risulta essere computazionalmente più

efficiente, ovvero più veloce, rispetto all'instradamento tramite tabelle di routing consentendo di ottenere throughput più

elevati.