Gracias por A2A
Respuesta corta:
El enrutamiento de estado de enlace (LSR) usa ancho de banda y retraso, mientras que el enrutamiento por vector de distancia (DVR) usa conteos de saltos para asignar valores a los bordes y los valores de estas cosas no pueden ser negativos.
- ¿Podemos configurar las direcciones IP en las interfaces físicas de un conmutador?
- Para descargar, ¿es HTTP o FTP mejor hoy en día?
- ¿Cuáles son las razones por las que la mayoría de las empresas e instituciones utilizan TCP, no UDP, para llamadas de videoconferencia o para transmisión en vivo?
- ¿Puedo hacer ping a mi computadora portátil que está conectada a WiFi desde una instancia EC2?
- ¿Qué significa que HTTP está en capas?
El LSR se usa generalmente en redes más grandes en las que se requieren algoritmos más rápidos y robustos, como Dijkstra. La principal desventaja de usar el algoritmo Bellman-Ford en una red más grande es “Count to Infinity”, que se produce cuando un enrutador se apaga y sabemos que las posibilidades de esto son muy altas en redes más grandes.
Dijkstra no se puede usar en DVR porque requiere una base de datos completa de toda la topología de la red (o área). Los protocolos de DVR no llevan eso. [1]
Respuesta larga:
Enrutamiento de estado de enlace:
Tomado de: Página en nptel.ac.in
Enrutamiento de estado de enlace:
El enrutamiento por vector de distancia se utilizó en ARPANET hasta 1979, cuando fue
reemplazado por enrutamiento de estado de enlace. Dos problemas principales causaron su desaparición. Primero, dado que la métrica de retraso era la longitud de la cola, no tuvo en cuenta el ancho de banda de la línea al elegir las rutas. Inicialmente, todas las líneas tenían 56 kbps, por lo que el ancho de banda de la línea no era un problema, pero después de que algunas líneas se actualizaron a 230 kbps y otras a 1.544 Mbps, no tomar en cuenta el ancho de banda fue un problema importante. Por supuesto, habría sido posible cambiar la métrica de retraso para tener en cuenta el ancho de banda de la línea, pero también existía un segundo problema, a saber, el algoritmo a menudo tardaba demasiado en converger, incluso con trucos como el horizonte dividido. Por estas razones, fue reemplazado por un algoritmo completamente nuevo que ahora se denomina enrutamiento de estado de enlace. Las variantes de enrutamiento de estado de enlace ahora se usan ampliamente. La idea detrás del enrutamiento del estado del enlace es simple y puede expresarse en cinco partes.
Cada enrutador debe hacer lo siguiente:
1. Descubra a sus vecinos y conozca sus direcciones de red.
2. Mida el retraso o el costo para cada uno de sus vecinos.
3. Construya un paquete contando todo lo que acaba de aprender.
4. Envíe este paquete a todos los otros enrutadores.
5. Calcule la ruta más corta a cualquier otro enrutador.
Este también me pareció interesante, está aquí: Protocolos de enrutamiento de estado de enlace
Protocolos de enrutamiento de estado de enlace:
La información disponible para un enrutador de vector de distancia se ha comparado con la información disponible de una señal de tráfico. Los protocolos de enrutamiento de estado de enlace son como una hoja de ruta. Un enrutador de estado de enlace no puede ser engañado tan fácilmente para tomar malas decisiones de enrutamiento, ya que tiene una imagen completa de la red. La razón es que, a diferencia del enfoque de enrutamiento por rumor del vector de distancia, los enrutadores de estado de enlace tienen información de primera mano de todos sus enrutadores pares. Cada enrutador genera información sobre sí mismo, sus enlaces directamente conectados y el estado de esos enlaces (de ahí el nombre). Esta información se transmite de enrutador a enrutador, cada enrutador hace una copia, pero nunca la cambia. El objetivo final es que cada enrutador tenga información idéntica sobre la red interna, y cada enrutador calculará independientemente sus mejores rutas.
Los protocolos de estado de enlace, a veces llamados primero la ruta más corta o protocolos de bases de datos distribuidas , se basan en un algoritmo conocido de la teoría de gráficos, el algoritmo de ruta más corta de EW Dijkstra.Aunque los protocolos de estado de enlace se consideran más complejos que los protocolos de vector de distancia, la funcionalidad básica no es compleja en absoluto:
- Cada enrutador establece una relación, una adyacencia, con cada uno de sus vecinos.
- Cada enrutador envía anuncios de estado de enlace (LSA), algunos
- Cada enrutador almacena una copia de todos los LSA que ha visto en una base de datos. Si todo funciona bien, las bases de datos en todos los enrutadores deben ser idénticas.
- La base de datos topológica completa, también llamada base de datos de estado de enlace , describe un gráfico de la red interna. Usando el algoritmo Dijkstra, cada enrutador calcula la ruta más corta a cada red e ingresa esta información en la tabla de rutas.
Enrutamiento vectorial a distancia:
Forma tomada: Protocolos de enrutamiento por vector de distancia
La mayoría de los protocolos de enrutamiento se dividen en una de dos clases: vector de distancia o estado de enlace .
El nombre del vector de distancia se deriva del hecho de que las rutas se anuncian como vectores de (distancia, dirección), donde la distancia se define en términos de una métrica y la dirección se define en términos del enrutador del siguiente salto. Por ejemplo, “El destino A está a una distancia de 5 saltos en la dirección del enrutador X del siguiente salto”. Como esa afirmación implica, cada enrutador aprende rutas desde las perspectivas de sus enrutadores vecinos y luego anuncia las rutas desde su propia perspectiva. Debido a que cada enrutador depende de sus vecinos para obtener información, que los vecinos a su vez pueden haber aprendido de sus vecinos, y así sucesivamente, el enrutamiento de vector de distancia a veces se denomina “enrutamiento por rumor”.Características comunes:
Un protocolo de enrutamiento de vector de distancia típico utiliza un algoritmo de enrutamiento en el que los enrutadores envían periódicamente actualizaciones de enrutamiento a todos los vecinos transmitiendo sus tablas de rutas completas.
Junto con lo anterior:
1. Cada enrutador mantiene una tabla:
Destino, costo estimado, enlace, conteo de saltos, retraso de tiempo en ms, longitud de la cola, etc.
2. Actualizado mediante el intercambio de información entre el enrutador – ICMP
Algoritmo de Dijkstra:
Tomado de: el algoritmo de Dijkstra
El algoritmo de Dijkstra, concebido por el científico informático Edsger Dijkstra en 1956 y publicado en 1959, es un algoritmo de búsqueda de gráficos que resuelve el problema de la ruta más corta de una sola fuente para un gráfico con costos de ruta de borde no negativos, produciendo un árbol de ruta más corta. Este algoritmo se usa a menudo en el enrutamiento y como una subrutina en otros algoritmos gráficos.
Para un vértice fuente (nodo) dado en el gráfico, el algoritmo encuentra la ruta con el costo más bajo (es decir, la ruta más corta) entre ese vértice y todos los demás vértices. También se puede usar para encontrar los costos de las rutas más cortas desde un único vértice a un único vértice de destino deteniendo el algoritmo una vez que se ha determinado la ruta más corta al vértice de destino. Por ejemplo, si los vértices del gráfico representan ciudades y los costos del camino de borde representan distancias de conducción entre pares de ciudades conectadas por una carretera directa, el algoritmo de Dijkstra se puede usar para encontrar la ruta más corta entre una ciudad y todas las demás ciudades. Como resultado, el algoritmo de ruta más corta se usa ampliamente en protocolos de enrutamiento de red, especialmente IS-IS y OSPF (Open Shortest Path First).
Ilustración de la búsqueda del algoritmo de Dijkstra para encontrar la ruta desde un nodo de inicio (abajo a la izquierda, rojo) hasta un nodo objetivo (arriba a la derecha, verde) en un problema de planificación de movimiento del robot. Los nodos abiertos representan el conjunto “tentativo”. Los nodos rellenos son visitados, con un color que representa la distancia: cuanto más verde, más lejos. Los nodos en todas las diferentes direcciones se exploran de manera uniforme, apareciendo como un frente de onda circular más o menos, ya que el algoritmo de Dijkstra usa una heurística idénticamente igual a 0:
Algoritmo:
Selecciona el vértice no visitado con la distancia más baja, calcula la distancia a través de él a cada vecino no visitado y actualiza la distancia del vecino si es más pequeño. Mark visitó (configurado en rojo) cuando terminó con los vecinos.
Algoritmo de Bellman-Ford:
Tomado de: algoritmo Bellman – Ford
El algoritmo Bellman-Ford es un algoritmo que calcula las rutas más cortas desde un vértice de origen único a todos los otros vértices en un dígrafo ponderado. Es más lento que el algoritmo de Dijkstra para el mismo problema, pero más versátil, ya que es capaz de manejar gráficos en los que algunos de los pesos de los bordes son números negativos. El algoritmo generalmente lleva el nombre de dos de sus desarrolladores, Richard Bellman y Lester Ford, Jr., quienes lo publicaron en 1958 y 1956, respectivamente; sin embargo, Edward F. Moore también publicó el mismo algoritmo en 1957, y por esta razón también a veces se le llama algoritmo Bellman-Ford-Moore.
Los pesos de borde negativos se encuentran en varias aplicaciones de gráficos, de ahí la utilidad de este algoritmo. Si un gráfico contiene un “ciclo negativo” (es decir, un ciclo cuyos bordes suman un valor negativo) al que se puede acceder desde la fuente, entonces no hay una ruta más barata: cualquier ruta puede volverse más barata con una caminata más alrededor del ciclo negativo. En tal caso, el algoritmo Bellman-Ford puede detectar ciclos negativos e informar su existencia.
Algoritmo:
Bellman – Ford se basa en el principio de relajación, en el que una aproximación a la distancia correcta se reemplaza gradualmente por valores más precisos hasta llegar a la solución óptima. En ambos algoritmos, la distancia aproximada a cada vértice es siempre una sobreestimación de la distancia real, y se reemplaza por el mínimo de su valor anterior con la longitud de una ruta recién encontrada. Sin embargo, el algoritmo de Dijkstra selecciona con avidez el nodo de peso mínimo que aún no se ha procesado, y realiza este proceso de relajación en todos sus bordes salientes; por el contrario, el algoritmo Bellman-Ford simplemente relaja todos los bordes y hace esto | V | -1 veces, donde | V | es el número de vértices en el gráfico. En cada una de estas repeticiones, aumenta el número de vértices con distancias calculadas correctamente, de lo que se deduce que eventualmente todos los vértices tendrán sus distancias correctas. Este método permite aplicar el algoritmo Bellman-Ford a una clase de entradas más amplia que Dijkstra.
Ahora, aquí hay algunos puntos importantes tomados de las fuentes mencionadas anteriormente:
En LSR, cada nodo envía el mapa completo de toda la red a todos los demás nodos de la red, mientras que en DVR cada nodo envía un vector de distancia, es decir (distancia, vector), solo a sus nodos vecinos. Ahora, en el caso de LSR, siempre que haya un cambio en la conectividad entre un nodo y sus vecinos, se vuelve a calcular el mensaje de estado de enlace que proporciona información sobre los vecinos, y luego se inunda a través de la red, mientras que en DVR el cambio solo se envía a los vecinos debido a se produce este conteo hasta el infinito (esta es la principal desventaja del algoritmo Bellman-Ford).
Cuenta hasta el infinito [2]:
Supongamos que todos los nodos acaban de iniciarse como se muestra en la figura (a). Inicialmente no existen rutas como se muestra por los puntos. La figura solo explica las rutas de A. A recibe una actualización de enrutamiento de B y A se entera de que está a solo 1 salto de distancia, por lo que se ingresa en la tabla de enrutamiento de A. B aprende una ruta a C en este mismo turno a partir de la actualización de C. Incluye esto en su próxima actualización de A y, por lo tanto, A aprende que C está a 1 salto de distancia de B. Por lo tanto, la actualización se realiza en A que C está a 2 saltos de distancia (A a B + B a C). Del mismo modo, A aprende que D es de 2 saltos de B y E es de 3 saltos, de las actualizaciones posteriores. Así, A aprende las rutas a cada nodo.
Ahora suponga que A se apaga. El enlace AB se corta. La métrica se ha convertido en infinito. En esta situación, cuando B recibe una actualización de C, se da cuenta de que hay una ruta a A a través de C y, por lo tanto, actualiza su tabla de enrutamiento (B a C + C a A). Este cambio se refleja en la próxima actualización de B. C actualiza su enlace a A (A a B + B a C) y así sucesivamente. Como se puede ver, la métrica seguirá aumentando y continuará hasta el infinito, y de ahí el nombre ‘Cuenta hasta el infinito’. ¡El problema surge porque B no se da cuenta de que el camino hacia A que C anunció pasa a través de B mismo!
Para resolver esto, se define el conteo máximo de saltos que introduce su primera desventaja (redes grandes). Las técnicas como horizonte dividido y horizonte dividido con veneno inverso también se utilizan para eliminar este problema
Pero el algoritmo de Dijkstra también es mucho más rápido que Bellman-Ford.
El algoritmo Dijkstra no se puede usar en DVR porque el algoritmo necesita una base de datos de toda la red que no es transportada por DVR.
El algoritmo de Dijkstra no funciona en bordes negativos, mientras que el algoritmo Bellman-Ford funciona en bordes negativos. LSR usa ancho de banda y tiempo de retraso y algunos otros factores, estos factores no pueden ser negativos, mientras que DVR usa el conteo de saltos y la longitud de la cola y algunos otros factores, estos tampoco pueden ser negativos por razones obvias.
Conclusión:
DVR no lleva la base de datos de topología de red completa, debido a esto Dijkstra no se puede usar en DVR.
En redes más grandes, las posibilidades de falla de un enrutador son altas debido a que este algoritmo de Bellman-Ford no se puede usar en redes más grandes porque tiene la desventaja de contar hasta el infinito.
El LSR generalmente se usa en redes más grandes y el algoritmo Bellman-Ford es más lento que el algoritmo Dijkstra, por lo tanto, este es otro problema del algoritmo Bellman-Ford debido a que no se puede usar en redes más grandes.
Espero que hayas recibido tu respuesta.
Referencias
[1] La respuesta de Tony Li al algoritmo Dijkstra ¿Se puede utilizar para el enrutamiento de vector de distancia?
[2] La respuesta de Siddharth Sheth a ¿Cómo funcionan el algoritmo de Bellman-Ford y el algoritmo de Dijkstra de manera diferente en los protocolos de enrutamiento?
