algoritmos de enrutamiento

ALGORITMOS DE ENRUTAMIENTO Lina Marcela Mejía M

INTRODUCCIÓN

La función principal de la capa de red es enrutar

paquetes de la máquina de origen a la de destino.

El algoritmo de enrutamiento es aquella

parte del software de la capa de red encargada de

decidir la línea de salida por la que se

transmitirá un paquete de entrada.

Se puede considerar 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

ahí donde entra en acción el algoritmo de

enrutamiento.

Sin importar si las rutas para cada paquete se eligen

de manera independiente o sólo cuando se establecen

nuevas conexiones, hay ciertas propiedades que todo

algoritmo de enrutamiento debe poseer:

Exactitud

Sencillez

Robustez

Estabilidad

Equidad

Optimización.

Conflicto entre equidad y optimidad

El algoritmo de enrutamiento debe ser capaz de

manejar los cambios de topología y tráfico sin

requerir el aborto de todas las actividades en

todos los hosts y el reinicio de la red con cada

caída de un enrutador.

CLASE DE ALGORITMOS DE

ENRUTAMIENTO

Algoritmos no adaptables: No basan sus

decisiones de enrutamiento en mediciones o

estimaciones del tráfico ni en la topología.

Enrutamiento estáticos.

Algoritmos adaptables: contrarios a los

algoritmos no adaptables, éstos cambian sus

decisiones de enrutamiento para reflejar los

cambios de topología y de tráfico.

ALGORITMOS DE ENRUTAMIENTO

Principio de optimización

Enrutamiento por la ruta más corta

Enrutamiento por Inundación

Enrutamiento por vector de distancia

Enrutamiento por estado del enlace

Enrutamiento jerárquico

Enrutamiento por difusión

Enrutamiento por multidifusión

PRINCIPIO DE OPTIMIZACIÓN

Se busca tener una trayectoria optima para el

enrutador.

Árbol de descenso, donde la métrica de

distancia es el número de escalas. El árbol de

descenso puede no ser único, pueden existir otros

árboles con las mismas longitudes de trayectoria.

ENRUTAMIENTO POR LA RUTA MÁS

CORTA (DIJKSTRA)

La idea es 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).

La ruta más corta es la más rápida, en lugar de

la ruta con menos arcos o kilómetros.

La forma de medir la longitud de la red es usando

alguna métrica:

Número de saltos

Distancia física

Retraso de información por un paquete de

prueba

Ancho de banda

Trafico promedio

Costo de comunicación

RUTA DE A - D

INUNDACIÓN

Cada paquete que de entrada se envía por cada

una de las líneas de salida excepto por aquella

por la que llego. La inundación evidentemente

genera grandes cantidades de paquetes

duplicados; de hecho, una cantidad infinita a

menos que se tomen algunas medidas para

limitar el proceso.

Una de estas medidas es integrar un contador de

saltos en el encabezado de cada paquete, que

disminuya con cada salto, y el paquete se

descarte cuando el contador llegue a cero.

ENRUTAMIENTO POR VECTOR DE

DISTANCIA

Los algoritmos de enrutamiento por vector de

distancia operan 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.

PROBLEMA DE LA CUENTA HASTA INFINITO

propagación de las buenas noticias, considere la

subred de cinco nodos (lineal), en donde la

métrica de retardo es el número de saltos.

ENRUTAMIENTO POR ESTADO DEL

ENLACE

El enrutamiento por vector de distancia fue

remplazado por el enrutamiento por estado del

enlace. Debido a dos problemas

La métrica de retardo era la longitud de la

cola, no tomaba en cuenta el ancho de banda

al escoger rutas.

El algoritmo con frecuencia tardaba

demasiado en converger (el problema de la

cuenta hasta el infinito).

Puede enunciarse en cinco partes

1. CONOCIMIENTO DE LOS VECINOS

Averigua quiénes son sus vecinos con el

paquete HELLO.

Considerar LAN como otro nodo (N),

conectados A, C y F.

2. MEDICIÓN DEL COSTO DE LA LÍNEA

Se mide el tiempo de ida y vuelta que demora el

ECHO y lo divide entre dos, el enrutador

transmisor puede tener una idea razonable del

retardo. Se realizan varias pruebas para

promediar y así tener mejor resultado.

3. CONSTRUCCIÓN DE LOS PAQUETES

DE ESTADO DEL ENLACE

Construirlos periódicamente, a intervalos

regulares. Otra posibilidad es al ocurrir un

evento significativo, como la caída o reactivación

de una línea o de un vecino, o el cambio

apreciable de sus propiedades.

4. DISTRIBUCIÓN DE LOS PAQUETES DE

ESTADO DEL ENLACE

Estructura de datos usada por el enrutador B

5. CÁLCULO DE LAS NUEVAS RUTAS

Una vez que un enrutador ha acumulado un grupo

completo de paquetes de estado del enlace, puede

construir el grafo de la subred completa porque todos

los enlaces están representados. De hecho, cada

enlace se representa dos veces, una para cada

dirección. Los dos valores pueden promediarse o

usarse por separado.

Ahora puede ejecutar localmente el algoritmo de

Dijkstra para construir la ruta más corta a todos los

destinos posibles. Los resultados de este algoritmo

pueden instalarse en las tablas de enrutamiento, y la

operación normal puede reiniciarse.

ENRUTAMIENTO JERÁRQUICO

A medida que crece el tamaño de las redes,

crecen proporcionalmente las tablas de

enrutamiento del enrutador. Consumen:

Memoria del enrutador

Tiempo CPU para examinarlas

Ancho de banda para enviar informes

Niveles para una subred N enrutadores es de

lnN

ENRUTAMIENTO POR DIFUSIÓN

El envío simultáneo de un paquete a todos los

destinos se llama difusión.

El árbol de expansión es un subgrupo de la

subred que incluye todos los enrutadores pero no

contiene ciclos

ENRUTAMIENTO POR MULTIDIFUSIÓN

Enviar mensajes a grupos definidos de tamaño

numéricamente grande, pero pequeños en

comparación con la totalidad de la red.

Cuando un proceso envía un paquete de

multidifusión a un grupo, el primer enrutador

examina su árbol de expansión y lo recorta,

eliminando todas las líneas que conduzcan a

hosts que no sean miembros del grupo.