Encaminamiento en redes: conceptos, tipos y protocolos

5. Encaminamiento consiste en encontrar un camino de origen a destino a través de routers intermedios. Suele haber varias alternativas, lo más común es decidir el mejor, el más corto, en base a unas métricas como: número de saltos, distancia geográfica, retardo, promedio, ancho de banda, congestión de tráfico… que pueden ser combinadas linealmente. La elección del camino (enlace) se hace en base a: Tablas de encaminamiento (usando la dir. destino, no orientado a conexión): se basan en el siguiente salto, que estará en las entradas de las tablas por host, red o por defecto. Etiquetas: según las etiquetas del datagrama (flujo en IPv6) y reduce la complejidad de la tabla, usan siempre el mismo circuito (entrega en orden y predecible). // Next-Hop Routing, se basa en ppio. de optimización, si de A y C el mejor camino pasa por B, de B a C es el mismo camino. Por tanto el router solo conoce el salto al siguiente router. // ***Las tablas contienen info. sobre destino, máscara o prefijo de red, siguiente salto y coste asociado. Cada entrada destino puede ser para host (inviable en internet), red o por defecto (cuando ninguna entrada sirve). En internet se usa CIDR (superredes o subredes) para jerarquizar y resumir las entradas.

• Encaminamiento local, sólo utilizan información local y no global, no miran la topología de la red:
  1. Encaminamiento aleatorio o aislado (por un camino aleatorio o el mejor en base a algún criterio local) son fáciles de implementar pero no garantizan el camino más corto, y una ruta incorrecta perdería el paquete.
  2. Inundación: envía el paquete a todos sus vecinos menos el que se lo envió, el destino recibirá muchos duplicados. Se puede mejorar evitando la retransmisión de duplicados. El paquete llegará seguro por el camino más corto, se visitan todos los nodos, pero puede saturar la red.
• Encaminamiento estático, las tablas se construyen manualmente en base a la topología de la red, pero no se adaptan a los cambios de la misma, requiere vigilancia por parte del administrador de la red.
• Encaminamiento dinámico, las tablas se construyen de forma automática mediante el intercambio periódico de info. entre los routers, permite adaptarse a los cambios en la red. Se suelen hacer mediante vectores de distancia o estado de los enlaces.

Vectores de distancia. Los routers mantienen una entrada por cada posible destino con el router al que debe saltar y la distancia/métrica. La tabla se construye mediante el intercambio periódico de info. con los vecinos. La distancia total a un destino es la que anuncia el router vecino más la distancia a dicho router, si esa distancia es menor a la de nuestra entrada, se sustituye la entrada. La iteración de este proceso converge idealmente al camino óptimo (algoritmo Bellman-Ford). El coste suele ser el número de saltos. Ej.: RIP.

Problemas de convergencia: *Cuenta a infinito. Los cambios tardan en propagarse, si una red se cae, y antes de poder notificarlo a todos, llega una falsa info. de que es alcanzable por otro router, intercambian hasta infinito. Como soluciones, se limita a 16 (como si fuera infinito) los saltos, y se usan técnicas para evitarlo: horizonte dividido (nunca difundes a un router del que aprendiste una entrada dicha entrada), horizonte dividido con respuesta envenenada (sí se difunden pero con infinito) y actualizaciones forzadas (difundir en cuanto se detecta un cambio en la tabla).*Bucles. En redes con bucles, la pérdida de actualizaciones puede provocar la pérdida de convergencia, incluso con las medidas anteriormente descritas.

Estado de los enlaces. Los routers guardan info. de la topología exacta de la red. Cada router identifica a sus vecinos y su distancia (estado del enlace) e inunda a todos los nodos con esa info. Así cada router construye su grafo de cómo se ve la red (algoritmo de Dijsktra). Ej.: OSPF.

Encaminamiento en Internet. Internet organizada en Sistemas autónomos (AS) son colecciones de redes y routers, gestionadas por una misma autoridad. Los router internos del AS solo conectan redes dentro del mismo, y solo conocen al detalle la topología del AS; utilizan protocolos IGP (Interior Gateway Protocol) como RIP y OSPF. Los routers externos (border router) interconectan distintas AS, conocen el camino a los otros AS, pero no su organización interna al detalle; utilizan protocolos EGP (Exterior) o BGP (Border).

1. IGP: basados en vector de distancias (inestabilidad con pocos saltos entre redes y problemas de convergencia), basados en el estado de enlaces convergen rápidamente pero requieren gran intercambio información
2. Vector de rutas: Intentan resolver problemas anteriores para encaminamiento inter-AS (EGP), basado en vector de distancias, a partir de la información de destinos alcanzables en el AS mediante intercambio obtiene la lista de destinos alcanzables y la ruta completa al destino (y ASs a atravesar), uso de CIDR, detección de bucles sencilla y permite implementar políticas comprobando si un AS es parte del camino.

• RIP. Protocolo IGP de vectores de distancia que contienen pares destino-distancia, siendo distancia el número de saltos (max. 16 ~ infinito) (métrica es el número de saltos) (mensajes encapsulados en datagramas UDP dirigidos al puerto 520) (Puede utilizar 3 mecanismos: horizonte dividido, dividido con ruta inversa envenenada y actualiz forzadas). La versión 1 sirve para mensajes (por UDP 520) de:

1. REQUEST: enviados al conectarse a la red (0.0.0.0) y cuando caduca una entrada (dir. de esa red).
2. RESPONSE: periódicamente con los vectores, en respuesta o actualización forzada.

RIP v1 - Temporizadores.

• Periódico (aleatorio 25-35 segs.) intervalo de envío de msj RESPONSE para anuncias vector de distancias
• de expiración controla el periodo de validez, borra entradas que no hayan recibido datos en 180 segs,
• de colección de basura cuando la entrada expira no la elimina inmediat., sigue anunciando una entrada ya expirada con distancia máxima durante 120 segs.

Limitaciones RIP. Gran cantidad de tráfico broadcast, no admite métricas ni caminos alternativos (para equilibrar carga), los cambios tardan en propagarse, 16 puede ser poco para grandes redes y no soporta CIDR.

RIP v2 mejora algunas limitaciones de la v1 → Soporta máscaras (CIDR), multicasting y autentificación. RIPng adapta RIPv2 a IPv6: · Usa UDP 521 difundidos a IPv6 multicast FF02::9 · Los RESPONSE anuncian prefijos IPv6 · No hay Next Hop · No usa autentificación, se lo deja a IPv6

OSPF: Open Shortest Path First: protocolo de route interno IGP basado en el estado de los enlaces. Quita las limitaciones de RIP: equilibrado de la carga, particionado lógico de la red, convergencia más rápida por propagar inmediatamente los cambios, soporte para MAC de long variable y CIRD. Usa un protocolo de encapsulado y dir multicast. Los router tienen un identificador único.

EXAMEN: Tipos de encaminadores OSPF:

• Intra-area routers (IA): en un área y su BD con info de esa área
• Area border router (ABR): conectado a varias áreas y una es la 0, mantiene una BD por cada área
• AS boundary routers (ASBR): en la frontera de un sistema autónomo, intercambia rutas entre red OSPF y otras, responsables de transmitir rutas externas a la OSPF y pueden inyectar OSPF rutas aprendidas mediante otro protoc.

Relación de Vecinidad: comparten link común, pertenecen a la misma OSPF, mecanismos de autenticación, conf de los temp del protoc y conf del área.

Relación de adyacencia: solo entre routers vecinos, intercambian info de de estados de los enlaces, permite limitar la info intercambiada entre routers y la relación de adyaciencia se desarrola según el tipo de red (multiacceso por router designado y el de respaldo; punto a punto entre dos dispositivos).

• Funcionamiento: *Descubrimiento de vecinos: protoc OSPF Hello. Descubrir y mantener vecinos, cada router envía periódicamente “Hello” por sus enlaces, el mensaje incluye el ID de los router de todos los Hello recibidos por ese enalce, si un router recibe un Hello de otro con su ID, establece conex. *Elección del encaminador designado: El RD y RDB se selec usando info de prioridad contenida en los Hello.*Establecimiento de adyacencias 1: intercambio de BD: después e la vecindad se intercambian las BD con el estado de los enlaces, el intercambio sigue un patrón de maestro-esclav*Establecimiento de adyacencias 2: generación de BD: durante la 1 detectan info faltante u obsoleta en su BD. Tras la 1 se solicita una copia de estos, el proceso de solicitud es similar al de inundación. *Construcción de tablas de encaminamiento: cuando dispone de la info del estado de los enlaces, construye un árbol de rutas que incluye tanto routers como redes y su coste.

BGP: Border Gateway Protocol Protocolo de encaminamiento Inter-AS (o exterior) basado en vector de rutas. La función principal de un sistema BGP es intercambiar información sobre las redes alcanzables (Network Layer Reachability Information, NLRI) con otros sistemas BGP. *La información incluye la lista de ASs atravesados por la propia información*Esta información es suficiente para construir un grafo de conectividad de ASs para las redes alcanzables, libre de bucles*Cada AS puede aplicar ciertas políticas para aceptar y publicar las rutas recibidas // La versión actual, BGP-4, soporta CIDR y agregación rutas

Tipos de Sistemas Autónomos (AS): *Stub: conectado solo a otro AS. Dest u origen para el tráfico y no permite transportar info de tránisto. *Multihomed: conecta con varios AS pero sigue siendo dest y origen del tráfico, no permite transportar info de tránsito. *Tránsito: AS de tipo multihomed que permite el tráfico de tránsito.

Políticas de encaminamiento: cada AS puede aplicarlas para limitar el flujo de tráfico en la red. No forman parte del BGP, la conf de cada router, según la ruta puede optar por ejemplo: conf como AS multihomed anunciando solo sus redes alcanzables; no actuar como AS para algunos AS; escoger la ruta según el tráfico; evitar ciertos como tránsito.

Funcionamiento: la comunic se realiza por TCP, p 179. Intercambian la tabla de rutas al establecer la conexión. Se envían actualizaciones periódicamente. Los mensajes BGP incluyen: *OPEN (establece sesión, id de AS y router, param de conf); *UPDATE (actualización de la info, info de las redes CIRD, atributos incluida la ruta);*NOTIFICATION (enviado a vecinos cuando hay error, implica cierre de sesión y las rutas asociadas son inválidas); *KEEPALIVE (respuesta a un OPEN periódicamente para informar de la presencia del router, pasado un tiempo sin info cierra sesión)

Atributos: los UPDATE tienen las redes alcanzables y los atributos de ruta, permite evaluar caminos alternos, los atributos de ruta los genera el router y los puede modificar. Tipos: *Conocidos (bien conocidos): deben ser admitidos por todas las implementaciones BGP. Pueden ser obligatorios o discrecionales. Los atributos obligatorios se deben incluir en cada actualización.*Opcionales: específicos de cada implementación, pueden ser transitivos o no. Los atributos transitivos se deben incluir en las actualizaciones aunque no sean implementados por el encaminador. // Ejemplos de atributos conocidos y obligatorios: *ORIGIN: de la ruta IGP, EGP o INCOMPLETE. No debe modificarse; *AS_PATH o AS_SEQUENCE: la ruta como conjunto o secuencia de ASs; *NEXT_HOP: IP del siguiente salto para alcanzar destino.