Towards reliable communication and agreement in mobile ad-hoc networks

During the last decade, the number of wireless devices like digital organizers, mobile phones and laptop computers has drastically increased. At the same time, several technologies, like Bluetooth, GPRS, or WiFi have become mature and offer a high-performance wireless infrastructure to mobile users. However, there exist still many non-equipped areas where no infrastructure is available. For example, during emergency operations, rescuers may want to deploy temporarily an autonomous (or ad-hoc) network. Under these settings, mobile devices (or nodes) operate in a self-organized manner and can only communicate with their immediate wireless neighbors. To send a packet to a remote destination, a node relies on the routing capabilities of the other nodes. In a mobile ad-hoc network (MANET), problems are inherently more complicated to solve than in a regular wired network because of the dynamic topology and the absence of an underlying communication infrastructure. Many algorithms and protocols have been proposed for mobile ad-hoc networks, but very little has been done to evaluate these solutions in real environments. In most cases, algorithms are evaluated by simulation. Such a solution leads however to incorrect conclusions, as we show in the thesis. In order to avoid the shortcomings of simulations, an adequate software framework must be available, in order to ease the development and the deployment of applications or algorithms. We have developed FRANC, a lightweight Java framework dedicated to the implementation of real ad-hoc applications. FRANC is composed of an extensible library of building blocks that can be composed to build more complex applications. The thesis is not limited to practical contributions. We have also addressed two important problems that are at the root of many other distributed computing algorithms. Although extensively studied in wired networks, this research domain is however still in its early stages in MANETs. We first propose a simple broadcast protocol that disseminates efficiently and reliably a message in a one dimensional graph like a car highway. Then, we study the consensus problem and identify the necessary and sufficient conditions for solving it in self-organized networks when the participants are unknown (in the absence of crashes). Finally, we discuss a pragmatic solution to consensus with crashes based on weak ordering oracles. More specifically, we propose an implementation of these oracles and present results collected in a real small-scale wireless testbed.

Large scale selective event dissemination

Sidath Handurukande

Event-based systems usually denote distributed infrastructures that are used to asynchronously disseminate information among geographically distant computing units. In these systems, the information sources (a.k.a. publishers) produce events and the system delivers these events to destinations (a.k.a. subscribers). Subscribers are "decoupled" from publishers in the sense that they do not need to know each other or even be "up" at the same time. The subscribers can specify the kind of information they like to receive in order not to be flooded with events of all kinds. Depending on the applications, different requirements are imposed on the event-based system. On the one hand, some applications require very strong reliability guarantees while other applications can tolerate a certain percentage of event-losses. On the other hand, while some applications can tolerate large delivery latency, others require latency to be small. In certain cases, it is adequate that the subscribers receive a particular "type" of events irrespective of their actual content. In others, the subscribers like to receive a given type of events with a specific content. The event filtering mechanisms used in these applications need to be decentralized to favor the scalability of the applications. Gossip-based broadcast (also called epidemic) algorithms are particularly appropriate for large scale event dissemination. In these algorithms, processes forward the events they receive to other processes they know of (most of the time in a randomized manner): this continues until all or at least a significant percentage of the processes, receive the events. These broadcast algorithms can be tuned to deliver events according to their type. This is done by mapping a broadcast group to a type. However, more elaborate schemes are necessary to deliver events according to their content. This thesis investigates a number of algorithms that can be used in the context of event dissemination. First, we examine two mechanisms in order to make gossip-based algorithms more reliable for event dissemination. More precisely, we propose a garbage collection technique that can be used to purge events according to their level of dissemination among processes. Furthermore, we introduce an adaptation mechanism to increase the reliability of gossip-based broadcast algorithms. The mechanism controls the amount of events injected into the system and adjusts the broadcast rate according to the buffer resources at processes. Then we discuss how clustering of processes according to their network locality can be useful in delivering events. This clustering mechanism could help to reduce the congestion in network links and also helps to disseminate time sensitive events. Finally, we propose an algorithm to achieve a fine-grained event selection in a completely decentralized environment. To this end, processes use gossip messages to form a structured overlay network and a dictionary based subscription model when joining the overlay.

EPFL2005

On broadcast and agreement in mobile ad hoc networks

Yoav Sasson

This thesis studies communication and agreement protocols in wireless ad hoc networks from both theoretical and practical perspectives. The last decade has given rise to the rapid growth of wireless telecommunications such as cellular mobile phone networks and wireless LANs. The diversity of network-aware appliances and devices is ever-increasing. Ultimately, these wireless technologies will seemingly inter-operate, offering a new range of services. This ubiquity of wireless devices will introduce a paradigm shift in the way we conceive distributed applications. Wireless ad hoc networks are self-organizing radio networks that do not rely on a preexisting infrastructure to communicate. Nodes of such networks have limited transmission range, and data packets may need to traverse multiple other nodes before reaching their destination. Research in wireless multi-hop networks was initiated 1970s by the Defense Advanced Research Projects Agency (DARPA) and has regained popularity nowadays due to the widespread availability of wireless devices. Examples of wireless ad hoc networks are i) sensor networks, which are distributed sensors that monitor environmental conditions for civil or military purposes, ii) vehicular ad hoc networks, which offer inter/intra-vehicle and infrastructure-to-vehicle communication to improve the safety, security and efficiency of transportation systems and iii) mesh networks, which provide an instantaneous, reliable and inexpensive network infrastructure to local communities. The multi-hop nature of wireless ad hoc networks, along with possible node mobility and limited energy supplies lead to highly dynamic network topology and significantly different network characteristics and behavior than their wired counterparts. Algorithms that have proved successful for traditional networks such as LANs and WANs are generally not directly transposable to such dynamic environments. This thesis is divided into two parts. In the first part we focus on basic communication primitives such as broadcast and multicast. We first study the impact of mobility on the time complexity of deterministic broadcast algorithms. We then explore the phase transition phenomenon observed in percolation theory and random graphs as a basis for reducing the overhead of broadcast through probabilistic flooding, while maintaining satisfactory message delivery reliability. Finally, we propose a novel location service solution for handling geographically scattered and mobile multicast group members, by dynamically adjusting the number and density of nodes responsible for managing multicast group membership information. The second part of the thesis studies agreement problems. Agreement-related solutions can contribute to enhance the structure and reliability to the highly disorganized and dynamic environment of self-organized networks. We first investigate the consensus problem in the context of self-organized networks. Consensus is a cornerstone of many agreement problems. We define a variant of the traditional consensus problem, by relaxing the requirement for the set of participating processes to be known by all at the beginning of the computation. We then identify the necessary and sufficient conditions under which consensus can be solved. We finally address the problem of resource allocation in mobile ad hoc networks, by designing a novel broadcast mechanism that achieves reliable and total-order delivery of messages with high probability. These properties provide the basis of a mutual exclusion algorithm.

EPFL2007

Modeling and Measuring Performance of Data Dissemination in Opportunistic Networks

Nikodin Ristanovic

In this thesis we focus on understanding, measuring and describing the performance of Opportunistic Networks (ONs) and their applications. An “opportunistic network” is a term introduced to describe a sparse, wireless, ad hoc network with highly mobile nodes. The opportunistic networking paradigm deviates from the traditional end-to-end connectivity concept: Forwarding is based on intermittent connectivity between mobile nodes (typically, users with wireless devices); complete routes between sources and destinations rarely exist. Due to this unique property of spontaneous link establishment, the challenges that exist in ONs are specific. The unstructured nature of these networks makes it difficult to give any performance guarantees on data dissemination. For this reason, in Part I of this thesis we explore the dynamics that affect the performance of opportunistic networks. We choose a number of meaningful scenarios where our models and algorithms can be validated using large and credible data sets. We show that a drift and jump model that takes a spatial approach succeeds in capturing the impact of infrastructure and mobile-to-mobile exchanges on an opportunistic content update system. We describe the effects of these dynamics by using the age distribution of a dynamic piece of data (i.e., information updates) as the performance measure. The model also succeeds in capturing a strong bias in user mobility and reveals the existence of regions, whose statistics play a critical role in the performance perceived in the network. We exploit these findings to design an application for greedy infrastructure placement, which relies on the model approximation for a large number of nodes. Another great challenge of opportunistic networking lies in the fact that the bandwidth available on wireless links, coupled with ad hoc networking, failed to rival the capacity of backbones and to establish opportunistic networks as an alternative to infrastructure-based networks. For this reason, we never study ONs in an isolated context. Instead, we consider the applications that leverage interconnection between opportunistic networks and legacy networks and we study the benefits this synergy brings to both. Following this approach, we use a large operator-provided data set to show that opportunistic networks (based on Wi-Fi) are capable of offloading a significant amount of traffic from 3G networks. At the same time, the offloading algorithms we propose reduce the amount of energy consumed by mobiles, while requiring Wi-Fi coverage that is several times smaller than in the case of real-time offloading. Again we confirm and reuse the fact that user mobility is biased towards certain regions of the network. In Part II of this thesis, we treat another issue that is essential for the acceptance and evolution of opportunistic networks and their applications. Namely, we address the absence of experimental results that would support the findings of simulation based studies. Although the techniques such as contact-based simulations should intuitively be able to capture the performance of opportunistic applications, this intuition has little evidence in practice. For this reason, we design and deploy an experiment with real users who use an opportunistic Twitter application, in a way that allows them to maintain communication with legacy networks (i.e., cellular networks, the Internet). The experiment gives us a unique insight into certain performance aspects that are typically hidden or misinterpreted when the usual evaluation techniques (such as simulation) are used. We show that, due to the commonly ignored factors (such as the limited transmission bandwidth), contact-based simulations significantly overestimate delivery ratio and obtain delays that are several times lower than those experimentally acquired. In addition to this, our results unanimously show that the common practice of assuming infinite cache sizes in simulation studies, leads to a misinterpretation of the effects of a backbone on an opportunistic network. Such simulations typically overestimate the performance of the opportunistic component, while underestimating the utility of the backbone. Given the discovered deficiencies of the contact-based simulations, we consider an alternative statistical treatment of contact traces that uses the weighted contact graph. We show that this approach offers a better interpretation of the impact of a backbone on an opportunistic network and results in a closer match when it comes to modeling certain aspects of performance (namely, delivery ratio). Finally, the security requirements for the opportunistic applications that involve an interconnection with legacy networks are also highly specific. They cannot be fully addressed by the solutions proposed in the context of autonomous opportunistic (or ad hoc) networks, nor by the security frameworks used for securing the applications with continuous connectivity. Thus, in Part III of this thesis, we put together a security framework that fits the networks and applications that we target (i.e., the opportunistic networks and applications with occasional Internet connectivity). We then focus on the impact of security print on network performance and design a scheme for the protection of optimal relaying capacity in an opportunistic multihop network. We fine-tune the parameters of our scheme by using a game-theoretic approach and we demonstrate the substantial performance gains provided by the scheme.

EPFL2012