algoritmos de enrutamiento

© 2006 Cisco Systems, Inc. All rights reserved. Cisco ConfidentialBSCI 8 - 5 1

ALGORITMOS DE ENRUTAMIENTO Router

Es un dispositivo que se encarga de mover paquetes de datos de una red a otra (pueden ser entre redes LAN o WAN o una combinación de ambas). En dicho dispositivo se implementa el algoritmo de enrutamiento

El algoritmo de enrutamiento decide la interfaz por la que sale el paquete

RouterEntradas Salidas

Tabla deenrutamiento

Motor deenrutamiento


ALGORITMOS DE ENRUTAMIENTO 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 transmitirá el paquete de entrada. Los paquetes de datos simplemente siguen la ruta previamente establecida.

Existen ciertas propiedades que resulta deseable tener en un algoritmo de encaminamiento:

Corrección

Simplicidad

Robustez

Estabilidad

Justicia

Optimalidad


Existen 3 tipos básicos de arquitectura de los protocolos de enrutamiento:

1) Protocolos de enrutamiento de distancia vectorial: Algoritmos sencillos que calculan un valor de distancia

acumulativa entre enrutadores basándose en la cuenta de saltos.

2) Protocolos de enrutamiento de estado del enlace: Algoritmos sofísticados que mantienen una compleja base

de datos de la topología de red.

3) Protocolos de enrutamiento híbridos: Una combinación de los métodos de distancia vectorial y

de estado del enlace que intenta incorporar las ventajas de ambos y minimizar sus desventajas.

PROTOCOLOS DE ENRUTAMIENTO

• 6) Manual de CISCO - Tom Shaughnessy con Toby Velte / traducción de la primera versión en inglés / McGraw Hill / Madrid España 2002 / ISBN: 84-481-2727-7


En este algoritmo (conocido también como Bellman-Ford) los ruteadores pasan sus tablas de enrutamiento a sus vecinos inmediatos en todas direcciones.

En cada intercambio, el enrutador incrementa el valor de la distancia recibida para una ruta, aplicando así su propio valor a esa ruta.

La tabla actualizada se pasa después al exterior donde los ruteadores receptores repiten el proceso.

RUTEADORES- DISTANCIA VECTORIAL



Cada ruteador no necesita conocer todo lo relativo a otros enlaces, sólo si están allí y cuál es la distancia aproximada hasta ellos.

Se actualizan cada X tiempo definido previamente (p. e. 30 segs.), por lo que no se puede saber el estado de los enlaces hasta que se hacen las actualizaciones.

De lo anterior se ve que es lento de converger. Es susceptible a caer en bucles de enrutamiento. La mayoría de ellos están limitados a 16 saltos y

se utilizan en redes de menos de 50 ruteadores. Los protocolos más utilizados son RIP e IGRP.

RUTEADORES- DISTANCIA VECTORIAL



Ruteadores- Distancia Vectorial



También es conocido como SPF (Shortest Path First – Primero el Camino Más Corto).

Se basan en el estado de los enlaces de red que forman las rutas.

El enrutamiento de estado del enlace lo administran los eventos.

Siempre que cambia el estado de un enlace, los ruteadores intercambian una actualización de enrutamiento denominada LSA (Link State Advertisement – Aviso del Estado del Enlace).

RUTEADORES- ESTADO DEL ENLACE



Cuando un ruteador recibe una LSA, se utiliza el algoritmo del estado del enlace para recalcular la ruta más corta hacia los destinos afectados

Este protocolo de enrutamiento intenta conocer siempre en todo momento la topología de la red, mediante la actualización, siempre que sucede un cambio.

Los cálculos del estado del enlace se basan en el algoritmo de Dijkstra (el cual también se conoce como el algoritmo SPF).




Con este algoritmo se obtienen rutas nuevas, en vez de aplicar simplemente nuevos valores distancia a las rutas ya conocidas.

Las nuevas rutas calculadas por SPF se introducen en la tabla de enrutamiento actualizada.

Estas entradas incluyen valores recalculados de todas las métricas configuradas para utilizarlas en la implementación del estado del enlace.

Las métricas posibles son costo, retardo, ancho de banda, fiabilidad y otras.




Los protocolos de enrutamiento híbrido utilizan métricas de distancia vectorial más precisas en un protocolo diseñado para converger rápidamente.

Existe un estándar abierto para este protocolo.

Existe otra versión propietaria de CISCO que se llama EIGRP (Enhanced Interior Gateway Routing Protocol – Protocolo de Enrutamiento de Pasarela Interior Mejorada).

RUTEADORES- HÍBRIDOS



CLASIFICACIÓN DE LOS ALGORITMOS DE RUTEO

Según información global o descentralizada?

Global: Todos los routers tienen la

topología completa y costos de enlaces

Algoritmo “estado de enlace” Descentralizada: El router conoce a sus vecinos

conectados físicamente y su costo del enlace a ellos.

Proceso iterativo de cómputo e intercambio de información con sus vecinos

Algoritmo “vector de distancia”

Según si es estático o dinámico?

Estático: routes cambian lentamente

en el tiempoDinámico: routes cambia más

rápidamente–Actualizaciones periódicas–En respuesta a cambios de costos de enlaces


ALGORITMO DE RUTEO DE ESTADO DE ENLACE

Algoritmo de Dijkstra Conoce topología de red y

costos de enlaces conocidos a todos los nodos

–Se logra vía “difusión de estado de enlace”

–Todos los nodos tienen la misma información

Se calcula el camino de costo menor desde un nodo (fuente) a todos los otros

–Entrega la tabla de re-envío para ese nodo

iterativo: después de k iteraciones, conoce camino de menor costo a k destinos

Notación: c(x,y): costo del enlace

desde nodo x a y; = ∞ si no es vecino directo

D(v): valor actual del costo del camino desde fuente a destino v.

p(v): nodo predecesor a v en el camino de fuente a v.

N': conjunto de nodos cuyo camino de costo mínimo ya se conoce


Algoritmo de Dijsktra Notación:D(v): Coste del camino

con menor coste desde el nodo fuente al nodo destino v.

P(v): Nodo previo (vecino v) a lo largo del actual camino con menor coste desde el nodo fuente v.

N’: Subgrupo de nodos, v esta en N’ si el camino con menor coste desde el nodo fuente es conocido.


ALGORITMO VECTOR DE DISTANCIA (1)

Ecuación de Bellman-Ford (programación dinámica)Define

dx(y) := costo del camino de menor costo de x a y

Entonces:

dx(y) = min {c(x,v) + dv(y) }

v es vecino de x

Donde min es tomado sobre todos los vecinos v de x



Dx(y) = costo mínimo estimado de x a y

Vector de distancia: Dx = [Dx(y): y є N ]

Nodo x conoce el costo a cada vecino v: c(x,v)

Nodo x mantiene Dx = [Dx(y): y є N ]

Nodo x también mantiene los vectores de distancia de sus vecinos

–Para cada vecino v, x mantiene Dv = [Dv(y): y є N ]



Idea básica: Cada nodo envía periódicamente su vector de

distancia estimado a sus vecinos Cuando el nodo x recibe un nuevo DV estimado

desde un vecino, éste actualiza su propio DV usando la ecuación de B-F:

Dx(y) ← minv{c(x,v) + Dv(y)} para cada nodo y ∊ N

Bajo condiciones naturales, el valor estimado de Dx(y) converge al menor costo real dx(y)



Iterativo y asincrónico: cada iteración local es causada por: Cambio en costo de enlace local Actualización de DV por mensaje de vecino

Distribuido: Cada nodo notifica a sus vecinos sólo cuando su DV cambia

–Vecinos entonces notifican a sus vecinos si es necesario


Ejemplo: Vector de distancia


Ruteo Jerárquico

En cierto momento la red puede crecer hasta el punto en que ya no es factible que cada enrutador tenga una entrada para cada uno de los demás enrutadores, por lo que el enrutamiento tendrá que hacerse jerárquicamente, como ocurre en la red telefónica.

Al usarse el enrutamiento jerárquico, los enrutadores se dividen en lo que llamaremos regiones, donde cada enrutador conoce todos los detalles de la manera de enrutar paquetes a destinos dentro de su propia región, pero no sabe nada de la estructura interna de las otra regiones.


Ruteo Jerárquico


FinAlgoritmos de RuteoAlgoritmos de Ruteo

algoritmos de enrutamiento

Documents