Tanto el algoritmo de Bellman-Ford como el algoritmo de Dijkstra se usan para calcular ‘métricas’ (distancia / costo de atravesar un enlace) en los protocolos de enrutamiento. Ambos consideran solo el conteo de saltos (el número de máquinas entre el origen del mensaje y el destino) como la métrica entre dos nodos. Otros factores, como el ancho de banda y el retraso, también se pueden usar para calcular la métrica, pero otros protocolos complejos los usan. La diferencia entre estos dos algoritmos radica en el tipo de protocolos que utilizan los algoritmos respectivos .
Hay dos tipos principales de protocolos de enrutamiento: protocolos de enrutamiento de vector de distancia (DVR) y protocolos de enrutamiento de estado de enlace (LSR) . Se supone que cada nodo conoce el costo para llegar a cada uno de sus vecinos.
- ¿Qué es un paquete en una red informática?
- Para la transmisión del sistema de archivos, ¿hay alguna manera de 'mantener una conexión abierta', como con TCP, o la transferencia de datos relativamente sin estado es lo suficientemente rápida?
- ¿Cómo explicaría el Protocolo de transmisión en tiempo real (RTSP) de una manera no complicada? ¿Por qué es mejor para la transmisión de video vigilancia?
- ¿La transferencia de archivos es más rápida cuando transfieres 1 archivo enorme, en comparación con numerosos archivos pequeños?
- ¿Cómo controla la ventana de congestión TCP la velocidad de envío en específico?
He dado una explicación detallada aquí. Si comprende los conceptos básicos, hay una respuesta resumida al final.
El algoritmo Bellman-Ford es utilizado por protocolos DVR como RIP y RIPv2. En un protocolo de enrutamiento por vector de distancia, cada enrutador de la red, en el que se ejecuta el protocolo, prepara paquetes de actualización de enrutamiento. La información en cada paquete de actualización de enrutamiento incluye la lista de todos los nodos en la red y los costos métricos correspondientes . Este paquete se reenvía a todos los vecinos del enrutador. Del mismo modo, el enrutador recibe una actualización de cada vecino y realiza las actualizaciones necesarias en su tabla de enrutamiento. Las distancias se calculan usando el algoritmo Bellman-Ford
Por otro lado, el algoritmo de Dijkstra es utilizado por protocolos LSR como OSPF. Los protocolos LSR son diferentes de los protocolos DVR ya que los enrutadores que implementan estos protocolos almacenan toda la topología de la red en su memoria. Hay 2 etapas en la construcción de una tabla de enrutamiento en protocolos LSR. Primero, debe almacenarse un mapa de toda la red en cada enrutador, y luego cada enrutador debe calcular la distancia más corta a cada nodo. Incluso aquí, las actualizaciones de enrutamiento se preparan periódicamente y cuando cambia la topología. Pero aquí, la actualización, llamada paquete de estado de enlace, se inunda (LSP) en toda la red , a diferencia del caso anterior, donde se envía solo a los vecinos. Cada LSP contiene una ID para la fuente, un Número de secuencia (para distinguir los paquetes más nuevos de los paquetes más antiguos) y las distancias desde el remitente a cada uno de sus vecinos. Cuando cada enrutador ha recopilado LSP de cada enrutador, comienza a crear la tabla de enrutamiento que incluye las rutas más cortas a cada nodo, utilizando el algoritmo de Dijkstra.
El algoritmo Bellman-Ford también tiene algunas desventajas adicionales . No se recomienda su uso en redes grandes. También sufre de algo conocido como el problema del conteo hasta el infinito que he explicado a continuación. (Imagen cortesía de Computer Networks por A. Tanenbaum)
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.
RESUMEN:
En el algoritmo de Bellman-Ford, cada nodo le dice a sus vecinos todo lo que sabe, incluso cosas que no sabe con certeza (los costos para los nodos vecinos).
En el algoritmo de Dijkstra, cada nodo le dice a toda la red solo las cosas que sabe con seguridad (el costo para cada uno de sus vecinos).
