4.2 Internet IP Parte2

7/23/2019 4.2 Internet IP Parte2

http://slidepdf.com/reader/full/42-internet-ip-parte2 1/31

Parte IV

Interconnessione di rete

Instradamento in Internet

Parte IV

Interconnessione di rete

Instradamento in Internet

Instradamento IP



Router IP

q I router IP ricevono datagrammi IP da un’interfaccia e

li inoltrano su un’altra

q Si distinguono dagli Host perché:ä hanno in genere più di un’interfaccia

ä utilizzano “protocolli di routing” più sofisticati

q I router IP hanno (normalmente) un indirizzo IP perogni interfaccia.

Instradamento dei datagrammi

q Ogni datagramma IP attraversa un camminocomposto da router e da sotto-reti

q Quando un router consegna un datagramma ad unasotto-rete questo diventa l’unità dati di serviziopropria di quella sotto-rete

q La sotto-rete consegna poi tale unità dati al prossimorouter o a destinazione (se la destinazione èall'interno della sotto-rete stessa) con le stessemodalità con cui tratta le unità dati ad essa"appartenenti"



Instradamento di datagrammi IP

Instradamento diretto

Instradamento indiretto

Sotto-rete 1

Sotto-rete 2

Router 1Host 1

Host 2

Host 3


Instradamento diretto

q La trasmissione di un datagramma IP tra duemacchine connesse su una stessa sotto-rete (stessonet_id) non coinvolge i router

q Il trasmettitore IP risolve l’indirizzo fisico dell’hostdestinatario, incapsula il datagramma nell’unità datidella rete fisica e lo invia verso destinazione

q Utilizza i meccanismi propri della rete fisica inquestione per inviare il datagramma




Instradamento indiretto

q L’host di destinazione non è sulla stessa sotto-rete del mittente

q Il mittente deve identificare un router a cui inviare il datagramma; ilrouter deve inviare il datagramma verso la sotto-rete di destinazione. Irouter non si occupano dell'instradamento attraverso le sotto-reti

l Il mittente invia il datagramma al router più vicino utilizzando lasotto-rete fisica a cui è connesso

l Il router esamina il datagramma ricevuto e decide verso quale altrorouter instradarlo

l Il processo si ripete di router in router finché si arriva alla sotto-rete di destinazione; qui tramite un instradamento diretto ildatagramma viene inviato allo specifico host di destinazione

l I router formano una struttura inter-connessa e cooperativa. Idatagrammi passano di router in router finché ne raggiungono unoche può consegnare il datagramma direttamente (cioè tramite uninoltro diretto)

q Per effettuare l’instradamento diretto è necessarioassociare l’indirizzo IP del destinatario con l’indirizzo fisico corrispondente

q Associazione staticao la tabella di associazione viene predisposta staticamente (ad esempio rete X.25,

ISDN, etc.)

q Associazione dinamicao la tabella viene costruita dinamicamente attraverso un protocollo ARP (AddressResolution Protocol) RFC826

– broadcast (sulle LAN) – ARP-Server (su reti Non Broadcast)

A B

C D E

A Bmessaggiobroadcast

richiestarisposta

C D E

IP: Risoluzione degli Indirizzi



Traduzione di indirizzi

q Nella rete sono presenti 3 livelli di indirizzamento:o Indirizzi MAC (ad es. 6 byte per LAN IEEE 802)

o Indirizzi IP (4 byte)

o Indirizzi simbolici (host names, URL)

q Il modello di rete ad overlay non prevede unmetodo diretto e/o algoritmico di associazione fra idiversi spazi di indirizzamento, per cui si rendononecessari dei protocolli di risoluzione degliindirizzi:

MAChostname

IP

ARPDNS

Address Resolution Protocol (ARP)

q Il protocollo ARP (Address Resolution Protocol)fornisce un meccanismo dinamico di associazionefra indirizzi MAC ed indirizzi IP

q Viene utilizzato ogni qual volta un nodo di una LANdeve inviare un pacchetto ad un altro nodo, sullastessa LAN, di cui però conosce solo l’indirizzo IP

q Il RARP (Reverse Address Resolution Protocol)realizza l’associazione inversa, ossia associa ad unindirizzo MAC il corrispondente indirizzo IP

o Si usa al bootstrap nei sistemi diskless

o È basato su un paradigma Client/Server



ARP/RARP

q Il formato dei pacchetti è identico per ARP e RARP

q ARP/RARP si appoggiano direttamente sullo strato MAC (non su IP). Ciòsignifica che un opportuno campo nell’intestazione della MAC-PDU indica se ilcontenuto deve essere consegnato a ARP,RARP o IP.

q ARP prevede caching delle informazioni [ > arp -a visualizza il contenuto dellacache]

hard

type

prot

size

hard

size

prot

typeoperation

sender

Ethernet Address

sender

IP Address

target

Ethernet Address

target

IP Address

2 12 1 2 6 4

Ethernet dataEthernet Header FCS

4

MAC-source addr. (6 bytes)

MAC-dest. addr. (6 bytes)

Type (2 bytes) - 0800 IP, 0806 ARP, 8035 ARP

hard

type

prot

size

hard

size

prot

typeoperation

sender

Ethernet Address

sender

IP Address

target

Ethernet Address

target

IP Address

2 12 1 2 6 4

Ethernet dataEthernet Header FCS

4

MAC-source addr. (6 bytes)

MAC-dest. addr. (6 bytes)

Type (2 bytes) - 0800 IP, 0806 ARP, 8035 ARP

Messaggi ARP

Subnet 192.168.10.0/24

.10 .35

MAC-D 00:00:00:00:00:00

MAC-S 00:08:2C:78:58:52

IP-D 192.168.10.35

IP-S 192.168.10.10

MAC-D 00:00:00:00:00:00

MAC-S 00:08:2C:78:58:52

IP-D 192.168.10.35

IP-S 192.168.10.10

MAC 00:08:2C:78:58:52 MAC 00:00:60:AD:87:44

.11 .15 .16 .20

ARP request

TO: ff:ff:ff:ff:ff:ff:

Ogni postazione aggiunge la coppia

MAC/IP alla propria cacheMAC-D 00:00:60:AD:87:44

MAC-S 00:08:2C:78:58:52

IP-D 192.168.10.35

IP-S 192.168.10.10

MAC-D 00:00:60:AD:87:44

MAC-S 00:08:2C:78:58:52

IP-D 192.168.10.35

IP-S 192.168.10.10

ARP reply

TO: 00:08:2C:78:58:52



Esempio ARP n.1

C:\>arp -a

Interfaccia: 150.24.37.30 on Interface 0x1000002

Indirizzo internet Indirizzo fisico Tipo

150.24.37.6 20-53-52-43-00-00 dinamico150.24.37.12 20-53-52-43-00-00 dinamico

150.24.37.84 20-53-52-43-00-00 dinamico

150.24.37.86 20-53-52-43-00-00 dinamico

In questoesempio gliindirizzi fisici

sono tuttiuguali perché èun modem

C:\>arp -a

Interfaccia: 151.100.37.83 on Interface 0x1000003

Indirizzo Internet Indirizzo fisico Tipo

150.24.37.12 00-50-da-49-bb-63 dinamico

150.24.37.14 00-a0-c9-41-11-dd dinamico

150.24.37.111 00-60-6c-12-21-cc dinamico

Tabelle di instradamento




q Il meccanismo per l’instradamento in IP è basato su una tabella

che ogni host e router mantiene allo scopo di conoscere lepossibili destinazioni e le modalità per raggiungerle

q Una tabella di instradamento (routing table) contiene delle triple(R,M,I) dove R è l’indirizzo della rete di destinazione M lamaschera di rete associata ad R ed I è l’indirizzo del prossimorouter lungo la strada che porta alla rete di destinazione

q La tabella di instradamento specifica quindi solo un passolungo il cammino verso la destinazione

q Un router non conosce quindi il cammino completo che il

datagramma dovrà compiere

Tabella di instradamento di R2 (semplificata)

20.0.0.5

20.0.0.6

130.11.0.6

213.2.97.7

130.11.0.7

Rete11.0.0.0

Rete20.0.0.0

Rete130.11.0.0R1 R2 R3

11.0.0.5

Rete213.2.97.0

Rete

213.2.98.0

213.2.98.12

Rete di

DestinazioneR

Next hop

(Prossimo router)I

20.0.0.0 instrada direttamente (20.0.0.6)

130.11.0.0 instrada direttamente (130.11.0.6)

11.0.0.0 20.0.0.5

213.2.97.0 130.11.0.7

213.2.98.0 130.11.0.7


MascheraM

255.0.0.0

255.255.0.0

255.0.0.0

255.255.255.0

255.255.255.0




q Al fine di mantenere piccole le tabelle diinstradamento e realizzare un instradamento

efficiente, le tabelle contengono solo informazionisulle reti di destinazione e non sui singoli nodi

q Se un router non trova nella sua tabella diinstradamento un’entrata relativa ad una certa sotto-rete, allora se è presente, indirizza i suoi datagrammiverso il “router di default”

q Il meccanismo del router di default è usato:

o sia da piccoli host, al quale in genere vengono inviati tutti i

datagrammi non diretti alla sotto-rete a cui sono connessio sia da router o host con tabelle che non coprono tutte le

possibili destinazioni


Instradamento del router X:

1) estrai l’indirizzo IP di destinazione dal datagramma(=Y)

2) se è presente una richiesta di instradamento esplicitosu un dato percorso (nel campo Source RouteOption) instradalo come richiesto

3) se l’indirizzo di destinazione Y coincide con X (ladestinazione è il router X), estraine il contenutoinformativo e consegnalo al protocollo indicato

4) decrementa il Time To Live del datagramma; se ilTime To Live è arrivato a zero scarta il datagramma edanne comunicazione all’host mittente (utilizzando ilprotocollo ICMP)




5) confronta la componente XandM con YandM (M

maschera di rete del router X), se sono uguali inoltrail datagramma direttamente (→ ARP)

6) Per tutte le righe della tabella di instradamento[R,M,I] confronta se XandM = RandM (R indirizzodella sotto-rete, M maschera di sotto-rete ed I ind.prossimo router). Inoltra il datagramma verso ilrouter I relativo alla corrispondenza con la mascherapiù lunga

7) altrimenti (non c’era nessuna corrispondenza) inoltra

verso il default router se ne è stato specificato unooppure dichiara errore di instradamento (ICMP)

Operatore AND

213.2.97.0 11010101.00000010.01100001.00000000

213.2.96.0 11010101.00000010.01100000.00000000

255.255.252.0 11111111.11111111.11111100.00000000

AND AND

= =

1

1AND

=

1

1

0AND

=

0

0

1AND

=

0

0

0AND

=

0

R

M

RandM



Esempio di instradamento

H1 R1 H2

195.168.14.0/24 195.168.12.0/24195.168.14.2

195.168.14.1

eth0

195.168.12.1

eth1

195.168.12.2eth2

Destination Gateway Genmask Iface

195.168.14.0 195.168.14.2 255.255.255.0 eth0

127.0.0.0 127.0.0.1 255.0.0.0 lo

0.0.0.0 195.168.14.1 0.0.0.0 eth0

Tabella di instradamento di H1

Come procede l’instradamento di un pacchetto indirizzato a:

a) 195.168.14.5b) 195.168.12.2

c) 195.168.14.2

Destination Gateway Genmask Iface

195.168.14.0 195.168.14.2 255.255.255.0 eth0

127.0.0.0 127.0.0.1 255.0.0.0 lo

0.0.0.0 195.168.14.1 0.0.0.0 eth0

1) 195.168.14.5 AND 255.255.255.0 = 195.168.14.0 è uguale a 195.168.14.0?

2) 195.168.14.5 AND 255.0.0.0 = 195.0.0.0 è uguale a 127.0.0.0?

3) 195.168.14.5 AND 0.0.0.0 = 0.0.0.0 è uguale a 0.0.0.0?

Indir izzo IP Destinazione AND Mask == Dest inat ion AND Mask ?

Nota: Destination AND Mask = Destination

Indirizzo IP di destinazione del pacchetto: 195.168.14.5

SI

SI

NO

Tra i record c he dann o SI qual è quello con la masc hera più lun ga? Il n.1

E’ instradamento di ret to o ind i ret to?

Ci sono cas i in cui i l record n.3 non d a corr ispondenza ?

Esempio di instradamento



Interfaccia di loopback

C:\>ping localhost

Esecuzione di Ping xxx [127.0.0.1] con 32 byte di dati:

Risposta da 127.0.0.1: byte=32 durata=1ms TTL=128

Risposta da 127.0.0.1: byte=32 durata<10ms TTL=128



Statistiche Ping per 127.0.0.1:

Pacchetti: Trasmessi = 4, Ricevuti = 4, Persi = 0 (0% persi),

Tempo approssimativo percorsi andata/ritorno in millisecondi:

Minimo = 0ms, Massimo = 1ms, Medio = 0ms

Funzioni di

ingresso IP

Funzioni di

uscita IP

Metti nella

coda diingresso

IP

LoopbackDriver

IP

Server/Client Client/Server

Interfaccia di loopback

Funzioni di

ingresso IP

Funzioni di

uscita IP

L’indirizzo IP di

destinazione è

multi/broadcast?

Metti nella

coda diingresso

IP

L’indirizzo IP di

destinazione è ugualeall’indirizzo IP

dell’interfaccia?

ARPDemultiplatore basato

sul tipo di tramaEthernet

Metti nella coda

di ingresso IP

Ethernet

NO/SI

IP

SI

SI

NO

IP

ARP

Send Receive

EthernetDriver

LoopbackDriver



Esempio 1

Tabella di instradamento di R1

Destination Gateway NetMask Iface

HOST 1 ROUTER 1 HOST 2195.168.14.0/24 195.168.12.0/24

195.168.14.2

195.168.14.1

eth0

195.168.12.1

eth1

195.168.12.2

195.168.14.0 255.255.255.0195.168.14.1 (diretto) eth0

195.168.12.0 255.255.255.0195.168.12.1 (diretto) eth1

Traceroute

q TraceRouteo identificazione dei percorsi sulla rete

– generazione di più pacchetti successivi di Echo Request• TTL inizia da 1 e viene incrementato di 1 ad ogni successivo Echo Request

– ogni pacchetto percorre un passo in più r ispetto al precedente

– L’host di destinazione riceve il pacchetto, che contiene come porta destinazione delTCP un numero generalmente inutilizzato (>30000). L’host destinazione invierà quindiall’host sorgente un messaggio ICMP “port unreachable”, sempre contenente il suo

indirizzo IP

– osservazione del l’indirizzo sorgente dei pacchetti di “Time Exceded”

q Problemaä come per il pingscarsa capacità diagnostica

« Esempio: cosa succede se il percorso dei pacchetti nelle due direzioni è diverso(Es. 1,2,3,5,6,5,3,4,8,1) ed il nodo 8 è guasto ?

1

2

4

3

6

5

78

SSEcho Request

Time Exceded



Traceroute

traceroute www.stanford.edu

traceroute to www.stanford.edu (171.64.14.203), 30 hops max, 40 byte

packets

1 151.100.238.1 (151.100.238.1) 2678.773 ms

2 rc-uniromaI.rm.garr.net (193.206.131.49) 1859.746 ms

3 rt-rc-2.rm.garr.net (193.206.134.165) 788.237 ms

4 mi-rm-1.garr.net (193.206.134.17) 766.614 ms

5 ny-mi.garr.net (212.1.200.17) 894.860 ms

6 Abilene-DANTE.abilene.ucaid.edu (212.1.200.222) 1118.096 ms

7 clev-nycm.abilene.ucaid.edu (198.32.8.29) 970.481 ms

8 ipls-clev.abilene.ucaid.edu (198.32.8.25) 1161.797 ms

9 kscy-ipls.abilene.ucaid.edu (198.32.8.5) 967.958 ms

10 denv-kscy.abilene.ucaid.edu (198.32.8.13) 1200.059 ms

11 scrm-denv.abilene.ucaid.edu (198.32.8.1) 985.121 ms

12 BERK--abilene.POS.calren2.net (198.32.249.41) 1166.336 ms

13 SUNV--BERK.POS.calren2.net (198.32.249.14) 1087.366 ms

14 STAN--SUNV.POS.calren2.net (198.32.249.74) 962.810 ms15 i2-gateway.Stanford.EDU (171.64.1.214) 566.572 ms

16 Core3-gateway.Stanford.EDU (171.64.1.222) 215.399 ms

17 sweet-gateway.Stanford.EDU (171.64.3.110) 215.441 ms

18 www1.Stanford.EDU (171.64.14.203) 215.697 ms

Instradamento dinamico



Chi “scrive” le tabelle di routing ?

q La tabella di routing può essere statica (=configurata manualmente) odinamica

q

Nel caso di tabella dinamica, sono presenti dei protocolli eseguiti dairouter, che dinamicamente scrivono/aggiornano la tabella di routing

q Tali protocolli rappresentano il modo in cui i routers comunicano tra diloro allo scopo di determinare i percorsi, e per aggiornarli in caso divariazioni della topologia di rete (ad esempio eventi di guasto, nuovilink,...)

1.vecchio percorso2.guasto

3.nuovo percorso

Sistemi autonomi

q Si definisce come sistema autonomo un insieme di hosts,routers e reti fisiche controllate da una singola autoritàamministrativa; ogni SA è identificato da un numero assegnatodal NIC.

q Ogni SA è libero di scegliere i criteri di determinazione dellestrade al suo interno

q Ogni SA deve però affidare in modo specifico ad uno o piùrouters (bo rd er r o ut er s) il compito di comunicare al mondoesterno le informazioni di routing al suo interno

q Le informazioni di instradamento riguardanti le strade all’internodi un sistema autonomo sono gestite tra i router del SA permezzo degli Interior Gateway Protocols(IGP)

q Le informazioni di instradamento riguardanti strade checoinvolgono più di un sistema autonomo sono scambiatemediante gli Exterior Gateway Protocols (EGP) tra i border rou te rs



Sistemi autonomi

SA 1

SA 2

SA 3

BGP-4

BGP-4

BGP-4

OSPF

RIP

RIP-2

Routing Protocols

Interior Gateway Protocols (intra AS)

q Dis tance vector

o RIP, RIP-2 (Routing Information Protocol)

o IGRP, EIGRP: CISCO proprietary

q Link s tate o OSPF, OSPF-2

o IS-IS

Exterior Gateway Protocols (inter AS)

q BGP-4 (currently used)

q EGP (formerly used)



Interior Gateway Protocols

I più usati oggi sono RIP e OSPF

q RIP (Routing Information Protocol)o E del tipo “d is tance vec to r” ,

o ha problemi di convergenza e instabilità

o è affetto dal problema dei loop

o non può gestire cammini con oltre 15 salti

o la metrica usata è il numero di salti

o la versione RIP-1 NON comunica la maschera di rete (la RIP-2 si)

o non va bene per SA grandi

o vantaggi: semplicità, non richiede onere di CPU ai router

Interior Gateway Protocols

I più usati oggi sono RIP e OSPF

q OSPF (Open Shortest Path First)o E del tipo “l ink state”,

o converge più velocemente

o può definire diverse metriche

o comunica la maschera di rete

o può fare load balancing (ma solo tra cammini equi-costo)

o prevede autenticazione

o svantaggi: complessità realizzativa, onere per le CPU



Exterior Gateway Protocols

q Un Exterior Gateway Protocol (EGP) svolge trefunzioni:

o individuazione dei routers adiacenti con cui scambiare leinformazioni di instradamento; per adiacenza si intende quellalogica; i routers delegati allo scambio di informazioni possonoessere separati anche da altri routers

o verifica continua della funzionalità dei routers interlocutori

o scambio periodico delle informazioni di instradamento, contenutein appositi messaggi; queste riguardano la sola raggiungibilitàdelle reti, non la distanza

q I più comuni EGP sono:

o EGP (Exterior GatewayProtocol): vecchioo BGP (Border GatewayProtocol): attualmente in uso nella v. 4


q EGP (Exterior Gateway Protocol)o È simile ad un algoritmo Distance Vector, ma non tiene conto di

alcuna metrica (specifica semplicemente se una destinazione èraggiungibile o meno)

o Non ammette la presenza di magliature nella tipologia, perchépotrebbe generare dei loop (funziona solo se tutti gli AS sonocollegati al router EGP in modo stellare)

q BGP (Border Gateway Protocol)o È una evoluzione dell'EGP, in quanto alle funzionalità di base

aggiunge lo scambio di informazioni sulla raggiungibilità dellereti

o Per lo scambio di messaggi tra le entità vengono utilizzati iservizi di trasporto offerti da TCP. Il protocollo effettua la verificadello stato di un link o di un host inviando periodicamentemessaggi di keepalive (il periodo raccomandato è di 30 sec.).




o Le informazioni di raggiungibilità includono il percorso completoche il traffico deve seguire attraverso un sistema autonomo perraggiungere determinate reti di destinazione

o Queste informazioni sono sufficienti a costruire il grafo diconnettività dei sistemi autonomi

o L'informazione sulla raggiungibilità delle reti ha ovviamentemaggior impatto nel caso in cui sia presente, lungo il percorso traun sistema autonomo sorgente e uno di destinazione, un certonumero di altri sistemi autonomi con funzioni di transito; in casocontrario l'impiego di BGP od EGP è pressoché equivalente

o Consente di utilizzare opportune politiche di restrizione per iltraffico in transito, stabilite dal gestore del sistema e codificate intabelle di configurazione, che vengono poi passate al protocollo

o Il protocollo consente la configurazione manuale delle priorità discelta tra più instradamenti disponibili: ciò consente uninstradamento extra-SA sostanzialmente statico

Routing Information Protocol (RIP)

q RIP appartiene alla categoria dei Distance Vector RoutingProtocols

q Applica l’algoritmo di Bellman-Ford per la determinazione delletabelle di instradamento

q E’ richiesto che ogni nodo scambi informazioni con i nodi vicini

o due nodi sono vicini se sono direttamente connessi mediante la s tessa rete

q RIP è utilizzato in reti di piccole dimensioni

q E’ molto semplice, tuttavia

o la convergenza è lenta

o lo stato di equilibrio può essere un sub-ottimo



Routing Information Protocol (RIP)Routing Information Protocol (RIP)

q Notazioni

o M : numero di reti a cui il nodo x è direttamente connesso

o w(x,i) : costo associato al ramo uscente dal nodo x verso la rete i (1≤i ≤M)o N : numero di reti

o L(x,j) : stima della lunghezza del cammino minimo dal nodo x alla rete j

o R(x,j) : next router nel cammino a minima lunghezza dal nodo x alla rete j

q Ogni nodo mantiene al suo interno tre vettori

=

)M,x(w

)1,x(w

Wx M

=

)N,x(L

)1,x(L

Lx M

=

)N,x(R

)1,x(R

Rx M

Vettore dei costi dei ramiuscenti dal nodo

Vettore delle distanzeminime verso le altre reti

Vettore next hopverso le altre reti

Routing Information Protocol (RIP)Routing Information Protocol (RIP)

qq PeriodicamentePeriodicamente (circa 30 s) avviene lo scambio dei vettoriLx tra i nodi vicini

q Il nodo x aggiorna i suoi vettori nel seguente modo

q doveo A : insieme dei nodi vicini al nodo x

o Nx y : rete che interconnette i nodi x e y

) j,y(L)N,x(wMin) j,x(LxyAy

+=∈

y) j,x(R =



RIP: tabelle di statoRIP: tabelle di stato

q

Ogni router ha una tabella di stato in cui compare una riga(colonna) per ciascuna rete di cui il router sia aconoscenza

q Ogni riga (colonna) contiene le seguenti informazioni:

o indirizzo identificativo della rete

o indirizzo del primo router del percorso (next hop)

o distanza dalla rete (numero minimo di reti da attraversare semetriche unitarie)

Esempio RIPEsempio RIP

Tabella di stato Host X (iniziale)

Dest. NetR(X,j)L(X,j)

1 2 3 4 5--- B B A A1 2 5 2 6

Tabella di stato Host X (finale)

Dest. NetR(X,j)L(X,j)

1 2 3 4 5--- B AA A A1 2 33 2 33

1 Network 1

Network 3 Network 2 Network 4

8

5

C B A

3

1

7

1

G D

3 6 2 2

E

9 → 1

Network 5

1

1

H F

1

Host Y

Host X

9→ 110→ 1

4→ 1

3 1 4 3 44B

8 88 5 66 6C

7 3 22 1 22A

Messaggi RIP verso Host X

(primo refresh dopo variazione)

X XX

X



RIP (Versione 1)

q Formato compatibile con i messaggi Berkeley Software

Distribution (BSD) UNIXq Un messaggio RIP è incapsulato in una unità dati UDP

q Pacchetto Request

o è emesso da un router per chiedere ad un nodo vicino l’invio della distancevector table o di una parte di essa

q Pacchetto Response

o è emesso per inviare tutta o una parte della distance vector table

o è emesso

– ogni 30 secondi

– in risposta ad un pacchetto Request – quando la routing table cambia (Triggered updates)

RIP (Versione 1)

q Il formato massimo di un messaggio RIP è di 512 bytes

o massimo 25 blocchi per messaggio

o in caso di un numero maggiore di 25 indirizzi da aggiornare si utilizzanomessaggi RIP multipli

q Non supporta la tecnica della subnet mask

o un router deve conoscere la struttura degli indirizzi

q La metrica usata è la distanza (intero compreso da 1 a 16)

o il valore 16 indica in f in i to

q Se per 180 s un indirizzo di rete non è rinfrescato viene rimossodalla routing table del router

q In caso di variazioni consecutive dello stato dei link i messaggiRIP sono emessi con intervallo da 1 a 5 s



Formato pacchetto RIP (Versione 1)

q

Header o Command

– request

– response

o Version

q Block

o IP address

– rete, sottorete o host

o Metric

– distanza dalla rete

indicata nell’IPaddress

Address Identifier 0

IP Address N

00

Metric for address N

Command Version 0

Address Identifier 0IP Address 1

0

0

Metric for address 1

Address Identifier 0

IP Address 2

0

0


A d d r e s s 1

d i s t a n c e

A d d r e s s

2

d i s t a n c e

F i n o

a 2 5

a d d r e

s s e s

RIP (Versione 2)

q Estende le funzionalità di RIP-1

o può essere utilizzato in reti di media dimensione

o supporta la tecnica di subnetting variabile o supernetting(CIDR)

o è compatibile con RIP-1

o router di diverso tipo possono coesistere in una stessa rete

q Le metrica utilizzata è identica a quella di RIP-1

o distanza (intero da 1 a 16)

o il valore 16 indica infinito

q RIP-2 utilizza i byte inutilizzati nel formato dei pacchettiRIP-1



Formato pacchetto RIP (Versione 2)

o Route Tag

– gestisce l’interoperabilità con altriprotocolli di routing (es. EGP)

o IP address

– rete, sottorete o host

o Subnet Mask

– specifica come interpretare i bitdell’indirizzo

o Next Hop

– indica quale è il next hop router acui il router emittente il messaggioRIP invierà i pacchetti direttiall’indirizzo specificato

o Metric – distanza della rete indicata nell’IP

address dal router emittente

Address Identifier Route Tag

IP Address N

Subnet MaskNext Hop

Metric for address N

Command Version Routing Domain

Address Identifier Route TagIP Address 1

Subnet Mask

Next Hop


Address Identifier Route Tag

IP Address 2

Subnet Mask

Next Hop


A d d r e s s 1

d i s t a n c e

A d d r e s s

2

d i s t a n c e

F i n o

a 2 5

a d d r e

s s e s

Open Shorthest Path First (OSPF)Open Shorthest Path First (OSPF)

q E’ un protocollo di tipo linklink--statestate che supera le limitazionidel protocollo RIP

q Consente una maggiore velocità di convergenza

q Algoritmo:o inizialmente ogni router determina il costo dei rami uscenti

o invia questi dati a tutti i router della rete (tecnica flooding)

o continua a monitorare il costo dei propri rami

oo in caso di variazionein caso di variazione del costo di un ramo, il router invia il nuovovalore del costo di quel ramo a tutti i router

q Ogni nodo conosce quindi lo stato dell’intera rete e puòusare localmente l’algoritmo di Dijkstra



Link State Routing

q I protocolli “Link State” sono adatti a reti di grandidimensioni

q Principi base:o i router hanno la responsabilità di contattare i router vicini e

acquisire la loro identità (pacchetti Hello )

o i router emettono i lin k s t at e pac ket s (LSP) che contengono lalista delle reti connesse al router (vicini) ed i loro costi associati

o gli LSP sono trasmessi a tutti gli altri router (f looding )

o tutti i router hanno lo stesso insieme di dati e quindi possonocostruire la stessa mappa della rete (database topologicodatabase topologico)

o le mappe di rete sono utilizzate per determinare i camminimigliori e quindi l’instradamento

Link State Routing

q Gli LSP sono emessi

o quando un router contatta un nuovo router vicino

o quando un link si guasta

o quando il costo di un link varia

o periodicamente ogni fissato intervallo di tempo

q La rete trasporta gli LSP mediante la tecnica del f lood ing

o un LSP è rilanciato da un router su tutte le sue interfacce tranne quellada cui è stato ricevuto

o gli LSP trasportano dei riferimenti temporali (time stamp) o numeri disequenza per

– evitare il rilancio di pacchetti già rilanciati

– consentire un corretto riscontro dal ricevente



Tecnica del “Flooding”

q Assicura che tutti i router di una rete

o riescano a costruire un database contenente lo stato della rete

o abbiano le stesse informazioni sullo stato dei link

q Alla ricezione di un LSP:

o un router esamina i campi di un LSP: link identifier, metrica, time stamp onumero di sequenza

o se il dato non è contenuto nel database, viene memorizzato e l’LSP è rilanciatosu tutte le interfacce del router tranne quella di ricezione

o se il dato ricevuto è più recente di quello contenuto nel database, il suo valoreè memorizzato e l’LSP è rilanciato su tutte le interfacce del router tranne quelladi ricezione

o se il dato ricevuto è più vecchio di quello contenuto nel database, vienerilanciato un LSP con il valore contenuto nel database esclusivamentesull’interfaccia di arrivo dell’LSP

o se i due dati sono della stessa età non viene eseguita alcuna operazione

Tecnica del “Flooding”

q La tecnica del f lood ing ha i seguenti vantaggi

o esplora tutti i possibili cammini tra origine e destinazione

o è estremamente affidabile e robustao almeno una copia di ogni LSP seguirà la via a minor costo

q Dall’altro lato, il traffico generato dipende dalle dimensionidella rete e può essere molto elevato



OSPF : Topologia della Rete (1/2)OSPF : Topologia della Rete (1/2)

q Ogni router mantiene un database che riflette idati aggiornati sulla topologia della rete (LinkLink

State Database o Database topologicoState Database o Database topologico)q La topologia di rete è rappresentata come un

grafo orientatoo I nodi rappresentano

– router

– networkè reti di transito: non contengono host (sorgenti e/o destinazioni)è reti stub: reti non di transito

o I rami rappresentano

– collegamenti diretti tra nodi di tipo router – collegamenti tra nodi di tipo router e nodi di tipo network

OSPF: Topologia della Rete (2/2)OSPF: Topologia della Rete (2/2)

N11

N3

N4

N6

N7

N8

N9

N1

N2

N10

R2 R3

R1

R6

R4 R5

R7

R10R9

R11 R8

H1 R12

31

3

1 1

1 8 8

7

6

2

7

5

6

6

1

1

4

12

1

3

2

1

6

8

10

N12 N13 N14

N12

N15

Rete8

88

2

9

N6

R1

R2

R4

R3 R6

R5

R7

R10

R8

R11

R9

R12

N1

N2

N3

N4

N7

N8

N11

N9

N10

3

3 1

11 8

6

7

6

6

1

5

7

8

6

1

3

1

1

41

2

3

1

1

10 2

Grafo

8

H1

2



OSPF: Costruzione del GrafoOSPF: Costruzione del Grafo

q Nel grafo rappresentativo della rete:

o due router collegati da una linea punto-punto sono connessida due rami orientati (uno per ogni verso)

o più router connessi alla stessa rete sono rappresentati danodi (router node) connessi ciascuno da due rami orientati(uno per ogni verso) al nodo rappresentativo della rete(network node)

o una rete connessa ad un singolo router è rappresentata da unnodo di tipo stub

o un host direttamente connesso ad un router è rappresentatocon un ramo

o sistemi autonomi esterni sono rappresentati da nodi stub ed

il costo dei rami è determinato dal protocollo EGP

Spanning Tree e Tabelle di RoutingSpanning Tree e Tabelle di Routing

q Ogni router calcola lo spanningtree a partire dal graforappresentativo della retemediante l’algoritmo di Dijkstra

R1

R2

R4

R3 R6

R5

R7

R10

R8

R11

R9

R12

N1

N2

N3

N4

N6

N7

N8

N11

N9

N10

3

3

6 8

7

2

6

1

3

1

4

1

3

10 2

8

8

9

2

N12

N13

N14

N12

N15

H1

Destin. N. H. Dist.N1 R3 10N2 R3 10N3 R3 7N4 R3 8R1 R3 7N6 R10 8N7 R10 12N8 R10 10

Destin. N.H. Dist.

N9 R10 11

N10 R10 13

R5 R5 6R7 R10 8

N12 R10 10N13 R5 14N14 R5 14N15 R10 17

N11 R10 14H1 R10 21

Spanning Tree e Routing Tablein R6



OSPF: Costruzione delleTabelle di Routing


q Nodi vicini si riconoscono attraverso messaggi di “Hello”

q Una volta riconosciutisi, instaurano rapporti di adiacenza

q Nodi adiacenti si scambiano le informazioni sullatopologia dell’intera rete in loro possesso

q A regime tutti i nodi hanno una visione completa (eduguale) della topologia di tutta la rete (DatabaseDatabaseTopolog ico Topolog ico )

q A partire dal database topologico ogni router costruisce

la propria tabella di routing



Ogni routercalcola i percorsi a

costo più basso

Algoritmo SPF(Dijkstra)

C

DA

B

1(15)

2(25)

3(15)

4(5)

5(10)

Link ID (Metrica)

Database Topologico

From To Link Costo

A B 1 15 A C 2 25B A 1 15

B C 3 10B D 4 5C A 2 25

C B 3 10C D 5 10D B 4 5D C 5 10

Routing Table for A

Dest C o s t Nex t HoB 1 5 B

C 2 5 CD 2 0 B



Esempio OSPF (1/3)

A B C

D E

3

2

5

1

6

4 A

Destinazione

Distanza

A B C D E

0 1 2 1 2Link local 1 1 3 1

BDestinazione

Distanza

A B C D E

1 0 1 2 1

Link 1 local 2 1 4

CDestinazione

Distanza

A B C D E

2 1 0 2 1

Link 2 2 local 5 5

DDestinazione

Distanza

A B C D E

1 2 2 0 1

Link 3 3 6 local 6

EDestinazione

Distanza

A B C D E

2 1 1 1 0

Link 4 4 5 6 local

Routing Table

Database Topologico (link bidirezionali)

Da A link

A B 1

A D 3

B C 2

B E 4D E 6

E C 5

Dist

1

1

1

11

1

Esempio OSPF (2/3)

q Guasto del ramo AB

A B C

D E

3

2

5

xxxx

6

4

ADestinazione

Distanza

A B C D E

0 inf inf 1 inf Link local 1 1 3 1

BDestinazione

Distanza

A B C D E

inf 0 1 inf 1

Link 1 local 2 1 4

CDestinazione

Distanza

A B C D E

2 1 0 2 1

Link 2 2 local 5 5

DDestinazione

Distanza

A B C D E

1 2 2 0 1

Link 3 3 6 local 6

EDestinazione

Distanza

A B C D E

2 1 1 1 0

Link 4 4 5 6 local

Routing Table



Esempio OSPF (3/3)

A B C

D E

3

2

5

xxxx

6

4

A Link

Metric

1

Inf B Link

Metric

1

Inf

Database

Topologico

Da A link

A B 1

A D 3

B C 2

B E 4

D E 6

E C 5

Dist

Inf

1

1

1

1

1

A

Destinazione

Distanza

A B C D E

0 3 3 1 2Link local 3 3 3 3

BDestinazione

Distanza

A B C D E

3 0 1 2 1

Link 4 local 2 4 4

CDestinazione

Distanza

A B C D E

3 1 0 2 1

Link 5 2 local 5 5

DDestinazione

Distanza

A B C D E

1 2 2 0 1

Link 3 6 6 local 6

EDestinazione

Distanza

A B C D E

2 1 1 1 0

Link 6 4 5 6 local

Routing Table

4.2 Internet IP Parte2

Documents

Transcript of 4.2 Internet IP Parte2