AA 2009/2010

Parte terzaParte terza

Routing & forwardingRouting & forwarding

2AA 2009/2010

Routing: due diverse attivitàRouting: due diverse attività

■ forwarding forwarding (aspetto esecutivo) (aspetto esecutivo) ◆ scegliere la direzione di uscita su cui inoltrare il datagram scegliere la direzione di uscita su cui inoltrare il datagram

(... tramite la tabella)(... tramite la tabella)■ routing routing (aspetto algoritmico) (aspetto algoritmico)

◆ calcolare la tabella di routingcalcolare la tabella di routing

■ routing (routing (forwardingforwarding))◆ direttodiretto: trasmissione di un datagram da A a B direttamente: trasmissione di un datagram da A a B direttamente

■ è possibile solo se A e B appartengono alla stessa rete fisicaè possibile solo se A e B appartengono alla stessa rete fisica■ A controlla il net-id dell’indirizzo IP del destinatarioA controlla il net-id dell’indirizzo IP del destinatario

◆ indirettoindiretto: il mittente deve inviare il datagram ad un router : il mittente deve inviare il datagram ad un router intermedio ...intermedio ...

3AA 2009/2010

come un router processa un datagram IPcome un router processa un datagram IPDD

■ controllo versionecontrollo versione■ controllo CHKcontrollo CHK■ decrementa TTL [decrementa TTL [0? Scarto e ICMP back to sorgente0? Scarto e ICMP back to sorgente]]■ ricalcolo CHKricalcolo CHK■ IPIPDD = IP = IProuterrouter => consegna payload => consegna payload ■ IPIPDD = Indirizzo diretto => ARP + frame [ = Indirizzo diretto => ARP + frame [frammentiframmenti?]?]■ consulta tabella => inoltro NextHop => ARP + frame consulta tabella => inoltro NextHop => ARP + frame

(chi è?)(chi è?) [[frammentiframmenti?]?]

4AA 2009/2010

Gerarchia in InternetGerarchia in Internet

■ Tre livelliTre livelli◆ networknetwork◆ subnetsubnet◆ hosthost

■ I router centrali (I router centrali (corecore) gestiscono i cammini tra ) gestiscono i cammini tra network e non tra subnet network e non tra subnet

■ Malgrado questo i Malgrado questo i core routercore router devono gestire più di devono gestire più di 100,000 networks100,000 networks

5AA 2009/2010

Tabelle di routingTabelle di routing

■ Tabelle piccoleTabelle piccole◆ solo informazioni sulle retisolo informazioni sulle reti◆ no informazioni sui singoli hostno informazioni sui singoli host

■ TabellaTabella◆ (N , R)(N , R)

■ N: indirizzo IP di una rete DestinazioneN: indirizzo IP di una rete Destinazione■ R: indirizzo IP del R: indirizzo IP del prossimoprossimo router sulla rotta per N router sulla rotta per N

6AA 2009/2010

esempioesempio

15.0.0.0 20.0.0.0 30.0.0.0 40.0.0.0F HG

15.0.0.515.0.0.5

20.0.0.520.0.0.5

30.0.0.730.0.0.720.0.0.620.0.0.6

30.0.0.630.0.0.6 40.0.0.740.0.0.7

Tabella per router GTabella per router G

20.0.0.0 diretto30.0.0.0 diretto15.0.0.0 20.0.0.540.0.0.0 30.0.0.7

Raffinamenti: Raffinamenti: rotta di defaultrotta di default

utile quando un sito ha solo una utile quando un sito ha solo una connessione al resto della rete connessione al resto della rete (ad esempio un host)(ad esempio un host)

comando unix: comando unix: netstat -rnetstat -r per vedere le tabelle di routingper vedere le tabelle di routing

7AA 2009/2010

Algoritmo (Algoritmo (prima versioneprima versione))

Estrai IEstrai IDD, indirizzo destinazione dal datagram, indirizzo destinazione dal datagramCalcola Calcola IINN: IP: IPADDADD reterete di destinazione di destinazioneIfIf I IN N è è direttamente collegatadirettamente collegataThenThen invia datagram a destinazione su questa reteinvia datagram a destinazione su questa rete

(risolvi I(risolvi ID ; D ; incapsula datagram ; manda frame)incapsula datagram ; manda frame)Else Else IfIf I IDD compare in Tabellacompare in Tabella

ThenThen inoltra come indicato inoltra come indicatoElseElse IfIf rotta per defaultrotta per default

ThenThen inoltra come indicato inoltra come indicatoElseElse segnala “ segnala “routing errorrouting error””

8AA 2009/2010

Algoritmo (Algoritmo (in presenza di subnetin presenza di subnet))

■ La tabella contiene linee tipoLa tabella contiene linee tipo◆ (this-subnet, subnet-mask, next-hop)(this-subnet, subnet-mask, next-hop)

■ si esegue si esegue IPIPDD AND subnet-mask AND subnet-mask per isolare per isolare net-id e trovarne l’indirizzo in tabellanet-id e trovarne l’indirizzo in tabella

9AA 2009/2010

esempioesempio

10AA 2009/2010

tabella per R5tabella per R5

Destinazione Destinazione next hopnext hop190.3.6.0/24 190.3.6.0/24 direttadiretta190.3.3.0/24 190.3.3.0/24 direttadiretta190.3.1.0/24 190.3.1.0/24 190.3.3.2190.3.3.2190.3.7.0/24 190.3.7.0/24 190.3.3.2190.3.3.2190.3.9.0/24 190.3.9.0/24 190.3.6.8190.3.6.8150.1.0.0/16 150.1.0.0/16 190.3.6.8190.3.6.8Default Default 190.3.6.8190.3.6.8

■ Gli host dovranno conoscere il Gli host dovranno conoscere il proprio ind. IPproprio ind. IP, la , la NetmaskNetmask e e l’indirizzo del l’indirizzo del router di defaultrouter di default. .

■ host H3 avrà:host H3 avrà:◆ IP = 190.3.6.2IP = 190.3.6.2◆ NetMask = 255.255.255.0 (o /24)NetMask = 255.255.255.0 (o /24)◆ default router = 190.3.6.8default router = 190.3.6.8

11AA 2009/2010

altro esempioaltro esempio

Mask=255.255.255.128Mask=255.255.255.128subnet=128.96.34.0subnet=128.96.34.0

H1

H3

H2R2

R1Mask=255.255.255.128Mask=255.255.255.128subnet=128.96.34.128subnet=128.96.34.128

Mask=255.255.255.0Mask=255.255.255.0subnet=128.96.33.0subnet=128.96.33.0

128.96.34.5128.96.34.5128.96.34.1128.96.34.1

128.96.34.130128.96.34.130

128.96.34.129128.96.34.129

128.96.33.1128.96.33.1

128.96.34.139128.96.34.139

128.96.33.14128.96.33.14

12AA 2009/2010

Tabella di R1Tabella di R1

subNetsubNet maskmask next-hopnext-hop

128.96.34.0128.96.34.0 255.255.255.128255.255.255.128 Interfaccia-0Interfaccia-0128.96.34.128128.96.34.128 255.255.255.128255.255.255.128 Interfaccia-1Interfaccia-1128.96.33.0128.96.33.0 255.255.255.0255.255.255.0 R2R2

13AA 2009/2010

Routing: H1 invia un pacchetto a H2Routing: H1 invia un pacchetto a H2

■ H1H1: mask AND IP: mask AND IPH2H2 255.255.255.128 AND 128.96.34.139 = 128.96.34.128 (subnet di H2)255.255.255.128 AND 128.96.34.139 = 128.96.34.128 (subnet di H2)

H2 non appartiene alla stessa LAN di H1H2 non appartiene alla stessa LAN di H1=> => H1 invia pacchetto a router di default: R1H1 invia pacchetto a router di default: R1

■ R1R1: Mask AND IP: Mask AND IPH2H2

255.255.255.128 AND 128.96.34.139 = 128.96.34.128 (subnet di H2)255.255.255.128 AND 128.96.34.139 = 128.96.34.128 (subnet di H2)

match nella seconda riga della tabella match nella seconda riga della tabella => => forward su Interfaccia-1forward su Interfaccia-1

14AA 2009/2010

Algoritmi di routingAlgoritmi di routing

■ Caratteristiche tipiche della reteCaratteristiche tipiche della rete◆ link e router non affidabililink e router non affidabili◆ pochi cammini alternativipochi cammini alternativi◆ le caratteristiche di traffico possono cambiare rapidamentele caratteristiche di traffico possono cambiare rapidamente

■ Due algoritmi di baseDue algoritmi di base◆ distance vectordistance vector◆ link-statelink-state

■ Tutte e due assumono che il router sappiaTutte e due assumono che il router sappia◆ l’indirizzo di ciascun “vicino”l’indirizzo di ciascun “vicino”◆ il “costo” per raggiungere ciascun vicinoil “costo” per raggiungere ciascun vicino

■ Tutte e due gli algoritmi ammettono che un router scambi Tutte e due gli algoritmi ammettono che un router scambi ““informazioniinformazioni” con “” con “altrialtri” router per determinare le ” router per determinare le informazioni globali necessarie a costruire la tabella di routinginformazioni globali necessarie a costruire la tabella di routing

15AA 2009/2010

Distance vectorDistance vector

■ Ciascun nodo informa Ciascun nodo informa i suoi vicini (i suoi vicini (gli altrigli altri)) della sua “opinione” della sua “opinione” riguardo al modo di raggiungere in maniera ottimale riguardo al modo di raggiungere in maniera ottimale tutti gli altri tutti gli altri nodi della rete (nodi della rete (informazioniinformazioni))

■ Ciascun nodo riceve queste informazioni Ciascun nodo riceve queste informazioni (distance vector) (distance vector) dai dai suoi vicini e le usa per migliorare la propria informazione suoi vicini e le usa per migliorare la propria informazione riguardo al cammino migliore per raggiungere ciascuna riguardo al cammino migliore per raggiungere ciascuna destinazionedestinazione

■ CaratteristicheCaratteristiche◆ distribuitodistribuito◆ si adatta a cambiamenti di traffico e guasti delle connessionisi adatta a cambiamenti di traffico e guasti delle connessioni◆ non richiede un amministratore centralenon richiede un amministratore centrale

16AA 2009/2010

operazionioperazioni

■ Ogni router mantiene una tabella (Ogni router mantiene una tabella (vectorvector) contenente una riga per ) contenente una riga per ogni altro routerogni altro router

■ Ogni riga della tabella contiene: Ogni riga della tabella contiene: ◆ la distanza (metrica: numero di hop, ritardo, ecc.) che lo separa dal router la distanza (metrica: numero di hop, ritardo, ecc.) che lo separa dal router

in oggetto; in oggetto; ◆ la linea in uscita da usare per arrivarci; la linea in uscita da usare per arrivarci;

■ A intervalli regolari ogni router manda A intervalli regolari ogni router manda l’intera sua tabella a tutti i l’intera sua tabella a tutti i vicinivicini, e , e ricevericeve quelle dei vicini. quelle dei vicini.

■ Quando un routerQuando un router A riceve la tabella da B (suo vicino), verifica quali A riceve la tabella da B (suo vicino), verifica quali sarebbero i costi per le varie destinazioni usando come transito B; per sarebbero i costi per le varie destinazioni usando come transito B; per le destinazioni in cui tali costi risultano minori di quelli attuali, le destinazioni in cui tali costi risultano minori di quelli attuali, sostituisce il costo vecchio con quello calcolato e lo stesso fa con il sostituisce il costo vecchio con quello calcolato e lo stesso fa con il next-hop nella Tabellanext-hop nella Tabella.

■ In generale, calcola una nuova tabella scegliendo, fra tutte, la In generale, calcola una nuova tabella scegliendo, fra tutte, la concatenazione miglioreconcatenazione migliore

se stesso -> vicino immediato -> router remoto di destinazionese stesso -> vicino immediato -> router remoto di destinazione

17AA 2009/2010

Count-to-infiniteCount-to-infinite

■ Il link A-B non è più Il link A-B non è più disponibiledisponibile

■ C 'crede' di poter C 'crede' di poter raggiungere A attraverso raggiungere A attraverso B (e lo comunica a B)B (e lo comunica a B)

■ B non può raggiungere A B non può raggiungere A direttamente, quindi cerca direttamente, quindi cerca di passare attraverso C di passare attraverso C per farloper farlo

■ Loop...Loop...

A

D

C

B

18AA 2009/2010

Link state routingLink state routing

■ Il distance vector comunica solo il costo per Il distance vector comunica solo il costo per raggiungere la destinazioneraggiungere la destinazione

■ Negli algoritmi “Negli algoritmi “link statelink state”, il router conosce l’intera ”, il router conosce l’intera topologia e calcola da solo il cammino più breve topologia e calcola da solo il cammino più breve ((shortest pathshortest path))◆ evita il problema base degli algoritmi “distance-vector” che è evita il problema base degli algoritmi “distance-vector” che è

quello di fare un calcolo distribuito (che può essere errato)quello di fare un calcolo distribuito (che può essere errato)■ Elementi chiaveElementi chiave

◆ il calcolo dei costi di comunicazione con i viciniil calcolo dei costi di comunicazione con i vicini◆ la disseminazione affidabile della topologiala disseminazione affidabile della topologia◆ il calcolo del cammino più breveil calcolo del cammino più breve

19AA 2009/2010

attivitàattività

■ scoprire i router adiacenti e i loro IDscoprire i router adiacenti e i loro ID■ misurare il costo della comunicazione per ciascun vicinomisurare il costo della comunicazione per ciascun vicino■ costruire un pacchetto con queste informazionicostruire un pacchetto con queste informazioni■ inviare il pacchetto a tutti i router della reteinviare il pacchetto a tutti i router della rete■ previa ricezione degli analoghi pacchetti che arrivano dagli previa ricezione degli analoghi pacchetti che arrivano dagli

altri router, costruire la topologia dell'intera retealtri router, costruire la topologia dell'intera rete■ calcolare le nuove rotte per ogni altro router (cammino calcolare le nuove rotte per ogni altro router (cammino

minimo) ==> minimo) ==> tabelle di routingtabelle di routing

20AA 2009/2010

Link state: calcolo dei costiLink state: calcolo dei costi■ Ciascun router, al boot, Ciascun router, al boot, conosce i viciniconosce i vicini inviando un inviando un

pacchetto speciale (pacchetto speciale (HELLOHELLO) su ogni linea punto-punto a ) su ogni linea punto-punto a cui viene risposto con l’ID del router adiacente.cui viene risposto con l’ID del router adiacente.

■ Ciascun router misura il Ciascun router misura il costo di comunicazionecosto di comunicazione con i con i vicini per mezzo di pacchetti che vengono ritornati dai vicini per mezzo di pacchetti che vengono ritornati dai vicini (vicini (ECHOECHO))◆ Se si considera il carico si possono generare oscillazioniSe si considera il carico si possono generare oscillazioni◆ Se non si considera il carico si può scegliere una via meno Se non si considera il carico si può scegliere una via meno

buonabuona

21AA 2009/2010

Link state: disseminazione della topologiaLink state: disseminazione della topologia

■ Ciascun router descrive i suoi vicini con un Ciascun router descrive i suoi vicini con un link state packet (LSP)link state packet (LSP)■ Usa Usa controlled floodingcontrolled flooding per distribuire per distribuire a tuttia tutti questa informazione questa informazione

■ floodingflooding◆ l’informazione è trasmessa su tutte le linee di uscital’informazione è trasmessa su tutte le linee di uscita◆ i router riceventi propagano le informazioni ricevute su tutte le loro linee di i router riceventi propagano le informazioni ricevute su tutte le loro linee di

uscita e così viauscita e così via■ controlledcontrolled

◆ tiene gli LSP in un tiene gli LSP in un LSP databaseLSP database◆ per poter decidere se un LSP ricevuto è significativo (contiene una per poter decidere se un LSP ricevuto è significativo (contiene una

informazione più recente di quella attualmente nel informazione più recente di quella attualmente nel databasedatabase) ogni LSP ) ogni LSP deve contenere un numero di sequenza progressivodeve contenere un numero di sequenza progressivo

◆ Ogni volta che un router riceve un LSP più vecchio di quello in memoria, lo Ogni volta che un router riceve un LSP più vecchio di quello in memoria, lo elimina senza propagarloelimina senza propagarlo

◆ se un LSP è nuovo lo ritrasmette a tutti meno a chi lo ha mandatose un LSP è nuovo lo ritrasmette a tutti meno a chi lo ha mandato■ un LSP non viene mai trasmesso due volte sullo stesso link nella stessa un LSP non viene mai trasmesso due volte sullo stesso link nella stessa

direzionedirezione

22AA 2009/2010

DV vs LSDV vs LS

■ DVDV: ogni router comunica : ogni router comunica solo con i nodi adiacenti:solo con i nodi adiacenti:

◆ quanto è distante ogni quanto è distante ogni singolo nodosingolo nodo

◆ il primo salto per andare in il primo salto per andare in quella direzionequella direzione

■ Le rotte sono direttamente Le rotte sono direttamente calcolate dalle tabelle ricevutecalcolate dalle tabelle ricevute

■ LSLS: ogni router comunica : ogni router comunica ((floodflood) con tutti i router della ) con tutti i router della reterete

◆ quali link sono lui collegatiquali link sono lui collegati◆ lo stato di questi linklo stato di questi link

■ Calcola poi le tabelle di routingCalcola poi le tabelle di routing

23AA 2009/2010

Routing Information Protocol (RIP)Routing Information Protocol (RIP)■ Originariamente progettato dalla Xerox per la propria rete, sviluppato Originariamente progettato dalla Xerox per la propria rete, sviluppato

dall’Università di Berkley per la propria implementazione di TCP/IP, e dall’Università di Berkley per la propria implementazione di TCP/IP, e standardizzato con RFC 1058 nel 1988.standardizzato con RFC 1058 nel 1988.

■ E’ un E’ un Distance VectorDistance Vector, usa una metrica statica:il costo di un percorso è , usa una metrica statica:il costo di un percorso è il numero di hop ossia di linee che esso attraversa.il numero di hop ossia di linee che esso attraversa.

■ E il problema del E il problema del count-to-infinitycount-to-infinity? ? ◆ split horizonsplit horizon

■ non si propagano informazioni su una rotta ai vicini da cui si è avuta la notizia non si propagano informazioni su una rotta ai vicini da cui si è avuta la notizia ◆ with poisonous reversewith poisonous reverse

■ distanza - per link caduti - settata espressamente a distanza - per link caduti - settata espressamente a infinitoinfinito◆ triggered updatetriggered update

■ sisi chiede agli altri router l’invio di informazioni non appena questi verifichino chiede agli altri router l’invio di informazioni non appena questi verifichino cambiamenti nella loro tabellacambiamenti nella loro tabella

■ Aggiorna la Tabella ogni 30 s. e elimina ogni rotta non aggiornata per Aggiorna la Tabella ogni 30 s. e elimina ogni rotta non aggiornata per 180 s consecutivi180 s consecutivi

24AA 2009/2010

RIPRIP

■ Ha come valore massimo del costo 15. Ha come valore massimo del costo 15. Il valore 16 Il valore 16 corrisponde ad infinitocorrisponde ad infinito. Quindi non permette reti con . Quindi non permette reti con percorsi con più di 15 percorsi con più di 15 router router attraversati.attraversati.

■ La limitazione di cui sopra è legata al fatto che per La limitazione di cui sopra è legata al fatto che per reti più grandi è troppo lento a convergere reti più grandi è troppo lento a convergere

■ Ne esistono due versioni, la seconda (RIPv2) Ne esistono due versioni, la seconda (RIPv2) consente l’uso del CIDR e una autenticazioneconsente l’uso del CIDR e una autenticazione

■ Lo scambio di informazioni avviene attraverso il Lo scambio di informazioni avviene attraverso il protocollo UDP (livello trasporto)protocollo UDP (livello trasporto)

25AA 2009/2010

Open Shortest Path First (OSPF)Open Shortest Path First (OSPF)

■ Nasce nel 1990 con l’RFC 1247 per sostituire il RIPNasce nel 1990 con l’RFC 1247 per sostituire il RIP■ Link StateLink State■ E’ stato realizzato per rispondere a diverse esigenze:E’ stato realizzato per rispondere a diverse esigenze:

◆ ““Open” ossia aperto e non proprietarioOpen” ossia aperto e non proprietario◆ Multi-metrica (anche dinamiche)Multi-metrica (anche dinamiche)◆ Capace di autoadattarsi a cambi topologiciCapace di autoadattarsi a cambi topologici◆ Routing Routing diversi per tipi di servizi differentidiversi per tipi di servizi differenti◆ Bilanciamento dei flussi (multi-percorso)Bilanciamento dei flussi (multi-percorso)◆ GerarchicoGerarchico◆ Protezione da aggiornamenti fallaciProtezione da aggiornamenti fallaci◆ TunnelingTunneling

26AA 2009/2010

gerarchiagerarchia

■ suddivisione della rete in un set di parti indipendenti (suddivisione della rete in un set di parti indipendenti (areearee) ) connesse attraverso un backbone (connesse attraverso un backbone (backbone area)backbone area)

■ ciascuna area si comporta come una rete indipendente; il ciascuna area si comporta come una rete indipendente; il database include solo lo stato dei link dell'area, il database include solo lo stato dei link dell'area, il protocollo di protocollo di floodingflooding si ferma ai confini dell'area ed i routers calcolano solo si ferma ai confini dell'area ed i routers calcolano solo le rotte all'interno dell'areale rotte all'interno dell'area

◆ costo del protocollo di routing legato alle dimensioni dell'area e non costo del protocollo di routing legato alle dimensioni dell'area e non a quelle della retea quelle della rete

■ per connettere l'intera rete, alcuni routers appartengono a più per connettere l'intera rete, alcuni routers appartengono a più aree - tipicamente a un'area a basso livello e all'area di aree - tipicamente a un'area a basso livello e all'area di backbonebackbone

◆ "area-border routers" ("area-border routers" (ABRABR))◆ almeno un almeno un ABRABR in ciascun area, per connetterla al in ciascun area, per connetterla al backbonebackbone

27AA 2009/2010

struttura effettiva di Internetstruttura effettiva di Internet

Internet distingue tre livelli gerarchici principali:Internet distingue tre livelli gerarchici principali:■ Sottoreti o singoli domini di Sottoreti o singoli domini di broadcast broadcast (LAN)(LAN)

◆ All’interno dei quali l’instradamento fa uso di ARP.All’interno dei quali l’instradamento fa uso di ARP.■ Autonomous System Autonomous System (AS)(AS)

◆ In cui i protocolli di instradamento prendono il nome di In cui i protocolli di instradamento prendono il nome di Interior Gatway Protocol Interior Gatway Protocol (IGP): RIP e OSPF.(IGP): RIP e OSPF.

■ BackboneBackbone◆ In cui i protocolli di instradamento prendono il nome di In cui i protocolli di instradamento prendono il nome di

Exterior Gateway Protocol Exterior Gateway Protocol (EGP): BGP.(EGP): BGP.

28AA 2009/2010

Autonomous system (AS)Autonomous system (AS)

■ Internet è una collezione di Internet è una collezione di ASAS connessi da connessi da backbonebackbone ad alta ad alta velocitàvelocità

◆ raggruppamenti di network in un “dominio” riconosciuto, identificato raggruppamenti di network in un “dominio” riconosciuto, identificato univocamente e unicamente amministrato dal punto di vista del routing univocamente e unicamente amministrato dal punto di vista del routing internointerno

■ Ciò che caratterizza un Ciò che caratterizza un ASAS è il fatto di essere gestito da una singola è il fatto di essere gestito da una singola autoritàautorità

◆ GARRGARR è un è un ASAS◆ le reti deile reti dei grandi ISP grandi ISP sonosono AS AS

■ La presenza degli La presenza degli ASAS fa sì che i fa sì che i router router vengano distinti in vengano distinti in Interior Interior Router Router (IR) e (IR) e Exterior Router Exterior Router (ER).(ER).

◆ Gli IR instradano entro un Gli IR instradano entro un ASAS, mentre gli ER instradano tra diversi , mentre gli ER instradano tra diversi ASAS

29AA 2009/2010

Autonomous systemAutonomous system■ a set of routers under a single technical administration, using an a set of routers under a single technical administration, using an

interior gateway protocol (IGP) and common metrics to route interior gateway protocol (IGP) and common metrics to route packets within the autonomous system, and using an exterior packets within the autonomous system, and using an exterior gateway protocol (EGP) to route packets to other autonomous gateway protocol (EGP) to route packets to other autonomous systems. systems.

◆ Since this classic definition was developed, it has become common for Since this classic definition was developed, it has become common for a single autonomous system to use several interior gateway protocols a single autonomous system to use several interior gateway protocols and sometimes several sets of metrics within an autonomous system. and sometimes several sets of metrics within an autonomous system.

■ The use of the term "autonomous system" stresses that even when The use of the term "autonomous system" stresses that even when multiple IGPs and metrics are used, the administration of an multiple IGPs and metrics are used, the administration of an autonomous system appears to other autonomous systems to have autonomous system appears to other autonomous systems to have a a single coherent interior routing plansingle coherent interior routing plan and to present a and to present a consistentconsistent picture of what networks are reachable through it. picture of what networks are reachable through it.

■ The autonomous system is represented by a number (ASN - 16 bit) The autonomous system is represented by a number (ASN - 16 bit) assigned by the Internet Assigned Numbers Authority.assigned by the Internet Assigned Numbers Authority.

30AA 2009/2010

A network of routers split into 5 Autonomous Systems

31AA 2009/2010

ASAS

■ AS sono spesso grandiAS sono spesso grandi◆ divisi in Aree (collezioni di reti contigue)divisi in Aree (collezioni di reti contigue)◆ all’esterno di un’area la sua topologia non è visibileall’esterno di un’area la sua topologia non è visibile

■ ogni AS ha un’area dorsale (ogni AS ha un’area dorsale (backbonebackbone) chiamata Area0) chiamata Area0■ tutte le aree sono connesse a questatutte le aree sono connesse a questa

◆ topologia “a stella”topologia “a stella”◆ un router connesso a due e più aree fa parte del backboneun router connesso a due e più aree fa parte del backbone

■ all’interno di ciascuna area ogni router esegue lo stesso algoritmo per all’interno di ciascuna area ogni router esegue lo stesso algoritmo per calcolare i cammini minimi interni all’areacalcolare i cammini minimi interni all’area

■ se un router connette due aree mantiene due diversi DB, uno per ciascuna se un router connette due aree mantiene due diversi DB, uno per ciascuna area, e calcola i cammini minimi separatamentearea, e calcola i cammini minimi separatamente

■ L’instradamento fra due aree viene realizzato in tre parti:L’instradamento fra due aree viene realizzato in tre parti:◆ Il percorso nell’area sorgente fra la sorgente stessa ed un Il percorso nell’area sorgente fra la sorgente stessa ed un Area Border RouterArea Border Router◆ Il percorso fra le due aree tramite il backboneIl percorso fra le due aree tramite il backbone◆ Il percorso nell’area destinazione fra l’ABR che riceve il pacchetto dal Il percorso nell’area destinazione fra l’ABR che riceve il pacchetto dal backbone backbone e e

la destinazione.la destinazione.■ In pratica si forza un instradamento a stella in cui il backbone rappresenta il In pratica si forza un instradamento a stella in cui il backbone rappresenta il

centro stellacentro stella

32AA 2009/2010

Router di un ASRouter di un AS

I router di un AS possono essere: I router di un AS possono essere: ● interniinterni a un area: si occupano del routing all'interno dell'area; a un area: si occupano del routing all'interno dell'area; ● sul confinesul confine di un'area: si occupano del routing fra le diverse aree via di un'area: si occupano del routing fra le diverse aree via backbone; backbone; ● nell'area backbonenell'area backbone: si occupano del routing sul backbone; : si occupano del routing sul backbone; ● sul confine dell'ASsul confine dell'AS: si occupano del routing fra gli AS (: si occupano del routing fra gli AS (applicandoapplicando EGPEGP); ); possono trovarsi anche sul confine di un'area. possono trovarsi anche sul confine di un'area.

33AA 2009/2010

Exterior Gateway ProtocolExterior Gateway Protocol

■ Tra router di diverse amministrazioniTra router di diverse amministrazioni◆ che non si fidano l’uno dell’altroche non si fidano l’uno dell’altro◆ che usano diversi modi di calcolare il costo che usano diversi modi di calcolare il costo

■ ci si riduce al costo comune più semplice: il numero di hopci si riduce al costo comune più semplice: il numero di hop

■ Problemi di transitoProblemi di transito

34AA 2009/2010

routing vs. policy routingrouting vs. policy routing

■ Nel caso standard il routing dipende dal costo, dalla Nel caso standard il routing dipende dal costo, dalla topologia e dalla disponibilitàtopologia e dalla disponibilità

■ Nel caso di Nel caso di policy routingpolicy routing, i cammini sono scelti , i cammini sono scelti anche sulla base dianche sulla base di◆ indirizzo di partenza e arrivoindirizzo di partenza e arrivo◆ domini attraversati domini attraversati ◆ quality of servicequality of service◆ ora del giornoora del giorno◆ addebitiaddebiti

■ In generale è un problema irrisoltoIn generale è un problema irrisolto

35AA 2009/2010

BGP (Border Gateway Protocol)BGP (Border Gateway Protocol)

■ E’ il protocollo EGP relativamente recente, definito dal E’ il protocollo EGP relativamente recente, definito dal RFC 1654RFC 1654◆ La versione in uso attualmente è la 4 (BGP4)La versione in uso attualmente è la 4 (BGP4)

■ Permette la cooperazione fra Permette la cooperazione fra router router di AS diversi di AS diversi (chiamati (chiamati gatewaygateway) per la realizzazione ) per la realizzazione dell’instradamento fra ASdell’instradamento fra AS

■ Per lo scambio di informazioni fra i nodi usa TCP Per lo scambio di informazioni fra i nodi usa TCP (porta 179)(porta 179)

■ Visione di Internet per BGPVisione di Internet per BGP◆ collezione di router che “parlano” BGP connessi da linee collezione di router che “parlano” BGP connessi da linee

36AA 2009/2010

BGPBGP

■ Anche se tutti i Anche se tutti i router router all’interno di un AS sono fra loro all’interno di un AS sono fra loro cooperativi, non è detto che i nodi che interconnettono due AS cooperativi, non è detto che i nodi che interconnettono due AS si “fidino” l’uno dell’altrosi “fidino” l’uno dell’altro

■ Questo accade in quanto gli AS sono in genere controllati o Questo accade in quanto gli AS sono in genere controllati o posseduti da organizzazioni diverse e quindi l’instradamento posseduti da organizzazioni diverse e quindi l’instradamento deve dipendere anche dagli accordi fra i diversi AS (transito)deve dipendere anche dagli accordi fra i diversi AS (transito)

37AA 2009/2010

BGPBGP

■ Opera in tre passi:Opera in tre passi:◆ Identificazione dei nodi adiacentiIdentificazione dei nodi adiacenti◆ Raggiungibilità dei nodi adiacentiRaggiungibilità dei nodi adiacenti◆ Raggiungibilità delle retiRaggiungibilità delle reti

■ Utilizza un algoritmo tipo Distance Vector (Utilizza un algoritmo tipo Distance Vector (Path Vector)Path Vector)■ Distingue tre tipi di retiDistingue tre tipi di reti

◆ Stub: Stub: che hanno un’unica connessione con il che hanno un’unica connessione con il backbone backbone e non e non possono venir usate come transitopossono venir usate come transito

◆ MulticonnectedMulticonnected: che potenzialmente possono essere usate per : che potenzialmente possono essere usate per transito (se lo permettono)transito (se lo permettono)

◆ TransitTransit: costruite per realizzare il transito: costruite per realizzare il transito

38AA 2009/2010

BGP BGP

■ E' fondamentalmente di tipo distance vector, con E' fondamentalmente di tipo distance vector, con due novità: due novità: ◆ possiede la capacità di gestire politiche di instradamento possiede la capacità di gestire politiche di instradamento

(derivanti, ad esempio, da leggi nazionali), configurate (derivanti, ad esempio, da leggi nazionali), configurate manualmente nei router manualmente nei router

◆ mantiene (e scambia con gli altri router) non solo il costo mantiene (e scambia con gli altri router) non solo il costo per raggiungere le altre destinazioni, ma anche il per raggiungere le altre destinazioni, ma anche il cammino cammino completocompleto..

■ Ciò consente di risolvere il problema del Ciò consente di risolvere il problema del count-to-infinitycount-to-infinity: se : se una linea va giù, il router può subito scartare, senza quindi una linea va giù, il router può subito scartare, senza quindi poi distribuirli, tutti i cammini che ci passano. poi distribuirli, tutti i cammini che ci passano.

■ Periodicamente ogni router BGP scambia coi vicini Periodicamente ogni router BGP scambia coi vicini l’elenco dei cammini esattil’elenco dei cammini esatti

39AA 2009/2010

toolstools

■ http://www.bgp4.as/toolshttp://www.bgp4.as/tools

■ GARR: AS137GARR: AS137http://www.ripe.net/whois?searchtext=AS137http://www.ripe.net/whois?searchtext=AS137■ Tiscali: AS3228Tiscali: AS3228■ Libero: AS1267 - 1268Libero: AS1267 - 1268