PDF de programación - Direccionamiento y enrutamiento en Internet

Direccionamiento y enrutamiento en

Internet

Avi Freedman
Ravi Sundaram

Esquema

Orígenes de Internet
Protocolos y paquetes

Direccionamiento - IPv4 frente a IPv6

Enrutamiento – visión global

BGP - modelo
BGP - convergencia y dificultades



Introducción

• Internet es una RED de redes – tanto desde el punto
de vista lógico como físico.
• Millones de ordenadores son capaces de comunicarse
entre sí en tiempo real.
• Almacenamiento y envío basados en paquetes.
• Direccionamiento – modo de identificar ordenadores.
• Enrutamiento – transmisión de paquetes desde un
origen hasta un destino.



Orígenes

• Experimento académico realizado en la década de los 60,

financiado por ARPA - Advanced Research Projects
Agency, conocida ahora como DARPA.

• Diciembre de 1969 – se activó la primera red de 4 nodos,

utilizando para ello una conexión de 56 kbps.

• 1978 – surge el protocolo IP.
• 1982 – surge TCP, ARPANET se divide en MILNET e

Internet.

• 1983 - Internet consta de 200 ordenadores.


Orígenes

• 1984 – nacen los grupos de noticias.
• 1986 – surge el DNS y, motivado por el correo electrónico,

sustituye a la tabla de host.

• 1988 – surge el gusano, creado por el CERT.
• 1989 – 100.000 ordenadores en Internet, con readaptación

del protocolo TCP para evitar congestionamiento.

• 1990 – tráfico comercial aún prohibido en el backbone de
Internet.

• 1991 – fin de la prohibición comercial, nace la www.

Orígenes

• Mayo de 1993 – última petición de la NSFNET para NAPs

privados.

• 1995 – vBNS sustituye a NSFNET – un servicio de
backbone de alto rendimiento que conecta ciertas
universidades y centros de investigación a una velocidad de
155 Mbps e incluso más, contrato otorgado a MCI
(reemplazado por Abilene 10 Gbps?).

• 2002 - 350 millones de hosts.

Observaciones

• Crecimiento sin precedentes.
• Control descentralizado – desafíos y oportunidades.
• Rendimiento.
• Fiabilidad.
• Contabilidad.
• Seguridad.
• Directorio.
• Argumentos finales sobre el diseño del sistema. ACM Trans
on Comp systems, noviembre de 1984, págs. 277-288.



Protocolos

FTP


SMTP

DNS

SNMP

TCP

UDP

ICMP

IP

Paquetes

De 46 a 1500 bytes

Cabecera
Ethernet

IP

Cabecera
TCP/UDP

Datos de la aplicación Cola

Ethernet

Direccionamiento

• Direcciones de 32 bits - a.b.c.d
• 4.000 millones de direcciones posibles.
• 250 millones de hosts aproximados.
• IPv4 basado en RFC791 en 1981.

Direccionamiento

• Clasificación en el pasado:
Class A - primeros 8 bits fijos.
Class B - primeros 16 bits fijos.
Class C - primeros 24 bits fijos.

• CIDR – Enrutamiento de interdominio sin clases.

a.b.c.d/m - primeros bits m fijos.
p.ej. 0.0.0.0/29 = 0.0.0.0 a 0.0.0.7

• Regla de enrutamiento de correspondencia más concreta.

Direccionamiento

• Cuestiones relacionadas con IPv4.

Reducción del espacio de direcciones.
Control realizado por el registro central.
Ninguna consideración sobre redes/enrutamiento.
Ninguna consideración de seguridad.
Ninguna consideración en cuanto a calidad de
servicio (QoS).

Esto quedaría resumido como escalabilidad, seguridad y
calidad de servicio (QoS).

Direccionamiento

• IPv6 o IPng
128 bits
jerárquico (basado en la red);
seguro (usa IPSec);
calidad de servicio (bits repartidos para el etiquetado
de flujos).

Direccionamiento

• La migración tendrá lugar de 4 a 6.

Escalabilidad - CIDR/NAT (no antes del 2010).
Seguridad - IPSec y nivel de aplicación.
Calidad de servicio – nivel de aplicación.

Enrutamiento

• Internet – colección de sistemas autónomos.
• Sistema autónomo (AS) – conjunto de enrutadores que

comparten la misma política de enrutamiento, los
enrutadores de un AS son parecidos a las oficinas de
correo de un país.

• Protocolo de enrutamiento – colección de reglas para el

envío de paquetes.

Enrutamiento
• Distancia (ruta)- protocolos de vector.
Las actualizaciones de enrutamiento incluyen vector
de distancias (rutas);



Cada nodo posee un árbol de ruta más corta
(basado en una política).

Ejemplos: RIP, BGP4

Enrutamiento

• Protocolos de estados de conexión.



Las actualizaciones de enrutamiento incluyen estados
de conexión y otras actualizaciones;
Cada nodo contiene un grafo completo;
Ejemplo: OSPF

Localización de rutas

[koods@koods-desktop ~]$ traceroute www.berkeley.edu
traceroute to arachne.berkeley.edu (169.229.131.109), 30 hops max, 40 byte packets
1 172.24.80.1 (172.24.80.1) 0.401 ms 0.308 ms 0.291 ms
2 corp2-primary.kendall.akamai.com (172.24.8.2) 0.411 ms 0.334 ms 0.331 ms
3 akafire.kendall.akamai.com (172.24.44.4) 0.280 ms 0.208 ms 0.368 ms
4 65.202.32.3 (65.202.32.3) 0.608 ms 1.651 ms 0.923 ms
5 65.202.33.246 (65.202.33.246) 0.754 ms 0.664 ms 0.832 ms
6 serial4-0-2.hsipaccess1.Boston1.Level3.net (166.90.184.53) 0.912 ms 0.888 ms 0.881 ms
7 unknown.Level3.net (64.159.3.141) 1.349 ms 1.696 ms 2.018 ms
8 so-2-0-0.mp2.SanJose1.Level3.net (64.159.0.218) 85.658 ms 85.287 ms 84.278 m
9 gige9-1.hsipaccess1.SanJose1.Level3.net (64.159.2.103) 84.682 ms 84.666 ms 84.404 m
10 unknown.Level3.net (209.247.159.110) 80.145 ms 80.630 ms 80.860 m
11 ucb-gw--qsv-juniper.calren2.net (128.32.0.69) 83.634 ms 84.703 ms 110.922 m
12 vlan196.inr-201-eva.Berkeley.EDU (128.32.0.74) 83.906 ms 87.205 ms 85.161 m
13 vlan209.inr-203-eva.Berkeley.EDU (128.32.255.2) 138.753 ms 141.608 ms 142.004 m
14 arachne.Berkeley.EDU (169.229.131.109) 140.416 ms 128.705 ms 143.716 ms

BGP - modelo

• Modelado como una colección de sistemas autónomos

con relaciones no jerárquicas entre sí.

• Se puede considerar como un grafo G=(V,E) con

sistemas autónomos representados por los vértices v
en V, y por relaciones no jerárquicas por
extremidades e en E.

12222

701

BGP- Protocolo de puerta de enlace en el borde
• Protocolo vector-ruta – cada vértice mantiene un árbol de

camino más corto, arraigado en sí mismo.

• “más corto” – combinación de política y distancia basada
en métrica.
• Cada sistema autónomo selecciona sus rutas basadas en
su propia política, junto a las mejores rutas de sus vecinos.

BGP – modelo idealizado

• Internet está modelada como un grafo no dirigido G=(V,E), donde
V corresponde a los sistemas autónomos y E a las relaciones no
jerárquicas.

• Cada vértice asimila un conjunto de avisos de ruta de sus vecinos.

• Un aviso de ruta es un registro con los siguientes atributos:
nlri: información sobre accesibilidad de capa de red, ej. 1.2.3.4

as_path: lista ordenada de vértices, comenzando con el próximo

salto, ej. 701 12222.
loc_pref: preferencia local con dlp usado para representar un valor
por defecto.

BGP – modelo idealizado

• Cada vértice selecciona la mejor ruta para un determinado

destino. Si posee muchas rutas r_1, r_2 … r_k con el
mismo destino, es decir, r_i.nlri = r_j.nlri, éste selecciona la
primera con base en la más alta local-pref, luego con base
en el as_path más corto, con vínculos rotos arbitrariamente.

• Transformaciones de ruta:

- Las preferencias locales no son comunicadas.
- Sin bucles: v nunca acepta rutas r donde v ε r.as_path.
- El conjunto de rutas seleccionadas en v se pasa a los vecinos
de v con v colgando de as_path.
- Política de importación y exportación.

BGP – modelo idealizado

• Política de importación y exportación.

Exportar

Importar

Verdadero=> aceptar

17 ε

as_path => rechazar

• Si todas las reglas de importación y exportación fuesen
“verdadero => aceptar”, BGP quedaría reducido a un



puro protocolo de vector de distancia.

BGP – modelo idealizado
• Comportamiento dinámico.

Informalmente, un sistema BGP S = <G, Policy(G), S0>,
compuesto de un grafo AS G= (V,E), posee una
política de importación y exportación para cada v_j en V,
y un estado inicial S0 = (c0_1,c0_2,…c)_n), donde
c0_j es el destino originado por v_j.

• Si v_j se activa, obtendrá avisos de ruta de sus vecinos

más próximos y seleccionará sus mejores rutas.

BGP – cuestión de convergencia

• Grafo de estado.

- Grafo dirigido de todos los estados con S_j => S_k, si existe un v
cuya activación provoque el cambio.
- Se dice que un estado S es final si S => S en la activación de
cualquier v.
- Se dice que un sistema BGP se puede solventar si posee un
estado final.
- Se dice que un sistema BGP es convergente si termina en un
estado final independientemente de la secuencia de
activación.

BGP - cuestión de convergencia

• ¿Es posible que la política configurada localmente de modo

correcto provoque anomalías globales de enrutamiento?
• ¿Puede el protocolo divergir, es decir, puede hacer que
una colección de sistemas autónomos intercambien
mensajes continuamente sin llegar a converger?

BGP - cuestión de convergencia

• ¿Es un sistema BGP divergente en la práctica? Existen historias

terroríficas sobre redes que se han configurado accidentalmente para
absorber todo el tráfico, pero que no dan pruebas de trampas a gran
escala.

• Sin embargo, se dan muchos y frecuentes casos de convergencia
retrasada hasta 50 minutos. En Labovitz, C., Ahuja, A., Bose, A. y
Jahanian, F., “Delayed Internet Routing Convergence”, Proceedings
of Sigcomm, 2000, págs. 175-18, los autores realizan experimentos en
los que apartan una ruta y la sustituyen por otra, para ver cuánto
tiempo antes descarga en Internet, mientras es observada desde
varios puntos con ventaja.

BGP - cuestión de convergencia

• Además de las varias anomalías espec