An algorithmic toolbox for Network Calculus.
A. Bouillard and E. Thierry.
News! An implementation of some of our algorithms has been achieved by
Errata (many thanks to Jorn Migge) :
• Statement of Lemma 13 (page 26): if a=0 and f(a+)<0 then f∗=−∞
• Proofs of Lemma 11 (page 26) and Lemma 14 (page 27): the case T=0 and f(T)<0 for spots
and the case T=0 and f(T+)<0 for open segments are not treated in Lemma 1. For those cases a simple
yet special lemma is necessary : for spots if T=0 and f(T)<0 then f∗(t)=−∞
for all t≥0 and for open segments if T=0 and f(T+)<0 then f∗(t)=−∞
for all t>0.
• Proof of Lemma 14 - several typos in inequalities:
In the case c/d≤ρ and f(T+)/T≤c/d, after "Such an integer K exists since" (page 29),
replace "0≤ρ-c/d<ρ-f(T+)/T" by "ρ-c/d≤ρ-f(T+)/T" (0≤ρ-c/d is true,
but not necessary for the existence of K).
In the case c/d≤ρ and f(T+)/T>c/d, after "Such an integer K exists since" (page 30),
replace "0≤ρ-f(T+)/T<ρ-c/d" by "ρ-f(T+)/T<ρ-c/d" (since ρ-f(T+)/T can be negative).
Extend the case c/d>ρ and f(T+a+)/(T+a)>c/d to c/d>ρ and f(T+a+)/(T+a)≥c/d, and
after "Such an integer K exists since" (page 31), replace "0< c/d-ρ< f(T+a+)/(T+a)-ρ" by
"c/d-ρ≤f(T+a+)/(T+a)-ρ" (0< c/d-ρ is true but not necessary).
The last case c/d>ρ and f(T+a+)/(T+a)< c/d (page 31) is ok.
• Statement and Proof of Lemma 11 (resp. Lemma 14): the cases when T=0 and f(T)>0 or f(T)=0
(resp. f(T+)>0 or f(T+)=0) are not explicitely treated since the cases in the paper refer to f(T)/T
(resp. f(T+)/T) which have to be defined here:
Case T=0 and f(T)>0 (resp. f(T+)>0): do as if f(T)/T=+∞ (resp. f(T+)/T=+∞).
Case T=0 and f(T)=0 (resp. f(T+)=0): do as if f(T)/T=c/d (resp. f(T+)/T=c/d).
• Proof of Proposition 4 (page 15-18): two important remarks (present in a former technical report) are missing in the paper ! In particular,
one special case in the proof of Proposition 9 refers to one of those remarks about the preservation of ultimate pseudo-periodicity for
the convolution when one input function is not ultimately plain, which uses itself a first remark about such a preservation for the minimum.
The text below must be added at the end of Point 1. (and 2.) (minimum and maximum) in the proof of Proposition 4 (page 16):
"As a complement, note that if c'1≤c'2, another way to
ensure that min(f1,f2) is locally bounded, ultimately plain and
pseudo-periodic, is to keep locally bounded and pseudo-periodicity assumptions on inputs but
suppose that only f1 is ultimately plain with ∀ t ≥ T1,
f1(t) ∈ R and that f2 is not necessarily ultimately
plain (it may have +∞ values from T2) but ∀ t ≥ T2,
f2(t) ≠ −∞. If c'1=c'2, the minimum is still
clearly plain and pseudo-periodic from max(T1,T2). If c'1 < c'2,
then proceed exactly as above (we still have M1<+∞ and m2>−∞)
and remark that min(f1,f2) is clearly ultimately plain from T1."
The text below must be added at the end of Point 5. (convolution) in the proof of Proposition 4 (page 17) :
"As a complement, note that to preserve the ultimate pseudo-periodicity, we only need one input function to be ultimately
plain as shown now. Suppose that f1 is ultimately plain
from T1 (here possibly ∈ R or =+∞ or =−∞), but
that f2 is not necessarily ultimately plain. We first dismiss the
case treated in Lemma 1 when ∃ a ∈ R+,
f1(a)=−∞ or f2(a)=−∞, both leading to
f1*f2=−∞ from a, i.e. an ultimately plain pseudo-periodic
output. In the reasoning, the first term f'1*f'2 is still equal
to +∞ from T1+T2, and we consider two cases depending of
f''1 which represents the ultimate behaviour of f1:
- If f''1=+∞ all over R+, then
f''1*f'2=f''1*f''2=+∞ all over R+. Since
f'1*f'2=+∞ from T1+T2, we have f1*f2=f'1*f''2
from T1+T2 which is ultimately pseudo-periodic with
period d2 and increment c2. But it is not necessarily
ultimately plain (e.g. choose f1(t)=0 if t=0 and =+∞
otherwise, and f2(t)=t if t is an even integer and =+∞
otherwise, and then f1*f2=f2).
- If f''1(t) ∈ R from T1, then either ∃ a ≥
T2, f''2(a) ∈ R or f''2=+∞ all over R+. In the
first case, f''1*f''2 is ultimately plain with values in R
from T1+a. Since it is ultimately pseudo-periodic with period d and
increment min(c'1,c'2), whereas f'1*f''2 and f''1*f'2
are ultimately pseudo-periodic with same period but larger
increments (resp. c'2 and c'1), their minimum is ultimately
plain and pseudo-periodic (see the complement in the study of the
minimum). In the second case when f''2=+∞ all over R+,
f1*f2=f''1*f'2 from T1+T2 which is also clearly ultimate
plain and pseudo-periodic."
• Inputs of Algorithm 2 (page 37): as mentionned in Proposition 4, this algorithm will work for a larger set of inputs. In the description
of the input data, replace "f1,f2 both ultimately plain and pseudo-periodic" by the following valid cases (which cover this
previous case) "f1,f2 both ultimately pseudo-periodic, with f1 ultimately plain and
c1/d1 ≤ c2/d2, or f2 ultimately plain and c2/d2
≤ c1/d1". One should also change the presentation just above by adding to "it works if they are both
ultimately plain" the others cases "or if f1 ultimately
plain and pseudo-periodic and c1/d1 ≤ c2/d2, or
f2 ultimately plain and pseudo-periodic and c2/d2 ≤ c1/d1".
• Inputs of Algorithm 3 (page 40): change the description of the input data into "both ultimately pseudo-periodic, and at least one ultimately plain."
since it is necessary as mentioned in the text before the algorithm.
Optimal routing for end-to-end guarantees using Network Calculus.
A. Bouillard, B. Gaujal, S. Lagrange and E. Thierry.
This paper deals with the same routing problem as the Valuetools'2007 paper.
It solves in polynomial time the general "shortest path" problem left open
in Valuetools'2007, but does not present the Valuetools algorithms designed
for particular cases (simpler and thus with lower complexity). Moreover it
shows that the nice Valuetools algorithm to compute the multi-dimensional
convolution has a flaw. We did not manage to correct this algorithm or
specify the additional assumptions necessary to make it work. We only
present a special case where the computation is easy.
News ! It appears that searching a path which achieves some end-to-end
delay requirement (decision problem) in a Network Calculus model, has been
discussed in S. Recker, "Service curve based routing subject to deterministic
QoS constraints", Telecommunication Systems 24, pages 385-413, 2003, and
M. Fidler, S. Recker, "Conjugate network calculus: a dual approach
applying the Legendre transform", Computer Networks 50, pages 1026-1039, 2006.
Their idea of using Legendre transform to simplify the problem is similar to
ours. However the algorithms presented in those papers are not fully analyzed
and there is no clear reference to the classical shortest path algorithms with additive
Greedy algorithms for optimization on distance-hereditary graphs.
O. Cogis, E. Thierry.
Although it is difficult to provide formal definitions of "greedy algorithms" or
"dynamic programming" covering exactly their use in the literature, it is clear
that the term "greedy" is inappropriate in most of this work and it should be replaced
by "dynamic programming" (during the process of building a solution, the algorithms
advance by maintaining several candidate-solutions of subproblems).
Computational aspects of the 2-dimension of partially ordered sets.
M. Habib, L. Nourine, O. Raynaud and E. Thierry.
Several sources indicate several articles where the computation of the
2-dimension or more generally the k-dimension has been showed NP-hard first.
Here are some candidates:
Unfortunately we did not manage to check whether those references actually
contain such proofs.
• Statement of Proposition 13 (page 411): replace max(|J(L)|,|M(L)|) par min(|J(L)|,|M(L)|).
Extending a partially ordered set: links with its lattice of ideals.
P. Baldy, M. Morvan and E. Thierry.
Concerning the bijection between the linear extensions of a poset and the maximal chains
of its lattice of ideals, Stefan Felsner
has suggested another link with the linear-extension graph.
Optimal routing for end-to-end guarantees: the price of multiplexing.
A. Bouillard, B. Gaujal, S. Lagrange and E. Thierry.
This paper contains several errors which are listed and explained in the Performance 2008
journal version. We managed to patch some of them, but not all of them.
Dynamics of the Picking transformation on integer partitions.
H. D. Phan Ti and E. Thierry.
News ! It appears that this transformation has been previously
studied under the name "Bulgarian solitaire". The main results of
our article have already been proved and some of our conjectures have been
solved. A survey of these results may be found here.
Thanks to Kyle Petersen for letting us
A quasi optimal bit-vector encoding of tree hierarchies. Application to efficient type inclusion tests.
O. Raynaud and E. Thierry.
News ! An improvement of our algorithm has been presented at the next ECOOP'2002
by Robert E. Filman with
News ! We have presented at MCO'2008 a new algorithm computing arbitrarily
smaller bit vector encodings than polychotomic encodings. However the complexity of computing
the 2-dimension for trees remains an open problem.
Generating random permutations in the framework of parallel coarse grained models.
I. Guérin-Lassous and E. Thierry.
News ! A solution verifying simultaneously our three main criteria has
been presented by Jens Gustedt,
"Efficient Sampling of Random Permutations", Journal of Discrete Algorithms 6(1), pages 125-139, 2008
(download the 2002 Inria report).