Complementi di Reti di telecomunicazioni

Martina Contestabile ingegneria informatica a.a. 2020/2021

Complementi di Reti di Telecomunicazioni 1ti ti

Martina Contestabile Ingegneria informatica a.a. 2020/2021

Indice

• Obiettivi 6
• Programma — 3 crediti – Complementi di reti di TLC. 6
• Testi consigliati 6
• Testi principali 6
• Altri testi 6
• Il routing IP — introduzione 7
• Internetworking? L’instradamento dei pacchetti IP 7
• Il routing IP 7
• Il legame tra routing e indirizzamento 7
• Il routing IP - meccanismi fondamentali 7
• Il meccanismo di inoltro locale 7
• Il calcolo dei percorsi ottimali 7
• La distribuzione delle informazioni di routing 8
• Il routing IP — il meccanismo di inoltro a livello locale 8
• La tabella di routing 8
• Il meccanismo classless di inoltro sui router 8
• Note 8
• Meccanismo di inoltro diretto e indiretto 8
• Inoltro diretto direct routing 8
• Inoltro indiretto indirect routing 9
• Il routing — «casi particolari» 9
• Routing multicast 9
• Multi protocol label switching MPLS 9
• Algoritmi di routing - introduzione 10
• Richiami di matematica discreta: i grafi 10
• I grafi e le reti 11
• Note sui grafi orientati 11
• Algoritmi di routing 11
• Qualche semplice esempio 11
• Un problema fondamentale nel routing: il calcolo dell’albero dei cammini ottimi 11
• Algoritmi di routing nelle reti 12
• Classificazione 12
• Proprietà fondamentali 12
• Algoritmi di routing statici 12
• I non-algoritmi 12
• Configurazione statica delle tabelle di routing 12
• 2À Martina Contestabile Ingegneria informatica a.a. 2020/2021
• Flooding 13
• Algoritmo di Dijkstra 13
• Dijkstra — albero dei cammini minimi 13
• Parentesi — complessità degli algoritmi 13
• Proprietà 14
• Algoritmi di routing dinamici 14
• Algoritmi statici - algoritmi dinamici 14
• Distributed Bellman-Ford DBF 14
• Più comunemente: distance vector routing 14
• Link state routing 18
• Algoritmi di routing: riassunto 20
• Protocolli di routing TBD 22
• Rapporto tra algoritmi e protocolli di routing 22
• Il routing nelle internetwork — le reti di reti 22
• Principali problematiche da risolvere 22
• Routing gerarchico 22
• Autonomous system 22
• Routing intra-AS 22
• Routing inter-AS 22
• Gli svantaggi del routing gerarchico 23
• IGP e EGP 23
• Protocolli di routing: classificazione 23
• Routing con informazione incompleta default 24
• Ulteriore nota riguardo alla relazione tra topologia e tabelle di routing 24
• Protocolli di routing intra-AS 25
• Routing information protocol RIP 25
• Introduzione 25
• Caratteristiche tecniche 25
• Ottimizzazioni rispetto al classico DBF 25
• Split horizon 25
• Split horizon + poison reverse 25
• Triggered update 26
• Formato dei messaggi 26
• RIP entry versione 2 26
• Strutture di controllo sui nodi attivi router 26
• Ottimizzazioni rispetto all’algoritmo DBF — processing dei messaggi 27
• 3Ù À À Martina Contestabile Ingegneria informatica a.a. 2020/2021
• Nota sulla default route 27
• Problemi e limitazioni 27
• Open shortest path first OSPF 27
• Introduzione 27
• Componenti fondamentali dello standard 28
• Dalla rete al grafo che la rappresenta 28
• Lo shortest path tree per il nodo M 28
• I problemi di una visione piatta dell’AS 29
• Il concetto di area 29
• Il concetto di backbone 29
• Classificazione dei router 29
• Il processo di routing 30
• Il database topologico dei router dell’area 1 30
• Database topologico dei router del backbone 30
• Il database topologico dei router dell’area 3 30
• Il processo di routing 30
• Ottimizzazioni per le stub area 30
• Contiguità del backbone 30
• I messaggi protocollari 31
• Tipi di messaggio 31
• Caratteristiche comuni a tutti i messaggi 31
• Tipologie principali di LSA 32
• Reti multi-access, relazione di adiacenza e router designati 32
• Equal cost multipath e TOS-based routing 32
• Riassunto 33
• Protocolli di routing inter-AS 34
• Border gateway protocol BGP 34
• Introduzione 34
• Dalla rete al grafo 34
• Concetti fondamentali, definizioni e terminologia 34
• Le informazioni scambiate dai BGP speaker 35
• Il meccanismo base e il policy routing 36
• Policy routing: architettura ed esempio 36
• Quando usare BGP 36
• BGP non serve nel caso di stub AS 36
• I messaggi protocollari e il meccanismo di 36
• 4À Martina Contestabile Ingegneria informatica a.a. 2020/2021
• Comunicazione tra BGP speaker 36
• I messaggi BGP 37
• Il concetto di path attribute 37
• Path attribute 37
• Origin 37
• AS_PATH 37
• NEXT_HOP 37
• MULTI_EXIT_DISCRIMINATOR MED 38
• ATOMIC_AGGREGATE e AGGREGATOR 38
• I problemi legati a IBGP 38
• Le conseguenze di un meccanismo basato su path vector 38
• Riassunto 38
• Routing IP — conclusioni 39
• Il routing IP unicast 39
• Multi protocol label switching 40
• Introduzione — concetti fondamentali e definizioni 40
• Multi-protocol label switching MPLS 40
• Routing IP e forward equivalence class FEC 40
• Routing IP tradizionale 40
• Multi-protocol label switching MPLS 40
• Vantaggi rispetto al routing IP tradizionale 41
• Note e altre definizioni 41
• Etichette e stack di etichette 41
• Gestione delle etichette 41
• Stack di etichette 41
• Label switched path LSP 42
• Considerazioni 42
• LSP tunnel 42
• Applicazione di LSP, LSP tunnel e gerarchie di tunnel 42
• VPN 42
• Proprietà fondamentali e ipotesi 42
• VPN realizzate con tecnologie a circuito 43
• VPN realizzate direttamente su IP 43
• VPN realizzate con MPLS 43
• Conclusioni 43
• 5À Martina Contestabile Ingegneria informatica a.a. 2020/2021

Obiettivi

Il corso si propone di illustrare i concetti di base riguardanti le architetture di rete locale e geografica di cui vengono approfonditi gli aspetti legati al routing. Durante le lezioni in laboratorio gli studenti potranno familiarizzare con i concetti visti a lezione utilizzando un sistema di emulazione delle reti a pacchetti e toccare con mano il mondo dei sistemi di routing e switching.

Programma — 3 crediti – Complementi di reti di TLC

1. Il routing nelle reti IP.

• Algoritmi di routing: classificazione, proprietà.
• Protocolli intra-dominio — RIP, OSPF.
• Cenni ai protocolli inter-dominio BGP.
• Multi-Protocol Label Switching: cenni.
• Algoritmi e protocolli di routing multicast: cenni.

NB non svolto a lezione, le slide in cui compare un box rosso con la nota il materiale all’interno del box non viene chiesto all’esame.

Testi consigliati

Testi principali

Lucidi del corso.

J.F. Kurose, K.W. Ross, «Reti di Calcolatori e Internet», 7a edizione, Pearson, 2017, ISBN 9788891902542.

A.S. Tanenbaum, N. Feamster, D.J. Wetherall, «Computer Networks, Global Edition», 6a edizione, Pearson, 2021, ISBN 9781292374062.

B. A. Forouzan, «TCP/IP Protocol Suite», 4th ed., McGraw-Hill, 2009, ISBN 9780073376042.

Altri testi

W.R. Stevens, «TCP/IP Illustrated, Volume 1: The Protocols», Addison-Wesley Professional Computing Series.

W.R. Stevens, «TCP/IP Illustrated, Volume 2: The Implementation», Addison-Wesley Professional Computing Series.

In caso si vogliano approfondire particolari aspetti dei protocolli TCP/IP trattati durante il corso, si consiglia la consultazione on-line della libreria di Request For Comments RFC al sito http://www.ietf.org. 6

Martina Contestabile Ingegneria informatica a.a. 2020/2021

Il routing IP — introduzione

Internetworking? L’instradamento dei pacchetti IP

Il routing IP

Il routing IP è l’operazione di instradamento dei pacchetti IP. La decisione di instradamento viene presa localmente in base a informazioni contenute nelle tabelle di routing in ciascun gateway. L’instradamento hop-by-hop del pacchetto è quando ogni router deve solo conoscere la porta di uscita e il next-hop che porteranno il pacchetto più vicino alla destinazione.

L’inoltro di un pacchetto IP dall’host sorgente all’host di destinazione è un’operazione distribuita che comporta un’azione coordinata da tutti i router sul percorso del pacchetto. Il coordinamento tra i vari router viene garantito dall’aggiornamento costante delle tabelle di routing. I protocolli di routing configurano e mantengono aggiornate le tabelle di routing. L’operazione di coordinazione fra router si chiama supernetting, subnetting. È l’opposto del.

Il legame tra routing e indirizzamento

L'indirizzo IP è l’identità del nodo di rete. Tuttavia, qual è la posizione del nodo all’interno della rete? È difficile da sapere, a causa delle operazioni di subnetting, il partizionamento poco smart degli indirizzi IPv4 ha reso difficile sapere la posizione del nodo.

Quindi, usiamo la tabella di routing, che rappresenta il legame tra identità e next hop, ovvero la conoscenza locale della direzione che il pacchetto deve prendere. La tabella di routing si trova all’interno della memoria del router, è l’unica conoscenza che i router possiedono per svolgere il compito — conoscenza prettamente locale, al router non interessa altro che trasportare l’informazione, non la topologia della rete mondiale.

Appena acceso il router, l’unica conoscenza che possiede è la struttura della sua rete, ovvero le reti a cui è direttamente connesso. Poi, mano a mano, quando svolgiamo operazioni, le tabelle di routing si riempiono e svolgono le operazioni di instradamento. Il primo gennaio alle ore 00:00:00 viene svolta quest’operazione. I protocolli di routing, invece, coordinano le tabelle di routing, ossia permettono a ciascuna decisione di inoltro di portare in maniera cooperativa all’inoltro end-to-end del datagramma.

L’insieme delle tabelle di routing contiene la conoscenza globale, ma distribuita, del legame tra indirizzi e posizione dei nodi.

Il routing IP - meccanismi fondamentali

Il meccanismo di inoltro locale

Una volta ricevuto un pacchetto in ingresso, come viene presa la decisione su che porta di uscita inviarlo?

Next-hop è l’indirizzo IP del router a cui inoltrare il pacchetto. Se c’è «- -», la consegna è diretta, ovvero c’è una connessione punto punto al livello data link col router successivo. In caso contrario, si ripete l’operazione di longest prefix match.

Il calcolo dei percorsi ottimali

Il calcolo dei percorsi ottimali porta alla configurazione delle tabelle di routing, e al loro aggiornamento quando la configurazione o la situazione della rete cambia — aggiunta/rimozione di router, aumento/diminuzione del carico, ecc. Gli algoritmi di routing si occupano di questo problema, essi vanno implementati all’interno dei protocolli. 7

Martina Contestabile Ingegneria informatica a.a. 2020/2021

La distribuzione delle informazioni di routing

Una volta calcolato il percorso ottimale tra due nodi di rete, bisogna configurare le tabelle di routing dei nodi perché riflettano il percorso ottimale.

I protocolli di routing si occupano di fare in modo che i router si scambino tutte le informazioni necessarie per tenere aggiornate le proprie tabelle di routing. Dopo lo spegnimento del primo gennaio, il router deve rimanere aggiornato per continuare a permettere lo scambio di pacchetti.

Il routing IP — il meccanismo di inoltro a livello locale

La tabella di routing

Le righe di una tabella di routing IP puntano sempre ad indirizzi di router che possono essere raggiungibili direttamente — a livello 2 — dal router in esame, ossia al next-hop a livello IP nel percorso dei pacchetti.

Esaminando la propria tabella di routing, il singolo router non ha visibilità globale sul percorso che i pacchetti IP debbano seguire: l’unico elemento che conosce, per ogni dato indirizzo di destinazione, è il next-hop a livello IP.

Quando questo router riceve un pacchetto che va a matchare una di quelle righe, rimane nel campo next-hop, che è direttamente raggiungibile a livello 2.

Il meccanismo classless di inoltro sui router

on receipt of IP packet source IP = A, destination IP = B:

Parse destination IP address B from packet;

If B matches any directly attached local LAN:

Resolve layer-2 address for B;

Encapsulate packet in layer-2 frame;

Send encapsulated packet on outgoing interface;

Else: next-hop = find_longest_prefix_match B, routing table;

If next-hop == NULL:

If default_route != NULL:

next-hop = default next-hop;

If next-hop != NULL:

[resolve layer-2 address for next-hop;]

Encapsulate packet in layer-2 frame;

Send encapsulated frame to next-hop;

Else: generate routing error ICMP dest unreachable.

Note

Il router non modifica gli indirizzi IP di sorgente o destinazione del pacchetto: il pacchetto originario, a meno di aggiornamento di alcuni campi dell’header come TTL e checksum, viene incapsulato in una trama di livello due e inoltrato al next-hop o direttamente alla destinazione.

Longest prefix match per un dato indirizzo di destinazione D:

• Per ciascuna riga i della tabella di routing, contente l’indirizzo di rete Ri e la netmask Mi, si faccia l’«AND» binario tra D e Mi X = D & Mi.
• Si confronti Ri con X, e si memorizzi i in caso di match.
• In caso più di una riga abbia dato luogo ad un match, la riga con Mi più lunga è quella «vincente».

Meccanismo di inoltro diretto e indiretto

Inoltro diretto direct routing

La destinazione del pacchetto è raggiungibile direttamente a livello 2 senza passare per 8 ulteriori router.

Richiede la risoluzione dell’indirizzo di livello 2 della destinazione del pacchetto.

Il router invia il pacchetto IP incapsulato nella frame di livello 2 direttamente alla destinazione.

Inoltro indiretto indirect routing

La destinazione del pacchetto non è direttamente raggiungibile a livello 2 dal router.

Il router deve selezionare il next-hop prossimo gateway al quale inoltrare il pacchetto.

A meno che il link che lega i due router sia di tipo point-to-point per esempio, una linea seriale, il router deve risolvere l’indirizzo di livello 2 del next-hop.

Il routing — «casi particolari»

Routing multicast

Algoritmi e protocolli di routing che permettono ad una rete l’inoltro di informazioni da una o più sorgenti a più destinatari contemporaneamente.

Problemi: scalabilità ed efficienza.

Multi protocol label switching MPLS

Non è un protocollo di routing, bensì una tecnologia di livello intermedio tra rete e data-link per facilitare la scalabilità delle reti moderne. 9

Martina Contestabile Ingegneria informatica a.a. 2020/2021

Algoritmi di routing - introduzione

Richiami di matematica discreta: i grafi

Il grafo è una struttura costituita da un insieme di vertici, e lati.

I lati congiungono i vertici. Ci può essere più di un lato tra due vertici.

Il grafo orientato, invece, è un grafo nel quale a ciascun lato è associata una direzione. È possibile percorrere ciascun lato da un vertice ad un altro in una sola direzione. Si può ricondurre un grafo non orientato ad un grafo orientato sostituendo ogni lato con due lati orientati in senso inverso.

Il grafo pesato, a sua volta, è un grafo nel quale a ciascun lato è associato un valore numerico.

In TLC, potrebbe essere il ritardo, il costo che ha immettere un pacchetto in rete, l’ampiezza della banda…

Il cammino dal vertice A al vertice Z, P(A...Z) è un sotto-grafo composto dalla successione dei vertici da A a Z, percorsi una sola volta.

Se il grafo è orientato, si deve tener conto della direzione dei lati — non è possibile percorrere un lato dal nodo H al nodo K se l’unico lato che li collega è orientato da K a H. Dato un grafo G che contiene i vertici A e Z, Z è raggiungibile da A se e solo se esiste nel grafo G un cammino da A a Z.

In generale, in un grafo possono esistere più cammini distinti tra due nodi.

Il peso di un cammino è la somma dei pesi associati a tutti i lati che compongono il cammino.

P = 1 + 2 + 4 + 1 = 8.

Peso di 1.

Ciclo grafi orientati: cammino, che contiene almeno un lato, nel quale il vertice di partenza e il vertice di arrivo sono gli stessi.

Grafi non orientati: cammino, che contiene almeno un lato, nel quale i vertici sono tutti distinti, tranne il primo e l’ultimo, e tutti i lati sono distinti — ossia, non si può percorrere lo stesso lato più di una volta.

• (A,E,D,C,A) è un ciclo.
• (C,B,C) non lo è.

Grafo aciclico è il grafo che non contiene cicli.

Grafo connesso è il grafo nel quale esiste almeno un cammino tra ogni sua coppia di nodi.

L’albero è il grafo non orientato, connesso e aciclico. Ossia, per ogni coppia di nodi del grafo esiste uno e un solo cammino che li congiunge.

L’albero di copertura di un grafo, invece, è un albero i cui vertici sono tutti i vertici del grafo.

Un grafo ammette almeno un albero di copertura se e solo se connesso. 10

Martina Contestabile Ingegneria informatica a.a. 2020/2021

I grafi e le reti

La struttura delle reti di telecomunicazione si presta ad essere rappresentata con grafi.

Di solito ci interessano i grafi pesati e connessi.

Nel caso delle reti IP:

• Vertici nodi = router.
• Lati link = collegamenti trasmissivi.
• Pesi = caratteristiche dei collegamenti trasmissivi, come banda disponibile, ritardo, costo relativo alla trasmissione al byte, ecc., o una combina