PDF de programación - Encaminamiento en MANETs

SIMULACIÓN DE PROTOCOLOS DE ENRUTAMIENTO

PARA REDES MÓVILES AD-HOC MEDIANTE

HERRRAMIENTA DE SIMULACIÓN NS-3

Encaminamiento en MANETs

Outline

1. Conceptos generales de las redes ad hoc
2. Conceptos generales sobre protocolos de encaminamiento
3. Protocolos de enrutamiento

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

2

Mobile Ad Hoc Networks (MANETs)

Redes formadas por nodos móviles con conexión

inalámbrica.

Sin infraestructura previa
Las rutas contienen varios saltos
Las rutas varían en el tiempo
Problemas de particionamiento

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

Tipos de redes ad hoc

Entornos completamente simétricos.

• Todos los nodos tienen las mismas capacidades y

responsabilidades.

Entornos asimétricos. Pueden variar:

• los rangos de transmisión
• la duración de las baterías
• la capacidad de proceso
• la capacidad de proceso
• la velocidad de movimiento
• capacidad de enrutamiento
• Algunos nodos pueden tener mayores responsabilidades

(nodos lider)

• tecnologías inalámbricas (bit rate,..)

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

3

4

Variaciones en las redes ad hoc

Patrones de movilidad

• Gente esperando en el aeropuerto
• La red de taxis
• Movimientos militares
• Personal area network

Características de la movilidad

•
• Velocidad
• Predicción de movimientos
o Patrón de movimiento
o La dirección

• Uniformidad entre los nodos.

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

5

Conceptos generales sobre protocolos de

enrutamiento
enrutamiento

Conceptos generales sobre enrutamiento

Objetivo: Enviar los mensajes de un nodo a otro hasta

llegar al destino.
• ¿Cuál es el mejor camino?

o El más corto (menos nodos)
o El más rápido (menor retardo)
o Otros factores: baterías, ancho de banda…

• ¿Quién decide: la fuente o los nodos intermedios?
• ¿Quién decide: la fuente o los nodos intermedios?

o Source routing. (servicio áereo)

• La fuente decide el camino
• Los nodos intermedios reenvian el mensaje al siguiente nodo.

o hop-by-hop routing. (servicio correo)

• La fuente espeficica el destino en la cabecera del mensaje.
• Los nodos intermedios observan la dirección destino y consultan en sus

tablas de enrutamiento para seleccionar el siguiente salto.

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

Encaminamiento en redes ad hoc I

Características del enrutamiento en una MANET:

• Gran probabilidad de fallo en el enlace, lo que causa

frecuentes cambios de ruta.

• Topología dinámica (sin predicciones).
• Ancho de banda limitado.
• Cada dispositivo potencialmente puede comportarse como un

router.

• No hay administrador.
• No hay administrador.

Aparecen nuevos criterios de enrutamiento:

• Estabilidad de las rutas.
• Consumo de potencia.

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

7

8

Encaminamiento en redes ad hoc II

Se han propuesto muchos protocolos:

• Algunos específicos.
• Otros adaptados de las redes cableadas.

Ninguno funciona bien en todos los entornos.

Funciones de un protocolo de encaminamiento:

• Descubrimiento de la ruta:

o “Necesito hablar con Pepe, ¿donde está?”

• Mantenimiento de la rutas:

o “¿Dónde se fue Pepe?”
o “¿Dónde se fue el chico que sabía donde estaba Pepe?”

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

9

Descubrimiento y mantenimiento de las rutas

Dos filosofías básicas para el descubrimiento de rutas:

• Conocimiento de la topología de la red.
• Pregunta-respuesta.

Procedimientos para el mantenimiento de las rutas:

• Intercambio periódico de mensajes.
• Escucha de mensajes.
• Escucha de mensajes.
• Temporizadores.

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

10

Clasificación de los protocolos de enrutamiento MANET

Protocolos Proactivos

• Se mantiene en cada nodo información actualizada acerca de

la topología de red.

• Los tradicionales protocolos de estado de enlace y vector-

distancia son proactivos.

Protocolos reactivos

• Solamente se busca una ruta cuando se necesita.
• Solamente se busca una ruta cuando se necesita.

Protocolos híbridos

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

11

Características Protocolos Proactivos

Protocolos Proactivos

• Periódicamente envían información de las rutas, por ejemplo

cada T segundos.

• Se crean tablas de enrutamiento.
• Si T es demasiado grande, las rutas pueden quedar obsoletas,

y eso puede producir más retardo y pérdidas.

• Si T es demasiado pequeño, saturación de información de

control, también puede causar retardo y pérdidas.
control, también puede causar retardo y pérdidas.

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

12

Características Protocolos Reactivos

Protocolos reactivos

• Solamente se busca una ruta cuando se necesita.
• Se utiliza la ruta hasta que la comunicación finaliza.
• Se busca una nueva ruta cuando la anterior falla.

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

13

Características de los protocolos de enrutamiento

Tiempo de espera para el descubrimiento de una ruta

• Los protocolos proactivos tienen una latencia menor gracias al

conocimiento de la topología de la red que tiene cada nodo.

• Los protocolos reactivos tienen mayor latencia.

o Mayor retardo porque antes de transmitir hay que buscar la

ruta.

Información de control del descubrimiento y del

mantenimiento de la ruta.
mantenimiento de la ruta.
• Los protocolos reactivos pueden tener un overhead menor

porque buscan rutas únicamente cuando es necesario.

• Los protocolos proactivos pueden tener un overhead mayor

porque siempre están actualizando las rutas.

Qué solución adoptar depende del tipo de tráfico y del tipo

de movilidad.

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

14

Ejemplo de protocolos

http://en.wikipedia.org/wiki/List_of_ad-hoc_routing_protocols

Proactivos:

• OLSR – Optimized Link-State Routing

o RFC 3626.

• TBRF – Topology-Based Reserve Path Forwarding

o RFC 3684.

Reactivos:

• AODV - Ad hoc On-demand Distance Vector routing

o RFC 3561

• DSR – Dynamic Source Routing

o RFC 4728

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

15

Protocolos de enrutamiento

Protocolos de enrutamiento

Flooding controlado
DSR
AODV
OLSR

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

17

Flooding for Data Delivery

Sender S broadcasts data packet P to all its neighbors

Each node receiving P forwards P to its neighbors

Sequence numbers used to avoid the possibility of

forwarding the same packet more than once

Packet P reaches destination D provided that D is reachable

from sender S

Node D does not forward the packet

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

18

Flooding for Data Delivery

B

H

A

S

E

C
C

I

F

G

J

K

Represents a node that has received packet P

Y

Z

M
M

L
L

D

N

Represents that connected nodes are within each other’s transmission range

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

19

Flooding for Data Delivery

Broadcast transmission

B

H

A

S

E

C
C

I

F

G

J

K

Represents a node that receives packet P for the first time

Represents transmission of packet P

Y

Z

M
M

L
L

D

N

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

20

Flooding for Data Delivery

B

H

A

S

E

C
C

I

F

G

J

K

Y

Z

M
M

L
L

D

N

Node H receives packet P from two neighbors: potential for collision

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

21

Flooding for Data Delivery

B

H

A

S

E

C
C

I

F

G

J

K

Y

Z

M
M

L
L

D

N

Node C receives packet P from G and H, but does not forward
it again, because node C has already forwarded packet P once

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

22

Flooding for Data Delivery

• Nodes J and K both broadcast packet P to node D
• Since nodes J and K are hidden from each other, their

transmissions may collide

=> Packet P may not be delivered to node D

at all, despite the use of flooding

Y

Z
Z

B

H

A

S

E

C

I

F

G

J

K

M

L

D

N

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

23

Flooding for Data Delivery

B

H

A

S

E

C
C

I

F

G

J

K

Y

Z

M
M

L
L

D

N

Node D does not forward packet P, because node D is the intended
destination of packet P

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

24

Flooding for Data Delivery

• Flooding completed
• Nodes unreachable from S do not receive packet P (e.g., node Z)

B

H

A

S
S

E

C

I

F

G

J

K

Y

Z

M

L

D

N

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

25

Flooding for Data Delivery

• Flooding may deliver packets to too many nodes (in the worst
case, all nodes reachable from sender may receive the packet)

B

H

A

S
S

E
E

C

I

F

G

J

K

Y

Z

M

L

D

N

Simulación de Protocolos de
Enrutamiento para MANET con
ns-3

Loja - 2014

26

Ventajas del flooding

Sencillo
Robusta, porque la entrega de paquetes se puede realizar

por múltiples rutas.

Es más eficiente cuando la tasa de envio de paquetes de
información es más baja que el overhead de los procesos
de busqueda y mantenimiento de rutas.
• Por ejemplo en el caso de que los nodos transmitan pocos
mensajes de datos de tamaño pequeño y que