ALGORITMOS DE ENRUTAMIENTO

UNIVERSIDAD AUTONOMA DEL ESTADO DE MEXICO

CENTRO UNIVERSITARIO ATLACOMULCO

INGENIERIA EN COMPUTACION

INTERCONEXIÓN DE REDES

TAREA #2

ALGORITMOS DE ENRUTAMIENTO

LIC.ELIZABETH EVANGELISTA

YABIN GONZAGA LOPEZ

8° SEMESTRE

ICO – 14

ALGORITMOS DE ENRUTAMIENTO

La función principal de la capa de red es enrutar paquetes de un punto a otro (de un equipo a otro), y esta utiliza algoritmos que eligen las rutas por donde transitan los diferentes paquetes, así como las estructuras de datos que usan estos, estos anteriores se conocen como algoritmos de enrutamiento.

Una definición sencilla de los algoritmos de enrutamiento es que son los encargados de decidir la línea de salida y camino por la que se transmitirá un paquete de información determinado en la capa de red. Estos algoritmos utilizan tablas en donde se encuentra la información de sus vecinos (otros equipos o puntos de la red) pesos de los caminos y otros datos de importancia para la red.

El enrutamiento esel proceso que consiste en tomar la decisión de cuales rutas utilizar para dirigir un paquete de información. Se puede considerar entonces que un enrutador realiza dos procesos internos. Uno de ellos maneja cada paquete conforme llega, buscando en las tablas de enrutamiento la línea de salida por la cual se enviará. Este proceso se conoce como reenvío. El otro proceso es responsable de llenar y actualizar las tablas de enrutamiento, es allí donde entra en acción el algoritmo de enrutamiento.

A continuación algunos algoritmos de enrutamiento y sus formas básicas de funcionamiento. Los anteriores son:

·         Enrutamiento por la ruta más corta.

·         Inundación.

·         Enrutamiento por vector de distancia.

·         Enrutamiento por estado del enlace.

·         Enrutamiento jerárquico.

·         Enrutamiento por difusión.

·         Enrutamiento por multidifusión.

·         Enrutamiento para hosts móviles.

·         Enrutamiento en redes ad hoc.

·         Búsqueda en nodos de redes de igual a igual.

Enrutamiento por la ruta más corta.

Esta forma de enrutamiento consiste en armar un grafo de la subred, en el que cada nodo representa un enrutador y cada arco del grafo una línea de comunicación (con frecuencia llamada enlace). Para elegir una ruta entre un par dado de enrutadores, el algoritmo simplemente encuentra en el grafo la ruta más corta entre ellos.

Ej. Algoritmo de Dijkstra.

 Inundación.

Este es un algoritmo de tipo estático el cual consiste en que cada paquete de entrada se envía por cada una de las líneas de salida, excepto aquella por la que llegó (en forma de difusión (hacia todas las direcciones posibles desde un nodo)).

Existe una variación de la inundación, llamada inundación selectiva, que consiste en un algoritmo en el que los enrutadores no envían cada paquete de entrada por todas las líneas, sino solo por aquellas que van aproximadamente en la dirección correcta.

Enrutamiento por vector de distancia.

Este tipo de algoritmo de enrutamiento es dinámico, el cual opera haciendo que cada enrutador mantenga una tabla (es decir, un vector) que da la mejor distancia conocida a cada destino y la línea que se puede usar para llegar ahí. Estas tablas se actualizan intercambiando información con los vecinos. Cada enrutador mantiene 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 una estimación del tiempo o distancia a ese destino.

Enrutamiento por estado del enlace.

Este tipo de enrutamiento es dinámico y es una evolución del enrutamiento por vector de distancia puesto que el anterior tiene un bajo rendimiento y falencias respecto a los retardos, ancho de banda entre otros, dado lo anterior se modelo un algoritmo en donde los enrutadores deberían cumplir cinco características específicas, estas son:

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

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

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

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

5.      Calcular la ruta más corta a todos los demás enrutadores.

CARACTERISTICASDELOS ALGORITMOS DE ENRUTAMIENTO

Un algoritmo de enrutamiento debe tener en cuenta HO cinco características generales, debe ser óptimo, sencillo, robusto, de rápida convergencia y flexible.

Óptimo. Hace referencia a la habilidad del algoritmo de seleccionar la mejor ruta, donde la mejor ruta depende de la métrica que se use para calcularla. Cada protocolo define y sigue en forma estricta su algoritmo y su métrica para cálculos de rutas.

Sencillez. Los algoritmos de enrutamiento debe ser definidos de la forma más sencilla posible, esta sencillez es realmente importante cuando éste se desarrolla en software. El software debe ser eficiente y funcional, también es necesario tener en cuenta que el tiempo de procesamiento en cada nodo debe ser lo más corto posible.

Robusto. Los algoritmos deben estar diseñados para solucionar problemas imprevistos, especialmente cambios topológicos por daño en los enlaces. Es necesario que trabajen de forma apropiada frente a sobrecargas en la red, así como de forma estable y adaptarse dinámica a las condiciones de la red.

Rápida convergencia. La convergencia en un algoritmo se dicta por la rapidez con la cual los enrutadores (router) establecen sus rutas y de una manera estable. Ante los cambios o problemas en la red, el algoritmo debe percatarse rápidamente y reaccionar con agilidad. Si el algoritmo posee una convergencia lenta generalmente produce loops y caídas de la red.

Flexibles. Los algoritmo se deben acomodar de una forma rápida y eficiente a una gran variedad de eventos en la red, como:

Ø  Ancho de banda del canal.

Ø  Tamaño de las colas del enrutador.

Ø  Retardos en la red.

Los algoritmos de enrutamiento pueden agruparse básicamente en dos clases principales: no adaptivos y adaptivos.

CATEGORIAS DE LOS ALGORITMOS DE ENRUTAMIENTO

No adaptivos: Estos algoritmos no basan sus decisiones de enrutamiento en mediciones o estimaciones del tráfico y la topología actual, su decisión acerca de que ruta usar para llegar de un punto a otro, se toma por adelantado, fuera de línea, y se carga en los enrutadores al arrancar la red. Este procedimiento se conoce como enrutamiento estático.

Adaptivos: Estos algoritmos a diferencia de los anteriores cambian sus decisiones de enrutamiento para reflejar los cambios de topología, tráfico, entre otros cambios de la red.

Sin embargo, la clasificación de los algoritmos de enrutamiento puede hacerse de la siguiente manera:

v  Dinámicos Estáticos

v  Single Path Multi Path

v  Planos Jerárquicos.

v  Inter-dominio Intra-dominio

v  De estado de Enlace De vector distancia.

CARACTERÍSTICAS DE LOS DIFERENTES ALGORITMOS DE ENRUTAMIENTO.

	Algoritmo Estático vs. Dinámico
Algoritmos Estáticos  Las tablas de enrutamiento son establecidas por el administrador de la red. Estas solo se modifican por el administrador de la red y no se adaptan a cambios dinámicos en la red. Es muy simple de diseñar e implementar Aplicada en redes pequeñas, de diseño simple y con alto tráfico. Los sistemas estáticos no operan bien en un ambiente de rápido crecimiento o cambios rápidos. Las tablas de enrutamiento no responden completamente en caso de fallas, ya que los enrutadores de respaldo usan los recursos del dispositivo o de red con problemas. Un cambio físico de la topología hace que todos los enrutadores de la red deban ser modificados manualmente. Los errores de configuración en las tablas estáticas puede que no sean fáciles de encontrar o arreglar.		Algoritmos Dinámicos Estos se adaptan en forma dinámica y en tiempo real a las distintas circunstancias de la red. Utilizan información de actualización de recibidos. El software de enrutamiento recalcula rutas y envía mensajes de actualización. Los enrutadores se comunican entre si e intercambian información de enrutamiento. Sus esquemas incorporan un nuevo cambio de la red por medio de adición o retiro de las entradas en sus tablas de enrutamiento. Estos algoritmos responden automáticamente a la congestión de la red o cambios de la topología física. Existen dos tipos de algoritmos de enrutamiento dinámicos que calculan el camino al más corto nodo destino. Uno está basado en el concepto de vector distancia Vector, el otro está basado en el estado del enlace Link State . Todos los algoritmos usan métricas para escoger el mejor  camino a su destino. De acuerdo a cual de estos caminos posea la métrica más baja, para lo cual se usa: A.      Número de saltos. B.      Retardo en la transmisión. C.      La capacidad de la línea.

Algoritmo Single Path vs. Multi Path
	Algoritmos Single Path  Solo definen una ruta para comunicar un nodo origen con un nodo destino. Soportan múltiples rutas entre un nodo fuente y un nodo destino.	Algoritmos Multi- Path Permiten distribuir y balancear el tráfico entre las múltiples líneas. Proveen a la red con características de mejor  desempeño y mayor disponibilidad

Algoritmo Plano vs. Jerárquico
Algoritmos Planos Estos algoritmos estructuran a la red en forma plana. Todos los nodos o enrutadores están en el mismo nivel de jerarquía. Todos intercambian información de enrutamiento.	Algoritmos Jerárquicos Se establecen grupos jerárquicos alrededor del Backbone. Designan grupos lógicos llamados dominios, sistemas autónomos o áreas. Algunos enrutadores pueden comunicarse entre dominios y otros solo en su dominio. Se adapta a la estructura de la empresa.

Algoritmo Intra dominio vs. Inter dominio
	Algoritmos Intra-dominio Solo trabajan dentro de cada dominio.	Algoritmos Inter-dominio Están diseñados para conectar dominios.

Algoritmo Estado de Enlace vs. Vector distancia

Algoritmos de Estado de Enlace Cada enrutador envía a todos los nodos en la red información del estado de enlace con  sus vecinos. Los mensajes de actualización son pequeños pero se replican por toda la red. Requieren más máquina. Tienen mejor convergencia. En este tipo de algoritmo el enrutador debe conocer la topología total de la red para calcular el camino más corto a cada una de las redes de destino. Cada enrutador hace un Broadcast a cada uno de los otros enrutadores de la red. Estos mensajes contienen el estado de cada uno de los enlaces directamente conectados a cada puerto. Las rutas son consistentes, porque cada nodo está usando exactamente el mismo algoritmo de enrutamiento y la misma base de  atos. Cada nodo tiene la información necesaria para calcular la ruta con el costo mínimo. Usa excesiva cantidad de memoria y sobrecarga de comunicaciones es requerida para que redes grandes puedan trabajar. Ya que cada enrutador debe mantener una base de datos conteniendo el total de la topología de la red. Este algoritmo requiere una gran cantidad de tiempo de CPU. Cada enrutador mantiene una vista consciente de la red eliminando el problema de los ciclos y convergencia lenta. Enrutadores con información errónea son fáciles de detectar, porque cada uno mantiene una base de datos idéntica. Para redes muy grandes este sistema permite crear sistemas autónomos y el estado de la red es calculado solo para el sistema local.

Algoritmos de Vector Distancia Cada enrutador envía toda su tabla de enrutamiento (incluye a sus vecinos y a todos los nodos de la red que conozca) Los mensajes de actualización son de gran tamaño pero solo los envía a sus vecinos. Requiere menos máquina, son un poco  más lentos. Un problema es el de la transmisión de malas noticias por la red tales como la ruptura de un enlace o la desaparición de un nodo. Este algoritmo converge lentamente en estos casos. Aunque el principal inconveniente de este algoritmo es el de la cuenta a infinito. El problema más frecuente en este tipo de algoritmo es la cuenta a infinito, donde se hace que los costes o distancias se incrementen indefinidamente sin que el algoritmo llegue a converger nunca.