Enrutamiento

Características

Corrección, simplicidad, robustez, estabilidad, equidad y optimalidad.

Datagramas vs. Circuitos Virtuales (CV)

Con datagramas, la decisión de enrutamiento se toma en cada paquete que llega. Con CV, puede tomarse en cada establecimiento de un CV nuevo.

Algoritmos de Enrutamiento

Algoritmos No Adaptativos (Estáticos)

No se basan en medir o estimar el tráfico, se determinan anticipadamente.

Algoritmos Adaptativos

Cambian las rutas de encaminamiento para reflejar cambios de topología y de tráfico actual.

Tipos de Algoritmos Adaptativos

• Centralizado: Un nodo calcula la ruta a todos los demás.
• Aislados: Operan separados sobre cada Sistema Intermedio (SI), sólo utilizan información disponible en cada nodo (información local), por ejemplo, longitud de colas (hot potato).
  • Algoritmo de Inundación: Los paquetes se envían por cada vía de salida.
  • Inundación Selectiva: Los paquetes se ponen en líneas de salida en dirección del destino.
  • Aprendizaje Atrás: Aprende de los paquetes que pasan por él.
  • Hot Potato: El enrutador coloca el paquete de datos en la primera línea que pueda de acuerdo a una métrica local, como el tamaño de las colas de espera en las líneas de salida.
• Distribuido: Combinación de información global y local. Se utiliza en grandes redes. Cada SI mantiene una tabla de encaminamiento.

Enrutamiento IP

Los routers reciben y envían datagramas.

Clases de Direcciones IP

Las direcciones de internet son de 32 bits, una parte de red y otra de host.

• Clase A: Comienza con 0. Red (7 bits), Host (24 bits).
• Clase B: Comienza con 10. Red (14 bits), Host (16 bits).
• Clase C: Comienza con 110. Red (21 bits), Host (8 bits).
• Clase D: Comienza con 1110. Multicast el resto.

Subredes y Máscara de Subred

Permiten una complejidad arbitraria de LANs interconectadas. Un sitio es visto por internet como una única red. Cada LAN tiene una subred. La máscara indica los bits del número de subred y del número de host.

Enrutamiento Estático vs. Adaptativo

Estático: Ruta única.

Adaptativo: Las rutas cambian a medida que las condiciones de internet cambian (fallas: la ruta puede evitar problemas; congestión: la ruta puede evitarla, al menos no agregar más). Decisiones de enrutamiento más complejas, aumenta el procesamiento en routers. Depende de la información recogida en un lugar y usada en otro (mejora decisiones, aumenta overhead). Puede reaccionar rápido a la congestión, o lento si es irrelevante.

Patologías del Enrutamiento Adaptativo

• Fluttering: Oscilación rápida en el enrutamiento pues el router intenta balancear la carga o dividirla (puede provocar que paquetes sucesivos que van al mismo destino tomen rutas muy diferentes). Dificulta el cálculo del retardo, mayor probabilidad de error.
• Lazos: Paquetes reenviados por un router retornan a ese mismo router. Los algoritmos lo previenen. Pueden ocurrir cuando los cambios en la conectividad no se propagan rápido a otros routers.

Estrategias de Enrutamiento Adaptativo

• Basada en fuentes de información local (enruta cada datagrama a la red con la cola más corta, balancea la carga, puede no ir en la dirección correcta).
• Nodos adyacentes (algoritmo vector de distancias).
• Todos los nodos (algoritmo de estado de enlaces).

Algoritmos Distribuidos

• Vectores de Distancia: Cada enrutador calcula las rutas a partir de la información suministrada por enrutadores en su vecindad (visión parcial de la red). Ventajas: sencillo, robusto, tablas pequeñas (topología local). Desventajas: convergencia lenta, pueden haber bucles, crecimiento difícil.
• Estado de los Enlaces: Cada enrutador informa al resto el estado de sus enlaces. Con la información recibida, construye un mapa completo de la red, sobre el cual se utiliza un algoritmo de cálculo de rutas (visión global del estado de la red). Ventajas: convergencia rápida, fácil crecimiento, detección y corrección de problemas más fácil. Desventajas: la difusión del estado de los enlaces puede ser complicada (se limita el tiempo de vida de un paquete de difusión), cada nodo debe conocer la topología de la red (tablas grandes).

Sistemas Autónomos (AS)

Grupos de routers que intercambian información vía protocolo de enrutamiento común. Conjunto de redes y routers manejados por una única organización, conectadas excepto en periodos de fallas.

• IRP (Protocolo de Routing Interior): Pasa información de routing dentro de un AS. Son ERP.
• ERP (Protocolo de Routing Exterior): Pasan menos información que los IRP.
• RIP (Routing Information Protocol): Simple, conveniente para redes pequeñas, muy usado, usa enrutamiento por vector de distancias.
• OSPF (Open Shortest Path First): RIP limitado en redes grandes. Preferido en TCP/IP, usa enrutamiento por estado de enlaces.

Enrutamiento por Estado de Enlaces

El router determina el costo de enlace en cada interfaz y avisa el costo a otros routers.

Congestión

El número de paquetes transmitidos alcanza la capacidad de manejo de paquetes de la red. 80% o más es crítico. Los datos se pueden perder por colas finitas. Ocasionada por:

• Si los Sistemas Intermedios (SI) son lentos para sus tareas, las colas crecen.
• Aunque la velocidad sea rápida, las colas de espera crecen cada vez que la velocidad del tráfico de entrada excede la capacidad de las líneas de salida. Si no tiene buffers de salida, los paquetes son ignorados. Con ello, al SI se le vence el tiempo y debe retransmitir.

Es diferente del control de flujo. El flujo de paquetes debe ser controlado para evitar que el enrutador sea incapaz de manejarlos y comience a descartarlos.

Flujo: Secuencia de paquetes que van de una fuente a un destino, siguen la misma ruta de red.

Clasificación de Mecanismos de Control de Congestión

• Centrado en enrutadores vs. centrado en fuentes:
  • Centrado en enrutadores: Cada uno toma la responsabilidad de decidir qué paquetes serán descartados e informar a las fuentes cuántos paquetes puede enviar.
  • Centrado en fuentes: La fuente ajusta su tasa de envío según cuántos de sus paquetes viajan exitosamente por la red. No son exclusivos.
• Basado en reservación vs. en realimentación:
  • Basado en reservación: La fuente pide a la red una cantidad determinada de su capacidad al momento de que el flujo es establecido, cada enrutador reserva recursos para satisfacer el requerimiento.
  • Basado en realimentación: La fuente envía datos sin reservar capacidad y luego adapta su tasa de envío acorde con la realimentación que se recibe.
• Basado en ventana vs. basado en tasa:
  • Basado en ventana: La ventana corresponde a cuánto espacio de buffer tiene disponible el receptor, esto limita la cantidad de datos que envía el emisor.
  • Basado en tasa: Cuántos bits por segundo el receptor o red son capaces de absorber.

Algoritmos de Colas

• FIFO: No consideran el flujo del que provienen los paquetes. Si un paquete llega y la cola está llena, se descarta sin importar el flujo. Variantes: cola con prioridad. Desventaja: no discriminan entre fuentes diferentes. Principal desventaja: una fuente puede inundar el enrutador con muchos paquetes, descartando paquetes de otras fuentes.
• Cola por flujo: Una cola distinta por cada flujo. Desventaja: no considera el tamaño del paquete. Implementa un servicio por turnos bit por bit.

Un Solo Flujo

Pi = longitud del paquete; Si = tiempo en que el enrutador comienza a transmitir el paquete i; Fi = tiempo en que el enrutador termina de transmitir el paquete i. Dado que el reloj avanza en un bit -> Fi = Si + Pi. Inicio de transmisión de un nuevo paquete -> Si = MAX(Fi-1, Ai); Fi = MAX(Fi-1, Ai) + Pi.

Varios Flujos

Se calcula Fi para cada paquete en cada flujo, y el próximo paquete es el que tiene menor Fi. Importante: En ocasiones prevalece el tamaño de paquete a ser enviado. El enlace nunca estará desocupado si hay paquetes en las colas. Ningún flujo utilizará más de 1/n (con n = cantidad de flujos) del ancho de banda del enlace.

Control de Congestión

• Ciclo abierto: Decide cuándo se acepta tráfico nuevo, cuándo se descartan paquetes y cuáles. Se puede dividir en algoritmos que actúan en los orígenes y en el destino.
• Conformaciones de tráfico: Obliga a la transmisión de paquetes a una tasa predecible.
• Ciclo cerrado: Tres partes:
  • Supervisa el sistema para detectar cuándo y dónde se produce la congestión.
  • Pasa esta información a donde pueden llevarse a cabo las acciones.
  • Ajusta la operación del sistema para corregir el problema.

Algoritmos de Control de Congestión

• Cubeta con goteo: Cada host está conectado a la red mediante una interfaz que contiene una cola finita. Si llega un paquete y la cola está llena, se descarta. El host puede poner un paquete por pulso de reloj, convirtiendo el flujo en un flujo continuo hacia la red.
• Cubeta con ficha: Igual que el anterior, pero contiene fichas generadas por reloj, una ficha por cada delta T segundos. Para transmitir un paquete, el transmisor debe capturar y destruir una ficha. Con N como tamaño máximo de la cubeta, pueden enviarse N ráfagas de paquetes.
• Backpressure: Si un nodo se congestiona, puede disminuir o detener el flujo de paquetes. Esto restringe las conexiones lógicas de alto tráfico. No se usa en ATM ni en Frame Relay.
• Choque de paquete (Packet Discard): Paquete de control generado en un nodo congestionado, enviado al nodo fuente. Mecanismo no elaborado.