On Calculating the Minimum Rate for the Cooperative Data Exchange Problem Over Fully Connected Networks

We study the cooperative data exchange problem for fully connected networks. In this problem, nodes make broadcast transmissions to recover a file consisting of K independent packets. Each node initially only possesses a subset of the packets. We propose (d,K) -Basis Searching, a deterministic polynomial-time minimization approach, to calculate the minimum rate for this problem. (d,K) -Basis Searching has strictly reduced complexity compared with the state-of-the-art algorithms, which are based on submodular function minimization. We extend our algorithm to a generalized problem: the so-called successive local omniscience problem.

Cooperative data exchange based on MDS codes

Michael Christoph Gastpar, Su Li

The coded cooperative data exchange problem is studied for the fully connected network. In this problem, each node initially only possesses a subset of the K packets making up the file. Nodes make broadcast transmissions that are received by all other nodes. The goal is for each node to recover the full file. In this paper, we present a polynomial-time deterministic algorithm to compute the optimal (i.e., minimal) number of required broadcast transmissions and to determine the precise transmissions to be made by the nodes. A particular feature of our approach is that each of the K − d transmissions is a linear combination of exactly d + 1 packets, and we show how to optimally choose the value of d. We also show how the coefficients of these linear combinations can be chosen by leveraging a connection to Maximum Distance Separable (MDS) codes.

2017

Stability and bounds in aggregate scheduling networks

Gianluca Rizzo

We study networks of FIFO nodes, where flows are constrained by arrival curves. A crucial question with these networks is: Can we derive a bound to the maximum delay that a packet can experience when traversing the network, and to the maximum queue size at each node? For a generic FIFO network these are still open issues: Some examples show that, contrary to common sense, no matter how low the maximum node utilization is in the network, it is possible to build an example of an unstable FIFO network. The importance of this issue lies in the necessity of hard bounds on packet delay and queue size, in order to enable QoS guarantees in these networks. For this reason we choose to tackle this problem through a deterministic approach, based on worst-case behavior. Our first result is the determination of a general method to derive sufficient conditions for the stability of a network: We show how, with a proper choice of the observed variables in the network and with the use of network calculus results, it is possible to derive the expression of an operator whose properties are associated to the stability of the network. Exploiting this method on a simple example, we first derive a generalization of the RIN result to heterogeneous settings and to leaky bucket constrained flows. Through some realistic examples, we show how this method allows networks to achieve a level of utilization which is more than three times larger than the best existing result. By applying the general method to three different variable classes, we derive some new sufficient conditions for stability, that perform largely better than all the main existing results, and we show how they can all be derived from the new sufficient conditions. Finally, we present a new formula for the computation of end-to-end delay bounds in a network of GR nodes.

EPFL2008

Network Coding

Mahdi Jafari Siavoshani

The demand for higher throughput and better efficiency are two important challenges for future communication networks. During the past decades, a lot of research studies have been devoted to investigating and proposing near optimal and efficient schemes and algorithms for point-to-point communication. However, in communication networks, especially in wireless systems, we require more intricate algorithms and coding schemes that are optimized for networks rather than for point-to-point communications. In recent years, the network coding paradigm has opened new opportunities for network information flow algorithms. In the first part of the thesis, we consider a non-coherent transmission scenario in a network performing randomized linear network coding. Our main goal is to find the optimal performance in terms of communication rate in such a transmission scenario and to discover the optimal coding scheme to achieve it. It is observed by Koetter et al. [1] that because the network performs an unknown linear transformation, coding over subspaces spanned by the source packets could be a reasonable coding scheme. In order to make this claim information-theoretically justified, we study a multiplicative matrix channel over a finite field with a uniform and independent distribution over the transfer matrix. The capacity for this unicast communication scenario is characterized and it is shown that coding over subspaces is indeed optimal. A similar result is also derived for the two users multiple access problem in such a non-coherent network coding scenario. We then generalize this model by proposing a more universal scenario which is based on an arbitrarily varying channel approach. This result shows the optimality of subspace coding for a wider class of matrix channels, i.e., the channels where only the rank distribution of the transfer matrix is known. Moreover, the above results show that the overhead of schemes based on coding vectors is negligible for many practical situations, i.e., the situations where the rank of the transfer matrix is concentrated around some integer number. Next, we observe that in a network performing randomized linear network coding, the coding vectors carry topological and state-dependent information about the network. Considering the subspaces spanned by the coding vectors at the relay nodes of the network, we investigate the properties of these subspaces and leverage them for some practical problems including network tomography, network management, and Byzantine attack detection. In the last part of the thesis, we consider the problem of secret key sharing among multiple nodes in a network, in the presence of a passive eavesdropper. We assume that there exists a broadcast channel from one of the trusted nodes to the rest of them (including the eavesdropper). Moreover, we assume that the trusted entities can discuss over a public channel overheard by everyone. The secrecy key generation capacity for this problem is still unknown (in general, there exist only some upper and lower bounds). For the erasure broadcast channel as well as the linear deterministic wireless broadcast channel, we propose optimal and efficient schemes that enable arbitrary number of legitimate entities to share a secret key among themselves. By extending these results, we propose achievability schemes for the non-coherent network coding broadcast channel and the state-dependent Gaussian wireless broadcast channel.

EPFL2012

Network Coding

Mahdi Jafari Siavoshani

EPFL2012