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
2171844485 2104496515 2129119419 108696806
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 in-network computation of an arbitrary function over an arbitrary communication network. A network with capacity constraints on the links is given. Some nodes in the network generate data, e.g., like sensor nodes in a sensor network. An arbitrary function of this distributed data is to be obtained at a terminal node. The structure of the function is described by a given computation schema, which in turn is represented by a directed tree. We design computing and communicating schemes to obtain the function at the terminal at the maximum rate. For this, we formulate linear programs to determine network flows that maximize the computation rate. We then develop a fast combinatorial primal-dual algorithm to obtain near-optimal solutions to these linear programs. As a subroutine for this, we develop an algorithm for finding the minimum cost embedding of a tree in a network with any given set of link costs. We then briefly describe extensions of our techniques to the cases of multiple terminals wanting different functions, multiple computation schemas for a function, computation with a given desired precision, and to networks with energy constraints at nodes. 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. This book contains a thorough discussion of the classical topics in information theory together with the first comprehensive treatment of network coding, a subject first emerged under information theory in the mid 1990's that has now diffused into coding theory, computer networks, wireless communications, complexity theory, cryptography, graph theory, etc. With a large number of examples, illustrations, and original problems, this book is excellent as a textbook or reference book for a senior or graduate level course on the subject, as well as a reference for researchers in related fields.