Ferkans — Interactive Telecom Tutor

Why Relay Networks Are Hard

The relay channel — a three-node network where a relay helps communication between source and destination — has been studied since Cover and El Gamal (1979). For the simplest case (one relay), the capacity is known only in special cases (degraded relay, deterministic relay). For general relay networks with multiple relays, the gap between the best achievable rates and the best outer bounds remains significant.

The difficulty is fundamental: in a relay network, each node must simultaneously transmit and receive, creating complex dependencies between signals. The cut-set bound provides an elegant outer bound, but it is not always tight because it ignores the causality constraints that distinguish relaying from full cooperation.

Definition:
The Cut-Set Bound

For a general network with nodes $\mathcal{V}$ and channel $P_{Y_\mathcal{V} | X_\mathcal{V}}$ , the rate from source $s$ to destination $d$ is bounded by: $R \leq \max_{P_{X_\mathcal{V}}} \min_{\Omega: s \in \Omega, d \in \Omega^c} I(X_\Omega; Y_{\Omega^c} | X_{\Omega^c})$ where the minimum is over all cuts separating $s$ from $d$ , and the maximum is over all input distributions. This is the max-flow min-cut theorem of information theory.

The cut-set bound assumes that all nodes on the source side of each cut cooperate fully, ignoring the fact that relay nodes can only transmit functions of their past received signals (causality). This makes the cut-set bound generally loose for relay networks.

Theorem: The Gap for the Gaussian Relay Channel

For the Gaussian relay channel $Y_R = X_S + Z_R$ , $Y_D = X_S + X_R + Z_D$ (with power constraints $P_S, P_R$ and noise variances $\sigma^2_{R}, \sigma^2_{D}$ ):

Cut-set bound: $C \leq \min\!\left\{\frac{1}{2}\log\!\left(1 + \frac{P_S}{\sigma^2_{R}} + \frac{P_S}{\sigma^2_{D}}\right), \frac{1}{2}\log\!\left(1 + \frac{(\sqrt{P_S} + \sqrt{P_R})^2}{\sigma^2_{D}}\right)\right\}$
Compress-forward achieves: $R_{\text{CF}} \geq C - \frac{1}{2}$ bit for all parameters. The gap is at most $1/2$ bit, but the exact capacity is unknown in general.

The cut-set bound has two terms: the first is the cut between $\{S, R\}$ and $\{D\}$ (relay and source cooperate), the second is the cut between $\{S\}$ and $\{R, D\}$ (source-to-relay link). Compress-forward is nearly optimal because the relay's quantization noise adds at most $1/2$ bit of rate loss. Decode-forward can be tighter when the source-relay link is strong.

Proof

Cut-set bound

Cut 1 ( $\{S\}$ vs. $\{R,D\}$ ): $R \leq I(X_S; Y_R, Y_D | X_R)$ . For Gaussian signals: $= \frac{1}{2}\log(1 + P_S/\sigma^2_{R} + P_S/\sigma^2_{D})$ . Cut 2 ( $\{S,R\}$ vs. $\{D\}$ ): $R \leq I(X_S, X_R; Y_D)$ . For coherent Gaussian: $= \frac{1}{2}\log(1 + (\sqrt{P_S}+\sqrt{P_R})^2/\sigma^2_{D})$ .

Compress-forward gap analysis

In compress-forward, the relay quantizes $Y_R$ at distortion $\hat{\sigma^2}$ and sends the quantization index to the destination using Wyner-Ziv coding. The optimal quantization noise satisfies $(1 + P_R/(\hat{\sigma^2} + \sigma^2_{D})) = 1 + P_R/\sigma^2_{D}$ , giving $\hat{\sigma^2} = \sigma^2_{D}(1 + P_R/\sigma^2_{D})/P_R$ . The resulting rate gap to the cut-set bound is bounded by $1/2$ bit.

Definition:
Noisy Network Coding (NNC)

Noisy network coding (Lim, Kim, El Gamal, Chung, 2011) is a relaying strategy for general multi-source multi-relay networks. Each relay quantizes its received signal and maps it to a channel codeword. The destination jointly decodes the source message and all relay quantization indices. NNC achieves: $R \geq \max_{P_{X_\mathcal{V}}} \min_{\Omega} \left[I(X_\Omega; \hat{Y}_{\Omega^c}, Y_D | X_{\Omega^c}) - \sum_{j \in \Omega^c \setminus D} I(Y_j; \hat{Y}_j | X_\mathcal{V}, \hat{Y}_{j^c}, Y_D)\right]$ where $\hat{Y}_j$ is relay $j$ 's quantized observation.

NNC is the multi-relay generalization of compress-forward. It achieves within a constant gap of the cut-set bound for many network topologies. The gap grows logarithmically with the number of relays in the worst case, which means NNC is near-optimal for small networks but may leave a significant gap for large ones.

Relay Channel: Achievable Rates vs. Cut-Set Bound

Compare decode-forward, compress-forward, and the cut-set bound for the Gaussian relay channel as a function of relay position and power.

Parameters

Source power Pₛ10

Relay power Pᵣ10

Source-relay distance (fraction of S-D)0.5

Path loss exponent α3

Common Mistake: The Cut-Set Bound Is Not Always Tight

Mistake:

Assuming the cut-set bound is the capacity of a relay network because it matches an achievable scheme in some special cases.

Correction:

The cut-set bound is tight for the degraded relay channel and for networks where the relay can fully decode the source message. For non-degraded channels, especially those with interference between relay and direct paths, the cut-set bound can be strictly loose. The gap can be arbitrarily large for certain discrete memoryless relay channels. Always state whether the cut-set bound is known to be tight for the specific channel model.

Quick Check

Which relaying strategy is near-optimal (within 1/2 bit) for the general Gaussian relay channel?

Decode-forward

Amplify-forward

Compress-forward

Time-sharing between decode-forward and direct transmission

Correction:

Compress-forward

Compress-forward achieves within 1/2 bit of the cut-set bound for ALL Gaussian relay channel parameters.

Cut-Set Bound

An upper bound on achievable rates in a network, obtained by considering all cuts separating the source from the destination and bounding the information flow across each cut. The network-theoretic generalization of the channel capacity bound.

Related: The Cut-Set Bound

Noisy Network Coding (NNC)

A multi-relay coding strategy where each relay quantizes and forwards its observation. The destination jointly decodes all quantization indices and the source message. Generalizes compress-forward to multi-relay networks.

Related: Noisy Network Coding (NNC)

The General Relay Network