Algoritmos para el estudio de técnicas multi-path y network-coding en redes inalámbricas multi-salto

Abstract

RESUMEN: A día de hoy existen multitud de técnicas y mecanismos para mejorar el rendimiento en redes de comunicación cableadas. Sin embargo, al trabajar con sistemas inalámbricos, son muchos los nuevos aspectos a tener en cuenta para alcanzar un comportamiento comparable, o al menos adecuado para satisfacer la cada vez mayor demanda de calidad por parte de los usuarios. En ese sentido, existen distintas posibilidades que actualmente se encuentran en fases de investigación, ya que necesitan de un nivel de maduración mayor para llegar a ser implementadas. Se ha demostrado que dividir el tráfico a través de múltiples caminos (encaminamiento multi-camino o multi-path) incrementa el rendimiento de una red, en comparación con encaminamientos de una única ruta, en donde aparecen problemas como la fiabilidad o la congestión de la red. Sin embargo, las interferencias causadas por la naturaleza (intrínsecamente de difusión) de los medios inalámbricos pueden reducir notablemente los beneficios de tal aproximación. Por otro lado, también se ha demostrado que permitir que los nodos intermedios de una red mezclen (codifiquen) la información procedente de distintas fuentes para enviarla hacia sus destinos correspondientes, donde será decodficada, puede aumentar su throughput. Esta técnica, que se conoce como codificación de red (network-coding), ha sido estudiada principalmente en entornos de red cableados, y resulta interesante analizar sus posibilidades en redes inalámbricas. En este trabajo se ha hecho uso de las dos propuestas anteriores para implementar una serie de algoritmos en C++, basándose en la teoría de grafos. En primer lugar, un conjunto de funciones para hallar diferentes clases de caminos disjuntos en un grafo dado, con los que poder aplicar un tipo de encaminamiento multipath. En un segundo bloque, una serie de algoritmos para establecer la posibilidad de aplicar la técnica de network-coding en un escenario inalámbrico dado, así como para identificar los posibles nodos encargados de mezclar la información. Todos los algoritmos implementados se validarán, mediante un exhaustivo proceso de análisis, utilizando despliegues de redes generados de manera aleatoria. Además, los resultados obtenidos serán llevados a un simulador de redes para comprobar, utilizando protocolos reales, cuáles son los posibles beneficios que pueden aportar.

ABSTRACT: Nowadays, there are several mechanisms to improve performance over traditional wired networks. On the other hand, some new challenges will spring while trying to apply the same techniques over wireless networks and obtain comparable performance gains. There are various possibilities that are currently being research by the scientific community, since they need a higher degree of maturity to go to real development and deployment. It has been shown that splitting trafic over multiple paths (multi-path routing), can increase the network performance, as compared to legacy single-path routing, where there could be reliability and congestion issues. However, the interference caused by simultaneous transmissions, due to the intrinsic broadcast nature of wireless networks, can significantly reduce the benefits of such an approach. On the other hand, it has been proved that allowing intermediate nodes mixing (\encoding") information from different sources in order to be sent joined to their respective destination nodes, where the packets will be decoded, can signi cantly increase the network throughput. This technique, known as \network-coding", has been already studied, but most of the existing works are done for wired network environments, and it becomes interesting to analyze its potential in wireless networks. In this project we have used both of the previous proposals to implement a number of algorithms, using the C++ programming language, which are based on the traditional graph theory. On the first hand, we have implemented a set of functions to find a number of disjoint paths in a given graph, in order to apply multi-path routing. Afterwards, we also implemented algorithms to establish the feasibility of \network-coding" over wireless scenarios, to identify which nodes would need to take the coding role, mixing the information before transmitting it. All implemented algorithms have been validated through an extensive simulation campaign, using randomly generated network topologies. Last, but not least, the obtained results will be exploited, over a network simulator, to assess, by means of real protocols, which are the potential benefits they might bring about.