Reti di Telecomunicazioni R. Bolla, L. Caviglione, F. Davoli

33.2

 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.3

  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.4

A. Pattavina, Reti di Telecomunicazione – Networking e Internet, 2a ed., McGraw-Hill, 2007

Problema del “conto all’infinito” nel distance vector

33.5

  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.6

  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.7

  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.8

  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.9

E

I

E

I AS 137 AS 66

33.10

  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.11

  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.12

R2 H5 R6

R5 H2

H4 H3

R3

R4

Backbone Area

Area 2 R1

Altro Sistema

Autonomo H1

Boundary Router

Area 1

Area Border Router

33.13

  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.14

  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).

AS 1 AS 2 AS 7 AS n

Core Router

Core Router

Core Router

33.15

 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.16

  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.17

  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.18

 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.19

  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.20

 È 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.21

  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.

Internet sta evolvendo rapidamente. Il suo tasso di crescita è molto elevato.

33.22

 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.23

Internet Host Count History Number Of Internet Hosts

Date Hosts 08/1981 213 05/1982 235 08/1983 562 10/1984 1,024 10/1985 1,961 02/1986 2,308 11/1986 5,089 12/1987 28,174 07/1988 33,000 10/1988 56,000 01/1989 80,000 07/1989 130,000 10/1989 159,000 10/1990 313,000 01/1991 376,000 07/1991 535,000 10/1991 617,000 01/1992 727,000 04/1992 890,000 07/1992 992,000

10/1992 1,136,000

Date Hosts 01/1993 1,313,000 04/1993 1,486,000 07/1993 1,776,000 10/1993 2,056,000 01/1994 2,217,000 07/1994 3,212,000 10/1994 3,864,000 01/1995 4,852,000 (5,846,000) 07/1995 6,642,000 (8,200,000) 01/1996 9,472,000 (14,352,000) 07/1996 12,881,000 (16,729,000) 01/1997 16,146,000 (21,819,000) 07/1997 19,540,000 (26,053,000) 01/1998 29,670,000 07/1998 36.739,000 01/1999 43,230,000

Date Hosts 07/1999 56,218,000 01/2000 72,398,092 07/2000 93,047,785 01/2001 109,574,429 07/2001 125,888,197 01/2002 147,344,723 07/2002 162,128,493 01/2003 171,638,297 01/2004 233,101,481 07/2004 285,139,107 01/2005 317,646,084 07/2005 353,284,187 01/2006 394,991,609 07/2006 439,286,364 01/2007 433,193,199 07/2007 489,774,269 01/2008 541,677,360

07/2008 570,937,778

33.24 http://www.ripe.net/is/hostcount/?wicket:interface=:4:1:::

RIPE NCC The RIPE NCC is one of five Regional Internet Registries (RIRs) providing Internet resource allocations, registration services and co-ordination activities that support the operation of the Internet globally.

33.25

 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?