Routing algorithms: Distance Vector, RIP

De Departamento de Informatica
Saltar a: navegación, buscar

Contenido

Distance Vector

El algoritmo de vector distancia es iterativo, asíncrono y distribuido. Es iterativo, debido a que el proceso que se desarrolla continúa hasta que no hay más información para ser intercambiada entre los vecinos. Es asíncrono en el sentido en que no se requiere que todos los nodos operen sincronizados entre sí. Por último, es distribuido ya que cada nodo recibe información de uno o más de sus vecinos directamente conectados, realiza un cálculo y luego actualiza la información a sus vecinos.

¿Cómo funciona?

Al principio, cada nodo tiene un vector con las distancias de los nodos de la red. Sin embargo, el nodo no conoce el costo que tiene comunicarse con sus vecinos. Cabe destacar que los nodos se representan con letras mayúsculas, y los costos se representan con números. Entonces, primero, debemos anotar todos los nodos que se conectan directamente entre sí con su respectivo costo. Los nodos que no pueden conectarse inicialmente, tendrán costo infinito. Posteriormente, se dice que cada nodo le envía información a sus nodos vecinos, de forma tal que si un nodo anteriormente no tenía como llegar a otro, ahora que cuenta con la información de sus nodos vecinos, eventualmente podría llegar a nodos que anteriormente no veía. Esto se logra pasando por diferentes nodos, hasta llegar al que tenía un costo infinito. Luego como este costo es menor que infinito, entonces se reemplazará y se volverá a realizar la misma acción para calcular la distancia de todos los nodos entre sí. Una vez que se tenga la información de todos los costos, se volverá a repetir lo mismo, y a medida que se encuentren caminos que representen costos menores para llegar a un nodo, se reemplazará dicho valor por el anterior, hasta que los valores de los costos no cambien.

Repasando:

  • Anotar costos de nodos conectados directamente entre sí.
  • Los que no se encuentren conectados, anotar como costo infinito.
  • Determinar todas las formas posibles de ir a los distintos nodos.
  • Reemplazar en caso de encontrar costos menores.
  • Repetir el mismo procedimiento hasta que los valores en la tabla no cambien.

¿Problemas?

Como podemos apreciar, es un método muy sencillo en el cual sólo debemos fijarnos en todas las posibilidades que tenemos para llegar de un nodo a otro utilizando el mínimo de recursos posibles. Sin embargo no todo es color rosa, ya que este método presenta un problema al momento de aislar un nodo cortando un camino. Esto se debe a que luego de muchas iteraciones, veremos que el costo irá incrementando cada vez más debido a que un nodo creerá que puede llegar al nodo aislado pasando por otro nodo.

Ejemplo

DistanceVector-ejemplo1.png

Primero debemos ver las distancias o costos de cada uno de los nodos, a todos los demás que son sus vecinos directos. Los otros, que no son vecinos directos, se dejan en signo de interrogación, ya que no se sabe su distancia aún.

Costos iniciales de nodo a nodo
Nodo A B C D E F G
A 0 1 1 ? 1 1 ?
B 1 0 1 ? ? ? ?
C 1 1 0 1 ? ? ?
D ? ? 1 0 ? ? 1
E 1 ? ? ? 0 ? ?
F 1 ? ? ? ? 0 1
G ? ? ? 1 ? 1 0

Luego, queremos saber el costo hacia los demás nodos. Para esto se hacen los siguientes pasos:

  1. Cada nodo envía un mensaje a sus vecinos directos, el cual contiene su lista personal de costos. Por ejemplo, el nodo A, enviaría esta lista a sus vecinos B, C, E y F.
  2. Si alguno de estos vecinos encuentra que en la lista de A, hay un camino más corto que el que el tiene en su lista, entonces, actualiza su lista con el nuevo camino. Esto produce que todos los paquetes hacia ese destino, se irán a través de A, ya que por ahí está el camino más corto. Por ejemplo, en este caso, el nodo B encuentra que desde A el costo hacia E es 1, por lo tanto, sabiendo que también el costo hacia A es 1, y sumándole 1 por el costo de A hacia E, este nodo B aprende que el costo hacia E es 2.
  3. Repitiendo con cada nodo el paso anterior, finalmente se sabe el menor costo hacia cada uno de los otros nodos.
  4. Además de actualizar su lista cuando reciben actualizaciones, los nodos necesitan guardar cual es el nodo que usaron para calcular el nuevo costo. En el caso anterior, el nodo B, necesita guardar que debe pasar por A para llegar a E. Para esto, se crea la llamada forwarding table o tabla de transmisión por cada nodo.
Costos finales de nodo a nodo
Nodo A B C D E F G
A 0 1 1 2 1 1 2
B 1 0 1 2 2 2 3
C 1 1 0 1 2 2 2
D 2 2 1 0 3 2 1
E 1 2 2 3 0 2 3
F 1 2 2 2 2 0 1
G 2 3 2 1 3 1 0

A modo de ejemplo se muestra la tabla de transmisión del nodo B:

Tabla de transmisión nodo B
Destino Costo Próximo salto
A 1 A
C 1 C
D 2 C
E 2 A
F 2 A
G 3 A

RIP

Routing Information Protocol o Protocolo de Información de Enrutamiento, es un protocolo de puerta de enlace interna utilizado por routers y/o equipos, para intercambiar información acerca de redes IP.

Este protocolo de enrutamiento de información se desarrolló en 1970 en los laboratorios de Xerox como parte de otro protocolo de enrutamiento y se masificó debido a que fue distribuido en 1982 en la versión BSD (Berkeley Software Distribution) de UNIX que soportaba TCP/IP.

Al ser un protocolo de vector de distancias, funciona muy similar al protocolo de DV (Distance Vector). Este protocolo utiliza como métrica de costo el recuento de saltos; cada salto entre enlace tiene costo 1 que se calcula entre el router de origen a una subred de destino.

Por ejemplo: Tenemos la siguiente red conformada por 3 routers, A, B, C y sus respectivas subredes.

RIP-ejemplo1.png

El número de saltos desde un router de origen A hasta una subred sería:

Saltos desde router A hacia una subred
Destino Saltos
y 2
z 2
v 3
w 3

El costo máximo de una ruta está limitado a 15, es decir, que en una red no pueden haber más de 15 saltos.

En un protocolo que utilizan vector distancia, los routers intercambian dicho vector entre sí con sus vecinos. El vector de distancias para cualquier router es la estimación actual de la ruta más corta de dicho router a las subredes. En RIP, las actualizaciones de enrutamiento son actualizadas a cada 30 segundos mediante o que se denomina un mensaje de respuesta RIP. Un mensaje de respuesta enviado por un host o un router contiene una lista de hasta 25 subredes de destino. Estos mensajes de respuestas se conocen como anuncios RIP.

Cada router RIP mantiene una tabla de enrutamiento. Esta tabla de enrutamiento está compuesta por el vector de distancias del router como la tabla de reenvío del mismo.

Por ejemplo, utilizando el mismo esquema anterior, la tabla de enrutamiento para el router B sería:


Tabla de enrutamiento router B
Subred de destino Siguiente router Núm de saltos
v C 2
w C 2
x A 2
y - 1
z - 1

Implementación RIP

  • Los routers RIP intercambian información cada 30 segundos a través de anuncios.
  • Si un router no recibe información de un vecino durante 180seg. considera que éste ya no es alcanzable, por lo tanto, se elimina de la tabla de enrutamiento y propaga esa información a sus routers vecinos.
  • Un router puede solicitar información sobre el costo de un destino “X” a través de sus routers vecinos mediante un mensaje de solicitud RIP. Esta solicitud se realiza mediante el protocolo UDP en el puerto 520.
  • El segmento enviado por UDP es un “Datagrama IP estándar”.

¿Cómo funciona?

  • Cuando un router (enrutador) se inicializa, las únicas rutas de las que tiene conocimiento son las redes a las que está directamente conectado.
  • En la versión 1 del protocolo RIP, el router transmite información sobre todas las redes directamente conectadas. Estas difusiones se conocen como triggered updates (actualizaciones o anuncios)
  • Los routers RIP “escuchan” las difusiones RIP, esto permite que puedan informarse de las redes que no conocen directamente.
  • La métrica se basa en el número de saltos (núm de routers presentes en una ruta), los cuales se anuncian en cada difusión que se efectúa en cada red.
  • Se supone que cualquier ruta que conozca un router RIP pasa por dicho router. Es decir, si el router A envía una actualización al router B, este último supone que el salto siguiente corresponde a las redes que se incluyen en la actualización es el router A.
  • Las actualizaciones se envian en intervalos de 30 segundos.
  • Las métricas se actualizan solo en el caso de que la métrica anunciada más el costo en alcanzarla sea estrictamente menor a la almacenada.
  • Las rutas tienen un tiempo de vida de 180 segundos. Si pasado ese tiempo no se han recibido mensajes, se elimina.

Enlaces externos

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas