Complementi di Reti di telecomunicazioni

Martina Contestabile Ingegneria informatica a.a. 2020/2021

Complemen di Re di Telecomunicazioni

1

ti ti

Martina Contestabile Ingegneria informatica a.a. 2020/2021

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

geogra ca 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: classi cazione, 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

fi fi à

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

hop-by-

di routing in ciascun gateway. L’instradamento

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

protocolli di routing

garantito dall’aggiornamento costante delle tabelle di routing. I con gurano

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? È di cile da sapere, a causa delle operazioni di subnetting, il partizionamento poco smart

tabella di

degli indirizzi IPv4 ha reso di cile sapere la posizione del nodo. Quindi, usiamo la

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.

protocolli di routing,

Il primo gennaio alle ore 00:00:00 viene svolta quest’operazione. I invece,

tabelle di routing,

coordinano le 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,

longest pre x match.

si ripete l’operazione di

IL CALCOLO DEI PERCORSI OTTIMALI

Il calcolo dei percorsi ottimali porta alla

con gurazione delle tabelle di routing, e al loro

aggiornamento quando la con gurazione 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

fi ffi è ù à ffi fi fi à è fi

Martina Contestabile Ingegneria informatica a.a. 2020/2021

LA DISTRIBUZIONE DELLE INFORMAZIONI DI

ROUTING

Una volta calcolato il percorso ottimale tra due

tabelle di

nodi di rete, bisogna con gurare le

routing dei nodi perch ri ettano il percorso

ottimale.

protocolli di routing

I 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 = nd_longest_pre x_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 modi ca 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 pre x 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

ù fi fi fi é fi fl fi è è ù à è

Martina Contestabile Ingegneria informatica a.a. 2020/2021

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 e cienza.

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

è ù à à ffi è ì ù

Martina Contestabile Ingegneria informatica a.a. 2020/2021

ALGORITMI DI ROUTING - INTRODUZIONE

RICHIAMI DI MATEMATICA DISCRETA: I GRAFI

grafo

Il è 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.

grafo orientato, grafo

Il invece, è un 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.

grafo pesato, grafo

Il a sua volta, è un 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…

cammino

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

peso cammino

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

P = 1 + 2 + 4 + 1 = 8

Peso di .

1

Ciclo Gra orientati: cammino, che contiene almeno un lato, nel quale il vertice di

partenza e il vertice di arrivo sono gli stessi.

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

• ciclo.

(A,E,D,C,A) un

• (C,B,C) non lo .

Grafo aciclico è il grafo che non contiene cicli.

Grafo connesso cammino

è il grafo nel quale esiste almeno un tra

ogni sua coppia di nodi.

grafo non orientato, connesso aciclico.

L’albero è il e

Ossia, per ogni coppia di nodi del grafo esiste uno e un solo

cammino che li congiunge.

di copertura

L’albero di un grafo, invece, è un albero i cui vertici

grafo.

sono tutti i vertici del

grafo

Un ammette (almeno) un albero di copertura se e solo se

connesso. 10

ò fi

fi è ò è è è ù è È è ù ù ò è è è

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

gra pesati connessi.

Di solito ci interessano i e

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