Ferkans — Interactive Telecom Tutor

How Much Data Can a Large Wireless Network Carry?

We now ask a fundamentally different question: instead of a single relay, what happens when we have a network of $n$ nodes, each wanting to communicate with some other node? How does the total throughput scale with $n$ ? This is the capacity scaling question, and the answer has profound implications for the design of large wireless networks.

The surprising result of Gupta and Kumar (2000) is that with simple multi-hop routing, the per-node throughput vanishes as $n$ grows — the network becomes congested. But the equally surprising result of Özgür, Lévêque, and Tse (2007) is that with cooperative communication (nodes acting as virtual MIMO arrays), the total throughput can scale linearly with $n$ . The gap between these results captures the fundamental tension between interference management and cooperation in large networks.

Definition:
The Random Network Model

The random network model places $n$ nodes uniformly at random in a unit square $[0, 1]^2$ . Each node wants to communicate with a randomly chosen destination. Each node has a power constraint $P$ and the signal attenuates with distance as $d^{-\alpha}$ (path-loss exponent $\alpha \geq 2$ ). The ambient noise power is $N$ .

A throughput of $T(n)$ bits per second per node is achievable if every source-destination pair can communicate at rate $T(n)$ simultaneously with vanishing error probability as $n \to \infty$ .

Transport Capacity

The total throughput-distance product of a network: $\sum_k R_k d_k$ , where $R_k$ is the rate of the $k$ -th source-destination pair and $d_k$ is the distance. Measures the network's ability to deliver information over distance.

Related: Per-Node Throughput

Per-Node Throughput

The communication rate achievable by each source-destination pair in a network of $n$ nodes. In scaling law analysis, we study how this quantity scales with $n$ .

Related: Transport Capacity

Theorem: Gupta-Kumar Scaling Law

For $n$ nodes placed uniformly in a unit square with multi-hop routing and path-loss exponent $\alpha > 2$ , the per-node throughput achievable by any scheme scales as: $T(n) = \Theta\!\left(\frac{1}{\sqrt{n \log n}}\right).$

The total network throughput is $n \cdot T(n) = \Theta(\sqrt{n / \log n})$ , which grows but sub-linearly in $n$ .

The $1/\sqrt{n}$ factor arises from a simple geometric argument: in a unit square with $n$ nodes, each node's "fair share" of the spatial bandwidth is $\sim 1/\sqrt{n}$ (since the nodes are spaced $\sim 1/\sqrt{n}$ apart). Multi-hop routing uses $\sim \sqrt{n}$ hops per packet, and each hop consumes channel resources across the network. The interference from simultaneous transmissions further limits the throughput.

The point is that as the network grows, interference becomes the bottleneck. Each transmission creates interference for all other nodes, and the aggregate interference grows with $n$ . Multi-hop routing cannot overcome this fundamental limit.

Proof

Upper bound (converse)

Divide the unit square into cells of area $\sim \log n / n$ (so each cell has $\Theta(\log n)$ nodes w.h.p.). Any transmission from a cell interferes with all neighboring cells. By bounding the spatial reuse factor (at most $\Theta(n/\log n)$ simultaneous non-interfering transmissions) and the per-transmission rate ( $\Theta(\log(1 + \text{SNR}))$ ), the total throughput is $O(\sqrt{n/\log n})$ .

Achievability via multi-hop routing

Tessellate the square into cells of side $c\sqrt{\log n/n}$ . By connectivity results, each cell is non-empty w.h.p. Route each packet through a sequence of $\Theta(\sqrt{n/\log n})$ hops, using time-division among cells with the same color in a spatial reuse pattern. Each cell transmits for a fraction $1/c'$ of the time, achieving per-hop rate $\Theta(1)$ . The per-node throughput is $1/\Theta(\sqrt{n \log n}) = \Theta(1/\sqrt{n\log n})$ .

Historical Note: Gupta and Kumar: A Sobering Result for Ad Hoc Networks

2000-2007

When Gupta and Kumar published their scaling law in 2000, the ad hoc networking community was optimistic that multi-hop wireless networks could provide scalable high-throughput communication. The $\Theta(1/\sqrt{n\log n})$ result was a cold shower: it showed that per-node throughput vanishes as the network grows, no matter how clever the routing protocol.

This result sparked a decade of research asking: "Can we do better?" The answer, as we will see, is yes — but it requires cooperation (nodes acting as MIMO arrays), not just routing (nodes acting as packet forwarders). The intellectual journey from Gupta-Kumar to Özgür-Lévêque-Tse is one of the most beautiful arcs in network information theory.

Capacity Scaling: Multi-Hop vs. Cooperative MIMO

Animated visualization of the Gupta-Kumar scaling law vs. the Ozgur-Leveque-Tse cooperative scaling result. Shows a network growing in size and how per-node throughput vanishes with multi-hop routing but stays constant with hierarchical MIMO cooperation.

Common Mistake: Scaling Laws Depend on the Network Model

Mistake:

Applying the Gupta-Kumar $\Theta(1/\sqrt{n\log n})$ scaling to networks with fixed node density (extended networks) instead of fixed area (dense networks).

Correction:

The Gupta-Kumar result is for a dense network: $n$ nodes in a fixed unit square, so the node density grows with $n$ . For extended networks (fixed density, area grows with $n$ ), the scaling law is different: $T(n) = \Theta(1/\sqrt{n})$ per node. The distinction matters because dense and extended networks have different interference structures. Always specify the network model when citing scaling results.

Theorem: Linear Scaling via Hierarchical Cooperation (Özgür-Lévêque-Tse)

For $n$ nodes in a unit square with path-loss exponent $\alpha = 2$ and power constraint $P$ , cooperative communication using hierarchical MIMO achieves a total throughput of $n \cdot T(n) = \Theta(n),$ i.e., the per-node throughput $T(n) = \Theta(1)$ is constant, independent of $n$ .

For $\alpha > 2$ , the per-node throughput scales as $T(n) = \Theta(n^{1 - \alpha/2})$ for $2 < \alpha < 3$ , and $T(n) = \Theta(1/\sqrt{n})$ for $\alpha \geq 3$ , using a combination of cooperation and multi-hop.

The key idea is hierarchical MIMO: groups of $M$ nearby nodes cooperate to form a virtual MIMO transmitter and receiver. A virtual $M \times M$ MIMO link achieves $\Theta(M)$ throughput (linear in the number of antennas). By recursively forming larger and larger cooperative groups — groups of groups — the cooperation gain scales with $n$ , overcoming the interference bottleneck that limits multi-hop routing.

Intuitively, what happens is that cooperation converts interference into useful signal: instead of each transmission creating interference for others, nodes coordinate their transmissions to avoid interference and to beamform toward intended receivers.

Proof

Level-1 cooperation

Divide $n$ nodes into $n/M$ groups of $M$ nearby nodes. Within each group, nodes exchange their messages (local cooperation phase, using $\Theta(M)$ time slots). Then each group acts as a virtual $M$ -antenna array to transmit to a destination group via distributed MIMO, achieving rate $\Theta(M)$ per group.

Hierarchical extension

The local cooperation phase itself uses MIMO communication between sub-groups. Recursively applying this at $L$ levels, with group size $M_\ell = n^{\ell/L}$ , the total cooperation overhead is $\Theta(L)$ time slots per node. The net throughput is $\Theta(n/L) = \Theta(n)$ for fixed $L$ .

Path-loss exponent $\alpha = 2$

For $\alpha = 2$ , the received power decays as $1/d^2$ , and the sum power from $M$ cooperating nodes at distance $d$ is $MP/d^2$ . The MIMO capacity scales as $\Theta(M)$ regardless of distance (in the dense network model), enabling $\Theta(1)$ per-node throughput.

🎓CommIT Contribution(2007)

Hierarchical Cooperation Achieves Linear Capacity Scaling

A. Özgür, O. Lévêque, D. N. C. Tse, G. Caire — IEEE Transactions on Information Theory

Özgür, Lévêque, and Tse showed that cooperative communication using hierarchical MIMO can achieve linear capacity scaling $\Theta(n)$ in wireless ad hoc networks, dramatically exceeding the Gupta-Kumar multi-hop limit. This result established that cooperation — not just routing — is the key to scalable wireless networks, and provided the information-theoretic foundation for cooperative MIMO and massive MIMO system design.

scaling-lawcooperationMIMOView Paper →

Capacity Scaling Laws Comparison

Scheme	Per-Node Throughput $T(n)$	Total Throughput $nT(n)$	Mechanism
Multi-hop routing (Gupta-Kumar)	$\Theta(1/\sqrt{n\log n})$	$\Theta(\sqrt{n/\log n})$	Spatial reuse + forwarding
Hierarchical MIMO ( $\alpha = 2$ )	$\Theta(1)$	$\Theta(n)$	Virtual MIMO + distributed beamforming
Hierarchical MIMO ( $2 < \alpha < 3$ )	$\Theta(n^{1-\alpha/2})$	$\Theta(n^{2-\alpha/2})$	Cooperation + multi-hop hybrid
Hierarchical MIMO ( $\alpha \geq 3$ )	$\Theta(1/\sqrt{n})$	$\Theta(\sqrt{n})$	Cooperation limited by path loss

Capacity Scaling: Multi-Hop vs. Cooperative

Compare per-node throughput scaling for multi-hop routing (Gupta-Kumar) and hierarchical cooperation (Özgür-Lévêque-Tse) as a function of network size and path-loss exponent.

Parameters

Path-Loss Exponent

\alpha

2.5

Maximum Network Size

n

1000

Quick Check

The Gupta-Kumar result shows that per-node throughput vanishes as $n \to \infty$ . What is the fundamental bottleneck that limits multi-hop routing?

Node mobility — nodes move too fast to maintain routes

Aggregate interference — each transmission interferes with all other nodes in the network

Limited node power

Routing overhead consumes all the bandwidth

Correction:

Aggregate interference — each transmission interferes with all other nodes in the network

Correct. As $n$ grows in a fixed area, the aggregate interference from simultaneous transmissions increases, limiting the SINR and hence the achievable rate per link. Multi-hop routing cannot overcome this because each hop consumes spatial resources and creates interference.

Key Takeaway

Multi-hop routing limits per-node throughput to $\Theta(1/\sqrt{n\log n})$ — it vanishes as the network grows. Cooperative communication via hierarchical MIMO achieves linear scaling $\Theta(n)$ total throughput for $\alpha = 2$ , showing that cooperation, not routing, is the key to scalable wireless networks.

Why This Matters: From Scaling Laws to Massive MIMO

The Özgür-Lévêque-Tse hierarchical cooperation result provides the information-theoretic justification for massive MIMO: by deploying many antennas at a base station, we achieve the cooperative gains predicted by the scaling law without requiring mobile users to cooperate with each other. The base station "virtualizes" the cooperation.

See Book MIMO for massive MIMO capacity results, and Book telecom, Ch. 18 for the connection between scaling laws and 5G network architecture.

Capacity Scaling Laws for Large Networks

How Much Data Can a Large Wireless Network Carry?

Definition: The Random Network Model

Transport Capacity

Per-Node Throughput

Theorem: Gupta-Kumar Scaling Law

Upper bound (converse)

Achievability via multi-hop routing

Historical Note: Gupta and Kumar: A Sobering Result for Ad Hoc Networks

Capacity Scaling: Multi-Hop vs. Cooperative MIMO

Common Mistake: Scaling Laws Depend on the Network Model

Theorem: Linear Scaling via Hierarchical Cooperation (Özgür-Lévêque-Tse)

Level-1 cooperation

Hierarchical extension

Path-loss exponent $\alpha = 2$

Hierarchical Cooperation Achieves Linear Capacity Scaling

Capacity Scaling Laws Comparison

Capacity Scaling: Multi-Hop vs. Cooperative

Parameters

Quick Check

Key Takeaway

Why This Matters: From Scaling Laws to Massive MIMO

Definition:
The Random Network Model