api.snc

snc_thetaopt(fun, thetamax)

Minimize a Chernoff bound over the free parameter theta

Every bound in the snc family holds for each theta > 0 for which the arrival MGF is finite and the station is stable, so the reported bound is the infimum over theta. FUN is evaluated on a logarithmic grid, non-finite values (a diverging MGF, an unstable leftover rate) are discarded, and the best grid point is refined by fminbnd in log10(theta). The two-stage search is used because the feasible set is an interval whose endpoints are not known in closed form once envelopes are composed, and a plain fminbnd over the whole range would step into the infeasible region.

Parameters:

  • fun – Handle theta -> scalar objective to minimize

  • thetamax – Optional upper end of the search range, default 1e3

Returns:

val – Minimum found, Inf if no feasible theta exists theta: Minimizing theta, NaN if no feasible theta exists

Examples

[val,theta] = snc_thetaopt(fun)
[val,theta] = snc_thetaopt(fun,thetamax)
snc_srv_rate(C, theta)

MGF service envelope of a constant-rate work-conserving server

A work-conserving server of capacity C offers the deterministic service process S(s,t) = C*(t-s), whose exponential-form envelope

E[exp(-theta*S(s,t))] <= exp(-theta*(rho*(t-s) - sigma))

holds with rho(theta) = C and sigma(theta) = 0 for every theta > 0. This is the elementary service element of the snc family; a station shared by cross traffic is obtained from it through snc_leftover, and a tandem of stations through snc_conv.

Parameters:

  • C – Server capacity, work per slot

  • theta – Optional Chernoff parameter, unused

Returns:

sigma – Burst term of the service envelope (0 here) rho: Rate term of the service envelope, equal to C

Examples

[sigma,rho] = snc_srv_rate(C)
[sigma,rho] = snc_srv_rate(C,theta)   % theta ignored, kept for handle
                                      % compatibility
srv = @(theta) snc_srv_rate(C,theta);

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. IV.

snc_srv_exp(mu, theta)

MGF service envelope of an exponential server, in job units

A single server with Exp(MU) service times completes jobs at the epochs of a Poisson process of rate MU while it is busy, so its cumulative service S(s,t) counted in JOBS is Poisson with mean mu*(t-s) and

log E[exp(-theta*S(s,t))] = mu*(t-s)*(exp(-theta)-1),

giving the tight envelope rho(theta) = mu*(1-exp(-theta))/theta, sigma = 0.

THIS IS THE SERVICE ELEMENT TO USE WHENEVER THE WORK UNIT IS THE JOB. Pairing snc_srv_rate with a job-counting arrival envelope would model a server that completes jobs at deterministic intervals, an M/D/1, and would UNDERSTATE the delay of an exponential server rather than bound it. The M/M/1 read with this element instead reproduces both exact decay rates: the backlog bound decays as (lambda/mu)^n in jobs and the delay bound as exp(-(mu-lambda)*d) in time, since the optimal theta tends to log(mu/lambda).

Job units also compose across hops: a departure envelope from snc_output is a job count and is directly the arrival envelope of the next station, whereas service-time work units differ from station to station.

Parameters:

  • mu – Service rate, jobs per slot

  • theta – Chernoff parameter, theta > 0

Returns:

sigma – Burst term of the service envelope (0 here) rho: Rate term of the service envelope, jobs per slot

Examples

[sigma,rho] = snc_srv_exp(mu,theta)
srv = @(theta) snc_srv_exp(mu,theta);

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. IV.

snc_perc_delay(arv, srv, eps, thetamax)

Delay quantile at a prescribed violation probability

Inverts the delay bound of snc_bound_delay in d: the smallest target for which the bound certifies P{D > d} <= EPS is, at fixed theta,

d(theta) = (sigmaA + sigmaS - log(eps*(1-exp(-theta*(rhoS-rhoA))))/theta) / rhoS,

minimized over the feasible thetas. This is the deliverable of the family: a statistical delay guarantee, the quantity an SLA is written against, as opposed to the mean delay returned by the queueing-theoretic solvers.

Parameters:

  • arv – Handle theta -> [sigmaA,rhoA], e.g. an snc_env_* function

  • srv – Handle theta -> [sigmaS,rhoS], e.g. snc_srv_rate

  • eps – Violation probability, 0 < eps < 1

  • thetamax – Optional upper end of the theta search, default 1e3

Returns:

d – Delay quantile, slots, Inf if the station is unstable theta: Minimizing theta, NaN if no feasible theta exists

Examples

d = snc_perc_delay(arv,srv,eps)
[d,theta] = snc_perc_delay(arv,srv,eps,thetamax)

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. IV-B.

snc_perc_backlog(arv, srv, eps, thetamax)

Backlog quantile at a prescribed violation probability

Inverts the backlog bound of snc_bound_backlog in b: the smallest level for which the bound certifies P{B > b} <= EPS is, at fixed theta,

b(theta) = sigmaA + sigmaS - log(eps*(1-exp(-theta*(rhoS-rhoA))))/theta,

and the reported quantile is the minimum of b(theta) over the feasible thetas. Note that the minimizing theta differs from the one of the forward bound at a given level, which is why the inversion is done in closed form and re-optimized rather than by a search on snc_bound_backlog.

Parameters:

  • arv – Handle theta -> [sigmaA,rhoA], e.g. an snc_env_* function

  • srv – Handle theta -> [sigmaS,rhoS], e.g. snc_srv_rate

  • eps – Violation probability, 0 < eps < 1

  • thetamax – Optional upper end of the theta search, default 1e3

Returns:

b – Backlog quantile, units of work, Inf if the station is unstable theta: Minimizing theta, NaN if no feasible theta exists

Examples

b = snc_perc_backlog(arv,srv,eps)
[b,theta] = snc_perc_backlog(arv,srv,eps,thetamax)

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. IV-B.

snc_output(sigmaA, rhoA, sigmaS, rhoS, theta)

Output arrival envelope of a flow leaving a server

The departures of a flow with arrival envelope (sigmaA,rhoA) from a server with service envelope (sigmaS,rhoS) admit, for independent processes and a stable station rhoA < rhoS, the arrival envelope

rho = rhoA, sigma = sigmaA + sigmaS - log(1-exp(-theta*(rhoS-rhoA)))/theta.

The rate is conserved and the server adds burstiness. This is what carries a flow across a feed-forward network one hop at a time; for a tandem traversed by the same flow, snc_conv gives the tighter end-to-end result.

Parameters:

  • sigmaA,rhoA – Arrival envelope of the flow entering the server

  • sigmaS,rhoS – Service envelope of the server

  • theta – Chernoff parameter, theta > 0

Returns:

sigma – Burst term of the departure envelope, Inf if unstable rho: Rate term of the departure envelope, equal to rhoA

Examples

[sigma,rho] = snc_output(sigmaA,rhoA,sigmaS,rhoS,theta)

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. V-A.

snc_mean_delay(arv, srv, thetamax)

Upper bound on the mean delay from the tail bound

Integrates the delay tail bound of snc_bound_delay over the whole positive axis, which for a nonnegative delay gives E[D] = int_0^inf P{D>d} dd and hence an upper bound on the MEAN. At fixed theta the bound is K*exp(-a*d) with a = theta*rhoS and

K = exp(theta*(sigmaA+sigmaS)) / (1-exp(-theta*(rhoS-rhoA))),

so, clipping the bound at 1 where it exceeds it, the integral is available in CLOSED FORM: (log(K)+1)/a when K >= 1 and K/a otherwise. No quadrature is involved, so the result is a bound and not a bound plus a discretization error; the only numerical step is the minimization over theta.

This is the entry point SolverBA calls for the ‘snc.upper’ response-time column. IT IS A LOOSE MEAN BOUND AND THAT IS INHERENT: on the M/M/1 read in job units (snc_env_poisson feeding snc_srv_exp) it returns 2.4x the exact 1/(mu-lambda) at rho = 0.1 and 10.4x at rho = 0.95, because the prefactor of the tail bound, not its decay rate, is what dominates an integral over the whole axis. The tail bound it integrates is the sharp object; use snc_perc_delay when the quantile is what matters.

Parameters:

  • arv – Handle theta -> [sigmaA,rhoA], e.g. an snc_env_* function

  • srv – Handle theta -> [sigmaS,rhoS], e.g. snc_srv_exp

  • thetamax – Optional upper end of the theta search, default 1e3

Returns:

ED – Upper bound on E[D], Inf if no feasible theta exists theta: Minimizing theta, NaN if no feasible theta exists

Examples

ED = snc_mean_delay(arv,srv)
[ED,theta] = snc_mean_delay(arv,srv,thetamax)

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. IV-B.

snc_mean_backlog(arv, srv, thetamax)

Upper bound on the mean backlog from the tail bound

The counterpart of snc_mean_delay for the backlog: integrating the tail bound of snc_bound_backlog gives E[B] = int_0^inf P{B>b} db and hence an upper bound on the mean. At fixed theta the bound is K*exp(-theta*b) with

K = exp(theta*(sigmaA+sigmaS)) / (1-exp(-theta*(rhoS-rhoA))),

so the clipped integral is (log(K)+1)/theta when K >= 1 and K/theta otherwise, in closed form. The unit of the answer is the unit of the envelopes: jobs when the pair is snc_env_poisson with snc_srv_exp, units of work when it is snc_env_cpoisson with snc_srv_rate.

SolverBA does NOT use this for its queue-length column: it applies Little’s law to the response-time bound instead, so that Q and R stay consistent with the exact open-network throughput. The two are close but not identical, since each optimizes its own theta.

Parameters:

  • arv – Handle theta -> [sigmaA,rhoA], e.g. an snc_env_* function

  • srv – Handle theta -> [sigmaS,rhoS], e.g. snc_srv_exp

  • thetamax – Optional upper end of the theta search, default 1e3

Returns:

EB – Upper bound on E[B], Inf if no feasible theta exists theta: Minimizing theta, NaN if no feasible theta exists

Examples

EB = snc_mean_backlog(arv,srv)
[EB,theta] = snc_mean_backlog(arv,srv,thetamax)

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. IV-B.

snc_leftover(sigmaS, rhoS, sigmaX, rhoX)

Leftover service envelope under blind multiplexing

A server with envelope (sigmaS,rhoS) shared with a cross flow of arrival envelope (sigmaX,rhoX) leaves the flow of interest, under blind (arbitrary) multiplexing, the service process S(s,t)-X(s,t), whose envelope is

rho = rhoS - rhoX, sigma = sigmaS + sigmaX.

The subtraction of the two exponential forms is exact when the two processes are independent; otherwise the pair must be split by Hoelder’s inequality, which this elementary version does not do. A nonpositive rho means the cross traffic can exhaust the server, and the bound functions return a violation probability of 1 in that case rather than a number.

Parameters:

  • sigmaS – Burst term of the service envelope

  • rhoS – Rate term of the service envelope

  • sigmaX – Burst term of the cross-flow arrival envelope

  • rhoX – Rate term of the cross-flow arrival envelope

Returns:

sigma – Burst term of the leftover service envelope rho: Rate term of the leftover service envelope

Examples

[sigma,rho] = snc_leftover(sigmaS,rhoS,sigmaX,rhoX)

% leftover of a rate-C server shared with a Poisson cross flow, as the
% service handle expected by snc_bound_delay:
function [s,r] = srv(theta)
  [sX,rX] = snc_env_poisson(lambdaX,theta);
  [sS,rS] = snc_srv_rate(C,theta);
  [s,r] = snc_leftover(sS,rS,sX,rX);
end

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. V-B.

snc_env_tokenbucket(b, r, theta)

Deterministic token-bucket arrival envelope

A flow policed by a (b,r) token bucket satisfies A(s,t) <= b + r*(t-s) with probability one, hence E[exp(theta*A(s,t))] <= exp(theta*(r*(t-s)+b)) for every theta > 0. The envelope is therefore constant in theta:

sigma(theta) = b, rho(theta) = r.

This is the deterministic network calculus arrival curve read as a degenerate MGF envelope, so it can be mixed freely with the stochastic ones.

Parameters:

  • b – Bucket depth, units of work

  • r – Token rate, work per slot

  • theta – Optional Chernoff parameter, unused

Returns:

sigma – Burst term of the envelope, equal to b rho: Rate term of the envelope, equal to r

Examples

[sigma,rho] = snc_env_tokenbucket(b,r)
[sigma,rho] = snc_env_tokenbucket(b,r,theta)   % theta ignored, kept for
                                               % handle compatibility

References

J.-Y. Le Boudec and P. Thiran, “Network Calculus”, LNCS 2050, Springer, 2001.

snc_env_poisson(lambda, theta)

MGF arrival envelope of a Poisson flow with unit-size jobs

Returns the pair (sigma,rho) such that the cumulative arrivals A(s,t) of a Poisson process of rate LAMBDA, each job carrying one unit of work, satisfy the (sigma(theta),rho(theta))-constrained bound

E[exp(theta*A(s,t))] <= exp(theta*(rho*(t-s) + sigma)), theta > 0.

Since log E[exp(theta*A(0,t))] = lambda*t*(exp(theta)-1) exactly, the envelope is tight with a zero burst term:

rho(theta) = lambda*(exp(theta)-1)/theta, sigma(theta) = 0.

Time is slotted with unit slot length, the convention of the whole snc family; rho is therefore work per slot.

Parameters:

  • lambda – Arrival rate, jobs per slot

  • theta – Chernoff parameter, theta > 0

Returns:

sigma – Burst term of the envelope (0 here) rho: Rate term of the envelope, work per slot

Examples

[sigma,rho] = snc_env_poisson(lambda,theta)
arv = @(theta) snc_env_poisson(lambda,theta);   % handle form for the bounds

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. IV.

snc_env_map(D0, D1, theta)

MGF arrival envelope of a MAP/MMPP flow with unit-size jobs

For a Markovian arrival process (D0,D1) counting N(0,t) unit-work jobs,

E[exp(theta*N(0,t))] = pi*expm((D0+D1*exp(theta))*t)*1.

Let lambda* be the eigenvalue of maximal real part of A(theta)=D0+D1*e^theta and v>0 its right Perron eigenvector. Bounding 1 <= v/min(v) entrywise and using the nonnegativity of expm(A*t) off the diagonal gives

rho(theta) = lambda*/theta, sigma(theta) = log(max(v)/min(v))/theta,

which is the standard exponential-form envelope of a Markov-modulated source. The burst term is what the modulating chain contributes: it is 0 for a one-phase MAP (Poisson) and grows with the phase disparity of an MMPP.

Parameters:

  • D0 – Hidden-transition generator block of the MAP

  • D1 – Arrival-transition block of the MAP

  • theta – Chernoff parameter, theta > 0

Returns:

sigma – Burst term contributed by the modulating chain rho: Rate term of the envelope, jobs per slot

Examples

[sigma,rho] = snc_env_map(D0,D1,theta)
arv = @(theta) snc_env_map(D0,D1,theta);

References

C.-S. Chang, “Performance Guarantees in Communication Networks”, Springer, 2000, Ch. 7 (effective bandwidth of a Markov-modulated source).

snc_env_cpoisson(lambda, mu, theta)

MGF arrival envelope of a compound Poisson flow with Exp job sizes

Jobs arrive Poisson at rate LAMBDA and each carries an Exp(MU) amount of work, so the cumulative work A(s,t) is a compound Poisson process with

log E[exp(theta*A(0,t))] = lambda*t*theta/(mu-theta), 0 < theta < mu,

giving the tight envelope rho(theta) = lambda/(mu-theta), sigma(theta) = 0. The MGF diverges at theta >= mu, where rho is returned as Inf so that the theta search in snc_thetaopt discards the point.

Fed to a constant-rate server of rate MU (snc_srv_rate) this is the network calculus model of the M/M/1 queue: the resulting delay bound decays at rate mu-lambda, the exact asymptotic decay rate of the M/M/1 waiting time.

Parameters:

  • lambda – Job arrival rate, jobs per slot

  • mu – Rate of the Exp job size, so mean work per job is 1/mu

  • theta – Chernoff parameter, theta > 0

Returns:

sigma – Burst term of the envelope (0 here) rho: Rate term of the envelope, Inf when theta >= mu

Examples

[sigma,rho] = snc_env_cpoisson(lambda,mu,theta)
arv = @(theta) snc_env_cpoisson(lambda,mu,theta);

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. IV.

snc_conv(sigma1, rho1, sigma2, rho2, theta, delta)

Min-plus convolution of two service envelopes (tandem concatenation)

Two stations traversed in series offer the flow their min-plus convolution. For independent servers with exponential-form envelopes (sigma1,rho1) and (sigma2,rho2), summing the geometric series over the intermediate epoch gives

rho = min(rho1,rho2), sigma = sigma1 + sigma2 - log(1-exp(-theta*|rho1-rho2|))/theta.

This is the pay-bursts-only-once result: the end-to-end burst term grows additively rather than the delay bounds of the two stations being summed.

The series diverges when rho1 = rho2, so equal rates are handled by shifting the slower server down by DELTA, which is the usual regularization; DELTA then trades rate against burst and can be optimized jointly with theta.

Parameters:

  • sigma1,rho1 – Envelope of the first station

  • sigma2,rho2 – Envelope of the second station

  • theta – Chernoff parameter, theta > 0

  • delta – Optional rate separation used when rho1 = rho2, default

Returns:

sigma – Burst term of the concatenated service envelope rho: Rate term of the concatenated service envelope

Examples

[sigma,rho] = snc_conv(sigma1,rho1,sigma2,rho2,theta)
[sigma,rho] = snc_conv(sigma1,rho1,sigma2,rho2,theta,delta)

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. V-C.

Original: F. Ciucu, A. Burchard, J. Liebeherr, “Scaling Properties of Statistical End-to-End Bounds in the Network Calculus”, IEEE Trans. on Information Theory, 52(6):2300-2312, 2006.

snc_bound_delay(arv, srv, d, thetamax)

Violation probability of a delay target (stochastic network calculus)

For a flow with arrival envelope (sigmaA,rhoA) served by an element with service envelope (sigmaS,rhoS), the virtual delay D(t) of the stable station rhoA < rhoS obeys, for every theta > 0,

P{D(t) > d} <= exp(-theta*(rhoS*d-sigmaA-sigmaS)) / (1-exp(-theta*(rhoS-rhoA))),

the horizontal rather than vertical deviation between the arrival and service envelopes. The returned value is the infimum over theta, clipped at 1. On the M/M/1 parameterization (snc_env_cpoisson feeding snc_srv_rate with C = mu) the optimal theta approaches mu-lambda, so the bound reproduces the exact asymptotic decay rate of the waiting-time tail.

Parameters:

  • arv – Handle theta -> [sigmaA,rhoA], e.g. an snc_env_* function

  • srv – Handle theta -> [sigmaS,rhoS], e.g. snc_srv_rate

  • d – Delay target, slots

  • thetamax – Optional upper end of the theta search, default 1e3

Returns:

eps – Upper bound on P{D > d}, in [0,1] theta: Minimizing theta, NaN if no feasible theta exists

Examples

eps = snc_bound_delay(arv,srv,d)
[eps,theta] = snc_bound_delay(arv,srv,d,thetamax)

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. IV-B.

snc_bound_backlog(arv, srv, b, thetamax)

Violation probability of a backlog level (stochastic network calculus)

For a flow with arrival envelope (sigmaA,rhoA) served by an element with service envelope (sigmaS,rhoS), the backlog B(t) of the stable station rhoA < rhoS obeys, for every theta > 0,

P{B(t) > b} <= exp(-theta*(b-sigmaA-sigmaS)) / (1-exp(-theta*(rhoS-rhoA))),

the union bound over the start of the backlogged period summed as a geometric series on the unit-slot time axis. The returned value is the infimum over theta, clipped at 1, and is an upper bound on the tail, never an estimate of it: the decay rate is asymptotically exact and the prefactor is loose.

Parameters:

  • arv – Handle theta -> [sigmaA,rhoA], e.g. an snc_env_* function

  • srv – Handle theta -> [sigmaS,rhoS], e.g. snc_srv_rate

  • b – Backlog level, units of work

  • thetamax – Optional upper end of the theta search, default 1e3

Returns:

eps – Upper bound on P{B > b}, in [0,1] theta: Minimizing theta, NaN if no feasible theta exists

Examples

eps = snc_bound_backlog(arv,srv,b)
[eps,theta] = snc_bound_backlog(arv,srv,b,thetamax)

References

M. Fidler and A. Rizk, “A Guide to the Stochastic Network Calculus”, IEEE Communications Surveys and Tutorials, 17(1):92-105, 2015, Sec. IV-B.