Protocolo de enrutamiento por vector de distancia
 | Este artículo tiene varios problemas. Ayúdenos a mejorarlo o a discutir estos problemas en la página de discusión . ( Aprenda cómo y cuándo eliminar estos mensajes )
|
Un protocolo de enrutamiento por vector de distancia en 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 según la cantidad de enrutadores que debe atravesar 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 que utilizan un protocolo de vector de distancia intercambian información entre sí, generalmente tablas de enrutamiento más conteos 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 de los cambios de topología de red periódicamente.
Los protocolos de enrutamiento por vector de distancia utilizan el algoritmo 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 original de ARPANET y se implementó de manera más amplia en redes de área local con el Protocolo de información de enrutamiento (RIP).
Descripción general
Los protocolos de enrutamiento por vector de distancia utilizan el algoritmo Bellman-Ford . En estos protocolos, cada enrutador no posee información sobre la topología completa de la red . Anuncia su valor de distancia (DV) calculado a otros enrutadores y recibe anuncios similares de otros enrutadores a menos que se realicen cambios en la red local o por parte de vecinos (enrutadores). Mediante estos anuncios de enrutamiento, cada enrutador llena su tabla de enrutamiento. En el siguiente ciclo de anuncios, un enrutador anuncia información actualizada de su tabla de enrutamiento. Este proceso continúa hasta que las tablas de enrutamiento de cada enrutador convergen a valores estables.
Algunos de estos protocolos tienen la desventaja de una convergencia lenta.
Ejemplos de protocolos de enrutamiento por vector de distancia:
- Protocolo de información de enrutamiento (RIP)
- Protocolo de información de enrutamiento versión 2 (RIPv2)
- Protocolo de información de enrutamiento de próxima generación (RIPng), una extensión de RIP versión 2 con soporte para IPv6
- Protocolo de enrutamiento de puerta de enlace interior (IGRP)
- Protocolo de enrutamiento de puerta de enlace interior mejorado (EIGRP)
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 datos a través de una red de datos se mide en términos de la cantidad de enrutadores (saltos) que un paquete debe atravesar 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 conteo 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 exclusivamente 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 para llegar a un nodo determinado. La ruta de menor costo entre dos nodos es la ruta con la distancia mínima.
Las actualizaciones se realizan periódicamente en un protocolo de vector de distancia donde la totalidad 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 sobre los cambios. Este proceso se ha descrito como "enrutamiento por rumores" porque los enrutadores dependen de 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 características 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 se deben pasar 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 de borde. Los enrutadores con implementación RIPv1 intercambian sus tablas de enrutamiento con enrutadores vecinos mediante la difusión de un paquete RIPv1 cada 30 segundos en todas las redes conectadas. RIPv1 no es adecuado para redes grandes, ya que limita la cantidad 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 de borde (BGP). BGP es un protocolo de puerta de enlace exterior y, por lo tanto, se implementa en enrutadores de borde 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 distintos de los saltos. BGP también puede ser configurado por los administradores para que se prefieran o eviten ciertas 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, debido a que utilizan métodos de enrutamiento asociados con los protocolos de enrutamiento de estado de enlace , se encuentra el protocolo propietario Enhanced Interior Gateway Routing Protocol (EIGRP). 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 .
Problema de contar hasta el infinito
El algoritmo Bellman-Ford no evita que se produzcan bucles de enrutamiento y sufre del problema de contar hasta el infinito . El núcleo del problema de contar hasta el infinito es que si A le dice a B que tiene una ruta en alguna parte, no hay forma de que B sepa si la ruta tiene a B como parte de ella. Para ver el problema, 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 del vector, B nota 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 es consciente del hecho de que A está inactivo, por lo que le dice a B que A está a solo dos saltos de C (C a B a A). Como B no sabe que la ruta de C a A pasa por 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 alcanzable 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 alternativas y alternativas
RIP utiliza la técnica de horizonte dividido con reversión de envenenamiento para reducir la posibilidad de formación de bucles y utiliza un número máximo de saltos para contrarrestar el problema de "contar 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 (rechazando las actualizaciones de ruta durante unos minutos después de una retracción de 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; algunos ejemplos notables son EIGRP , DSDV y Babel . Estos evitan la formación de bucles en todos los casos, pero sufren 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 desde 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 nuevos "caminos más cortos" para su DV (la lista de distancias que hay 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 el camino más corto usándola. Por ejemplo: A recibe un DV de C que le dice que hay un camino a través de C hacia D, con una distancia (o costo) de 5. Como el "camino más corto" actual hacia C es 23, entonces A sabe que tiene un camino hacia D que cuesta 23+5=28. Como no hay otros caminos más cortos que A conozca, pone este como su estimación actual para el camino más corto desde sí mismo (A) hacia D, vía C. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| T=1 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Nuevamente, todos los enrutadores han ganado en la última iteración (en T=1) nuevos "caminos más cortos", por lo que todos transmiten sus DV a sus vecinos; esto impulsa a cada vecino a volver a calcular sus distancias más cortas. Por ejemplo: A recibe un DV de B que le dice que hay un camino a través de B hacia D, con una distancia (o costo) de 7. Como el "camino más corto" actual hacia B es 3, entonces A sabe que tiene un camino hacia D que cuesta 7+3=10. Este camino hacia D de longitud 10 (a través de B) es más corto que el "camino más corto" existente hacia D de longitud 28 (a través de C), por lo que se convierte en el nuevo "camino más corto" hacia D. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| T=2 |
|
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Esta vez, solo los enrutadores A y D tienen nuevas rutas más cortas para sus DV. Por lo tanto, transmiten sus nuevas 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 las nuevas DV vuelva a calcular sus rutas más cortas. Sin embargo, dado que la información de las DV no produce rutas más cortas que 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). Guía de redes de Network+ . Cengage Learning. pp. 274. ISBN 9781423902454.
- ^ C. Hedrick (junio de 1988). Protocolo de información de enrutamiento. Grupo de trabajo de redes. doi : 10.17487/RFC1058 . RFC 1058. Histórico. Actualizado por RFC 1388 y 1723.
- ^ Tamara Dean (2009). Guía de redes de Network+ . Cengage Learning. pp. 274. ISBN 9781423902454.
- ^ Tamara Dean (2009). Guía de redes de Network+ . Cengage Learning. págs. 274-275. ISBN 9781423902454.
- ^ Tamara Dean (2009). Guía de redes de Network+ . Cengage Learning. pp. 275. ISBN 9781423902454.
- ^ C. Hedrick (junio de 1988). Protocolo de información de enrutamiento. Grupo de trabajo de redes. doi : 10.17487/RFC1058 . RFC 1058. Histórico. Sección 2.2.2. Actualizado por RFC 1388 y 1723.
- G. Malkin (noviembre de 1998). RIP versión 2. Grupo de trabajo de redes. doi : 10.17487/RFC2453 . STD 53. RFC 2453. Estándar de Internet. Obsoletos RFC 1723 y 1388. Actualizado por RFC 4822.
- "Un algoritmo de búsqueda de rutas para enrutamiento sin bucles" , JJ Garcia-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
Lectura adicional
- Sección "Estado de enlace versus vector de distancia" Archivado el 14 de diciembre de 2010 en Wayback Machine 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", 4.ª edición, de Andrew S. Tanenbaum
