Un protocolo de enrutamiento por vector de distancia en las redes de datos determina la mejor ruta para los paquetes de datos en función de la distancia. Los protocolos de enrutamiento por vector de distancia miden la distancia por el número de enrutadores que tiene que pasar un paquete, un enrutador cuenta como un salto. Algunos protocolos de vector de distancia también tienen en cuenta la latencia de la red y otros factores que influyen en el tráfico en una ruta determinada. Para determinar la mejor ruta a través de una red, los enrutadores, en los que se implementa un protocolo de vector de distancia, intercambian información entre sí, generalmente tablas de enrutamiento más recuentos de saltos para las redes de destino y posiblemente otra información de tráfico. Los protocolos de enrutamiento por vector de distancia también requieren que un enrutador informe a sus vecinos deLa topología de la red cambia periódicamente.
Los protocolos de enrutamiento por vector de distancia utilizan el algoritmo de Bellman-Ford para calcular la mejor ruta. Otra forma de calcular la mejor ruta a través de una red se basa en el costo del enlace y se implementa a través de protocolos de enrutamiento de estado de enlace .
El término vector de distancia se refiere al hecho de que el protocolo manipula vectores ( matrices ) de distancias a otros nodos de la red. El algoritmo de vector de distancia fue el algoritmo de enrutamiento de ARPANET original y se implementó más ampliamente en redes de área local con el Protocolo de información de enrutamiento (RIP).
Metodología
Los enrutadores que utilizan el protocolo de vector de distancia determinan la distancia entre ellos y un destino. La mejor ruta para los paquetes de Protocolo de Internet que transportan datos a través de una red de datos se mide en términos de la cantidad de enrutadores (saltos) que debe pasar un paquete para llegar a su red de destino. Además, algunos protocolos de vector de distancia tienen en cuenta otra información de tráfico, como la latencia de la red . Para establecer la mejor ruta, los enrutadores intercambian información regularmente con los enrutadores vecinos, generalmente su tabla de enrutamiento , el recuento de saltos para una red de destino y posiblemente otra información relacionada con el tráfico. Los enrutadores que implementan el protocolo de vector de distancia se basan únicamente en la información que les proporcionan otros enrutadores y no evalúan la topología de la red . [1]
Los protocolos de vector de distancia actualizan las tablas de enrutamiento de los enrutadores y determinan la ruta por la que se enviará un paquete en el siguiente salto, que es la interfaz de salida del enrutador y la dirección IP de la interfaz del enrutador receptor. La distancia es una medida del costo de llegar a un determinado nodo. La ruta de menor costo entre dos nodos es la ruta con distancia mínima.
Las actualizaciones se realizan periódicamente en un protocolo de vector de distancia donde toda o parte de la tabla de enrutamiento de un enrutador se envía a todos sus vecinos que están configurados para usar el mismo protocolo de enrutamiento de vector de distancia. Una vez que un enrutador tiene esta información, puede modificar su propia tabla de enrutamiento para reflejar los cambios y luego informar a sus vecinos de los cambios. Este proceso se ha descrito como 'enrutamiento por rumor' porque los enrutadores se basan en la información que reciben de otros enrutadores y no pueden determinar si la información es realmente válida y verdadera. Hay una serie de funciones que se pueden utilizar para ayudar con la inestabilidad y la información de enrutamiento inexacta.
Desarrollo de enrutamiento por vector de distancia
El protocolo de enrutamiento más antiguo y el protocolo de vector de distancia más antiguo es la versión 1 del Protocolo de información de enrutamiento (RIPv1). RIPv1 se estandarizó formalmente en 1988. [2] Establece la ruta más corta a través de una red basándose únicamente en los saltos, es decir, la cantidad de enrutadores que deben pasarse para llegar a la red de destino. RIP es un protocolo de puerta de enlace interior , por lo que se puede utilizar en redes de área local (LAN) en enrutadores interiores o fronterizos. Los enrutadores con implementación RIPv1 intercambian sus tablas de enrutamiento con los enrutadores vecinos transmitiendo un paquete RIPv1 cada 30 segundos a todas las redes conectadas. RIPv1 no es adecuado para redes grandes, ya que limita el número de saltos a 15. Este límite de saltos se introdujo para evitar bucles de enrutamiento, pero también significa que las redes que están conectadas a través de más de 15 enrutadores son inalcanzables. [3]
El protocolo de vector de distancia diseñado para su uso en redes de área amplia (WAN) es el Protocolo de puerta de enlace fronteriza (BGP). BGP es un protocolo de puerta de enlace exterior y, por lo tanto, se implementa en enrutadores fronterizos y exteriores en Internet . Intercambia información entre enrutadores a través de una sesión de Protocolo de control de transmisión (TCP). Los enrutadores con implementación de BGP determinan la ruta más corta a través de una red en función de una variedad de factores además de los saltos. Los administradores también pueden configurar BGP para que se prefieran o eviten determinadas rutas. BGP es utilizado por proveedores de servicios de Internet (ISP) y empresas de telecomunicaciones. [4]
Entre los protocolos de vector de distancia que se han descrito como híbridos, porque utiliza métodos de enrutamiento asociados con protocolos de enrutamiento de estado de enlace , se encuentra el Protocolo de enrutamiento de puerta de enlace interior mejorado (EIGRP) patentado . Fue desarrollado por Cisco en la década de 1980 y fue diseñado para ofrecer una mejor convergencia y causar menos tráfico de red entre enrutadores que el protocolo de enrutamiento de estado de enlace Open Shortest Path First (OSPF). [5]
Otro ejemplo de un protocolo de enrutamiento por vector de distancia es Babel .
Cuenta hasta el infinito problema
El algoritmo Bellman-Ford no evita que se produzcan bucles de enrutamiento y sufre el problema de conteo hasta el infinito . El núcleo del problema del conteo hasta el infinito es que si A le dice a B que tiene un camino en alguna parte, no hay forma de que B sepa si el camino tiene a B como parte de él. Para ver el problema con claridad, imagine una subred conectada como A – B – C – D – E – F y deje que la métrica entre los enrutadores sea "número de saltos". Ahora suponga que A se desconecta. En el proceso de actualización de vectores, B se da cuenta de que la ruta a A, que era la distancia 1, está inactiva; B no recibe la actualización del vector de A. El problema es que B también recibe una actualización de C y C todavía no lo está. consciente del hecho de que A está abajo, por lo que le dice a B que A está solo a dos saltos de C (C a B a A). Dado que B no sabe que la ruta de C a A es a través de sí mismo (B), actualiza su tabla con el nuevo valor "B a A = 2 + 1". Posteriormente, B reenvía la actualización a C y debido a que A es accesible a través de B (Desde el punto de vista de C), C decide actualizar su tabla a "C a A = 3 + 1". Esto se propaga lentamente a través de la red hasta que se vuelve infinito (en cuyo caso el algoritmo se corrige a sí mismo, debido a la propiedad de relajación de Bellman-Ford).
Soluciones provisionales y soluciones
RIP utiliza la técnica de horizonte dividido con veneno inverso para reducir la posibilidad de que se formen bucles y utiliza un número máximo de saltos para contrarrestar el problema de "cuenta hasta el infinito". Estas medidas evitan la formación de bucles de enrutamiento en algunos casos, pero no en todos. [6] La adición de un tiempo de espera (rechazar las actualizaciones de la ruta durante unos minutos después de una retracción de la ruta) evita la formación de bucles en prácticamente todos los casos, pero provoca un aumento significativo en los tiempos de convergencia.
Más recientemente, se han desarrollado varios protocolos de vector de distancia sin bucles; ejemplos notables son EIGRP , DSDV y Babel . Éstos evitan la formación de bucles en todos los casos, pero adolecen de una mayor complejidad y su implementación se ha visto ralentizada por el éxito de los protocolos de enrutamiento de estado de enlace como OSPF .
Ejemplo
En esta red tenemos 4 routers A, B, C y D:
Marcamos el tiempo actual (o iteración) en el algoritmo con T, y comenzamos (en el tiempo 0, o T = 0) creando matrices de distancia para cada enrutador a sus vecinos inmediatos. A medida que construimos las tablas de enrutamiento a continuación, la ruta más corta se resalta en verde y una nueva ruta más corta se resalta en amarillo. Las columnas grises indican nodos que no son vecinos del nodo actual y, por lo tanto, no se consideran una dirección válida en su tabla. El rojo indica entradas no válidas en la tabla, ya que se refieren a distancias de un nodo a sí mismo o a través de sí mismo.
T = 0 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
En este punto, todos los enrutadores (A, B, C, D) tienen nuevas "rutas más cortas" para su DV (la lista de distancias entre ellos y otro enrutador a través de un vecino). Cada uno de ellos transmite este nuevo DV a todos sus vecinos: A a B y C, B a C y A, C a A, B y D, y D a C.A medida que cada uno de estos vecinos recibe esta información, ahora recalculan la camino más corto usándolo. Por ejemplo: A recibe un DV de C que le dice a A que hay una ruta a través de C a D, con una distancia (o costo) de 5. Dado que la "ruta más corta" actual a C es 23, entonces A sabe que tiene una camino a D que cuesta 23 + 5 = 28. Como no hay otros caminos más cortos que A conozca, lo pone como su estimación actual para el camino más corto desde sí mismo (A) a D, a través de C. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
T = 1 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Nuevamente, todos los enrutadores han ganado en la última iteración (en T = 1) nuevas "rutas más cortas", por lo que todos transmiten sus DV a sus vecinos; Esto hace que cada vecino vuelva a calcular sus distancias más cortas. Por ejemplo: A recibe un DV de B que le dice a A que hay un camino a través de B a D, con una distancia (o costo) de 7. Dado que el "camino más corto" actual a B es 3, entonces A sabe que tiene un camino a D que cuesta 7 + 3 = 10. Esta ruta a D de longitud 10 (vía B) es más corta que la "ruta más corta" existente a D de longitud 28 (a través de C), por lo que se convierte en la nueva "ruta más corta" a D. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
T = 2 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Esta vez, solo los enrutadores A y D tienen nuevas rutas más cortas para sus DVs. Entonces, transmiten sus nuevos DV a sus vecinos: A transmite a B y C, y D transmite a C. Esto hace que cada uno de los vecinos que reciben los nuevos DV vuelva a calcular sus rutas más cortas. Sin embargo, dado que la información de los DV no produce rutas más cortas de las que ya tienen en sus tablas de enrutamiento, no hay cambios en las tablas de enrutamiento. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
T = 3 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Ninguno de los enrutadores tiene nuevas rutas más cortas para transmitir. Por lo tanto, ninguno de los enrutadores recibe información nueva que pueda cambiar sus tablas de enrutamiento. El algoritmo se detiene. |
Referencias
- ^ Tamara Dean (2009). Red + Guía de redes . Aprendizaje Cengage. págs. 274 . ISBN 9781423902454.
- ^ Hedrick, CL "Protocolo de información de enrutamiento" . tools.ietf.org . RFC 1058 . Consultado el 16 de abril de 2019 .
- ^ Tamara Dean (2009). Red + Guía de redes . Aprendizaje Cengage. págs. 274 . ISBN 9781423902454.
- ^ Tamara Dean (2009). Red + Guía de redes . Aprendizaje Cengage. pp. 274 -275. ISBN 9781423902454.
- ^ Tamara Dean (2009). Red + Guía de redes . Aprendizaje Cengage. págs. 275 . ISBN 9781423902454.
- ^ RFC 1058 , Sección 2.2.2
- "RFC1058 - Protocolo de información de enrutamiento", C. Hedrick, Grupo de trabajo de ingeniería de Internet, junio de 1988
- "RFC1723 - RIP Versión 2 con información adicional", G. Malkin, Grupo de trabajo de ingeniería de Internet, noviembre de 1994
- "RFC2453 - RIP Version 2", G. Malkin, Grupo de trabajo de ingeniería de Internet, noviembre de 1998
- "Un algoritmo de búsqueda de rutas para enrutamiento sin bucles , JJ García-Luna-Aceves y S. Murthy, IEEE / ACM Transactions on Networking, febrero de 1997
- "Detección de anuncios de enrutamiento no válidos en el protocolo RIP", D. Pei, D. Massey y L. Zhang, IEEE Global Communications Conference (Globecom), diciembre de 2003
Otras lecturas
- Sección "Estado de enlace versus vector de distancia" en el capítulo "Conceptos básicos de enrutamiento" en el "Manual de tecnología de interconexión de redes" de Cisco
- Sección 5.2 "Algoritmos de enrutamiento" en el Capítulo "5 LA CAPA DE RED" de "Redes de computadoras" 4to. Edición de Andrew S. Tanenbaum