Print indd

Fig. 2. Results standard network (PDH)
5.2
Critical Networks
Empiric performance analyses showed that calculation time for optimization has
a nearly quadratic growth rate for every hundred demands (e.g. if a problem with
100 demands needs about 60 s to run, one with 200 needs about 275 s), while the
number of links and nodes do not have a pronounced effect. This is due to the
significant number of constraints that need to be created and evaluated, as the
placement of every demand influences every other demand in the network and
also the reason to use a smaller number of demands of 100 for AFDX.
What is more, while standard networks with around 20 demands can easily
and generally quickly be calculated with standard hardware and open-source
software, the constraints needed for the full AFDX dataset need more than the

---

136
C. Perner
Optim.
Dijkstra
Heur. Capa. Heur. EDF
5000
10000
15000
20000
25000
Relative cost
(a) Cost
Optim.
Dijkstra
Heur. Capa. Heur. EDF
75
100
125
150
175
200
225
Flow table entries
(b) Flow table entries
Optim.
Dijkstra
Heur. Capa. Heur. EDF
10
20
30
40
50
60
Latency (Std) [s]
(c)
Δt - Standard
Optim.
Dijkstra
Heur. Capa. Heur. EDF
50
100
150
200
250
300
Latency (Res) [s]
(d)
Δt - Resilient
Optim.
Dijkstra
Heur. Capa. Heur. EDF
0
250
500
750
1000
1250
1500
Used capacity (Link)
(e) Link capacity
Optim.
Dijkstra
Heur. Capa. Heur. EDF
2
3
4
5
6
Number of hops (Res)
(f) Number of hops (Res)
Fig. 3. Results resilient network (AFDX)
internal memory of the GNU Linear Programming Kit and half the dataset
already requires about 64 GB of RAM, thus making it only solvable on special
hardware and commercial software. The results for the flow placement with the
various algorithms can be obtained from Fig.
3
. As for the PDH network, the
results for the Dijkstra algorithm and the capacity-constrained heuristic are
identical in this case, as the largest possible capacities were taken from the
definitions, but this will not generally be the case.
The distribution of flow placements is depicted in Fig.
3
b. Here, the opti-
mization has the lowest number, while the Dijkstra and heuristics have a much
larger value on average. This is due to the much higher amount of hops for the
resilient path, which of course results in fewer entries per switch. This is also
reflected in the time delay Δt for the standard and the resilient case as shown

---

Network Optimization for Safety-Critical Systems
137
in Figs.
3
c and d. As with the standard networks, since the main goal of cost
minimization results on average in a significantly lower link utilization, which is
shown in Fig.
3
e and further illustrated by the number of hops for the resilient
case in Fig.
3
f. With one exception in the optimization solution, the number of
hops was uniformly one for all algorithms.