Algoritmos de Enrutamiento Estático:

Enrutamiento Por Trayectoria más Corta: La idea es armar un grafo de la subred, donde cada Nodo representa un Enrutador y cada Arco una línea de comunicación (ó enlace). Algoritmo encuentra la trayectoria más corta para escoger una ruta entre 2 enrutadores.

• Métricas para longitud de trayectoria:
  •  Cantidad de Escalas,
  •  Distancia geográfica en km,
  •  Retardo medio de encolamiento,
  •  Tráfico medio, etc.

varios algoritmos según criterio:

Algoritmo de Dijkstra (1959) de etiquetado

1. Cada nodo se etiqueta con su distancia al nodo de origen a través de la mejor trayectoria conocida ® B(2,A).
2. Inicialmente no se conocen trayectorias ® D(¥,-)
3. A medida que avanza algoritmo, y se encuentran trayectorias, pueden cambiar etiquetas de tentativa (nodo o ) a permanente (nodo ·).
4. Ejplo. en Fig.5.5 de trayectoria más corta de A a D, dde se examinan por turno cada uno nodos adyacentes al nodo de trabajo, reetiquetando c/u con distancia desde A.

Inundación: Cada paquete de entrada se envía por c/u de las líneas de salida, excepto aquélla por la que llegó.

• Genera gran cantidad de paquetes duplicados
• Colocar Contador escalas en cabecera paquete que disminuye en cada escala, y al llegar a cero, se descarta el paquete.
• Ó llevar registro de paquetes diseminados en enrutador/ evitar enviarlos por 2ª vez ® Enrutador de origen coloca nº secuencia en cada paquete que  recibe de sus hosts.

Inundación Selectiva: variante donde enrutadores envían paquetes no por todas, sino por las líneas que van aprox. en dirección correcta. Uso en aplicaciones militares, en caso falla de muchos routers, ó para actualizar todas las bases de datos distribuídas.

Enrutamiento Basado en Flujo: Algoritmo estático que usa la topología y también la carga de tráfico para enrutar.

• Idea: para una línea dada, si se conoce la capacidad y el tráfico (flujo) promedio, es posible calcular el Retardo Promedio de los paquetes en esa línea, a partir de Teoría de Colas.
• Algoritmo para TMIN (retardo promedio mínimo para la subred)

Algoritmos de Enrutamiento Dinámico: veremos 2 algoritmos de enrutamiento dinámicos:Por Vector de Distancia, Por Estado de Enlace

Enrutamiento por Vector de Distancia : Opera haciendo que cada enrutador mantenga una Tabla (ó Vector) que da la mejor distancia conocida a cada destino y la línea a usar para llegar ahí.

• Tablas se actualizan intercambiando información con los vecinos.
• Otros nombres: Algoritmos de enrutamiento Bellman-Ford distribuido y de Ford-Fulkerson.
• Algoritmo original de ARPANET hasta 1979, y en Internet con nombre

RIP (Routing Info.Protocol), y en versiones de DECNet e IPX de Novell.

• Cada Enrutador conoce “distancia” a c/u de sus vecinos / si la métrica es “retardo”, se mide con paquetes de ECO que el receptor marca con la Hora y envía de regreso enseguida.
• Una vez cada T(mseg), c/enrutador envía a todos sus vecinos lista de sus retardos estimados a cada destino, y recibe los mismos de c/vecino.
• Actualiza Tabla de Enrutamiento indexada por cada enrutador de la subred.
• Cómo calcula J su nueva ruta a G? J-A=8 mseg, A-G=18 mseg Þ J-A-G=8+18=26 mseg.
• J-I-G=10+31=41 , J-H-G=12+6=18, J-K-G=6+31=37 ® el menor valor  retardo es 18 mseg Þ en su Tabla J-G de 18 mseg y ruta a usar es vía H.

Enrutamiento Por Estado de Enlace (Link state ó SPF): Usado en ARPANET desde 1979, toma en cuenta además del Retardo, el Ancho de Banda, ya que algunas líneas pasaron de ser todas de 56 (kbps) a 230 y 1544 (kbps).

Postulados: cada enrutador debe hacer 5 pasos:

1. Descubrir a sus vecinos y conocer sus direcciones de red. Al activarse un enrutador envía paquete especial de HOLA por cada línea PaP y espera que el otro extremo responda quién es (dirección globalmente única)
2. Medir el Retardo ó costo para c/u de sus vecinos. Envía un paquete especial de ECO a través de la línea, que se regresa inmediatamente del otro lado, se mide tiempo de ida y vuelta (RTT: Round Trip Time), se divide por 2 (Retardo)
3. Construir un paquete de Estado de Enlace. Con identidad del transmisor, Nº secuencia, Edad y Lista de vecinos con retardo a ese vecino. ( Fig.5.9 ). Se construye periódicamente ó con evento significativo
4. Enviar este paquete a todos los demás enrutadores. Usa inundación para distribuir los paquetes de Estado de Enlace / se controla con nº secuencia de paq. (32 bits).

Enrutadores llevan registro de todos los pares (Router de origen, Secuencia) / si es nuevo, lo reenvían por líneas salvo la de arribo, si es duplicado se descarta y si nº secuencia menor, se rechaza. Solución a problemas de error en nº secuencia es Campo de Edad en cada paquete, que se disminuye una vez/seg, y cuando llega a cero, se descarta

5. Calcular la Trayectoria más corta a los demás enrutadores. Con grupo completo de paq. de estado de enlace, puede construir grafo de subred completa y, Ejecutar Algoritmo de Dijkstra para calcular ruta más corta a todos los destinos y armar Tablas de Enrutamiento.