Encaminamiento en Internet

© GSyC 2000

Encaminamiento en Internet − 1

El problema del encaminamiento


Encaminar : encontrar el mejor camino entre dos nodos de la red.




¿Mejor? 

el más rápido



el de más ancho de banda



el más barato



el más descongestionado

© GSyC 2000

Encaminamiento en Internet − 2

Algoritmos de encaminamiento


Generan la tabla de encaminamiento.




Luego, para encaminar un datagrama, sólo hay que consultar la tabla.




Normalmente se requiere la colaboración entre nodos para generar las tablas: Protocolos de Encaminamiento.

© GSyC 2000

Encaminamiento en Internet − 3

Objetivos de los protocolos de encaminamiento







Descubrir las mejores rutas en cada momento Generar tablas consistentes. Minimizar número de entradas en la tabla. Minimizar número y tamaño de los mensajes que intercambian los encaminadores para generarla.

© GSyC 2000

Encaminamiento en Internet − 4

Familias de protocolos de encaminamiento


Los protocolos de encaminamiento más usados en redes TCP/IP pueden clasificarse en dos grupos: 

Protocolos de Vector de Distancias (distance vector protocols)



Procolos de Estado del Enlace (link state protocols)

© GSyC 2000

Encaminamiento en Internet − 5

Protocolos de Vector de Distancias


Cada nodo mantiene una tabla de este estilo: Desde A hasta Enlace Coste A local 0 B 1 1 C 2 3 D 2 5




Periódicamente, cada nodo pasa su tabla a sus nodos vecinos.




Con la información recibida de sus vecinos, cada nodo recalcula su tabla.

© GSyC 2000

Encaminamiento en Internet − 6

Problemas de los Protocolos de Vector de Distancias


Las malas noticias se propagan lentamente: 




un enlace caído se puede manifiestar como un “coste” que crece en cada ronda, haciéndose cada vez mayor (cuenta hacia infinito).

Se pueden formar (temporalmente) bucles en las tablas (efecto rebote). 

una solución: además de enviar las tablas a los vecinos periódicamente, se pueden enviar por causa de un evento externo (cambio de condiciones de la red).

© GSyC 2000

Encaminamiento en Internet − 7

Protocolos de Estado del Enlace


Todos los nodos mantienen una copia completa del mapa de la red, y calculan las rutas sobre ese mapa siguiendo el mismo algoritmo A

1

B

2 C

© GSyC 2000

3 4

D

Desde A A B B C C D D

Hasta Enlace Distancia B 1 1 C 2 1 A 1 1 D 3 1 A 2 1 D 4 1 B 3 1 C 4 1

Encaminamiento en Internet − 8

Protocolos de Estado del Enlace


Cada nodo manda periódicamente el estado del enlace con sus nodos vecinos: 

El nodo A mandaría:


De A a B, enlace 1, distancia 1, número 1




De A a C, enlace 2, distancia 1, número 1

© GSyC 2000

Encaminamiento en Internet − 9

Protocolos de Estado del Enlace





Los mensajes se mandan por inundación: 

se emiten por todos los enlaces salientes



cuando se recibe uno:


si es nuevo o tiene un número mayor que el presente en el mapa, se actualiza el mapa y se reenvía.




si tiene un número menor, se manda el de la tabla por en enlace que me llegó el mensaje (que es viejo).




si tiene un número igual, no se hace nada.

Con la tabla los nodos aplican el Algoritmo de Dijkstra para encontrar las rutas óptimas.

© GSyC 2000

Encaminamiento en Internet − 10

Ventajas de los Protocolos de Estado del Enlace


Convergen más rápido y sin bucles.




Permiten usar varias métricas para calcular el mejor camino




Permiten obtener varias rutas alternativas para un mismo destino: balanceo de tráfico...




Representan mejor las “rutas hacia el exterior”

© GSyC 2000

Encaminamiento en Internet − 11

Problemas de los Protocolos de Estado del Enlace


Son mucho más complejos que los de Vector de Distancia.




Es imprescindible asegurar la consistencia de las tablas. Si distintos nodos tienen tablas distintas, la situación es desastrosa.




Las tablas pueden hacerse muy grandes.




Pueden necesitarse muchos mensajes para propagar las tablas.




Necesito abordar problemas de seguridad.

© GSyC 2000

Encaminamiento en Internet − 12

Protocolos Interiores y Exteriores


A principios de los 80, Internet era una sola red. Las tablas mantenían entradas para todas las subredes.




En 1982 se decide agrupar subredes en Sistemas Autónomos (AS):  Uno de los AS es el backbone, y a él se conecta al menos un

encaminador de cada uno de los otros AS (representante).  Cada AS ejecuta Protocolos Interiores de Encaminamiento

para sus subredes.  Los encaminadores representantes de cada AS ejecutan un

Protocolo Exterior de Encaminamiento. © GSyC 2000

Encaminamiento en Internet − 13

Ejemplos de protocolos de encaminamiento





Protocolos Interiores: 

RIP (Routing Information Protocol)



OSPF (Open Shortest Path First)

Protocolos Exteriores: 

EGP (Exterior Gateway Protocol)



BGP (Border Gateway Protocol)

© GSyC 2000

Encaminamiento en Internet − 14

RIP


RIP (Routing Information Protocol) es el protocolo interior más usado en Internet, aunque va siendo reemplazado por OSPF.




Deriva de GGP (Gateway to Gateway Protocol), usado en los primeros tiempos de Internet.




Es un protocolo de Vector de Distancias.




Versiones: 

Versión 1 (RFC−1058, Junio 1988)



Versión 2 (RFC−2453, Noviembre 1998)

© GSyC 2000

Encaminamiento en Internet − 15

RIP−1: Características






El coste de cada ruta es el número de saltos. El infinito es 16. Los mensajes se encapsulan en datagramas UDP. Se envían mensajes: 




cada 30 segundos (mediante broadcast)



“disparados por eventos”



como respuesta a solicitudes

Se desaconseja que los host finales “escuchen” los mensajes para mantener su tabla de encaminamiento.

© GSyC 2000

Encaminamiento en Internet − 16

RIP−2: Novedades


Permite manejar máscaras de subred.




Soporta autentificación en los mensajes.




Puede enviar sus mensajes utilizando multicast: 

Tres modos de operación:


Envía mensajes con el formato RIP−1 por broadcast




Envía mensajes con el formato RIP−2 por broadcast




Envía mensajes con el formato RIP−2 por multicast

© GSyC 2000

Encaminamiento en Internet − 17

OSPF


OSPF (Open Shortest Path First) es un protocolo más moderno y mucho más complejo que RIP.




Es un protocolo interior, aunque puede usarse en redes grandes.




Es un protocolo de Estado del Enlace.




Versión actual: Versión 2 (RFC−2328, Abril 1998).




Se considera mucho mejor que RIP y es el protocolo “recomendado” en Internet.

© GSyC 2000

Encaminamiento en Internet − 18

OSPF: Características







Sus mensajes se encapulan en datagramas IP. Distingue entre máquinas finales y encaminadores Incluye soporte especial para redes de broadcast:


se elige uno de los encaminadores de la red como encaminador designado




el resto consideran una topología de estrella con él (ahorra rutas)

Incluye soporte especial para redes grandes:


se divide la red en áreas




cada área tiene al menos un encaminador de borde de área, que es el que anuncia hacia fuera de ella las redes disponibles dentro (y en sentido contrario)

© GSyC 2000

Encaminamiento en Internet − 19

OSPF: Características


Se comprueba periódicamente que los enlaces siguen operacionales (protocolo de HELLO).




La gestión del número de serie de los mensajes es compleja para resolver el problema de los encaminadores que rearrancan: 

Espacio de números de “piruleta”:

−N+1

N−1 N/2 0

© GSyC 2000

Encaminamiento en Internet − 20

EGP


EGP (Exterior Gateway Protocol) fue el primer protocolo exterior usado en Internet.




Es un protocolo con un “aire” de Vector de Distancias.




Se define con la RFC−827 en Octubre de 1982




No es usable en la Internet actual, más que en algunas partes muy concretas




Actualmente se utiliza BGP.

© GSyC 2000

Encaminamiento en Internet − 21

EGP: Características


EGP organiza el intercambio (entre dos encaminadores vecinos) de las rutas “alcanzables” por cada uno de ellos.




Se encapsula en datagramas IP.




Tres partes: 

Adquisión de vecinos



Alcanzabilidad de vecinos



Alcanzabilidad de redes

© GSyC 2000

Encaminamiento en Internet − 22

EGP: Adquisición de vecinos


Propósito: Ver si dos encaminadores adyacentes están de acuerdo en ser vecinos, es decir, están dispuestos a encaminar el tráfico que les pase el otro.




Normalmente un encaminador sólo escoge sus vecinos de entre los de una lista previa.




El protocolo seguido es de solicitud−respuesta, con plazos y retransmisiones para solucionar las pérdidas.

© GSyC 2000

Encaminamiento en Internet − 23

EGP: Alcanzabilidad de vecinos


Propósito: comprobar si el enlace con el vecino sigue operativo.




El protocolo seguido es de solicitud (Hello) − respuesta (I Hear You), con plazos y retransmisiones, y se ejecuta periódicamente.

© GSyC 2000

Encaminamiento en Internet − 24

EGP: Alcanzabilidad de redes


Propósito: intercambiar la lista de redes alcanzable desde cada vecino.




El protocolo seguido es de “sondeo” por parte de los vecinos, repetidos periódicamente.




La respuesta al sondeo es un mensaje con la lista de todas las redes que alcanza el vecino, junto con su métrica.

© GSyC 2000

Encaminamiento en Internet − 25

EGP: Problemas


Estaba pensado para una interconexión de Sistemas Autónomos en forma de árbol. Con la Internet actual, se forman multitud de bucles difícilmente evitables.




El tamaño de los mensajes con la lista de redes accesibles puede ser muy grande y obliga a fragmentar el datagrama IP: muy grave




Muchos plazos y retransmisiones para evitar las pérdidas.

© GSyC 2000

Encaminamiento en Internet − 26

BGP


BGP (Border Gateway Protocol) es el protocolo exterior recomendado en Internet.




Junto con CIDR (Classless Inter−Domain Routing) ha permitido la subsistencia del IP actual pese a la escasez de direcciones IP y el crecimiento exponencial de las tablas de encaminamiento.




BGP se empezó a publicar en 1989. Acualmente se utiliza la Versión 4 (RFC−1771, Marzo 1995).

© GSyC 2000

Encaminamiento en Internet − 27

CIDR


Problema con las “clases” de direcciones IP.










Clases A: pocas y muy “grandes” Clases C: muchas, pero muy pequeñas Clases B: las buenas, pero ya no quedan casi

Además, cada dirección de clase requiere una entrada en las tablas de routing. Solución:




Se dan clases C contiguas Se olvidan las máscaras de subred Se pasa a usar prefijos de superred para encaminar: 197.8.0/22 sólo se miran los 22 primeros bits

© GSyC 2000

Encaminamiento en Internet − 28

BGP: Características


Se encapsula sobre TCP: se evitan todos los plazos y retransmisiones.




Para evitar los bucles, se utilizan Vectores de Ruta (path vectors) como evolución de los Vectores de Distancia: 



© GSyC 2000

cada red accesible se anuncia junto con la lista de AS que hay desde el encaminador que la anuncia hasta esa red cuando se recibe un auncio, si el AS del que lo recibe ya está en el lista del trayecto, se rechaza Encaminamiento en Internet − 29

BGP: Intercambio inicial


Juega el papel de la adquisición de vecinos de EGP.




Se abre la conexión TCP y se intercambian mensajes; si se rechaza al vecino se cierra la conexión.

© GSyC 2000

Encaminamiento en Internet − 30

BGP: Actualización de rutas


Una vez abierta la conexión, se intercambian mensajes.




Cada mensaje puede incluir:







una lista de rutas que se rechazan (se habrían anunciado antes y ya no son válidas)




el anuncio de una sola ruta, incluyendo el trayecto de ASs.

Juega el papel de la alcanzabilidad de redes de EGP.

© GSyC 2000

Encaminamiento en Internet − 31

BGP: Estoy vivo


Por la conexión TCP abierta, periódicamente cada vecino envía mensajes KEEPALIVE.




El periodo mínimo se negocia en el intercambio inicial.




Estos mensajes juegan el papel de la alcanzabilidad de vecinos de EGP.




Además, por la conexión abierta se pueden enviar mensajes notificando situaciones de error.

© GSyC 2000

Encaminamiento en Internet − 32

Encaminamiento por Políticas


Originalmente Internet era un “bien público” a disfrutar entre todos a partes iguales.




Desde que aparece la Internet “comercial” la cosa cambia: 

¿Encamina una empresa el tráfico de otra?



¿Cómo se tarifica y cómo influyen las eso en el encaminamiento?

El Encaminamiento por Políticas (Policy Routing) es hoy materia de investigación en curso.




© GSyC 2000

Encaminamiento en Internet − 33

Encaminamiento por Políticas: consideraciones Es necesario tener en cuenta de dónde vienen los datagramas para, por ejemplo, elegir entre varios proveedores:




usuario 1

usuario 2

usuario 3




proveedor 1

red regional

proveedor 2

destino

proveedor 3

Las soluciones vienen por usar el encaminamiento en origen (source routing) o tunneling.

© GSyC 2000

Encaminamiento en Internet − 34

Encaminamiento por Políticas: consideraciones


Otros factores a considerar:  Tarifas que se cobran  Prioridad del tráfico propio frente al alquilado  Cuestiones de calidad de servicio







Es complejo de hacer sin un protocolo de Estado de Enlace que haga juicios globales. Ejemplo: IDPR (Inter− Domain Policy Routing). Otra aproximación: MPLS (Multiprotocol Label Switching):





© GSyC 2000

En vez de encaminar por direcciones IP, se hace según una pequeña etiqueta Las etiquetas se colocan como resultado de las diferentes políticas de encaminamiento a aplicar Encaminamiento en Internet − 35