UNIVERSIDAD AUTNOMA DE COLOMBIA TRABAJO DE GRADO:

DISEO DE UNA INTERFAZ GRFICA PARA EL ANLISIS DE ALGORITMOS DE ENRUTAMIENTO UTLIZANDO EL PROTOCOLO

RIP v2, POR MEDIO DE LA PLATAFORMA JAVA.

ALGORITMOS DE ENRUTAMIENTO

ALGORITMOS DE ENRUTAMIENTO

La funcin 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 definicin sencilla de los algoritmos de enrutamiento es que son los encargados de decidir la lnea de salida y camino por la que se transmitir un paquete de informacin determinado en la capa de red. Estos algoritmos utilizan tablas en donde se encuentra la informacin de sus vecinos (otros equipos o puntos de la red) pesos de los caminos y otros datos de importancia para la red.

El enrutamiento es el proceso que consiste en tomar la decisin de cuales rutas utilizar para dirigir un paquete de informacin. 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 lnea de salida por la cual se enviar. Este proceso se conoce como reenvo. El otro proceso es responsable de llenar y actualizar las tablas de enrutamiento, es all donde entra en accin el algoritmo de enrutamiento.

A continuacin estudiaremos brevemente algunos algoritmos de enrutamiento y sus formas bsicas de funcionamiento. Los anteriores son:

Enrutamiento por la ruta ms corta.

Inundacin.

Enrutamiento por vector de distancia.

Enrutamiento por estado del enlace.

Enrutamiento jerrquico.

Enrutamiento por difusin.

Enrutamiento por multidifusin.

Enrutamiento para hosts mviles.

Enrutamiento en redes ad hoc.

Bsqueda en nodos de redes de igual a igual.

7.1.1 Enrutamiento por la ruta ms 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 lnea de comunicacin (con frecuencia llamada enlace). Para elegir una ruta entre un par dado de enrutadores, el algoritmo simplemente encuentra en el grafo la ruta ms corta entre ellos.

Ej. Algoritmo de Dijkstra.

7.1.2 Inundacin.

Este es un algoritmo de tipo esttico el cual consiste en que cada paquete de entrada se enva por cada una de las lneas de salida, excepto aquella por la que lleg (en forma de difusin (hacia todas las direcciones posibles desde un nodo)). Existe una variacin de la inundacin, llamada inundacin selectiva, que consiste en un algoritmo en el que los enrutadores no envan cada paquete de entrada por todas las lneas, sino solo por aquellas que van aproximadamente en la direccin correcta.

7.1.3 Enrutamiento por vector de distancia.

Este tipo de algoritmo de enrutamiento es dinmico, 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 lnea que se puede usar para llegar ah. Estas tablas se actualizan intercambiando informacin 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 lnea preferida de salida hacia ese destino y una estimacin del tiempo o distancia a ese destino.

7.1.4 Enrutamiento por estado del enlace.

Este tipo de enrutamiento es dinmico y es una evolucin 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 deberan cumplir cinco caractersticas especficas, estas son:

Descubrir a sus vecinos y conocer sus direcciones de red.

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

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

Enviar este paquete a todos los dems enrutadores.

Calcular la ruta ms corta a todos los dems enrutadores.

CARACTERISTICAS DE LOS ALGORITMOS DE ENRUTAMIENTO

Un algoritmo de enrutamiento debe tener en cuenta HO cinco caractersticas generales, debe ser ptimo, sencillo, robusto, de rpida convergencia y flexible.

ptimo. Hace referencia a la habilidad del algoritmo de seleccionar la mejor ruta, donde la mejor ruta depende de la mtrica que se use para calcularla. Cada protocolo define y sigue en forma estricta su algoritmo y su mtrica para clculos de rutas.

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

Robusto. Los algoritmos deben estar diseados para solucionar problemas imprevistos, especialmente cambios topolgicos por dao en los enlaces. Es necesario que trabajen de forma apropiada frente a sobrecargas en la red, as como de forma estable y adaptarse dinmica a las condiciones de la red.

Rpida 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 rpidamente y reaccionar con agilidad. Si el algoritmo posee una convergencia lenta generalmente produce loops y cadas de la red.

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

o Ancho de banda del canal. o Tamao de las colas del enrutador. o Retardos en la red.

Los algoritmos de enrutamiento pueden agruparse bsicamente en dos clases principales: no adaptivos y adaptivos.

GRFICA 1. CATEGORIAS DE LOS ALGORITMOS DE ENRUTAMIENTO

No adaptivos: Estos algoritmos no basan sus decisiones de enrutamiento en mediciones o estimaciones del trfico y la topologa actual, su decisin acerca de que ruta usar para llegar de un punto a otro, se toma por adelantado, fuera de lnea, y se carga en los enrutadores al arrancar la red. Este procedimiento se conoce como enrutamiento esttico.

Adaptivos: Estos algoritmos a diferencia de los anteriores cambian sus decisiones de enrutamiento para reflejar los cambios de topologa, trfico, entre otros cambios de la red.

Sin embargo, la clasificacin de los algoritmos de enrutamiento puede hacerse de la siguiente manera:

Dinmicos

Estticos

Single Path

Multi Path

Planos

Jerrquicos.

Inter-dominio

Intra-dominio

De estado de Enlace

De vector distancia.

A continuacin se dan unas tablas en donde se muestran las caractersticas de los diferentes algoritmos de enrutamiento.

Algoritmos Estticos

Algoritmos Dinmicos

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 dinmicos en la red.

Es muy simple de disear e implementar

Aplicada en redes pequeas, de diseo simple y con alto trfico.

Los sistemas estticos no operan bien en un ambiente de rpido crecimiento o cambios rpidos.

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 fsico de la topologa hace que todos los enrutadores de la red deban ser modificados manualmente.

Los errores de configuracin en las tablas estticas puede que no sean fciles de encontrar o arreglar.

Estos se adaptan en forma dinmica y en tiempo real a las distintas circunstancias de la red.

Utilizan informacin de actualizacin de recibidos.

El software de enrutamiento recalcula rutas y enva mensajes de actualizacin.

Los enrutadores se comunican entre si e intercambian informacin de enrutamiento.

Sus esquemas incorporan un nuevo cambio de la red por medio de adicin o retiro de las entradas en sus tablas de enrutamiento.

Estos algoritmos responden automticamente a la congestin de la red o cambios de la topologa fsica.

Existen dos tipos de algoritmos de enrutamiento dinmicos que calculan el camino al ms corto nodo destino. Uno esta basado en el concepto de vector distancia Distance Vector , el otro esta

basado en el estado del enlace Link State .

Todos los algoritmos usan mtricas para escoger el mejor camino a su destino. De acuerdo a cual de estos caminos posea la mtrica mas baja, para lo cual se usa:

Nmero de saltos.

Retardo en la transmisin.

La capacidad de la lnea.

Tabla 1. Algoritmo Esttico vs. Dinmico

Algoritmos Single

Path

Algoritmos Multi-

Path

Solo definen una ruta para comunicar un nodo origen con un nodo destino.

Soportan mltiples rutas entre un nodo fuente y un nodo destino.

Permiten distribuir y balancear el trfico entre las mltiples lneas.

Proveen a la red con caractersticas de mejor desempeo y mayor disponibilidad

Tabla 2. Algoritmo Single-Path vs. Multi-Path

Algoritmos Planos

Algoritmos Jerrquicos

Estos algoritmos estructuran a la red en forma plana.

Todos los nodos o enrutadores estn en el mismo nivel de jerarqua.

Todos intercambian informacin de enrutamiento.

Se establecen grupos jerrquicos alrededor del Backbone.

Designan grupos lgicos llamados dominios, sistemas autnomos o reas.

Algunos enrutadores pueden comunicarse entre dominios y otros solo en su dominio.

Se adapta a la estructura de la empresa.

Tabla 3. Algoritmo Plano vs. Jerrquico

Algoritmos Intra-dominio

Algoritmos Inter-dominio

Solo trabajan dentro de cada dominio.

Estn diseados para conectar dominios.

Tabla 4. Algoritmo Intra-dominio vs. Inter-dominio

Algoritmos de Estado de Enlace

Algoritmos de Vector Distancia

Cada enrutador enva a todos los nodos en la red informacin del estado de enlace con sus vecinos.

Los mensajes de actualizacin son pequeos pero se replican por toda la red.

Requieren ms maquina.

Tienen mejor convergencia.

En este tipo de algoritmo el enrutador debe conocer la topologa total de la red para calcular el camino mas 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 esta usando exactamente el mismo algoritmo de enrutamiento y la misma base de datos. Cada nodo tiene la informacin necesaria para calcular la ruta con el costo mnimo.

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 topologa 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 informacin errnea son fciles de detectar, porque cada uno mantiene una base de datos idntica.

Para redes muy grandes este sistema permite crear sistemas autnomos y el estado de la red es calculado solo para el sistema local.

Cada enrutador enva toda su tabla de enrutamiento (incluye a sus vecinos y a todos los nodos de la red que conozca)

Los mensajes de actualizacin son de gran tamao pero solo los enva a sus vecinos.

Requiere menos mquina.

Son un poco ms lentos.

Un problema es el de la transmisin de malas noticias por la red tales como la ruptura de un enlace o la desaparicin 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 mas 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.

Tabla 5. Algoritmo Estado de Enlace vs. Vector distancia

This document was created with Win2PDF available at http://www.win2pdf.com.The unregistered version of Win2PDF is for evaluation or non-commercial use only.This page will not be added after purchasing Win2PDF.