PDF de programación - Capa Red - Algoritmos de Enrutamiento

Capa Red
Capa Red

Algoritmos de Enrutamiento
Algoritmos de Enrutamiento

Prof. Wílmer Pereira

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Servicios de redes
Servicios de redes

No Orientado Conexión vs Orientado Conexión
Por inestabilidad vs Calidad de servicio
no hay controles
IP

vs ATM



Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Principios de enrutamiento
Principios de enrutamiento

Encaminamiento de paquetes,
Encaminamiento de paquetes,

desde una línea de entrada a una de salida,
desde una línea de entrada a una de salida,
considerando cambios de topología y tráfico
considerando cambios de topología y tráfico

Tolerante a fallas (continua funcionando aún con caídas)
Estable (debe equilibrarse)
Justo y óptimo (i.e. equilibrio entre maximizar tasa
de transmisión y minimizar retardos)
Simplicidad
Estáticos o no adaptativos (inundación, ruta más corta, ...)
Dinámicos o adaptativos (vector distancia, estado del enlace, ...)
Importante es construir el árbol sumidero (sin ciclos)

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Enrutamiento por la ruta mas corta
Enrutamiento por la ruta mas corta

Métricas:
Métricas:

Saltos, Tiempo en colas de espera,
Saltos, Tiempo en colas de espera,
Tráfico, Velocidad de transmisión ...
Tráfico, Velocidad de transmisión ...

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Inundación
Inundación

Mucho ancho de banda

Colocar contador de saltos en el encabezado del paquete
y disminuir en cada router (inicializado al diámetro de la red)
Cada paquete lleva un número de secuencias y se evitan
duplicados
Inundación selectiva (debe conocer a priori algo de la topología)
Usar árbol expandido es una buena opción

Aplicaciones

Tolerancia a fallas
Modificación de bases de datos distribuidas en paralelo
Detección del camino óptimo para métrica

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Vector Distancia
Vector Distancia

(RIP)
(RIP)

Cada router con tabla de la mejor distancia al destino
Cada router con tabla de la mejor distancia al destino

por intercambio de información con sus vecinos inmediatos
por intercambio de información con sus vecinos inmediatos

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Problemas de Vector Distancia
Problemas de Vector Distancia

Problema de la cuenta hasta infinito:

Las buenas noticias se propagan bien y las malas muy lentamente

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Enrutamiento por estado del enlace
Enrutamiento por estado del enlace

(OSPF)
(OSPF)

(1) Descubrir a sus vecinos inmediato (HELLO o ping)
(2) Medir el retardo o costos a cada uno de esos vecinos (colas?)
(3) Construir un paquete que indique lo que acaba de aprender
(4) Enviar a todos los demás routers (inundación usando seq.)
(5) Cada router calcula la ruta más corta (Dijsktra)

La edad sirve para borrar entradas
de la tabla de enrutamiento. Esto
evita problema de números de
secuencia fuera de orden (caída

de router) o alterados

Problemas:
•Información incorrecta de las líneas
•Memoria de los routers agotada

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Enrutamiento Jerárquico
Enrutamiento Jerárquico

Debido al crecimiento de la red es conveniente jerarquizarla
Debido al crecimiento de la red es conveniente jerarquizarla

( sistema telefónico) en regiones, zonas, grupos, etc
( sistema telefónico) en regiones, zonas, grupos, etc

Ejemplo: red a 720 routers con tablas:

Sin jerarquía:
24 regiones de 30 routers:
8 zonas con 9 regiones a 10 routers:

720
30+23 = 53
10+8+7 = 25

Número de niveles óptimos es para n enrutadores ln n

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Estrategias por Difusion
Estrategias por Difusion

(1) Enviar a todos los destinos explícitamente (muy costoso)
(2) Política multidestino:

Cada paquete tiene una lista de los destinos
El router copia y envía por la línea que use alguno de los destinos
Después de muchos saltos, el paquete tendrá sólo un destino …

(3) Construir un árbol de expansión (se logra fácilmente con EE)

(4) Reenvío por ruta invertida

Al llegar paquete de difusión,

Si viene por el puerto de origen, reenviar a todas las salidas
Si viene por otro puerto diferente, suponer que es duplicado

Ventajas:

Sencillo
No requiere árbol de expansión ni lista de destino
No usa mecanismo de detención (contadores) como la inundación

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Enrutamiento por multidifusión
Enrutamiento por multidifusión

Difusión en grupos numéricamente grandes (no punto a punto)
Difusión en grupos numéricamente grandes (no punto a punto)

pero pequeños en comparación con la red (no difusión)
pero pequeños en comparación con la red (no difusión)

Como unirse a un grupo no compete al algoritmo de enrutamiento

Generar árboles expandidos de cada grupo y los almacena cada router

Muchos árboles por cada router

Construir un solo árbol de núcleo (la raíz es la mitad del grupo)

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Direccionamiento por multidifusión
Direccionamiento por multidifusión

28 bits para grupos => 250 millones de grupos

Hay grupos temporales y permanentes
224.0.0.1 Todos en la LAN
224.0.0.2 Todo router de la LAN
224.0.0.5 Todo router OSPF de la LAN
224.0.0.6 Todo router designado de la LAN

Cada host debe unirse explícitamente a cada grupo
Los router deben ser especiales. Cada minuto le pregunta
a los host de la LAN (224.0.0.1) a cuales grupos están
adscritos
Crea árboles de ruta invertida para cubrir todos los miembros
del grupo con su mejor esfuerzo (sin garantías)

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Enrutamiento con IP móvil
Enrutamiento con IP móvil

Tipos de nodos:

Estacionarios (fijos)
Migratorios (fijos móviles)
Ambulantes (en movimiento)

El área foránea puede ser una
LAN o una celda inalámbrica

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Algoritmo de IP móvil
Algoritmo de IP móvil

Periódicamente cada agente foráneo difunde un paquete.
Sin embargo también es posible que un móvil pregunte
por algún agente foráneo

El móvil se registra con el agente foráneo e intercambia
información de seguridad

El agente foráneo contacta al agente base e intercambia la
información de seguridad

El agente base indica al agente foráneo que proceda

El agente foráneo indica al móvil que está registrado

El enrutamiento puede hacerse pasando por el agente base aunque

es más eficiente que la comunicación sea directa entre nodos

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Enrutamiento ad hoc
Enrutamiento ad hoc

Nodos móviles y routers móviles ...
Nodos móviles y routers móviles ...

No hay topología fija ni vecinos conocidos ...
No hay topología fija ni vecinos conocidos ...

AODV (Vector distancia ad hoc bajo demanda)

Limitaciones:

B

A

Los enlaces pueden ser asimétricos
Estar en el radio de acción, no significa estar
conectado (interferencias)
Se envían paquetes de route request y route reply
Se calculan árboles sumideros



Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Descubrimiento de ruta en redes ad-hoc
Descubrimiento de ruta en redes ad-hoc

Solicitud de ruta (route request):
Se busca en la tabla de historia, si es duplicado descartar sino
agregar a la tabla de historia
Respuesta de ruta (route reply):
Si el receptor conoce el destino, le indica al solicitante que puede pasar
a través de él (si es más reciente es decir número de secuencia mayor)
Ruta desconocida:
Incrementa número de saltos y vuelve a difundir. Además aprovecha
esta información para construir el árbol sumidero.

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de la Información

Mantenimiento de ruta en redes ad hoc
Mantenimiento de ruta en redes ad hoc

En el camino de regreso se inspeccionan los paquetes y se actualizan las
tablas de enrutamiento local
Si no se conoce esa ruta
El número de secuencia mayor que la ruta conocida (más reciente)
La nueva ruta es más corta
Con el tiempo de vida se difunde menos y puede ser variable
Difunde periódicamente HELLO para ver vecinos activos

Route Request

Route Reply

Universidad Católica Andrés Bello

Prof. Wílmer Pereira

Diploma de Estudios Avanzados
en Gestión de la Comunicaciones
y Tecnología de l