Apunte de Algoritmos de Ruteo (Teoría de las Comunicaciones)

Archivo:Back.png Volver a la página de la materia

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

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 el enlace 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 parcialmente 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 ciclo 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!)

Comparación de los algoritmos de ruteo

Sacado de la Wikipedia: falta traducir y completar.

Distance-vector routing protocols are simple and efficient in small networks, and require little, if any management. However, naïve distance-vector algorithms do not scale well (due to the count-to-infinity problem), and have poor convergence properties, which has led to the development of more complex but more scalable algorithms for use in large networks, such as link-state routing protocols and loop-free distance-vector protocols (e.g. EIGRP). loop-free distance-vector protocols are as robust and manageable as distance-vector protocols, while avoiding counting to infinity and hence having good worst-case convergence times.

The primary advantage of link-state routing is that it reacts more quickly, and in a bounded amount of time, to connectivity changes. Also, the link-state packets that are sent over the network are smaller than the packets used in distance-vector routing. Distance-vector routing requires a node's entire routing table to be transmitted, while in link-state routing only information about the node's immediate neighbours are transmitted. Therefore, these packets are small enough that they do not use network resources to any significant degree. The primary disadvantage of link-state routing is that it requires more storage and more computing to run than distance-vector routing.

(*) Cita extraida del Tanenbaum