Encaminamiento (Routing)

El encaminamiento consiste en encontrar un camino de origen a destino a través de routers intermedios. Suele haber varias alternativas, y 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, etc., que pueden ser combinadas linealmente.

La elección del camino (enlace) se hace en base a:

• Tablas de Encaminamiento (usando la dirección 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: Se utilizan según las etiquetas del datagrama (flujo en IPv6), lo que reduce la complejidad de la tabla. Usan siempre el mismo circuito (entrega en orden y predecible).

El Next-Hop Routing se basa en el principio de optimización: si de A a C el mejor camino pasa por B, de B a C es el mismo camino óptimo. Por tanto, el router solo conoce el salto al siguiente router.

Estructura de las Tablas de Encaminamiento

Las tablas contienen información 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 (Classless Inter-Domain Routing, superredes o subredes) para jerarquizar y resumir las entradas.

Tipos de Encaminamiento

• Encaminamiento Local

  Solo utiliza información local y no global, no considera la topología de la red:

  1. Encaminamiento Aleatorio o Aislado: Se elige 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 (Flooding): Envía el paquete a todos sus vecinos menos al 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 y 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 información entre los routers, lo que permite adaptarse a los cambios en la red. Se suelen implementar mediante vectores de distancia o estado de los enlaces.

Protocolos de Encaminamiento Dinámico

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 información 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 en Vectores de Distancia

Conteo hasta infinito (Count to Infinity): Los cambios tardan en propagarse. Si una red se cae, y antes de poder notificarlo a todos, llega una falsa información de que es alcanzable por otro router, intercambian información hasta el infinito.

Como soluciones, se limita a 16 (considerado infinito) el número de saltos, y se usan técnicas para evitarlo:

• Horizonte dividido: Nunca se difunde a un router del que se aprendió una entrada, dicha entrada.
• Horizonte dividido con respuesta envenenada: Sí se difunden, pero con distancia infinita (16).
• Actualizaciones forzadas: Difundir la información tan pronto como 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 (Link State)

Los routers guardan información 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 información. Así, cada router construye su grafo de cómo se ve la red (algoritmo de Dijkstra). Ej.: OSPF.

Encaminamiento en Internet

Internet está organizada en Sistemas Autónomos (AS), que son colecciones de redes y routers gestionadas por una misma autoridad.

• Los routers 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 distintos AS, conocen el camino a los otros AS, pero no su organización interna al detalle; utilizan protocolos EGP (Exterior Gateway Protocol) o BGP (Border Gateway Protocol).

1. IGP: Basados en vector de distancias (inestabilidad con pocos saltos entre redes y problemas de convergencia) o basados en el estado de enlaces (convergen rápidamente pero requieren gran intercambio de 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 se obtiene la lista de destinos alcanzables y la ruta completa al destino (y AS a atravesar). Permite el uso de CIDR, la detección de bucles es sencilla y permite implementar políticas comprobando si un AS es parte del camino.

Protocolo RIP (Routing Information Protocol)

Protocolo IGP de vectores de distancia que contiene pares destino-distancia, siendo la distancia el número de saltos (máximo 16, considerado infinito). Los mensajes están encapsulados en datagramas UDP dirigidos al puerto 520. Puede utilizar los 3 mecanismos de solución a problemas de convergencia: horizonte dividido, dividido con ruta inversa envenenada y actualizaciones forzadas.

La versión 1 utiliza mensajes (por UDP 520) de:

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

RIP v1 – Temporizadores

• Periódico (aleatorio 25-35 segs.): Intervalo de envío de mensajes RESPONSE para anunciar el vector de distancias.
• De Expiración: Controla el periodo de validez. Borra entradas que no hayan recibido datos en 180 segundos.
• De Colección de Basura: Cuando la entrada expira, no la elimina inmediatamente, sino que sigue anunciando una entrada ya expirada con distancia máxima (16) durante 120 segundos.

Limitaciones de RIP

RIP presenta las siguientes limitaciones:

• Gran cantidad de tráfico broadcast.
• No admite métricas complejas ni caminos alternativos (para equilibrar carga).
• Los cambios tardan en propagarse.
• 16 saltos puede ser poco para grandes redes.
• No soporta CIDR (en v1).

Evolución de RIP

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

Protocolo OSPF (Open Shortest Path First)

Protocolo de routing interno (IGP) basado en el estado de los enlaces. Elimina las limitaciones de RIP: permite el equilibrado de la carga, el particionado lógico de la red, ofrece una convergencia más rápida por propagar inmediatamente los cambios, y soporta máscaras de longitud variable y CIDR. Usa un protocolo de encapsulado y direcciones multicast. Los routers tienen un identificador único.

Tipos de Routers OSPF

• Intra-area routers (IA): Están en un área y su Base de Datos (BD) contiene información solo de esa área.
• Area Border Router (ABR): Conectado a varias áreas, y una de ellas es el área 0 (Backbone). Mantiene una BD por cada área.
• AS Boundary Routers (ASBR): Están en la frontera de un Sistema Autónomo. Intercambian rutas entre la red OSPF y otras redes. Son responsables de transmitir rutas externas a OSPF y pueden inyectar rutas aprendidas mediante otro protocolo en OSPF.

Relaciones en OSPF

• Relación de Vecindad: Se establece entre routers que comparten un enlace común, pertenecen a la misma OSPF, comparten mecanismos de autenticación, configuración de los temporizadores del protocolo y configuración del área.
• Relación de Adyacencia: Solo se establece entre routers vecinos. Intercambian información de estado de los enlaces. Permite limitar la información intercambiada entre routers. La relación de adyacencia se desarrolla según el tipo de red (multiacceso por router designado y el de respaldo; punto a punto entre dos dispositivos).

Funcionamiento de OSPF

• Descubrimiento de Vecinos: Protocolo OSPF Hello. Se utiliza para descubrir y mantener vecinos. Cada router envía periódicamente mensajes “Hello” por sus enlaces. El mensaje incluye el ID de los routers de todos los Hello recibidos por ese enlace. Si un router recibe un Hello de otro con su ID, establece conexión.
• Elección del Router Designado (RD): El RD y el Router Designado de Respaldo (RDB) se seleccionan usando información de prioridad contenida en los mensajes Hello.
• Establecimiento de Adyacencias 1: Intercambio de BD: Después de la vecindad, se intercambian las Bases de Datos con el estado de los enlaces. El intercambio sigue un patrón de maestro-esclavo.
• Establecimiento de Adyacencias 2: Generación de BD: Durante la fase 1, los routers detectan información faltante u obsoleta en su BD. Tras la fase 1, se solicita una copia de estos datos. El proceso de solicitud es similar al de inundación.
• Construcción de Tablas de Encaminamiento: Cuando se dispone de la información completa del estado de los enlaces, se construye un árbol de rutas que incluye tanto routers como redes y su coste.

Protocolo 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 AS atravesados por la propia información.
• Esta información es suficiente para construir un grafo de conectividad de AS 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 de rutas.

Tipos de Sistemas Autónomos (AS)

• Stub: Conectado solo a otro AS. Es destino u origen para el tráfico y no permite transportar información de tránsito.
• Multihomed: Conecta con varios AS, pero sigue siendo destino y origen del tráfico. No permite transportar información de tránsito.
• Tránsito: AS de tipo multihomed que sí permite el tráfico de tránsito.

Políticas de Encaminamiento BGP

Cada AS puede aplicar políticas para limitar el flujo de tráfico en la red. Estas políticas no forman parte del protocolo BGP, sino de la configuración de cada router. Según la ruta, se puede optar, por ejemplo, por:

• Configurarse como AS multihomed anunciando solo sus redes alcanzables.
• No actuar como AS de tránsito para algunos AS.
• Escoger la ruta según el tipo de tráfico.
• Evitar ciertos AS como tránsito.

Funcionamiento de BGP

La comunicación se realiza por TCP, puerto 179. Intercambian la tabla de rutas al establecer la conexión. Se envían actualizaciones periódicamente. Los mensajes BGP incluyen:

• OPEN: Establece la sesión (incluye ID de AS y router, parámetros de configuración).
• UPDATE: Actualización de la información (información de las redes CIDR, atributos incluida la ruta).
• NOTIFICATION: Enviado a vecinos cuando hay un error. Implica el cierre de sesión y las rutas asociadas se invalidan.
• KEEPALIVE: Respuesta a un OPEN periódicamente para informar de la presencia del router. Si pasa un tiempo sin información, se cierra la sesión.

Atributos BGP

Los mensajes UPDATE contienen las redes alcanzables y los atributos de ruta, lo que permite evaluar caminos alternos. Los atributos de ruta los genera el router y los puede modificar.

• 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: Origen de la ruta (IGP, EGP o INCOMPLETE). No debe modificarse.
• AS_PATH o AS_SEQUENCE: La ruta como conjunto o secuencia de AS.
• NEXT_HOP: Dirección IP del siguiente salto para alcanzar el destino.

Etiquetas: Encaminamiento, protocolos de red, RIP, Routing