Modeling and Measuring Performance of Data Dissemination in Opportunistic Networks

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.

Routing and search on large scale networks

Dominique Florian Tschopp

In this thesis, we address two seemingly unrelated problems, namely routing in large wireless ad hoc networks and comparison based search in image databases. However, the underlying problem is in essence similar and we can use the same strategy to attack those two problems. In both cases, the intrinsic complexity of the problem is in some sense low, and we can exploit this fact to design efficient algorithms. A wireless ad hoc network is a communication network consisting of wireless devices such as for instance laptops or cell phones. The network does not have any fixed infrastructure, and hence nodes which cannot communicate directly over the wireless medium must use intermediate nodes as relays. This immediately raises the question of how to select the relay nodes. Ideally, one would like to find a path from the source to the destination which is as short as possible. The length of the found path, also called route, typically depends on how much signaling traffic is generated in order to establish the route. This is the fundamental trade-off that we will investigate in this thesis. As mentioned above, we try and exploit the fact that the communication network is intrinsically low-dimensional, or in other words has low complexity. We show that this is indeed the case for a large class of models and that we can design efficient algorithms for routing that use this property. Low dimensionality implies that we can well embed the network in a low-dimensional space, or build simple hierarchical decompositions of the network. We use both those techniques to design routing algorithms. Comparison based search in image databases is a new problem that can be defined as follows. Given a large database of images, can a human user retrieve an image which he has in mind, or at least an image similar to that image, without going sequentially through all images? More precisely, we ask whether we can search a database of images only by making comparisons between images. As a case in point, we ask whether we can find a query image q only by asking questions of the type "does image q look more like image A or image B"? The analogous to signaling traffic for wireless networks would here be the questions we can ask human users in a learning phase anterior to the search. In other words, we would like to ask as few questions as possible to pre-process and prepare the database, while guaranteeing a certain quality of the results obtained in the search phase. As the underlying image space is not necessarily metric, this raises new questions on how to search spaces for which only rank information can be obtained. The rank of A with respect to B is k, if A is B's kth nearest neighbor. In this setup, low-dimensionality is analogous to the homogeneity of the image space. As we will see, the homogeneity can be captured by properties of the rank relationships. In turn, homogeneous spaces can be well decomposed hierarchically using comparisons. Further, it allows us to design good hash functions. To design efficient algorithms for these two problems, we can apply the same techniques mutatis mutandis. In both cases, we relied on the intuition that the problem has a low intrinsic complexity, and that we can exploit this fact. Our results come in the form of simulation results and asymptotic bounds.

EPFL2010

Signaling and Reciprocity

Wojciech Galuba

Complex networks exist for a number of purposes. The neural, metabolic and food networks ensure our survival, while the social, economic, transportation and communication networks allow us to prosper. Independently of the purposes and particularities of the physical embodiment of the networks, one of their fundamental functions is the delivery of information from one part of the network to another. Gossip and diseases diffuse in the social networks, electrochemical signals propagate in the neural networks and data packets travel in the Internet. Engineering networks for robust information flows is a challenging task. First, the mechanism through which the network forms and changes its topology needs to be defined. Second, within a given topology, the information must be routed to the appropriate recipients. Third, both the network formation and the routing mechanisms need to be robust against a wide spectrum of failures and adversaries. Fourth, the network formation, routing and failure recovery must operate under the resource constraints, either intrinsic or extrinsic to the network. Finally, the autonomously operating parts of the network must be incentivized to contribute their resources to facilitate the information flows. This thesis tackles the above challenges within the context of several types of networks: 1) peer-to-peer overlays – computers interconnected over the Internet to form an overlay in which participants provide various services to one another, 2) mobile ad-hoc networks – mobile nodes distributed in physical space communicating wirelessly with the goal of delivering data from one part of the network to another, 3) file-sharing networks – networks whose participants interconnect over the Internet to exchange files, 4) social networks – humans disseminating and consuming information through the network of social relationships. The thesis makes several contributions. Firstly, we propose a general algorithm, which given a set of nodes embedded in an arbitrary metric space, interconnects them into a network that efficiently routes information. We apply the algorithm to the peer-to-peer overlays and experimentally demonstrate its high performance, scalability as well as resilience to continuous peer arrivals and departures. We then shift our focus to the problem of the reliability of routing in the peer-to-peer overlays. Each overlay peer has limited resources and when they are exhausted this ultimately leads to delayed or lost overlay messages. All the solutions addressing this problem rely on message redundancy, which significantly increases the resource costs of fault-tolerance. We propose a bandwidth-efficient single-path Forward Feedback Protocol (FFP) for overlay message routing in which successfully delivered messages are followed by a feedback signal to reinforce the routing paths. Internet testbed evaluation shows that FFP uses 2-5 times less network bandwidth than the existing protocols relying on message redundancy, while achieving comparable fault-tolerance levels under a variety of failure scenarios. While the Forward Feedback Protocol is robust to message loss and delays, it is vulnerable to malicious message injection. We address this and other security problems by proposing Castor, a variant of FFP for mobile ad-hoc networks (MANETs). In Castor, we use the same general mechanism as in FFP; each time a message is routed, the routing path is either enforced or weakened by the feedback signal depending on whether the routing succeeded or not. However, unlike FFP, Castor employs cryptographic mechanisms for ensuring the integrity and authenticity of the messages. We compare Castor to four other MANET routing protocols. Despite Castor's simplicity, it achieves up to 40% higher packet delivery rates than the other protocols and recovers at least twice as fast as the other protocols in a wide range of attacks and failure scenarios. Both of our protocols, FFP and Castor, rely on simple signaling to improve the routing robustness in peer-to-peer and mobile ad-hoc networks. Given the success of the signaling mechanism in shaping the information flows in these two types of networks, we examine if signaling plays a similar crucial role in the on-line social networks. We characterize the propagation of URLs in the social network of Twitter. The data analysis uncovers several statistical regularities in the user activity, the social graph, the structure of the URL cascades as well as the communication and signaling dynamics. Based on these results, we propose a propagation model that accurately predicts which users are likely to mention which URLs. We outline a number of applications where the social network information flow modelling would be crucial: content ranking and filtering, viral marketing and spam detection. Finally, we consider the problem of freeriding in peer-to-peer file-sharing applications, when users can download data from others, but never reciprocate by uploading. To address the problem, we propose a variant of the BitTorrent system in which two peers are only allowed to connect if their owners know one another in the real world. When the users know which other users their BitTorrent client connects to, they are more likely to cooperate. The social network becomes the content distribution network and the freeriding problem is solved by leveraging the social norms and reciprocity to stabilize cooperation rather than relying on technological means. Our extensive simulation shows that the social network topology is an efficient and scalable content distribution medium, while at the same time provides robustness to freeriding.

EPFL2011

On uncoordinated wireless ad-hoc networks

Alaeddine El Fawal

Emerging pervasive wireless networks, pocket switched networks, Internet of things, vehicular networks and even sensor networks present very challenging communication circumstances. They might involve up to several hundreds of wireless devices with mobility and intermittent connectivity. Centralized coordination in such networks is practically unfeasible. We deal with these challenge using two potential technologies: WIFI and Ultra Wide Band (UWB) Impulse Radio (IR) for medium and short communication range, respectively. Our main goal is to improve the communication performance and to make these networks sustainable in the absence of a centralized coordination. With WIFI, the goal is to design an environment-oblivious data dissemination protocol that holds in highly dynamic unpredictable wireless ad-hoc networks. To this end, we propose a complete design for a scope limited, multi-hop broadcast middleware, which is adapted to the variability of the ad-hoc environment and works in unlimited ad-hoc networks such as a crowd in a city, or car passengers in a busy highway system. We address practical problems posed by: the impossibility of setting the TTL correctly at all times, the poor performance of multiple access protocols in broadcast mode, flow control when there is no acknowledgment and scheduling of multiple concurrent broadcasts. Our design, called "Self Limiting Epidemic Forwarding" (SLEF), automatically adapts its behavior from single hop MAC layer broadcast to epidemic forwarding when the environment changes from being extremely dense to sparse, sporadically connected. A main feature of SLEF is a non-classical manipulation of the TTL field, which combines the usual decrement-when-sending to many very small decrements when receiving. Then, we identify vulnerabilities that are specific to epidemic forwarding. We address broadcast applications over wireless ad-hoc networks. Epidemic forwarding employs several mechanisms such as forwarding factor control and spread control, and each of them can be implemented using alternative methods. Thus, the existence of vulnerabilities is highly dependent on the methods used. We examine the links between them. We classify vulnerabilities into two categories: malicious and rational. We examine the effect of the attacks according to the number of attackers and the different network settings such as density, mobility and congestion. We show that malicious attacks are hard to achieve and their effects are scenario-dependent. In contrast, rational attackers always obtain a significant benefit. The evaluation is carried out using detailed realistic simulations over networks with up to 1000 nodes. We consider static scenarios, as well as vehicular networks. In order to validate our simulation results, we build a solid and widely adaptable experimental testbed for wireless networks. It is composed of 57 mobile wireless nodes equipped with WIFI interface. The adopted platform is OpenWrt, a Linux-like firmware, which makes the testbed robust and easily configurable. With UWB IR, the main problem we deal with is the presence of uncontrolled interference. Indeed, similarly to Code Division Multiple Access (CDMA) systems, signal acquisition with UWB IR signaling requires power control in the presence of interferers, which is very expensive in an uncoordinated system. We solve this problem through a cross-layer optimization: We propose a new signal acquisition method that is independent of the received signal power and we adapt the MAC layer accordingly. Our signal acquisition method is designed to solve the IUI (Inter-User Interference) that occurs in some ad-hoc networks where concurrent transmissions are allowed with heterogeneous power levels. In such scenarios, the conventional detection method, which is based on correlating the received IR signal with a Template Pulse Train (TPT), does not always perform well. The complexity of our proposal is similar to that of the conventional method. We evaluate its performance with the Line Of Sight (LOS) and the Non-LOS (NLOS) office indoor-channel models proposed by the IEEE P802.15.4a study group and find that the improvement is significant. We also investigate the particular case where the concurrent transmissions have the same time-hopping code, and we show that it does not result in collision, such scenarios appear in ad-hoc networks that employ a common code for control or broadcast purposes. At the MAC level, we focus only on one component of a MAC layer, which is the sleeping mode that could be added to any MAC layer proposal adequate to UWB IR. We are motivated by the low power consumption constraint required by the potential applications. We identify the design elements that should be taken into account for an optimal design for a sleeping protocol for UWB-IR such as the possibility of transmitting concurrently without collision and the power consumption model of the hardware behind which is completely different than with the narrow-band signaling. Then, we design two sleeping protocols for centralized and decentralized ad-hoc networks, respectively. We evaluate their performance analytically with the adopted metric being the average life-time of the wireless nodes.

EPFL2009