iconNotes in Public

OSPF e LS - Routing Protocol Intra-Domino

5 min read

Introduzione

Questo protocollo è basato sull’idea di Link State, ovvero il costo associato al link (collegamento), in particolare:

  • indica un collegamento inesistente o interrotto
  • Ogni nodo deve conoscere i costi di tutti i collegamenti della rete

Per la memorizzazione di queste informazioni è utilizzato un Link State Database (LSDB).

oss: è un alternativa al distance vector (DC) utilizzato in RIP.

Il link state database mantiene la mappa completa della rete, ogni nodo ne mantiene una copia e deve essere univoco (uguale) tra tutti i nodi della rete.

Rappresentazione

É rappresentato attraverso una matrice dove M[x][y]contiene il costo del collegamento tra il nodo x e il nodo y.

Creazione (flooding)

Ogni nodo della rete deve innanzitutto conoscere i propri vicini e i costi dei collegamenti verso di loro, per fare ciò:

  • ogni nodo invia un messaggio di hello a tutti i suoi vicini.
  • ogni nodo riceve gli hello dei vicini e crea la lista dei vicini chiamata LS Packet (LSP) contenente tuple (vicino, costo).

Ogni nodo esegue un flooding, ovvero:

  • Invia a tutti i vicini il proprio LSP.
  • Quando riceve LSP da un vicino, se è nuovo allora, aggiorna il suo LSP e lo inoltra a tutti suoi vicini, eccetto quello da cui lo ha ricevuto.
  • In questo modo aggiorniamo tutta la rete.

Una volta terminato questo processo abbiamo costruito l’LSDB.

Per costruire il suo albero a costo minimo utilizzando il LSDB ogni nodo deve eseguire l’algoritmo di Dijkstra, in modo indipendente, scegliendo se stesso come nodo radice.

Definiamo la seguente notazione:

  • : insieme di nodi della rete.
  • : costo collegamento dal nodo x al nodo y.
  • : costo del cammino minimo dal nodo origine alla destinazione v (nel iterazione corrente).
  • : immediato predecessore del nodo v lungo il cammino minimo.
  • : sottoinsieme dei nodi per cui il cammino a costo minimo dall’origine è definitivamente noto.

Inizializzazione

Prima di utilizzare l’algoritmo di Dijkstra, dobbiamo inizializzare il sottoinsieme di nodi adiacenti alla radice:

N' = {r}
for all nodi n in N:
  se n è adiacente a r
  	allora D(n) = c(r,n)
  altrimenti D(n) = inf

Ciclo

Una volta inizializzato il sottoinsieme con i nodi adiacenti alla radice, possiamo far partire il ciclo:

determina un `n` non in N' tale che D(n) sia minimo

aggiungi `n` a N'

per ogni nodo `a` adiacente a `n` e non in N' aggiorna D(a):
  D(a) = min(D(a), D(n) + c(n, a))
Termina quando N' = N

Possiamo applicare Dijkstra per risolvere esercizi in modo “grafico”:

Quindi ad ogni step aggiorniamo i costi per ogni nodo e allo step successivo aggiungiamo in N' il nodo con costo minimo.

Al termine della procedura otteniamo, l’albero dei percorsi minimi che collega il nodo radice a tutti i nodi della rete.

Confronto tra algoritmi LS e DV

Complessità

Con algoritmi LS se abbiamo n ed E collegati implica l’invio di O(nE) messaggi.

Con un algoritmo DV è richiesto lo scambio di informazioni soltanto tra i nodi adiacenti, e quindi il tempo di convergenza è potenzialmente più basso, ma può variare.

Velocità di convergenza

Con algoritmi LS abbiamo complessità di , dato che procede prima n nodi, poi n-1, n-2, etc , quindi n(n+1)/2.

Con algoritmi DV abbiamo una convergenza più lenta, dato che:

  • può presentare cicli d’instradamento
  • può presentare il problema del conteggio all’infinito (lo scambio di aggiornamenti infinito)

Robustezza

In generale l’OSPF (LS) è più robusto di RIP (DV), infatti cosa succede se un router funziona male?

Con OSPF che si basa su LS, se un router comunica a tutti un costo sbagliato per uno dei suoi collegamenti non compromette l’intera rete dato che ogni nodo calcola la tabella localmente.

Com RIP che si basa su DV, se un router comunica cammini errati significa che questa informazioni si diffonde su tutta la rete portando a calcoli errati.

Approfondimento Protocollo OSPF (Open Shortest Path First)

Fino ad ora abbiamo visto un algoritmo, ma un protocollo è composto da molto altro, infatti deve definire

  • il suo ambito di funzionamento
  • i messaggi che vengono scambiati
  • la comunicazione tra router
  • l’interazione con gli altri protocolli.

In particolare vediamo il protocollo OSPF (Open Shortest Path First) basato su Algoritmo Link State (LS).

Nota: si dice open perché le sue specifiche sono pubblicamente disponibili.

Questo è un protocollo a stato del collegamento, ovvero:

  • Utilizza il flooding di informazioni di stato del collegamento.
  • Utilizza Dijkstra (algoritmo LS) per la determinazione del percorso a costo minimo.

Flooding in OSPF

Nel OSPF, ogni volta che si verifica un cambiamento nello stato di un collegamento, il router manda informazioni d’instradamento a tutti gli altri router, utilizzando la tecnica del flooding.

Invia periodicamente (ogni 30 minuti) messaggi OSPF all’intero sistema autonomo, utilizzando il flooding.

Messaggi OSPF

  • Hello - Usato dai router per annunciare la loro esistenza ai vicini

  • Database Description - Risposta ad hello, di solito per inviare il LSDB ai nuovi router

  • Link State Request - Usato per richiedere specifiche informazioni su un collegamento

  • Link State Update - Messaggio principale usato da OSPF per la costruzione del LSDB

  • Link State ACK - Riscontro al link state update (offre più affidabilità)

Nota: I messaggi OSPF vengono trasportati direttamente in datagrammi IP usando il numero di protocollo 89 nel campo IP protocol.

Graph View

Backlinks