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 tra 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.

b) Tabella di instradamento (route table):

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

dostnextdostnext172828253103852516733211IP_due semplifica tale tabella

Meno ridondanza nel pacchetto.

Metriche di instradamento

Relazione d'ordine.

• Costo
• Qualità studio
• 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

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.

destnextdestnext12532863397841087511IP due semplifica tale tabella.

Meno ridondanza nei pacchetti.

Metrica di instradamento

Relazione d'ordine:

• Costo
• Qualità studio
• 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:1s₁: 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

• Bellman-Ford (O(N³) o O(dE))
• 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