Routing Flashcards
Qual è la corrispondenza tra rete e grafi
Gli algoritmi per la gestione di una rete sono basati sulla teoria dei grafi
nodi=router
archi=link fisici
ogni link ha un costo determinato da vari fattori
La scelta del cammino va fatta in base al costo minimo
Quali sono i parametri per scegliere quale percorso è più vantaggioso
*Bandwidth: capacità di un link, tipicamente definita in bit per secondo (bps)
*Delay: il tempo necessario per spedire un pacchetto da una sorgente ad una destinazione
*Load: una misura del carico di un link
*Reliability: riferita, ad esempio, all’error rate di un link
*Hop count: il numero di router da attraversare nel percorso dalla sorgente alla destinazione
*Cost: un valore arbitrario che definisce il costo di un link
Qual è la funzione principale di un router
La funzione principale di un router è quella di determinare i percorsi che i pacchetti devono seguire per arrivare a destinazione, partendo da una data sorgente
Quali sono le tecniche di routing
Routing by Network Address: ogni pacchetto contiene l’indirizzo del nodo destinatario, che viene usato come chiave di accesso alle tabelle di instradamento
Label Swapping: ogni pacchetto è marcato con una label (etichetta) che identifica la connessione e viene usata come chiave per determinare l’instradamento
Differenza del routing nelle reti a circuito virtuale e nelle reti a datagramma
Reti a circuito virtuale: Viene aperta una connessione prima di inviare dati
Reti a datagramma: I pacchetti sono indirizzati usando un ID di destinazione
Differenza tra routing centralizzato e routing distribuito
Routing centralizzato: Esiste un nodo centrale che calcola e distribuisce le tabelle. Ottimizza le prestazioni, ma è poco robusto
Routing Distribuito: Ogni router calcola le sue tabelle dialogando con gli altri router tramite dei protocolli ausiliari, utilizzando principalmente due algoritmi, distance vector e link state
Come possono scambiarsi informazioni i router per rimanere aggiornati sullo stato della rete
Broadcast periodico: i router possono trasmettere agli altri router informazioni circa la raggiungibilità delle reti (destinazioni) di propria competenza ad intervalli regolari di tempo->inefficiente perché gli scambi avvengono anche in presenza di nessun cambio
Event-driven: gli update sono inviati solo quando è cambiato qualcosa nella topologia oppure nello stato della rete->più efficiente
Quali sono i parametri per garantire l’efficienza di un algoritmo di routing
Semplicità
Robustezza
Stabilità
Equità
Metrica da Adottare
Come funziona l’algoritmo Distance Vector
Ogni router mantiene una tabella di tutti gli instradamenti a lui noti
Ogni entry della tabella indica:
* una rete raggiungibile
* il next hop
* il numero di hop necessari per raggiungere la destinazione
Periodicamente, ogni router invia a tutti i vicini un messaggio di aggiornamento contenente tutte le informazioni della propria tabella.
I router che ricevono tale messaggio aggiornano la propria tabella
Come funziona l’algoritmo Link State
Utilizza l’algoritmo Shortest Path First, non basato sullo scambio delle tabelle e ogni router conosce la topologia della rete.
Ogni router esegue due azioni:
* controlla lo stato di tutti i router vicini
* periodicamente invia, in broadcast, un messaggio contenente lo stato dei link a cui è collegato
I router utilizzano i messaggi ricevuti per aggiornare la loro mappa della rete
Cos’è l’algoritmo di DIjkstra
Ogni nodo usa l’algoritmo di Dijkstra per costruire lo Spanning Tree del grafo, ovvero l’albero dei cammini di costo minimo
Cos’è un Autonomous System
Internet è strutturata come un insieme di Autonomous System, una collezione di reti amministrate da un’unica autorità. Ogni AS contiene un numero limitato di reti
Ogni AS è responsabile del routing all’interno delle sue reti (routing interno) e devono scambiarsi informazioni di raggiungibilità (routing esterno)
Da chi sono mantenute le tabelle di routing interne ed esterne
Le tabelle di routing interne di un AS sono mantenute dall’Interior Gateway Protocol (IGP)
Le tabelle di routing esterne di un AS sono mantenute dall’Exterior Gateway Protocol
Cosa sono i gateway router
Sono speciali router dell’AS, che eseguono protocolli di routing intra-AS con altri router appartenenti all’AS
Sono, inoltre, responsabili del routing verso destinazioni esterne al proprio AS
Quanti tipi di AS esistono
Un solo border router:
* stub o single-homed
Più border router:
* multi-homed:
* transit (provider)
(accetta di essere attraversato da traffico diretto ad altri AS)
*non-transit (grandi corporate)
(non accetta di essere attraversato da traffico diretto ad altri AS)
