Loss networks: feasible states, product-form weights, truncation, and the Erlang fixed point equations
DefinitionKellyStochasticNetworks_LossNetworkThe model of Chapter 3 of Kelly and Yudovina, Stochastic Networks: a loss network with fixed routing, and the objects its analysis needs.
There are links, link carrying circuits, and routes. The link-route incidence matrix records that a call on route requires circuits from link ; it is lost if any link has fewer free. Calls requesting route arrive as a Poisson process of rate , independently across routes, and hold their circuits for an exponentially distributed time of unit mean. With the number of calls in progress on route , the feasible states are
Four further objects are introduced.
- The product-form weight of equation (3.3), which becomes the equilibrium distribution once multiplied by the normalizing constant .
- Truncation of a Markov process to a subset of its state space: rates between states of the subset are unchanged, and a transition leaving it is suppressed. Truncating the uncapacitated network to is what produces the loss network.
- The objective of the Dual problem (3.5) of section 3.4,
to be minimized over . 4. The Erlang fixed point equations (3.7),
where is Erlang's formula. The factor removes link 's own thinning from the product, so that the argument is the reduced load offered to link : the traffic on the routes through , thinned by the blocking probability of every other link each route uses.
Formalization Note Links and routes are indexed by finite types and the incidence matrix has natural-number entries, which is the general case of section 3.3 rather than only the – case of section 3.1. Truncation is the restriction of the rate matrix to the subtype of feasible states, so a transition out of the set has no target rather than being explicitly zeroed. Erlang's formula is the definition published in mission I of this series.
import Mathlib
import Definitions.Def_KellyStochasticNetworks_Erlang
import Definitions.Def_KellyStochasticNetworks_Migration
namespace KellyStochasticNetworks
/-- The state space `S(C) = {n : A n ≤ C}` of a loss network with fixed routing: `n r` calls are
in progress on route `r`, route `r` requires `A j r` circuits from link `j`, and link `j` has
`C j` circuits. Kelly–Yudovina, *Stochastic Networks*, pp. 50 and 53. -/
def lossStates {J R : ℕ} (A : Fin J → Fin R → ℕ) (C : Fin J → ℕ) : Set (Fin R → ℕ) :=
{n | ∀ j, (∑ r, A j r * n r) ≤ C j}
/-- The unnormalized product-form weight `∏_r ν_r^{n_r} / n_r!` of equation (3.3). -/
noncomputable def lossWeight {R : ℕ} (ν : Fin R → ℝ) (n : Fin R → ℕ) : ℝ :=
∏ r, ν r ^ n r / (Nat.factorial (n r) : ℝ)
/-- A Markov process truncated to a subset `A` of its state space: the rates are unchanged
between states of `A`, and a transition leaving `A` is suppressed. Kelly–Yudovina, p. 52. -/
def truncatedRates {S : Type*} (q : S → S → ℝ) (A : Set S) : A → A → ℝ :=
fun j k => q (j : S) (k : S)
/-- The objective of the **Dual** problem (3.5) of section 3.4. -/
noncomputable def dualObjective {J R : ℕ} (A : Fin J → Fin R → ℕ) (ν : Fin R → ℝ)
(C : Fin J → ℕ) (y : Fin J → ℝ) : ℝ :=
(∑ r, ν r * Real.exp (-∑ j, y j * (A j r : ℝ))) + ∑ j, y j * (C j : ℝ)
/-- The **Erlang fixed point equations** (3.7):
`E_j = E((1 - E_j)⁻¹ ∑_r A_{jr} ν_r ∏_i (1 - E_i)^{A_{ir}}, C_j)` for every link `j`. -/
def ErlangFixedPoint {J R : ℕ} (A : Fin J → Fin R → ℕ) (ν : Fin R → ℝ) (C : Fin J → ℕ)
(E : Fin J → ℝ) : Prop :=
∀ j, E j = erlang ((1 - E j)⁻¹ * ∑ r, (A j r : ℝ) * ν r * ∏ i, (1 - E i) ^ (A i r)) (C j)
end KellyStochasticNetworks