Download - Algoritmos de Enrutamiento
![Page 1: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/1.jpg)
ALGORITMOS DE ENRUTAMIENTO Lina Marcela Mejía M
![Page 2: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/2.jpg)
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.
![Page 3: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/3.jpg)
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.
![Page 4: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/4.jpg)
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.
![Page 5: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/5.jpg)
Conflicto entre equidad y optimidad
![Page 6: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/6.jpg)
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.
![Page 7: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/7.jpg)
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.
![Page 8: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/8.jpg)
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
![Page 9: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/9.jpg)
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.
![Page 10: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/10.jpg)
![Page 11: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/11.jpg)
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.
![Page 12: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/12.jpg)
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
![Page 13: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/13.jpg)
RUTA DE A - D
![Page 14: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/14.jpg)
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.
![Page 15: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/15.jpg)
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.
![Page 16: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/16.jpg)
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.
![Page 17: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/17.jpg)
![Page 18: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/18.jpg)
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.
![Page 19: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/19.jpg)
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
![Page 20: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/20.jpg)
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.
![Page 21: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/21.jpg)
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.
![Page 22: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/22.jpg)
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.
![Page 23: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/23.jpg)
4. DISTRIBUCIÓN DE LOS PAQUETES DE
ESTADO DEL ENLACE
Estructura de datos usada por el enrutador B
![Page 24: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/24.jpg)
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.
![Page 25: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/25.jpg)
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
![Page 26: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/26.jpg)
![Page 27: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/27.jpg)
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
![Page 28: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/28.jpg)
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.
![Page 29: Algoritmos de Enrutamiento](https://reader034.vdocumento.com/reader034/viewer/2022052223/557201e74979599169a2952a/html5/thumbnails/29.jpg)