algoritmos de enrutamiento

2016

Carlos Eduardo Gómez Montoya. M.Sc Luis Eduardo Sepúlveda Rodríguez. M.Sc

Redes de computadores II

Capa de Red

Algoritmos de Enrutamiento

1

Enrutamiento

2

• Es función de la capa de red enruta paquetes desde el nodo origen hasta el nodo destino.

• Generalmente se requieren varios saltos para alcanzar el destino, excepto cuando se trata del último salto.

| Capa de red | Algoritmos de enrutamiento |

Enrutamiento

3

• Los algoritmos de enrutamiento son la parte de software encargad0 de elegir la línea de salida por la cual un router transmitirá un paquete.

• En una red de datagramas esta decisión se toma cada vez que llega un paquete, dado que la mejor ruta puede haber cambiado desde la última vez.


Enrutamiento

4

• Un enrutador usa una tabla de enrutamiento y un algoritmo para calcular las rutas.

• Los algoritmos de enrutamiento se dividen en algoritmos estáticos y dinámicos.

• Los algoritmos de enrutamiento dinámico toman decisiones sobre las rutas con base en la topología actual o en estimaciones de tráfico, mientras que los algoritmos estáticos lo hacen por adelantado, fuera de línea y esta información es cargada en los enrutadores por anticipado.

• Los algoritmos de enrutamiento clásicos son:

• Inundación.

• Estado de enlace o LS (por sus siglas en inglés Link State).

• Vector de distancia o VD (por sus siglas en inglés Distance Vector).


Algoritmo de inundación

5

• Es un algoritmo estático en el cual cada paquete que se recibe por una línea de entrada es enviado por todas las líneas de salida, excepto aquella por la cual ha llegado el paquete.

• La inundación, genera grandes cantidades de paquetes duplicados en la red, a menos que se tomen medidas para controlar la duración de los paquetes (similar al TTL usado en el protocolo IP).

• La inundación no es práctica en la mayoría de las aplicaciones, sin embargo, se caracteriza por su robustez y la rapidez en alcanzar el destino.

| Capa de red | Algoritmos de enrutamiento | Algoritmo de inundación |

Estado de Enlace - Link State (Dijkstra)

6

• También llamado algoritmo de enrutamiento global, ya que el algoritmo tiene que ser consciente del costo de cada enlace de la red.

• Calcula la ruta de menor costo desde un nodo (el origen), a todos los demás nodos en la red.

• El algoritmo link state es iterativo y tiene la propiedad que después de la k-ésima iteración del algoritmo, las rutas de menor costo son conocidas a k nodos de destino, y entre las rutas de menor costo a todos los destinos, estás k rutas tendrán los k costos menores.

| Capa de red | Algoritmos de enrutamiento | Algoritmo Estado de Enlace |


7

A continuación, se define la siguiente notación:

• d(x): Es el valor de la ruta de menor costo desde el nodo origen hasta el nodo x, como resultado de una iteración del algoritmo.

• p(x) : Nodo anterior, vecino de x, a lo largo de la ruta de menor costo desde el origen hasta el nodo x.

• def: Es un subconjunto de nodos; x está en def si la ruta de menor costo del origen hasta x ya está definida completamente.



8

• El algoritmo de enrutamiento global consiste en un paso de inicialización seguido por un ciclo que se ejecuta n veces para una red de n nodos.

• Después de terminar, el algoritmo habrá calculado las rutas más cortas desde el nodo origen hasta cada uno de los otros nodos en la red.



9

• Como ejemplo, considere la siguiente figura y calcule las rutas de menor costo desde el nodo u (origen) hasta todos los posibles destinos en la red.



10

• En el paso de inicialización, las rutas de menor costo actualmente conocidas desde u hasta sus vecinos directamente conectados, v, x, w, son iniciados en 2, 1 y 5, respectivamente.



11

• Note que el costo hasta w, aunque es establecido en 5, no es el menor costo desde u hasta w.

• El costo hasta el nodo y, y hasta el nodo z se establecen en infinito porque ellos no están directamente conectados a u.



12

• En la primera iteración, se puede observar que el nodo de menor costo es x con un costo de 1.

• De este modo, x es agregado al conjunto def. Luego, se actualiza d(v) y p(v) para cada nodo, produciendo los resultados que se pueden ver en la siguiente tabla.



13

• El costo de la ruta desde u hasta v, no cambia.

• El costo de la ruta desde u hasta w, que era 5 al final del paso de inicialización, ahora es cambiado a 4 pasando a través de x.

• De forma similar, el costo de y, a través de x es calculado como 2 y la tabla es actualizada.



14

• En la siguiente iteración, el nodo v y el nodo y han encontrado que la ruta de menor costo es 2.

• Para resolver el empate, se escoge arbitrariamente y se adiciona el nodo elegido al conjunto def.

• En este caso, se ha elegido el nodo y, por lo que ahora el conjunto def ahora contiene los nodos u, x, y.



15

• El costo a los nodos restantes que aún no están en def, es decir, los nodos v, w, z, son actualizados y se produce el resultado de la siguiente tabla.



16

• Al realizar los pasos faltantes obtendremos la siguiente tabla.



17

• Cuando el algoritmo termina, cada nodo tiene su predecesor a lo largo de la ruta de menor costo, desde el nodo origen.

• Cada predecesor, también tiene su predecesor, por lo que de esta forma se puede construir la ruta completa.



18

• La tabla de reenvío de un nodo, por ejemplo, el nodo u, se puede construir con esta información, almacenando para cada nodo destino, el siguiente salto en la ruta de menor costo desde u hasta cada uno de los destinos.



19

• A continuación se muestran las rutas de costo mínimo y la tabla de reenvío para el nodo u.


Vector de Distancias - Distance Vector

20

• También conocido como Bellman-Ford.

• Es un algoritmo dinámico que se adapta a los cambios en la topología de la red.

• Cada router mantiene una tabla de enrutamiento en la cual hay una entrada por cada nodo destino en la red.

• En cada entrada es encuentra la línea de salida y una estimación de alguna métrica, por ejemplo la cantidad de saltos o el delay.

| Capa de red | Algoritmos de enrutamiento | Algoritmo Vector de distancias |


21

• Cada router conoce la distancia a sus vecinos directos.

• Cada nodo recibe de sus vecinos sus respectivas tablas de enrutamiento, las compara con la suya para calcular su nueva tabla de enrutamiento.

• La nueva tabla de enrutamiento calculada es compartida con los vecinos.



22

• La interacción entre los vecinos es realizada periódicamente hasta que haya estabilización en las tablas de enrutamiento de los diferentes routers.

• Considere una red con los siguientes enrutadores:



23

• Suponga que el enrutador J ha calculado las distancias (milisegundos) a los enrutadores vecinos así: desde J hasta A, 8 ms; desde J hasta I, 10 ms; desde J hasta H, 12 ms y desde J hasta K, 6 ms.

• También suponga que cada uno de los cuatro enrutadores vecinos ha enviado su tabla de enrutamiento, como se observa en la figura a continuación.



24

Con la información recibida, el enrutador J realiza los siguientes cálculos para actualizar su tabla de enrutamiento:

• Desde J hasta A, se usa el enlace directo entre ellos y el valor previamente calculado, es decir, 8 ms.

• Desde J hasta B, existen cuatro posibilidades:

• Si se va por A, se demora 12 ms, más los 8 ms que toma ir desde J hasta A, es decir, 20 ms.

• Si se va por I, se demora 36 ms, más los 10 ms que toma ir desde J hasta I, es decir, 46 ms.

• Si se va por H, se demora 31 ms, más los 12 ms que toma ir desde J hasta H, es decir, 43 ms.

• Finalmente, si se va por K, se demora 28 ms, más los 6 ms que toma ir desde J hasta K, es decir, 34 ms.



25

Luego, para ir desde J hasta B, se elige la ruta que va por A, con una distancia de 20 ms.

Para el cálculo de los siguientes destinos se procede de la misma forma.



26

Al final, se obtiene la siguiente tabla de enrutamiento para el enrutador J.


Nueva tabla de enrutamiento para JDestino Retardo Linea

A 8 AB 20 A

C 28 I

D 20 HE 17 I

F 30 IG 18 H

H 12 H

I 10 IJ 0 -

K 6 KL 15 K

algoritmos de enrutamiento

Documents