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.
A technique which we use is that of transmitting data along paths, or through flows. This approach has been widely used in the network coding literature, and has enabled many significant results. In Jaggi @cite_8 , the polynomial-time algorithms for multicast problems rely on the concept of sending data down [perhaps overlapping] paths. @cite_16 , Fragouli and Soljanin give a decomposition of networks into flows, in order to model data transmission in a network more simply. Using this decomposition and a graph coloring formulation, alphabet size bounds for any network code are then proven. Although the flow-based and path-based approaches are similar in many ways, the two techniques differ in that the flow-based approach creates a new flow every time a piece of data is transformed by coding, whereas the path-based approach keeps track of each piece of data as it is sent individually down a path, even if any transformations get applied to the data. We shall use a path-based approach.
@cite_16 @cite_8
2134859306 2123562143
We propose a method to identify structural properties of multicast network configurations, by decomposing networks into regions through which the same information flows. This decomposition allows us to show that very different networks are equivalent from a coding point of view, and offers a means to identify such equivalence classes. It also allows us to divide the network coding problem into two almost independent tasks: one of graph theory and the other of classical channel coding theory. This approach to network coding enables us to derive the smallest code alphabet size sufficient to code any network configuration with two sources as a function of the number of receivers in the network. But perhaps the most significant strength of our approach concerns future network coding practice. Namely, we propose deterministic algorithms to specify the coding operations at network nodes without the knowledge of the overall network topology. Such decentralized designs facilitate the construction of codes that can easily accommodate future changes in the network, e.g., addition of receivers and loss of links The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to re-encode the information they receive. We demonstrate examples of networks where the achievable rates obtained by coding at intermediate nodes are arbitrarily larger than if coding is not allowed. We give deterministic polynomial time algorithms and even faster randomized algorithms for designing linear codes for directed acyclic graphs with edges of unit capacity. We extend these algorithms to integer capacities and to codes that are tolerant to edge failures.