We consider a communication network consisting of nodes and directed edges that connect the nodes. The network may contain cycles. The communications are slotted where the duration of each time slot is equal to the maximum propagation delay experienced by the edges. The edges with negligible delays are allowed to be operated before the other edges in each time slot. For any pair of adjacent edges @math and @math , where @math terminates at node @math and @math originates from node @math , we say @math incurs zero delay on @math if @math is operated before @math ; otherwise, we say @math incurs a unit delay on @math . In the classical model, every edge incurs a unit delay on every adjacent edge and the cut-set bound is a well-known outer bound on the capacity region. In this paper, we investigate the multimessage multicast network (MMN) consisting of independent channels, where each channel is associated with a set of edges and each edge may incur zero delay on some other edges. Our result reveals that the capacity region of the MMN with independent channels and zero-delay edges lies within the classical cut-set bound despite a violation of the unit-delay assumption.
The main contribution of this paper is twofold: First, we establish an edge-delay model for the MMN consisting of independent channels which may contain zero-delay edges. Our model subsumes the classical model which assumes that every edge incurs a unit delay on every adjacent edge. Second, we prove that for each DM-MMN consisting of independent channels with zero-delay edges, the capacity region always lies within the classical cut-set bound despite a violation of the classical unit-delay assumption. Combining our cut-set bound result with existing achievability results from network equivalence theory @cite_6 and noisy network coding (NNC) @cite_0 @cite_7 , we establish the tightness of our cut-set bound under our edge-delay model for the MMN with independent DMCs, and hence fully characterize the capacity region. More specifically, we show that the capacity region is the same as the set of achievable rate tuples under the classical unit-delay assumption. The capacity region result is then generalized to the MMN consisting of independent additive white Gaussian noise (AWGN) channels with zero-delay edges.
@cite_0 @cite_7 @cite_6
2156567124 2132100261 2054405836
This paper deals with the problem of multicasting a set of discrete memoryless correlated sources (DMCS) over a cooperative relay network. Necessary conditions with cut-set interpretation are presented. A Joint source-Wyner-Ziv encoding sliding window decoding scheme is proposed, in which decoding at each receiver is done with respect to an ordered partition of other nodes. For each ordered partition a set of feasibility constraints is derived. Then, utilizing the submodular property of the entropy function and a novel geometrical approach, the results of different ordered partitions are consolidated, which lead to sufficient conditions for our problem. The proposed scheme achieves operational separation between source coding and channel coding. It is shown that sufficient conditions are indeed necessary conditions in two special cooperative networks, namely, Aref network and finite-field deterministic network. Also, in Gaussian cooperative networks, it is shown that reliable transmission of all DMCS whose Slepian-Wolf region intersects the cut-set bound region within a constant number of bits, is feasible. In particular, all results of the paper are specialized to obtain an achievable rate region for cooperative relay networks which includes relay networks and two-way relay networks. A noisy network coding scheme for communicating messages between multiple sources and destinations over a general noisy network is presented. For multi-message multicast networks, the scheme naturally generalizes network coding over noiseless networks by Ahlswede, Cai, Li, and Yeung, and compress-forward coding for the relay channel by Cover and El Gamal to discrete memoryless and Gaussian networks. The scheme also extends the results on coding for wireless relay networks and deterministic networks by Avestimehr, Diggavi, and Tse, and coding for wireless erasure networks by Dana, Gowaikar, Palanki, Hassibi, and Effros. The scheme involves lossy compression by the relay as in the compress-forward coding scheme for the relay channel. However, unlike previous compress-forward schemes in which independent messages are sent over multiple blocks, the same message is sent multiple times using independent codebooks as in the network coding scheme for cyclic networks. Furthermore, the relays do not use Wyner-Ziv binning as in previous compress-forward schemes, and each decoder performs simultaneous decoding of the received signals from all the blocks without uniquely decoding the compression indices. A consequence of this new scheme is that achievability is proved simply and more generally without resorting to time expansion to extend results for acyclic networks to networks with cycles. The noisy network coding scheme is then extended to general multi-message networks by combining it with decoding techniques for the interference channel. For the Gaussian multicast network, noisy network coding improves the previously established gap to the cutset bound. We also demonstrate through two popular Gaussian network examples that noisy network coding can outperform conventional compress-forward, amplify-forward, and hash-forward coding schemes. A family of equivalence tools for bounding network capacities is introduced. Given a network N with node set V, the capacity of N is a set of non-negative vectors with elements corresponding to all possible multicast connections in N; a vector ℜ is in the capacity region for N if and only if it is possible to simultaneously and reliably establish all multicast connections across N at the given rates. Any other demand type with independent messages is a special case of this multiple multicast problem, and is therefore included in the given rate region. In Part I, we show that the capacity of a network N is unchanged if any independent, memoryless, point-to-point channel in N is replaced by a noiseless bit pipe with throughput equal to the removed channel's capacity. It follows that the capacity of a network comprised entirely of such point-to-point channels equals the capacity of an error-free network that replaces each channel by a noiseless bit pipe of the corresponding capacity. A related separation result was known previously for a single multicast connection over an acyclic network of independent, memoryless, point-to-point channels; our result treats general connections (e.g., a collection of simultaneous unicasts) and allows cyclic or acyclic networks.