Algoritmi di Instradamento Flashcards
Routing con Dijkstra, Bellman-Ford, OSPF, RIP, BGP
- Qual è l’obiettivo degli algoritmi di instradamento?
Determinare percorsi a costo minimo da mitt a dest.
Sempre avere sequenza ben definita (sia che piano controllo sia distribuito o centralizzato)
- Come si modella una rete?
Come grafo G=(V,E)
Ogni arco ha un costo (velocità, lunghezza o prezzo…) che è infinito se irraggiungibile
- Quali sono i tipi di algoritmi?
- Centralizzato: visione completa della rete (link-state) di cui conoscono tutti i collegamenti e costi. Riceve questi dati prima di essere eseguito
- Decentralizzato: inizialmente nodo conosce solo vicini. Ad iterazioni successive scambia distance-vector con loro e viceversa.
- Come si suddividono algoritmi in proattivi, reattivi e flooding?
- Proattivi: creano tabelle di routing sia se c’è comunicazione o no
- Reattivi: non fanno niente a meno di comunicazione pendente
- flooding: i dati vengono inviati a tutti
- Qual è la differenza tra algoritmi statici e dinamici?
statici cambiano poco, dinamici variano in base a traffico (vulnerabili a routing loop)
- Come si comportano generalmente con il carico?
Pacchetto salta avanti e indietro tra più router senza arrivare a destinazione.
Causato da più soluzioni che agiscono in contemporanea
- Come si ottengono dati in input per gli algoritmi link-state?
Ogni nodo invia identità e costo dei collegamenti
OSPF fa flooding
- Come è definito l’algoritmo di Djikstra?
Inizializzazione: dato nodo di origine, metto i vicini a costo rispettivo
Passo successivo: fino a quando non ho visitato tutti i nodi trovo il nodo più vicino (aggiungo a quelli visitati) e vedo se da lui c’è percorso più veloce di quello che ho
Complessità O(n^2)
- Quali problemi può avere l’algoritmo di Dijkstra?
Problemi di oscillazione se i percorsi vengono aggiornati in base alla congestione sul momento.
Evitare che tutti i router eseguano simultaneamente, così rete può stabilizzarsi.
Router tendono a sincronizzarsi (sol=tempo randomico)
- Quali sono le caratteristiche principali del Distance-Vector?
- iterativo: si ripete fino a quando non avvengono piu scambi
- asincrono: non richiede che nodi operino in modo sincronizzato
- distribuiti: ogni nodo riceve info da nodi vicini
- Quali caratteristiche ha l’algoritmo di Bellman-Ford?
Periodicamente invia proprio vettore delle distanze.
Quello proprio viene aggiornato con Dx(y)=min_v(c(x,v)+Dv(y))
12a. Algoritmo di Bellman-Ford?
Inizializzazione: vicini con rispettivo costo, infinito altrimenti
Per ogni vicino, leggo il Distance vector e invio il mio
Fino a quando non si verifica cambiamento di costo
- per ogni destinazione calcolo il minimo
- se il mio Dv è cambiato reinvio
- Cosa succede se il costo cambia troppo velocemente?
La rete non si e1 stabilizzata con nuove info quindi si rischia loop.
Vecchie tratte non vengono aggiornate con le nuove distanze (richiede tempo da parte dei vicini)
- A cosa serve la poisoned reverse?
X→Z→Y
se cambia costo XY ma non si aggiorna
Z instrada verso X passando da Y (Z→Y→X) informa Y che distanza X è infinita (così NOT Y→Z→X)
Risolve il problema dei cicli nei nodi adiacenti ma non risolve cicli più complessi
- Quali sono le differenze tra LS e DV?
- DV comunica con nodi adiacenti, LS con tutti
- DV scambia messaggi solo con vicini, LS richiede che ogni nodo conosca tutta la rete → O(|N||E|) messaggi
- LS è più rapido, DV più lento e ci possono essere cicli
- LS è robusto, errori non si diffondono facilmente, DV errore può propagarsi velocemente
- Perchè non si può rappresentare internet come semplice collezione di router? Cosa sono AS?
Troppi router → Calcolare e comunicare instradamento troppo dispendioso
Internet è fatta da ISP che si gestiscono autonomamente
AS gruppi di router sotto unico controllo amministrativo
- Cosa è OSPF?
Open Shortest Path First (Intra-AS)
Usa Flooding di informazioni. Costi fissati a priori (=1→costo=#hop)
per Ipv4 e Ipv6(con autenticazione, bilanciamento del carico e gerarchia dei domini)
Gestisce casi in cui percorsi a stessa dest abbiamo pesi diversi (visione completa, posso splittare traffico)
- Perchè si introducono gradi di gerarchia?
AS grande
Garantiscono scalabilità alla struttura
- Come vengono definiti i costi?
basati su Hop o capacità collegamento.
annunci contenuti in IP (protocollo 89)
- Quali sono le caratteristiche di sicurezza?
Scambi possono essere autenticati (password condivisa, MD5)
Supporta percorsi multipli
- Cosa è BGP?
Border Gateway Protocol
EGP (Inter ES) ma può essere usato anche intra-as (iBGP)
- Ottiene info sulla raggiungibilità dei prefissi di sottorete dai prefissi confinanti
- Determina percorsi ottimali verso sottoreti
- Propaga le info
- Come si propaga informazione?
Ogni router è sia gateway che router interno
Router vuole annunciare prefisso di rete → invia BGP (ASy x) al router di confine
router di confine invia a tutti quelli interni, invia ASz ASy x all’altro router di confine
In questo modo tutti i router conoscono il percorso per raggiungerli
- Quali sono le alternative al BGP?
AODV, DSR → MANET (Mobile Ad-hoc NETwork) dove tutti i nodi appartengono a stesso prefisso
Tutti hanno stesso meccanismo (router comunicano con vicino con messaggi di hello)
- Come funziona RIP?
Intra-as
Limite massimo di Hop = 15 → limita il diametro della rete di RIP
Ogni 30 secondi, ogni router invia tabella di routing a vicini.
Usa UDP (520), comodo
