Strato rete in Internet
Gruppo Reti TLC
[email protected]
http://www.tlc-netwroks.polito.it/
STRATO RETE IN INTERNET - 1
Internet protocol suite
Application
Presentation
Session
Transport
Network
NFS
Telnet
FTP
SMTP
SNMP
XDR
RPC
TCP e/o UDP
ICMP
Protocolli
di routing
IP
ARP | RARP
Data Link
Physical
OSI
Non Specificati
Internet Protocol Suite
STRATO RETE IN INTERNET - 2
IP: Internet Protocol
• Livello rete dell’architettura TCP/IP
• Offre un servizio
– non connesso
– inaffidabile
– best-effort
– senza garanzie di qualità di servizio
STRATO RETE IN INTERNET - 3
Il protocollo IP
• È un protocollo di strato rete (strato 3)
• Si occupa quindi dell’indirizzamento e
instradamento dei pacchetti (detti datagram)
• La consegna dei pacchetti IP è:
– connectionless
• ogni pacchetto trattato in modo indipendente
– inaffidabile (unreliable)
• perdita, duplicazioni, ritardi
– non distingue tra diversi tipi di traffico (no
priorità, tratta tutti in modo best-effort)
STRATO RETE IN INTERNET - 4
Protocollo IP
• Consegna inaffidabile
– In caso di guasti (es. un router fuori servizio,
collegamento non disponibile)
• scarta il datagram
• cerca di inviare un messaggio di errore al mittente
• Consegna connectionless
– Non conserva informazioni di stato sui datagram
in corso di trasmissione
– Ogni datagram instradato in modo indipendente
– Due pacchetti con stessa sorgente e
destinazione possono seguire percorsi
diversi
STRATO RETE IN INTERNET - 5
Intestazione pacchetto IP
0
4
8
Version HLEN
16
Service Type
Identification
Time To Live
19
31
Total Length
Fragment Offset
Flags
Protocol
24
Header Checksum
Source IP Address
Destination IP Address
Options
PAD
STRATO RETE IN INTERNET - 6
Intestazione pacchetto IP: i campi
• VER: versione del protocollo IP
• HLEN: lunghezza dell’header in parole da 32
bit (se opzioni assenti, vale 5)
• Type of service (TOS): tipo di servizio
richiede il datagram (minimize delay,
maximize throughput, maximize reliability,
minimize cost ). Ignorato dai router.
• Total Length: lunghezza del datagram in byte
(incluso header). Dimensione massima
65535 byte
STRATO RETE IN INTERNET - 7
Frammentazione
• Ogni rete ha massima dimensione ammessa
– MTU (Maximum Transfer Unit) Ethernet 1.5 kB
• Quando devo attraversare rete con MTU più
piccola del datagram si deve frammentare
• Frammenti
– diventano datagram indipendenti, con
intestazione quasi uguale a quella del datagram
originario
– ricostruiti solo alla destinazione, mai nei router
• Frammentazione trasparente a sorgente e
destinazione
STRATO RETE IN INTERNET - 8
Frammentazione
• La frammentazione è dannosa
– aumento overhead di intestazione, duplicato su
ogni frammento
– perdita di un frammento comporta la perdita al
ricvevitore di tutto il datagram; aumenta la
probabilità di errore
– ricevitore deve attivare timer di attesa arrivo
frammenti e riassemblare
• I router IP però non si devono occupare di
riassemblare frammenti
STRATO RETE IN INTERNET - 9
Intestazione pacchetto IP: i campi
• Identification, Flags, Fragment offset:
controllano operazioni di frammentazione
• Identification: permette di riconoscere a quale
datagram il frammento appartiene (frammenti
dello stesso datagram hanno stesso valore
deciso da chi genera datagram)
• Fragment offset: specifica offset dati contenuti
nel frammento, in multipli di 8 byte
• Flags (2 bit): don’t fragment e more fragments
(identifico ultimo frammento)
STRATO RETE IN INTERNET - 10
Intestazione pacchetto IP: i campi
• TTL (time to live):
– tempo di vita (in hop) di un datagram
– Ogni router decrementa di 1 il valore di TTL
– Se TTL=0 scarta datagram ed invio messaggio
di errore
• Protocol: formato dei dati specificando un
protocollo di livello superiore
• Header Checksum (16 bit): controllo di errore
sulla sola intestazione, non sui dati utente.
Somma in complemento a 1 allineando
header a 16 bit.
STRATO RETE IN INTERNET - 11
Intestazione pacchetto IP
• Source e Destination Address (32 bit):
indirizzo sorgente e destinazione degli host
• Formato opzioni: option code (option
number, option class, flag di copia nei
frammenti) + lunghezza opzione + dati
• Opzioni
– record route: registro percorso del datagram
– source route (loose and strict): sorgente
specifica percorso del datagram
– timestamp: permette di registrare tempo di
STRATO RETE IN INTERNET - 12
elaborazione del datagram
Il protocollo ICMP
• ICMP (Internet Control Message Protocol ) è
solitamente considerato parte del livello IP
• Comunica messaggi di errore o di controllo.
Può trasportare richieste di informazioni e
risposte alle richieste.
• I messaggi ICMP sono trasmessi all’interno
di datagram IP
STRATO RETE IN INTERNET - 13
Formato del messaggio ICMP
0
7
type
15
code
31
checksum
data
STRATO RETE IN INTERNET - 14
Esempi di messaggi ICMP
messaggio
type
echo reply
0
echo request
8
network unreachable
3
host unreachable
3
port unreachable
3
destn net unknown
3
destn host unknown
3
redirect
5
time exceeded (TTL)
11
time exceeded (fragment reass)11
code
0
0
0
1
3
6
7
1
0
1
query
query
errore
errore
errore
errore
errore
controllo
errore
errore
STRATO RETE IN INTERNET - 15
Il comando ping
• Se un host non risponde al ping, non è
raggiungibile.
• Spesso usato per rilevare guasti in rete
• E’ disponibile su macchine Unix e su PC
• Informazioni visualizzate da ping:
– numero di sequenza
– TTL
– round-trip-time (tempo impiegato a percorrere la
tratta sorgente-destinatario-sorgente)
STRATO RETE IN INTERNET - 16
Applicazione: il comando ping
• Il nome è ispirato al rumore del sonar
• Esegue un test di raggiungibilità
dell’interfaccia di rete di un host remoto
• Invia un messaggio ICMP echo request ad
un host, aspettandosi un echo reply
• Di default, l’ ICMP viene inviato ogni secondo
allo stesso host; è possibile tuttavia
modificare la frequenza di invio
STRATO RETE IN INTERNET - 17
Il comando traceroute
• traceroute permette di seguire il percorso
dei datagram IP hop-per-hop fino a
destinazione
• Funzionamento:
– host invia datagram IP vuoti, con TTL crescenti e
destinati alla porta 33434 dell’host remoto
– I router intermedi ritornano ICMP “time
exceeded”
– La destinazione ritorna ICMP “port unreachable”
– Se non torna messaggio ICMP in risposta entro
un timeout di 3 sec., si segnala erroreSTRATO RETE IN INTERNET - 18
Indirizzi IP
Andrea Bianco
[email protected]
http://www.tlc.polito.it/
STRATO RETE IN INTERNET - 19
Indirizzamento IP:
obiettivi e risultati
• Obiettivo originale: rendere efficienti le
operazioni di routing (router lenti - anni ‘80)
con indirizzi facilmente “classificabili”
– Spreco dello spazio di indirizzamento
(esaurimento degli indirizzi - anni ‘90)
• Nuovo obiettivo: razionalizzare
l’assegnazione degli indirizzi e la loro
aggregazione nelle routing tables
– Riduzione delle dimensioni delle routing tables e
riutilizzo di indirizzi già assegnati
STRATO RETE IN INTERNET - 20
Indirizzi IP: Principi
• Ogni host (interfaccia) è individuato da un
indirizzo a 32 bit, assegnatogli univocamente
• Un indirizzo è caratterizzato da informazioni
sulla rete (netid) e sull’host (hostid)
• L’instradamento si basa sul netid
– indirizzo non individua la macchina ma la rete 
se sposto host di rete devo cambiare indirizzo
• Ogni router ha almeno due indirizzi IP
• Gli host solitamente uno solo
STRATO RETE IN INTERNET - 21
Multi-Homed Hosts
• Poiché l’indirizzo ha
informazioni su rete e
host, se ho più di una
interfaccia di rete, devo
avere due indirizzi
• Più che un host, un
indirizzo individua una
connessione ad una
rete!
Interfaccia #1
H
Interfaccia #2
STRATO RETE IN INTERNET - 22
Classi di indirizzi
1 2 3 4
Classe A 0
8
16
netid=7 bit
24
32
hostid=24 bit
Indirizza 127 reti, ciascuna delle quali può contenere oltre 16 milioni di hosts
Classe B 1 0
netid=14 bit
hostid=16 bit
Indirizza 16384 reti, ciascuna delle quali può contenere 65536 hosts
Classe C 1 1 0
netid= 21 bit
hostid=8 bit
Indirizza oltre 1 milioni di reti, ciascuna delle quali può contenere però ‘solo’ 256 hosts
Classe D 1 1 1 0
Indirizzi multicast
STRATO RETE IN INTERNET - 23
Rappresentazione decimale
• L’indirizzo Internet viene comunemente
rappresentato nella forma:
xxx.xxx.xxx.xxx
con xxx numero decimale tra 0 e 255
• Il primo numero permette di riconoscere la
classe dell’indirizzo:
Classe A Classe B Classe C Classe D Classe E
0...127 128...191 192...223 224...239 240...255
STRATO RETE IN INTERNET - 24
Classi di indirizzi IP
• A: 105.20.38.165
• B: 130.192.2.158
• C: 193.24.54.110
indirizzo di rete (netid)
STRATO RETE IN INTERNET - 25
Indirizzi di rete e Broadcast
• Indirizzo con hostid di tutti 0, individua la rete
• Indirizzo con hostid di tutti 1, rappresenta
l’indirizzo broadcast della rete stessa
(trasmetto in broadcast su quella rete)
• netid di tutti 1 indica questa rete. Trasmetto
senza conoscere IP della rete (boot)
• Se il netid e` tutti 0, indirizzo all’host sulla
rete cui sei collegato
• Indirizzi riservati (127.0.0.0 loopback,
192.168.2.0 reti private)
STRATO RETE IN INTERNET - 26
Problemi delle classi
• Nessuno usa classe A
• Pochi usano (male) classe B
• Classe C identifica reti piccole; indirizzi poco
richiesti
• Fare crescere una rete oltre i limiti di
dimensione della classe richiede la modifica
degli indirizzi di tutti gli host
STRATO RETE IN INTERNET - 27
L’introduzione delle maschere
• È necessario superare la divisione rigida in
netid e hostid
• Scompare il concetto di classe
• Uso maschera per definire quanti bit dei 32
di indirizzo individuano la rete, ovvero per
indicare l’estensione del campo netid
• Inizialmente si utilizzano le maschere per
suddividere indirizzi di classe B
STRATO RETE IN INTERNET - 28
La subnet mask
• La subnet mask (o netmask) è un valore di
32 bit contenente:
– bit messi a 1 per identificare la parte di rete
– bit messi a 0 per identificare la parte di host
• Per esigenze di instradamento, un host deve
conoscere la parte di rete del proprio
indirizzo IP (netid+subnetid): utilizza la
subnet mask
• La subnet mask viene introdotta in fase di
configurazione di un host
STRATO RETE IN INTERNET - 29
La subnet mask
• Esempio: indirizzo host 130.192.2.7
130.192.2.7
255.255.255.0
10000100 11000000 00000010 00000111
11111111 11111111 11111111 00000000
AND
130.192.2.0
10000100 11000000 00000010 00000000
STRATO RETE IN INTERNET - 30
Maschere per supernetting
• In una seconda fase si utilizzano le
maschere per accorpare indirizzi di classe C
• Si assegnano blocchi contigui di indirizzi di
classe C
• Si usano sempre maschere (supernetting)
per identificare netid
• Si parla di CIDR: Classless Interdomain
Routing (1992)
STRATO RETE IN INTERNET - 31
Supernetting
• Esempio: assegno 2048 indirizzi contigui, a
partire da indirizzo 202.170.168.0
202.170.168.0
11001010 10101010 10101000 00000000
202.170.175.255 11001010 10101010 10101111 11111111
• Per rappresentare tale intervallo di valori,
utilizzo AND tra indirizzo inferiore e la
maschera
111111111 11111111 11111000 00000000
STRATO RETE IN INTERNET - 32
Instradamento in reti IP
Andrea Bianco
[email protected]
http://www.tlc.polito.it/~bianco
STRATO RETE IN INTERNET - 33
Consegna diretta e indiretta
• Se due host sono
connessi direttamente
alla stessa sottorete
(intesa come
collegamento fisico) si
ha consegna diretta
• Se due host non sono
connessi alla stessa
sottorete, la consegna
è mediata da uno o più
router: si ha consegna
indiretta
STRATO RETE IN INTERNET - 34
Consegna diretta
• Per decidere se effettuare una consegna
diretta, l’host mittente controlla la porzione di
rete dell’indirizzo IP destinatario
• Se tale porzione coincide con il proprio
indirizzo di rete, si ha consegna diretta
• In ogni comunicazione tra host, si ha almeno
una consegna diretta
• Il trasferimento avviene mappando l’indirizzo
IP in un indirizzo MAC della LAN cui l’host è
collegato
STRATO RETE IN INTERNET - 35
Risoluzione di indirizzi:
• Problema che si presenta per ogni
trasmissione di datagram IP (host-host, hostrouter, router-router, router-host)
• Da indirizzo IP ad indirizzo MAC (fisico)
– Direct mapping: mediante tabella statica
– Dynamic bynding: protocollo ARP: Address
Resolution Protocol
• ARP e` utilizzato su reti broadcast (LAN)
• Dato l’indirizzo IP dell’host con cui si vuole
comunicare, permette di ricavarne l’indirizzo
MAC (es: Ethernet)
STRATO RETE IN INTERNET - 36
ARP
• Viene costruito dall’host che vuole risolvere
l’indirizzo un pacchetto broadcast (request)
che contiene
– l’indirizzo IP del destinatario,
– indirizzo IP ed Ehternet di chi origina la richiesta
• L’host che riconosce nel campo richiesta il
proprio indirizzo IP invia un pacchetto di
risposta (reply) direttamente al sender
STRATO RETE IN INTERNET - 37
ARP
• Sia chi origina il pacchetto sia chi lo riceve (e
risponde) aggiungono una informazione nella
propria tabella ARP
• Le successive comunicazioni tra i due
elaboratori possono avvenire senza ulteriori
richieste di ARP
• Le entry nella tabella di ARP scadono dopo
un tempo prefissato
STRATO RETE IN INTERNET - 38
ARP
a.b.c.d
A
1
e.f.g.h
B
i.j.h.k
l.m.n.o
p.q.r.s
C
D
E
i.j.h.k ?
2
08-00-2b-15-47-2c
LAN address di C
STRATO RETE IN INTERNET - 39
Tabelle di ARP
Corrispondenze tra indirizzi IP e indirizzi LAN
IP addr
130.192.2.58
130.192.2.64
. . . .
LAN addr
age
08-00-2b-15-47-2e
08-00-2b-21-56-64
. . . .
10
12
. .
STRATO RETE IN INTERNET - 40
Tabelle di ARP
• Ogni volta che un elaboratore deve
comunicare con un altro sulla stessa LAN
conoscendone l’indirizzo IP, viene ricercato
l’indirizzo nella tabella di ARP
• Se non si trova un match viene emessa una
richiesta di ARP, altrimenti la comunicazione
può avvenire usando direttamente l’indirizzo
MAC
STRATO RETE IN INTERNET - 41
Formato del pacchetto ARP
0
8
16
Hardware Type
HLEN
PLEN
31
Protocol Type
Operation
Sender HW Address
Sender HW Address
Sender IP Address
Sender IP Address
Target HW Address
Target IP Address
Protocol
Target HW Address
Time To Live
Target IP Address
STRATO RETE IN INTERNET - 42
ARP: formato pacchetto
• Operation: tipo di operazione
– arp request, arp reply, rarp request, rarp reply
• Hardware type: tipo di MAC (Ethernet = 1)
• Protocol type: protocollo che usa ARP
(IP=0800H)
• HLEN e PLEN permettono di utilizzare ARP
con rete arbitraria (indirizzi di dimensione
variabile)
STRATO RETE IN INTERNET - 43
Consegna indiretta
• Il mittente identifica quale router incaricare
della consegna del datagram IP tra quelli
raggiungibili con consegna diretta
• Il router incaricato sceglie il router
successivo, da lui raggiungibile direttamente,
sul percorso verso la destinazione
• Il datagram passa da router a router fino a
quello che lo consegna direttamente a
destinazione
STRATO RETE IN INTERNET - 44
Le Routing Tables
• Ogni host ed ogni router coinvolto nella
consegna IP ha tabelle di instradamento (RT,
Routing Table)
• Ovviamente, le tabelle non possono avere
informazioni su ogni possibile destinazione
• Principio: nascondo l’informazione
• I router remoti instradano usando solo la
porzione di rete dell’indirizzo IP
STRATO RETE IN INTERNET - 45
Il Next-hop Routing
• Una tabella di routing contiene almeno due
informazioni:
– D indirizzo destinazione
R = next-hop
• D è normalmente un indirizzo di rete
• R è detto next-hop, e corrisponde ad un host
o un router raggiungibile direttamente
• Se è possibile mettere in relazione l’indirizzo
di destinazione del pacchetto in transito con
un indirizzo D delle RT, il pacchetto viene
inviato al relativo R
STRATO RETE IN INTERNET - 46
Next-hop Routing - esempio
Tabella del router A
rete
20.0.0.0
A
30.0.0.99
rete
30.0.0.0
rete
50.0.0.0
50.0.0.13
30.0.0.13
X
B
90.0.0.254
rete
90.0.0.0
INDIR. RETE
DESTINAZ.
NEXT
HOP
20.0.0.0
30.0.0.0
50.0.0.0
90.0.0.0
diretto
diretto
30.0.0.13
30.0.0.13
STRATO RETE IN INTERNET - 47
Instradamenti Default e Specifici
• Se il next-hop è unico (es: piccola sottorete
con unico router), le tabelle di instradamento
degli host possono contenere solo una
default route per l’esterno
• L’instradamento può essere specificato per
host (host specific route) e non per sottorete
per ragioni di:
– testing
– maggior sicurezza
STRATO RETE IN INTERNET - 48
Gestione delle Routing Tables
• Le tabelle di Routing sono fondamentali per il
funzionamento corretto di Internet
• Problemi da affrontare:
–
–
–
–
come inizializzare le RT?
quali informazioni devono contenere?
come aggiornarle?
consistenza tra RT e assenza di loop
STRATO RETE IN INTERNET - 49
Inizializzazione delle RT
• Dipende dal sistema operativo:
– lettura da un file di configurazione,
eventualmente scritto dall’operatore
– esecuzione di “comandi di scoperta” da inviare
sulla rete
– scambio di informazioni con altri host sulla rete
locale
STRATO RETE IN INTERNET - 50
La propagazione delle
Routing Tables
• Le RT possono cambiare a causa di:
– interventi sulle topologie
– guasti
– sovraccarichi
• L’informazione sui cambiamenti deve essere
propagata tra router mediante le procedure
previste dall’algoritmo di instradamento
utilizzato
STRATO RETE IN INTERNET - 51
Algoritmo di instradamento IP
• Estraggo dal pacchetto la parte netid
dell’indirizzo IP di destinazione (facile con
classi)
• Se sono collegato direttamente alla
destinazione, uso consegna diretta (ARP)
• altrimenti, cerco host specific route
• altrimenti, cerco next-hop memorizzato per
quella rete
• altrimenti, cerco default route
• altrimenti, dichiaro errore di routing
STRATO RETE IN INTERNET - 52
Conseguenze dell’introduzione
delle subbnet mask
• Gli host ed il router locale (solo quello!) deve
utilizzare AND tra indirizzo IP e maschera
per individuare il netid correttamente
• Devo memorizzare nella routing table dell
router locale anche le netmask
• Per gli altri ruoter non sono richieste
modifiche. Posso usare routing standard
STRATO RETE IN INTERNET - 53
Conseguenze dell’introduzione
del CIDR
• Introdotto (1992) per ridurre le RT e ovviare
all’imminente esaurimento della classe B
• Ad un sito che richiede più indirizzi IP questi
sono allocati in modo “contiguo”,
condividendo i bit più significativi
• Il risultato è l’occupazione di una sola “riga”
(per tutti gli indirizzi richiesti) nelle RT, che
sono consultate con il criterio del longest
match
STRATO RETE IN INTERNET - 54
Conseguenze dell’introduzione
del CIDR
• CIDR ha il vantaggio di permettere una
aggregazione degli indirizzi su base
topologica e geografica...
• ...ma lo svantaggio di complicare la funzione
di lookup perchè:
– è necessario fare confronti con prefissi a
lunghezza variabile (necessario memorizzare
nelle RT, oltre all’indirizzo di rete, anche la
relativa netmask)
– bisogna scorrere tutta la tabella per individuare il
prefisso con il longest match
STRATO RETE IN INTERNET - 55
CIDR: operazioni di un router
• Un router riceve un pacchetto con indirizzo
destinazione x.y.z.w
• Esegue AND bit a bit, per ogni riga delle R.T. tra:
– l’indirizzo di destinazione nella routing table e la netmask
– l’indirizzo ricevuto x.y.z.w e la stessa netmask
• Confronto i risultati degli AND: se sono uguali, ho
un matching
• Instrado secondo la riga delle R.T. che ha avuto il
maggior numero di bit di matching
STRATO RETE IN INTERNET - 56
Esempio CIDR
130.192.68.0 01000100
130.192.71.8
S
R
R2 130.192.71.0
R1
01000111
01110000
R3 130.192.120.0
STRATO RETE IN INTERNET - 57
Esempio CIDR
130.192.68.0 01000100
130.192.71.8
R2 130.192.71.0
S
R
R3 130.192.120.0
R.T.
130.192.68.0
01000111
R1
255.255.192.0 R1
11000000
01110000
STRATO RETE IN INTERNET - 58
Esempio CIDR
130.192.68.0 01000100
130.192.71.8
S
R
R.T.
130.192.68.0
R2 130.192.71.0
01000111
R1
R3 130.192.120.0
255.255.192.0 R1 (18)
01110000
STRATO RETE IN INTERNET - 59
Esempio CIDR
130.192.68.0 01000100
130.192.71.8
S
R
R2 130.192.71.0
01000111
R1
R.T.
R3 130.192.120.0
130.192.68.0 255.255.192.0 R2
130.192.120.0 255.255.240.0 R3
01110000
11110000
STRATO RETE IN INTERNET - 60
Esempio CIDR
130.192.68.0 01000100
130.192.71.8
S
R
R2 130.192.71.0
01000111
01110000
R1
R.T.
R3 130.192.120.0
130.192.68.0 255.255.192.0 R2 (18)
130.192.120.0 255.255.240.0 R3
STRATO RETE IN INTERNET - 61
Esempio CIDR
130.192.68.0 01000100
R2 130.192.71.0
S
R
R1
01000111
130.192.71.8 01110000
R.T.
130.192.68.0
130.192.71.0
R3 130.192.120.0
255.255.255.0 D
255.255.255.0 D
STRATO RETE IN INTERNET - 62
Esempio CIDR
130.192.68.0 01000100
R2 130.192.71.0
S
R
R1
R.T.
130.192.68.0
130.192.71.0
130.192.71.8
R3 130.192.120.0
255.255.255.0 D
255.255.255.0 D (24)
STRATO RETE IN INTERNET - 63
Come si ottengono indirizzi IP?
• Indirizzi di host in sottorete (host_id):
– liberi, configurati da amministratore di rete
• Wintel: control-panel->network->configuration->tcp/ip>properties
• UNIX: /etc/rc.config
• DHCP: Dynamic Host Configuration Protocol:
ottengo dinamicamente indirizzi:
– host inviano in broadcasts msg “DHCP discover”
– DHCP server risponde con “DHCP offer” msg
– host richiede indirizzo IP: “DHCP request” msg
– DHCP server invia indirizzo: “DHCP ack”
msg
STRATO
RETE IN INTERNET - 64
Come si ottengono indirizzi IP?
• Indirizzi di rete (net_id):
– si chiede una parzioni di indirizzi IP ad un ISP
ISP's block
11001000 00010111 00010000 00000000
200.23.16.0/20
Organization 0
11001000 00010111 00010000 00000000
200.23.16.0/23
Organization 1
11001000 00010111 00010010 00000000
200.23.18.0/23
Organization 2
...
11001000 00010111 00010100 00000000
…..
….
200.23.20.0/23
….
Organization 7
11001000 00010111 00011110 00000000
200.23.30.0/23
STRATO RETE IN INTERNET - 65
Come si ottengono indirizzi IP?
• Come ottiene indirizzi IP un ISP?
• ICANN: Internet Corporation for Assigned
– nomi e numeri
• alloca indirizzi
• gestisce DNS
• assegna nomi di dominio, risolve liti
STRATO RETE IN INTERNET - 66
Da sorgente a destinazione: esempio
tabella di routing in A
• Datagram IP:
source
misc
dest
fields IP addr IP addr
Dest. Net. next router
223.1.1
223.1.2
223.1.3
data
• datagram NON si
modifica da sorgente a
destinazione
• interessano solo campi
indirizzo
A
Nhops
1
2
2
223.1.1.4
223.1.1.4
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.1.3
223.1.3.1
223.1.2.9
223.1.3.27
223.1.2.2
E
223.1.3.2
STRATO RETE IN INTERNET - 67
Da sorgente a destinazione: esempio
misc
data
fields 223.1.1.1 223.1.1.3
• In A, noto indirizzo IP di
B:
– guardo net_id di B
– trovo che B appartiene
alla stessa sotto rete di A
– invio datagram
direttamente a B usando
indirizzo MAC
– B e A sono collegati
direttamente
Dest. Net. next router Nhops
223.1.1
223.1.2
223.1.3
A
1
2
2
223.1.1.4
223.1.1.4
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.1.3
223.1.3.1
223.1.2.9
223.1.3.27
223.1.2.2
E
223.1.3.2
STRATO RETE IN INTERNET - 68
Da sorgente a destinazione: esempio
misc
223.1.1.1 223.1.2.3
fields
data
Dest. Net. next router Nhops
• In A, noto IP di E:
223.1.1
223.1.2
223.1.3
– confronto net_id
– E su rete diversa
• A, E non sono collegati
direttamente
• tabella di routing: next
hop 223.1.1.4
• invio datagram al
router 223.1.1.4
usando indirizzo MAC
del router
A
1
2
2
223.1.1.4
223.1.1.4
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.1.3
223.1.3.1
223.1.2.9
223.1.3.27
223.1.2.2
E
223.1.3.2
STRATO RETE IN INTERNET - 69
Da sorgente a destinazione: esempio
misc
fields 223.1.1.1 223.1.2.3
data
• Arrivo a 223.1.1.4,
destinato a 223.1.2.2
• confronto net_id di E e
verifico che sono sulla
stessa rete con interfaccia
223.1.2.9
– router ed E attaccati
direttamente
• invio datagram a 223.1.2.2
con indirizzo MAC di E
Dest.
network
next
router
223.1.1
223.1.2
223.1.3
A
Nhops interface
-
1
1
1
223.1.1.4
223.1.2.9
223.1.3.27
223.1.1.1
223.1.2.1
B
223.1.1.2
223.1.1.4
223.1.1.3
223.1.3.1
223.1.2.9
223.1.3.27
223.1.2.2
E
223.1.3.2
STRATO RETE IN INTERNET - 70
Instradamento
Gruppo Reti TLC
[email protected]
http://www.tlc.polito.it/
STRATO RETE IN INTERNET - 71
Instradamento
• Obiettivo dei protocolli di instradamento:
– determinare un “buon” percorso (sequenza di
router) nella rete da sorgente a destinazione
• Grafo
– router sono nodi
– link fisici sono archi
• Costi su archi
5
2
A
B
2
1
D
– ritardo, euro, livello di congestione
3
C
5
F
1
3
E
1
2
• “Buon” percorso:
– tipicamente percorso a costo minimo
STRATO RETE IN INTERNET - 72
Classificazione algoritmi di routing
• Informazioni globale o decentralizzata?
• Globale:
– tutti i router conoscono la topologia completa,
compresi i costi dei canali
– scambio informazione tra tutti i router
– algoritmi link state
• Decentralizzata:
– i router conoscono i router cui sono fisicamente
collegati ed i costi dei canali cui sono collegati
– scambio di informazione solo con i router adiacenti
STRATO RETE IN INTERNET - 73
– algoritmi distance vector
Algoritmo Link-State
• Algoritmo di Dijkstra: determina cammini ottimi
• Tutti nodi conoscono topologia della rete e costi di
tutti i canali
– si inviano informazioni in broadcast
– tutti i nodi hanno stessa visione (completa) della rete
• Ogni nodo calcola i percorsi a minimo corso verso
tutti gli altri nodi
– si ottengono tabelle di routing per questo nodo
• Algortimo iterativo: dopo k iterazioni si ottengono i
cammini a costo minimo per k destinazioni
STRATO RETE IN INTERNET - 74
Algoritmo di Dijkstra
• Notazione:
• c(i,j): costo del canale dal nodo i al nodo j.
Infinito se nodo non collegato direttamente al
canale.
• D(v): valore corrente del percorso migliore da
sorgente alla destinazione v
• p(v): nodo che precede v nel percorso da
sorgente a destinazione v
• N: insieme di nodi per cui il cammino ottimo
e` noto
STRATO RETE IN INTERNET - 75
Algoritmo di Dijkstra
1 Initialization (nodo A):
2 N = {A}
3 per tutti i nodi v
4
if v adiacente ad A
5
then D(v) = c(A,v)
6
else D(v) = infty
7
8 repeat
9 trova w not in N tale per cui D(w) e` minimo
10 aggiungi w ad N
11 aggiorna D(v) per tutti i v adiacenti a w e not in N:
12
D(v) = min( D(v), D(w) + c(w,v) )
13 /* il nuovo costo verso v e` o il vecchi costo verso v o il cammin
14 cammino a minimo costo verso w piu` costa da w a v*/
15 until tutti i nodi in N
STRATO RETE IN INTERNET - 76
Dijkstra: esempio
Step
0
1
2
3
4
5
start N
A
AD
ADE
ADEB
ADEBC
ADEBCF
D(B),p(B)
2,A
2,A
2,A
D(D),p(D)
1,A
D(C),p(C)
5,A
4,D
3,E
3,E
D(E),p(E)
infinity
2,D
D(F),p(F)
infinity
infinity
4,E
4,E
4,E
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
STRATO RETE IN INTERNET - 77
Algoritmo di Dijkstra: proprietà
• Complessità con n nodi
• Ogni iterazione: controllo tutti i nodi w not in N
– n*(n+1)/2 confronti: O(n**2)
• Esistono implementazioni migliori: O(nlogn)
• Possibili oscillazioni:
– Esempio: costo canali legato al carico trasportato
D
1
A
1
0
0
C
e
1+e
0
B
e
2+e
D
0
1
Situazione inziale
A
1+e 1
C
0
B
0
… ricalcolo percorsi
0
D
1
A
2+e
0 0
B
C 1+e
… ricalcolo
2+e
D
0
A
1+e 1
C
0
B
e
…ricalcolo
STRATO RETE IN INTERNET - 78
Distance Vector
• Algoritmo iterativo:
– continua fino a quando I nodi non scambiano
piu` informazioni
• Termina in modo autonomo:
– nessun segnale esplicito di fine algoritmo
• Asincrono
– scambio informazioni necessario solo se
cambiamento di stato
• Distribuito:
– ogni nodo comunica solo con nodi adiacenti
STRATO RETE IN INTERNET - 79
L’algoritmo Distance Vector
• Ogni router scambia periodicamente con i
vicini diretti un vettore contenente:
– le destinazioni (reti) che può raggiungere
– la distanza dalle destinazioni misurata in hop
(num. router da attraversare compreso se
stesso)
• Il router che riceve il vettore lo confronta con
le proprie RT ed effettua modifiche:
– aggiunge nuove reti
– cambia instradamenti se nuovi sono più brevi
STRATO RETE IN INTERNET - 80
L’algoritmo Distance Vector
Destinazione
Net 1
Net 2
Net 4
Net 17
Net 24
Net 30
Net 42
Distanza
1
1
8
5
6
2
2
Routing Tables
del router K
Route
Distance
Vector
spedito dal
router J
Diretta
Diretta
Router L
Router M
Router J
Router Q
Router J
K
Destinazione Distanza
J
Net 1
Net 4
Net 17
Net 21
Net 24
Net 30
Net 42
2
3
6
4
5
10
3
STRATO RETE IN INTERNET - 81
L’algoritmo Distance Vector
• Vantaggi
– facile da implementare
• Problemi:
– lento a convergere
– propaga errori di routing
– non molto scalabile (le dimensioni dei messaggi
scambiati dai router crescono al crescere della
rete)
STRATO RETE IN INTERNET - 82
Distance Vector
• Struttura dati: tabella distanze
• Ogni nodo possiede la propria
– Una riga per ogni possibile destinazione
– Una colonna per ogni router adiacente
• Esempio: nel nodo X, per la destinazione Y
attraverso nodo adiacente Z:
X
D (Y,Z)
distanza da X ad Y,
= via Z come next hop
Z
= c(X,Z) + min {D (Y,w)}
w
STRATO RETE IN INTERNET - 83
Tabella distanze: esempio
Costo verso destinazione
7
A
B
1
E
2
attraverso nodo
E
2
8
1
C
D
E
D ()
A
B
D
A
1
14
5
B
7
8
5
C
6
9
4
D
4
11
2
D
D (C,D) = c(E,D) + min {D (C,w)}
= 2+2 = 4
w
E
D
D (A,D) = c(E,D) + min {D (A,w)}
E
w
= 2+3 = 5
anello!
B
D (A,B) = c(E,B) + min {D (A,w)}
= 8+6 = 14
w
anello!
STRATO RETE IN INTERNET - 84
Tabella di instradamento a partire
da tabella distanze
Costo verso destinazione
atttraverso nodo
E
Canale di uscita
D ()
A
B
D
A
1
14
5
A
A,1
B
7
8
5
B
D,5
C
6
9
4
C
D,4
D
4
11
2
D
D,4
Tabella distanze
da usare, costo
Tabella di Routing
STRATO RETE IN INTERNET - 85
Instradamento Distance Vector
• Iterativo, asincrono: una iterazione (locale al
nodo) causata da:
– modifica costo canale a cui nodo collegato
– messaggio ricevuto da nodo adiacente, che
causa modifica del cammino ottimo
• Distribuito:
– ogni nodo avvisa i vicini solo quando il suo
cammino migliore verso una certa destinazione
e` cambiato
– i vicini avviseranno a loro volta nodi vicini se
necessario
STRATO RETE IN INTERNET - 86
Instradamento Distance Vector
• Ogni nodo esegue un loop infinito
– aspetta
• modifica costo canale locale oppure
• messaggio da nodo adiacente
– ricalcola tabella distanze
– se percorso migliore verso qualche destinazione
cambiato, avvisa i vicini
STRATO RETE IN INTERNET - 87
Algoritmo Distance Vector
Ad ogni nodo X:
1 Inizializzazione:
2 per tutti i nodi adiacenti v:
3
D X(*,v) = infinito
4
D X(v,v) = c(X,v)
/* l’operatore * significa ”per ogni riga" */
5 per tutte le destinazioni, y
6
invia min DX(y,w) verso ogni nodo adiacente /* w sono tutti i vicini di X*/
w
STRATO RETE IN INTERNET - 88
Algoritmo Distance Vector
8 loop
9 wait (until I see a link cost change to neighbor V
10
or until I receive update from neighbor V)
11
12 if (c(X,V) changes by d)
13 /* change cost to all dest's via neighbor v by d */
14 /* note: d could be positive or negative */
X = D (y,V)
X +d
15 for all destinations y: D (y,V)
16
17 else if (update received from V wrt destination Y)
18 /* shortest path from V to some Y has changed */
19 /* V has sent a new value for its min DV(Y,w) */
w
20 /* call this received new value is "newval" */
X = c(X,V) + newval
21 for the single destination y: D (Y,V)
22
X
23 if we have a new min D (Y,w)for
any destination Y
w
X to all neighbors
24
send new value of min D (Y,w)
w
25
26 forever
STRATO RETE IN INTERNET - 89
Distance Vector: esempio
X
2
Y
7
1
Z
X
Z
X
Y
D (Y,Z) = c(X,Z) + min w{D (Y,w)}
= 7+1 = 8
D (Z,Y) = c(X,Y) + min w{D (Z,w)}
= 2+1 = 3
STRATO RETE IN INTERNET - 90
Distance Vector: esempio
X
2
Y
7
1
Z
STRATO RETE IN INTERNET - 91
Algoritmo DV: modifica costo canale
• Nodo riconosce modifica costo canale 1 Y
4
• Modifica tabella distanze (passo 15) X
50
• Se modifica implica modifica del cammino
migliore avvisa nodi adiacenti (passi 23,24)
“good
news
travels
fast”
1
Z
algoritmo
termina
STRATO RETE IN INTERNET - 92
Algoritmo DV: modifica costo canale
Modifica costo canale:
• good news travels fast
• bad news travels slow problema del “count to infinity”!
60
X
4
Y
50
1
Z
algoritmo
prosegue
STRATO RETE IN INTERNET - 93
Distance Vector: poisoned reverse
Se Z instrada via Y per raggiungere X:
60
• Z comunica ad Y sua distanza verso X e` infinito (Y
non instraderà verso X passando da Z)
X
• non risolve il problema completamente
4
Y
50
1
Z
algoritmo
termina
STRATO RETE IN INTERNET - 94
Confronto tra algoritmi LS e DV
• Complessità messaggi
– LS: con n nodi, E canali, ogni nodo invia O(nE)
messaggi
– DV: scambio messaggio solo tra nodi adicenti
• tempo di convergenza variabile
• Velocità di convergenza
– LS: algoritmo di complessità O(n**2) richiede O(nE)
messaggi
• puo` oscillare
– DV: tempo di convergenza variabile
• errori di routing creano anelli
• problema del count-to-infinity
STRATO RETE IN INTERNET - 95
Confronto tra algoritmi LS e DV
• Affidabilità: cosa succede se un router
funziona non correttamente?
• LS:
– i nodi possono annunciare costi dei canali
scorretti
– ogni nodo calcola la propria tabella
• DV:
– i nodi possono annunciare costi dei cammini
scorretti
– ogni tabella e` usata da tutti i nodi
• gli errori si propagano nella rete
STRATO RETE IN INTERNET - 96
Indirizzamento gerarchico:
aggregazione dei percorsi
• Indirizzamento gerarchico permette annunci
(invio info) efficienti delle informazioni di
instradamento
Organizzazione 0
200.23.16.0/23
Organizzazione 1
200.23.18.0/23
Organizzazione 2
200.23.20.0/23
.
.
Organizzazione 7.
200.23.30.0/23
“Inviami qualunque pacchetto
con indirizzi che iniziano per
200.23.16.0/20”
.
.
.
ISP B
Internet
ISP A
“Inviami qualunque pacchetto
con indirizzi che iniziano con
199.31.0.0/16”
STRATO RETE IN INTERNET - 97
Indirizzamento gerarchico:
aggregazione dei percorsi
• Se ISP A ha un percorso piu` specifico verso
Organizzazione 1
Organizzazione 0
200.23.16.0/23
Organizzazione 2
200.23.20.0/23
.
.
Organizzazione 7.
200.23.30.0/23
“Inviami pacchetti con indirizzi
che iniziano con
200.23.16.0/20”
.
.
.
ISP B
Internet
ISP A
Organizzazione 1
200.23.18.0/23
“Inviami pacchetti con indirizzi
che iniziano con
199.31.0.0/16
orppure 200.23.18.0/23”
STRATO RETE IN INTERNET - 98
Algoritmi di instradamento
in reti IP
Gruppo Reti TLC
[email protected]
http://www.tlc.polito.it/
STRATO RETE IN INTERNET - 99
Routing gerarchico
• Per ora caso ideale
– tutti router identici
– rete “piatta”, non gerarchica
• Approccio non utilizzabile in pratica
– scalabilità: con 50 milioni di destinazioni:
• tutte destinazioni in una tabella?
• Scambio di info di routing occuperebbe troppo canali
– Autonomia amministrativa
• internet = rete di reti
• ogni amministratore di rete puo` volere controllare
instradamento sulla propria rete
STRATO RETE IN INTERNET - 100
Routing gerarchico
• Router aggregati in regioni, dette
Autonomous System (AS)
– Insieme di router con struttura complessa (molte
sottoreti e router) ma unica identità
amministrativa
– Router nello stesso AS usano stesso protocollo
di instradamento
– Protocolli di instradamento intra-AS (IGP: Interior
Gateway Protocol)
• Router in AS diversi possono usare protocolli IGP
diversi (aggiornamento e validazione circoscritti)
STRATO RETE IN INTERNET - 101
Routing gerarchico
• In ogni AS devono esistere router “gateway”
• responsabili per instradare verso destinazioni esterne
all’AS
• usano protocolli inter-AS (EGP: Exterior Gateway
Protocol) con altri router gateway
• usano protocolli intra-AS con tutti altri router dell’AS
• Si parla quindi di routing interno (IGP) ed
esterno (EGP)
STRATO RETE IN INTERNET - 102
Routing Intra-AS and Inter-AS
C.b
a
C
Gateways:
B.a
A.a
b
A.c
A
d
a
b
c
a
c
B
b
•eseguono instradamento
inter-AS tra loro
•eseguono instradamento
intra-AS con altri router
nel loro AS
network layer
inter-AS, intra-AS
routing in
gateway A.c
link layer
physical layer
STRATO RETE IN INTERNET - 103
Routing Intra-AS and Inter-AS
C.b
a
Host
h1
C
A.a
b
Inter-AS routing
tra AS A e B B.a
A.c
d
a
c
b
A
Intra-AS routing
all’interno dell’AS A
a
c
B
Host
h2
b
Intra-AS routing
all’iterno dell’AS B
STRATO RETE IN INTERNET - 104
Definizione di un AS
• I “confini” tra AS devono essere ben definiti
per non creare confusione tra gli algoritmi di
routing
• A ciascun AS viene assegnato un numero di
ID su 16 bit da una authority centrale
(INTERNIC, APNIC, RIPE-NCC)
• Quando due router si scambiano
informazioni di raggiungibilità, i messaggi
contengono l’ID dell’AS a cui appartengono
STRATO RETE IN INTERNET - 105
Traffico locale e in transito
• Definiamo “traffico locale” ad un AS il traffico
IP che:
– ha come sorgente un host dell’AS
– ha come destinazione un host dell’AS
• In tutti gli altri casi, si tratta di “traffico in
transito” sull’AS
STRATO RETE IN INTERNET - 106
Autonomous Systems (AS)
• Gli AS sono origine/transito/destinazione del
traffico inter-dominio
• Tre categorie di AS:
– stub: connesso ad un unico AS, accetta solo
traffico locale
– multihomed: connesso a piu’ AS, accetta solo
traffico locale
– transit: connesso a piu’ AS, accetta anche
traffico in transito
STRATO RETE IN INTERNET - 107
EGP: Exterior Gateway Protocol
• Storicamente, il primo protocollo usato dagli
AS per diffondere informazioni di
raggiungibilità
• I router che lo usano sono detti router esterni
(exterior routers)
• Presuppone una rete con topologia ad albero
(come la “vecchia” ARPAnet)
• EGP va in crisi con l’introduzione di dorsali e
cammini multipli tra due host e per questo
motivo è stato sostituito con BGP
STRATO RETE IN INTERNET - 108
Funzioni di EGP
• Neighbor Acquisition: un router richiede ad
un “vicino” di accordarsi per comunicare
• Neighbor reachability: un router controlla
sempre se i suoi “vicini” sono raggiungibili
• Network reachability: i “vicini” si scambiano
sempre informazioni di raggiungibilità
STRATO RETE IN INTERNET - 109
EGP: Osservazioni e problemi
• Non propaga distanze tra reti, ma solo
raggiungibilità
• Presuppone un core system, non funziona
con l’attuale struttura a dorsali multiple
• Non supporta load sharing né cammini
alternativi
• Non supporta il policy routing
• Va in crisi con router malfunzionanti
(pubblicizzano route inconsistenti)
STRATO RETE IN INTERNET - 110
Da EGP a BGP
• La crescita nella complessità della topologia
Internet (backbone multiple) rende
inutilizzabile EGP (anelli)
• alternative?
– Protocolli link state (non realistico)
– Path-vector
STRATO RETE IN INTERNET - 111
BGP: Border Gateway Protocol
• E’ il più diffuso EGP in Internet
• BGP permette di specificare politiche di
instradamento per scegliere il cammino
migliore in presenza di scelte multiple
• Le politiche di instradamento sono
espressione di considerazioni economiche e
gestionali, e tengono conto di aspetti di
sicurezza
STRATO RETE IN INTERNET - 112
Path Vectors
• Ogni routing update trasporta un elenco di AS
necessari per raggiungere una certa destinazione
• Se un AS compare due volte, riconosco anello
• Vantaggi:
– non creo anelli
– non sono obbligato ad usare la stessa metrica per ogni
router
• Svantaggi:
– overhead (una entry per ogni AS che annucio nel path
vector)
STRATO RETE IN INTERNET - 113
BGP: Border Gateway Protocol
• Protocollo di instradamento esterno (or interAS) basato su path vector
• Funzione principale: scambiare informazioni
di raggiungibilità
• Ultimo RFC: 1771 (BGP-4), in corso di
aggiornamento
STRATO RETE IN INTERNET - 114
BGP: riassunto
• Due router che usano BGP aprono una
connessione utilizzando TCP
• Inizialmente scambiano le tabelle di
instradamento di BGP
• In caso di modifiche si inviano aggiornamenti
incrementali
• Non sono necessari aggiornamenti periodici
(sono inviati periodicamente solo messaggi
di KEEPALIVE)
STRATO RETE IN INTERNET - 115
BGP peering
AS 1
external
peers
AS 2
AS 3
internal
peers
AS 4
STRATO RETE IN INTERNET - 116
BGP messages
• Dimensione variabile tra 19 e 4096 bytes
• L’intestazione contiene:
– autenticazione
– lunghezza messaggio
– tipo messaggio
•
•
•
•
OPEN (first msg)
UPDATE
NOTIFICATION (of error condition)
KEEPALIVE
STRATO RETE IN INTERNET - 117
Messaggi di UPDATE
• Usato per:
– annunciare una nuovo percorso ammissibile
verso un peer router
AND/OR
– annullare percorsi inammissibili
BGP Header
Unfeasible Routes length (2 bytes)
Withdrawn routes (variable)
Total Path Attribute Length (2 bytes)
Path attributes (variable, as many as necessary)
Network Layer Reachability Information (variable)
STRATO RETE IN INTERNET - 118
Messaggi di UPDATE
• Percorsi da annullare sono identificati
mediante le destinazioni (come neti_d IP)
• I path attributes descrivone i nuovi percorsi
(uno per ogni messaggio di UPDATE)
• Gli attributi di path si riferiscono alla
destinazione specificata (utilizzando il netid
dell’indirizzo IP) nel campo Network Layer
Reachability Information
STRATO RETE IN INTERNET - 119
Routing in un AS
• I router di un AS sono detti interni
• Problema: come fa un router interno a
conoscere gli instradamenti dentro l’AS?
– Aggionamenti manuali? Forse per AS di piccole
dimensioni... se cambia una rete, bisogna
modificare le tabelle di routing su ogni host
(richiede tempo e può dare errori)
– Aggiornamenti automatici
STRATO RETE IN INTERNET - 120
Routing in un AS
• In un AS, i router interni si scambiano dati di
raggiungibilità per le reti dell’AS
• Un protocollo per router interni si chiama,
genericamente, IGP (Interior Gateway
Protocol )
• A differenza di EGP, non esiste un unico
standard per i protocolli interni
• Algoritmi di routing interno più diffusi:
– RIP (implementazione di distance vector)
– OSPF (implementazione di link state)
STRATO RETE IN INTERNET - 121
Routing Information Protocol
(RIP)
• Nato presso l’Univ. di Berkeley per servire la
loro (piccola) rete locale, e distribuito nella
suite UNIX 4BSD (routed)
• Adottato prima che ne fosse definito uno
standard (il primo RFC è del 1988)
• Oggi ha vasta diffusione anche in AS di
grandi dimensioni
STRATO RETE IN INTERNET - 122
RIP: caratteristiche
• Usa una implementazione di distance vector
• Divide gli host in attivi (router) e passivi
• Gli host attivi pubblicizzano le loro route a
tutti gli altri ogni n (di solito 30s) secondi,
sotto forma di coppie (indirizzo, n. di hop)
• Metrica e` numero di hop
• Se un router rileva un instradamento a costo
strettamente inferiore a quello che ha nelle
RT, lo sostituisce (e imposta un timeout pari
a 180s)
STRATO RETE IN INTERNET - 123
RIP: un esempio di problemi
Net 1
R1
Net 2
R2
R3
Net 3
R4
R5
Net 4
Net 5
STRATO RETE IN INTERNET - 124
RIP: un esempio di problemi
• R1 dichiara Net 1 a distanza 1
• R2 ed R3 inseriscono una entry che dichiare
Net 1 a distanza 2
• R4 ed R5 inseriscono una entry che dichiare
Net 1 a distanza 3
• R1 perde connettività e dichiara distanza
infinita (16) su Net1
• Se nel frattempo pero` R2 e/o R3 dichiarano
distanza 2 verso Net 1, R1 inserisce entry
che dichiara Net 1 a distanza 3
STRATO RETE IN INTERNET - 125
RIP: problemi
• Si converge lentamente crescendo le
distanze di 1 ad ogni routing updates
• Data la lentezza di propagazione, si possono
avere problemi di lenta convergenza o non
consistenza delle RT (count to infinity)
• Non riconosce automaticamente eventuali
loop (occorrono interventi esterni, o
modifiche al protocollo)
• I problemi nascono dal numero limitato di
informazioni scambiate tra i router (solo 2) e
STRATO RETE IN INTERNET - 126
RIP: soluzioni
• Split horizon con poisoning reverse: non
propagare informazioni di raggiungibilità
dall’interfaccia con cui si raggiunge la
destinazione
– R2 non propaga distanza 2 e dopo un tempo
breve tutti dichiarano distanza 16
• Non basta!
– R2 propaga su Net 3 distanza 2 verso Net 1
– R3 propaga su Net 3 distanza 3 verso Net 1
– R2 accetta distanza 4 verso Net 1
RETE IN INTERNET - 127
– Nessuno usa distanza 16 propagata STRATO
da R1
RIP: altre soluzioni
• Il router che vede rete disconnessa mantiene
questa informazione per un tempo molto
superiore al periodo di peridodico
aggiornamento
– R1 mantiene distanza 16 anche se riceve
informazione da R2 di distanza 2
• Triggering updates: quando vedo rete non
piu` connessa forzo update immediatamente
– R1 immediatamente informa che Net 1 e` a
distanza 16
– Rischioso perche` posso creare broadcast
STRATO RETE IN INTERNET - 128
ripetuti su LAN
L’algoritmo IGRP
• IGRP (Interior Gateway Routing Protocol)
venne proposto da Cisco Systems Inc. a
metà degli anni ‘80 per superare le limitazioni
di RIP
• E’ un algoritmo distance vector con metriche
più sofisticate: ritardo, banda, affidabilità,
carico
• Permette il multipath routing
• Limite: è solo disponibile sui router Cisco
STRATO RETE IN INTERNET - 129
L’algoritmo OSPF
• OSPF (Open Shortest Path First ) è una
proposta di IETF dell’89 [RFC 1247]
• E’ un algoritmo link-state: ogni router verifica
lo stato delle linee verso i router adiacenti e
lo invia a tutti i router conosciuti
• Ogni router si costruisce una mappa
completa della rete su cui calcole le route
con algoritmi sofisticati (SPF o alg. di
Dijkstra)
STRATO RETE IN INTERNET - 130
RIP e OSPF
• RIP:
– invia informazioni su
tutte le subnet solo ai
router adiacenti
– i router cooperano
direttamente per
calcolare le tabelle di
instradamento
• OSPF:
– invia a tutti i router noti
informazioni solo sulle
subnet a cui sono
connessi
– i router cooperano per
aggiornare la mappa
della rete, ma poi
ciascuno si calcola le
RT in modo autonomo
STRATO RETE IN INTERNET - 131
OSPF: caratteristiche
• Discrimina i percorsi verso una stessa
destinazione secondo il campo TOS
• E’ più veloce a convergere di RIP, ed esegue
il bilanciamento del carico sulle linee a costo
uguale verso una stessa destinazione
• Ad ogni interfaccia del router può essere
assegnato un costo adimensionale basato su
throughput, RTT, affidabilità o altro
• Connessioni punto-punto tra router OSPF
non necessitano di indirizzi IP per
l’interfaccia (risparmio!)
STRATO RETE IN INTERNET - 132