(Distance Vector e Link State Packet) L`instradamento nelle

Reti di Telecomunicazioni
R. Bolla, L. Caviglione, F. Davoli
  Realizzazione degli algoritmi di routing
(Distance Vector e Link State Packet)
  L’instradamento nelle reti IP
  Protocolli EGP e IGP
  Name server
  La crescita di Internet
33.2
  Come si è visto, l’algoritmo di Bellman-Ford si presta
ad una versione distribuita. L’informazione
propagata tra i nodi consiste in una coppia
[destinazione (detta vector), distanza] per ogni
destinazione raggiungibile.
  Il procedimento non è facilmente “scalabile”
all’aumentare delle possibili destinazioni, può
convergere molto lentamente e dar luogo a
oscillazioni (e a fenomeni di looping, in assenza di
meccanismi adeguati per evitarli).
33.3
Problema
del “conto
all’infinito”
nel distance
vector
A. Pattavina, Reti di
Telecomunicazione
– Networking e
Internet, 2a ed.,
McGraw-Hill, 2007
33.4
  Anche per l’algoritmo di Dijkstra (detto anche Shortest
Path First, SPF) è possibile una realizzazione
computazionalmente distribuita (ma non ad
informazione distribuita), basata sulla costruzione ed il
mantenimento ad ogni router della mappa completa
della rete (interessata dall’algoritmo), tramite lo scambio
di Link State Packet (LSP).
  I LSP sono inviati da ogni router agli altri in selective
flooding, per descrivere la mappa dei propri nodi
adiacenti (appresa tramite protocolli di neighbour
greetings).
33.5
  Internet adotta un instradamento gerarchico su
più livelli (subnet, network, autonomous
system).
  I protocolli SPF (tipo LSP) e distance vector
sono entrambi usati.
  Gli Autonomous Systems (AS) sono
raggruppamenti di network in un “dominio”
riconosciuto, identificato univocamente e
unicamente amministrato.
33.6
 
Within the Internet, an Autonomous System (AS) is a collection of connected IP routing prefixes
under the control of one or more network operators that presents a common, clearly defined routing
policy to the Internet, cf. RFC 1930, Section 3.
 
Originally, the definition required control by a single entity, typically an Internet service provider or a
very large organization with independent connections to multiple networks, that adhere to a single
and clearly defined routing policy. See RFC 1771, the original definition (now obsolete) of the
Border Gateway Protocol (BGP). The newer definition of RFC 1930 came into use because multiple
organizations can run BGP using private AS numbers to an ISP that connects all those
organizations to the Internet. Even though there are multiple Autonomous Systems supported by
the ISP, the Internet only sees the routing policy of the ISP. That ISP must have an officially
registered Autonomous System Number (ASN).
 
A unique ASN is allocated to each AS for use in BGP routing. With BGP, AS numbers are important
because the ASN uniquely identifies each network on the Internet.
 
AS numbers were, until 2007, 16-bit integers, which allowed for a maximum of 65536 assignments.
The Internet Assigned Numbers Authority (IANA) has designated ASN numbers 64512 through
65534 to be used for private purposes. The ASNs 0, 54272-64511, and 65535 are reserved by the
IANA and should not be used in any routing environment. ASN 0 may be used to label non-routed
networks. All other ASNs (1 - 54271) are subject to assignment by IANA, and, as of 2008-09-09,
only 49152-54271 remained unassigned. RFC 4893 introduced 32-bit AS numbers, which IANA
has begun to allocate. 32-bit AS numbers are written in the form x.y, where x and y are 16-bit
numbers. 0.y AS numbers are exactly the old 16-bit AS numbers, 1.y numbers and 65535.65535
are reserved and the remainder of the space is available for allocation.
http://en.wikipedia.org/wiki/Autonomous_system_(Internet)
33.7
  La presenza degli AS fa sì che i router
vengano distinti in Interior Router (IR) e
Border Router (BR).
  Gli IR instradano entro un AS, mentre i BR
instradano tra diversi AS.
  I protocolli di routing sono distinti in Interior
Gateway Protocol (IGP) ed in Exterior
Gateway Protocol (EGP).
33.8
AS 137
AS 66
I
I
E
E
33.9
  Routing Information Protocol (RIP) [RFC 1058 e 1723]:
è un IGP molto diffuso, di tipo distance vector, con
metrica in “hop” e che presenta diversi limiti (legati al
distance vector). L’intervallo di scambio delle tabelle
è di 30 s; un vicino è considerato non più
raggiungibile se rimane in silenzio per più di 180 s.
  Interior Gateway Routing Protocol (IGRP): è un IGP
proprietario Cisco, di tipo distance vector, con
metrica molto più sofisticata. Consente il multipath.
33.10
  Open Shortest Path First (OSPF) [RFC 1247 e 1583]: è
un IGP di tipo LSP, che definisce gerarchie esplicite
entro l’AS (aree).
  Classifica i router in quattro categorie.
  In OSPF, inoltre:
  Tutti gli scambi sono autenticati
  E’ possibile scegliere tra percorsi multipli di ugual costo
  E’ consentito definire diverse metriche per traffico con
diverso TOS (in presenza di classi di servizio differenziate
  Il supporto dell’instradamento multicast si integra
semplicemente con quello dell’unicast
33.11
Boundary
Router
R1
Altro
Sistema
Autonomo
Area 1
H1
R2
R3
H3
Area 2
Area Border
Router
H5
R6
R5
H2
R4
Backbone Area
H4
33.12
  In ambito OSPF sono definite quattro
tipologie di router:
 Autonomous System Border Router (tra AS)
 Area Border Router (all’infuori di un AS verso
un’area che non può essere considerata AS)
 Backbone Router (router che instradano su una
backbone)
 Internal Router (router che instradano traffico
all’interno di un AS)
33.13
  Exterior Gateway Protocol (EGP) [RFC 904]: si
trattava di un EGP operante come un distance
vector, propagando informazioni di raggiungibilità
(advertising), senza metriche associate.
  EGP era basato sul concetto di core system (ormai
obsoleto).
Core
Router
AS 1
Core
Router
AS 2
Core
Router
AS 7
AS n
33.14
  EGP è stato sostituito con il Border Gateway
Protocol (BGP) [RFC 1771, 1772, 1773], un
EGP di tipo distance vector, che propaga la
sequenza di AS verso una destinazione.
  BGP non stabilisce i meccanismi per
determinare i percorsi tra AS, ma piuttosto
quelli per distribuire le informazioni sul
percorso.
  Per BGP, l’Internet è un grafo di AS,
ciascuno identificato dal proprio numero. I
vicini immediati nel grafo sono detti peers.
33.15
  Le informazioni in BGP sono propagate attraverso 4 tipi di
messaggi (usando TCP e il numero di porta 179):
  OPEN: inviato da un gateway BGP ai peer per primo contatto
  UPDATE: per segnalare a un peer un percorso verso la
destinazione
  KEEPALIVE: in risposta a OPEN e per segnalare lo stato di
attività, pur non avendo informazioni nuove da spedire
  NOTIFICATION: per segnalare errori o la chiusura della sessione
con il peer
  L’apparente semplicità non tragga in inganno: il BGP è molto
complesso
  Pur essendo un protocollo inter-AS, può essere usato anche
come canale di comunicazione tra router BGP dello stesso AS
(connessioni “interne” o IBGP, contrapposte a quelle tra AS,
che sono “esterne” o EBGP), per scambiare aggiornamenti.
33.16
  Per l’utente è molto più facile ricordare un nome
piuttosto che un indirizzo di rete.
  In una rete di grandi dimensioni, è indispensabile
mantenere le corrispondenze tra nomi e indirizzi
(e.g., dist.dist.unige.it e 130.251.1.4) in una base
dati distribuita (name server).
  Un sistema simile mantiene la corrispondenza tra gli
applicativi e i loro SAP (porte).
33.17
  Quando Internet era composta da pochi nodi
(circa 50) la corrispondenza nome-indirizzo
era mantenuta in un file di testo chiamato
host.txt .
  Con l’aumento del numero degli host tale
soluzione non è più adatta:
 Non scalabile
 Soggetta ad errori
 Centralizzata
33.18
  IETF ha dunque sviluppato un meccanismo
per la risoluzione dei nomi.
  Il sistema utilizzato attualmente in Internet
per la risoluzione dei nomi è il Domain Name
Server (DNS).
  È definito in vari documenti ma i più
rappresentativi sono RFC 1034 e RFC 1033
33.19
  È un database distribuito. I nodi del
database sono interconnessi utilizzando una
organizzazione gerarchica.
  Quando si cerca una corrispondenza nel
database (Resolution Query) si interroga un
nodo. Nel caso in cui non vi sia
l’informazione voluta si propaga la richiesta
ad un altro nodo.
  Tecnicamente l’operazione si chiama
risoluzione (DNS look-up).
33.20
Internet sta evolvendo rapidamente. Il suo
tasso di crescita è molto elevato.
  Un primo censimento “ufficiale”, patrocinato dall’IETF, è
avvenuto nel 1992.
  I dati analizzati si riferivano ad un periodo temporale compreso
tra il 1981 ed il 1991.
  Sono stati presi in considerazione diverse tipologie di dati,
tuttora utilizzate nelle analisi più recenti:
  il numero di host
  il numero di domini
  la ripartizione dei top-level domain (ad es., .it .com .edu)
  L’RFC che analizza e presenta tali dati è l’RFC 1296.
33.21
  Oggi sono molti gli enti che si interessano di
analizzare la struttura e le dimensioni di
Internet.
  Ad esempio l’ Internet Software Consortium
(ISC), raccoglie periodicamente dati
rappresentativi della rete Internet.
  I dati sono prelevabili all’URL www.isc.org
33.22
Internet Host Count History
Number Of Internet Hosts
Date
08/1981
05/1982
08/1983
10/1984
10/1985
02/1986
11/1986
12/1987
07/1988
10/1988
01/1989
07/1989
10/1989
10/1990
01/1991
07/1991
10/1991
01/1992
04/1992
07/1992
Hosts
213
235
562
1,024
1,961
2,308
5,089
28,174
33,000
56,000
80,000
130,000
159,000
313,000
376,000
535,000
617,000
727,000
890,000
992,000
10/1992
1,136,000
Date
01/1993
04/1993
07/1993
10/1993
01/1994
07/1994
10/1994
01/1995
07/1995
01/1996
07/1996
01/1997
07/1997
01/1998
07/1998
01/1999
Hosts
1,313,000
1,486,000
1,776,000
2,056,000
2,217,000
3,212,000
3,864,000
4,852,000
6,642,000
9,472,000
12,881,000
16,146,000
19,540,000
29,670,000
36.739,000
43,230,000
(5,846,000)
(8,200,000)
(14,352,000)
(16,729,000)
(21,819,000)
(26,053,000)
Date
07/1999
01/2000
07/2000
01/2001
07/2001
01/2002
07/2002
01/2003
01/2004
07/2004
01/2005
07/2005
01/2006
07/2006
01/2007
07/2007
01/2008
Hosts
56,218,000
72,398,092
93,047,785
109,574,429
125,888,197
147,344,723
162,128,493
171,638,297
233,101,481
285,139,107
317,646,084
353,284,187
394,991,609
439,286,364
433,193,199
489,774,269
541,677,360
07/2008
570,937,778
33.23
RIPE NCC
The RIPE NCC is one of five Regional
Internet Registries (RIRs) providing
Internet resource allocations,
registration services and coordination activities that support the
operation of the Internet globally.
http://www.ripe.net/is/hostcount/?wicket:interface=:4:1:::
33.24
  Come operano gli algoritmi distribuiti di tipo
LSP?
  Cos’è un AS?
  Descrivete le caratteristiche di alcuni IGP ed
EGP
  Come opera il BGP?
  Cosa fà un name server?
33.25