Protocolo de enrutamiento por vector de distancia (DVR) – Part 1

Un protocolo de enrutamiento por vector de distancia (DVR) requiere que un enrutador informe periódicamente a sus vecinos sobre los cambios de topología. Históricamente conocido como el antiguo algoritmo de enrutamiento ARPANET (o conocido como algoritmo Bellman-Ford).

Conceptos básicos de Bellman Ford: cada enrutador mantiene una tabla de vectores de distancia que contiene la distancia entre él y TODOS los posibles Nodes de destino. Las distancias, basadas en una métrica elegida, se calculan usando información de los vectores de distancia de los vecinos.

Information kept by DV router -

• Cada enrutador tiene una identificación
• Asociado a cada enlace conectado a un router, existe un coste de enlace (estático o dinámico).
• Lúpulos intermedios

Inicialización de la tabla de vectores de distancia –

• Distancia a sí mismo = 0
• Distancia a TODOS los demás enrutadores = número infinito.

Algoritmo de vector de distancia –

1. Un enrutador transmite su vector de distancia a cada uno de sus vecinos en un paquete de enrutamiento.
2. Cada enrutador recibe y guarda el vector de distancia recibido más recientemente de cada uno de sus vecinos.
3. Un enrutador vuelve a calcular su vector de distancia cuando:
   • Recibe un vector de distancia de un vecino que contiene información diferente a la anterior.
   • Descubre que un enlace a un vecino se ha caído.

El cálculo del DV se basa en minimizar el costo a cada destino

Dx(y) = Estimate of least cost from x to y 
C(x,v) =  Node x knows cost to each neighbor v
Dx   =  [Dx(y): y ∈ N ] = Node x maintains distance vector
Node x also maintains its neighbors' distance vectors
– For each neighbor v, x maintains Dv = [Dv(y): y ∈ N ]

Nota –

• De vez en cuando, cada Node envía su propia estimación de vector de distancia a los vecinos.
• Cuando un Node x recibe una nueva estimación de DV de cualquier vecino v, guarda el vector de distancia de v y actualiza su propio DV usando la ecuación BF:

  Dx(y) = min { C(x,v) + Dv(y), Dx(y) } for each node y ∈ N
  

Ejemplo: considere 3 enrutadores X, Y y Z como se muestra en la figura. Cada enrutador tiene su tabla de enrutamiento. Cada tabla de enrutamiento contendrá la distancia a los Nodes de destino.

Considere el enrutador X, X compartirá su tabla de enrutamiento con los vecinos y los vecinos compartirán su tabla de enrutamiento con X y la distancia desde el Node X hasta el destino se calculará utilizando la ecuación Bellmen-Ford.

 Dx(y) = min { C(x,v) + Dv(y)} for each node y ∈ N

Como podemos ver, la distancia será menor yendo de X a Z cuando Y sea un Node intermedio (salto), por lo que se actualizará en la tabla de enrutamiento X.

De manera similar, para Z también:

Finalmente, la tabla de enrutamiento para todos:

ventajas del enrutamiento de vector de distancia:

• Es más sencillo de configurar y mantener que el enrutamiento de estado de enlace.

Desventajas del enrutamiento por vector de distancia:

• Es más lento para converger que el estado del enlace.
• Está en riesgo por el problema de contar hasta el infinito.
• Crea más tráfico que el estado del enlace, ya que un cambio en el conteo de saltos debe propagarse a todos los enrutadores y procesarse en cada enrutador. Las actualizaciones del conteo de saltos se realizan periódicamente, incluso si no hay cambios en la topología de la red, por lo que aún se producen transmisiones que desperdician ancho de banda.
• Para redes más grandes, el enrutamiento por vector de distancia da como resultado tablas de enrutamiento más grandes que el estado del enlace, ya que cada enrutador debe conocer todos los demás enrutadores. Esto también puede generar congestión en los enlaces WAN.

Nota: el enrutamiento de vector de distancia utiliza UDP (protocolo de datagrama de usuario) para el transporte.

Preguntas de GATE CS Corner

Practicar las siguientes preguntas te ayudará a poner a prueba tus conocimientos. Todas las preguntas se han hecho en GATE en años anteriores o en pruebas simuladas de GATE. Es muy recomendable que los practiques.

1. GATE CS 2011, Pregunta 52
2. GATE CS 2011, Pregunta 53
3. GATE CS 2010, Pregunta 54
4. GATE CS 2010, Pregunta 55
5. GATE IT 2005, Pregunta 28
6. GATE CS 2014 (Conjunto 1), Pregunta 33
7. GATE IT 2008, Pregunta 65
8. GATE CS 2014 (Conjunto 2), Pregunta 65

Referencias –

Enrutamiento por vector de distancia – wikipedia
www.eecs.yorku.ca

Este artículo es una contribución de Akash Sharan . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.