Cut-Set Bounds for Generalized Networks
Silas L. Fong, Raymond W. Yeung · arXiv (Cornell University) · 2013
In a network, a node is said to incur a delay if its encoding of each transmitted symbol involves only its received symbols obtained before the time slot in which the transmitted symbol is sent (hence the transmitted symbol sent in a time slot cannot depend on the received symbol obtained in the same time slot). A node is said to incur no delay if its received symbol obtained in a time slot is available for encoding its transmitted symbol sent in the same time slot. In the classical discrete memoryless network (DMN), every node incurs a delay. A well-known result for the classical DMN is the cut-set outer bound. In this paper, we generalize the model of the DMN in such a way that some nodes may incur no delay, and we obtain the cut-set bound on the capacity region of the generalized DMN. In addition, we establish the cut-set outer bound on the positive-delay region - the capacity region of the generalized DMN under the constraint that every node incurs a delay. Then, we use the cut-set bound on the positive-delay region to show that in some two-node generalized DMN, the positive-delay region is strictly smaller than the capacity region. Finally, we demonstrate that our cut-set bound on the capacity region subsumes an existing cut-set bound for the causal relay network.