Programs and numerical experiments referenced in the INRIA Research report Tight performance bounds in the worst-case analysis of feed-forward networks, Anne Bouillard, Laurent Jouhet and Eric Thierry (INFOCOM 2010).
Tandem Networks
Program
Installation
nc-tandem-tight is a program that generates from a small source file the linear program to compute tight bounds in tandem networks under blind multiplexing and Network Calculus constraints. It has been written in Ocaml and compiled from nc-tandem-tight.ml. The compilation command is:
Usage
#this is a comment
nservers 3 #number of servers
nflows 3 #number of flows
objective 'd' 1 #objective 'd' i -> max delay for flow i; 'b' j -> max
backlog for server j
beginservers # keeping order is mandatory
server 1 (6,3); # beta1 (t)= 6(t-3)+
server 2 (7,0) (10,3); # beta2(t) = max (7t, 10(t-3)+)
server 3 (5,2) (6,3);
endservers
beginflows # keeping order is mandatory
flow 1 [1,3] (2,1) (1,3); #[first server, last server] alpha1(t) = min (2+t,1+3t)
flow 2 [1,2] (1,2);
flow 3 [2,3] (4,2);
endflows
The execution command
generates from the file file.txt a linear program file.lp that can be solved using lp_solve.
Examples
Feed-forward example: square network
We are interested in computing the worst-case delay of the bottom flow. There are 11 possible orders for the dates of interest, then 11 linear programs to solve: (files given with unfixed parameters, you may use an automatic replacement command to fix them)
- carre1-1.lp
- carre1-2.lp
- carre1-3.lp
- carre1-4.lp
- carre2-1.lp
- carre2-2.lp
- carre3-1.lp
- carre3-2.lp
- carre4-1.lp
- carre4-2.lp
- carre4-3.lp
The following linear program does not give a tight bound but approches the worst-case delay by taking only the common constraints of the 11 linear programs above.