I router in Internet non sono dislocati a caso. Sono raggruppati sotto AS. Ogni AS gestisce una fetta in indirizzi IP -> network prefix
Ogni AS è identificato univocamente da un numero identificativo chiamato ASN - Autonomous System Number.
Inizialmente definito su 2 byte -> con il crescere di Internet non sufficienti -> 4 byte
Ogni AS controlla in modo esclusivo uno o più network prefix (eg:
120.240.0.0/16)
#Nota: nessun AS gestisce più del 5% del traffico -> no oligopoli o monopoli
Gli ISP nazionali o internazionali sono connessi tra loro al più alto livello mediante protocolli peering point, che mettono in comunicazione AS privati e di piccole dimensioni, o mediante IXP Internet Exchange Point, chiamati anche NAP - Network Access Point.
Rifrasato: i NAP o IXP sono infrastrutture che mettono in comunicazione più AS. Solitamente interi edifici. Sono l'equivalente (su scala diversa) delle cabine telefoniche per gli utenti privati.
Tipi di rapporti (POV gestionale/economico):
- Transit - punto di transito - che offre un servizio a pagamento. Le due parti sono AS sell e AS pay.
- Peering (o swap) - da qua peering point -: due AS si scambiano il traffico dei rispettivi utenti senza costi, per interesse reciproco.
Differenza: nel primo caso ci sono tanti AS messi in comunicazione. Nel secondo caso sono un numero esiguo, solitamente 2.
I protocolli di routing non sono guidati solamente da scelte tecniche, ma anche da interessi economici.
#Nota: inoltrare il traffico su Internet è prima di tutto un problema di inoltro del traffico tra AS. A questo livello router, indirizzi IP e simili sono oscurati dalla dimensione organizzativa degli AS. Ci interessa descrivere il percorso di un pacchetto in termini di hop tra AS numbers.
Sono tipicamente consorzi indipendenti senza scopo di lucro -> entità legale che gestisce l'IXP Finanziati pubblicamente. Si concretizza come struttura (datacenter) dalle grandi dimensioni. Spesso costruiti in aree metropolitane: MAE - Metropolitan Area Exchange
Es:
- NAMEX - Rome Internet Exchange Point
- MIX - Milan Internet Exchange Point
#Ricorda miscellaneo #Ricorda RIPE è l'organizzazione che ha in gestione gli indirizzi IP d'Europa
UniMo ha in gestione il blocco di indirizzi 155.185.0.0/16 assegnatogli dal GARR, che a sua volta lo ha avuto in concessione dal GARR. Il GARR è quindi l'AS (AS137), che possiede il blocco di indirizzi e ha il diritto di riassegnarli staticamente (come nel caso dell'uni) o dinamicamente (come nel caso di TIM) ad altre entità.
Informazioni sul blocco di indirizzi: https://apps.db.ripe.net/db-web-ui/query?searchtext=155.185.0.0 Visualizzazione di AS137: https://stat.ripe.net/widget/bgplay#w.resource=AS137
Tipi di rapporti:
- Stub: AS con una sola connessione ad un altro AS
- Multi-homed: AS connesso con diversi ASxxx che non permette traffico non generato o diretto verso l'AS
- Transit: AS connesso a diversi ASxxx che consente il passaggi di traffico tra gli ASxxx attraverso di lui #Grafico
#Nota il termine stub è utilizzato per indicare "appendici"
Obiettivo comune: dato un grafo che modella una rete, determinare il cammino ottimale e il costo minimo del percorso.
Un protocollo di routing è un protocollo che permette di popolare dinamicamente una tabella di routing comprendendo la topologia della rete e dei costi di ogni hop.
O exterior routing
Tra diversi AS si usa il BGP - Border Gateway Protocol, un protocollo di routing distribuito
In un contesto di exterior routing i nodi del grafo sono AS/ASN.
O interior routing
Tra nodi appartenenti alla stesso AS si usano: RIP - Routing Information Protocol, OSPF - Open Shortest Path First, EIGRP - Enhanced Interior Gateway Routing Protocol
Nonostante esistano diversi protocolli open e proprietari, pubblici e privati, custom o standard. In un contesto di interior routing i nodi del grafo sono router/ISP all'interno dell'AS.
A livello protocollare Internet può essere pensata come un'architettura a 2 livelli.
#Ricorda gli AS sono entità completamente connesse: comunicando tra due nodi interni all'AS, non deve uscire traffico dall'AS, altrimenti non si tratta di un unico AS. Viene contenuto tutto internamente.
Per uscire da un AS un pacchetto deve raggiungere il router di bordo (border gateway)
Esistono due classi di algoritmi di routing:
- globale: ogni nodo offre a tutti gli altri la sua visione della rete -> tutti i nodi conoscono la struttura di tuta la rete. Link state protocol
- locale (distribuito): conoscenza parziale della rete. Distance-vector routing protocol
Gli algoritmi LS - Link State - sono globali: prevedono che la topologia di rete e i costi di ogni link siano noti a tutti i nodi della rete. Concettualmente abbiamo una procedura ciclica:
- ogni nodo conosce i link ad esso connessi
- ogni nodo tramette periodicamente l'identità e il costo dei link conosciuti a tutta la rete
- Forward search algorithm. Un algoritmo come quello di Dijkstra, che ha una visione completa della rete, trova la shortest path verso ogni destinazione e crea la tabella di routing.
Pacchetti LSP - Link State Protocol: vengono periodicamente inviati in broadcast su tutti i link del nodo, contenenti le seguenti informazioni:
- node ID
- lista dei vicini e costo dei rispettivi link
- info supplementari
- numero di sequenza per identificare out of order delivery, si possono scartare pacchetti che arrivano dopo il dovuto.
- TTL per evitare di usare informazioni vecchie. Quando scade il protocollo.
Flooding = inondazione Quando il nodo i riceve un pacchetto LSP da un nodo j:
- se il pacchetto LSP è valido
- salva il valore nella tabella di routing
- inoltra una copia del pacchetto inviato da j su tutti i suoi link
- altrimenti scarta il pacchetto Il costo cresce quadraticamente con la dimensione della rete.
Ogni nodo esegue l'algoritmo di Dijkstra in locale e ottiene la stessa tabella di routing di tutti gli altri nodi. Pre-condizioni: conoscenza della rete e dei costi completa, informazioni affidabili ricevute dall'algoritmo di flooding.
Caratteristiche:
- algo iterativo
- asincrono. Ogni nodo si comporta in modo disaccoppiato dagli altri.
- non adatto a reti che cambiano dinamicamente il proprio stato.
I nodi della rete si cambiano vettori di distanze (ovvero di costi).
È basato su informazioni locali, non globali.
Ogni nodo conosce i propri vicini e i costi dei rispettivi link. Trasmette questa informazione ai suoi vicini. Costo lineare nel numero di nodi della rete.
Ogni nodo riceve il vettore dei costi dai suoi vicini. Le destinazioni non note vengono ricavate dai vettori ricevuti. È ovviamente necessario sommare al costo per uno specifico nodo, ricevuto in un vettore, quello per raggiungere il nodo da cui lo si ha ricevuto.
#Nota possono servire più iterazioni per arrivare a convergenza e trovare il costo minimo per ogni destinazione. Ogni costo viene sostituito con uno migliore se trovato. #Todo diagramma
La rete Internet può cambiare, di conseguenza viaria come viene calcolato il percorso minimo.
Nei protocolli globali non ci sono problemi: una nuova topologia comporta flooding e un ricalcolo dei percorsi.
Posso decidere di aggregare delle destinazioni. #Completa
O Effetto rimbalzo
Ho una topologia molto semplice: tre nodi connessi a triangolo. Immagina che in un dato istante un link vada molto lento rispetto a prima (praticamente immagina che si rompa).
Prendi il nodo non coinvolto con la rottura del link. Questo nodo è convinto che per raggiungere A possa passare attraverso un link dal costo di 2.
Diffondere informazioni localmente induce un naturale errore di propagazione.
L'effetto rimbalzo avviene in quanto nei vettori di distanza sono inclusi solo i costi ottimi, ma non il percorso con cui un nodo può essere raggiunto.
Si forma un ciclo su un segmento della rete, ovvero tra C e B: due nodi continuano a scambiarsi continuamente un pacchetto senza farlo uscire dal segmento.
Come risolvere?
- si può arrivare a convergenza, su un ciclo è diretto, aspettando che il costo di passaggio attraverso un nodo salga e superi il nuovo costo del link rotto
- link completamente inagibile: count to infinity -> se il costo diventa infinito perché il link non è assolutamente attraversabile. Non converge mai - o meglio - converge in tempi infiniti.
Soluzioni al count-to-infinity?
- scegliere una soglia (bassa) per rappresentare l'infinito. Ad esempio un numero massimo di hop può essere considerato 16. Ogni hop con costo costante 1.
- split horizon: se un nodo A sa che per raggiungere una destinazione deve passare per un nodo B, non comunica al nodo B questa informazione, viene depennata dal distance vector.
#Migliorie usare un protocollo path-vector. Ogni nodo non si salva soltanto il next hop dal costo minimo, ma tutto il percorso da seguire. Serve ad evitare cicli: un nodo può rilevarsi all'interno di un path -> rileva il ciclo. Aumenta il costo di trasmettere un interno percorso sulla rete.
Basato su distance vector Metrica di costo semplificata = numero di hop. Tutti i link hanno costo unitario. Costo massimo (rappresentazione inf) = 16
Sceglierà sempre i link diretti verso i suoi vicini
Tipi di pacchetti:
- RIP advertisement: vettore dei costi. Logica push
- RIP request. Logica pull, utile quando un router viene appena connesso alla rete.
Link failure: se un router non riceve messaggi dal suo vicino dopo 180 secondi lo considera irraggiungibile.
Adatto a reti di piccole dimensioni che cambiano lentamente nel tempo.
Algoritmo centralizzato link state
Caratteristiche aggiuntive:
- sicurezza - possibilità di autenticare i messaggi OSPF
- percorsi multipli con costo uguale
- ecc.
In contesti decentralizzati è difficile mantenere la sicurezza della rete conoscendo gli attori ecc.
L'area sulla quale OSPF è eseguito varia ed è definibile in base alla struttura della rete e a preferenze.
Protocollo decentralizzato (distribuito) che estende la logica di RIP con i percorsi -> path vector
Tra AS non è possibile mandare messaggi in broadcast. RIP è un protocollo pensato per reti piccole.
Peculiarità: è in grado di determinare i percorsi migliori anche in base a policy di routing. I rapporti tra AS sono regolati anche da regole contrattuali, non solo tecniche. Le policy possono essere economiche, gestionali o politiche; si integrano con le metriche prettamente tecniche.
Si individuano due categorie di router:
- transit router -> I-BGP Interior BGP
- border router -> E-BGP Exterior BGP
La versione Exterior si usa per comunicare tra AS differenti; la versione Interior si usa per diffondere (annunciare) informazioni di raggiungibilità tra router dello stesso AS.
Gli AS si scambiano prefissi
#Vedi BGP toolkit su Moodle
BGP identifica due categorie di router: i border router, che si trovano al confine tra due AS e i transit router, ovvero router interni all'AS. Queste due tipologie di router devono ovviamente comunicare tra loro.
Internet è un insieme di AS, identificati da un ASN; ogni AS conosce i propri vicini e il costo (espresso in diverse misure) per raggiungerli, oltre agli accordi che regolano le comunicazioni.
Il protocollo BGP prevede che ogni AS annunci il proprio prefisso, ovvero il range di indirizzi di propria competenza, ai propri vicini.
Quando un pacchetto arriva a un router, se la dst è un vicino, finito, altrimenti si usano i path vector comunicati dai vicini per inoltrare il pacchetto a destinazione.
#Vedi: https://radar.cloudflare.com Un AS può pubblicizzare un percorso falso (inondare la rete con regole di routing false) -> possibile con protocolli decentralizzati.
Vengono messe a disposizione delle sonde (probe)
#Vedi https://bgp.he.net traceroute di AS137