Notas de autoaprendizaje de redes informáticas: algoritmo de enrutamiento

La capa de red debe determinar la ruta que sigue el paquete desde el remitente hasta el receptor. El enrutamiento consiste en determinar la ruta (es decir, el enrutamiento) para un determinado datagrama en el enrutador de la red.

Un host generalmente está conectado directamente a un enrutador, que es el enrutador predeterminado del host, también conocido como puerta de enlace predeterminada del host. Siempre que un host envía un paquete a la red externa, el paquete se envía a su puerta de enlace predeterminada.

Si la puerta de enlace predeterminada del host de origen se llama enrutador de origen, la puerta de enlace predeterminada del host de destino se llama enrutador de destino. El problema de enrutar un paquete desde el host de origen al de destino puede reducirse al problema de enrutar desde el enrutador de origen al enrutador de destino.

El objetivo del algoritmo de enrutamiento es simple: dado un conjunto de enrutadores y los enlaces que conectan los enrutadores, el algoritmo de enrutamiento debe encontrar la mejor ruta desde el enrutador de origen al enrutador de destino. Generalmente, una buena ruta es. El camino con el menor coste.

Un grafo G = (N, E) es un conjunto de N nodos y E aristas, donde cada arista es un par de nodos de N. En el contexto del enrutamiento de red, los nodos representan enrutadores, que son los nodos que toman decisiones de reenvío de paquetes, y los bordes que conectan los nodos representan enlaces físicos entre enrutadores.

Una ventaja tiene un valor que representa su coste. Normalmente, el costo de un borde puede reflejar la longitud física del enlace correspondiente, la velocidad del enlace o los costos asociados con ese enlace.

Para cualquier arista (xy) en E, c(xy) se puede utilizar para representar el coste de la arista entre los nodos x e y. Generalmente se consideran grafos no dirigidos, por lo que las aristas (xy) y las aristas (y x) son iguales y tienen el mismo costo. El nodo y también se denomina vecino del nodo x.

Después de asignar un costo a cada borde del gráfico, el objetivo del algoritmo de enrutamiento es, naturalmente, encontrar la ruta de menor costo desde el origen hasta el destino. Un camino (Path) en el gráfico G = (N, E) es una secuencia de nodos tal que cada par que comienza con (x1, x2), (x2, x3), ..., es una arista en E. El costo de un camino es la suma de los costos de todos los bordes a lo largo del camino.

En términos generales, una forma de clasificar los algoritmos de enrutamiento se basa en si el algoritmo es global o distribuido.

.Algoritmo de enrutamiento global: utilice información completa y global de la red para calcular la ruta de menor costo desde el origen al destino.

De hecho, los algoritmos con información de estado global a menudo se denominan algoritmos LS de estado de enlace porque el algoritmo debe conocer el coste de cada enlace de la red.

.Algoritmo de enrutamiento distribuido: Calcula la ruta de menor costo de forma iterativa y distribuida. Al calcular e intercambiar información de forma iterativa con nodos adyacentes, se calcula gradualmente la ruta de menor costo hacia un determinado nodo de destino o un grupo de nodos de destino.

El algoritmo DV es un algoritmo de enrutamiento distribuido porque cada nodo mantiene un vector de estimaciones de costos (distancia) para todos los demás nodos de la red.

Una segunda forma amplia de clasificar los algoritmos de enrutamiento se basa en si el algoritmo es estático o dinámico.

Uno: algoritmo de enrutamiento del estado del enlace LS

En el algoritmo del estado del enlace, al permitir que cada nodo transmita paquetes de estado del enlace a todos los demás enrutadores, cada estado del enlace Un paquete contiene las características y costos de los enlaces que conecta, por lo que cada nodo de la red establece una topología sobre toda la red.

El algoritmo de Dijkstra calcula la ruta de menor costo desde el nodo de origen a todos los demás nodos de la red.

El algoritmo de Dijkstra es un algoritmo iterativo. Después de la k-ésima iteración del algoritmo. k se puede conocer La ruta de menor costo hacia cada nodo de destino.

Defina la siguiente notación:

D(V) A medida que el algoritmo avanza a través de esta iteración, el costo de la ruta de menor costo desde el nodo de origen al nodo de destino.

P(v) desde el nodo de origen hasta el nodo de destino v a lo largo del nodo anterior (vecino) de la ruta de menor costo actual.

N` subconjunto de nodos; si se ha encontrado la ruta de menor costo desde el nodo de origen al nodo de destino v, entonces v está en N`.

El algoritmo de enrutamiento global de Dijkstra consta de un paso de inicialización y un bucle. La cantidad de veces que se ejecuta el bucle es la misma que la cantidad de nodos en la red. Al final, el algoritmo calcula la ruta más corta desde el nodo de origen u hasta todos los demás nodos de la red.

Considerando la red de la figura, calcule la ruta de menor costo desde u a todos los destinos posibles.

.En la fase de inicialización, las rutas de menor costo actualmente conocidas desde u hasta sus vecinos directamente conectados v, x y w se inicializan en 2, 1 y 5 respectivamente. Los costos para y y z se establecen en infinito porque no están directamente conectados con u.

.En la primera iteración, debes verificar los nodos que no se han agregado al conjunto N` para encontrar el nodo con el costo más bajo al final de la iteración anterior. Ese nodo es x cuyo costo es 1, por lo que x se suma al conjunto N`. Luego, D(v) se actualiza para todos los nodos, lo que produce los resultados que se muestran en la fila 2 (paso) de la siguiente tabla. El costo del camino hacia v permanece sin cambios. Se determina que el costo del camino a través del nodo x al w es 4. Entonces, el nodo anterior a lo largo del camino más corto de u a w se establece en x. De manera similar, el costo para y vía x se calcula como 2 y la entrada se actualiza.

.En la segunda iteración, se encuentra que los nodos vey tienen la ruta 2 de menor costo. Elija arbitrariamente agregar y al conjunto N` de modo que N' contenga u, x e y. La actualización produce los resultados que se muestran en la fila 3 de la tabla.

.Y así sucesivamente...

Cuando finaliza el algoritmo LS, para cada nodo, se obtiene el nodo predecesor a lo largo de su ruta de menor costo desde el nodo de origen. Para cada predecesor A. El nodo sucesor tiene su nodo predecesor. De esta manera, se puede construir una ruta completa desde el nodo de origen hasta todos los nodos de destino.

Basado en la ruta más corta a partir de u, se puede construir la tabla de reenvío de un nodo (como el nodo u).

2. Algoritmo de enrutamiento por vector de distancia DV

El algoritmo LS es un algoritmo que utiliza información global, mientras que el algoritmo de vector de distancia es un algoritmo iterativo, asíncrono y distribuido.

Ecuación de Bellman-Ford:

Supongamos que dx(y) es el costo de la ruta de menor costo desde el nodo x al nodo y, entonces dx(y) = min {c(? x, v) dv(y) }

PD: El mínimo en la ecuación se refiere a tomar todos los vecinos de x.

El significado de la ecuación de Bellman-Ford es bastante intuitivo, lo que significa que el camino de menor costo desde el nodo x al y debe pasar por un vecino de x, y el costo de x para este vecino más el costo de este vecino para llegar al nodo de destino y La suma de costos es la más pequeña entre todos los caminos. De hecho, después de atravesar de x a v, si tomamos el camino de menor costo de v a y, el costo del camino será c (x, v) dv (y). Por lo tanto, debemos comenzar atravesando algunos vecinos v, y el costo mínimo de xay es el valor mínimo de c(x, v) dv(y) para todos los vecinos.

En el algoritmo DV, cuando el nodo x ve un cambio en el costo de su enlace conectado directamente o recibe una actualización del vector de distancia de un vecino, actualiza su tabla de vectores de distancia.

Comparación de tres algoritmos de enrutamiento LS y DV

Los algoritmos DV y LS utilizan diferentes métodos para resolver problemas de enrutamiento computacional.

En el algoritmo DV, cada nodo intercambia información solo con sus vecinos directamente conectados, pero proporciona a sus vecinos la ruta más baja posible desde sí mismo a todos los demás nodos de la red (que conoce). estimar.

En el algoritmo LS, cada nodo intercambia información (mediante transmisión) con todos los demás nodos, pero solo les dice el costo del enlace conectado directamente a él.

·Complejidad del mensaje:

El algoritmo LS requiere que cada nodo conozca el coste de cada enlace de la red y necesita enviar mensajes O(nE).

El algoritmo DV requiere el intercambio de mensajes entre dos vecinos conectados directamente en cada iteración. El tiempo necesario para la convergencia del algoritmo depende de muchos factores. Cuando el costo del enlace cambia, el algoritmo DV solo propaga el costo del enlace modificado si esto hace que cambie la ruta de menor costo al nodo.

·Velocidad del efecto:

El algoritmo DV converge lentamente y encontrará un bucle de enrutamiento durante la convergencia. El algoritmo DV también sufre el problema de contar hasta el infinito.

Robustez: En el algoritmo LS, si un router falla o se daña, el router transmitirá cargas incorrectas a sus enlaces conectados, provocando errores en toda la red.

Según el algoritmo Dv, en cada iteración, el resultado del cálculo de un nodo se pasará a sus vecinos y luego se pasará indirectamente a los vecinos del vecino en la siguiente iteración. En este caso, un resultado de cálculo incorrecto en el algoritmo DV también se propagará a toda la red.

4. Enrutamiento jerárquico

Dos razones conducen a una estrategia de enrutamiento jerárquico:

?Escala: a medida que aumenta el número de enrutadores, el cálculo de la información de enrutamiento y el almacenamiento y los gastos generales de comunicación aumentan gradualmente.

?Autonomía de gestión: en términos generales, una organización necesitará ejecutar enrutadores según sus propios deseos (como ejecutar un determinado algoritmo de enrutamiento de su elección) u ocultar los detalles de su red interna del exterior.

Las estrategias de enrutamiento jerárquico se implementan dividiendo los enrutadores en sistemas autónomos (AS).

Cada AS consta de un conjunto de enrutadores que normalmente están bajo el mismo control administrativo (por ejemplo, ser operados por el mismo ISP o pertenecer a la misma red corporativa). Todos los enrutadores dentro del mismo AS ejecutan el mismo algoritmo de enrutamiento.

El algoritmo de enrutamiento que se ejecuta dentro de un sistema autónomo se denomina protocolo de enrutamiento interno del sistema autónomo. Uno o más enrutadores en el borde de un AS son responsables de reenviar paquetes a destinos fuera del AS. Estos enrutadores se denominan enrutadores de puerta de enlace.

Entre los AS, los AS ejecutan el mismo protocolo de enrutamiento entre sistemas autónomo.