Consumer demand for high-quality video over wireless networks is increasing at fast pace. The resulting technical challenges are particularly stringent in crowded spaces, where the density of users far exceeds the ability to deploy cellular base stations or WiFi infrastructure in a cost effective way. To address this problem, we present a reliable and scalable live streaming solution based on wireless multicast with real-time network coding. At the core of our approach is a timely delivery scheme that uses a minimum amount of feedback from the receivers to generate coded repair packets that are simultaneously useful to a large number of users. Our protocol, which we implemented and tested in a real-world wireless testbed, differs from traditional wireless unicast and multicast schemes in that (a) the feedback messages of the users are treated jointly and (b) the repair mechanism considers both the playout deadlines of individual packets and the list of packets already received by the clients. In comparison with a standard video approach that sends an MPEG-2 encoded stream over 802.11 unicast links, our solution offers real-time guarantees for all users commensurate with the link quality and an 11x improvement in terms of bandwidth usage. A commercial version of the proposed solution shows a strong increase in the number of clients that can access video streams simultaneously over a single WiFi hotspot.

A fundamental understanding of the delay behavior of network coding is key towards its successful application in real-time applications with strict message deadlines. Previous contributions focused mostly on the average decoding delay, which although useful in various scenarios of interest is not sufficient for providing worst-case delay guarantees. To overcome this challenge, we investigate the entire delay distribution of random linear network coding for any field size and arbitrary number of encoded symbols (or generation size). By introducing a Markov chain model we are able to obtain a complete solution for the erasure broadcast channel with two receivers. A comparison with Automatic Repeat reQuest (ARQ) with perfect feedback, round robin scheduling and a class of fountain codes reveals that network coding on GF(24) offers the best delay performance for two receivers. We also conclude that GF(2) induces a heavy tail in the delay distribution, which implies that network coding based on XOR operations although simple to implement bears a relevant cost in terms of worst-case delay. For the case of three receivers, which is mathematically challenging, we propose a brute-force methodology that gives the delay distribution of network coding for small generations and field size up to GF(24).

Shannon defined channel capacity as the highest rate at which there exists a sequence of codes of block length n such that the error probability goes to zero as n goes to infinity. In this definition, it is implicit that the block length, which can be viewed as the number of available channel uses, is unlimited. This is not the case when the transmission power must be concentrated on a single transmission, most notably in military scenarios with adversarial conditions or delay-tolerant networks with random short encounters. A natural question arises: how much information can we transmit in a single use of the channel? We give a precise characterization of the one-shot capacity of discrete channels, defined as the maximum number of bits that can be transmitted in a single use of a channel with an error probability that does not exceed a prescribed value. This capacity definition is shown to be useful and significantly different from the zero-error problem statement.

Motivated by streaming applications with stringent delay constraints, we consider the design of online network coding algorithms with timely delivery guarantees. Assuming that the sender is providing the same data to multiple receivers over independent packet erasure channels, we focus on the case of perfect feedback and heterogeneous erasure probabilities. Based on a general analytical framework for evaluating the decoding delay, we show that existing ARQ schemes fail to ensure that receivers with weak channels are able to recover from packet losses within reasonable time. To overcome this problem, we re-define the encoding rules in order to break the chains of linear combinations that cannot be decoded after one of the packets is lost. Our results show that sending uncoded packets at key times ensures that all the receivers are able to meet specific delay requirements with very high probability.

In the field of next generation networks, the user's request for ubiquitous access has become paramount in powering the development and integration of new access technologies, thus increasing the support of ad-hoc networks as extension of infrastructure operator networks. In this paper we introduce the integration of Ad-Hoc networks in the mobility architecture of the IST Daidalos II project, whose goal is to provide the seamless mobility of nodes between different access technologies. Here we will focus on the mobility architecture of ad-hoc networks and the movement of nodes, while still providing them with the infrastructured features. To help accomplish this goal, concepts like the IEEE 802.21 and NetLMM are used and extended to support and integrate mobility in mobile ad-hoc networks. We also present the testbed implementation of this architecture and the experimental results. We show that the majority of the time spent in the handover is consumed firstly, in the scanning of the wireless environment for possible destination networks, and secondly in the ad-hoc procedures. We also show that there is a network breakpoint for both losses and delay, beyond which they become too large for normal communications.

Network coding is a highly efficient data dissemination mechanism for wireless networks. Since network coded information can only be recovered after delivering a sufficient number of coded packets, the resulting decoding delay can become problematic for delay-sensitive applications such as real-time media streaming. Motivated by this observation, we consider several algorithms that minimize the decoding delay and analyze their performance by means of simulation. The algorithms differ both in the required information about the state of the neighborspsila buffers and in the way this knowledge is used to decide which packets to combine through coding operations. Our results show that a greedy algorithm, whose encodings maximize the number of nodes at which a coded packet is immediately decodable significantly outperforms existing network coding protocols.

Recent results from statistical physics show that large classes of complex networks, both man-made and of natural origin, are characterized by high clustering properties yet strikingly short path lengths between pairs of nodes. Breaking with the traditional approach to these so called small worlds that relies mainly on graph parameters directly related to connectivity, we investigate the capacity of these networks from the perspective of network information flow. Our contribution includes upper and lower bounds for the capacity of standard and navigable small-world models based on added shortcuts, and the somewhat surprising result, that, with high probability, random rewiring does not alter the capacity of a small-world network.