Lemma 3.5, p. 14 — at most Ry packets on g in every y-frame for T ≤ y ≤ 2T − 1 implies the same for all y ≥ T
ProvedPacketRouting.CongDil.lemma_3_5p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1packet-routingscheduling
Fix any schedule of a finite set of packets (valid or not), an edge , a real number and a frame size . For a frame of consecutive steps starting at step , let be the number of packets that cross at some step of the frame.
Lemma 3.5. If
then for every start and every .
The lemma reduces the frame-congestion bounds of the refinement step to frames of a bounded range of sizes; it is used several times in the proof of Theorem 3.4.
Formalization Note The hypothesis is implicit on the page: for the range is empty and the conclusion fails. The range is written .
Preamble
import Mathlib import Definitions.Def_PacketRouting_CongDil_Timetable
Formal statement
namespace PacketRouting.CongDil
/-- Lemma 3.5 (Leighton–Maggs–Rao, p. 14): in any schedule (valid or not), if for every `y`
with `T ≤ y ≤ 2T − 1` at most `R y` packets use edge `g` in every `y`-frame, then at most `R y`
packets use `g` in every `y`-frame for every `y ≥ T`. -/
theorem lemma_3_5 {P E : Type*} [Fintype P] {path : P → List E} (τ : Timetable path)
(g : E) (R : ℝ) (T : ℕ) (hT : 1 ≤ T)
(h : ∀ y t : ℕ, T ≤ y → y < 2 * T → (τ.frameCount g t y : ℝ) ≤ R * y) :
∀ y t : ℕ, T ≤ y → (τ.frameCount g t y : ℝ) ≤ R * y := by sorry
end PacketRouting.CongDil
Source
Leighton, Maggs & Rao, Packet routing and job-shop scheduling in O(congestion + dilation) steps, authors' manuscript (preprint of Combinatorica 14 (1994), DOI 10.1007/BF01215349), p. 14, Lemma 3.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.