Algoritmos Algoritmos de enrutamientode enrutamiento

Integrantes:Integrantes:

Edwin PeñarandaEdwin Peñaranda

Jimmy DarochaJimmy Darocha

Algoritmos Algoritmos de enrutamientode enrutamiento

La función principal de la capa de red es la de La función principal de la capa de red es la de enrutar paquetes de la máquina de origen a la enrutar paquetes de la máquina de origen a la máquina destino. máquina destino.

En la mayoría de las subredes los paquetes En la mayoría de las subredes los paquetes requerirán varias escalas para completar el viaje. requerirán varias escalas para completar el viaje.

El algoritmo de enrutamiento es aquella parte del El algoritmo de enrutamiento es aquella parte del software encargada de decidir la línea de salida software encargada de decidir la línea de salida por la que se transmitirá un paquete de entrada.por la que se transmitirá un paquete de entrada.

Algoritmos de enrutamientoAlgoritmos de enrutamiento

El algoritmo de enrutamiento debe ser capaz de El algoritmo de enrutamiento debe ser capaz de manejar los cambios de topología y tráfico sin manejar los cambios de topología y tráfico sin requerir el aborto de todas las actividades en requerir el aborto de todas las actividades en todos los hosts y el rearranque de la red con cada todos los hosts y el rearranque de la red con cada caida de un enrutador.caida de un enrutador.

Muchas redes intentan minimizar el número de Muchas redes intentan minimizar el número de escalas que tiene que hacer un paquete, puesto escalas que tiene que hacer un paquete, puesto que la reducción de la cantidad de escalas tiende a que la reducción de la cantidad de escalas tiende a reducir el retardo y también el consumo de ancho reducir el retardo y también el consumo de ancho de banda, lo que tiende a mejorar el rendimiento.de banda, lo que tiende a mejorar el rendimiento.

algoritmos de enrutamiento algoritmos de enrutamiento (estáticos) y (dinámicos).(estáticos) y (dinámicos).

Los algoritmos no adaptables basan sus decisiones Los algoritmos no adaptables basan sus decisiones de enrutamiento en La decisión de que ruta se usará de enrutamiento en La decisión de que ruta se usará para llegar de I a J (para todas las I y J) se calcula por para llegar de I a J (para todas las I y J) se calcula por adelantado fuera de línea, y se carga en los adelantado fuera de línea, y se carga en los enrutadores al iniciar la red. Este procedimiento se enrutadores al iniciar la red. Este procedimiento se llama enrutamiento estático.llama enrutamiento estático.

Los algoritmos adaptables, en contraste, cambian Los algoritmos adaptables, en contraste, cambian sus decisiones de enrutamiento para reflejar los sus decisiones de enrutamiento para reflejar los cambios de topología, y generalmente también el cambios de topología, y generalmente también el tráfico. tráfico.

Estos difieren en el lugar de obtención de su Estos difieren en el lugar de obtención de su información (por ejemplo, localmente, de los información (por ejemplo, localmente, de los enrutadores adyacentes o de todos los enrutadores), enrutadores adyacentes o de todos los enrutadores), el momento de cambio de sus rutas (por ejemplo, el momento de cambio de sus rutas (por ejemplo, cada variación de tiempo, cuando cambia la carga o cada variación de tiempo, cuando cambia la carga o cuando cambia la topología).cuando cambia la topología).

Principio de optimaciónPrincipio de optimación

Principio de optimaciónPrincipio de optimación

Es posible hacer un postulado general sobre las Es posible hacer un postulado general sobre las

rutas óptimas sin importar la topología o el tráfico rutas óptimas sin importar la topología o el tráfico de la red, llamado principio de óptimación y de la red, llamado principio de óptimación y establece que si el enrutador J está en la trayectoria establece que si el enrutador J está en la trayectoria

Óptima del enrutador I al enrutador K, entonces la Óptima del enrutador I al enrutador K, entonces la trayectoria óptima de J a K también esta en la misma trayectoria óptima de J a K también esta en la misma

ruta.ruta.

EnrutamientoEnrutamiento estáticoestático

Enrutamiento por la Enrutamiento por la trayectoria más cortatrayectoria más cortaEs una técnica de amplio uso sencilla y fácil de Es una técnica de amplio uso sencilla y fácil de entender. La idea es armar un grafo de la subred, en entender. La idea es armar un grafo de la subred, en el que cada nodo representa un enrutador y cada el que cada nodo representa un enrutador y cada arco del grafo una línea de comunicación (llamada arco del grafo una línea de comunicación (llamada con frecuencia enlace). Para escoger una ruta entre con frecuencia enlace). Para escoger una ruta entre un par dado de enrutadores el algoritmo un par dado de enrutadores el algoritmo simplemente encuentra en el grafo la trayectoria simplemente encuentra en el grafo la trayectoria más corta entre ellos.más corta entre ellos.

EnrutamientoEnrutamiento estático estático (camino más corto)(camino más corto)

Algoritmo estático Algoritmo estático (de inundación)(de inundación)

En este algoritmo cada paquete de entrada se envía En este algoritmo cada paquete de entrada se envía por cada una de las líneas de salida, excepto aquella por cada una de las líneas de salida, excepto aquella por la que llegó.por la que llegó.

Evidentemente se generan grandes cantidades de Evidentemente se generan grandes cantidades de paquetes duplicados; de hecho una cantidad infinita paquetes duplicados; de hecho una cantidad infinita a menos que se tomen medidas para limitar el a menos que se tomen medidas para limitar el proceso. Una de estas medidas puede ser un proceso. Una de estas medidas puede ser un contador de escalas contenido en la cabecera de contador de escalas contenido en la cabecera de cada paquete.cada paquete.

Idealmente el contador debe inicializarse a la Idealmente el contador debe inicializarse a la longitud de la trayectoria entre el origen y el longitud de la trayectoria entre el origen y el destino. Si el transmisor no conoce el tamaño de la destino. Si el transmisor no conoce el tamaño de la trayectoria, puede inicializarse el contador al peor trayectoria, puede inicializarse el contador al peor caso, es decir, el diámetro total de la subred.caso, es decir, el diámetro total de la subred.

Algoritmo estático Algoritmo estático (basado en flujo)(basado en flujo)

Los algoritmos estudiados hasta ahora sólo toman Los algoritmos estudiados hasta ahora sólo toman en cuenta la topología; no consideran la carga. Si por en cuenta la topología; no consideran la carga. Si por ejemplo, siempre hay una gran cantidad de tráfico ejemplo, siempre hay una gran cantidad de tráfico entre A y B en la figura anterior.entre A y B en la figura anterior.

Entonces podría ser mejor enrutar el tráfico de A a C Entonces podría ser mejor enrutar el tráfico de A a C a través de AGEFC, aun cuando esta trayectoria es a través de AGEFC, aun cuando esta trayectoria es mucho más larga que ABC. El algoritmo estático mucho más larga que ABC. El algoritmo estático toma en cuenta la topología como la carga para el toma en cuenta la topología como la carga para el enrutamiento. enrutamiento.

Algoritmo dinámico Algoritmo dinámico (por vector de distancia)(por vector de distancia)

Las computadoras modernas generalmente usan Las computadoras modernas generalmente usan algoritmos de enrutamiento dinámico en lugar de los algoritmos de enrutamiento dinámico en lugar de los estáticos antes descritos. En particular, dos estáticos antes descritos. En particular, dos algoritmos dinámicos, el enrutamiento por vector de algoritmos dinámicos, el enrutamiento por vector de distancia y el enrutamiento por estado de enlace son distancia y el enrutamiento por estado de enlace son los más comunes.los más comunes.

En éste algoritmo cada enrutador mantiene una En éste algoritmo cada enrutador mantiene una

tabla de enrutamiento indizada por, y conteniendo tabla de enrutamiento indizada por, y conteniendo un registro de, cada enrutador de la subred.un registro de, cada enrutador de la subred.

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

Algoritmo dinámico Algoritmo dinámico (por vector de distancia)(por vector de distancia)

Problema de conteo a infinitoProblema de conteo a infinito

El enrutamiento por vector a distancia funciona en El enrutamiento por vector a distancia funciona en

teoría, pero tiene un problema serio en la práctica; teoría, pero tiene un problema serio en la práctica; aunque converge en la respuesta correcta, puede aunque converge en la respuesta correcta, puede hacerlo lentamente. En particular, reacciona con hacerlo lentamente. En particular, reacciona con rapidez a las buenas noticias, pero con lentitud ante rapidez a las buenas noticias, pero con lentitud ante las malas.las malas.

Algoritmo dinámico Algoritmo dinámico (por estado de enlace)(por estado de enlace)

Este surgió como mejora del algoritmo de Este surgió como mejora del algoritmo de enrutamiento por vector de distancia. Hoy en día se enrutamiento por vector de distancia. Hoy en día se usan ampliamente variantes del enrutamiento por usan ampliamente variantes del enrutamiento por estado de enlace.estado de enlace.

Este enrutamiento se basa en cinco funciones:Este enrutamiento se basa en cinco funciones:

Descubrir a sus vecinos y conocer sus direcciones de Descubrir a sus vecinos y conocer sus direcciones de red.red.

Medir el retardo o costo para cada uno de sus Medir el retardo o costo para cada uno de sus vecinos.vecinos.

Construir un paquete que indique todo lo que acaba Construir un paquete que indique todo lo que acaba de aprender.de aprender.

Enviar este paquete a todos los demás enrutadores.Enviar este paquete a todos los demás enrutadores.

Calcular la trayectoria más cortaCalcular la trayectoria más corta

EnrutamientoEnrutamiento (jerárquico) (jerárquico)

A medida que crecen en tamaño las redes, crecen A medida que crecen en tamaño las redes, crecen proporcionalmente las tablas de enrutamiento del proporcionalmente las tablas de enrutamiento del enrutador. enrutador.

Las tablas que siempre crecen no sólo consumen Las tablas que siempre crecen no sólo consumen

memoria del enrutador, si no que también se memoria del enrutador, si no que también se necesita más tiempo de procesamiento para necesita más tiempo de procesamiento para examinarlas y más ancho de banda para enviar examinarlas y más ancho de banda para enviar informes de estado entre enrutadores.informes de estado entre enrutadores.

Llegará un punto en el que la red pueda crecer y ya Llegará un punto en el que la red pueda crecer y ya no ser factible que cada enrutador tenga una no ser factible que cada enrutador tenga una entrada para cada uno de los demás enrutadores, entrada para cada uno de los demás enrutadores, por lo que el enrutamiento tendrá que hacerse por lo que el enrutamiento tendrá que hacerse jerárquicamente, como ocurre en la red telefónica.jerárquicamente, como ocurre en la red telefónica.

Enrutamiento Enrutamiento (para hosts móviles)(para hosts móviles)

Hoy en día, millones de personas tienen Hoy en día, millones de personas tienen computadoras portátiles, y generalmente computadoras portátiles, y generalmente quieren leer su correo electrónico y acceder quieren leer su correo electrónico y acceder a sus sistemas de archivo normales desde a sus sistemas de archivo normales desde cualquier lugar del mundo. cualquier lugar del mundo.

Estos hosts móviles generan una nueva Estos hosts móviles generan una nueva complicación: para enrutar un paqueta a un complicación: para enrutar un paqueta a un hosts móvil, la red primero tiene que hosts móvil, la red primero tiene que encontrarlo. Este tema de incorporación de encontrarlo. Este tema de incorporación de hosts móvil en una red es muy nuevo.hosts móvil en una red es muy nuevo.

Enrutamiento Enrutamiento (por difusión)(por difusión)

En algunas aplicaciones, los hosts necesitan En algunas aplicaciones, los hosts necesitan enviar mensajes a varios otros hosts o a enviar mensajes a varios otros hosts o a todos los demás. Por ejemplo, el servidor de todos los demás. Por ejemplo, el servidor de distribución de informes ambientales, los distribución de informes ambientales, los programas de radio en vivo, podrían programas de radio en vivo, podrían funcionar mejor difundiendolos a todas las funcionar mejor difundiendolos a todas las máquinas y dejando que aquellas máquinas y dejando que aquellas interesadas lean los datos. interesadas lean los datos.

Enrutamiento Enrutamiento (por difusión)(por difusión)

Un método es que el origen simplemente envíe copias Un método es que el origen simplemente envíe copias del paquete a todos los destinos. Este método no sólo del paquete a todos los destinos. Este método no sólo desperdicia ancho de banda, si no que también requiere desperdicia ancho de banda, si no que también requiere que el origen tenga una lista completa de todos los que el origen tenga una lista completa de todos los

destinos.destinos. La inundación es otro candidato obvio. Aunque la La inundación es otro candidato obvio. Aunque la inundación es poco adecuada para la comunicación inundación es poco adecuada para la comunicación punto a punto ordinaria, para difusión puede merecer punto a punto ordinaria, para difusión puede merecer consideración seriaconsideración seria

Un tercer algoritmo es el enrutamiento multidestino. Un tercer algoritmo es el enrutamiento multidestino. Con este método cada paquete contiene una lista de Con este método cada paquete contiene una lista de destinos o un mapa de bits que indica los destinos destinos o un mapa de bits que indica los destinos deseados. Al llegar un paquete al enrutador, este revisa deseados. Al llegar un paquete al enrutador, este revisa todos los destinos para determinar el grupo de líneas todos los destinos para determinar el grupo de líneas de salida que necesitará.de salida que necesitará.

Enrutamiento Enrutamiento (por multitransmisión)(por multitransmisión)

En algunas aplicaciones, procesos muy separados En algunas aplicaciones, procesos muy separados trabajan juntos en grupos: por ejemplo, un grupo de trabajan juntos en grupos: por ejemplo, un grupo de procesos que implementa una base de datos distribuida. procesos que implementa una base de datos distribuida. Con frecuencia es necesario que un proceso envíe un Con frecuencia es necesario que un proceso envíe un mensaje a todos los demás miembros del grupo.mensaje a todos los demás miembros del grupo.

Lo que le concierne al algoritmo es que, cuando un Lo que le concierne al algoritmo es que, cuando un proceso se una a un grupo, informe a sus host del proceso se una a un grupo, informe a sus host del hecho. Los hosts deben informar a sus enrutadores de hecho. Los hosts deben informar a sus enrutadores de los cambios en los miembros del grupo. De cualquier los cambios en los miembros del grupo. De cualquier manera los enrutadores aprenden qué los hosts manera los enrutadores aprenden qué los hosts pertenecen a cuáles grupos.pertenecen a cuáles grupos.

Muchísimas gracias a todos Muchísimas gracias a todos los presenteslos presentes