Print indd

5.1
Standard Networks
The results for the flow placement with the various algorithms can be obtained
from Fig.
2
, detailing the various performance characteristics. It can be noted
that the results for the Dijkstra algorithm and the capacity- constrained heuristic
are identical in this case, since the largest possible capacities from the definitions
were obtained, as k · qnt has to be transported due to the resilience requirement.
However, this cannot generally be assumed to be the case.
Figure
2
a shows that the cost varies significantly between the methods. While
the cost obtained through Dijkstra and the heuristics was identical through
all runs (since the different demands have not been considered), the cost for
the optimized rule placement varied significantly. What is more, it was only
about half of that obtainable through the other methods. The lower cost of the
EDF heuristic can be explained through the consideration of the latency, since
expensive links are not used by that many flows as the maximum number of
flows is mainly limited by the most critical demand placed there.
The distribution of flow placements is depicted in Fig.
2
b. Here, the Dijksta
and capacity heuristic both have a lower value since they only use the shortest
paths which means fewer hops for each flow and thus fewer flow table entries.
Additionally, the EDF heuristic has more than the optimization, since the former
uses the shortest path until one flow’s latency requirement is violated.
The time delay Δt for the resilient case is shown in Figs.
2
c and d. Here,
the optimization produces higher values than the other methods, since the cost
minimization leads to on average, a significantly lower link utilization, which is
shown in Fig.
2
e and further illustrated by the number of hops for the resilient
case in Fig.
2
f. In the standard case (not depicted) it was uniformly one (safe for
one flow in the optimization) and thus has a negligible impact.

---

Network Optimization for Safety-Critical Systems
135
Optim.
Dijkstra
Heur. Capa. Heur. EDF
3
4
5
6
7
×10
10
Relative cost
(a) Cost
Optim.
Dijkstra
Heur. Capa. Heur. EDF
5
10
15
20
25
Flow table entries
(b) Flow table entries
Optim.
Dijkstra
Heur. Capa. Heur. EDF
2
4
6
8
Latency (Std) [s]
(c)
Δt - Standard
Optim.
Dijkstra
Heur. Capa. Heur. EDF
5
10
15
20
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
4
6
8
Number of hops (Res)
(f) Number of hops (Res)