Interdomain routing Principi generali

(1)

RETI DI CALCOLATORI II

Prof. PIER LUCA MONTESSORO Facoltà di Ingegneria Università degli Studi di Udine

Prof. MARIO BALDI Facoltà di Ingegneria

Politecnico di Torino Prof. PIER LUCA MONTESSORO

Facoltà di Ingegneria Università degli Studi di Udine

Prof. MARIO BALDI Facoltà di Ingegneria

Politecnico di Torino

© 2003 Pier Luca Montessoro – Mario Baldi (si veda la nota a pagina 2) 2 Questo insieme di trasparenze (detto nel seguito slide) è protetto dalle leggi sul copyright e dalle disposizioni dei trattati internazionali. Il titolo ed i copyright relativi alle slides (ivi inclusi, ma non limitatamente, ogni immagine, fotografia, animazione, video, audio, musica e testo) sono di proprietà degli autori prof. Pier Luca Montessoro, Università degli Studi di Udine, e prof. Mario Baldi, Politecnico di Torino.

Le slide possono essere riprodotte ed utilizzate liberamente dagli istituti di ricerca, scolastici ed universitari afferenti al Ministero della Pubblica Istruzione e al Ministero dell’Università e Ricerca Scientifica e Tecnologica, per scopi istituzionali, non a fine di lucro. In tal caso non è richiesta alcuna autorizzazione.

Ogni altro utilizzo o riproduzione (ivi incluse, ma non limitatamente, le riproduzioni su supporti magnetici, su reti di calcolatori e stampe) in toto o in parte è vietata, se non esplicitamente autorizzata per iscritto, a priori, da parte degli autori.

L’informazione contenuta in queste slide è ritenuta essere accurata alla data della pubblicazione. Essa è fornita per scopi meramente didattici e non per essere utilizzata in progetti di impianti, prodotti, reti, ecc. In ogni caso essa è soggetta a cambiamenti senza preavviso. L’autore non assume alcuna responsabilità per il contenuto di queste slide (ivi incluse, ma non limitatamente, la correttezza, completezza, applicabilità, aggiornamento dell’informazione).

In ogni caso non può essere dichiarata conformità all’informazione contenuta in queste slide.

In ogni caso questa nota di copyright e il suo richiamo in calce ad ogni slide non devono mai essere rimossi e devono essere riportati anche in utilizzi parziali.

Nota di Copyright

Interdomain routing Principi generali

e BGP

Interdomain routing Interdomain routing

Principi generali Principi generali

e BGP e BGP

Argomenti della lezione Argomenti della lezione

Routing interdominio Routing interdominio

Architettura di routing di Internet

Neutral access point Neutral access point Border Gateway Protocol Border Gateway Protocol

Interdomain routing Principi generali Interdomain routing

Principi generali dal punto di vista amministrativodal punto di vista amministrativo Omogenea

Omogenea Indipendente Indipendente

Livello gerarchico superiore di routing

Autonomous system (AS) Autonomous system (AS)

Zona della rete Internet Zona della rete Internet

(2)

Tipico esempio di AS:

la rete di un service provider e suoi clienti Tipico esempio di AS:

la rete di un service provider e suoi clienti Autonomous system Autonomous system

Autonomous system Autonomous system

AS 1 AS 1

AS 2 AS 2

AS 3AS 3

AS 5AS 5 AS 4AS 4

AS 6AS 6 Exterior gateway

Border gateway Boundary router Exterior gateway Border gateway Boundary router

Autonomous system: perchè?

Impossibile gestire informazioni dettagliate su tutta Internet Impossibile gestire informazioni dettagliate su tutta Internet

Enorme quantità di memoria Enorme quantità di memoria Enorme potenza di calcolo Enorme potenza di calcolo Ragioni tecniche:

Scalabilità Ragioni tecniche:

Scalabilità

Dettagli di un AS non annunciati all’esterno

Aggregazione al confine Aggregazione al confine Ragioni tecniche:

Scalabilità Ragioni tecniche:

Scalabilità

Le scelte di routing tra AS non sono necessariamente basate sul percorso più breve

Rispecchiano accordi tra i gestori degli AS

Ragioni amministrative Ragioni amministrative

Ogni AS può realizzare il routing interno in modo indipendente Ogni AS può realizzare il routing interno in modo indipendente

Protocolli di routing

(IGP - interior gateway protocol) diversi

Protocolli di routing

(IGP - interior gateway protocol) diversi

Ragioni amministrative Ragioni amministrative

(3)

Architettura di routing Architettura di routing

L’unico punto di accordo deve

essere il protocollo utilizzato nei punti di collegamento (EGP - exterior gateway protocol)

L’unico punto di accordo deve

essere il protocollo utilizzato nei punti di collegamento (EGP - exterior gateway protocol)

OSPFOSPF

AS 2AS 2 AS 1AS 1

IGRPIGRP BGPBGP

Exterior gateway Border gateway Boundary rotuer Exterior gateway Border gateway Boundary rotuer

Scambio di informazioni di routing tra i router interni ad un AS Scambio di informazioni di routing

tra i router interni ad un AS IGP ed EGP

IGP ed EGP

Interior gateway protocol (IGP) Interior gateway protocol (IGP)

IGP ed EGP IGP ed EGP

Scambio di informazioni di routing tra router di AS diversi Scambio di informazioni di routing

tra router di AS diversi Exterior gateway protocol (EGP) Exterior gateway protocol (EGP)

Informazioni

trasportate da EGP Informazioni

trasportate da EGP

Informazioni riassuntive sull’interno dell’AS di appartenenza del border router Informazioni riassuntive sull’interno dell’AS di appartenenza del border router Informazioni su altri AS apprese da altri border router

Informazioni su altri AS apprese da altri border router

Interdomain routing Interdomain routing

Il traffico interno usa qualsiasi cammino

Il migliore Il migliore

Motivazioni di carattere economico, organizzativo e gestionale Motivazioni di carattere economico,

organizzativo e gestionale

Interdomain routing Interdomain routing

Il traffico di attraversamento no Il traffico di attraversamento no

Per esempio, non deve

danneggiare il traffico interno Per esempio, non deve

danneggiare il traffico interno Motivazioni di carattere economico,

organizzativo e gestionale Motivazioni di carattere economico,

organizzativo e gestionale

(4)

Politiche di routing Politiche di routing

Riflettono motivazioni di carattere economico, organizzativo e

gestionale

Riflettono motivazioni di carattere economico, organizzativo e

gestionale

Accordi tra i gestori degli AS Accordi tra i gestori degli AS

Definiscono i criteri per la scelta dei percorsi

Routing statico Routing statico

Niente traffico di controllo Niente traffico di controllo

☺☺

Politiche molto complesse Politiche molto complesse

☺

Non si adatta a cambiamenti topologici

È facile introdurre inconsistenze È facile introdurre inconsistenze Configurazione manuale dei router Configurazione manuale dei router

Routing dinamico: a che scopo?

Far conoscere all’esterno come raggiungere (route) le destinazioni (LIS) interne ad un AS

Apprendere in che modo

raggiungere (route) le destinazioni esterne ad un AS (il resto di

Internet)

Apprendere in che modo

raggiungere (route) le destinazioni esterne ad un AS (il resto di

Internet)

Routing dinamico: implicazioni Routing dinamico: implicazioni

Se si ridistribuiscono le route all’interno dell’AS si possono sovraccaricare i router interni Se si ridistribuiscono le route all’interno dell’AS si possono sovraccaricare i router interni È possibile che si ricevano route verso tutte le reti di Internet È possibile che si ricevano route verso tutte le reti di Internet

50.000 - 200.000 route 50.000 - 200.000 route Memoria

Memoria Processore Processore

Routing dinamico si o no?

Unico ingresso/uscita da AS no Unico ingresso/uscita da AS no

AS 1AS 1 AS 2AS 2

Inte rnet Inte

rnet

Unico ingresso/uscita da AS no Unico ingresso/uscita da AS no Più ingressi/uscite da AS

Più ingressi/uscite da AS Verso un solo AS probabilmente no Verso un solo AS probabilmente no

AS 1AS 1 AS 2AS 2

Inte rnet Inte

rnet

(5)

Unico ingresso/uscita da AS no Unico ingresso/uscita da AS no Più ingressi/uscite da AS

Più ingressi/uscite da AS Verso un solo AS probabilmente no Verso un solo AS probabilmente no Verso più AS si Verso più AS si

AS 1AS 1 AS 2AS 2

AS 3AS 3 Intern

et Inte

rnet

Internet Internet

Protocolli per interdomain routing (EGP)

Protocolli differenti Protocolli differenti

Trasporto di informazioni differenti Trasporto di informazioni differenti Requisiti diversi da quelli per routing interno

Requisiti diversi da quelli per routing interno

Diversi criteri di scelta dei percorsi Diversi criteri di scelta dei percorsi Meno evoluti

Meno evoluti

RFC 827 RFC 827

Reachability only Reachability only

Solo topologie lineari Solo topologie lineari Primo vero protocollo per interdomain routing Primo vero protocollo per interdomain routing

AS 2AS 2

AS 5AS 5 AS 3AS 3

AS 1AS 1

Exterior Gateway Protocol (EGP)

Largamente utilizzato Largamente utilizzato

Quasi 100% del routing dinamico Quasi 100% del routing dinamico Attualmente alla versione 4 Attualmente alla versione 4

RFC 1771 (1995) RFC 1771 (1995)

Border Gateway Protocol (BGP)

Evoluzione di BGP per reti OSI Evoluzione di BGP per reti OSI InterDomain Routing Protocol (IDRP)

InterDomain Routing Protocol (IDRP)

Migliorie rispetto a BGP Migliorie rispetto a BGP

Anche con IPv6 (per ora) Anche con IPv6 (per ora) Multiprotocol routing Multiprotocol routing

InterDomain Routing Protocol (IDRP)

Poco usato Poco usato

Modificato per fuzionare con indirizzi sia OSI sia IP Modificato per fuzionare con indirizzi sia OSI sia IP

(6)

Architettura di routing di Internet: gli ISP Architettura di routing di Internet: gli ISP

Cliente/fornitore Cliente/fornitore

Cliente/

fornitoreCliente/

fornitore Peering privato Peering privato

Peering privato Peering privato Tier 1 ISP Tier 1 ISP

Tier 1 ISP Tier 1 ISP Tier 1 ISP

Tier 1 ISP

Tier 2 ISP Tier 2 ISPTier 2 ISP

Tier 2 ISP Tier 2 ISP

Tier 2 ISP Tier 3

ISP Tier 3

Tier 3ISP ISP

Tier 3 ISP Tier 3

ISP Tier 3

Tier 3ISP ISP Tier 3

Cliente/

fornitore Peering privato Peering privato Tier 3

ISP Tier 3

Tier 3 ISP Tier 3

ISP Tier 1 ISP

Tier 1 ISP Tier 2 ISP Tier 2 ISP Tier 2 ISP

Tier 3 Tier 3ISP ISP

NAP/IXP NAP/IXP NAP/IXP

Cliente/

Tier 3ISP ISP Tier 3 Tier 3ISP

ISP Tier 3

ISP

Tier 3 Tier 3ISP ISP Tier 1 ISP

Tier 3 ISP Tier 3

ISP

Tier 3 ISP Tier 3

ISP

Cliente/

Tier 3ISP ISP Tier 3 Tier 3ISP

ISP Tier 3

ISP

Tier 3 Tier 3ISP ISP Tier 1 ISP

Tier 3 ISP Tier 3

ISP

Tier 3 ISP Tier 3

ISP

Cliente/

Tier 3ISP ISP Tier 3

ISP Tier 3

Tier 3 ISP Tier 3

ISP Tier 1 ISP

Tier 3 ISP Tier 3

ISP

NAP/IXP NAP/IXP

NAP/IXP Generalmente BGPGeneralmente BGP

Neutral Access Point (NAP) Internet eXchange Point (IXP) Neutral Access Point (NAP) Internet eXchange Point (IXP)

Coppie di router scambiano informazioni tramite un EGP Coppie di router scambiano informazioni tramite un EGP Una LAN cui sono connessi router appartenenti ad AS (ISP) differenti Una LAN cui sono connessi router appartenenti ad AS (ISP) differenti

BGPBGP BGP BGP

BGPBGP BGPBGP

(7)

Rete commutata Rete commutata

Commutatore ATM o Ethernet Commutatore ATM o Ethernet

Router Router

Connessione ad alta velocità Connessione ad alta velocità

2 in Italia

Milano - Roma

2 in Italia

Milano - Roma

TOPIX in via di realizzazione a Torino TOPIX in via di realizzazione a Torino

40 in Europa 40 in Europa

NAP/IXP NAP/IXP

BGP

Border Gateway Protocol BGP

Border Gateway Protocol

Comunicazione affidabile Comunicazione affidabile

TCPTCP

Attualmente alla versione 4 Attualmente alla versione 4

RFC 1771 (1995) RFC 1771 (1995)

Caratteristiche generali Caratteristiche generali

Adiacenze (peering session) sono configurate esplicitamente Adiacenze (peering session) sono configurate esplicitamente

Il distance vector puro indica solo il costo Il distance vector puro

indica solo il costo

Per una destinazione si annuncia la sequenza di Autonomous System (AS) da attraversare Per una destinazione si annuncia

la sequenza di Autonomous System (AS) da attraversare Algoritmo Path Vector Algoritmo Path Vector

Non c’è il problema del conteggio a infinito (“counting-to-infinity”) Non c’è il problema del conteggio a infinito (“counting-to-infinity”)

Compito dell’amministratore Compito dell’amministratore Non stabilita dalla specifica Non stabilita dalla specifica Scelta delle route

Scelta delle route

Politiche (policy) di routing Politiche (policy) di routing Esiste comportamento di default Esiste comportamento di default

(8)

Allora, cosa contiene la specifica di BGP?

Definisce modalità secondo cui Definisce modalità secondo cui

Stabilire criteri per selezionare Stabilire criteri per selezionare

I percorsi di inoltro (route) I percorsi di inoltro (route) Le informazioni da diffondere Le informazioni da diffondere Diffondere informazioni Diffondere informazioni

Peering Session Peering Session

Due peer hanno tra di loro una peering session

Due router che scambiano informazioni si dicono peer Due router che scambiano informazioni si dicono peer

Due peer non sono necessariamente collegati direttamente

Due tipi di utilizzo Due tipi di utilizzo External BGP (E-BGP) External BGP (E-BGP) Internal BGP (I-BGP) Internal BGP (I-BGP)

Interior GatewayInterior Gateway

AS 1AS 1 AS 2AS 2

AS 3AS 3 E-BGP

E-BGP

I-BGP I-BGP

Informazioni su destinazioni esterne all’AS

Tra router dello stesso AS Tra router dello stesso AS

Determinare punto di uscita Determinare punto di uscita Regole di propagazione diverse Regole di propagazione diverse

Identificazione delle destinazioni

Lunghezza prefisso/prefisso Lunghezza prefisso/prefisso

16/5.1 16/5.1

Classless Inter-Domain Routing (CIDR)

Identificazione delle destinazioni

Aggregazione prima di propagare Aggregazione prima di propagare

Meno traffico di routing Meno traffico di routing Basi dati più piccole Basi dati più piccole

(9)

Una include l’altra Una include l’altra

Esempio: 8/5 include 16/5.1 Esempio: 8/5 include 16/5.1 16/5.1 è più specifico 16/5.1 è più specifico 8/5 include più destinazioni 8/5 include più destinazioni

Route sovrapposte Route sovrapposte

Quale usare? Quale propagare?

Problematica complessa Problematica complessa

Gli attributi Gli attributi

Informazioni articolate Informazioni articolate

Più delle metriche Più delle metriche Associati ad una route Associati ad una route Descrivono il percorso Descrivono il percorso

No metriche no lunghezza percorso

Gli attributi Gli attributi

Trattati in modo differente Trattati in modo differente

Specificato nella definizione Specificato nella definizione Un annuncio include

parecchi attributi Un annuncio include parecchi attributi

Non tutte le combinazioni sono ammissibili

Riconosciuto da ogni realizzazione Riconosciuto da ogni realizzazione

Well-known/optional Well-known/optional

Classificazione degli attributi Classificazione degli attributi

Sempre propagato Sempre propagato

Deve apparire nella descrizione del percorso

Mandatory/discretionary Mandatory/discretionary

Transitive/non-transitive Transitive/non-transitive Usato per optiona

Usato per optiona

Transitive: è propagato da un router che non lo riconosce Transitive: è propagato da un router che non lo riconosce Contrassegnato come partial Contrassegnato come partial Non-transitive: eliminato da un router che non lo conosce Non-transitive: eliminato da un router che non lo conosce

Well-known Well Well--knownknown

Optional Optional Optional

Mandatory Mandatory Mandatory

Discretionary Discretionary Discretionary

Transitive Transitive

Transitive PartialPartialPartial

(10)

Origin Origin

Sempre presente (mandatory) Sempre presente (mandatory) Come è stata appresa una route Come è stata appresa una route

imparata tramite un

protocollo di routing interno all’ASimparata tramite un protocollo di routing interno all’AS IGP:

IGP:

imparata tramite scambi con l’esterno dell’ASimparata tramite scambi con l’esterno dell’AS EGP:

EGP:

Origin Origin

imparata né tramite IGP né tramite EGPimparata né tramite IGP né tramite EGP

Incomplete: Incomplete:

Route statica Route statica

Route non più raggiungibile Route non più raggiungibile

AS Path AS Path

Elenco degli AS da attraversare per raggiungere la destinazione Elenco degli AS da attraversare per raggiungere la destinazione

Componenti ordinati (AS_SEQUENCE)

Componenti non ordinati (AS_SET)

Sempre presente (mandatory) Sempre presente (mandatory)

AS sequence AS sequence AS set

AS set

AS 1AS 1 AS 2

AS 2

AS 3AS 3 AS 4AS 4

XX

Aggiornamento dell’AS Path Aggiornamento dell’AS Path

X:IGP;4 X:IGP;4 X:EGP;4,3

X:EGP;4,3 X:EGP;4,3 X:EGP;4,3 X:EGP;4,3,1

X:EGP;4,3,1

Politiche di routing Politiche di routing

Riflettono accordi tra gli AS Riflettono accordi tra gli AS

BGP permette di implementare politiche molto complesse BGP permette di implementare politiche molto complesse Configurate manualmente Configurate manualmente Imposte automaticamente Imposte automaticamente Criteri di scelta delle route Criteri di scelta delle route

Routing Information Base (RIB)

Una per vicino Una per vicino Adj-RIBs-In →

informazioni imparate dagli annunci ricevuti (e non scartati) Adj-RIBs-In →

informazioni imparate dagli annunci ricevuti (e non scartati)

Loc-RIB → informazioni usate per l’instradamento Loc-RIB → informazioni usate per l’instradamento

(11)

Una per vicino Una per vicino

Routing Information Base (RIB)

Adj-RIBs-Out →

informazioni da propagare Adj-RIBs-Out →

informazioni da propagare

Realizzazione delle politiche Realizzazione delle politiche

Adj-RIBs-In Adj

Adj--RIBsRIBs--InIn

Adj-RIBs-Out AdjAdj--RIBsRIBs--OutOut Policy

Information Base (PIB)

Policy Policy Information Information Base (PIB) Base (PIB) Configurazione Configurazione

Decision Process Decision Process Decision Process

Loc-RIB LocLoc--RIBRIB

Phase 2: scelta per uso locale Phase 2: scelta per uso locale Phase 3: disseminazione Phase 3: disseminazione Decision Process Decision Process

Phase 1: grado di preferenza Phase 1: grado di preferenza

Più precisamente Più precisamente

Adj-RIBs-In Adj

Adj--RIBsRIBs--InIn

Adj-RIBs-Out Adj

Adj--RIBsRIBs--OutOut Phase 1 Phase Phase11

Loc-RIB Loc Loc--RIBRIB

Gradi preferenza Gradi preferenza Gradi preferenza Phase 2

Phase Phase22

Phase 3 Phase Phase33

Una funzione, dati gli attributi di un percorso, restituisce un grado di preferenza

Phase 1 Phase 1

Numero intero Numero intero

Usato nelle fasi successive Usato nelle fasi successive

Configurazione politiche definizione della funzione Configurazione politiche

definizione della funzione

Grado di preferenza Grado di preferenza

Non deve essere basato su Non deve essere basato su Non esistenza di altre route Non esistenza di altre route Attributi di altre route Attributi di altre route Esistenza di altre route Esistenza di altre route Calcolato per ogni route indipendentemente Calcolato per ogni route indipendentemente

Usato da fasi 2 e 3 Usato da fasi 2 e 3

(12)

Selezione per propagazione all’interno dell’AS

Phase 3 Phase 3

Riduzione delle informazioni Riduzione delle informazioni Aggregazione delle route Aggregazione delle route Selezione per propagazione all’esterno dell’AS

Selezione per propagazione all’esterno dell’AS

Per esempio, access-list su Cisco Per esempio, access-list su Cisco Sintassi per la scrittura della PIB Sintassi per la scrittura della PIB Aspetti implementation-specific Aspetti implementation-specific

Funzione per il grado di preferenza Funzione per il grado di preferenza

I messaggi I messaggi

Inizio operatività di una peering session

Negoziazione della versione Negoziazione della versione All’instaurazione della connessione TCP All’instaurazione della connessione TCP Mesaggio Open Mesaggio Open

Può annullare (withdraw) molte route

Una sola route annunciata Una sola route annunciata Mesaggio Update

Mesaggio Update

Minimo tempo tra annunci Minimo tempo tra annunci Molte destinazioni

Molte destinazioni

Raggiungibili con la stessa route Raggiungibili con la stessa route

Mesaggio Keepalive Mesaggio Keepalive

Usato quando non si hanno informazioni di routing da trasmettere

Indica al router adiacente che il mittente è ancora attivo Indica al router adiacente che il mittente è ancora attivo