snc_conv.h File Reference

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

#include <algorithm>
#include <cmath>
#include <limits>
#include "line/api/snc/snc_types.h"
#include "line/util/error.h"

Include dependency graph for snc_conv.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::snc

Functions
Env	line::snc::snc_conv (const Env &s1, const Env &s2, double theta, double delta=-1.0)
	Min-plus convolution of two service envelopes (tandem concatenation).

Detailed Description

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, 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 per-station delay bounds being summed. The series diverges at equal rates, so those are handled by shifting the slower server down by delta, the usual regularization; delta trades rate against burst and is an argument so it can be optimized jointly with theta.

Port of matlab/src/api/snc/snc_conv.m. Original: F. Ciucu, A. Burchard, J. Liebeherr, IEEE Trans. Inf. Theory 52(6), 2300-2312, 2006.

Definition in file snc_conv.h.