An algorithmic toolbox for Network Calculus. A. Bouillard and E. Thierry.
News! An implementation of some of our algorithms has been achieved by Sébastien Lagrange.
Errata (many thanks to Jorn Migge) :
• Statement of Lemma 13 (page 26): if a=0 and f(a+)<0 then f∗=−∞ over R+∗.
• 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 weights.
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.
Errata
• 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 know.
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 "polychotomic encodings".
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).