Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Son útiles en situaciones de emergencia, como:
Desastres naturales.
Conflictos bélicos.
Requieren de muy poca configuración y permiten un despliegue rápido.
El protocolo de encaminamiento dinámico permite que entren en funcionamiento en un tiempo muy reducido.
Redes Ad Hoc y Redes Mesh
Ruiz Pedro. Introducción y estado del arte en redes Ad Hoc. 2003
Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Por su aplicación pueden clasificarse como:
Redes Móviles Ad Hoc (MANETs)
Redes Inalámbricas Mesh
Redes de Sensores.
Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Redes Móviles Ad Hoc (MANETs):
MANET (Mobile and Ad hoc NETworks) (Redes móviles sin cables) son redes formadas por nodos móviles. Se comunican sin cables y lo hacen de manera 'ad hoc'. En este tipo de redes, los protocolos de enrutamiento tienen que ser diferentes de los utilizados en redes fijas.
Un ejemplo de estas redes son las redes VANET.
Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Redes Móviles Ad Hoc (MANETs)
http://monet.postech.ac.kr/research.html
Redes VANET:
Las VANET (Vehicular Ad-Hoc Network, Red Ad Hoc de vehículos ) son un subconjunto de las redes móviles ad-hoc capaces de comunicar información entre diversos vehículos colindantes y el sistema de tráfico (roadside equipment, equipo de carretera).
Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Redes Inalámbricas Mesh:
Las Redes Inalámbricas Mesh (WMN, Wireless Mesh Network ) consisten en dos tipos de nodos los enrutadores y los clientes, donde los enrutadores tienen movilidad mínima y forman el backbone de las WMNs.
Estas redes pueden integrarse mediante funciones gateway y de puente con redes como Internet, IEEE 802.11, IEEE 802.15, IEEE 802.16, etc.
Los clientes pueden ser estáticos o móviles y pueden crear una red mallada entre ellos mismos o con los enrutadores.
Rubio Lluis. Redes mesh basadas en puntos de acceso inteligentes 802.11 open source. 2005
Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Redes Inalámbricas Mesh:
Rubio Lluis. Redes mesh basadas en puntos de acceso inteligentes 802.11 open source. 2005
Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Redes Inalámbricas Mesh:
Las redes Mesh o malladas resuelven los dos problemas principales que se presentan cuando se quiere desplegar una red en un área densamente poblada:
1) La interferencia resultante de usar espectro libre.
2) La necesidad de que todas las estaciones de usuario tengan línea de vista con la estación base.
Sebastian Buettrich, wire.less.dk. Adaptado por Ermanno Pietrosemoli, Javier Triviño, Fundación EsLaRed
Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Redes Inalámbricas Mesh:
Sebastian Buettrich, wire.less.dk. Adaptado por Ermanno Pietrosemoli, Javier Triviño, Fundación EsLaRed
Las redes Mesh resultan mucho más estables ya que pueden seguir funcionando aunque caiga un nodo.
Mejoran el rendimiento
de las redes ad-hoc.
Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Redes Inalámbricas Mesh:
Sebastian Buettrich, wire.less.dk. Adaptado por Ermanno Pietrosemoli, Javier Triviño, Fundación EsLaRed
Los nodos tienen un grado variable de conexión, con algunos nodos conectados a muchos nodos y otros en los extremos con una sola conexión.
Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Redes de Sensores
Las redes de sensores están formadas por un grupo de sensores con ciertas capacidades sensitivas y de comunicación inalámbrica los cuales permiten formar redes ad hoc sin infraestructura física preestablecida ni administración central.
http://zone.ni.com/devzone/cda/tut/p/id/9507
Redes Ad Hoc y Redes Mesh
Redes Ad Hoc
Redes de Sensores
http://zone.ni.com/devzone/cda/tut/p/id/9507
Protocolos de Enrutamiento en Redes MANET.
http://www.grc.upv.es/calafate/download/main_novatica.pdf
Las características de las Redes Ad Hoc impiden la utilización de protocolos de enrutamiento desarrollados para redes cableadas.
Es necesario superar los problemas tales como topología dinámica, recursos de ancho de banda y batería limitada y seguridad reducida.
Debido al interés por las redes Ad Hoc se ha establecido dentro del IETF (Internet Engineering Task Force, Grupo de Tareas de Ingeniería de Internet) un nuevo grupo de trabajo denominado Mobile Ad Hoc Networking group (MANET), cuyo principal objetivo es estimular la investigación en el área de las Redes Ad
Hoc.
Protocolos de Enrutamiento en Redes MANET.
http://www.grc.upv.es/calafate/download/main_novatica.pdf
Existen cerca de 60 propuestas de enrutamiento diferentes. Solamente cuatro de estas propuestas han resistido la fuerte competencia. Los protocolos:
AODV (Ad Hoc On Demand Distance Vector).
DSR (Dynamic Source Routing for Protocol Mobile Ad hoc Networks).
OLSR (Optimized Link State Routing Protocol).
TBRPF (Topology Broadcast based on Reverse-Path Forwarding).
Los protocolos AODV y OLSR han alcanzado el nivel de RFC (Request for Comment)
Protocolos de Enrutamiento en Redes MANET.
Red con Nodos
Objetivo:
Transferencia de mensajes de un nodo a otro.
Cual es el "mejor" camino?
Quien decide – fuente o nodos intermedios?
Protocolos de Enrutamiento en Redes MANET.
Departamento de Sistemas Telemáticos y Computación (GSyC). Universidad Rey Juan Carlos. 2005
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
Protocolos Proactivos (basados en tablas)
Determinan las rutas independientemente del modelo de tráfico
Buscan rutas periódicamente, suponiendo que serán útiles
Ejemplo: OLSR.
Protocolos Reactivos (por demanda)
Buscan y mantienen las rutas solamente si es necesario
Ejemplo: AODV, DSR
Protocolos de Enrutamiento en Redes MANET.
Aspectos a tener en consideración
Tiempo de espera para el descubrimiento de la ruta:
Los protocolos proactivos normalmente tienen una latencia menor gracias al uso de caches.
Los protocolos reactivos pueden tener mayor latencia.
Una ruta entre A y B es establecida solo si A intenta transmitir a B.
Overhead del descubrimiento y del mantenimiento de la ruta:
Los protocolos reactivos pueden tener un overhead menor por que buscan las rutas únicamente cuando es necesario.
Los protocolos proactivos pueden tener un overhead mayor por que siempre están actualizando las rutas.
Protocolos de Enrutamiento en Redes MANET.
Protocolos Unicast
DSR (Dynamic Source Routing, Fuente de enrutamiento dinámico)
AODV (Ad hoc On-demand Distance Vector, Protocolo de enrutamiento a demanda ad hoc del vector distancia )
OLSR (On-demand Link State Routing, Protocolo de enrutamiento de estado de enlace optimizado)
ZRP (Zone Routing Protocols, Protocolo de enrutamiento de la zona)
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
Uso del flooding para la entrega de datos
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
Uso del flooding para la entrega de datos
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
Uso del flooding para la entrega de datos
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
Uso del flooding para la entrega de datos
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
Uso del flooding para la entrega de datos
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
Uso del flooding para la entrega de datos
Protocolos de Enrutamiento en Redes MANET.
Uso del flooding para la entrega de datos
Muchos protocolos utilizan el flooding (limitado) de los paquetes del control, en vez de los paquetes de los datos.
Los paquetes de control se utilizan para descubrir las rutas.
Las rutas establecidas se utilizan posteriormente para enviar los paquetes de datos.
Protocolos de Enrutamiento en Redes MANET.
Uso del flooding para la entrega de datos
Ventajas
Sencillo
Es más eficiente si la tasa de envío es baja. El overhead de los procesos de búsqueda y mantenimiento de rutas explicitas resulte ser más alto.
Ejemplo: en el caso que los nodos transmitan pocos mensajes de tamaño pequeño y que la topología varíe muy a menudo
Potencialmente la entrega de los datos es más fiable, por que se pueden utilizar múltiples rutas.
Protocolos de Enrutamiento en Redes MANET.
Uso del flooding para la entrega de datos
Desventajas
Overhead potencialmente muy alto o en el peor de los casos todos los nodos alcanzable por el nodo fuente recibirán los datos.
Potencialmente la entrega de los datos es menos fiable a causa del uso de difusiones.
-Flooding usa transmisión broadcast y es muy difícil implementar un broadcast fiable sin incrementar la sobrecarga
– Broadcasting en IEEE 802.11 MAC es no fiable
– En nuestro ejemplo los nodos J y K podrían transmitir al nodo D simultáneamente, resultando en una pérdida del paquete.
Protocolos de Enrutamiento en Redes MANET.
DSR (Dynamic Source Routing, Fuente de enrutamiento dinámico)
Redes de tamaño medio (200 nodos), admite altas velocidades
Cuando el nodo S desea enviar un paquete al nodo D, pero no tiene una ruta hacia D, inicia un descubrimiento de la ruta (route discovery).
El nodo fuente S hace un flooding Route Request (RREQ)
Cada nodo añade su propio identificador cuando reenvía un RREQ.
Uso del "send buffer"
Uso de RREQ identifier
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
DSR (Dynamic Source Routing)
Uso del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
DSR (Dynamic Source Routing)
Uso del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
DSR (Dynamic Source Routing)
Uso del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
DSR (Dynamic Source Routing)
Uso del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
DSR (Dynamic Source Routing)
Uso del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
DSR (Dynamic Source Routing)
Uso del Route Reply
Protocolos de Enrutamiento en Redes MANET.
DSR (Dynamic Source Routing)
Uso del Route Reply
El Route Reply puede ser enviado invirtiendo la ruta en el Route Request (RREQ) solo si tenemos la garantía que los enlaces sean bi-direccionales o Para garantizarlo el RREQ es reenviado solo si se recibe desde un enlace que sabemos ser bi-direccional.
Si se permiten enlaces unidireccionales (asimétricos) entonces el RREP tiene que utilizar un route discovery desde D hacia S o A menos que D ya tenga una ruta hacia S.
El uso del estándar IEEE 802.11 para enviar datos implica que los canales son bi-direccionales (por que se utilizan los ACKs)
Protocolos de Enrutamiento en Redes MANET.
DSR (Dynamic Source Routing)
Cuando el nodo S recibe el RREP, memoriza en cache la ruta.
Cuando el nodo S envía un paquete de datos a D, la ruta está incluida en la cabecera o por eso el nombre de source routing.
Los nodos intermedio utilizan solo y únicamente la ruta incluida en la cabecera para saber a quien tienen que reenviar el paquete.
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
DSR (Dynamic Source Routing)
Data Delivery in DSR
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
DSR (Dynamic Source Routing)
Optimizaciones de DSR: Route Caching
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
DSR (Dynamic Source Routing)
Optimizaciones de DSR: Route Caching
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
DSR (Dynamic Source Routing)
Route Error (RERR)
Protocolos de Enrutamiento en Redes MANET.
DSR (Dynamic Source Routing)
Ventajas y Desventajas
Se gestionan solo las rutas entre nodos que quieren comunicarse o se reduce la carga para mantener varias rutas.
El uso de la cache puede reducir la carga de futuros procesos de route discovery
Un solo proceso de RR puede producir variar rutas hacia el destino gracias a las respuestas de las caches de los nodos intermedios.
Protocolos de Enrutamiento en Redes MANET.
DSR (Dynamic Source Routing)
Ventajas y Desventajas
El tamaño de la cabecera crece al crecer de la ruta debido al uso del source routing
El flooding de las peticiones de ruta puede potencialmente alcanzar todos los nodos en la red.
Hay que evitar las colisiones producidas por la retransmisión de los RREQ.
Aumento de la contienda para el acceso al canal si se producen demasiadas RR por nodos que usan sus caches.
Un nodo intermedio puede corromper las caches de otros nodos enviando RREP utilizando una cache obsoleta.
Protocolos de Enrutamiento en Redes MANET.
AODV (Ad hoc On-demand Distance Vector, Protocolo de enrutamiento a demanda ad hoc del vector distancia )
El DSR incluye el encaminamiento fuente en la cabecera de los paquetes. Si el tamaño de los paquetes resultantes es muy grande puede afectar a las prestaciones, sobre todo si los paquetes de datos son pequeños.
AODV intenta mejorar DSR utilizando tablas de encaminamiento en los nodos de forma que los paquetes no tengan que llevar información sobre la ruta.
AODV mantiene la característica del DSR que las rutas son mantenidas solo para los nodos que quieren comunicar.
Protocolos de Enrutamiento en Redes MANET.
AODV (Ad hoc On-demand Distance Vector)
Los mensajes de Route Requests (RREQ) son reenviados de manera similar a DSR.
Cuando un nodo retransmite un Route Request, activa también una ruta inversa que apunta a la fuente (AODV supone canales bidireccionales).
Cuando el destino recibe el Route Request, responde enviando un Route Reply
El Route Reply recorre la ruta activada a través del envío del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
AODV (Ad hoc On-demand Distance Vector)
Envió del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
AODV (Ad hoc On-demand Distance Vector)
Envió del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
AODV (Ad hoc On-demand Distance Vector)
Envió del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
AODV (Ad hoc On-demand Distance Vector)
Envió del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
AODV (Ad hoc On-demand Distance Vector)
Envió del Route Request
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
AODV (Ad hoc On-demand Distance Vector)
Envio del Route Reply
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
AODV (Ad hoc On-demand Distance Vector)
Setup del la ruta de envío
Protocolos de Enrutamiento en Redes MANET.
AODV (Ad hoc On-demand Distance Vector)
Temporizadores
Una entrada en la tabla de rutas que mantiene un camino inverso se elimina después de un periodo de tiempo
Una entrada en la tabla de rutas que mantiene un camino directo se elimina si no está siendo usada durante un intervalo de tiempo igual o mayor a active_route_timeout
– La entrada se eliminaría incluso si continua siendo válida
Protocolos de Enrutamiento en Redes MANET.
AODV (Ad hoc On-demand Distance Vector)
Detalles sobre el uso del route reply
Un nodo intermedio (no el destino final) puede también enviar un Route Reply (RREP) si conoce una ruta más reciente que la que "se sabe" el sender S.
Para determinar si la ruta conocida por un nodo intermedio es más reciente se utilizan los destination sequence numbers
-Si Node:dsn >= RREQ:dsn no reenvio
La probabilidad que un nodo intermedio envíe un Route Reply es inferior en AODV que en DSR
Protocolos de Enrutamiento en Redes MANET.
AODV (Ad hoc On-demand Distance Vector)
Notificación sobre interrupción de enlaces
Un nodo vecino de X se considera activo para una entrada de la tabla de encaminamiento si este vecino ha enviado un paquete dentro de el intervalo active_route_timeout .
Cuando un enlace 1-hop en una tabla de encaminamiento se interrumpe, se avisan a todos los vecinos activos.
Las interrupciones de enlaces se propagan utilizando los mensajes de Route Error, que también sirven para actualizar los destination sequence numbers.
Protocolos de Enrutamiento en Redes MANET.
AODV (Ad hoc On-demand Distance Vector)
Route Error
Cuando el nodo X es incapaz de enviar el paquete P (desde S hasta D) en el enlace (X,Y), genera un mensaje de RERR
El nodo X incrementa el número de secuencia para el destino D en su caché
Éste número de secuencia incrementado (N) se incluye en el mensaje RERR
Cuanod el nodo S recibe el RERR, inicial un nuevo descubrimiento de ruta para D usando un numero de secuencia al menos tan grande como N
Cuando el nodo D recibe el RREQ con número de secuencia N, éste establecerá su número de secuencia a N excepto si ya es mayor que N
Protocolos de Enrutamiento en Redes MANET.
AODV (Ad hoc On-demand Distance Vector)
Detección de rotura de enlace
Mensajes Hello: Los nodos vecinos intercambian periódicamente mensajes de hello
La ausencia de mensajes hello se interpreta como la rotura del enlace
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
AODV (Ad hoc On-demand Distance Vector)
¿Por qué números de secuencia en AODV?
Protocolos de Enrutamiento en Redes MANET.
AODV (Ad hoc On-demand Distance Vector)
Resumen: AODV
Las rutas no han de ir necesariamente en los paquetes de datos.
Los nodos solo mantienen rutas en sus tablas para nodos activos.
Como mucho se mantiene un único nodo como siguiente salto hacia un mismo destino
– DSR permite mantener varias rutas para un mismo destino
Aunque no cambie la topología, las rutas que no se usan se eliminan.
Protocolos de Enrutamiento en Redes MANET.
OLSR (On-demand Link State Routing, Protocolo de enrutamiento de estado de enlace optimizado)
Protocolo proactivo.
Adaptado para redes donde el trafico es aleatorio y esporádico entre un gran numero de nodos, y cuando los nodos que intercomunican varían en el tiempo
Esta preparado para soportar extensiones, como funcionamiento en sleep mode, routing multicast, etc.
No requiere modificar la estructura de los paquetes IP
Protocolos de Enrutamiento en Redes MANET.
OLSR (On-demand Link State Routing)
Una de las principales características de OLSR es que se diseño para reducir la cantidad de mensajes de control que se difunden en una Manet.
Esta optimización se logra al crearse un subconjunto de enlaces entre vecinos de una Manet.
El subconjunto de vecinos que se reporta por los nodos OLSR se conoce como "MPR seleccionados" (Multi-Point Relay Selectors).
En OLSR se logra reducir la cantidad de información de sobrecarga (overhead) al minimizar la cantidad de mensajes de control que se difunden en la Manet.
Protocolos de Enrutamiento en Redes MANET.
OLSR (On-demand Link State Routing)
La reducción en la difusión de mensajes de control se logra al seleccionar nodos MPR (Multi-Point Relay).
Los nodos MPR son los encargados de retransmitir los mensajes de control que se difunden en la Manet.
Cada nodo OLSR envía un mensaje periódicamente denominado HELLO (censado de vecinos).
Los mensajes HELLO incluyen una lista de vecinos del nodo OLSR que envía el mensaje HELLO.
El nodo OLSR reporta en los mensajes HELLO los enlaces unidireccionales y bidireccionales que tiene con sus vecinos.
Con la información de los mensajes HELLO cada nodo puede construir una tabla con los nodos vecinos a 1-salto.
Protocolos de Enrutamiento en Redes MANET.
OLSR (On-demand Link State Routing)
Adicionalmente, cada nodo OLSR construye una tabla que contiene a los "vecinos" que se encuentran a 2-saltos.
El proceso de selección de MPRs se basa en seleccionar un
subconjunto de "vecinos a 1-salto" que proporcionen conectividad con todos los "vecinos a 2-saltos".
Una vez que el nodo OLSR ha realizado la selección de
nodos MPR, este se lo informa a sus vecinos a 1-salto
mediante los mensajes HELLO.
Protocolos de Enrutamiento en Redes MANET.
Nitin H. Vaidya, Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues. 2007
OLSR (On-demand Link State Routing)
Protocolos de Enrutamiento en Redes MANET.
OLSR (On-demand Link State Routing)
Ventajas y Desventajas de OLSR
Reduce la sobrecarga de enrutamiento que se asocia comúnmente a los protocolos de enrutamiento basados en tablas.
Reduce la cantidad de mensajes de control que se difunden en la MANET.
Como cualquier protocolo de tipo proactivo, existe una sobrecarga inherente debido a la difusión periódica de mensajes de control
 Página anterior | Volver al principio del trabajo | Página siguiente  |