20.8 Algoritmos de routing

20.8.1 Algoritmo de routing Link-State

• Consta de dos fases:
  1. Fase de flooding (inundación). En ella, cada router “broadcasts” el estado de sus enlaces (destino^† y coste) al resto de routers del AS.
  2. Fase de cálculo de los caminos mínimos. Se utiliza normalmente el algoritmo de Dijkstra [21].

Flooding de los estados de los enlaces

• Cada router envía el estado de sus enlaces a todos los routers directamente conectados.
• Todo router que recibe un mensaje con información del tipo anterior retransmite el mensaje a través de todos sus enlaces excepto por el que llegó el mensaje.
• Cuando los mensajes son creados se les asigna un TTL que es decrementado cada vez que es retransmitido. De esta forma garantizamos que la fase de inundación finaliza.

Algoritmo de Dijkstra

1. Sean dos listas (Confirmed y Tentative) de ternas (Destination, Cost, NextHop). Inicializar Confirmed con el nodo que ejecuta el algoritmo y Tentative con los nodos que pueden alcanzarse desde él.
2. Mientras Tentative no esté vacía:
   1. Mover desde Tentative a Confirmed la terna de menor coste.
   2. Recarcular las distancias a los posibles destinos con esta terna.
3. En cada entrada de Confirmed queda almacenada la distancia mínima a cada nodo de la red y el primer nodo que se tiene que atravesar para conseguirlo.

Ejemplo

• Dada la red de la figura

  

  obtener la tabla de encaminamiento para el nodo E según el algoritmo Link-State.

Confirmed Tentative Comentarios (E,0,-) (B,4,B) Inicio (D,3,D) (F,2,F) (E,0,-) (B,4,B) Movemos (F,2,F) (D,3,D) (F,2,F) (E,0,-) (B,4,B) Actualizamos (F,2,F) (D,3,D) desde (C,2+1,F) (F,2,F) (E,0,-) (B,4,B) Movemos (F,2,F) (C,3,F) (D,3,D) (D,3,D) (E,0,-) (B,4,B) Actualizamos (F,2,F) (C,3,F) desde (D,3,D) (A,3+5,D) (D,3,D) (E,0,-) (B,4,B) Movemos (F,2,F) (A,8,D) (C,3,F) (D,3,D) (C,3,F) (E,0,-) (B,4,B) Actualizamos (F,2,F) (A,3+2,F) desde (D,3,D) (C,3,F) (C,3,F)

Confirmed Tentative Comentarios (E,0,-) (A,5,F) Movemos (F,2,F) (B,4,B) (D,3,D) (C,3,F) (B,4,B) (E,0,-) (A,5,F) Actualizamos (F,2,F) desde (D,3,D) (B,4,B) (C,3,F) (B,4,B) (E,0,-) Movemos (F,2,F) (A,5,F) (D,3,D) y (C,3,F) terminamos (B,4,B) (A,5,F)

20.8.2 Algoritmo de routing Distance-Vector

• También llamado algoritmo de Bellman-Ford [21].
• Emplea el mismo modelo de red mediante un grafo, donde los nodos representan routers y los arcos enlaces de transmisión.
• Es un algoritmo progresivo (calcula las rutas progresivamente, mejorándolas en cada iteración) y distribuido (los cálculos se realizan parcialmente en cada router).

Algoritmo de Bellman-Ford

• Cada cierto tiempo todos los routers vecinos intercambias los vectores con distancias a todos los demás routers del AS y se recalculan los vectores de distancias.
• Lo anterior también ocurre cuando un router detecta una variación en la distancia a algunos de sus vecinos.

Ejemplo

• Dada la red de la figura

  

  obtener las tablas de encaminamiento según el algoritmo Distance-Vector.

Tablas de encaminamiento iniciales. A B C D E F A 0 3/B 2/C 5/D ∞ ∞ B 3/A 0 ∞ 1/D 4/E ∞ C 2/A ∞ 0 2/D ∞ 1/F D 5/A 1/B 2/C 0 3/E ∞ E ∞ 4/B ∞ 3/D 0 2/F F ∞ ∞ 1/C ∞ 2/E 0

Tablas de encaminamiento tras el primer intercambio de vectores. A B C D E F A 0 3/B 2/C 4/C 7/B 3/C B 3/A 0 3/D 1/D 4/E 6/E C 2/A 3/D 0 2/D 3/F 1/F D 4/B 1/B 2/C 0 3/E 3/C E 7/B 4/B 3/F 3/D 0 2/F F 3/C 6/E 1/C 3/C 2/E 0