algoritmos de enrutamiento
TRANSCRIPT
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.
