PDF de programación - Protocolos de encaminamiento en redes inalámbricas mesh: un estudio teórico y experimental

UNIVERSITAT OBERTA DE CATALUNYA

Máster Oficial en Software Libre

Protocolos de encaminamiento en redes
inalámbricas mesh: un estudio teórico y

experimental

Albert Batiste Troyano

Tutor: Pablo Neira Ayuso, Universidad de Sevilla

Sevilla, junio de 2011

2

Índice general

1. Introducción

7

1.1. Objetivos.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2. Planificación.

. . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3. Conceptos básicos.

. . . . . . . . . . . . . . . . . . . . . . . . 14

1.3.1. WLAN/IEEE 802.11. . . . . . . . . . . . . . . . . . . . 14

1.3.2. Redes ad-hoc.

. . . . . . . . . . . . . . . . . . . . . . . 17

1.4. Orígenes e historia de las redes ad-hoc y mesh. . . . . . . . . . 22

1.4.1. 1970-1980: Primeras redes ad-hoc. . . . . . . . . . . . . 22

1.4.2. 1980-2000: Redes MANET y difusión de 802.11 . . . . 25

1.4.3. 2000-2011: amplia adaptación de 802.11 y primeras re-

des inalámbricas comunitarias. . . . . . . . . . . . . . . 26

2. Estado del arte

29

2.1. AODV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.1.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . 31

2.1.2. Funcionamiento . . . . . . . . . . . . . . . . . . . . . . 33

2.2. DSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.2.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . 41

3

4

ÍNDICE GENERAL

2.2.2. Funcionamiento . . . . . . . . . . . . . . . . . . . . . . 42

2.3.

IEEE 802.11s

. . . . . . . . . . . . . . . . . . . . . . . . . . . 50

2.3.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . 51

2.3.2. Funcionamiento . . . . . . . . . . . . . . . . . . . . . . 52

2.4. B.A.T.M.A.N. . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2.4.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . 61

2.4.2. Funcionamiento . . . . . . . . . . . . . . . . . . . . . . 62

2.5. Babel

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

2.5.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . 66

2.5.2. Funcionamiento . . . . . . . . . . . . . . . . . . . . . . 67

2.6. OLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

2.6.1.

Introducción . . . . . . . . . . . . . . . . . . . . . . . . 71

2.6.2. Funcionamiento . . . . . . . . . . . . . . . . . . . . . . 73

2.7. Ejemplos de redes mesh en funcionamiento . . . . . . . . . . . 79

2.7.1. Redes inalámbricas comunitarias.

. . . . . . . . . . . . 79

2.7.2. Redes inalámbricas municipales. . . . . . . . . . . . . . 84

3. Descripción del sistema

87

3.1. Sistema utilizado . . . . . . . . . . . . . . . . . . . . . . . . . 87

3.1.1. Hardware . . . . . . . . . . . . . . . . . . . . . . . . . 87

3.1.2. Software . . . . . . . . . . . . . . . . . . . . . . . . . . 89

3.1.3. Entorno de despliegue de la red y topologías modeladas. 92

4. Pruebas, resultados y evaluación.

95

4.1. Parámetros a evaluar. . . . . . . . . . . . . . . . . . . . . . . . 95

ÍNDICE GENERAL

5

4.2. Pruebas realizadas.

. . . . . . . . . . . . . . . . . . . . . . . . 96

4.3. Resultados y comparativa.

. . . . . . . . . . . . . . . . . . . . 99

4.3.1. RTT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

4.3.2. Sesiones por segundo y throughput.

. . . . . . . . . . . 102

4.3.3. Reconfiguración de rutas frente a la caída de un nodo. 104

5. Conclusiones y trabajos futuros.

107

5.1. Conclusiones.

. . . . . . . . . . . . . . . . . . . . . . . . . . . 107

5.2. Trabajos futuros.

. . . . . . . . . . . . . . . . . . . . . . . . . 110

Anexo

Bibliografía

Agradecimientos

Licencia

111

121

127

129

6

ÍNDICE GENERAL

Capítulo 1

Introducción

Desde que se desarrollaron las primeras máquinas computadoras, una de
las grandes líneas de investigación e innovación en el campo de la informática
ha sido la de las redes de computadores, cómo interconectar equipos alejados
en el espacio para que sus usuarios puedan comunicarse y compartir servicios
e información.

Se ha avanzado tanto en esta materia, que hoy en día, el mundo que
conocemos sería impensable sin la más extensa red de ordenadores que ha
creado la humanidad, Internet. Desde las primeras redes de los 60, como
ARPANET, hasta el Internet actual, la técnica ha recorrido un vertiginoso
camino, en el que se han desarrollado infinidad de protocolos, dispositivos y
estándares destinados a interconectar computadores.

En este trabajo estudiaremos, concretamente, los aspectos relacionados
con el diseño, la arquitectura, la implementación, el despliegue y la evaluación
experimental para redes inalámbricas mesh, centrándonos, sobre todo, en
la forma en que los distintos equipos o nodos mesh intercambian datos y
deciden qué camino debe seguir un mensaje para llegar del origen al destino.
Es decir, analizaremos, de forma teórica y experimental, distintos protocolos
de encaminamiento o enrutamiento usados en redes inalámbricas mesh.

Para desarrollar el trabajo será necesario hacer un estudio del arte que
describa los protocolos más extendidos para este tipo de redes y, posterior-
mente, desplegar una pequeña red mesh experimental sobre la que se pro-
barán y compararán dichos protocolos de enrutamiento. Finalmente, a partir
de las pruebas realizadas, extraeremos una serie de resultados experimentales

7

8

CAPÍTULO 1. INTRODUCCI ÓN

que nos servirán para redactar las conclusiones.

Los protocolos elegidos para el estudio serán: DSR (Dynamic Source
Routing), AODV (Ad-hoc On-demand Distance Vector ), OLSR (Optimized
Link State Routing), Babel, BATMAN (Better Aproach To Mobile Ad-hoc
Networking) e IEEE1 802.11s. Los protocolos DSR y OLSR están incluidos en
el estudio teórico, pero no en el experimental, ya que consideramos necesario
describirlos por su importancia y por ser precursores de otros protocolos.
Elegimos estos protocolos en concreto por ser los más ampliamente usados
a la hora de desplegar redes mesh y porque existen implementaciones libres,
lo que nos da la posibilidad de usarlos, estudiar en profundidad cómo están
diseñados los algoritmos e incluso introducir alguna modificación, si fuera
necesario, en el código.

Podríamos describir de forma breve (en 1.3.2 lo hacemos de manera más
detallada) una red mesh como un conjunto de dispositivos conectados de
manera inalámbrica formando una topología de malla (mesh, en inglés) en
la que cada nodo puede establecer un enlace inalámbrico con uno o más ve-
cinos. Dichos dispositivos no necesitan nodos especiales a los que conectarse
para formar parte de la red. Dentro de esta red, los nodos deben ser capaces
de reenviar paquetes de datos hacia otros nodos, distribuyendo la tarea de
encaminar o enrutar la información entre todos los nodos de la red. La deci-
sión sobre qué nodo debe enrutar un paquete determinado se hace de forma
dinámica, según la conectividad de la red.

Esta definición se puede aplicar también a lo que se conoce como red ad-
hoc. Pero a diferencia de esta, en una red mesh existen nodos que funcionan
también como puntos de acceso, a los que se conectan otros dispositivos
(clientes) para formar parte de la red. Finalmente, ciertos nodos mesh pueden
actuar como pasarela o portal mediante el cual interconectar la red mesh a
redes de otro tipo (una red cableada o Internet, por ejemplo).

El hardware necesario para implementar una red mesh es relativamente
económico y accesible, ya que es el mismo que se utiliza para redes WLAN
(Wireless Local Area Network ) convencionales. Por otra parte, esta tecno-
logía opera en una banda del espectro radioeléctrico que es de libre uso, sin
licencia, por lo que cualquiera puede usar el medio sin necesidad de trámites
o permisos.

Todos estos hechos hacen de las redes mesh soluciones ideales en esce-
narios donde es complicado desplegar una infraestructura cableada, debido a

1Institute of Electrical and Electronics Engineers

9

dificultades técnicas y/o económicas. Posibles escenarios son: un edificio en el
que sus habitantes se interconectan de manera inalámbrica para formar una
red en la que compartir información, servicios y, adicionalmente, una o varias
conexiones a Internet, un evento puntual en el que queremos desplegar una
red inalámbrica (una feria, un festival, un congreso), áreas rurales a las que
no llega la infraestructura comercial necesaria para tener conexión ADSL o
un conjunto de usuarios que decide crear una red comunitaria y abierta, que
va creciendo cuantos más usuarios se añaden.

Consideramos este último ejemplo especialmente interesante. Desde ha-
ce unos años han surgido, alrededor de todo el mundo, redes comunitarias
inalámbricas basadas en topologías mesh. Son redes sin ánimo de lucro, con
un origen ciudadano, autogestionadas y autofinanciadas. En ellas sus usuarios
comparten libremente todo tipo de recursos y servicios digitales (intercam-
bio de archivos, servidores ftp, chats, correo, etc.). Pueden abarcar desde un
edificio hasta áreas de varios cientos de kilómetros cuadrados.

Además, estas iniciativas suelen usar y desarrollar software libre para
hacer funcionar sus redes, permitiendo que otras personas y comunidades
aprovechen esos conocimientos para crear nuevas redes mesh comunitarias.
Existen numerosas aplicaciones y protocolos con licencia libre para imple-
mentar redes mesh. Incluso el núcleo Linux, en sus últimas versiones, ya
incluye funcionalidad mesh.

La comunidad del software libre y las redes mesh comunitarias tienen

algunos rasgos comunes:

Organizaciones de base, ciudadanas.

Despliegue espontáneo.

Uso de tecnología barata y estándar.

Sin ánimo de lucro.

Coordinación informal.

Estamos hablando, por lo tanto, de un nuevo campo en el mundo de
las redes informáticas que está destinado a ser protagonista en los próximos
años, de la mano del software libre y las iniciativas comunitarias.

10

CAPÍTULO 1. INTROD