in

Red informática | Algoritmo de enrutamiento por vector de distancia

distance vector routing algorithm
  • El algoritmo de vector de distancia es iterativo, asincrónico y distribuido.
    • Repartido: Se distribuye en el sentido de que cada nodo recibe información de uno o más de sus vecinos conectados directamente, realiza cálculos y luego distribuye el resultado a sus vecinos.
    • Iterativo: Es iterativo en el sentido de que su proceso continúa hasta que no hay más información disponible para intercambiar entre vecinos.
    • Asincrónico: No requiere que todos sus nodos operen en el paso de bloqueo entre sí.
  • El algoritmo de vector de distancia es un algoritmo dinámico.
  • Se utiliza principalmente en ARPANET y RIP.
  • Cada enrutador mantiene una tabla de distancias conocida como Vector.

Tres claves para comprender el funcionamiento del algoritmo de enrutamiento por vector de distancia:

  • Conocimiento sobre toda la red: Cada enrutador comparte su conocimiento a través de toda la red. El enrutador envía su conocimiento recopilado sobre la red a sus vecinos.
  • Enrutamiento solo a vecinos: El enrutador envía su conocimiento sobre la red solo a aquellos enrutadores que tienen enlaces directos. El enrutador envía todo lo que tiene sobre la red a través de los puertos. El enrutador recibe la información y la usa para actualizar su propia tabla de enrutamiento.
  • Intercambio de información a intervalos regulares: En 30 segundos, el enrutador envía la información a los enrutadores vecinos.

Algoritmo de enrutamiento por vector de distancia

Deja dX(y) será el costo de la ruta de menor costo desde el nodo x al nodo y. Los menores costos están relacionados por la ecuación de Bellman-Ford,

dx(y) = minv{c(x,v) + dv(y)}

Dónde el minv es la ecuación tomada para todos los x vecinos. Después de viajar de xa v, si consideramos la ruta de menor costo de vay, el costo de la ruta será c (x, v) + dv(y). El menor costo de xay es el mínimo de c (x, v) + dv(y) asumió el control de todos los vecinos.

Con el algoritmo de enrutamiento por vector de distancia, el nodo x contiene la siguiente información de enrutamiento:

  • Para cada vecino v, el costo c (x, v) es el costo de la ruta desde x hasta el vecino directamente adjunto, v.
  • El vector de distancia x, es decir, DX = [ Dx(y) : y in N ], que contiene su costo a todos los destinos, y, en N.
  • El vector de distancia de cada uno de sus vecinos, es decir, Dv = [ Dv(y) : y in N ] para cada vecino v de x.

El enrutamiento por vector de distancia es un algoritmo asincrónico en el que el nodo x envía la copia de su vector de distancia a todos sus vecinos. Cuando el nodo x recibe el nuevo vector de distancia de uno de sus vectores vecinos, v, guarda el vector de distancia de v y usa la ecuación de Bellman-Ford para actualizar su propio vector de distancia. La ecuación se da a continuación:

dx(y) = minv{ c(x,v) + dv(y)}     for each node y in N

El nodo x ha actualizado su propia tabla de vectores de distancia utilizando la ecuación anterior y envía su tabla actualizada a todos sus vecinos para que puedan actualizar sus propios vectores de distancia.

Algoritmo

At each node x,

Initialization

for all destinations y in N: Dx(y) = c(x,y) // If y is not a neighbor then c(x,y) = ∞ for each neighbor w Dw(y) = ? for all destination y in N. for each neighbor w send distance vector Dx = [ Dx(y) : y in N ] to w loop wait(until I receive any distance vector from some neighbor w) for each y in N: Dx(y) = minv{c(x,v)+Dv(y)} If Dx(y) is changed for any destination y Send distance vector Dx = [ Dx(y) : y in N ] to all neighbors forever

Nota: En el algoritmo de vector de distancia, el nodo x actualiza su tabla cuando ve cualquier cambio de costo en uno de los nodos directamente vinculados o recibe una actualización de vector de algún vecino.

Entendamos a través de un ejemplo:

Compartiendo información

Algoritmo de enrutamiento por vector de distancia

  • En la figura anterior, cada nube representa la red y el número dentro de la nube representa el ID de la red.
  • Todas las LAN están conectadas por enrutadores y están representadas en cuadros etiquetados como A, B, C, D, E, F.
  • El algoritmo de enrutamiento por vector de distancia simplifica el proceso de enrutamiento asumiendo que el costo de cada enlace es una unidad. Por lo tanto, la eficiencia de la transmisión se puede medir por el número de enlaces para llegar al destino.
  • En el enrutamiento por vector de distancia, el costo se basa en el recuento de saltos.

Algoritmo de enrutamiento por vector de distancia

En la figura anterior, observamos que el enrutador envía el conocimiento a los vecinos inmediatos. Los vecinos agregan este conocimiento a su propio conocimiento y envían la tabla actualizada a sus propios vecinos. De esta manera, los enrutadores obtienen su propia información más la nueva información sobre los vecinos.

Tabla de ruteo

Ocurren dos procesos:

  • Creando la Mesa
  • Actualizar la tabla

Creando la Mesa

Inicialmente, la tabla de enrutamiento se crea para cada enrutador que contiene al menos tres tipos de información, como la identificación de la red, el costo y el siguiente salto.

Algoritmo de enrutamiento por vector de distancia

  • ID DE RED: La ID de red define el destino final del paquete.
  • Costo: El costo es la cantidad de saltos que debe tomar el paquete para llegar allí.
  • Siguiente salto: Es el enrutador al que se debe entregar el paquete.

Algoritmo de enrutamiento por vector de distancia

  • En la figura anterior, se muestran las tablas de enrutamiento originales de todos los enrutadores. En una tabla de enrutamiento, la primera columna representa el ID de la red, la segunda columna representa el costo del enlace y la tercera columna está vacía.
  • Estas tablas de enrutamiento se envían a todos los vecinos.

Por ejemplo:

Actualizar la tabla

  • Cuando A recibe una tabla de enrutamiento de B, usa su información para actualizar la tabla.
  • La tabla de enrutamiento de B muestra cómo los paquetes pueden moverse a las redes 1 y 4.
  • El B es vecino del enrutador A, los paquetes de A a B pueden llegar en un salto. Entonces, 1 se agrega a todos los costos dados en la tabla de B y la suma será el costo para llegar a una red en particular.

Algoritmo de enrutamiento por vector de distancia

  • Después del ajuste, A combina esta tabla con su propia tabla para crear una tabla combinada.

Algoritmo de enrutamiento por vector de distancia

  • La tabla combinada puede contener algunos datos duplicados. En la figura anterior, la tabla combinada del enrutador A contiene los datos duplicados, por lo que solo conserva los datos que tienen el costo más bajo. Por ejemplo, A puede enviar los datos a la red 1 de dos formas. El primero, que no usa el siguiente enrutador, por lo que cuesta un salto. El segundo requiere dos saltos (A a B, luego B a la Red 1). La primera opción tiene el costo más bajo, por lo que se mantiene y la segunda se descarta.

Algoritmo de enrutamiento por vector de distancia

  • El proceso de creación de la tabla de enrutamiento continúa para todos los enrutadores. Cada enrutador recibe la información de los vecinos y actualiza la tabla de enrutamiento.

Las tablas de enrutamiento finales de todos los enrutadores se proporcionan a continuación:

Algoritmo de enrutamiento por vector de distancia

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Función Python open ()

Servicios web RESTful – Introducción