Skip to main content

Notation and results

Operators​

SymbolDefinitionName
f⊗gf \otimes ginf⁡0≤s≤t{f(t−s)+g(s)}\inf_{0 \le s \le t} \{ f(t-s) + g(s) \}Min-plus convolution
f⊘gf \oslash gsup⁡u≥0{f(t+u)−g(u)}\sup_{u \ge 0} \{ f(t+u) - g(u) \}Min-plus deconvolution
f‾\overline{f}inf⁡n≥0f(n)\inf_{n \ge 0} f^{(n)}Sub-additive closure
h(α,β)h(\alpha,\beta)sup⁡s≥0inf⁡{τ≥0:α(s)≤β(s+τ)}\sup_{s \ge 0} \inf \{ \tau \ge 0 : \alpha(s) \le \beta(s+\tau) \}Horizontal deviation
v(α,β)v(\alpha,\beta)sup⁡s≥0{α(s)−β(s)}\sup_{s \ge 0} \{ \alpha(s) - \beta(s) \}Vertical deviation

Standard curves​

SymbolDefinitionUse
γr,b(t)\gamma_{r,b}(t)b+rtb + rt for t>0t > 0, 00 at t=0t = 0Token-bucket arrival curve
λC(t)\lambda_C(t)CtCtPeak rate / constant-rate link
βR,T(t)\beta_{R,T}(t)R[t−T]+R[t-T]^+Rate-latency service curve
δT(t)\delta_T(t)00 for t≤Tt \le T, +∞+\infty otherwisePure delay
L⌈(t+J)/P⌉L\lceil (t+J)/P \rceilStaircasePeriodic stream with jitter JJ

Definitions​

ConceptCondition
Arrival curve α\alphaR≤R⊗αR \le R \otimes \alpha
Service curve β\betaR∗≥R⊗βR^* \ge R \otimes \beta
Strict service curve β\betaOutput ≥β(u)\ge \beta(u) over any backlogged period of length uu
Greedy shaper σ\sigmaR∗=R⊗σR^* = R \otimes \sigma

Fundamental results​

ResultStatement
Backlog boundR(t)−R∗(t)≤v(α,β)R(t) - R^*(t) \le v(\alpha,\beta)
Delay boundd(t)≤h(α,β)d(t) \le h(\alpha,\beta)
Output arrival curveα∗=α⊘β\alpha^* = \alpha \oslash \beta
Concatenationβ1,2=β1⊗β2\beta_{1,2} = \beta_1 \otimes \beta_2
Blind multiplexingβ1=[β−α2]+\beta_1 = [\beta - \alpha_2]^+ (β\beta strict)
FIFO multiplexingβ1θ(t)=[β(t)−α2(t−θ)]+1{t>θ}\beta_1^\theta(t) = [\beta(t) - \alpha_2(t-\theta)]^+ \mathbf{1}_{\{t>\theta\}}, θ≥0\theta \ge 0

Closed forms (token bucket, rate-latency, r≤Rr \le R)​

QuantityValue
Delay boundT+b/RT + b/R
Backlog boundb+rTb + rT
Output arrival curveγr, b+rT\gamma_{r,\, b + rT}
Tandem of nn serversβmin⁡iRi, ∑iTi\beta_{\min_i R_i,\, \sum_i T_i}
Blind residualβC−r2, (CT+b2)/(C−r2)\beta_{C - r_2,\, (CT + b_2)/(C - r_2)}

Non-preemptive static priority (class kk, rate CC)​

dk=BH+Llo+BkC−RH+tproc,RH+Rk≤C,d_k = \frac{B_H + L_{lo} + B_k}{C - R_H} + t_{proc}, \qquad R_H + R_k \le C, b′=b+r dk,D=∑h∈Pdk(h).b' = b + r\, d_k, \qquad D = \sum_{h \in \mathcal{P}} d_k^{(h)} .

BH,RHB_H, R_H: aggregate burst and rate of higher-priority classes; LloL_{lo}: largest lower-priority frame; Bk,RkB_k, R_k: aggregate burst and rate of class kk; b′b': output burst; DD: end-to-end bound over path P\mathcal{P} (Total Flow Analysis).

Time-Aware Shaper window (no guard band)​

Gate open ww in every cycle cc, link rate CC:

β(t)=Cwc [ t−(c−w) ]+.\beta(t) = \frac{Cw}{c}\, [\, t - (c - w) \,]^+ .