Abstract:
We consider the problem of network coding across multiple unicasts. We give, for wired and wireless networks, efficient polynomial time algorithms for finding optimal network codes within the class of network codes restricted to XOR coding between pairs of flows.

Abstract:
We consider a real-time streaming system where messages are created sequentially at the source, and are encoded for transmission to the receiver over a packet erasure link. Each message must subsequently be decoded at the receiver within a given delay from its creation time. The goal is to construct an erasure correction code that achieves the maximum message size when all messages must be decoded by their respective deadlines under a specified set of erasure patterns (erasure model). We present an explicit intrasession code construction that is asymptotically optimal under erasure models containing a limited number of erasures per coding window, per sliding window, and containing erasure bursts of a limited length.

Abstract:
In this paper we consider the problem of secure network coding where an adversary has access to an unknown subset of links chosen from a known collection of links subsets. We study the capacity region of such networks, commonly called "wiretap networks", subject to weak and strong secrecy constraints, and consider both zero-error and asymptotically zero-error communication. We prove that in general discrete memoryless networks modeled by discrete memoryless channels, the capacity region subject to strong secrecy requirement and the capacity region subject to weak secrecy requirement are equal. In particular, this result shows that requiring strong secrecy in a wiretap network with asymptotically zero probability of error does not shrink the capacity region compared to the case of weak secrecy requirement. We also derive inner and outer bounds on the network coding capacity region of wiretap networks subject to weak secrecy constraint, for both zero probability of error and asymptotically zero probability of error, in terms of the entropic region.

Abstract:
This paper considers the problem of defining a measure of redundant information that quantifies how much common information two or more random variables specify about a target random variable. We discussed desired properties of such a measure, and propose new measures with some desirable properties.

Abstract:
We consider the problem of optimally allocating a given total storage budget in a distributed storage system. A source has a data object which it can code and store over a set of storage nodes; it is allowed to store any amount of coded data in each node, as long as the total amount of storage used does not exceed the given budget. A data collector subsequently attempts to recover the original data object by accessing each of the nodes independently with some constant probability. By using an appropriate code, successful recovery occurs when the total amount of data in the accessed nodes is at least the size of the original data object. The goal is to find an optimal storage allocation that maximizes the probability of successful recovery. This optimization problem is challenging because of its discrete nature and nonconvexity, despite its simple formulation. Symmetric allocations (in which all nonempty nodes store the same amount of data), though intuitive, may be suboptimal; the problem is nontrivial even if we optimize over only symmetric allocations. Our main result shows that the symmetric allocation that spreads the budget maximally over all nodes is asymptotically optimal in a regime of interest. Specifically, we derive an upper bound for the suboptimality of this allocation and show that the performance gap vanishes asymptotically in the specified regime. Further, we explicitly find the optimal symmetric allocation for a variety of cases. Our results can be applied to distributed storage systems and other problems dealing with reliability under uncertainty, including delay tolerant networks (DTNs) and content delivery networks (CDNs).

Abstract:
We examine the problem of allocating a given total storage budget in a distributed storage system for maximum reliability. A source has a single data object that is to be coded and stored over a set of storage nodes; it is allowed to store any amount of coded data in each node, as long as the total amount of storage used does not exceed the given budget. A data collector subsequently attempts to recover the original data object by accessing only the data stored in a random subset of the nodes. By using an appropriate code, successful recovery can be achieved whenever the total amount of data accessed is at least the size of the original data object. The goal is to find an optimal storage allocation that maximizes the probability of successful recovery. This optimization problem is challenging in general because of its combinatorial nature, despite its simple formulation. We study several variations of the problem, assuming different allocation models and access models. The optimal allocation and the optimal symmetric allocation (in which all nonempty nodes store the same amount of data) are determined for a variety of cases. Our results indicate that the optimal allocations often have nonintuitive structure and are difficult to specify. We also show that depending on the circumstances, coding may or may not be beneficial for reliable storage.

Abstract:
One major open problem in network coding is to characterize the capacity region of a general multi-source multi-demand network. There are some existing computational tools for bounding the capacity of general networks, but their computational complexity grows very quickly with the size of the network. This motivates us to propose a new hierarchical approach which finds upper and lower bounding networks of smaller size for a given network. This approach sequentially replaces components of the network with simpler structures, i.e., with fewer links or nodes, so that the resulting network is more amenable to computational analysis and its capacity provides an upper or lower bound on the capacity of the original network. The accuracy of the resulting bounds can be bounded as a function of the link capacities. Surprisingly, we are able to simplify some families of network structures without any loss in accuracy.

Abstract:
The secrecy capacity of a network, for a given collection of permissible wiretap sets, is the maximum rate of communication such that observing links in any permissible wiretap set reveals no information about the message. This paper considers secure network coding with nonuniform or restricted wiretap sets, for example, networks with unequal link capacities where a wiretapper can wiretap any subset of $k$ links, or networks where only a subset of links can be wiretapped. Existing results show that for the case of uniform wiretap sets (networks with equal capacity links/packets where any $k$ can be wiretapped), the secrecy capacity is given by the cut-set bound, and can be achieved by injecting $k$ random keys at the source which are decoded at the sink along with the message. This is the case whether or not the communicating users have information about the choice of wiretap set. In contrast, we show that for the nonuniform case, the cut-set bound is not achievable in general when the wiretap set is unknown, whereas it is achievable when the wiretap set is made known. We give achievable strategies where random keys are canceled at intermediate non-sink nodes, or injected at intermediate non-source nodes. Finally, we show that determining the secrecy capacity is a NP-hard problem.

Abstract:
Regenerating codes allow distributed storage systems to recover from the loss of a storage node while transmitting the minimum possible amount of data across the network. We present a systematic computer search for optimal systematic regenerating codes. To search the space of potential codes, we reduce the potential search space in several ways. We impose an additional symmetry condition on codes that we consider. We specify codes in a simple alternative way, using additional recovered coefficients rather than transmission coefficients and place codes into equivalence classes to avoid redundant checking. Our main finding is a few optimal systematic minimum storage regenerating codes for $n=5$ and $k=3$, over several finite fields. No such codes were previously known and the matching of the information theoretic cut-set bound was an open problem.

Abstract:
We analyze the achievable rate in interference-free wireless networks with physical layer fading channels and orthogonal multiple access. As a starting point, the point-to-point channel is considered. We find the optimal physical and network layer rate trade-off which maximizes the achievable overall rate for both a fixed rate transmission scheme and an improved scheme based on multiple virtual users and superposition coding. These initial results are extended to the network setting, where, based on a cut-set formulation, the achievable rate at each node and its upper bound are derived. We propose a distributed optimization algorithm which allows to jointly determine the maximum achievable rate, the optimal physical layer rates on each network link, and an opportunistic back-pressure-type routing strategy on the network layer. This inherently justifies the layered architecture in existing wireless networks. Finally, we show that the proposed layered optimization approach can achieve almost all of the ergodic network capacity in high SNR.