Generaciones de enrutamiento

ARPANET estrategias de enrutamiento 1 ª Generación
1969
adaptativo distribuido con retraso estimado
longitud de la cola utilizada como estimación de la demora
utilizando el algoritmo de Bellman-Ford
nodo de intercambio vector retraso con los vecinos
actualizar la tabla de enrutamiento basado en información de entrada
problemas:
no tiene en cuenta la velocidad de línea, al igual longitudde la cola
longitud de la cola no es una buena medida de la demora
responde con lentitud a la congestión

En esta sección, veremos algunos ejemplos de las estrategias de enrutamiento. Todos estos fueron desarrollados inicialmente para ARPANET, que es una red de conmutación de paquetes que fue el fundamento de la Internet de hoy en día. Es instructivo examinar estas estrategias.
El algoritmo deenrutamiento original, diseñado en 1969, fue un algoritmo distribuido de adaptación con retraso estimado como el criterio de desempeño y una versión del algoritmo de Bellman-Ford. Para este algoritmo, cada nodo mantiene dos vectores: Di = retraso vector para el nodo i, y Si = nodo sucesor vector para el nodo i. Periódicamente (cada ms 128), cada nodo de intercambio de su vector de retraso contodos sus vecinos, que actualizan sus dos vectores utilizando esa información (véase el texto para más detalles). El retraso enlace estimada es simplemente la longitud de cola de ese enlace. Por lo tanto, en la construcción de una nueva tabla de enrutamiento, el nodo tienden a favorecer a los enlaces salientes con colas más cortas. Esto tiende a equilibrar la carga en los enlaces salientes. Sinembargo, debido a las longitudes de cola varían rápidamente con el tiempo, la percepción distribuidos de la ruta más corta podría cambiar, mientras que un paquete está en camino. Esto podría llevar a una situación paliza en la que un paquete sigue en busca de áreas de congestión de baja en lugar de procurar a su destino.


ARPANET estrategias de enrutamiento de 2 ª generación
1979
adaptativodistribuido con retraso medido
con marcas de tiempo de los tiempos de llegada, salida y ACK
recalcula promedio de los retrasos cada 10secs
cualquier cambio se distribuyen a todos los demás nodos
enrutamiento recalcula utilizando Dijkstraâ € ™ s algoritmo
bien bajo cargas ligeras y medianas
con cargas pesadas, poca correlación entre retrasos y experimentado esos
Después de algunos años deexperiencia y varias modificaciones menores, el algoritmo de encaminamiento original fue sustituida por otra muy diferente en 1979. El nuevo algoritmo es también una distribución adaptativa uno, con retraso, como el criterio de desempeño. En lugar de utilizar longitud de la cola como un sustituto en caso de retraso, la demora se mide directamente. En un nodo, cada paquete entrante es con fecha y hora conuna hora de llegada. A la hora de salida se registra cuando el paquete se transmite. Si una confirmación positiva se devuelve, la demora para que el paquete se registra como la hora de salida menos el tiempo de llegada, junto con el tiempo de transmisión y el retardo de propagación. Cada 10 segundos, el nodo calcula el retraso medio en cada enlace de salida. Si hay algún cambio significativo enla demora, la información se envía a todos los demás nodos con las inundaciones. Cada nodo mantiene una estimación de retardo en cada enlace de red. Cuando llega nueva información, se vuelve a calcular su tabla de enrutamiento utilizando el algoritmo de Dijkstra. La experiencia con esta nueva estrategia indicó que era más ágil y estable que el anterior. La sobrecarga inducida por las inundacionesfue moderado ya que cada nodo hace como máximo una vez cada 10 segundos. Sin embargo, como la carga en la red creció, un defecto en la nueva estrategia comenzó a aparecer, debido a la suposición de que el retardo medido en un enlace es un buen predictor de la demora enlace encontrado después de todos los nodos de desviar el tráfico sobre la base de este informó demora. Por lo tanto, se trata de...