Implementación del árbol de etiquetas en el simulador ns-3

Abstract

A routing algorithm for a network of computers is the operation that determines the best path that allows to connect two routing points (called nodes) in a network. This search is realized inside the set of all available paths. An ad-hoc network is a local area network of computers that is characterized by having an infrastructure of little or non-existing planning, and which are set in a very limited time and space; therefore, they do not require a central or fixed administration to communicate among them to be operational. In this thesis, the challenge of making possible the implementation of the routing algorithm for ad-hoc networks Tagtree is face by taking as a theoretical base the GPSR (Greedy Perimeter Stateless Routing) protocol. The objective is to obtain an optimization of the first algorithm over the second one through the use of more effective routes and to obtain a decrease of the delivery time of data packets to and from any one node to another. The chosen software to do such an implementation was the ns-3 simulator, which is based on object-oriented programming and operated under GNU type of license. To reach this objective, we started the development from a previous GPSR code that came from an earlier version of the simulator. The contribution of this work is to achieve the adaptation of the implementation of the GPSR, taken as a base, to recent versions of the ns-3. Similarly, after the needed update, the modification of the strategy of recovery is possible and as a result the implementation of the Tagtree is obtained. This is capable of development thanks to and because the simulator is based on C++ and makes it flexible to adaptation, extension and creation of the needed classes. In conclusion, once the algorithm is implemented through the comparison and results after running the simulations, it is possible to observe and compare the characteristics and advantages of the Tagtree over GPSR.

Un algoritmo de enrutamiento para redes de computadoras es el proceso que permite buscar la mejor opción dentro del conjunto de caminos disponibles para enlazar dos nodos de una red. Las redes de tipo ad-hoc se caracterizan por ser infraestructuras de dispositivos con poca o nula planificación, las cuales se despliegan en tiempo y espacio limitado; por lo que no requieren de una administración central o fija para su operación. En esta tesis se encara el reto de realizar la implementación del algoritmo de enrutamiento para redes ad-hoc Árbol de etiquetas tomando como base teórica el algoritmo Greedy Perimeter Stateless Routing (GPSR). El objetivo es obtener una optimización del primero sobre el segundo, mediante el uso de rutas más efectivas y obtener una disminución del tiempo de entrega de paquetes entre los nodos en comunicación. El software elegido para realizar dicha implementación es el simulador ns-3, el cual está basado en la programación orientada a objetos y es de licencia tipo GNU. Para alcanzar el objetivo de la implementación se partió sobre un código previo del GPSR desarrollado en una versión antigua del simulador. La contribución de este trabajo es lograr la adaptación de la implementación del GPSR tomada como base a versiones recientes del ns-3. Así mismo, después de la actualización requerida se logra realizar la modificación de la estrategia de recuperación y como resultado se obtiene la implementación del Árbol de etiquetas. Esto es viable gracias a que el simulador está basado en C++ y hace permeable la adaptación, extensión y creación de las clases necesarias. De esta manera, una vez implementado el algoritmo es mediante la comparación de resultados obtenidos al correr las simulaciones, que se puede observar y comparar las características y ventajas del Árbol de etiquetas sobre el GPSR.