Facultad de Ingeniería
Redes de Datos – Equipo 9
Protocolos de Enrutamiento
Arce Díaz Alejandra
Argüello González Omar Tonatiuh
Flores Aguilar Luis Floriberto
Pérez Medina Rodrigo
Velázquez Rodríguez Bianca Paola
Grupo 2
PROTOCOLOS DE
ENRUTAMIENTO
5.4 Protocolos de enrutamiento.
5.4.1 Algoritmos de Enrutamiento Estático.
5.4.1.1 Camino más corto.
5.4.1.2 Camino múltiple o bifurcado.
5.4.1.3 Centralizado.
5.4.1.4 Inundación.
5.4.2 Algoritmos de Enrutamiento Adaptativo.
5.4.2.1 Enrutamiento Distribuido.
5.4.2.2 Enrutamiento Óptimo.
5.4.2.3 Enrutamiento basado en Flujo.
5.4.2.4 Enrutamiento por difusión.
5.4.3 Aleatorio.
5.4.4 Híbridos.
INTRODUCCIÓN
ENCAMINAMIENTO
• Función de buscar un camino entre todos los
posibles en una red de paquetes cuyas topologías
poseen una gran conectividad.
OBJETIVO
• Mínimo costo
• Mínimo retardo
• Criterio administrativo
ALGORITMO DE ENCAMINAMIETO
Parte del software de la capa de red, responsable de
decidir sobre qué línea de salida se debe transmitir
un paquete que llega.
Corrección
Robustez
Equidad
Estabilidad
Simplicidad
Óptimo
5.4 Protocolos de enrutamiento.
5.4.1 Algoritmos de Enrutamiento Estático.
5.4.1.1 Camino más corto.
5.4.1.2 Camino múltiple o bifurcado.
5.4.1.3 Centralizado.
5.4.1.4 Inundación.
5.4.2 Algoritmos de Enrutamiento Adaptativo.
5.4.2.1 Enrutamiento Distribuido.
5.4.2.2 Enrutamiento Óptimo.
5.4.2.3 Enrutamiento basado en Flujo.
5.4.2.4 Enrutamiento por difusión.
5.4.3 Aleatorio.
5.4.4 Híbridos.
CAMINO MÁS CORTO
La idea consiste en construir un grafo de la subred, con
cada nodo representando una IMP y cada arco, una
línea de comunicación. Para escoger una ruta entre un
par de IMP dadas, el algoritmo solo determina el
camino más corto que existe entre ellos.
El camino más corto es una forma de medir la
longitud del camino. En el caso más general, las
etiquetas de los arcos se podrían calcular como
una función distinta, ancho de Banda, promedio
de tráfico, costo de comunicación, longitud
promedio de la cola de espera, retardo medido y
algunos otros factores.
• Se construye una gráfica de la red:
• Métricas
• Número de saltos
• Distancia en kilómetros
• Retardo medio
• Longitud promedio de la cola de espera
• Costo de comunicación
• Se calcula como una función entre todas las métricas
CAMINO MÚLTIPLE O BIFURCADO
• Con frecuencia, se puede obtener un mejor
rendimiento al dividir el tráfico entre varios caminos,
para reducir la carga en cada una de las líneas de
comunicación.
• Se aplica tanto en subredes con datagramas, como
en subredes con circuitos virtuales.
• Funcionamiento
Cada IMP mantiene una tabla con una ristra
reservada para cada uno de los posibles IMP
destinatarios; cada ristra ofrece la mejor, la segunda
mejor, la tercera mejor, etc. Línea de salida para este
destino en particular. Una de las ventajas del
encaminamiento es la posibilidad de poder transmitir
diferentes clases de tráfico sobre diferentes caminos.
5.4 Protocolos de enrutamiento.
5.4.1 Algoritmos de Enrutamiento Estático.
5.4.1.1 Camino más corto.
5.4.1.2 Camino múltiple o bifurcado.
5.4.1.3 Centralizado.
5.4.1.4 Inundación.
5.4.2 Algoritmos de Enrutamiento Adaptativo.
5.4.2.1 Enrutamiento Distribuido.
5.4.2.2 Enrutamiento Óptimo.
5.4.2.3 Enrutamiento basado en Flujo.
5.4.2.4 Enrutamiento por difusión.
5.4.3 Aleatorio.
5.4.4 Híbridos.
CENTRALIZADO
• Si la topología es de característica estática y él trafico
cambia muy rara vez, la construcción de las tablas de
encaminamiento es muy sencilla, y se realiza de una sola
vez, fuera de línea, cargándolas en los IMP
• Sin embargo, si los IMP y las líneas se desactivan y
después se restablecen, o bien, si el tráfico varia
violentamente durante todo el día, se necesitará algún
mecanismo para adaptar las tablas a las circunstancias
que imperan en este momento.
• Periódicamente, cada IMP transmite la información de su
estado al RCC. El RCC recoge toda esta información, y
después, con base en el conocimiento total de la red
completa, calcula las rutas optimas de todo los IMP a cada
uno de los IMP restantes, el encaminamiento centralizado
también tiene algunos serios, si no es que fatales,
inconvenientes. La vulnerabilidad del RCC es un problema
muy serio y para eso una solución es, tener una segunda
maquina disponible como respaldo
• También se necesitará establecer un método de arbitraje para
tener la seguridad de que el RCC primario y el de respaldo no
lleguen a entrar en conflicto para saber quien es el jefe
• Si el RCC calcula la ruta óptima para cada IMP, sin rutas
alternas, la pérdida de tan solo una línea o IMP, llegara a
desconectar algunos IMP del RCC, creando así terribles
consecuencias para el sistema
• Si el RCC utiliza rutas alternas, se debilitara el argumento a
favor de tener un RCC esto es el que pueda encontrar rutas
optimas
INUNDACIÓN
• Si un nodo recibe un paquete lo envía a todos sus
vecinos (menos a aquel que se lo ha enviado)
• Eventualmente múltiples copias llegarán al destino
• Necesitamos identificar cada paquete para distinguir
si un paquete lo hemos recibido ya o no. (Pero es
fácil, basta con poner un número de secuencia en el
paquete)
Problema:
• Los ciclos crean tráfico infinito
¿Cómo limitamos los el tráfico en los ciclos?
• Los nodos podrían recordar los paquetes que han reenviado y
no volver a reenviar de nuevo (Cuanto tiempo deben
recordarlos? Que problema hay si lo recuerdan mucho
tiempo?)
• Se puede incluir un numero máximo de saltos en cada
paquete e ir decrementando en cada salto
Propiedades de la inundación
• Todos los posibles caminos se prueban
o Muy robusto frente a fallos en nodos
o Estrategia indicada para envió de mensajes de alta
prioridad
• Al menos un paquete viaja por el camino más rápido
o Muy útil para establecer circuitos virtuales
• Todos los nodos son visitados
o Útil para distribuir información a múltiples destinos
(Broadcast y Multicast)
• Desventaja: mucho tráfico generado (incluso con limitaciones)
5.4 Protocolos de enrutamiento.
5.4.1 Algoritmos de Enrutamiento Estático.
5.4.1.1 Camino más corto.
5.4.1.2 Camino múltiple o bifurcado.
5.4.1.3 Centralizado.
5.4.1.4 Inundación.
5.4.2 Algoritmos de Enrutamiento Adaptativo.
5.4.2.1 Enrutamiento Distribuido.
5.4.2.2 Enrutamiento Óptimo.
5.4.2.3 Enrutamiento basado en Flujo.
5.4.2.4 Enrutamiento por difusión.
5.4.3 Aleatorio.
5.4.4 Híbridos.
Enrutamiento Distribuido
•
•
•
•
Son los más utilizados.
todos los nodos son iguales
todos envían y reciben información de control
todos calculan, a partir de su RIB sus tablas de
encaminamiento.
• Hay dos familias de procedimientos distribuidos:
 Vector de distancias.
 Estado de enlaces.
Vector de Distancia
• Determina la dirección y la distancia hacia cualquier
enlace de la red.
• Cada nodo informa a sus nodos vecinos de todas las
distancias conocidas por él, mediante vectores de
distancias
• El vector de distancias es un vector de longitud
variable que contiene un par por cada nodo
conocido por el nodo que lo envía. por ejemplo
(A:0;B:1;D:1)
• El nodo solo conoce la distancia a los distintos nodos
de la red pero no conoce la topología.
• Ejemplo:
• El vector de distancias de A sería:
• Con todos los vectores recibidos, cada nodo monta
su tabla de encaminamiento.
• Al final conoce qué nodo vecino tiene la menor
distancia al destino del paquete.
• los nodos no tienen información topológica de la red
completa, es decir, pueden conocer la distancia a
nodos lejanos, pero no donde están.
Ventajas:
• Muy sencillo.
• Muy robusto (gracias al envío periódico de
información)
• Consumo de memoria bajo: cada nodo sólo ha de
almacenar distancias con el resto de los nodos.
Desventajas :
• los vectores de distancia tardan en estabilizarse.
• Adaptabilidad a los cambios baja, ya que sólo sabe a
quién tiene que reenviar un paquete, pero no tiene
información de la topología.
• Consumo alto de capacidad: se transmiten vectores
cuyo tamaño es del orden del número de nodos de la
red pues cada nodo comunica a su vecino todas las
distancias que conoce
Estado de Enlace
• También llamado “Primero la Ruta Libre Mas Corta”
, recrea la topología exacta de toda la red.
• Es también un algoritmo de encaminamiento
distribuido e iterativo
• Cada nodo difunde a todos los demás nodos de la
red sus distancias con sus enlaces vecinos
• El nodo crea una base datos de la topología de la red
completa.
Su funcionamiento puede resumirse en cinco partes.
Cada nodo debe:
• 1. Descubrir a sus vecinos y aprender sus direcciones
de red.
• 2. Medir el coste a cada vecino.
• 3. Construir un paquete con esa información.
• 4. Enviar ese paquete a todos los nodos de la red.
• 5. Calcular el camino más corto a cada nodo.
Ventajas :
• Detección de errores más sencilla (si un estado de
enlace es infinito, significa que el nodo ha caído).
• Alta adaptabilidad a los cambios, ya que los nodos
tienen información de toda la red
• Menor consumo de capacidad: el tamaño del tráfico
enviado es siempre el mismo independientemente
del tamaño de la red.
Desventajas del método:
• Difusión.
• Consumo de memoria elevado: cada nodo
almacena toda la topología de la red.
Enrutamiento Optimo
• Principio de optimización.
• El conjunto de rutas optimas, procedentes de
todos los orígenes a un destino dato,
formando un árbol cuya raíz sale del destino.
• A este árbol se le llama árbol sumidero
• Cada paquete será entregado a través de un
número limitado finito de saltos.
5.4 Protocolos de enrutamiento.
5.4.1 Algoritmos de Enrutamiento Estático.
5.4.1.1 Camino más corto.
5.4.1.2 Camino múltiple o bifurcado.
5.4.1.3 Centralizado.
5.4.1.4 Inundación.
5.4.2 Algoritmos de Enrutamiento Adaptativo.
5.4.2.1 Enrutamiento Distribuido.
5.4.2.2 Enrutamiento Óptimo.
5.4.2.3 Enrutamiento basado en Flujo.
5.4.2.4 Enrutamiento por difusión.
5.4.3 Aleatorio.
5.4.4 Híbridos.
Encaminamiento basado en flujo
• Este encaminamiento busca una ruta alternativa, por donde el
tráfico sea menor, consiguiendo una ruta óptima.
• En muchas redes, la carga de tráfico entre dos nodos es
relativamente estable y predecible.
• Con una razonable aproximación, es posible analizar el flujo
de datos matemáticamente para optimizar en enrutamiento.
• La idea básica es que si para una línea, se conoce la capacidad
y el tráfico medio, entonces es posible calcular el retardo
medio de un paquete en esa línea, basándonos en la teoría de
colas.
• Una vez calculado el retardo medio de todas las líneas, es fácil
calcular una métrica basada en el peso y el flujo para
conseguir el retardo medio.
• El problema de enrutamiento se reduce entonces a encontrar
el algoritmo que genera el menor retardo.
Para poder utilizar esta técnica, es necesario conocer cierta
información:
•
•
•
•
•
Topología de la red
Matriz de tráfico
Capacidad de las líneas,en bps.
Longitud del paquete, en bits.
Elegir un algoritmo de enrutamiento.
• Para evaluar diferentes algoritmos de enrutamiento,
podemos repetir todo el proceso, cambiando solo los
flujos, y obtener un nuevo retardo medio.
• De esta forma obtendremos un número finito de
maneras de enrutar un paquete entre dos nodos. Por
tanto sólo quedará escoger el que genere el retardo
mínimo.
• En una cola M/M/1, la longitud media de la cola ( N ),
viene dada por:
Donde :
• λ : Es la tasa de llegada en pkt/sg
• µ : Es la tasa de salida en pkt/sg
• Conocida la relación de Little, obtenemos el
tiempo medio de espera en la cola:
• Siendo L la longitud del paquete en bits, y C la
capacidad de la línea en bps, obtenemos:
Enrutamiento por difusión
• El envío simultáneo de un paquete a todos los
destinos (broadcast).
Se han propuesto varios métodos para llevarla a cabo.
Enrutamiento directo
Un método de difusión es que el host envíe copias del
paquete a todos los destinos.
Este método desperdicia ancho de banda, sino que
también requiere que el origen tenga una lista
completa de todos los destinos.
Inundación
• La inundación es otro candidato pero el problema de
éste como técnica de difusión es el mismo que tiene
como algoritmo de enrutamiento punto a punto: genera
demasiados paquetes y consume demasiado ancho de
banda.
Enrutamiento multi destino
• Cada paquete contiene una lista de destinos que indican
los destinos deseados.
• El enrutador genera una copia nueva del paquete para
que cada línea de salida a usar, e incluye en cada paquete
sólo aquellos destinos que usan la línea.
• El grupo de destinos se divide entre las líneas de salida.
Árbol sumidero
• Árbol que forman el grupo de rutas óptimas hacia un
destino. Siendo la raíz del árbol el propio destino.
• Un árbol divergente no tiene porqué se único.
Árbol de expansión
Se envía el paquete a lo largo de un árbol que incluye todos los nodos
de la red.
• Para difundir datos desde el nodo n:
– El nodo n realiza una amplia difusión de los datos en todos los
arcos
– Otros nodos retardan los datos en los arcos de otros árboles
adyacentes
• El algoritmo nunca forma un ciclo, puesto que cada nuevo arco va a
un nuevo nodo
5.4 Protocolos de enrutamiento.
5.4.1 Algoritmos de Enrutamiento Estático.
5.4.1.1 Camino más corto.
5.4.1.2 Camino múltiple o bifurcado.
5.4.1.3 Centralizado.
5.4.1.4 Inundación.
5.4.2 Algoritmos de Enrutamiento Adaptativo.
5.4.2.1 Enrutamiento Distribuido.
5.4.2.2 Enrutamiento Óptimo.
5.4.2.3 Enrutamiento basado en Flujo.
5.4.2.4 Enrutamiento por difusión.
5.4.3 Aleatorio.
5.4.4 Híbridos.
Aleatorios
El paquete llegará al destino pero en un mayor tiempo que en el
de inundaciones.
 libera de cálculos para seleccionar el encaminamiento.
 La selección puede ser aleatoria o bien ir eligiendo uno cada
vez (Round Robin)
No requiere información de la red
Ventajas:
- muy simple
- poca carga (comparado con la inundación)
- visita un numero grande de nodos (aunque menos que la
inundación)
Desventajas:
- normalmente no llega por el camino mas corto
Puede seleccionar ruta de salida sobre la base de
cálculo de probabilidades
Gran retardo, poco seguro (seguridad de datos, espías)
y poco utilizado.
Híbrido
Utiliza vectores de distancia con métricas más precisas para
determinar las mejores rutas hacia las redes destino.
Utiliza menos recursos de ancho de banda, memoria
y ciclos del procesador.
Ejemplos de protocolos híbridos son IS-IS de OSI
(Sistema intermedio a Sistema intermedio)
y el protocolo EIGRP
(Protocolo de enrutamiento de gateway interior mejorado) de Cisco.
1) ¿Qué es un algoritmo de encaminamiento?
2) ¿Cuáles son los métodos de encaminamiento y explica cada uno?
3) Menciona los algoritmos de enrutamiento estático
4) Menciona los algoritmos de enrutamiento adaptativo (dinámico)
5) ¿Cuál es la diferencias entre camino mas corto y camino múltiple?
6) ¿En que consiste en encaminamiento aleatorio?
Si queda tiempo revisamos las respuestas
¿Qué es un algoritmo de encaminamiento?
Parte del software de la capa de red, responsable de decidir sobre qué línea de salida se debe
transmitir un paquete que llega.
¿Cuáles son los métodos de encaminamiento y explica cada uno?
DETERMINÍSTICOS O ESTÁTICOS. No tienen en cuenta el estado de la subred al tomar las
decisiones de encaminamiento. Las tablas de encaminamiento de los nodos se configuran de
forma manual y permanecen inalterables hasta que no se vuelve a actuar sobre ellas. Por
tanto, la adaptación en tiempo real a los cambios de las condiciones de la red es nula.
ADAPTATIVOS O DINÁMICOS. Pueden hacer más tolerantes a cambios en la subred tales
como variaciones en el tráfico, incremento del retardo o fallas en la topología. El
encaminamiento dinámico o adaptativo se puede clasificar a su vez en tres categorías,
dependiendo de donde se tomen las decisiones y del origen de la información intercambiada:
Adaptativo centralizado.
Adaptativo distribuido.
Adaptativo aislado.
Menciona los algoritmos de enrutamiento estático.
Camino más corto
Camino múltiple o bifurcado
Centralizado
Inundación
Menciona los algoritmos de enrutamiento adaptativo (dinámico).
Enrutamiento distribuido
Enrutamiento óptimo
Enrutamiento basado en Flujo
Enrutamiento por difusión
¿Cuál es la diferencias entre camino mas corto y camino múltiple?
En camino mas corto, la ruta entre dos nodos ya esta definida previamente en la tabla de
ruteo y simplemente se ordena la transmisión a través de ese camino a comparación de
camino múltiple que tenemos varias rutas a elegir teniendo así mayor opción para el
envío de paquetes.
¿En que consiste en encaminamiento aleatorio?
Consiste en que en cada nodo, se elegirá aleatoriamente el nodo al cuál se va a reenviar
el paquete. De esta forma, se puede asegurar que el paquete llegará al destino pero en
un mayor tiempo que en el de inundaciones. Pero el tránsito en la red es mucho menor,
esta técnica también libera de cálculos para seleccionar el encaminamiento.
Descargar

Diapositiva 1