Nel nostro studio sugli algoritmi di instradamento abbiamo considerato la rete come semplice interconnessione di router. Ciascun router non era diverso dagli altri, nel senso che tutti eseguivano lo stesso algoritmo di instradamento. Nella pratica questo modello risulta semplicistico, almeno per due motivi:

1. Scalabilità. Al cresce del numero di router il tempo per eseguire algoritmi di instradamento diventa proibitivo. Internet è formata da centinaia di milioni di host. Archiviare informazioni riguardo numeri di host così alti richiederebbe dimensioni di memoria enormi, inoltre il traffico generato da una comunicazione broadcast saturerebbe tutta la banda, non dando modo ai pacchetti contenti dati di esse spediti.
2. Autonomia amministrativa. Internet è una rete di ISP, tali ISP, in genere, desiderano gestire liberamente i propri router. L'ideale sarebbe che ciascun ISP fosse in grado di amministrare la propria rete come preferisce, mantenendo la possibilità di comunicare con reti esterne.
   Questi problemi si risolvono con i sistemi autonomi (AS, autonomous system), generalmente composti da gruppi di router posti sotto lo stesso controllo amministrativo. A volte i router e i collegamenti di un ISP formano un unico AS, altri ISP invece preferiscono partizionare la propria rete in più AS. Un AS è identificato da un numero di AS (ASN) assegnato dall'ICANN (proprio come un IP).
   I router facenti parte dello stesso AS usano lo stesso algoritmo di instradamento. L'algoritmo in esecuzione su un AS è detto protocollo di instradamento interno al sistema autonomo (intra-AS routing protocol).

OSPF e il suo stretto parente, IS-IS, sono generalmente impiegati negli ISP di livello superiore. Il termine open indica che le specifiche del protocollo sono pubbliche.
OSPF è un protocollo LS che utilizza il flooding (inondazione) di informazioni riguardo lo stato dei collegamenti e l'algoritmo di Dijkstra per la determinazione del percorso a costo minimo. In OSPF, un router costruisce un grafo dell'intero sistema autonomo e manda in esecuzione (locale) l'algoritmo di Dijkstra per determinare un albero dei percorsi minimi verso tutte le sotto-reti (albero in cui il router stesso rappresenta il nodo radice). I costi dei collegamenti vengono fissati dall'amministratore di rete. L'amministratore di rete può scegliere di impostare i costi di tutti i collegamenti a 1 (ottenendo di conseguenza l'instradamento con il minimo numero di hop), oppure in modo inversamente proporzionale alla capacità del collegamento (al fine di scoraggiare l'uso di collegamenti con poca banda). OSPF non impone una politica sulla scelta dei pesi dei collegamenti (lavoro che compete all'amministratore di rete), ma fornisce invece i meccanismi per determinare l'instradamento con percorso a costo minimo per un dato insieme di pesi dei collegamenti. In OSPF, ogni qualvolta che si verifica un cambiamento nello stato di un collegamento (variazione di costo, o cambiamento di disponibilità), il router manda informazioni di instradamento via broadcast a tutti gli altri ruoter nel sistema autonomo. Inoltre, invia periodicamente lo stato dei collegamenti (almeno, ogni 30 minuti), anche se questo non è cambiato. Gli annunci OSPF sono contenuti in messaggi OSPF che vengono trasportati direttamente da IP come un protocollo di livello superiore con identificativo 89.
OSPF deve implementare il trasferimento affidabile dei messaggi e il broadcast dello stato dei collegamenti. Inoltre, controlla che i collegamenti siano operativi (tramite messaggio HELLO inviato a un vicino connesso) e consente ai router OSPF di accedere ai database sullo stato dei collegamenti della rete, contenuti nei router confinanti.
Tra i vantaggi ricordiamo:

• Sicurezza. Gli scambi tra router OSPF possono essere autenticati; di conseguenza soltanto router fidati possono prendere parte al protocollo OSPF in un sistema autonomo, evitando che malintenzionati immettano informazioni errate nelle tabelle dei router. Di base, OSPF non autentica i pacchetti e potrebbero essere contraffatti. L'autenticazione può essere di due tipi:
  • semplice: la meno sicura, sui router si configura la stessa password che deve essere inclusa, in chiaro, nei pacchetti OSPF ad essi inviati;
  • tramite MD5: si basa su chiavi segrete condivise, configurate in ogni router. Per ogni pacchetto OSPF che mandano, i router calcolano l'hash MD5 del contenuto a cui è stata aggiunta la chiave segreta e includono il risultato nel pacchetto OSPF. Il router ricevente calcola la funzione hash MD5 del pacchetto, usando la chiave segreta pre-configurata, e lo confronta con quello presente nel pacchetto OSPF per verificare l'autenticità. Insieme all'autenticazione MD5 vengono utilizzati anche i numeri di sequenza come protezione contro gli attacchi di ripetizione.
• Percorsi con lo stesso costo. Quando più percorsi hanno lo stesso costo non è necessario sceglierne uno, ma possono anche essere scelti tutti.
• Supporto integrato per l'instradamento unicasti e multicast. Per consentire l'instradamento multicast viene impiegata una semplice estensione di OSPF, MOSPF (multicast OSPF), che utilizza il database dei collegamenti OSPF e aggiunge un nuovo tipo di annuncio sullo stato dei collegamenti al meccanismo di broadcast.
• Supporto alle gerarchie in un dominio di instradamento. Con OSPF è possibile strutturare i sistemi autonomi in modo gerarchico. Un sistema autonomo può essere configurato in aree che eseguono diversi algoritmi di instradamento OSPF: ciascun router in un'area invia lo stato dei suoi collegamenti agli altri router nell'area. In ogni area, uno o più router di confine (area border router) si fa carico dell'instradamento dei pacchetti indirizzati all'esterno. Un'area di un sistema OSPF è configurata per essere l'area dorsale (backbone area), il cui ruolo principale è quello di instradare il traffico tra le altre aree nel sistema autonomo. La dorsale contiene sempre tutti i router di confine del sistema autonomo, ma non necessariamente soltanto quelli. L'instradamento nell'area di un sistema autonomo richiede che i pacchetti siano instradati dapprima verso il proprio router di confine dell'area (instradamento intra-area) e da questi, attraverso la dorsale, al router di confine dell'area di destinazione, che provvede a farli pervenire alla destinazione finale.

Come si vede nella figura sopra, il sistema autonomo è organizzato in modo gerarchico. In questo caso abbiamo 3 aree. La dorsale (backbone) è l'area che consente la comunicazione fra tutte le aree del sistema autonomo. I router delle aree (1, 2 e 3) collegate con la backbone, sono i router di confine dell'area (area border router), mentre quelli all'interno dell'area sono detti router interni. Nella dorsale vi è poi un router connesso con l'esterno che è detto router di confine.

OSPF è un protocollo abbastanza complesso e noi lo abbiamo trattato solo in modo schematico.

Abbiamo appena appreso come gli ISP usino OSPF per determinare percorsi ottimali per le coppie sorgente destinazione all'interno dello stesso sistema autonomo. Ma come vengono determinati i percorsi ottimali tra sorgente e destinazione tra sistemi autonomi. La risposta è BGP (border gateway protocol).

Prima di parlare di come fa un router a scegliere il percorso migliore tra i diversi percorsi che riceve attraverso annunci di raggiungibilità, facciamo una panoramica sulla terminologia BGP.
Quando un router annuncia un prefisso per una sessione BGP, include anche un certo numero di attributi BGP. In gergo, un prefisso assieme ai suoi attributi è detto rotta (route). Due dei più importanti attributi sono AS-PATH e NEXT-HOP.

Il protocollo BGP, oltre a esse il protocollo inter-AS di internet, viene spesso usato per implementare il servizio IP anycast che è comunemente utilizzato in DNS. Per capire l'utilità di anycast si consideri che in molte applicazioni si è interessati a:

1. replicare lo stesso contenuto su server differenti sparsi in diverse aree geografiche;
2. che un utente accede al contenuto dal serve che gli è più vicino.
   Per esempio, una CDN può replicare oggetti sui suoi server in diversi paesi.
   Allo stesso modo, il sistema DNS può replicare i record DNS sui server DNS sparsi in tutto il mondo. Quando un utente vuole accedere ad un contenuto è preferibile che l'utente acceda al server a lui più vicino. L'algoritmo di selezione delle rotte di BGP fornisce un meccanismo semplice e naturale per tale operazione.

Consideriamo un caso concreto di come una CDN possa utilizzare l'anycast IP.

Consideriamo la figura sopra.
Durante la configurazione dell'anycast IP, la CDN assegna lo stesso IP a ognuno dei suoi server e utilizza BGP per annunciare tale indirizzo IP da ognuno dei suoi server.
Quando un router BGP riceve l'annuncio di più percorsi da questo IP, lo tratta come se fossero forniti diversi percorsi verso la stessa area fisica, anche se nella realtà sono percorsi diversi verso luoghi diversi. Ogni router, quando configura la sua tabella di inoltro, utilizza localmente l'algoritmo di selezione dei cammini BGP per scegliere il percorso migliore (per esempio il più vicino in base al conteggio degli hop AS) per quell'IP.
Per esempio, se un cammino BGP, corrispondente a un luogo, è solo un hop AS lontano dal router, e tutti gli altri percorsi BGP corrispondenti ad altri luoghi sono distanti più di un hop AS, il router BGP sceglierebbe di inviare i pacchetti al luogo distante un solo hop AS.
Dopo la fase iniziale di annuncio degli indirizzi BGP, la CDN può dedicarsi alla distribuzione dei contenuti.
Quando un client richiede un video alla CDN, la CDN gli fornisce (indipendentemente dal luogo in cui si trovi effettivamente il client) l'indirizzo IP usato da tutte le CDN. Quando il client inoltra la richiesta a tale IP, i router Internet inoltrano il pacchetto richiesto al server più vicino come definito da BGP.
Tale esempio illustra come le CDN potrebbero usare anycast IP, di fatto, le CDN non lo utilizzano perché cambiamenti nell'instradamento BGP potrebbero portare ad avere sulla stessa connessione TCP pacchetti differenti che arrivano a differenti istanze del server web.

Tuttavia anycast IP è ampiamente usato dai DNS per redirigere la richiesta al server root DNS più vicino.

Quando un router sceglie una rotta, le politiche di instradamento dell'AS possono intervenire facendo saltare qualsiasi altra considerazione riguardante per esempio la brevità del percorso.
Si osservi la seguente figura che illustra dei sistema autonomi:

W, X, Y sono reti stub, ovvero reti che hanno una sola via di uscita, come una rete domestica (esempio molto comune).
A, B, C sono reti di provider di dorsale.
Ipotizziamo che A, B, C siano provider l'uno dell'altro. Tutto il traffico che entra in una rete di accesso di un ISP è destinato a tale rete e tutto il traffico che esce da tale rete è originato in essa.
Esempio: tutto il traffico che entra va da A verso W è destinato a W, mentre tutto il traffico che esce da W ha origine solo in W.
X è è un ISP di accesso multihomed, dato che è connessa a due provider (B, C).
Come W e Y anche X deve essere sorgente o destinazione di tutto il traffico in uscita o in ingresso in attraverso X. Ma come viene implementato è imposto tale comportamento? Come si impedirà a X di smaltire traffico tra B e C? Una risposta risiede nel controllo degli annunci delle rotte BGP.
In particolare, X opererà come rete stub se annuncia ai suoi vicini B e C di non avere percorsi verso altre destinazione se non sé stessa. Anche se X fosse a conoscenza di un percorso XCY, non lo annuncerà a B. In questo modo, B, non inoltrerà mai traffico destinato a Y (né a C) attraverso X.
Consideriamo ora la rete di un provider, per esempio B e supponiamo che questo abbia appreso (da A) che A presenta un percorso AW verso W. Allora B può installare il percorso BAW nella sua struttura dati per l'instradamento. Chiaramente B vuole annunciare il percorso BAW anche al suo cliente X, per permettergli di raggiungere W tramite B.
Ma dovrebbe annunciarlo anche a C? In questo modo C potrebbe instradare anche attraverso B verso W con il percorso CBAW.
B, di suo, potrebbe pensare, giustamente, di non dover prendersi carico di tutto il peso (e costo) del traffico in transito tra A e C e che dovrebbe essere compito di A e C assicurarsi che C possa instradare da e verso i clienti di A tramite una connessione diretta tra A e C. Attualmente non esistono standard ufficiali per gestire l'instradamento reciproco degli ISP di dorsale. Una regola pratica seguita dagli ISP commerciali è quella per cui tutto il traffico che fluisce attraverso la rete di dorsale di un ISP deve avere origine e/o destinazione in una sua rete cliente. Accordi individuali di peering (e confidenziali) vengono negoziati tra coppie di ISP.