Funcionamiento de algoritmos bellman-ford y dijikstra

COMUNICACIÓN DE DATOS II

Algoritmo Bellman-Ford

Los algoritmos de enrutamiento por vector de distancia operan haciendo que cada enrutador mantenga una tabla (por ejemplo, un vector) que da lamejor distancia conocida a cada destino y la línea a usar para llegar ahí. Estas tablas se actualizan intercambiando información con vecinos.En el enrutamiento por vector de distancia, cada enrutadormantiene una tabla de enrutamiento indizada por, y conteniendo un registro de, cada enrutador de la subred.

Esta entrada comprende dos partes: la línea preferida de salida hacia ese destino y unaestimación del tiempo o distancia a ese destino. La métrica usada podría ser la cantidad de escalas, el retardo de tiempo en milisegundos, el número total de paquetes encolados por la trayectoria, oalgo parecido.

Se supone que cada enrutador conoce la “distancia” a cada uno de sus vecinos. Si la métrica es de escalas, la distancia simplemente es una escala. Si la métrica es la longitud de lacola, el enrutador simplemente examina cada cola. Si la métrica es el retardo, el enrutador puede medirlo directamente con paquetes especiales de ECO que el receptor simplemente marca con la hora yenvía de regreso tan rápido como puede.

Supóngase que se usa como métrica el retardo y que el enrutador conoce el retardo a cada uno de sus vecinos. Cada T mseg, cada enrutador envía a todos sus vecinosuna lista de los retardos estimados a cada uno de los destinos. También recibe una lista parecida de cada vecino. Imagine que una de estas tablas acaba de llegar del vecino X, siendo Xi la estimaciónde X respecto al tiempo que le toma llegar al enrutador i a través de X en Xi + m mseg vía X . Efectuando este cálculo para cada vecino, un enrutador puede encontrar la estimación que parezca ser lamejor y usar esa estimación y la línea correspondiente en su nueva tabla de enrutamiento.

Este proceso de actualización se ilustra en la figura 2. En la parte (a) se muestra una subred. En las...