Lemma 3.1, p. 1940 — the closure of C′ is {a : ∃ f ∈ F_a, c ∈ co(S), M⁻¹f̂ ≤ c}
ProvedConstrainedQueueing.MaxThroughput.lemma_3_1closuremulticommodity-flowp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stability-region
Consider a constrained queueing network with service probabilities , and let be the diagonal matrix with entries . Let be the set of -admissible multicommodity flows, the total flow, and the set of arrival-rate vectors defined on p. 1940 (see the Model definition).
Lemma 3.1. The closure of is
Thus the strict inequalities in the definition of become non-strict on the boundary. The lemma identifies the outer bound of the stability region in a form that no stationary policy can exceed.
Formalization Note. Rate vectors are indexed by the queues with ; the condition is part of both sides (the paper's rate vectors are nonnegative). is written componentwise as .
Preamble
import Mathlib import Definitions.Def_ConstrainedQueueing_MaxThroughput_MarkovChain import Definitions.Def_ConstrainedQueueing_MaxThroughput_Model
Formal statement
namespace ConstrainedQueueing.MaxThroughput
/-- Lemma 3.1 (p. 1940): `C̄′ = {a ≥ 0 : ∃ f ∈ F_a, ∃ c ∈ co(S), M⁻¹ f̂ ≤ c}`. -/
theorem lemma_3_1 {L N J : ℕ} (net : Network L N J) (hm : ∀ i, 0 < net.m i) :
closure (Cprime net) =
{a | (∀ p, 0 ≤ a p) ∧ ∃ f, IsAdmissibleFlow net a f ∧
∃ c ∈ coS net, ∀ i, fhat f i / net.m i ≤ c i} := by sorry
end ConstrainedQueueing.MaxThroughput
Source
Tassiulas and Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks, IEEE Trans. Automat. Control 37(12) (1992), p. 1940, Lemma 3.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.