The non-uniform demand network coding problem is posed as a single-source and multiple-sink network transmission problem where the sinks may have heterogeneous demands. In contrast with multicast problems, non-uniform demand problems are concerned with the amounts of data received by each sink, rather than the specifics of the received data. In this work, we enumerate non-uniform network demand scenarios under which network coding solutions can be found in polynomial time. This is accomplished by relating the demand problem with the graph coloring problem, and then applying results from the strong perfect graph theorem to identify coloring problems which can be solved in polynomial time. This characterization of efficiently-solvable non-uniform demand problems is an important step in understanding such problems, as it allows us to better understand situations under which the NP-complete problem might be tractable.
We briefly mention some results regarding the multiple multicast connections problem, since achievable solutions for such problems are also achievable for the non-uniform demand problem with the same demanded rates. (Of course, the reverse is not always true.) Many of these results consider the case of two sinks. @cite_10 , after enumeration of all possible scenarios, the authors conclude that in the case of two sinks with differing rates, linear coding is sufficient. The same conclusion is made in @cite_3 , although the authors use a different approach which considers a path-based enumeration. A characterization of the achievable data rate region using network coding is given for the two sink case. For more than two sinks, conditions under which solutions exist for the multiple connections problem have not been enumerated.
@cite_10 @cite_3
2152664953 1668074974
Network coding shows that the data rate can be increased if information is allowed to be encoded in the network nodes. The recent work of S.-Y.R. (see IEEE Trans. Inform. Theory, vol.49, no.2, p.371-81, 2003) and R. Koetter and M. Medard (see Proc. INFOCOM, 2002) shows that linear network coding is sufficient for a single source multicast network. The restrictiveness of the use of linear code is still an unknown in the general multisource multicast network. We characterize the achievable information rate region for a single source node multi-source multicast network with two sinks. We further show that linear coding is sufficient for achieving the maximum network capacity. We consider a communication network with a single source that has a set of messages and two terminals where each terminal is interested in an arbitrary subset of messages at the source. A tight capacity region for this problem is demonstrated. We show by a simple graph-theoretic procedure that any such problem can be solved by performing network coding on the subset of messages that are requested by both the terminals and that routing is sufficient for transferring the remaining messages.