Throughput Analysis of Large Networks

While wired infrastructure constitutes the backbone of most wireless networks, wireless systems appeal the most to the dynamic and rapidly evolving requirements of today's communication systems because of their ease of deployment and mobility, not to mention the high cost of building a wired infrastructure. This led to an increased interest in the so called wireless ad hoc networks formed of a group of users, known as nodes, capable of communicating with each other through a shared wireless channel. Needless to say, these nodes are asked to use the shared wireless medium in the most efficient fashion, which is not an easy task given the absence of wired backbone. This requires a profound understanding of the wireless medium to establish a decentralized cooperation scheme, if needed, that best utilizes the resources available in the wireless channel. A significant part of this thesis focuses on the properties of the shared wireless channel, whereby we are interested in studying the spatial diversity and the beamforming capabilities in large wireless networks which are crucial in analyzing the throughput of ad hoc networks. In this thesis, we mainly focus on the problem of broadcasting information in the most efficient manner in a large two-dimensional ad hoc wireless network at low SNR and under line-of-sight propagation. A new communication scheme, which we call multi-stage back-and-forth beamforming, is proposed, where source nodes first broadcast their data to the entire network, despite the lack of sufficient available power. The signal's power is then reinforced via successive back-and-forth beamforming transmissions between different groups of nodes in the network, so that all nodes are able to decode the transmitted information at the end. This scheme is shown to achieve asymptotically the broadcast capacity of the network, which is expressed in terms of the largest singular value of the matrix of fading coefficients between the nodes in the network. A detailed mathematical analysis is then presented to evaluate the asymptotic behavior of this largest singular value. We further characterize the maximum achievable broadcast rate under different sparsity regimes. Our result shows that this rate depends negatively on the sparsity of the network. This is to be put in contrast with the number of degrees of freedom available in the network, which have been shown previously to increase with the sparsity of the network. In this context, we further characterize the degrees of freedom versus beamforming gain tradeoff, which reveals that high beamforming gains can only be obtained at the expense of reduced spatial degrees of freedom. Another important factor that impacts the throughput in wireless networks is the transmit/receive capability of the transceiver at the nodes. Traditionally, wireless radios are half-duplex. However, building on self-interference cancellation techniques, full-duplex radios have emerged as a viable paradigm over the recent years. In the last part of this thesis, we ask the fundamental question: how much can full-duplex help? Intuitively, one may expect that full-duplex radios can at most double the capacity of wireless networks, since they enable nodes to transmit and receive at the same time. However, we show that the capacity gain can indeed be larger than a factor of 2; in particular, we construct a specific instance of a wireless network where the the full-duplex capacity is triple the half-duplex capacity.

Bits through Time

Elie Najm

In any communication system, there exist two dimensions through which the information at the source becomes distorted before reaching the destination: the noisy channel and time. Messages transmitted through a noisy channel are susceptible to modification in their content, due to the action of the noise of the channel. Claude E. Shannon, in his seminal paper of 1948 "A Mathematical Theory of Communication", introduces the bit as a unit of measure of information, and he lays down the theoretical foundations needed to understand the problem of sending bits reliably through a noisy channel. The distortion measure, which he used to quantify reliability, is the error probability. In his paper, Shannon shows that any channel is characterized by a number that he calls capacity: It represents the highest transmission rate that can be used to communicate information with, through this same channel, while guaranteeing a negligible error probability. Whereas, even if the messages are sent through a perfect channel, the time they take to reach their destination causes the receiver to acquire a distorted view of the status of the source that generated these messages. For instance, take the case of a monitor interested in the status of a distant process. A sender observes this process and, to keep the monitor up-to-date, sends updates to it. However, if, at any time t, the last received update at the monitor was generated at time u(t), then the information at the receiver reflects the status of the process at time u(t), not at time t. Hence, the monitor has a distorted version of reality. In fact, it has an obsolete version with an age of t-u(t). The concept of age as a distortion measure in communication systems was first used in 2011 by Kaul et al., in order to assess the performance of a given vehicular network. The aim of the authors was to come up with a transmission scheme that would minimize an age-related metric: the average age. Since then, a growing body of works has used this metric to evaluate the performance of multiple communication systems. The drive behind this interest lies in the importance that status-update applications are gaining in today's life (in vehicular networks, warehouse and environment surveillance, news feed,etc.). In this thesis, we choose age as a distortion measure and derive expressions for the average age and the average peak-age (another age-related metric) for different communication systems. Therefore, we divide this dissertation into two parts: In the first part, we assume that the the updates are transmitted through a noiseless channel that has a random service time. In the second part, we consider a special category of noisy channels, namely the erasure channel. In the first part of this thesis, in order to compute the age-related metrics, we employ queue-theoretic concepts. We study and compare the performance of various transmission schemes under different settings.We show that the optimal transmission scheme when the monitor is interested in a single source loses its optimality when another source of higher priority shares the system. In the second part of this thesis, we introduce, in our age calculations, the distortion caused by the erasure channel on the transmitted updates. In order to combat the erasures of the channel, we first consider two flavors of the hybrid automatic repeat request (HARQ). Finally, we focus on the optimal average age that could be achieved over an erasure channel.

EPFL2019

Broadcasting and Multicasting Nested Message Sets

Shirin Saeedi Bidokhti

Finding theoretical limits on the performance of communication systems and designing schemes to achieve them is one of the fundamental questions in information theory. While the theory of point-to-point communication is well-investigated, most problems have remained unresolved when communication is over a multi-user system. This lack of understanding is unsatisfactory for today’s growing networks. Recently, significant progress has been made on these problems through a deterministic approach which lays out a promising path in developing a better understanding of multi-user communication systems and in devising new communication schemes. In this thesis, we take a deterministic approach to the problem of communicating nested message sets over wireless and wireline networks. This class of problems is motivated by its applications in video streaming services over heterogeneous networks, where users have different quality-of-service demands. This thesis mainly considers the scenario where a common message (e.g., the low resolution information of a video stream) and a private message (e.g., a higher level of resolution) are to be encoded into a signal and transmitted over a shared medium (e.g., mobile networks, the Internet) towards a set of users. A group of the users, called public receivers, demand only the common message and the rest, called private receivers, demand both messages. The focus is on single-hop broadcast channels and multi-hop wireline networks. A Linear deterministic model for broadcast channels assumes that every user receives a linear transformation of the sent signal. This model is mainly motivated by the MIMO Gaussian broadcast problem in the high SNR regime. We start our study with a simple, yet rich, class of such broadcast channels. We address the main challenges in designing optimal encoding schemes and seek new techniques. In particular, we give an exact characterization of the ultimate rates of communication (together with a class of linear codes that achieves them) over channels with three public and any number of private receivers. We show sub-optimality of these schemes for channels with more than three public receivers and propose a block Markov scheme which allows communication at higher rates. Using this technique, we characterize a set of achievable rates of communication. The intuitions and techniques that we develop over this class of channels guide us towards designing optimal codes for (general) linear deterministic channels. We fully characterize the set of all admissible rates of communication for linear deterministic channels with two public and any number of private receivers. We extend this result to also allow communication of three nested message sets. The study of deterministic models is aimed to be instructive for understanding more general channels. In this regard, we consider the problem of broadcasting two nested message sets over general broadcast channels with two public and one private receiver. For such general broadcast channels, the ultimate rates of communications (and consequently optimal communication schemes) are still unknown. We adapt the block Markov encoding scheme, which we developed within the framework of linear deterministic channels, to general broadcast channels and characterize a set of achievable rates. This achievable rate-region turns out to be equal to the best previously known region (over channels with two public and one private receiver). Nonetheless, we argue that it remains possible that our block Markov encoding scheme may strictly outperform the previous schemes over channels with more (public) receivers. We discuss potential future directions that seem promising. When communication takes place over a multi-hop network, devising optimal communication strategies becomes much more challenging as the encoding scheme of the source should be designed jointly together with the encoding schemes of all the intermediate nodes of the network. We explore this problem over wireline networks, assuming two public and one private receiver. First, we ask if one can always devise a simple and rate-optimal strategy to route the private information to the private receiver and on the remaining network multicast the common message to all receivers. We discuss networks for which this strategy is suboptimal and characterize a class of networks for which it is indeed optimal. We also establish close connections of this problem to linear deterministic channels. This connection lets us formulate another strategy for nodes’ operations which achieves higher rates of transmission. Characterizing all admissible rates of communication over this three-receiver network remains open for further investigation.

EPFL2012

Reliable and Real-Time Distributed Abstractions

David Kozhaya

The celebrated distributed computing approach for building systems and services using multiple machines continues to expand to new domains. Computation devices nowadays have additional sensing and communication capabilities, while becoming, at the same time, cheaper, faster and more pervasive. Consequently, areas like industrial control, smart grids and sensor networks are increasingly using such devices to control and coordinate system operations. However, compared to classic distributed systems, such real-world physical systems have different needs, e.g., real-time and energy efficiency requirements. Moreover, constraints that govern communication are also different. Networks become susceptible to inevitable random losses, especially when utilizing wireless and power line communication. This thesis investigates how to build various fundamental distributed computing abstractions (services) given the limitations, the performance and the application requirements and constraints of real-world control, smart grid and sensor systems. In quest of completeness, we discuss four distributed abstractions starting from the level of network links all the way up to the application level. At the link level, we show how to build an energy-efficient reliable communication service. This is especially important for devices with battery-powered wireless adapters where recharging might be unfeasible. We establish transmission policies that can be used by processes to decide when to transmit over the network in order to avoid losses and minimize re-transmissions. These policies allow messages to be reliably transmitted with minimum transmission energy. One level higher than links is failure detection, a software abstraction that relies on communication for identifying process crashes. We prove impossibility results concerning implementing classic eventual failure detectors in networks with probabilistic losses. We define a new implementable type of failure detectors, which preserves modularity. This means that existing deterministic algorithms using eventual failure detectors can still be used to solve certain distributed problems in lossy networks: we simply replace the existing failure detector with the one we define. Using failure detectors, processes might get information about failures at different times. However, to ensure dependability, environments such as distributed control systems (DCSs), require a membership service where processes agree about failures in real time. We prove that the necessary properties of this membership cannot be implemented deterministically, given probabilistic losses. We propose an algorithm that satisfies these properties, with high probability. We show analytically, as well as experimentally (within an industrial DCS), that our technique significantly enhances the DCS dependability, compared to classic membership services, at low additional cost. Finally, we investigate a real-time shared memory abstraction, which vastly simplifies programming control applications. We study the feasibility of implementing such an abstraction within DCSs, showing the impossibility of this task using traditional algorithms that are built on top of existing software blocks like failure detectors. We propose an approach that circumvents this impossibility by attaching information to the failure detection messages, analyze the performance of our technique and showcase ways of adapting it to various application needs and workloads.

EPFL2016