Riassunto esame Telecomunicazioni, prof. Badia, testo consigliato Principles of Communications Networks and Systems", Benvenuto, Zorzi

Lezione 16/12/19 Rivisitazione

Network Layer - Livello 3

Collaborazione tra i diversi nodi.

Livello 2: due nodi principali a dover una coordinazione degli errori. Livello affidabile a livello 3!

La rete è un grafo con un insieme di nodi e un insieme di collegamenti.

Vogliamo molti vicini (nodi collegati da un arco)? No!

Tratti percorsi più prob. collez. con tanti vicini.

Problemi dell'instradamento.

• Source routing. La sorgente conosce il percorso da far fare al pacchetto, ma deve dunque inserire trae le informazioni che contiene il pacchetto anche le informazioni sul percorso.

Vantaggi: AFFIDABILE (conosco la strada da seguire)

Svantaggi: Elevata ridondanza - ripeto la stessa informazione tante volte nei pacchetti. In ogni pkt devo ripetere tale informazione.

Ogni nodo ha una tabella memorizzata in cui c'è scritto qual è il prossimo passo per arrivare a destinazione.

IP_due semplifica tale tabella

Meno ridondanza nel pacchetto

Metriche di instradamento.

Relazione d'ordine.

1. costo
2. qualità studio
3. numero di salti di tempo

Lezione 16/12/19 Rivisitazione

Network Layer - Livello 3

Collaborazione tra i diversi nodi.

Livello 2 due progetto a darvi una coordinazione degli errori. Livello affidabile è livello 3!

La rete è un grafo con un insieme di nodi e un insieme di collegamenti.

Vogliamo molti vicini (nodi collegati da un arco)? Distanza 1.

Tutti percorsi più prob. collis. con tutti vicini.

Problema dell'instradamento.

1. Source routing. La sorgente conosce il percorso da far fare al pacchetto, ma deve comunque inviare tra le informazioni che contiene il pacchetto anche le informazioni sul percorso.

Vantaggio: AFFIDABILE (conosco la strada da seguire!)

Svantaggio: Elevata ridondanza - ripeto la stessa informazione tante volte nei pacchetti. In ogni pkt devo ripetere tale informazione.

2. Tabella di instradamento (route table):

Ogni nodo ha una tabella memorizzata in cui c'è scritto quale è il prossimo passo per arrivare a destinazione.

IP due semplifica tale tabella.

Meno ridondanza nei pacchetti.

Metrica di instradamento.

Relazione d'ordine:

1. costo
2. qualità studio
3. numero di salti di tempo

A seconda della metrica scelgo la strada.

Metrica lineare di solito (meglio se additiva). Il costo complessivo della rotta è la somma dei singoli pezzi che si attraversano.

Possiamo allora trovare la strada migliore, anche se è molto complessa.

• Generic routing protocol
• Cost: function of congestion nel caso della rotta con costo x

Il traffico va da s a d.

Per il singolo automobile è meglio il percorso x, visto che ha un costo sempre minore dell'altra strada (in pratica, è strategia dominante in teoria dei giochi).

Si poteva fare meglio... dividere il costo s nel ts sopra pago:

• x
• s₁/(2 - 1/2)
• [3/4]

Sotto pago:

• 1
• s₁: 1/2 : 1

Qualcuno dovrebbe decidere il instruttoremetro.

Tutti i giocatori, prendendo una decisione individuale, prenderebbero la strada con costo x: che credono sia la migliore

Controllore difficile da avere in pratica

Ogni singolo individuo viene spedito per la rotta che per lui è la migliore (non è la scelta ottima). Individuo «pacchetto».

Approcci per trovare la strada migliore

1. Bellman-Ford (O(N³) o O(dE))
2. Dijkstra (O(N²))

Nota: Tipologia stella → d=2

Diametro piccolo → Bellman-Ford va meglio bene

si presta bene ad una implementazione distribuita:

Chiedo ad ogni singolo nodo di eseguire l'algoritmo

per conto suo e non ho bisogno di un'unità

centrale per trovare l'indirizzam