We consider the over an error-free broadcast network in which a source generates a set of messages and there are multiple receivers, each holding a set of functions of source messages in its cache, called the , and demands to know another set of functions of messages, called the . Cognizant of the receivers' , the source aims to satisfy the demands of each receiver by making coded transmissions, called a . The objective is to minimize the number of such transmissions required. The restriction a receiver's demands pose on the code is represented via a constraint called the and obtain a code using the constructed using these constraints. Bounds on the size of an optimal code based on the parameters of the confusion graph are presented. Next, we consider the case of erroneous transmissions and provide a necessary and sufficient condition that an FIC must satisfy for correct decoding of desired functions at each receiver and obtain a lower bound on the length of an error-correcting FIC.
Network coding problem has garnered much attention of the research community, see @cite_10 and references therein. The main advantage network coding offers is improvement in throughput by exploiting the fact that intermediate nodes can perform computation on incoming information rather than merely route them. Though ICP falls as a special case of a more general network coding problem, equivalence between the two has been shown in @cite_7 @cite_21 , , every index coding problem can be converted to an instance of network coding problem and vice versa. Network coding capacity by examining the corresponding index coding problem was studied in @cite_21 . The in-network function computation problem comprises source nodes generating messages, intermediate nodes performing computation on incoming information and sink nodes seeking functions of source messages @cite_27 @cite_16 . The aim is to maximize the frequency of target function computation per network use @cite_16 . This motivated to study ICP where clients' demands may also include functions of messages.
@cite_7 @cite_21 @cite_27 @cite_16 @cite_10
2129119419 2171844485 2089001139 2106831077
The following network computing problem is considered. Source nodes in a directed acyclic network generate independent messages and a single receiver node computes a target function f of the messages. The objective is to maximize the average number of times f can be computed per network usage, i.e., the “computing capacity”. The network coding problem for a single-receiver network is a special case of the network computing problem in which all of the source messages must be reproduced at the receiver. For network coding with a single receiver, routing is known to achieve the capacity by achieving the network min-cut upper bound. We extend the definition of min-cut to the network computing problem and show that the min-cut is still an upper bound on the maximum achievable rate and is tight for computing (using coding) any target function in multi-edge tree networks. It is also tight for computing linear target functions in any network. We also study the bound's tightness for different classes of target functions. In particular, we give a lower bound on the computing capacity in terms of the Steiner tree packing number and a different bound for symmetric functions. We also show that for certain networks and target functions, the computing capacity can be less than an arbitrarily small fraction of the min-cut bound. The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messages X= x1,...,xk and a set of receivers R. Each receiver (x,H) in R needs to obtain a message x X and has prior side information consisting of a subset H of X . The sender uses a noiseless communication channel to broadcast encoding of messages in X to all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show that vector linear codes outperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions. We consider a group of n wireless clients and a set of k messages. Each client initially holds a subset of messages and is interested in an arbitrary subset of messages. Each client cooperates with other clients to obtain the set of messages it wants by exchanging instantly decodable network coded (IDNC) packets. This problem setting is known as the cooperative index coding problem. Clients are assumed to be connected through an arbitrary topology. In the absence of any known algorithm to complete the exchange of packets for general network topologies, we propose a greedy algorithm to satisfy the demands of all the clients with the aim of reducing the mean completion time. Our algorithm, in a completely distributed fashion, decides which subset of clients should transmit at each round of transmission and which messages should be coded together by each transmitting client to generate an IDNC packet. The algorithm encourages transmissions which are decodable for a larger number of clients and attempts to avoid collisions. We evaluate the performance of our algorithm via numerical experiments. 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 links, our first algorithm achieves a rate of , where is the network capacity. In contrast, when the adversary has limited eavesdropping capabilities, we provide algorithms that achieve the higher rate of . 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.