Search

In this work, we study the computational perspective of network coding, focusing on two issues. First, we address the computational complexity of finding a network code for acyclic multicast networks. Second, we address the issue of reducing the amount of computation performed by network nodes. In particular, we consider the problem of finding a network code with the minimum possible number of encoding nodes, i.e., nodes that generate new packets by performing algebraic operations on packets received over incoming links. We present a deterministic algorithm that finds a feasible network code for a multicast network over an underlying graph G(V, E) in time O([absolute value of E]kh + [absolute value of V][k.sup.2]h.sup.2] + [h.sup.3][k.sup.3](k + h)), where k is the number of destinations and h is the number of packets. Our algorithm improves the best known running time for network code construction. In addition, our algorithm guarantees that the number of encoding nodes in the obtained network code is upper-bounded by O([h.sup.3][k.sup.2]). Next, we address the problem of finding integral and fractional network codes with the minimum number of encoding nodes. We prove that in the majority of settings this problem is NP-hard. However, we show that if h = O(1), h = O(1), and the underlying communication graph is acyclic, then there exists an algorithm that solves this problem in polynomial time. Index Terms--Algorithms, computational perspective, encoding complexity, fractional network coding, integer network coding, multicast connections.

We study broadcast systems that distribute a series of data updates to a large number of passive clients. The updates are sent over a broadcast channel in the form of discrete packets. We assume that clients periodically access the channel to obtain the most recent update. Such scenarios arise in many practical applications, such as distribution of traffic information and market updates to mobile wireless devices. Our goal is to design broadcast schedules that minimize the waiting time, i.e., the amount of time the client needs to wait in order to obtain the most recent update. We assume that each client has a different access pattern depending on the channel conditions, computing power, and storage capabilities. We introduce and analyze optimal universal schedules that guarantee low waiting time for any client, regardless of its behavior. Index Terms--Broadcast systems, data updates, universal schedules, waiting time.

Network coding substantially increases network throughput. But since it involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up contaminating all the information reaching a destination, preventing decoding. This paper introduces distributed polynomial-time rate-optimal network codes that work in the presence of Byzantine nodes. We present algorithms that target adversaries with different attacking capabilities. When the adversary can eavesdrop on all links and jam [z.sub.O] finks, our first algorithm achieves a rate of C--2[z.sub.O], where C is the network capacity. In contrast, when the adversary has limited eavesdropping capabilities, we provide algorithms that achieve the higher rate of C--[z.sub.O]. Our algorithms attain the optimal rate given the strength of the adversary. They are information-theoretically secure. They operate in a distributed manner, assume no knowledge of the topology, and can be designed and implemented in polynomial time. Furthermore, only the source and destination need to be modified; nonmalicious nodes inside the network are oblivious to the presence of adversaries and implement a classical distributed network code. Finally, our algorithms work over wired and wireless networks. Index Terms--Byzantine adversaries, distributed network error-correcting codes, eavesdroppers, information-theoretically optimal, list decoding, polynomial-time algorithms.

Let C = {[x.sub.1],..., [x.sub.N]} [subset] [{0.1 }.sup.n] be an [n, N] binary error correcting code (not necessarily linear). Let e [member of] [{0, 1}.sup.n] be an error vector. A codeword x [member of] C is said to be disturbed by the error e if the closest codeword to x [direct sum] e is no longer x. Let [A.sub.e] be the subset of codewords in C that are disturbed by e. In this work, we study the size of [A.sub.e] in random codes C (i.e., codes in which each codeword [x.sub.i] is chosen uniformly and independently at random from [{0, 1}.sup.n]). Using recent results of Vu [Random Structures and Algorithms, vol. 20, no. 3, pp. 262-316, 2002] on the concentration of non-Lipschitz functions, we show that [absolute value of [A.sub.e]] is strongly concentrated for a wide range of values of N and [parallel]e[parallel]. We apply this result in the study of communication channels we refer to as oblivious. Roughly speaking, a channel W(y|x) is said to be oblivious if the error distribution imposed by the channel is independent of the transmitted codeword x. A family of channels W is said to be oblivious if every member W of the family is oblivious. In this work, we define oblivious and partially oblivious families of (not necessarily memoryless) channels and analyze their capacity. When considering the capacity of a family of channels W, one must address the design of error correcting codes which allow communication under the uncertainty of which channel W [member of] W is actually used. The oblivious channels we define have connections to Arbitrarily Varying Channels with state constraints. Index Terms--Arbitrarily varying channels, capacity, channel coding, channel uncertainty.

In the multicast network coding problem, a source s needs to deliver h packets to a set of k terminals over an underlying communication network G. The nodes of the multicast network can be broadly categorized into two groups. The first group incudes encoding nodes, i.e., nodes that generate new packets by combining data received from two or more incoming links. The second group includes forwarding nodes that can only duplicate and forward the incoming packets. Encoding nodes are, in general, more expensive due to the need to equip them with encoding capabilities. In addition, encoding nodes incur delay and increase the overall complexity of the network. Accordingly, in this paper, we study the design of multicast coding networks with a limited number of encoding nodes. We prove that in a directed acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded by [h.sup.3][k.sup.2]. Namely, we present (efficiently constructible) network codes that achieve capacity in which the total number of encoding nodes is independent of the size of the network and is bounded by [h.sup.3][k.sup.2]. We show that the number of encoding nodes may depend both on h and k by presenting acyclic coding networks that require [OMEGA]([h.sup.2k]) encoding nodes. In the general case of coding networks with cycles, we show that the number of encoding nodes is limited by the size of the minimum feedback link set, i.e., the minimum number of links that must be removed from the network in order to eliminate cycles. We prove that the number of encoding nodes is bounded by (2B + 1)[h.sup.3][k.sup.2], where B is the minimum size of a feedback link set. Finally, we observe that determining or even crudely approximating the minimum number of required encoding nodes is an NP-hard problem. Index Terms--Coding networks, encoding links, encoding nodes, multicast, network coding.