Apunte de Algoritmos de Ruteo (Teoría de las Comunicaciones)
Algoritmos de ruteo
Son aquellos que construyen la tabla de ruteo, a partir de la cual luego se construye la tabla de forwardeo. La red se puede ver como un grafo donde cada router es un nodo (aunque como nodos tambien se pueden considerar los hosts, los switches, segmentos de red) y donde cada enlance entre routers es un eje. Viendolo de este modo, el ruteo se reduce al calculo de los caminos minimos de un nodo a los demas.
Algoritmo estatico
Dada una red, se pueden calcular los caminos minimos una unica vez y guardar en cada nodo dicha informacion. Eso tiene sus problemas: no considera la adicion de nuevos nodos, ni la caida de los mismos, ni cambios de costos en los ejes.
Algoritmos dinamicos
Algoritmo Distance vector (RIP)
Cada nodo construye un vector con su distancia a cada uno de los demas nodos. Aunque se use el termino distancia, en realidad nos referimos a un costo, que puede estar dado por la distancia pero tambien por el delay en milisegundos, por el numero total de paquetes encolados esperando ser enviados a ese destino, etc.
Se asume en principio que cada nodo conoce la distancia a sus vecinos. Si la metrica empleada es efectivamente la distancia entonces sera de un hop; si es el numero total de paquetes encolados entonces el router solo tiene que examinar la cola para ese destino; si es el delay en milisegundos entonces el router puede determinarlo mediante un ping.
Al principio, cada nodo construye su poniendo la distancia para los nodos vecinos e infinito para los que no lo son. Pasemos a verlo con un ejemplo, en este y en los sucesivos por simplicidad el costo estara dado por la distancia. Sea la siguiente red:
Para A: Destino | Costo | Next Hop -------------------------- B | 1 | B C | 1 | C D | inf | - Para B: Destino | Costo | Next Hop -------------------------- A | 1 | A C | 1 | C D | inf | - Para C: Destino | Costo | Next Hop -------------------------- A | 1 | A B | 1 | B D | 1 | D Para D: Destino | Costo | Next Hop -------------------------- A | inf | - B | inf | - C | 1 | C
Luego, cada nodo le manda su vector (el vector es de la forma (Destino, Costo), no incluye el Next Hop) a sus vecinos quienes a su vez le mandan el suyo. Es mediante la comparacion entre su propio vector y los enviados por los vecinos que cada nodo va determinando el caminos minimo hacia todos los demas nodos. En cada comparacion, en caso de hallar un camino de menor costo, el nodo actualiza su vector. Volviendo al ejemplo, supongamos que C es el primero en enviarle su vector a A. Como resultado, A decide acceder a D mediante C ya que 2 hops (1 hop para ir de A a C mas 1 hop para ir de C a D) es menor que la distancia actual de infinitos hops. Sin embargo, A no va a acceder a B mediante C porque en ese caso le llevaria 2 hops, que es mayor que la distancia actual a B de 1 hop. La tabla de A entonces quedaria:
Para A: Destino | Costo | Next Hop -------------------------- B | 1 | B C | 1 | C D | 2 | C
Si mas adelante se coloca un nuevo nodo E entre C y D, ahora la distancia entre C y D sera de 2 hops. Cuando C le envie su vector a A, A cambiara la distancia actual a D de 2 hops por una distancia de 3 hops, aun cuando esta ultima mayor, ya que A accede a D mediante C.
Cada nodo ira actualizando su vector hasta que finalmente todos seran consistentes entre si, este proceso se denomina convergencia. Es importante destacar que cada nodo solamente conoce su distancia a los demas nodos pero desconoce por completo las distancias entre los otros nodos, en otras palabras, no tiene una perspectiva global (mas adelante veremos que Link State si la tiene).
Hay dos cirscunstancias bajo las cuales un nodo puede mandarle su vector al vecino. La primera es por una actualizacion periodica (periodic update). Aun cuando nada cambio, esto puede servir para hacerle saber a sus vecinos que aun sigue alli. La segunda es por una actualizacion disparada (triggered update) causada por un evento en la red que hizo que el nodo modifique su vector, el envio a los vecinos se debe a que estos tambien podrian tener que cambiar los suyos. Uno de estos eventos en la red puede deberse a la caida de un nodo, que sera advertida por sus vecinos ya sea porque no envio su actualizacion periodica o porque estos estan continuamente probando la conexion entre ambos. De esta manera, los nodos se mantienen al tanto de la situacion de la red.
Sea la siguiente red:
Supongamos que el nodo A acaba de caer y que hay un gong gigante (*) que suena periodicamente haciendo que se produzca un intercambio simultaneo de vectores entre nodos vecinos:
Tabla de distancias a A:
Intercambios | Nodo B | Nodo C | Nodo D | Nodo E
-----------------------------------------------
ninguno | 1 | 2 | 3 | 4
1 | 3 | 2 | 3 | 4
2 | 3 | 4 | 3 | 4
3 | 5 | 4 | 5 | 4
4 | 5 | 6 | 5 | 6
5 | 7 | 6 | 7 | 6
6 | 7 | 8 | 7 | 8
| | | |
| ... | ... | ... | ...
| | | |
| inf | inf | inf | inf
En el primer intercambio B recibe la tabla de C pero no la de A. Asume que el enlace con A esta caido, o sea que la distancia a A es de infinitos hops. Como la distancia de C a A es de 2 hops, decide acceder a A mediante C en 3 hops. El problema es que C accede a A mediante B y esto B no lo sabe (B conoce sus propios Next Hop pero desconoce los Next Hop de C). En el proximo intercambio, C aumenta su distancia a A a 4 hops ya que accede a A mediante B y este esta a una distancia de 3 hops. Siguiendo asi sucesivamente, todos los nodos terminan con una distancia de infinitos hops a A. Este problema se conoce como count-to-infinity.
Una forma de abordarlo puede ser determinar un valor numerico para del infinito lo mas bajo posible para terminar cuanto antes con el ciclo. Una buena eleccion es el diametro de la red mas uno.
Otra forma, que evita los ciclos, es el split horizon, donde los nodos no intercambian con sus vecinos aquellos destinos cuyos Next Hop son los mismos vecinos. En el ejemplo, C no hubiera intercambiado (A,2) con B. Una variante de esto ultimo es el split horizon with poison reverse, donde se intercambian todos los destinos pero cuando los Next Hop son los mismos vecinos, se pone un valor de infinito como costo. En el ejemplo, C hubiera intercambiado (A,inf) con B.
Esto ultimo es efectivo solo cuando el loop involucra dos nodos pero falla en el caso general como puede verse en el siguiente ejemplo:
Inicialmente A y B tienen ambos una distancia a D de 2 hops. Supongamos que D se cae y nuevamente consideremos el gong gigante que determina periodicamente intercambios simultaneos. Usando split horizon, ni A ni B intercambian (D,2) con C. Asi, C determina que la distancia a D es de infinitos hops y reporta esto a A y B. Pero A ve que B tiene una distancia de 2 hops a D y B ve que A tiene una distancia de 2 hops a D, ambos asumen una distancia a D de 3 hops. En el proximo intercambio su distancia a D sera de 4 hops, esto se repite una y otra vez hasta que su distancia a D es de infinitos hops, justamente el comportamiento que queriamos evitar.
Algoritmo Link State (OSPF)
(¡A Completar!¡Me muero de sueño!)
(*) Cita extraida del Tanenbaum
