redes moviles

Encaminamiento en Redes Ad-Hoc
Departamento de Sistemas Telem´ticos y Computaci´n (GSyC)
a
o
gsyc-profes (arroba) gsyc.es

Noviembre de 2012

GSyC - 2012

Encaminamiento en Redes Ad-Hoc

1

c 2012 GSyC
Algunos derechos reservados.
Este trabajo se distribuye bajo la licencia
Creative Commons Attribution Share-Alike 3.0

GSyC - 2012

Encaminamiento en Redes Ad-Hoc

2Protocolos de encaminamiento para MANETs

Protocolos de encaminamiento para MANETs
Protocolos Reactivos vs Protocolos Proactivos
Reactivos (Bajo demanda): Buscan una ruta s´lo cuando se
o
necesita
Ej: AODV, DSR
Proactivos: Buscan rutas peri´dicamente, suponiendo que
o
ser´n utiles
a ´
Ej: OLSR
Enfoque reactivo suele implicar
Asumible latencia alta para el primer paquete
Aunque latopolog´ cambie,
ıa
una ruta individual vive cierto tiempo
Cierta independencia entre las rutas
El n´mero de rutas utiles es bajo frente a todas las posibles.
u
´
(Como solo usar´ algunas, busco esas cuando hacen falta, no
e
me esfuerzo en buscar todas las posibles)
GSyC - 2012

Encaminamiento en Redes Ad-Hoc

3

Protocolos de encaminamiento para MANETs

Enfoque proactivo sueleimplicar
Alguna variante de Estado del enlace
(foto completa del grafo, Dijkstra)
Exigencia de respuesta r´pida
a
La modificaci´n de una ruta puede afectar a cualquier nodo
o
El n´mero de rutas utiles es relativamente alto frente a todas
u
´
las posibles.
(Merece la pena buscar continuamente todas las posibles,
porque muchas ser´n utiles)
a ´
Tambi´n hay aproximaciones mixtas
e

GSyC -2012

Encaminamiento en Redes Ad-Hoc

4

Protocolos de encaminamiento para MANETs

Encaminamiento en Origen vs Encaminamiento Salto a
Salto

Encaminamiento Salto a Salto (Hop by Hop Routing)
Cada router decide s´lo el siguiente salto
o
La informaci´n de enrutado la guardan los routers
o
Encaminamiento en Origen (Source Routing)
La ruta se establece al enviar el paquete
Cadapaquete lleva incluida su ruta
La informaci´n de enrutado la guarda el paquete
o

GSyC - 2012

Encaminamiento en Redes Ad-Hoc

5

Protocolos de encaminamiento para MANETs

Protocolos para redes Ad-Hoc

Proactivos
Reactivos

Encaminamiento salto a salto
DSDV, OLSR, CGSR, WRP, TBRPF
AODV, LMR, TORA

Encaminamiento en origen
DSR, LQSR

Destacan
- AODV Ad-hoc On-Demand DistanceVector Routing.
Perkins, 1997
- DSR Dynamic Source Routing.
Johnson, Maltz 1998
- OLSR Optimized Link State Routing Protocol.
Clausen & Jacquet, 2003
Mantienen direccionamiento IP

GSyC - 2012

Encaminamiento en Redes Ad-Hoc

6

Protocolo AODV

Protocolo AODV

Bajo demanda
Encamina salto a salto
Vector de distancias:
Nadie tiene grafo completo
Para cada posible destino s´lose conoce el primer salto por
o
donde debe encaminarse y la distancia a la que se encuentra

Para distinguir la informaci´n moderna de la antigua, se
o
emplean horas l´gicas (Identificador de nodo, No de secuencia)
o
La hora l´gica es local, no hay reloj absoluto
o

GSyC - 2012

Encaminamiento en Redes Ad-Hoc

7

Protocolo AODV

Toda informaci´n en una tabla lleva la hora l´gicade quien la
o
o
gener´, ya que es posible que cierta informaci´n reci´n
o
o
e
recibida sea m´s antigua que otra recibida anteriormente
a
Toda informaci´n acaba caducando, t´
o
ıpicamente al cabo de
pocos segundos

GSyC - 2012

Encaminamiento en Redes Ad-Hoc

8

Protocolo AODV

Funcionamiento General
Cuando se necesita una ruta desde un origen (Source) hasta
un destino(Destination), se inunda la red con peticiones
RREQ (Route REQuest)
Cuando un RREQ llega al destino buscado, o a alguien que
conoce una ruta para el destino, se genera una respuesta
RREP (Route RREP)
El RREP sabe volver al origen porque la inundaci´n de RREQ
o
fue creando el camino de vuelta
Cuando el RREP va volviendo al origen, va creando el camino
de ida
Una vez que el origen ha...