Laboratorio di Reti Informatiche

IP Routing

A. Lainalaina@cisi.unito.it

Terminologia

IP: Internet Protocol protocollo di comunicazioni tra reti (locali)

Routing: da to route instradare (anche ruotare)

Ambito

Autonomous System (AS, sistema autonomo) insieme di reti gestite da una singola organizzazioneex: GARR

Internet: tutte le AS “integrate” da BGP-4

Modalità di routing

CIDR Classless Interdomain Routing Network classless

Scopo

• Assegnare network logici alle reti fisiche

• Distribuire le informazioni per rendere raggiungibile i network

LAN

LAN

ES

ES

IS

IS ES

OSI TCP/IP

Application ApplicationPresentation TransportSession NetworkTransport InterfaceNetworkData LinkPhysical

LAN a livello 3: 1+ network number (prefissi)

prefisso: 32 bits + lunghezza (L) e i bits oltre i primi L messi a 0

ex: 10101100.11110000.01010011.10000000/27 = 172.240.83.128/27 (172.240.83.128 255.255.255.224)

Notazione: A.B.C.D/L A, B, C, D {}L {}

Prefissi particolari: 127.0.0.0/8 loopback 10.0.0.0/8 privati 172.16.0.0/12 192.168.0.0/16 239.0.0.0/8 multicast privati 0.0.0.0/0 Internet

Supernet (~ aggregato): A.B.C.D/L A.B.C.D/L se L L e i primi L bits sono uguali

ex: 172.240.83.0/24 172.240.83.128/27

10101100.11110000.01010011.00000000/24 10101100.11110000.01010011.10000000/27

Subnet (sottorete): A.B.C.D/L A.B.C.D/L se A.B.C.D/L A .B .C .D /L

è una relazione d’ordine parziale

Proprietà:

1. 0.0.0.0/0 A.B.C.D/L2.

················

. ! A.B.C.D/L come in 2. con L massimosummary network (riassume i prefissi)

4. Non tutti i network IP corrispondono a reti locali (fisiche)

11111 /L.D.C.BA

nnnnn /L.D.C.BA

i /L.D.C.BA A.B.C.D./L iiiii

172.240.83.128/27

172.240.83.160/27

172.240.83.192/27

172.240.83.128/2710101100.11110000.01010011.10000000/27

172.240.83.160/2710101100.11110000.01010011.10100000/27

172.240.83.192/2710101100.11110000.01010011.11000000/27

summary172.240.83.128/2510101100.11110000.01010011.10000000/25

Riassumendo prefissi, si diminuisce la quantità di da elaborare.Un router Internet BGP-4 con full routes contiene informazioni per 55000-60000 prefissi.

Suddividere un prefisso in prefissi più piccoli permette di delegare la gestione di una sottorete.

Indirizzi IP

A.B.C.D./L =

yy…yy 00…00 networkyy…yy 11…11 direct broadcast

In un network /L (L 30) si possono assegnare indirizzi IP “utilizzabili”

Indirizzi unicast A {1,…,223} multicast A {224,…,239}

Limited broacast 255.255.255.255

L-3200...00

L

xx...xx

L-32yy...yy

L

xx...xx

22 L32

130.192.197.0/26

A B

IPAI PBI

PAB

9/30 10/30 22/29

18/29

17/29

6/30

5/301/30

2/30

62/27

33/27

34/27

35/27

60.2/30

Internet (60.1/30)

PAI 0/30 0,1,2,3

PBI 4/30 4,5,6,7

PAB 8/30 8,9,10,11

B 12/29? 12=00001100 NO!!!

B 16/29 16,17,…,22,23 (12/30 non usato)

A 24/27? 24=00011000 NO!!!

A 32/27 32,33,…,62,63 (24/29 non usato)

130.192.197.0/26 non è associato ad una LAN fisica ma le riassume tutte.

Alcuni “trucchi” per assegnare i prefissi

• Assegnare i prefissi in modo progressivo in ordine sempre crescente o sempre decrescente della dimensione dei network

• Raggruppare prefissi di dimensione inferiore in modo da costituire blocchi di dimensioni simili

• Se un prefisso contiene N indirizzi (senza –2), il valore numerico deve essere un multiplo di N (in notazione decimale basta considerare solo uno dei 4 numeri e dividere N opportunamente

Datagramma IP

Ver H L TOS Total Length

ID Flag Fragmet Offset

TTL Protocol Header Checksum

Source IP

Destination IP

Options Pad

Data

Ver 0100 per IPv4HL in unità di 32 bits (lw o dw)TOS ora chiamato anche DSCPTLen in bytes (max 64K) header + dataID id del dtg, identifica i frammentiFlags (M)ore (F)rag|(D)on’t (F)rag|Unused

MF=1 su tutti I frammenti tranne ultimoFO in unità di 8 bytes, posizione relativa

nel datagramma originaleTTL “durata” di vita del datagrammaProt identificativo del protocollo in Data

ICMP=1, TCP=6, UDP=17, OSPF=89HC Controllo di integrità headerOpt sezione per opzioni (source routing,

trace, timestamps)

Pad dimensione campo Opt multiplo di 32 bits

Frame Ethernet

Ethernet II T/L = type (protocollo in data)802.3 T/L = length (di data)T/L (hex) 0000-05DC 802.3 0800 IPv4 0806 ARP 6004 LAT 8035 RARP

MTU IP = 65536 (64K)MTU Eth = 1500 frammentazione per i datagrammi lunghi

Preamble Dest Src T/L Data FCS6+1 6 6 2 46-1500 4

Dest e Src sono indirizzi MAC 48 bits

Conversione indirizzi IP MAC Unicast: protocollo ARP Broadcast: FFFF:FFFF:FFFF Multicast: 0100:5Exx:xxxx 28 bits 23 bits eliminando i primi 5

Modulo IP

IP

Path Determination

Forwarding

Sorgenti IP Dest IP

A B

IPAI PBI

PAB

9/30 10/30 22/29

18/29

17/29

6/30

5/301/30

2/30

62/27

33/27

34/27

35/27

60.2/30

Internet (60.1/30)

AP

TR

NW

DL

AP

TR

NW

DL

AP

TR

NW

DL

AP

TR

NW

DL

Modulo Path Determination I

Ogni modulo IP deve avere un’idea più o meno “completa” di come siano disposti i prefissi. Quella parte del software che si occupa di questo prende il nome di modulo di “Path Determination”. Costruisce un database, chiamato tabella di routing, che contiene tutte le informazioni messe a disposizione del modulo IP.

Per ogni prefisso destinazione, si stabiliscono uno o più percorsi “ottimali” e si distribuisce (parzialmente) l’informazione a tutti i sistemi coinvolti. I precorsi devono essere “coerenti” tra di loro.

Longest Match: una sottorete (prefisso più lungo) ha la precedenza sui suoi supernet

Informazione per ogni prefisso:

• indirizzo next hop

• interfaccia di uscita

Tabella di routing

prefisso destinazione IPnh o interfaccia altri dati

AP

TR

NW

DL

lo

fisiche

Ex: pc con una interfaccia Ethernet

quasi sempre anche:

La tabella di routing viene costruita mediante varie sorgenti di informazione non necessariamente concordi tra di loro (vince la fonte più “attendibile”). Ogni fonte può a sua volta dare indicazioni contrastanti. Non ci sono standard per definire l’affidabilità delle fonti, ogni fabbricante usa uno schema proprio.

127.0.0.0/8 loIPscheda/32 lo

prefisso scheda eth0

0.0.0.0/0 IPDG

Ex: Cisco IOS “Attendibilità” = Administration distance 0…255

prefissi interfacce attive 0 statiche 1 EBGP 20 EIGRP 90 OSPF 110 RIP 120 IBGP 200 sconosciuto 255

Prefissi interfacce attive 35/27 35/32 lo

32/27 eth0

Statiche = direzioni configurate manualmente default gateway 35/27 0.0.0.0/0 62

Si possono usare interfacce al posto del next hop

Questi due tipi di sorgenti di informazione sono sufficienti per la maggior parte degli ES ma non per gli IS, tranne i più periferici e meno collegati.

Sono sorgenti molto stabili, in certi casi “troppo” stabili perchè richiedono di intervenire su molti sistemi se si modifica la topologia delle LAN. Non sono le più adatte ad un sistema che compensi automaticamente guasti e nuovi allacciamenti.

Ex

35/2735/32 lo32/27 eth0

0.0.0.0/0 62 ………

17/2917/32 lo16/29 eth0

0.0.0.0/0 22 ………

A2/32 lo0/30 eth09/32 lo8/30 eth162/32 lo32/27 eth2

16/29 104/30 14/30 100.0.0.0/0 1 ………

B6/32 lo4/30 eth010/32 lo8/30 eth122/32 lo16/29 eth2

32/27 90/30 50/30 90.0.0.0/0 5 ………

Modulo Forwarding

Per ogni datagramma, si cerca nella tabella di routing di ogni sistema la coppia (IPnh, ifexit) (ifexit = interfaccia di uscita).

Si usa il seguente algoritmo con i dati iniziali IPnh = IPdest e ifexit = null.

1. IPnh IP/32

2. Costruire la lista (anche vuota) dei supernet con L massimodi 1. esaminando la tabella di routing.

3. Se, ad un supernet, è associata una interfaccia if ifexit = if.Se, invece, è associato un IP IPnh = IP e per questa coppia si riparte da 1.

Si presentano 3 casi mutuamente esclusivi

• La lista è vuota. Il datagramma viene scartato e, se è il caso, viene spedito un ICMP a IPsorgente.

• La lista contiene una singola coppia. Il datagramma viene inviato alla corrispondente interfaccia e da questa ad IPnh senza modificare gli indirizzi dell’intestazione.

• La lista contiene più di una coppia. Se il datagramma è un unicast o un broadcast, viene scelta una coppia e si procede come al punto precedente. Se invece è un multicast, lo si replica su tutte le coppie.

Tranne configurazione particolare, un broadcast di livello 2, ricevuto da una interfaccia viene spedito solo ai livelli superiori.

Ex: Trasmissione datagramma 35 17, frame Ethernet II

Percorso 35 A B 17Ipotesi ARP: 130.192.197.xy 5555:55AB:CDyx 130.192.197.35 5555:55AB:CD53 130.192.197.2 5555:55AB:CD20

35IP: S = 35 D = 17 TTL = 64 HC = x1

E: S = 53 D = 26 FCS = y1

AIP: S = 35 D = 17 TTL = 63 HC = x2

E: S = 90 D = 01 FCS = y2

BIP: S = 35 D = 17 TTL = 62 HC = x3

E: S = 22 D = 71 FCS = y3

17

Ex: Trasmissione datagramma 35 23 (direct broadcast), frame Ethernet II

Percorso 35 A B 23ARP come esempio precedente

35IP: S = 35 D = 23 TTL = 64 HC = x1

E: S = 53 D = 26 FCS = y1

AIP: S = 35 D = 23 TTL = 63 HC = x2

E: S = 90 D = 01 FCS = y2

BIP: S = 35 D = 23 TTL = 62 HC = x3

E: S = 22 D = FFFF:FFFF:FFFF FCS = y3

17…22

Modulo Path Determination II

I sistemi di configurazione manuale non sono ottimali se ci sono cambiamenti di topologia nelle reti.

A B

IPAI PBI

PAB

9/30 10/30 22/29

6/30

5/301/30

2/30

62/27

60.2/30

Interruzione a livello fisico.

A B I2/32 lo 6/32 lo 60.2/32 lo0/30 eth0 4/30 eth0 60.0/30 eth09/32 lo 10/32 lo 1/32 lo8/30 eth1 8/30 eth1 0/30 eth162/32 lo 22/32 lo 5/32 lo32/27 eth2 16/29 eth2 4/30 eth2

16/29 10 32/27 9 8/30 24/30 1 0/30 5 8/30 64/30 10 0/30 9 16/29 60.0.0.0/0 1 0.0.0.0/0 5 32/27 2

0.0.0.0/0 60.1

Protocolli di Routing

Sistemi automatici di scambio di informazione dei network.Si “accorgono” del cambiamento di stato delle interfacce e della reale connettività a livello 2 (keep alive).

Le informazioni si propagano a velocità finita tempi di convergenza non nulli (possono essere lunghi)

Due famiglie (rispetto all’AS): Interno: RIP, (E)IGRP, OSPF, IS-IS Esterno: EGP, BGP-4

Terminologia

Metrica (metric): valore numerico associato ai prefissi per quantificarne il grado di preferenza. Il significato dipende dal protocollo

Convergenza: processo che porta tutti i router ad avere tabelle di routing consistenti (stato stazionario)

Tempo di convergenza: il periodo temporale che intercorre mentre il sistema di router passa da uno stato stazionario (e consistente) ad un altro

Aggiornamento: metodo con il quale vengono condivise le informazioni sui prefissi

RIP e IGRP

(R)outing (I)nformation (P)rotocol, standard di Internet(I)nternet (G)ateway (R)outing (P)rotocol, proprietario Cisco

Tipo Distance Vector: gli aggiornamenti contengono “vettori” della forma (distanza, direzione).

Aggiornamenti periodici: l’intera tabella di routing di ogni singolo router viene spedita periodicamente a tutti i router connessi. I router non sincronizzano gli aggiornamenti tra di loro. RIP 30 sec, IGRP 90 sec.

Metrica: RIP numero di hop per raggiungere la destinazione. IGRP combinazione (configurabile) di banda, ritardo, carico e affidabilità di ogni collegamento; si sommano i valori ottenuti per tutti i collegamenti necessari per arrivare al prefisso di destinazione.

Durata di vita dei prefissi: ogni riga della tabella di routing a cui non corrisponde una interfaccia sul router stesso, ha una durata di vita finita (di solito tra 3 e 6 aggiornamenti). Se il router non riceve un aggiornamento con informazioni sul prefisso entro questo periodo, la riga viene eliminata, altrimenti la durata di vita viene prorogata. convergenza anche in presenza di guasti.

Split horizon (facoltativo): gli aggiornamenti di A verso B non contengono le righe il cui next hop è B (perchè è stato B a comunicare ad A questa informazione). Permette di evitare routing loop “semplici”. Una variante (split horizon with poisoned reverse) prevede di includere anche questi prefissi ma dichiarandoli irraggiungibili (= distanza “infinita”).

A B

Counting to infinity: si considera come distanza infinita un valore finito (RIP 16 hop, IGRP 255 hop). In un loop come sopra l’informazione sbagliata viene eliminata quando, dopo successivi aggiornamenti, l’hop count raggiunge “infinito”.

C D

A B