Print indd

Fig. 1. Network topologies used
Table 1. Network parameters
Network
Nodes Links Demands
DI-YUAN 11
42
22
PDH
11
34
24
AFDX
8
15
200
NOBEL
28
41
200
Table 2. Probability distribution for
Δt = Δt
max
[d] for critical networks
Δt
125 25 500 1000 2000 4000 8000
P(Δt) [%] 2.5 7.5 15 50
15
7.5
2.5
of 10 for every link was assumed. The main properties of the networks under
study are provided in Table
1
.
The AFDX network used in this study follows the description in [
16
]. The
information useful for the problem considered in this paper is summarized in
Tables
3
and
4
.
Table 3. Number of VLANs from
source src to destination dst [
16
]
src/dst 1
2
3
4
5
6
7
8
1
71 78
34
2
72
77
34
3
90
212 35
42 52
4
97 134
37 35 48
5
80
72 64
6
82
61
52
7
52
47
59 67
8
51 45 43
52
Table 4. AFDX Frame lengths [
16
]
Frame length
(bytes)
Number
of VLANs
0–150
561
151–300
202
301–600
114
601–900
57
901–1200
12
1201–1500
35
>1500
3
4.1
Assumptions
In order to reduce the problem space, the following assumptions were made with
no loss of generality:
– src[d] = dst[d]
– separate output queue for each link

---

Network Optimization for Safety-Critical Systems
133
– identical switch capacities
– identical link capacities
– the bandwidth of an SDN switch is 10
7
Bits/s (compare [
19
])
Generally, the delay for each flow in the network is calculated as in (
2
). However,
as all terms save t
q
are constant (and depend on fixed, physical properties of the
network), they are assumed to be zero i.e. t
pp
= t
t
= t
pr
= 0. Thus the latency
solely depends on the number of flows sharing the link and the sending capacity
of the link.
Since the focus of this paper does not lie on the queuing model, a worst case
scenario is assumed (i.e. all demands need to be satisfied simultaneously) with
no preemption (FIFO). Thus a simplified model for the delay can be constructed
as follows:
Δt =

d
∈D

(i,j)
∈L
x[r,d,i,j]
·qnt[d]
bw
max
[i,j]
if the path traverses(i, j)
0
otherwise
(12)
To avoid including an additional dimension into the problem (and thus being
no longer able to use linear programming) an auxiliary variable y[r, d, i, j], with
r ∈ R, d ∈ D, (i, j) ∈ L is introduced where
∀r ∈ R : ∀d ∈ D : ∀(i, j) ∈ L : y[r, d, i, j] ≤ u · x[r, d, i, j]
(13)
with u = max(d
Δt
).
∀r ∈ R : ∀d ∈ D : ∀(i, j) ∈ L : y[r, d, i, j]
≥

r1
∈R

d1
∈D
x[r, d1, i, j] · qnt[d1]
bw
max
[i, j]
− (u · 1 − x[r, d, i, j])
(14)
and
∀r ∈ R : ∀d ∈ D : ∀(i, j) ∈ L : y[r, d, i, j] ≥ 0
(15)
applies. Consequently, the constraint for time delay of a flow can be simplified
from (
10
) to
∀r ∈ R, d ∈ D :

(i,j)
∈L
y[r, d, i, j] ≤ d
Δt
(16)
4.2
Baseline
For comparison with the optimization algorithm in this paper, the shortest path
and Dijkstra algorithm of Python’s networkx software package as well as two
simple heuristics are used. Additionally, the first heuristic (
Heur. Capa.) uses
Dijkstra’s algorithm until the link capacity is exceeded, at which point that link
can be no longer used, while the second (
Heur. EDF ) implements a simple Ear-
liest Deadline First (EDF) schedule, where the path with the smallest resulting
latency is selected for placement first and the placement of successive flows must
not violate the requirements of the previous ones. Those were selected as the
capacity and latency requirements were observed to be frequently violated by
applying the shortest path algorithms.

---

134
C. Perner