A methodological approach to routing protocol design and evaluation in opportunistic networking

Abstract

Al llarg dels anys, les tecnologies sense fils s’han integrat en dispositius quotidians com ara telèfons, tauletes i portàtils. Al principi, les comunicacions sense fil es basaven en una infraestructura fixa. Després, es van estudiar i implementar xarxes sense infraestructura. Aquestes xarxes van mostrar una oportunitat per a ambients amb topologia dinàmica, una mala connectivitat o comunicacions interrompudes. La investigació va mostrar que l’explotació de les oportunitats de comunicació node-a-node permet la transmissió d’informació en condicions extremes de xarxa, fins i tot quan un camí d’extrem a extrem no pot existir. Una pila de xarxa típica com TCP/IP podria no ser factible. S’han desenvolupat algunes tecnologies específiques per abordar aquests reptes. Aquests paradigmes emergents de xarxa van ser Delay Tolerant Networks (DTN), una classe de Opportunistic Networks (OppNets). Hem estudiat els entorns OppNets i les característiques que descriuen els comportaments de les xarxes intrínseques. Hem definit un conjunt de característiques que descriuen plenament un escenari OppNet. Per tant, els escenaris d’OppNet es poden descriure amb un vector d’aquestes característiques. A més, hem dissenyat una col·lecció d’escenaris, un corpus, per al seu ús en l’estudi i el desenvolupament d’algorismes d’encaminament per a Xarxes Opportunistes. Per a obtenir aquests escenaris, seguim una metodologia basada en la caracterització de l’espai i l’elecció dels millors elements exemplars de manera que el corpus en el seu conjunt sigui representatiu de tots els escenaris possibles. Fins ara, la recerca en aquest àmbit utilitza traces de xarxa no estàndard, fent que sigui difícil avaluar algoritmes i realitzar comparacions justes entre ells. Aquests desenvolupaments van ser difícils d’avaluar objectivament i propensos a biaixos no intencionats que van afectar directament la qualitat de la recerca. La nostra contribució és més que una col·lecció d’escenaris; el nostre corpus proporciona una col·lecció fina de comportaments de xarxa que s’adapten al desenvolupament d’algorismes d’encaminament, en particular l’avaluació i comparació d’aquests. Si la comunitat científica accepta aquest corpus, la comunitat tindrà una metodologia d’acord global on la validesa dels resultats no es limitarà a escenaris específics o condicions de xarxa. Així, evitant les configuracions d’avaluació autoproduides, estalviant temps, problemes de disponibilitat i biaix de selecció. Una nova investigació a la zona podrà validar els algoritmes d’encaminament ja publicats. També serà possible identificar els escenaris que s’adaptin millor per a fins específics, i els resultats es verificaran fàcilment. El corpus està disponible gratuïtament per descarregar i utilitzar.

A lo largo de los años, las tecnologías inalámbricas se han integrado en dispositivos cotidianos como teléfonos, tabletas y ordenadores portátiles. En un principio, las comunicaciones inalámbricas se basaban en una infraestructura fija. Después se estudiaron e implementaron redes libres de infraestructura. Estas redes mostraron una oportunidad para entornos con topología dinámica, mala conectividad o comunicaciones interrumpidas. La investigación demostró que aprovechar las oportunidades de comunicación de nodo a nodo permite la transmisión de información en condiciones de red extremas, incluso cuando es posible que nunca exista una ruta de extremo a extremo. Una pila de red típica como TCP/IP no es adecuada. Por lo tanto, se han desarrollado algunas tecnologías específicas para hacer frente a estos desafíos. Estos paradigmas de redes emergentes fueron las redes tolerantes al retraso (DTN), un tipo de Redes Oportunistas (OppNets). Hemos estudiado los entornos OppNets y las características que describen los comportamientos intrínsecos de la red. Hemos definido un conjunto de características que describen completamente un escenario de OppNet. Los escenarios de OppNet se pueden describir con un vector de esas características. Además, hemos diseñado una colección de escenarios, un corpus, para su uso en el estudio y desarrollo de algoritmos de enrutamiento para Redes Oportunistas. Para la obtención de estos escenarios se siguió una metodología basada en la caracterización del espacio y la elección de los mejores ejemplares de manera que el corpus en su conjunto fuera representativo de todos los escenarios posibles. Hasta ahora, la investigación en esta área utilizaba trazas de red no estándar, lo que dificultaba la evaluación de algoritmos y la realización de comparaciones justas entre ellos. Estos desarrollos fueron difíciles de evaluar objetivamente y propensos a sesgos no intencionales que afectaron directamente la calidad de la investigación. Nuestra contribución es más que una colección de escenarios; nuestro corpus proporciona una excelente colección de comportamientos de red que se adaptan al desarrollo de algoritmos de enrutamiento, evaluándolos y comparándolos específicamente. Si la comunidad científica adopta este corpus, la comunidad tendrá una metodología acordada globalmente donde la validez de los resultados no se limitará a escenarios específicos o condiciones de red. Así, se evitan montajes de evaluación autoproducidos, ahorro de tiempo, problemas de disponibilidad y sesgos de selección. Nuevas investigaciones en el área podrán validar los algoritmos de enrutamiento ya publicados. También será posible identificar los escenarios que mejor se adapten a propósitos específicos, y los resultados se verificarán fácilmente. El corpus está disponible para su descarga y uso de forma gratuita.

Over the years, wireless technologies have been integrated into everyday devices such as phones, tablets and laptops. At first, wireless communications were based on fixed infrastructure. Then, infrastructure-free networks were studied and implemented. These networks showed an opportunity for environments with dynamic topology, poor connectivity or disrupted communications. Research showed that exploiting node-to-node communication opportunities enables information transmission in extreme network conditions, even when an end-to-end path may never exist. A typical network stack such as TCP/IP is not a feasible solution. Thus, some specific technologies have been developed to address these challenges. These emerging networking paradigms were Delay Tolerant Networks (DTN), a class of Opportunistic Networks (OppNets). In this thesis, we have studied the OppNets environments and the characteristics that describe the intrinsic network behaviours. We have defined a set of characteristics that fully describes an OppNet scenario. The OppNet scenarios can be described with a vector of those characteristics. Furthermore, we have designed a collection of scenarios, a corpus, for its use in the study and development of routing algorithms for Opportunistic Networks. To obtain these scenarios, we followed a methodology based on characterising the space and choosing the best exemplary items in such a way that the corpus as a whole was representative of all possible scenarios. Until now, research in this area used non-standard network traces, making it challenging to evaluate algorithms and perform fair comparisons between them. These developments were hard to assess objectively and prone to unintentional biases that directly affected the quality of the research. Our contribution is more than a collection of scenarios; our corpus provides a fine collection of network behaviours that suit the development of routing algorithms, specifically evaluating and comparing them. If the scientific community embraces this corpus, the community will have a global-agreed methodology where the validity of results would not be limited to specific scenarios or network conditions. Thus, avoiding self-produced evaluation setups, saving time, availability problems and selection bias. New research in the area will be able to validate the routing algorithms already published. It will also be possible to identify the scenarios that suit better for specific purposes, and results will be easily verified. The corpus is available free to download and use.