In this paper, the problem of transmitting two symbols from two sources to multiple destinations using network coding is considered for general directed acyclic graphs. When all destination nodes are interested in both symbols, the feasibility of this problem is characterized by the classic min-cut max-flow theorem. This work focuses on the scenarios in which each destination is interested in one source symbol. If no coding is allowed at intermediate nodes, the feasibility of this traditional two-session routing problem is equivalent to the existence of two edge-disjoint sets of paths. Similarly, in this paper, it is proven that the feasibility of this inter-session network coding problem is equivalent to the existence of multiple sets of paths with controlled edge overlaps. In particular, for the degenerate case of two sources and two destinations, it is proven that a binary field is sufficient and an optimal network coding solution must be of one of the three different forms, which includes the well-studied butterfly graph as a special case.
展开▼
