Wireless Networking Complete

• Flows f_(k,i),j are all nonnegative and positive flows are not assigned to nonexistent links.

• Packets that have reached the destination are not injected back into the network.

We can show the following lemma.

Lemma 7.3

If λ ∈ Λ₁ then there exists a stationary randomized algorithm to choose μ_(i,k),j(t) independent of the history of the arrivals and departures up to timeslot t, such that

$E\left(\sum _{k\in {\mathit{N}}_{\text{out}(i)}}{\mu }_{(i,k),j}(t)-\sum _{k\in {\mathit{N}}_{\text{in}(i)}}{\mu }_{(k,i),j}(t)\right)>{\lambda }_{i,j}$ (7.20)

(7.20)

for all 1 ≤ i ≤ N, and 1 ≤ j ≤ J.

The following is an informal proof. Recall that any link capacity vector in $\text{Co}(\mathit{S})$ can be achieved by a stationary randomized schedule that chooses the link ...