Riassunto intero programma Fondamenti di reti di telecomunicazioni

Algoritmo di Dijkstra

L'algoritmo di Dijkstra individua il cammino a lunghezza minima tra un nodo s e tutti gli altri nodi di un grafo G procedendo in modo da aumentare progressivamente la distanza.

L'algoritmo procede a passi successivi:

• Al passo k-esimo sono individuati i k nodi raggiungibili dal nodo sorgente tramite i cammini a costo minimo.
• Tali k nodi formano l'insieme T.
• Al passo k+1-esimo è aggiunto un ulteriore nodo all'insieme T caratterizzato dal cammino a costo minimo dal nodo s che transita esclusivamente nei nodi dell'insieme T.
• L'algoritmo termina quando si sono esplorati tutti i nodi, |T|=N^2.

La complessità dell'algoritmo è O(N).

Algoritmo di Bellman-Ford

L'algoritmo di Bellman-Ford individua il cammino a una lunghezza minima tra un nodo s e tutti gli altri nodi di un grafo G aumentando progressivamente il numero di rami.

L'algoritmo procede a passi:

• Al primo passo individua i cammini minimi tra il nodo s e tutti gli altri nodi.

nodo sorgente e gli altri nodi con il vincolo che icammini contengano al più 1 ramo.- al secondo passo si trovano i cammini minimi tra il nodo sorgente e gli altri nodi con il vincolo che icammini contengano al più 2 rami- si itera il procedimento sino al valore massimo di rami possibili di un cammino

Al termine dell’algoritmo si individua uno spanning tree del grafo di partenza che contiene i cammini acosto minimo tra il nodo sorgente e tutti gli altri nodi. 2 3

La complessità dell’algoritmo è O(|N|*|archi|) ossia nel peggiore dei casi con |archi|=|N| si ha O(N )

BELLMAN-FORD vs DIJKSTRA

I due algoritmi convergono (in condizioni statiche di topologia e costo dei link) alla stessa soluzione.

L’algoritmo di Belman-Ford nel caso peggiore è più complesso, ma in molti casi pratici gli algoritmi siequivalgono.

L’algoritmo di Dijkstra richiede un nodo conosca l’intera topologia della rete e il peso di tutti i rami

>c’è quindi necessità di un colloquio tra tutti i nodi

L’algoritmo di Bellman-Ford richiede la conoscenza dello stato dei rami uscenti da un nodo insieme alle informazioni provenienti dai nodi vicini -> necessità di colloquio solo tra nodi adiacenti.

INTERIOR GATEWAY PROTOCOLS (IGP)

GGP , SPREAD , SPF , OSPF, RIP, HELLO

Il modo in cui i protocolli IGP determinano le tabelle di instradamento può essere vario ed utilizzare svariati algoritmi ognuno dei quali ha i suoi pro e contro

La maggior parte dei protocolli IGP si basa su due classi di filosofie di routing: 20

DISTANCE-VECTOR ROUTING:

• si basa sull’algoritmo di Bellman-Ford.
• più semplice.
• impegna meno risorse sul router.
• meno efficiente.
• adatto a reti piccole

LINK-STATE ROUTING:

• si basa sull’algoritmo di Dijkstra.
• molto più complesso.
• molto più efficiente.
• impegna più risorse.
• adatto a reti più grandi

1. VECTORI protocolli della classe Distance Vector (DV) si basano sull'algoritmo i Bellman-Ford distribuito.
2. Facciamo l'ipotesi di un funzionamento sincrono di tutti i nodi della rete, quindi ogni nodo potrebbe eseguire le operazioni di Bellman-Ford in modo sincrono a tutti gli altri nodi. La procedura terminerebbe in al più N operazioni.
3. Il problema è che la condizione di sincronia tra i nodi è difficilmente raggiungibile.
4. I protocolli Distance Vector utilizzano la versione asincrona dell'algoritmo di B.F.
5. L'algoritmo di Bellman-Ford distribuito converge a soluzione se la dinamica delle variazioni è più lenta della velocità di convergenza dell'algoritmo.
6. C'è la possibilità di "Bad News Phenomenon" cioè variazioni particolari per cui la convergenza è molto lenta e quindi il numero di iterazioni può essere molto elevato.
7. Ogni router mantiene, oltre alla tabella di instradamento,

una struttura dati, detta distance vector, perogni sua linea attiva.

Il distance vector contiene informazioni ricvavate dalle tabelle di instradamento dei router collegatiall’estremo della linea.

Il distance vector è un insieme di coppie (indirizzo-distanza).

Il calcolo delle tabelle di routing avviene tramite la fusione (merge) di tutti i distance vector associatialle linee attive di un router.

Tutte le volte che un router modifica la sua tabella di routing, la invia ai router adiacenti sotto forma didistance vector.

Ciascun router apprende tramite un protocollo di neighbor greetings le informazioni relative i nodiadiacenti.

Quando un router memorizza un distance vector nella sua struttura dati locale, verifica se sono presentivariazioni rispetto al distance vector precedentemente memorizzato: in caso affermativo ricalcola letabelle di instradamento fondendo tutti i distance vector delle linee attive.

I passi del funzionamento del Distance Vector sono:

1. Quando riceve un

messaggio (distance vector) da un router adiacente confronta ogni coppia(destinazione, costo) col contenuto della sua tabella di routing. Se la destinazione non è in tabella allora crea una nuova entry per la nuova destinazione. Se la destinazione è in tabella e il next hop è il router adiacente che ha fatto l'annuncio allora aggiorna il costo ed il next hop nella entry. Se la destinazione è nella tabella e il costo indica un percorso migliore, allora aggiorna il costo e il next hop nella entry.

Ad intervalli regolari trasmette ai router adiacenti un messaggio (distance vector) che riporta tutte le coppie (destinazione, costo) contenute nella tabella di routing. Ogni nodo applica l'algoritmo di Bellman-Ford in modo distribuito. Periodicamente (circa 30 s) ogni nodo scambia il suo distance vector con quelli dei nodi vicini.

LINK STATE

Un protocollo di tipo Link State (LS) assume che ogni router dispone della mappa completa della rete su cui calcolare gli

a ogni router per calcolare gli instradamenti ottimali utilizzando l'algoritmo di Dijkstra. L'algoritmo di Dijkstra è un algoritmo di ricerca del percorso più breve utilizzato per determinare il percorso ottimale tra due nodi in un grafo pesato. In questo caso, il grafo rappresenta la rete di router e i pesi dei link rappresentano i costi associati a ciascun link. Per utilizzare l'algoritmo di Dijkstra, ogni router utilizza il suo LSP database per costruire una mappa della rete con i costi associati. Questa mappa logica della rete viene utilizzata per determinare il percorso ottimale tra due nodi. L'algoritmo di Dijkstra funziona nel seguente modo: 1. Inizializzare tutti i nodi con un costo infinito, tranne il nodo di partenza che viene inizializzato con un costo di 0. 2. Selezionare il nodo con il costo minimo tra quelli non ancora visitati. 3. Per ogni nodo adiacente al nodo corrente, calcolare il costo totale per raggiungere quel nodo sommando il costo del link tra i due nodi al costo del nodo corrente. 4. Se il costo totale per raggiungere un nodo adiacente è inferiore al costo attuale associato a quel nodo, aggiornare il costo associato a quel nodo. 5. Segnare il nodo corrente come visitato. 6. Ripetere i passaggi 2-5 fino a quando tutti i nodi sono stati visitati o fino a quando il nodo di destinazione è stato visitato. 7. Il percorso ottimale tra il nodo di partenza e il nodo di destinazione può essere determinato seguendo i collegamenti con i costi minimi tra i nodi visitati. Utilizzando l'algoritmo di Dijkstra e la mappa logica della rete costruita dai router tramite LSP, ogni router può determinare gli instradamenti ottimali per inviare i pacchetti di dati attraverso la rete.

affinché il router calcoli le sue tabelle di instradamento. Ogni router calcola la sua tabella di instradamento, indipendentemente dagli altri router, applicando alla mappa della rete l'algoritmo di Dijkstra, che trasforma una rete magliata in un albero scegliendo i percorsi a più basso costo e in cui la radice è il router che sta applicando l'algoritmo. Da questo albero vengono estratte per ogni destinazione il next-hop e il costo totale del percorso. Si noti la differenza tra il Link state e il distance vector: Nel distance vector i router cooperano per calcolare le tabelle di instradamento, qui i router cooperano per mantenere aggiornata la mappa di rete, poi ogni router calcola la propria tabella di instradamento in modo autonomo. Un aspetto critico dei protocolli del tipo Link State è la sincronizzazione tra i router. Se i router hanno diversi LSP database, allora sono disponibili dei loop. Il LSP è trasmesso in flooding su tutti i link del router.

Il flooding è stato pensato per assicurare la più rapida diffusione e l'aggiornamento di eventuali variazioni di topologia. DISTANCE VECTOR vs LINK STATE DISTANCE VECTOR:

• Ogni router invia le informazioni di routing ai router adiacenti
• L'informazione trasmessa è una stima del costo verso tutte le reti
• L'informazione è trasmessa su base periodica regolare
• Un router determina l'informazione sul next-hop usando l'algoritmo di Bellman-Ford distribuito sulle stime dei costi ricevuti

LINK STATE:

• Ogni router invia le informazioni di routing a tutti gli altri router
• L'informazione trasmessa è il valore esatto del costo dei link verso le reti adiacenti
• L'informazione è trasmessa solo quando avviene un cambiamento
• Un router costruisce prima una descrizione della topologia della rete e poi usa un algoritmo di routing qualsiasi per calcolare le informazioni sul next-hop (tipicamente Dijkstra)

LO STRATO DI TRASPORTO

Il servizio

host. Inoltre, il livello di trasporto si occupa di suddividere i dati in segmenti o datagrammi, in base al protocollo utilizzato (TCP o UDP), e di gestire la trasmissione e la ricezione dei messaggi tra i processi applicativi. Il protocollo TCP offre un servizio affidabile, garantendo la consegna dei messaggi nel corretto ordine. Questo significa che i dati inviati da un processo applicativo vengono ricevuti correttamente dal processo applicativo destinatario, senza perdite o duplicazioni, e nell'ordine corretto. TCP è anche orientato alla connessione, il che significa che viene stabilita una connessione tra i processi applicativi prima di iniziare la trasmissione dei dati. Il protocollo UDP, invece, offre un servizio non affidabile. Non garantisce la consegna dei messaggi né l'ordine corretto di ricezione. È semplicemente un protocollo di indirizzamento, che permette di inviare dati a un indirizzo IP specifico senza stabilire una connessione preliminare. Il livello di trasporto è implementato solo nei sistemi finali delle reti IP, cioè nelle macchine remote. Il suo compito principale è quello di indirizzare i diversi processi applicativi in esecuzione su un host, utilizzando i Service Access Point (SAP) corrispondenti ai vari protocolli applicativi (ad esempio, HTTP, FTP, SMTP). Inoltre, il livello di trasporto si occupa di gestire lo stato di trasporto, che permette di distinguere i diversi processi applicativi o utenti all'interno dello stesso host. Questo è particolarmente importante quando più processi o utenti utilizzano contemporaneamente lo stesso protocollo di trasporto.

host. L'indirizzo IP identifica l'host e non gli utenti o i processi attestati all'host; l'indirizzo usato dai protocolli di trasporto è il numero di porta.

Ogni elaboratore contiene un insieme di punti logici di accesso/destinazione detti "porte". Ogni porta è individuata da un intero positivo. È il sistema operativo a mettere in corrispondenza ogni porta con il relativo processo.

In terminologia OSI, una porta non è altro che un SAP dello strato 4 situato tra gli strati di trasporto e applicativo, che identifica univocamente una specifica entità di destinazione responsabile del processo di destinazione.

L'indirizzo completo TCP/IP è costituito dall'insieme di indirizzo IP e del numero di porta e identifica univocamente un processo in esecuzione su un host.

La divisione dei compiti fra lo strato di trasporto (UDO, TCP) e IP è la seguente:

• lo strato IP si occupa del trasferimento dei dati fra

elaboratori collegati alle reti in