Bartosz Pałubicki

Rémy Marchal

Jean-Claude Butaud

Louis-Etienne Denaud

Laurent Bléron

Robert Collet

Grzegorz Kowaluk

J.-C Butaud

L.-E Denaud

A Method of Lathe Checks Measurement; SMOF device and its software

In the present paper, a novel method for veneer checks measurement and description based on digital image analysis is evaluated. According to this method, the camera is located sideways to the veneer allowing for viewing the checks geometry in the cross-section of the veneer. Checks are opened by bending the veneer on a roller of a specific diameter and they are exposed in such a way that good visibility of checks is assured. The algorithm used reproduces the checks by finding their coarse positions on the rescaled image and then migrating to the original, full resolution image to precisely localize the checks' bottom. The method is automatic and delivers the most important information on checks of veneer, namely distances between checks and their depths.

Ein Verfahren zur Messung von Rissen in Furnieren: SMOF-Apparatus und zugehörige Software

Zusammenfassung In dieser Studie wird ein neues Verfahren zur Messung von Rissen in Furnieren unter Verwendung digitaler Bildanalyse untersucht. Dabei ist die Kamera seitlich angeordnet, wodurch die Rissgeometrie auf einer Querschnittsseite des Furniers betrachtet werden kann. Durch Biegen des Furniers auf einer Rolle mit spezifischem Durchmesser werden die Risse geöffnet und so belichtet, dass diese gut sichtbar sind. Der verwendete Algorithmus bestimmt die Risse, indem er zunächst in einem Bild mit verringerter Auflösung deren ungefähre Position feststellt und dann an diesen Stellen im Originalbild mit voller Auflösung die Risstiefe genau erfasst. Es handelt sich um ein automatisches Verfahren, das die wichtigsten Informationen zur Rissbildung, nämlich den Abstand zwischen den Rissen und deren Tiefe, liefert.

Introduction

Usually, a few parameters are used for the description of veneer quality: thickness variation, surface roughness, veneer curl-up and lathe checks [START_REF] Lutz | Techniques for peeling process, slicing, drying veneer[END_REF][START_REF] Feihl | Veneer cutting manual[END_REF][START_REF] Nagatomi | Relation between veneer quality and peeling sound in the peeling of Sugi[END_REF][START_REF] Denaud | Vibration and acoustic analyses of peeling[END_REF]. Methods for surface roughness evaluation as well as thickness variation measurement are easily available, but methods and devices for lathe check detection are not so common. It must be pointed out that lathe check occurrence is a very serious defect because of its huge effect, first on the veneer and then on the mechanical strength of plywood or LVL [START_REF] Ohya | The effect of veneer quality on the bending strength of laminated wood[END_REF][START_REF] Devallance | Douglas-Fir plywood gluebond quality as influenced by veneer roughness, lathe checks, and annual ring characteristics[END_REF]). It also affects the glue consumption during panel production.

The lathe checks phenomenon has been widely studied for a long time with regard to the forming mechanisms (Leney 1960a,b) and it is still of high interests [START_REF] Ohbayashi | Observation of crack propagation in wood oa the cellular level considering the occurrence of lathe checks[END_REF]). Furthermore, an energetic approach and risk of lathe check occurrence has been reported [START_REF] Thibaut | Le processus de coupe du bois par déroulage[END_REF][START_REF] Thibaut | Some considerations about energetical balance between friction fracture and strains during veneer cutting at different temperature, 15th International Wood Machining Seminar[END_REF].

There are two main characteristics describing lathe checks: the depths and the intervals between two neighbor checks. Most of the researchers [START_REF] Koch | Wood machining processes[END_REF][START_REF] Devallance | Douglas-Fir plywood gluebond quality as influenced by veneer roughness, lathe checks, and annual ring characteristics[END_REF][START_REF] Denaud | Vibration and acoustic analyses of peeling[END_REF] and others) use the lathe check frequency defined as the inverse of check interval. However, since frequency is used in the time and not in the geometrical domain, lathe check interval is preferred in the present work.

It would be ideal to determine the checks pattern on the veneer surface as well as the depth function along each check. Some problems occur though. Usually, the measurement of average intervals is not a complicated task -it is sufficient to count the checks on a given veneer length (e.g., 100 mm) and divide this length by the number of checks counted. The check depth, however, is more difficult to evaluate. The geometry of checks usually makes it hard to measure the depth on many points along the check using a nondestructive method (unless tomography is available). Figure 1 shows lateral views of checks opened by bending. Having a manipulated access only from the open face (possibly also from the closed face) of the veneer, it is impossible to reproduce the shape of the check's cross-section or, what would be even more interesting, to determine its depth (e.g., using laser displacement sensor). Two groups of approximate methods are exploited instead: indirect methods or single cross-section optical measurement.

Several indirect methods of lathe check depth measurement exist, however they all give values averaging not only along one, but often along several checks. The simplest and widely used method in industry is the "stiffness" method. By bending the veneer in both opposite directions, the difference of stiffnesses is perceptible between open and closed veneer faces. When the open face is on the compressed side, the fact of check existence does not influence the rigidity, but the veneers seem to be significantly weaker when bending in the opposite direction. The difference of bending stiffnesses in both directions gives an idea of the checks depth. The disadvantages of this method are:

• the initial curvature of the veneer introduces measuring difficulties to the method and • the resulting difference of the stiffness depends not only on the depth but also on the intervals of the checks for a given veneer.

Another method uses air pressure loss during passing through the veneer [START_REF] Haouzali | Peeling of poplar: cultivars and forest stations effects on cutting forces and veneer quality[END_REF]). This technique is based on imposing a compressed air by exterior area ring of the head on the veneer face and then measuring the pressure of the air, which passed through the wood to the interior ring area. The difference between input and output pressure (pressure loss) gives quantitative knowledge of the air permeability of the veneer. This is influenced by: lathe checks, surface roughness, wood tissue density and porosity etc. Assuming that on both sides of the veneer the wood tissue is the same and the roughness is similar, the difference of pressure losses between both faces becomes highly correlated to lathe checks. The loss is lower on the open face (air passes more easily), compared to the closed face. Like in the case of the "stiffness" method, here again the result includes at once both depths and intervals of several checks. Additionally, the surface roughness and wood structure on both veneer faces might not be similar and therefore might influence the result.

Bearing in mind the mentioned disadvantages, researchers prefer to utilize single cross-section optical measurement [START_REF] Wang | Nondestructive evaluation of veneer quality using acoustic wave measurements[END_REF][START_REF] Devallance | Douglas-Fir plywood gluebond quality as influenced by veneer roughness, lathe checks, and annual ring characteristics[END_REF]). The image of the veneer side is usually obtained by using a microscope. However, to be able to see the checks clearly (improve contrast), it is necessary to use extra techniques, like for example covering the open face with an ink penetrating the checks, or bending the veneer in order to open checks. After improving the contrast between wood tissue and checks, they are often "manually" measured on a screen. Frequently, authors do not provide details of their measurement. For example, lathe checks were investigated by [START_REF] Nagatomi | Relation between veneer quality and peeling sound in the peeling of Sugi[END_REF], but a detailed methodology was not given, except for the fact that a CCD camera with a magnification lens was used. It can be assumed that it was examined by manual image analysis.

Two other, very promising methods of lathe checks quantification were proposed by Denaud et al. (2007b). Instead of a strict, post factum measurement of the veneer geometry, an indirect, online "sensing" of veneer checking during peeling was performed. By using a microphone or an accelerometer mounted on the cutting knife and analyzing their signals in the frequency domain, it is possible to obtain the checks frequency and in some cases also an estimation of their depth. Denaud et al. (2007a) have also developed a convenient method to identify lathe checks sig-natures on the temporal signal issued from the mentioned sensors: a local Root Mean Square (RMS) averaging and a peak detection algorithm which does not require any threshold. These methods, however, seem to be more suitable for laboratory than for industrial applications because of their sensitivity to background noise. No automated industrial solutions for the lathe check detection are known to the authors.

Summarizing above considerations, there is need for a fast, effective method able to measure numerous lathe checks in order to provide statistically important results on check interval as well as on their depth.

Experimental stand

The SMOF device (Fig. 2) dedicated for measuring the intervals and the depths of lathe checks present in the wood veneer has been developed for some time [START_REF] Haouzali | Peeling of poplar: cultivars and forest stations effects on cutting forces and veneer quality[END_REF]. Contrary to the measurement of checks on the surface of wood pieces presented by [START_REF] Christy | Automated measurement of checks at wood surfaces[END_REF], lathe checks are usually almost invisible on the flat veneer. The presented measuring technique is based on checks opening by bending the veneer on a pulley of a specific radius. Since the veneers are fragile, this operation has to be done with special care. It is essential to choose an appropriate bending pulley for the veneer being inspected, because success of the measurement depends on it. If the pulley diameter is too small, the measurement will provoke cracking and increasing lathe checks depth, so that the measurement is not reliable. On the other hand, if the pulley diameter is too big, the checks might not be opened and thereafter are poorly visible on the image and hard to detect. Latter, however, is Fig. 2 SMOF device; 1 -veneer, 2 -veneer movement measurement, 3 -LVDT sensor for thickness measurement, 4 -elastic feeding belt, 5 -bending pulley Abb. 2 SMOF-Apparat, 1 -Furnier, 2 -Messung der Furnierdurchbiegung, 3 -LVDT-Sensor zur Dickenmessung, 4 -Elastisches Vorschubband, 5 -Biegerolle less unwanted. Recommended pulley diameters for varying beech veneer thicknesses were found experimentally after numerous measurements and are given in Fig. 3. Additionally, in the current setup, the flexible, inextensible belt, also acting as a conveyor (feeding system), fastens the veneer on the pulley and forces it to become evenly bent over the pulley. This decreases the stress concentration at the bottom of the check and the risk of the veneer breakage. It is advised to utilize wet veneers for the measurement, as they are more flexible than dry ones. Moreover, a perspective of the development of an on-line control of the peeling process requires the checks characterization of wet wood, as it is peeled. Dry wood measurement would differ because of heterogeneous wood shrinkage.

The SMOF system is designed to operate with veneer stripes 15 up to 40 mm wide either produced by wood disc peeling on laboratory micro-lathe [START_REF] Butaud | An experimental device for the study of wood cutting mechanisms: the microlathe[END_REF] or by regular bolt peeling (veneer stripe to be cut-off from the sheet in this case). The measuring speed (feed rate) is regulated between 0.5 and 7 m/min. The applicable veneer thickness to be measured may not exceed 4 mm.

For veneer measurement it is crucial to prepare its edge properly. It has to be flat in order to keep it always in the focus plane of the camera. Furthermore, it should be clean without fuzzy grains. High smoothness of the veneer side is advised in order to recognize the checks more easily. The best way to achieve all mentioned properties is -in the case of micro-peeling -planing of at least one of the faces of the wood disk. For cut-off veneer stripes, it is advised to sand their edges with special care in order to preserve the veneer structure (e.g., between wooden clamps).

Once the veneer is bent over the pulley (and the checks are opened) the line-scan camera starts scanning a veneer side.

With a conventional bright field illumination, some small variations of brightness caused by the distance of the object from the camera would not provide sufficient contrast be- tween checks and veneer. However, to assure successful and automatic lathe check analysis, the effect of such brightness variations should be minimized. A special illuminating system based on the laser line projector has been developed in order to ensure high contrast of the images (Fig. 4). Both, the line-scan camera and the laser projector, have a linear field of view (projection). If their triangular beams (being inclined with respect to each other) cross in the same plane, all the objects located within such intersection will appear on the image as highly illuminated pixels. Contrary, all the surface valleys (such as checks) are not illuminated and represented as dark pixels on the image. The laser line fully covers the field of view of the camera; 10 μm and 5 mm width and height, respectively.

The Dalsa Spyder III high-speed camera (max line frequency 36 kHz) with 1024 pixels equipped with a special NAVITAR PreciseEye macro-objective (magnification 3,6) ensuring low distortion was used. The camera is externally triggered, the encoder coupled with the veneer movement. After putting each linear frame next to each other, it is possible to create a quasi never-ending reproduction of the veneer edge, ready to be analyzed for checks determination. The resolution of the image is 0.01 mm.

Dedicated software was written in LabView ® environment to maintain all necessary tasks: 1. start/stop veneer feeding, 2. continuous obtaining of veneer thickness, 3. continuous acquisition of single-line frames from camera and reconstructing the entire image of the veneer, 4. image analyzing toward automatic check detection.

The SMOF software runs under Microsoft Windows system on a standard PC equipped with Pentium III 2.0 GHz processor and 1024 MB DDR-RAM memory. The PC communicates with SMOF in two ways: i) by ethernet connection (GigE network adapter 1000 Mb/s) to set up the camera and acquire images and ii) by USB 2.0. serial port (NI USB-6210 M series Data Acquisition Card) which is used in three ways:

• as a digital counter -to calculate the feed speed and length of veneer, • as a A/D converter -to obtain veneer thickness values from the LVDT sensor and • as a steering unit -to start and stop the feeding system.

Lathe check detection algorithm

When a high resolution image of the veneer is acquired and saved, the check detection procedure starts. The SMOF system performs an analysis in fully automatic mode; it allows however some manual adjustments for semi-automatic check detection, especially useful when the inspected veneer has very dark or rough side surfaces. Figure 5 displays the block diagram of the algorithm used.

Since the image is high resolution in both X and Y direction (100 pix/mm) leading to high image size, the algorithm used is optimized to save the computation time. At the beginning, just after loading the image, its resolution shrunk by a rescale coefficient preset to s = 10. This operation has two advantages: it decreases CPU load for operations that do not require high resolution data and it works as a low pass filter removing the noise from the original picture. After automatic threshold, based on the image histogram, the Region Of Interest (ROI) is extracted by cutting off unused area under and above the veneer (depending on veneer thickness).

Then detection of coarse positions of the checks on a rescaled image is performed. As can be seen in Fig. 6, one horizontal row of pixels is selected at a specified depth of the veneer profile y h = 0.1h (10% of veneer thickness). Along this line the checks occurrences are examined and the horizontal position x h i of each check found at this (y h ) level is memorized.

In the meantime, the original image is cropped according to rescaled ROI obtained before rescaled photo processing, in order to minimize the amount of data to be processed. Transforming the high resolution image into a binary one (Fig. 8a) using automatic threshold is followed by a closing operation as described below.

One of the problems in automatic lathe check detection is the occurrence of out-standing wood fibers, bridging (Fig. 7) accompanying cracking of a wood tissue (Landis ). During the crack opening, not the entire material releases the constraints, some fibers (bridges) remain connected over the crack mouth opening. This results in similar problems like the one of not fully opened check: on the veneer images, they might appear as discontinuities of a check, therefore, a method to establish the real bottom of check, despite of bridging, is required. The closing operation performed on the image joins all the parts of one check by removing the narrow discontinuities (bridges), so that fragmented checks turn into continuous ones. The operation fills the space between two pixel "islands" and, in this way, joins them together when the distance between the two closest pixels of both "islands" is within the kernel size. The different resulting images are obtained when using 2 × 2 kernel (Fig. 8b) and 5 × 5 kernel (Fig. 8c). As can be seen, closing with too small kernel may cause the checks to be partially unnoticed (check No. 4, Fig. 8b is more shallow compared to check 5, Fig. 8c) or partially qualified as another particle (object number 3, Fig. 8b is considered separated from no.

2) and disqualified in the next processing steps. Closing operation does not cause any additional bi-directional growth of the "island" like e.g., the dilatation operation does.

Next, the small and bottom touching objects are removed to "clean-up" the image and then, all resting objects are enumerated and labeled. Now, to distinguish checks from the noise (e.g., objects 2, 3, 6, 8 of Fig. 8c) the coarse positions of checks determined before on the small, rescaled image are used. These check positions (x h i ; y h ) are transferred to the high resolution image using the rescale coefficient s giving positions in the actual, high resolution image (x hi ; y h ) of pixels surely belonging to the checks. The labels of the objects containing these pixels are memorized. Only these objects are considered as checks and subjected to further analysis.

With the coordinate system center (0, 0) located on the top left corner of the image and directed as shown in Fig. 9, for each confirmed check two coordinates (a i , b i ) of check's bottom are calculated. The vertical one b i given by its pos-Fig. 9 Resulting image of checked veneer with overlaid detected checks' bottoms Abb. 9 Ausgewertetes Bild eines gerissenen Furniers mit Angabe der ermittelten Rissenden ition is the lowest of all pixels belonging to the check Eq. 1

b i = max y j i , ( 1
)
where y j is the vertical position of j-th pixel of i-th check The horizontal coordinate a i of the check bottom is calculated as a center of all n i pixels belonging to the bottom of the considered i-th check Eq. 2

a i = 1 n i n i k=1 (x k ) i (2)
where x k is a horizontal position of k-th pixel of the i-th check with the pixel being located at the b i level In such a way, the set of all check bottoms are found and overlaid on the original picture (Fig. 9). Afterwards, based on the thickness of the veneer as a function of its length and b i values, the depth of each check is calculated. Intervals I i between neighbor checks are calculated by simple subtraction of x-positions of neighbor checks' bottoms. These results are provided in form of raw data as well as a simple statistic summary containing: average, standard deviation and histograms of both depth and interval of the checks.

Results and discussion

The system was used for measuring lathe checks generated by beech wood peeling on the experimental peeling microlathe built in Arts et Metiers ParisTech Cluny, France [START_REF] Butaud | An experimental device for the study of wood cutting mechanisms: the microlathe[END_REF]. Wood discs were peeled under laboratory conditions to veneers of different thicknesses ranging from 0.7 up to 3 mm (see legend of Fig. 11 for more details) with a constant cutting speed of 0.5 m/s. The clearance angle of the newly sharpened cutting knife was set to 0.5 • and no pressure bar was used during the experiments.

As can be seen in Fig. 10, average depth of lathe checks as well as their average interval increase with veneer thickness. For 0.7 mm thick veneer no checks occurred. When the veneer thickness increases, checks start to appear, first shallow but close to each other (small interval) and then deeper and more distant. For 3 mm veneers, the depth of checks is around 70% of their thickness and the mean distance between them reaches 3.5 mm. These results are in agreement with research work by Denaud et al. (2007a). hand side to the right with increasing thickness meaning that both average depth and interval increases. The type of scatter for all cases is natural Gaussian.

Conclusion

An effective, high yield and positively verified direct method of lathe checks detection and measurement by using the SMOF device has been developed and presented. The measurement speed is regulated and may go up to 7 m/min imagining veneers of up to 4 mm thickness, with high resolution of 0.01 mm.

The presented system, SMOF, is capable of automatically characterizing the quality, in terms of lathe checking, of long veneers produced on a microlathe at laboratory level.

A complete system containing the device, a PC and a special software may easily provide summarized information on veneer checks (number, average distance, average depth, standard deviations and histograms of both). The report may also include a detailed set of all check positions and depths and more advanced analyses of obtained data.

Fig. 1

 1 Fig. 1 Lateral view of checked veneers under the microscope Abb. 1 Seitenansicht von gerissenen Furnieren unter dem Mikroskop

Fig. 3

 3 Fig. 3 Recommended pulley diameters for wet beech veneer bending Abb. 3 Empfohlene Rollendurchmesser zum Biegen von feuchten Buchenfurnieren

Fig. 5 Fig. 8

 58 Fig. 5 Block diagram of algorithm used for automatic lathe check detection; the gray blocks represent parameters adjustable in semi-automatic mode Abb. 5 Blockdiagramm des Algorithmus zur automatischen Risserkennung; die grauen Felder bezeichnen veränderbare Parameter bei halbautomatischer Betriebsart

Fig. 10

 10 Fig. 10 Average depth (a) and interval (b) of lathe checks occurred in beech veneers of different thickness Abb. 10 a Mittlere Tiefe und b Abstand von Rissen in unterschiedlich dicken Buchenfurnieren

Fig. 11

 11 Fig. 11 Lathe checks of the beech wood veneer of different thickness: 0.7 mm (a), 1 mm (b), 1.5 mm (c), 2 mm (d), 2.5 mm (e), 3 mm (f), presented together with histograms (number of check occurrences on 1 m long veneer) of lathe checks depths (in % of thickness) and intervals Abb. 11 Risse in unterschiedlich dickem Buchenholzfurnier: a 0,7 mm, b 1 mm, c 1,5 mm, d 2 mm, e 2,5 mm, f 3 mm und zugehörige Balkendiagramme (Risstiefe und Rissabstände bezogen auf eine Furnierlänge von 1 m) der Risstiefe (in % der Dicke) und der Rissabstände

Acknowledgement

We wish to express our thanks to Conseil Régional de Bourgogne for its financial support given during presented research.

The first author wishes to thank LABOMAP team of ParisTech ENSAM Cluny for all the help provided during this project.

We all appreciate the help of Jakub Sandak from IVALSA Italy. Part of this work was presented on 3rd International Symposium on Veneer Processing and Products, Shanghai, China, 23-26 Oct 2007 and on 2007 IUFRO All Division 5 Conference, Taipei: Forest Products and Environment -A Productive Symbiosis, October 29th-November 2nd, 2007.


Anne Bouillard

Thomas Nowak

Fast Symbolic Computation of the Worst-Case Delay in Tandem Networks and Applications

Keywords: performance analysis, worst-case delay, network calculus, stochastic network calculus

Computing deterministic performance guarantees is a defining issue for systems with hard real-time constraints, like reactive embedded systems. In this paper, we use burst-rate constrained arrivals and ratelatency servers to deduce tight worst-case delay bounds in tandem networks under arbitrary multiplexing.

We present a constructive method for computing the exact worst-case delay, which we prove to be a linear function of the burstiness and latencies; our bounds are hence symbolic in these parameters. Our algorithm runs in quadratic time in the number of servers. We also present an application of our algorithm to the case of stochastic arrivals and server capacities. For a generalization of the exponentially bounded burstiness (EBB) model, we deduce a polynomial-time algorithm for stochastic delay bounds that strictly improve the state-of-the-art separated flow analysis (SFA) type bounds.

Introduction

With the explosive growth of embedded systems, which often have hard real-time constraints, having efficient tools for computing worst-case performance bounds for those systems has become a necessity. Several methods for deriving network performance bounds have been subsumed under the network calculus formalism: From local and simple description of the system elements, one derives deterministic performance bounds for the network. Servers and the flows circulating in the network are described by service curves and arrival curves. These functions provide guarantees on the minimal amount of service provided by the servers and on the shape of incoming traffic. In the past, deterministic guarantees have provided the analytical framework for Internet QoS (DiffServ/IntServ) [START_REF] Parekh | A generalized processor sharing approach to flow control in integrated services networks: the single-node case[END_REF][START_REF] Parekh | A generalized processor sharing approach to flow control in integrated services networks: the multiple-node case[END_REF], switched networks [START_REF] Chang | Load balanced Birkhoff-von Neumann switches[END_REF][START_REF] Chang | Load balanced Birkhoff-von Neumann switches, part II: multi-stage buffering[END_REF][START_REF] Cruz | Quality of service guarantees in virtual circuit switched networks[END_REF], and Video-on-Demand [START_REF] Mcmanus | Video-on-demand over ATM: constant-rate transmission and transport[END_REF].

More recently, deterministic bounds have become especially useful in the context of large embedded networks

Email addresses: anne.bouillard@ens.fr (Anne Bouillard), thomas.nowak@ens.fr (Thomas Nowak) Preprint submitted to Performance Evaluation November 20, 2015 like AFDX (Avionics Full Duplex) [START_REF] Boyer | PEGASE -a robust and efficient tool for worst-case network traversal time evaluation on AFDX[END_REF]. Among other methods for computing worst-case performance bounds, one can cite model-checking, which enables to compute accurate performance bounds but has a prohibitive algorithmic cost [START_REF] Chakraborty | Event count automata: a state-based model for stream processing systems[END_REF], or the trajectorial method [START_REF] Martin | Worst case end-to-end response times of flows scheduled with FP/FIFO[END_REF], where worst-case delay bounds are given by the solution of a fixed-point equation. One main advantage of network calculus over these methods is its modularity and its scalability that permits to analyze large and complex networks.

Recent years have seen several advances for deducing tight network performance bounds. On one hand, there were several attempts to improve the computations of the end-to-end performances. Indeed, classically, the performances are computed using (min,plus) operations, which introduce a certain pessimism to the analysis. The methods used range from the exhaustive computations, which can be performed only for small networks [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF], approximate methods that are exact for subclasses of networks [START_REF] Lenzini | Tight end-to-end per-flow delay bounds in FIFO multiplexing sink-tree networks[END_REF]. More recently, exact methods [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF][START_REF] Bouillard | Exact worst-case delay for FIFO-multiplexing tandems[END_REF] using linear programming have been proposed. Unfortunately, the solution is given as the solution of an optimization problem, which makes the use of this method difficult for solving more general issues, such as optimizing on a parameter.

On the other hand, stochastic versions of network calculus have been defined. This stochastic network calculus (SNC) started with the work of Chang [START_REF] Chang | Stability, queue length and delay of deterministic and stochastic queueing networks[END_REF], and several models have since been derived. The main approach is to mix the basic results of network calculus with large deviation theory. Reviews of these results can be found in [START_REF] Jiang | Stochastic Network Calculus[END_REF][START_REF] Fidler | Survey of deterministic and stochastic service curve models in the network calculus[END_REF][START_REF] Chang | Performance Guarantees in Communication Networks[END_REF]. Many studies focus on the case of a single server and multiple flows. Different service policies are studied [START_REF] Liebeherr | On the impact of link scheduling on end-to-end delays in large networks[END_REF], and very sophisticated results show that SNC can be adapted to a variety of service policies [START_REF] Poloczek | Scheduling analysis with martingales[END_REF]. Network analysis has received less attention. End-to-end delay bounds are computed in presence of disjoint cross-traffic in [START_REF] Burchard | A min-plus calculus for end-to-end statistical service guarantees[END_REF]. Also, the study of stochastic network calculus opens new fields of application for network calculus, such as smart-grids [START_REF] Wang | A stochastic power network calculus for integrating renewable energy sources into the power grid[END_REF] and soft real-time systems [START_REF] Santinelli | A component-based framework for modeling and analyzing probabilistic real-time systems[END_REF].

In the present paper, we present two main contributions. The first concerns deterministic networks. When the arrival curves are burst-rate and the service curves are rate-latency, we present an explicit construction for the optimal residual service curve and exact worst-case delay of an arbitrary flow crossing a tandem network. In particular, we show that the residual service curve is rate-latency and that the latency (and hence also the worst-case delay) is a polynomial of degree one in the latencies of the servers and the bursts of the flows.

Secondly, we extend our analysis to the stochastic settings and compare it to results that can be obtained from the literature. Our algorithm produces stochastic delay bounds in polynomial time for the case of convex error probability functions, like the exponentially bounded burstiness (EBB) model. The bounds are always better than those coming from a separated flow analysis (SFA) of the network. We also discuss how to adapt our results to more general stochastic frameworks and the difficulties that are involved.

The remaining of the paper is organized as follows. In Section 2, we give our model definition for deterministic networks. In Section 3 we present our algorithm to compute the worst-case delay in deterministic tandem networks. In Section 4, we show how the result can be used in the stochastic setting to optimize the error probability in tandem networks. The conclusion is in Section 5. The appendix contains serveral supplementary proofs and discussions of our approach.

Framework and Model

We denote by N the set of non-negative integers {0, 1, . . .} and for all n ∈ N, we set [[n]] = {1, . . . , n}. For

x ∈ R, we set (x) + = max(x, 0). We write R + for the set of non-negative reals.

General Model

While our model is in line with the standard definitions of networks calculus, we present only the material that is needed in this paper. A more complete presentation of the network calculus framework can be found in the reference books [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF][START_REF] Chang | Performance Guarantees in Communication Networks[END_REF].

Flows of data are represented by non-decreasing and left-continuous functions that model the cumulative processes. More precisely, if A represents a flow at a certain point in the network, A(t) is the amount of data of that flow that crossed that point in the time interval [0, t), with the convention A(0) = 0. More formally, let F = {f : R + → R |f is non-decreasing, left-continuous, and satisfies f (0) = 0}.

A system S is a non-deterministic relation between input and output flows, where the number of inputs is the same as the number of outputs: S ⊆ F m × F m and there is a one-to-one relation between the inputs and the outputs of the system, such that to each input flow corresponds one and only one output flow that is causal-no data is created inside the system-meaning that for (

(A i ) m i=1 , (B i ) m i=1 ) ∈ S, ∀i ∈ [[m]], A i ≥ B i . The vector ((A i ) m i=1 , (B i ) m i=1 ) is an (admissible) trajectory of S if ((A i ) m i=1 , (B i ) m i=1 ) ∈ S. If m = 1, i.
e., the system has exactly one incoming and one outgoing flow, then we will also refer to it as a server.

Arrival curves. The notion of arrival curve is quite simple: The amount of data that arrived during an interval of time is a function of the length of this interval. More formally, let α ∈ F. A flow is constrained by the arrival curve α, or is α-constrained if ∀s, t ∈ R + with s ≤ t : A(t) -A(s) ≤ α(t -s).

A typical example of such arrival curve are the pseudo-affine burst-rate functions: α b,r : 0 → 0; t → b+rt, if t > 0. The burstiness parameter b can be interpreted as the maximal amount of data that can arrive simultaneously and the rate r as a maximal long-term arrival rate.

Service curves. The role of a service curve is to constrain the relation between the input of a server and its output. Let A be an cumulative arrival process to a server and B be its cumulative departure process.

Several types of service curves have been defined in the literature, and the main types are the simple and strict service curves, which we now define.

We say that β is a simple service curve for a server

S if ∀(A, B) ∈ S : A ≥ B ≥ A * β, with the convolution A * β(t) = inf 0≤s≤t A(s) + β(t -s). An interval I is a backlogged period for (A, B) ∈ F × F if ∀u ∈ I, A(u) > B(u). The start of the backlogged period of an instant t ∈ R + is start(t) = sup{u ≤ t | A(u) = B(u)}.
As both A and B are left-continuous, we have A start(t) = B start(t) , and start(t), t is always a backlogged period.

We say that β is a strict service curve for server S if ∀(A, B) ∈ S : A ≥ B and for all backlogged periods (s, t]: B(t) -B(s) ≥ β(t -s). The name strict service curves implies a difference to simple service curves.

Works on the comparisons between the different types of service curves can be found in [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF][START_REF] Bouillard | Comparison of different classes of service curves in network calculus[END_REF]. In this article, we will mainly deal with strict service curves, but will make use of the convolution A * β used to define simple service curves.

A typical example of a service curve are the rate-latency functions: β R,T : t → R • (t -T ) + , where T is the latency until the server has to become active and R is its minimal service rate after this latency.

Note that a server S may not be deterministic, as the function β only corresponds to a guarantee on the service offered. Among this non-determinism, we will focus on two modes of operation:

• Exact service mode: During a backlogged period (s, t], the service is exact if for all u ∈ (s, t] we have B(u) = A start(t) + β u -start(t) . (In this case, start(u) = start(t).)

• Infinite service mode: During an interval of time (s, t], the service is infinite if ∀u ∈ (s, t] : B(u) = A(u), i.e., the server serves all data instantaneously.

For a system S ∈ F m × F m with m inputs and outputs, we say that S offers a strict service curve β if the aggregate system is, that is, if

∀ (A i ) i∈[[m]] , (B i ) i∈[[m]] ∈ S :   i∈[[m]] A i , i∈[[m]] B i   ∈ S(β).
We assume no knowledge about the service policy in this system (except that it is FIFO per flow).

Performance guarantees. In this article, we focus on the worst-case delay of a flow in a network. Let (A, B) ∈ F 2 be an admissible trajectory of a server. The delay of a bit that arrives at time t is d(t) = We are interested in the bit of data that suffers the maximal delay. This bit will be called in the following the bit of interest. Due to the left-continuity assumption, its formal definition is not straightforward. A bit of interest can be associated with a quantity of data x and for each process A having that bit of data, there must exists t A,x such that ∀t > t A,x : A(t) ≥ x and ∀t < t A,x : A(t) < x. It coincides with the infimum t A,x = inf{t ∈ R + | A(t) ≥ x}. We call t A,x the time that data x leaves flow A. Denote by

rg(A) = {x ∈ R + | ∃t ∈ R + : A(t) ≥ x} the range of A. The worst-case delay of trajectory (A, B) is then equal to d max = sup x∈rg(A) t B,x -t A,x .

Tandem Networks

Throughout the paper, we consider networks in tandem only: Assume a sequence of n servers numbered from 1 to n and m flows, flow i crossing servers s i to d i in order, with s i ≤ d i . Figure 1 depicts a tandem network with 3 servers and 3 flows. We have s 1 = s 2 = 1, d 2 = s 3 = 2 and d 1 = d 3 = 3. For a server j, we set Fl(j) the set of flows that crosses that server. In the example network, Fl(1) = {1, 2}, Fl(2) = {1, 2, 3}, and Fl(3) = {1, 3}.

Concerning the arrival and service guarantees, we assume the following:

• Flow i ∈ [[m]] has a burst-rate arrival curve α i : 0 → 0; t → b i + r i t. • Server j ∈ [[n]
] offers the strict rate-latency service curve β j : t → R j (t -T j ) + .

We aim at finding the worst-case delay of a given flow of an admissible trajectory. Formally, we call trajectory a collection of cumulative arrival and departure processes for each flow at each server it crosses.

We say that a trajectory is admissible if the processes satisfy the network calculus constraints given by the arrival curves of the flows and the strict service curves of the servers. We denote by F (j-1) i (resp. F (j) i ) the cumulative arrival (resp. departure) process of flow i at server j. The trajectory (F

(j) i ) is admissible if • ∀i : F (si-1) i
has arrival curve α i and

• ∀j : ((F (j-1) i ), (F (j) i )) has a strict service curve β j .
We assume that we focus on the worst-case delay of a flow that crosses every server. Assume it is flow 1.

The goal is to compute sup

x∈rg(F (0) 1 ) t F (n) 1 ,x -t F (0) 1 ,
x . To this aim, let us introduce the dates we will focus on for given admissible trajectory and bit of interest x.

Set t n = t B,x , the departure date of the system of the bit of interest. Then, t j , j ≤ n are defined recursively by setting t j-1 = start j (t j ) where start j is the start of the backlogged period at server j.

Worst-Case Delay in Deterministic Tandem Networks

In this section we present the main contribution of this paper, that is, the construction of a worst-case delay trajectory for tandem networks. We prove that we need to focus on limited number of trajectories only. Then, the delay of the bit of interest can be explicitly computed for these trajectories. Moreover, it is not necessary to compute the delays for all those trajectories, as a greedy algorithm enables to find one with the largest delay. Interestingly, the worst-case delay turns out to be an affine function of the burstiness of the arrivals and the latencies of the servers.

We first present several properties of a worst-case trajectory that can be assumed to hold, and then present the construction of the worst-case trajectory that lead to the worst-case delay.

Properties of a Worst-Case Scenario

Several scenarios can lead to the worst-case delay. In this subsection, we show that we can construct a worst-case scenario with certain additional properties that facilitate its analysis. This permits to consider only a limited number of scenarios to find the worst-case delay. Let us first state them and next comment them.

(H 1 ) Service policy is SDF (shortest-to-destination first): for two flows i and j, if d i < d j , then flow i is served with higher priority than flow j.

(H 2 ) Server j has the unique backlogged period (t j-1 , t j ) and provides infinite service outside its backlogged period.

(H 3 ) Each server provides exact service in its backlogged period and t j -t j-1 ≥ T j .

(H 4 ) The new arrivals at server j are maximal from time t j-1 on and zero before that.

(H 5 ) The bit of interest that suffers the longest delay is b 1 , the burstiness of flow 1.

It is proved in [START_REF] Bouillard | Worst-case delay bounds with fixed priorities using network calculus[END_REF]Theorem 8] that any admissible trajectory can be replaced by another satisfying (H 1 ) and (H 2 ) and such that the delay of the bit of interest increases. The transformation does not modify the arrival processes and the global service offered by a server during its backlogged period. The result is quite intuitive: Firstly, the SDF policy is known for being among the ones that can make a cyclic network unstable. Secondly, we focus on the delay suffered by one bit of interest. Its delay depends only on the service provided in the backlogged periods it belongs to. So these backlogged periods should be charged as much as possible for the worst-case delay. Hence, the upstream servers should transmit their backlogs instantaneously and simultaneously to the newly backlogged server. A direct consequence is that the bit of interest leaves server j at time t j .

Lemma 1. For any admissible trajectory T , there exists an admissible trajectory T satisfying (H 3 ) and that does not modify the arrival processes and whose maximum delay is larger.

Proof. Let T = (F (j)
i ) be a trajectory and B the bit with the worst-case delay. Suppose there exists a backlogged period (t j-1 , t j ) where the service offered by server j is not exact. The quantity i∈Fl(j) (F

(j) i (t j ) - F (j-1) i (t j-1
)) = B is the quantity of data served during [t j-1 , t j ) by server j. There exists t such that β j (t ) = B and, because β j is a strict service curve for server j, we have

t > t j -t j-1 . Set d = t -t j + t j-1 .
As a consequence, one can replace F (j) i by F (j) i , which is modified only in its backlogged period (t j-1 , t j ).

The backlogged period becomes (t j-1 , t j +d), the service is exact and for all i ∈ Fl(j),

F (j) i (t j +d) = F (j) i (t j ).
Replace every cumulative function

F (k) i after t j by F (k) i (t) = F (k) i (t + d).
The trajectory is still admissible and the delay of bit B is increased by d. Note that if B = 0, then one can take t = T j .

Lemma 2. For any admissible trajectory T , there exists an admissible trajectory T satisfying (H 4 ) and whose maximum delay is larger.

Proof. From (H 2 ), one can assume without loss of generality that (t j-1 , t j ) is the unique backlogged period for server j, and then that if flow i starts at server j, then

F (si-1) i (t) = 0 for all t ≤ t j-1 . Let T = (F (j) i )
and consider the trajectory T = ( F (j) i ) where for all t ≥ 0 :

F (si-1) i (t) = α i ((t -t si-1 ) +
) and the rest of the trajectory is the same as T . Note that by doing so, the arrival time of the bit of interest decreases.

As the arrival processes increase, for server 1, (t 0 , t 1 ) is still a backlogged period, and the backlog transmitted to server 2 at time t 1 is greater than for trajectory T . By induction, this is also true at each server: (t j-1 , t j ) is still a backlogged period for server j and the backlog transmitted at time t j to server j + 1 increases. Then t n is still in the backlogged period of server n, and if all the backlog is served at time t n , then the departing time of the bit of interest is unchanged, hence the result. If there is no server j (including server n) for which the backlog transmitted to the next server is 0 at time t j , then bit x does not suffers the largest delay: There exists a bit y < x of flow 1 that exits at the same time, but arrives strictly before. Bit y is transmitted at the same time as x.

2 r 2 t 1 t 0 t 1 b 3 x 1 server 1 server 2 server 3 t 2 t 2 t 3
Now suppose that there is a server j that transmits no backlog at time t j . This means that there is an ε > 0 such that during the interval of time [t j -ε, t j ], flow 1 is served at rate

ρ = R j - i∈Fl(j)\{1} r i > r 1 , (1)
since (H 1 ), . . . , (H 4 ) are satisfied. The delay of bit x can be decomposed in d = d 1 + d 2 , where d 2 = t n -t j and d 1 = t j -t , where t is the arrival time of bit x at server 1.

Replace t k by t k -ε for all k > j and replace the arrival processes accordingly (if

s i > j, then F (si-1) i (t) = F (si-1) i (t + ε)). By (1), the delay of bit y = x -ρε is d 1 + d 2 , where d 1 < d 1 .
As a consequence, x does not suffer the largest delay. This is true for all x > b 1 , and, hence, b 1 suffers the largest delay for some trajectory.

As the bit of interest is b 1 , we can and will set the rate of the flow of interest to r 1 = 0.

Figure 2 illustrates the properties (H 1 ), . . . , (H 5 ) a scenario should have for the analysis in the next section. The only non-determinism now are the start times t j of the backlogged periods, which also define the bursts that are transmitted from a server to the next one. In server 1, the dashed line is

F (0)
2 , the plain line above is

F (0) 1 + F (0)
2 , and the bottom is

F (1) 1 + F (1) 2 . When F (0) 2 ≤ F (1) 1 + F (1)
2 , flow 2 is not backlogged in server 1 (because of the SDF service policy). Then at time t 1 , the burst of size x 1 transmitted belongs to flow 1 only. The same hold for server 2 (from bottom to top, according to the SDF policy, F

2 , F

2 + F (1) 3 , F (1)
2 + F

(1)

3 + F

(1) 1 are drawn). At time t 2 , the burst of size x 2 is sent to server 3, which is shared between flows 1 and 3.

Computation of the Worst-Case Scenario

Using the properties above, we can build a worst-case trajectory with the following properties: Each server j has only two modes: infinite server or exact server (during the backlogged period (t j-1 , t j )). This means that at time t j-1 , server j -1 transmits all its backlog to server j. Furthermore, the flows i entering the network at server j send their burst b i at time t j-1 . Afterward, the arrival rate of data at server j is exactly i∈Fl(j) r i .

The service policy is SDF, but it should be clear that flows crossing server j and having the same destination do not need to be distinguished. We will introduce notation that distinguishes flows only by their destination.

To compute the worst-case trajectory, we only need to decide when the servers are exact. For example, if from time t j-1 server j -1 serves as an infinite server, it will transmit data to server j, and the delay from time t j-1 depends only on the quantity of these data for any destination and on the parameters of servers j, . . . , n. We denote this delay by ∆ j (x j , . . . , x n ). It is the delay from server j of the bit of interest, that is

t n -t j-1 if
x k is the burst transmitted at t j-1 to server j by the flows ending at server k, for k ≥ j. Finally, the worst-case delay is D = ∆(0, . . . , 0). We will show by induction that:

(A) ∆ j is affine in the x k , T k , and b i . More precisely we can write ∆ j (x j , . . . ,

x n ) = D j + n k=j x k R k j
, where R k j only depends on the R k and r i , and D j is a polynomial of degree 1 in the T k and b i (with coefficients depending on the R k and r i only).

(B) R k j ≥ R k+1 j .
This inequality (B) is quite intuitive: the coefficient R k j roughly corresponds to the service rate of flows ending at server k in the servers j, . . . , k. It means that a flow that has higher priority received a larger service rate than a flow with lower priority.

Algorithm 1 outputs the worst-case delay of the tandem network as an affine function

D = j∈[[n]] λ j T j + i∈[[m]] µ i b i .
It uses the following additional notations:

• b k j = i, si=j
,di=k b i size of the burst arriving at server j at time t j-1 belonging to flows starting at server j and ending at server k;

• r k j = i, si≤j,di=k r i arrival rate at server j for all flows ending at server k and crossing j (remember that we fixed r 1 = 0);

Algorithm 1: Worst-case delay algorithm begin R n n ← R n -r n n ; for j from n -1 to 1 do k ← n; while R k j+1 < (R j - k =j r j ) 1 + n =k+1 r j R j+1 -1 do R k j ← R k j+1 ; k ← k -1; for from j to k do R j+1 ← (R j - k =j r j ) 1 + n =k+1 r j R j+1 - 1
; ;

for j from 1 to n do λ j ← 1 + n =j r j /R j ; ; for i from 1 to m do µ i ← (R di si ) -1 ;
Theorem 1. Consider a tandem network of n servers offering rate-latency service curves β j : t → R j (t -

T j ) + , j ∈ [[n]
] and crossed by m flows with pseudo-affine arrival curves

α i : t → b i + r i t, i ∈ [[m]]. The expression D = j∈[[n]] λ j T j + i∈[[m]] µ i b i
where the λ j and µ i are the outputs of Algorithm 1 is the worstcase delay of a tandem network. The coefficients λ j and µ i depend only on

(r i ) i∈[[m]] and (R j ) j∈[[n]] . D can be effectively computed in time O(n 2 + m).
Due to space limitations, the proof of this theorem is postponed to Appendix A.

From this theorem, a (simple) service curve can be derived for flow 1. Intuitively, it is the inverse of the function ∆(0, 0, . . . , 0) = D(b 1 ) seen as a function of b 1 . It is then a rate-latency function. The next theorem proves this and states that this is the best service curve that can be found for flow 1 crossing this system.

Note that the rate of this function is easyly computed by min j∈[[n]] R j -i∈Fl(j) r i , the latency is D(0).

Ser. 2 1 R2-r1-r2 ≥ 1 R3-r2 1 R2-r1-r2 < 1 R3-r2
Ser. 1

1 R1-r1 ≥ 1 R2-r1-r2 1 R1-r1 > 1 R2-r1-r2 1 R1-r1 ≥ 1 R3-r2 R 3 (R 2 -r 1 )(R 3 -r 2 ) ≤ 1 R 1 -r 1 < 1 R 3 -r 2 otherwise a b 2 + b 1 + r 2 T 1 0 b 1 + b 2 + r 2 T 1 0 0 b b 3 + (r 2 + r 3 )T 2 b 1 + b 2 + b 3 0 0 0 +r 2 T 1 + (r 2 + r 3 )T 2 c 0 0 r 3 T 2 r 2 T 2 b 2 + r 2 (T 1 + T 2 ) d 0 0 b 3 + r 3 T 2 b 3 + b 1 + r 3 T 2 b 3 + b 1 + r 3 T 2
Table 1: Worst-case delay for the tandem network in Figure 1.

Theorem 2. The curve β R,T with R = min j∈[[n]] R j -i∈Fl(j) r i and T = D(0) is a service curve for flow 1 and there is no function β ∈ F greater than β R,T that is a service curve for flow 1.

Proof. Let us first prove that there exists no β > β R,T that is a service curve for the system. Suppose that β(s) > β R,T (s). Then there exists u > s such that β(s) = β R,T (u) = b. By Theorem 1, the worst-case delay for the arrival process A : t → b1 t>0 is u. But A * β(s) = b, so the delay obtained using β is less than u. So β cannot be a service curve.

We now show that β R,T is a service curve. Let A be a cumulative arrival process for flow 1 and B its output process. Let t n > 0, and define t 0 as in the notations, that is,

t 0 = start 1 • start 2 • • • • • start n (t n ). Set b = B(t n ) -A(t 0 ). Then from Theorem 1, t n -t 0 ≤ ∆(0, . . . , 0) = D(b 1 ), so b 1 ≥ β R,T (t n -t 0 ). As a consequence, B(t n ) = A(t 0 ) + b 1 ≥ A(t 0 ) + β R,T (t n -t 0 ) ≥ A * β R,T (t n ).

Example

Consider the example of Figure 1 and assume we want to compute the delay of flow 3.

We compute ∆ 3 , ∆ 2 and then ∆ 1 .

Server 3: ∆ 3 (x 3 ) = T 3 + x3+r3T3 R3-r3 (we do not take r 1 into account as the worst-case delay is obtained at the burst);

Server 2: if 1 R2-r2-r3 ≥ 1 R3-r3 , then ∆ 2 (x 2 , x 3 ) = T 2 + T 3 + x 2 + r 2 T 2 + b 2 + x 3 + r 3 T 2 R 2 -r 2 -r 3 . Otherwise ∆ 2 (x 2 , x 3 ) = T 2 + T 3 + R 3 (x 2 + r 2 T 2 ) (R 2 -r 2 )(R 3 -r 3 ) + b 3 + x 3 + r 3 T 2 R 3 -r 3 .
Server 1: According to our construction, there are be 5 cases to consider. The delay has a general form

D = T 1 + T 2 + T 3 + r3T3 R3-r3 + a R1-r2 + b R2-r2-r3 + cR3 (R2-r2)(R3-r3) + d R3-r3
, where a, b, c, d are shown in Table 1.

Comparison with the State of the Art

The problem of computing exact worst-case delays is a long-standing problem in the literature. As far as arbitrary multiplexing is concerned, this problem has been extensively studied in [START_REF] Schmitt | Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch[END_REF], where the authors first present the difficulties of obtaining closed formulas, even for the trivial case of two flows crossing two servers.

Then they completely study the case of the tandem network depicted in Figure 1. Their analysis exhibits 5

cases leading to 4 different formulas. The worst-case scenario the author construct is slightly different than the one constructed in Section 3.3 as they do not assume that the backlogged periods are disjoint, leading to a case distinction that is more intricate than the one we presented. However, we checked that the cases we found for this network are exactly the same as theirs, and so we compute exactly the same delays. Note that we have 5 different cases instead of 4 because we take into account the service time of the burst of the flow of interest. Apart from this service time, the third and fourth cases are similar.

Secondly, some work has been done to compute worst-case delays in feed-forward network using linear programs in [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF]. In the case of tandem network the authors show that it can be done by solving a single linear program making the procedure polynomial in time. They can handle more general arrival and service curves. We believe that our approach can easily be generalized to obtain good approximations in general feed-forward network, which is, due to space limitation, beyond the scope of this article. The generalization to general concave or convex arrival and service curves would be more demanding, as delay would not be an affine function anymore. One drawback of the method in [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF] is that no intuition is provided for the construction of the worst-case trajectory and then a slight modification of the parameters cannot be handled, which is a major issue with this method. In particular, computing the residual service curve of the flow of interest is intractable with the method of [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF], as is explained in [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF]. Theorem 2 states that it can be done in polynomial time with our algorithm.

Moreover it is not possible to use the method of [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF] directly to optimize on a parameters b i or T j . We will provide a more explicit application in the next section, where we give an application to Stochastic Network Calculus, that requests to optimize on the parameters. We explain in Appendix B why we cannot apply [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF] to solve this problem.

Application to Stochastic Arrivals and Servers

In this section, we apply our results to a stochastic extension of network calculus. The results of this section provide an upper bound on the probability that a given stochastic system fails to satisfy a given delay bound. Along the way, we introduce a new definition for stochastic service curves, which is based on the notion of variable capacity nodes (VCNs), that plays the role of strict service curves. Indeed, until now, strict service curves have not received a lot of attention, with the notable exception of guaranteed rate curves (curves of type t → Rt).

In Section 4.1, we give the definitions of stochastic network calculus, including the new stochastic VCN service curves. In Section 4.2, we present the state-of-the-art method for deriving delay bounds in stochastic network calculus, and discuss a new result on the composability of stochastic curves. Section 4.3 introduces our new method for deriving delay bounds and proves its correctness. We provide numerical examples, including quantitative comparison to the state-of-the-art method, in Section 4.4. We discuss the stochastic model assumptions in Appendix C.

Stochastic Arrivals and Servers

Stochastic network calculus is a generalization of deterministic network calculus, in which the arrival processes and departures processes are stochastic processes. We now give the definition of the stochastic model we use in this paper.

Stochastic Arrival Curves

Let α ∈ F and ε t : R + → R + for every t ≥ 0. We say that the arrival process A is ε t , α -constrained if we have: ∀t ∀σ :

P ∃u ≤ s ≤ t : A(s) -A(u) > α(s -u) + σ ≤ ε t (σ)
, where "∃u ≤ s ≤ t" signifies the existence of u and s with u ≤ s ≤ t. We call ε t the error probability function. This definition is called the maximum virtual backlog centric (m.b.c.) model by Jiang and Liu [START_REF] Jiang | Stochastic Network Calculus[END_REF]. An important example process are families of burst-rate curves with a common arrival rate. In this case, we can choose the failure probability function to directly depend on the burst parameter b:

∀t ∀b : P u ≤ s ≤ t and A(s) -A(u) > b + r(s -u) ≤ ε t (b). (2)
An important family of typical choices for the error probability function, originating from an exponentially bounded burstiness (EBB) assumption, is of the form

ε t (b) = Ke ct-ab , (3)
with positive real constants a, c, and K. We call it the time-dependent EBB (tEBB) model. The EBB assumption was originally introduced by Yaron and Sidi [START_REF] Yaron | Performance and stability of communication networks via robust exponential bounds[END_REF] in the form ∀s, t : type (virtual backlog centric [START_REF] Cruz | Quality of service management in integrated services networks[END_REF]): For all r 2 > r 1 there exists an N such that ∀t : P ∃s : 3), by sacrificing an epsilon of its rate bound. On the other hand, in a heavy load scenario, this translation cannot be done, as there is no epsilon rate to spare.

P A(t) -A(s) > r 1 • (t -s) + b ≤ M e -
A(t) -A(s) > r 2 • (t -s) + b ≤ N e -

Stochastic VCN Service Curves

We now go on to define a similar stochastic definition for strict service curves. A desirable property of a service curve process would be to be independent of the arrival process. To come up with such a definition is not obvious from the definition of a strict service curve, which depends on the start times of backlogged periods, which clearly depend on the input. Fortunately, there exists an almost equivalent definition for strict service curves, the variable capacity node (VCN) service curve. For the classes of service curves we are interested in, these notions coincide (see [START_REF] Bouillard | Comparison of different classes of service curves in network calculus[END_REF] for mode details).

In deterministic network calculus, variable capacity nodes are defined as follows: A server offers a VCN service curve β if there is some C ∈ F such that ∀s < t :

B(t) = inf 0≤u≤t A(u) + C(t) -C(u) and
C(t) -C(s) ≥ β(t -s).
Intuitively, C(t) represents the amount of service offered by the server up to time t, and the relation between A, B, and C is a direct consequence of the Lindley equation, that is widely used in the context of queueing theory. For rate-latency curves, the notions of strict service and VCN service coincide (see next theorem). However, the extension to the stochastic setting is more natural to define with VCN service curves as it is not necessary to distinguish backlogged and non-backlogged periods of a stochastic process.

Theorem 3 ([24, Theorem 3]). Let β be a rate-latency curve. Then a deterministic server S offers β as a strict service curve if and only if it offers β as a VCN service curve.

Starting from this formulation, it is now easy to adapt the notion of service curve to the stochastic case:

Definition 1. Let β ∈ F and η t : R + → R + for every t ≥ 0. The service C offers a stochastic variable capacity node β with failure probability η if ∀t ∀θ :

P ∃u ≤ s ≤ t : C(s) -C(u) < β(s -u) -θ ≤ η t (θ).
In this case, we will say that C offers η t , β .

The equality B(t) = inf 0≤u≤t A(u) + C(t) -C(u) does not appear in the definition, as we assume that B is a stochastic process that deterministically depends on A and C.

Similarly to arrival curves, if the service curve is rate-latency, one can make η t depend on the latency T , i.e., ∀t ∀T :

P ∃u ≤ s ≤ t : C(s) -C(u) < R(s -u -T ) + ≤ η t (RT ).
In analogy to the tEBB constraint for arrival curves, we are led to consider a time-dependent exponentially bounded latency (tEBL) constraint, i.e., an error probability function for VCN service curves of the form

η t (RT ) = Le f t-gRT , (4)
with positive real constants f , g, and L.

An example where this kind of stochastic service guarantees naturally occur is the case of crossing highpriority flows that, themselves, have stochastically constrained arrivals; see Figure 3. Take, e.g., a single server with deterministic VCN service β(t) = Rt and a crossing stochastic tEBB arrival with α(t) = r h t and error probability function ε t (b) = M e ct-ab . If the server always serves the stochastic arrival with highest priority, then the residual service provided is tEBL constrained with service curve β(t) = (R -r h )t and error probability function η t (R -r h )T = M e ct-a(R-r h )T .

State-of-the-Art Delay Bounds

In this section, we present the state of the art for deriving probabilistic delay bounds in feed-forward networks. The following theorem sums up the single-node performance bounds in stochastic network calculus that are used as the basis for performance bounds of a network. It uses the definitions of the vertical distance Theorems 5.1, 5.4, and 5.12 in [START_REF] Jiang | Stochastic Network Calculus[END_REF]) to the case of VCN service curves. Our algorithm does not rely on them.

v(α, β) = sup s≥0 α(s) -β(s) , horizontal distance h(α, β) = sup{d ≥ 0 | ∃t ≥ 0 : α(t) > β(t + d)},
Theorem 4. Let A be the arrival process that is constrained by ε t , α and B the departure process that offers a VCN service of η t , β .

(i) Worst-case backlog: For all t ≥ 0 and all γ ≥ 0, P ∃s ≤ t :

A(s) -B(s) > v(α, β) + γ ≤ ε t * η t (γ);
(ii) Worst-case delay: For all t ≥ 0 and all γ ≥ 0, P ∃s ≤ t :

A(s -h(α + γ, β)) -B(s) > 0 ≤ ε t * η t (γ).
(iii) Constraint propagation: For all t ≥ 0 and γ ≥ 0,

P ∃u ≤ s ≤ t : B(s) -B(u) > α β(s -u) + γ ≤ ε t * η t (γ).
Theorem 4, together with similar results on the concatenation, superposition, and leftover service curve (cf. [15, Theorems 5.36, 5.42, 5.64]), allows for a worst-case delay analysis very similar to the deterministic case. Note, however, that the notion of stochastic worst-case delay bound is stronger than that used in [START_REF] Jiang | Stochastic Network Calculus[END_REF], which consists in bounding the probability of a delay occuring at a specific time instant. In particular, separated flow analysis (SFA) techniques can be adapted to the stochastic setting. We discuss the SFA technique and its generalization to stochastic arrivals and servers in more detail together with a comparison to our new algorithm in Section 4.3.

New Stochastic Delay Bounds

This section presents our algorithm for deriving upper bounds on the probability that the maximum delay passes a given delay bound. It requires the arrivals and servers to be burst-rate and rate-latency, respectively, and the error probability functions to be convex in the burst parameters σ i and the latency parameters θ j . These assumptions allow us to use convex programming to find the optimal bound among the family of bounds our analytic results of this section establish. Our algorithm is based on Algorithm 1, i.e., it focuses on sample paths instead of focusing on residual services at each server.

We again assume that we are given a tandem network of n servers with a set of m flows crossing it, and a distinguished flow of interest, flow 1. We assume that every arrival curve F

t , α i constrained where α i is a burst-rate curve and the error probability function ε

(i) t (σ i ) is convex in σ i .
For the servers, we assume that they provide a η (j) t , β j VCN service where β j is rate-latency and η

(j) t (θ j ) is convex in θ j .
In our numerical examples, we will use the exponentially bounded burstiness and latency (tEBB and tEBL) functions of ( 3) and ( 4), which are clearly convex in σ and θ.

Let D(σ 1 , . . . , σ m , θ 1 , . . . , θ n ) denote the worst-case delay of the deterministic tandem network with burst parameters σ 1 , . . . , σ m and delay parameters θ 1 , . . . , θ n : The arrival of flow i is deterministically (α i + σ i )constrained and server j provides a deterministic VCN service that is (β j -θ j ) + -constrained. Theorem 1

shows that D is an affine polynomial in the σ i and θ j , and Algorithm 1 allows to compute their coefficients.

The convexity assumption, together with the affinity of the system's delay in the burst and delay parameters, will allow us to use convex programming to find, for a given delay, the optimal assignment of the parameters that (a) allows the system to experience the given delay and (b) minimizes the probability bound given by the sum of the flows' and servers' error probability functions.

Theorem 5. Let S be a tandem network with n servers and m flows. Assume that the arrival of flow i is stochastically constrained by a burst-rate arrival curve with error probability function ε

(i)
t and that server j is stochastically constrained by a rate-latency VCN service curve with error probability function η (j)

t . Let σ 1 , . . . , σ m , θ 1 , . . . , θ n ≥ 0 and t ≥ 0. Denote by d = D(σ 1 , . . . , σ m , θ 1 , . . . , θ n ) the delay of the corresponding deterministic tandem network with burst parameters σ i and latency parameters θ j .

Then the probability that flow 1 experiences a delay of more than d up to time t is upper-bounded by:

P ∃s ≤ t : F (0) 1 (s -d) -F (n) 1 (s) > 0 ≤ m i=1 ε (i) t (σ i ) + n j=1 η (j) t (θ j ).
Proof. Because the function D(σ 1 , . . . , σ m , θ 1 , . . . , θ n ) is nondecreasing in all arguments, the event ∃s ≤ t :

F (0) 1 (s -d) -F (n)
1 (s) > 0 of violating the delay bound of d before time t implies that one of deterministic arrival or service assumptions was violated before time t. That is, one of the events ∃v ≤ u ≤ t :

F (0) i (u) - F (0) i (v) > α i (u -v) + σ i or ∃v ≤ u ≤ t : C j (u) -C j (v) < (β j (u -v) -θ j )
+ where C j denotes the capacity of server j. Taking the union bound now proves the claimed inequality.

As the sum of convex functions is convex and the constraint of the deterministic delay being equal to d is linear, hence convex, in the parameters σ i and θ j , the optimization problem in Figure 4 is a convex program.

By Theorem 5, its optimal value is indeed an upper bound on the probability that flow 1 experiences a delay of more than d up to time t. In fact, it is the best bound that we can achieve with Theorem 5.

We compare our approach with the SFA technique, which relies on the modularity of Network calculus.

For each server j it computes a residual service curve for the flow of interest (flow 1) as βj = (β j -αj ) + ,

where αj is a constraint on the cross traffic at server j, and then computes the global service for flow 1 , β, by computing the convolution of all βj . Then the end-to-end delay is bounded by the horizontal distance between the arrival curve of flow 1 and β.

For example, on the network of Figure 1, β1 = (β 1 -α 2 ) + , β2 = β 2 -(α 3 + α 2 β 1 ) + (we make an improvement compared to the classical SFA as from [START_REF] Bouillard | Worst-case delay bounds with fixed priorities using network calculus[END_REF]Theorem 8], the worst-case delay is obtained for the SDF service policy) and β3 =

β 3 -(α 3 [β 2 -(α 2 β 1 )] + ) + , hence SFA obtains a delay bound of h α 1 , (β 1 -α 2 ) + * β 2 -(α 3 + α 2 β 1 ) + * β 3 -(α 3 [β 2 -(α 2 β 1 )] + ) + .
With rate-latency VCN and burst-rate arrival curves, the delay bound obtained is also affine in the bursts and latencies. The optimization problem of Figure 4 can then be applied to obtain an error probability bound, which we call the sSFA bound. We denote sExact the solution of the convex program in Figure 4 that uses Algorithm 1 for the computation of the exact worst-case delay. The delays obtained with sExact will always minimize be better than those obtained with sSFA, simply because both use a deterministic bound and then the union bound as in the proof of Theorem 5. This technique benefits from having a tighter deterministic bound.

m i=1 ε (i) t (σ i ) + n j=1 η (j) t (θ j ) subject to D(σ 1 , . . . , σ m , θ 1 , . . . , θ n ) = d σ i ≥ 0, i = 1 . . . , m θ j ≥ 0, j = 1 . . . , n
Hence, sExact gives a tighter stochastic bound than sSFA since it starts with an optimal deterministic bound.

Numerical Examples and Comparison

In this section, we give numerical examples and comparisons for the tandem network in Figure 1. We used a MATLAB implementation of our algorithm and the CVX optimization package to carry out the computations.

We assume identical Bernoulli arrival processes that have a probability p = 0.15 to generate a bit every millisecond, i. for all t. This is an explicit tEBB error probability bound for the Bernoulli arrivals. We assume constant-rate servers with a rate of R = 1 180 b/s and additional independent high-priority cross-traffic at every server identical to the arrivals, which, by the discussion at the end of Section 4.1.2, gives a tEBL error probability bound for the service to flows 1, 2, and 3 at each server of P ∃u ≤ s ≤ t : C(s)-C(u) < (s-u-T ) + ≤ 436 424•e 0.00151•t-0.151•T where u, s, t, and T are measured in ms. This makes server 2 have a utilization rate of ρ = 4 • 150/1 180 ≈ 50.85%.

Figure 5 shows the bounds of the sExact and sSFA algorithms in the three-server system for the probability that the delay up to time t = 10 s is more than d for values of d between 0 s and 2 s. Both bounds are close to each other and larger than 10 12 for d = 0.02 s. After that, however, their ratio gets larger as d increases. (Note that the figure uses a logarithmic scale and thus their distance does not.) We observe that the bound of our sExact algorithm becomes meaningful, i.e., becomes less than 1, at d ≈ 1.74 s, whereas the bound of the sSFA algorithm becomes meaningful only at d ≈ 4.4 s. Figure 5 also contains simulation data for the network with Bernoulli arrivals. It uses N = 20 000 simulation runs and depicts the relative amount of runs in which the maximum delay up to t = 10 s is greater than d. This relative amount is strictly between 0 and 1 only for values of d between 0.78 s and 2 s. In this interval, the sSFA bound is still larger than 1. While there is still a considerable gap between the simulated maximum delays and the sExact bound, the plots suggest a similar slope of the simulated data and the sExact bound in logarithmic scale. This observation spawns further questions and directions for future research.

Conclusion

This paper presented a new and fast algorithm for computing the exact worst-case delay of tandem networks with arbitrary multiplexing when the arrivals are constrained by burst-rate arrival curves and the servers provide a rate-latency service curve. As a byproduct, we proved that the worst-case delay is, in fact, an affine function of the burstiness and latency parameters of the arrivals and servers. Our algorithm is the first that computes the linear coefficients and runs in time O(n 2 ).

Linearity in the burstiness and latency parameters allowed the extension of our bounds to the case where arrivals and server capacities are stochastic processes. For the case that the error probability functions are convex, e.g., the exponentially bounded burstiness (tEBB) and exponentially bounded latency (tEBL) models, we gave a polynomial-time algorithm based for finding stochastic delay bounds. We showed that our algorithm gives bounds at least as good as the state-of-the-art SFA-type method and provided a quantitative numerical comparison.

Future work will focus on finding the worst-case delay for specific multiplexing policies and more general topologies. As some of these problems are NP-hard even in feed-forward topologies, only approximations can be efficiently computed, but the quantification of such an approximation is an important issue. We would also like to further explore the gap between v.b.c.-type and m.b.c.-type stochastic models with respect to delay bounds. In particular, the correlation between the arrival processes and the events of breaking a constraint should be worth investigating. Inductive step: Computation of ∆ j from ∆ j+1 . Suppose that ∆ j+1 is known and satisfies the properties above. We first compute the delay induced from server j assuming that the service is exact for flows ending at server k (of before) and infinite for flows ending at server k + 1 (or after). Call ∆ k j this delay. This is a function of x k j the bursts transmitted by server j -1.

∆ k j (x j j , . . . , x n j ) is computed the following way: It takes time δ to serve flows ending at j, . . . , k, and data from any other flow is transmitted to server j + 1. This quantity of data is x j+1 = b j + x j + r j δ for > k where δ satisfies

k =j x j + b j + r j δ = R j (δ -T j ) + , i.e., δ = T j + k =j Q j / R j - k =j r j .
For > k, we then have the equality

x j+1 = Q j + r j k =j Q j R j - k =j r j . Then ∆ k j (x j j , . . . , x n j ) = δ + ∆ j+1 (0, . . . , 0, x k+1 j+1 , . . . , x n j+1 ) = T j + k =j Q j R j - k =j r j + D j+1 + n =k+1 1 R j+1 Q j + r j k =j Q j R j - k =j r j = T j + D j+1 + n =k+1 Q j R j+1 + k =j Q j R j - k =j r j 1 + n =k+1 r j R j+1
The other scenarios that should be taken into account is when part of the flows ending at k are served, and the other part is transmitted instantaneously to server j + 1 (due to the SDF service policy, only one flow can be partially served). When y k is this latter quantity, the worst-case delay from time t j-1 is

∆ k,y k j (x j , . . . , x n ) = T j + X + ∆ j+1 0, . . . , 0, y k , Q k+1 j + r k+1 j X, . . . , Q n j + r n j X = T j + D j+1 + X 1 + n =k+1 r j R j+1 + n =k+1 Q j R j+1 + y k R k j+1 where X = ( k =j Q j ) -y k / R j - k =j r j
. This is a linear function in y k . The next lemma shows that we can drop these "mixed" scenarios as they lead to shorter delays.

Lemma 4. ∀y k , ∆ k,y k j ≤ max(∆ k j , ∆ k-1 j ).
Proof. First notice that there exists α such that ∆ k,y

k j = ∆ k j + αy k with α = 1 R k j+1 - 1 + n =k+1 r j /R j+1 R j - k =k r j .
Depending on whether α is positive or negative (the null case is trivial), ∆ k,y k j is maximized when y k is maximized or for y k = 0.

If α is positive, then the delay is maximized with the maximal value for y k , which corresponds to not serving the flow ending at k at all and to ∆ k-1 j . If it is negative, then the delay is maximized by y k = 0, which corresponds to reducing the flow's backlog to 0 and to ∆ k j .

We now prove that there ∆ j is in fact on of the ∆ k j . In other words, ∆ j is affine.

Lemma 5. There exists k such that ∆ j = ∆ k j (that is, for all x j , . . . , x n , we have ∆ j (x j , . . . , x n ) = ∆ k j (x j , . . . , x n )) and for all k, R k j ≥ R k+1 j .

Proof. The proof is also by induction. We prove that ∀j, we have the equivalence

∆ j = ∆ k j ⇔ ∀k > k 1 R k j+1 > 1 R j - k =j r j 1 + n =k +1 r j R j+1 and 1 R k j+1 ≤ 1 R j - k =j r j 1 + n =k+1 r j R j+1 .
Assertion (B) is proved at the same time.

The equivalence above also state that if for all k > k ∆ j = ∆ k j , then ∆ n j ≤ ∆ n-1 j ≤ • • • ≤ ∆ k j . Let us assume this.

The coefficient of Q j in ∆ k j for all k ≤ k and > k is 1 R j+1

and that of Q k j is

• either

1 Rj -k =j r j 1 + n =k+1 r j R j+1
(for ∆ k j )

• or 1 R k j+1 (for ∆ j , < k).

Suppose that 1

R j - k =j r j 1 + n =k+1 r j R j+1 ≥ 1 R k j+1 .
(A.1) Moreover, for k < < k, the coefficient of

For ≤ k < k, the coefficient of Q j in ∆ k j is 1 R j - k =j r j 1 + n =k +1 r j R j+1 ≤ ≤ 1 R j - k =j r j 1 + n =k+1 r j R j+1 + k =k +1 r j R k j+1 ≤ 1 R j - k =j r j 1 + n =k+1 r j R j+1 + k =k +1
Q j in ∆ k j is 1 R k j+1 ≤ 1 R k j+1 ≤ 1 R j - k =j r j 1 + n =k+1 r j R j+1 , so ∆ k j ≥ ∆ k j and ∆ j = ∆ k j .
The same kinds of computations lead to ∆ k-1 j

> ∆ k j if 1 R k j+1 > 1 Rj -k =j r j 1 + n =k+1 r j R j+1
Set R k j according to the ∆ j that is computed (that is ∆ k j for some k). Then we still have R j ≤ R +1 j and (B) is true for server j.

calculus (see, e.g., [START_REF] Boudec | Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[END_REF]) that ∀s ≤ t : C 2 (t) -C 2 (s) ≥ β 2 (t -s) ∧ ∀u ≤ s = start(t) : C 1 (s) -C 1 (u) ≥ β 1 (s -u)

⇒ B 2 (t) ≥ A * β 1 * β 2 (t).
As a consequence, we can write: P B 2 (t) < A * β 1 * β 2 (t) ≤ P ∃s ≤ t : C 2 (t) -C 2 (s) < β 2 (t -s)

+ P ∃u ≤ ŝ = start(t) : C 1 (ŝ) -C 1 (u) < β 1 (ŝ -u) (C.1)
The term P ∃s ≤ t : C 2 (t) -C 2 (s) < β 2 (t -s) is at most η 2 by the service constraint for server 2.

Difficulties arise when wanting to bound the second probability. One cannot simply use the definition of the service constraint for server 1 because ŝ = start(t) is not a constant value. Buchard et al. [START_REF] Burchard | A min-plus calculus for end-to-end statistical service guarantees[END_REF] stated that the fact that ŝ is not a constant value, but a random variable, is what causes problems. We want to make the somewhat more precise statement that the problem lies in the potential dependency of ŝ and the violation of the service constraint. Denote by E t the event ∃s ≤ t : C 1 (t) -C 1 (s) < β 1 (t -s). In fact, we will show that the second probability of the sum in (C.1) is bounded by η 1 if ŝ is independent of E ŝ in the sense that the conditional probability P E ŝ | ŝ = s is equal to (or upper-bounded by) P(E s ).

But first, to have the conditional probability and also the event E ŝ well-defined, we need to show that ŝ is indeed a random variable, which is not trivial. Lemma 6. Let A be the arrival process and B the departure process of a server. Then start(t) is a random variable for every t ≥ 0.

Proof. We start by proving that every arrival and service process is separable. Indeed, we show the stronger claim that every (random) element of the function class F only depends on its values at the positive rationals Q + : So let F ∈ F and t ≥ 0. We choose an increasing sequence of positive rationals t k ∈ Q + with limit t k → t. By left-continuity, F (t) = lim F (t k ), i.e., the function value F (t) only depends on the function values F (t k ) at positive rationals.

Set D(t) = A(t) -B(t). Because of left-continuity, for all 0 ≤ s < t, we have the equivalence

∃s < τ ≤ t : D(τ ) = 0 ⇐⇒ ∃s < τ 1 < τ 2 < • • • < t : ∀k : τ k ∈ Q + ∧ D(τ k ) ≤ 2 -k (C.2)

Figure 1 :

 1 Figure 1: Tandem network with 3 servers and 3 flows.

  b

b 1 + b 2 r 2 + r 3 x 2 Figure 2 :Lemma 3 .

 122223 Figure 2: Trajectories satisfying (H 1 ), . . . , (H 5 ).

  ab to compute stochastic backlog bounds. They also showed [27, Theorem 1] that it is possible to translate this form of EBB constraint of t.a.c.-type (traffic amount centric) into a constraint of v.b.c.-

Figure 3 :

 3 Figure 3: Tandem network with crossing high-priority flows.

  and the deconvolution α β(t) = sup τ ≥0 α(t + τ ) -β(τ ) of α and β. It is a generalization of existing results (cf.

Figure 4 :

 4 Figure 4: Convex program to bound the probability of a delay > d up to time t.

  e., they have an expected rate of r = 150 b/s. An application of [27, Proposition 3] with p = 0.15 and ε = 0.01 shows the t.a.c. guarantee that P A(t)-A(s) ≥ 0.16(t-s)+b ≤ e -αb where α is maximal such that pe α + 1 -p ≤ e (p+ε)α for all s and t measured in ms. The value of α is approximately α ≈ 0.151, for which the inequality still holds. Applying [15, Theorem 3.13(ii)] with θ = 0.01 gives the v.b.c. guarantee of P ∃s ≤ t : A(t) -A(s) > 0.17(t -s) + b ≤ e -0.151•b + θ -1 ∞ b e -0.151•y dy = (1 + 100/0.151) • e -0.151•b ≤ 659•e -0.151•b for all t. Finally, using [15, Theorem 3.24(ii)] with θ = 0.01, i.e., by relaxing the rate by another 10 b/s, we get the m.b.c. bound of P ∃u ≤ s ≤ t : A(s)-A(u) > 0.18(s-u)+b ≤ θ -1 b b-θt 659•e -0.151•y dy ≤ 100• ∞ b-0.01•t 659•e -0.151•y dy = (65 900/0.151)•e 0.00151•t-0.151•b ≤ 436 424•e 0.00151•t-0.151•b

Figure 5 :

 5 Figure 5: Stochastic delay bounds and simulations for three-server system.

Figure A. 6 :

 6 Figure A.6: Delay incurred at server n.

,

  which is the coefficient of Q j in ∆ k j . The first inequality uses (B) for server j + 1 and the second uses Ineq. (A.1).

Acknowledgments

The authors would like to thank Florin Ciucu for many comments on earlier versions of this paper.

Appendix A. Proof of Theorem 1

The worst-case delay is ∆ 1 (0, . . . , 0) and we need to to compute ∆ j . Define

As Q j is an affine function in T j , b j and x j , we only need to show that every ∆ j is affine in the Q j .

Initialization: Computation of ∆ n . The only burst that can be transmitted by server n -1 is for destination n. Suppose that a burst of size x n is transmitted at time t n-1 . It is obvious that the worst-case scenario is that the server is exact until the bit on interest is served.

The delay of the bit of interest is then the solution δ = ∆ n (x n n ) of the equation

To conclude, just remark that the delay for flow 1 is ∆ 1 (0, . . . , 0), which is a polynomial of degree 1 of the variables b i and T j . Lemma 5 also gives a polynomial greedy algorithm to compute the coefficients for every b i and T j in polynomial time, and an explicit construction for a worst-case scenario: Proceed backward from server n to server 1, and for each server k, there are n -k + 1 potential worst-case trajectories. Checking that one case is the actual worst-case trajectory can be done by checking one inequality. Those inequalities imply the computation of some constants (new flows arriving). As a flow enters the system at one server only, the total number of computations for constants is O(m). So, finding the actual worst-case can be done in O(n -k) operations (there is one inequality to check for each case) apart from the computation of the constants r j and b j , and the computation of the worst-case delay can be done in O(n 2 + m). Note that if every flow has a different path, then m = O(n 2 ) and computing the worst-case delay can be done in O(n 2 ).

Appendix B. About the Linear Programming Approach

Since other approaches to worst-case delay bounds already exist in the literature, we now want to explain the differences of our new formulation to existing ones.

In [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF], the linear program presented to compute the worst-case delay is of the form maximize AX subject to BX ≤ C and X ≥ 0.

Vector A and matrix B do not depend on the parameters Params = (σ 1 , . . . , σ m , θ 1 . . . , θ n ). Translating our approach naïvely into this formalism would lead to compute the minimum of a function with the constraint

The maximum cannot be dropped since we want to ensure a worst-case trajectory.

Another solution, following the lines of [START_REF] Bouillard | Tight performance bounds in the worst-case analysis of feed-forward networks[END_REF], would be to consider the dual problem: as A and B do not depend on P aram, the dual problem is (expressing the dependencies in the parameters)

Now, only the objective function depends on the parameters, and the optimal value is then obtained at a vertex of the convex set of the constraints. The delay can then be expressed as a minimum of a finite number of linear functions, but this number can be exponential in the number of constraints, which makes this solution intractable. -type conditions would need to be evaluated at a time t that is a random variable and not a constant value. In the rest of this section, we want to extend on this point by giving an in-depth explanation of the problem. By that, we give an argument for the usage of the m.b.c. model by showing that we would otherwise need to make very strong independence assumptions.

Let us focus on the simple example of the composition of two VCN servers and two flows crossing both servers with two stochastic service constraints of v.b.c.-type. That is,

We want to derive a (simple) service curve for the composed server. It is a result of deterministic network with probability 1. Setting V K equal to

we see that every V K is measurable and the sequence of the V K is nonincreasing. Hence the monotone limit

is measurable. Thus for every t ∈ R + , start(t) is a random variable as we can write

which is clearly a measurable set for every 0 ≤ s ≤ t.

We can then use the law of total probability P(E ŝ) = E P(E ŝ | ŝ) to show that the probability of interest P(E ŝ) is bounded by η 1 by monotony of the expected value because the conditional probability

On the other hand, if there is a tight correlation between the instant of violating the service constraint and ŝ, then this argument is not valid. Take, for instance, ŝ as the random variable

of the earliest instance ≤ t where the service constraint is violated, or 0 if it is not violated before time t.

Then, in fact, P(E ŝ) = P ∃u ≤ s ≤ t : C 1 (s) -C 1 (u) < β 1 (s -u) , which suggests that an m.b.c.-type constraint is more natural to consider if correlation cannot be ruled out.

A method for getting delay bounds for a chain of server with disjoint cross-traffic was introduced by Burchard et al. [START_REF] Burchard | A min-plus calculus for end-to-end statistical service guarantees[END_REF]. The key ingredient to their proof is to relax the latency of almost each server by a parameter a > 0. By that, they are able to circumvent the formally stronger assumptions of an m.b.c. model, which are know to lead to several zero-one-laws in certain cases. We believe that an adaption of their method can be combined with our approach.