|
3
Problem Formulation
Thus a software-defined network constituting of a number of network switches,
with a given topology and links between them is considered. Across this network
a number of demands needs to be routed. This network consists of network
switches s ∈ S, with the number of forwarding rules r
s
and the throughput of
the switch c
s
. The network links (i, j) ∈ L have a capacity c[i, j] of the link
(i, j) and cost a[i, j] of using this link. This network is used to satisfy the traffic
demands d ∈ R
3
from a source switch src
∈ S to a destination switch dst ∈ S.
Each demand is composed of a bandwidth demand qnt[d], a maximum latency
of d
Δt
and the resilience k required, i.e. how many independent paths must be
provided. Beyond the requirements originating from the traffic demands, three
constraints apply. Firstly, the maximum number of forwarding rules r
max
that
130
C. Perner
may be placed at each SDN switch. Secondly, the maximum capacity c
max
that
each switch can handle. Thirdly, the maximum bandwidth bw
max
of each link.
The traffic demands are satisfied through the according placement of flows
by the introduction of the variable x[r, d, i, j] ∈ X defined as
x[r, d, i, j] =
1
if d ∈ (i, j)
0
if d /
∈ (i, j)
.
(1)
where r = {1, . . . , k} of the resilient path, since this paper does not consider
multipath routing. The latency for each demand can be obtained from
(i,j)
∈L
t
q
[d] + t
pp
+ t
t
s
∈S
t
pr
= d
Δt
(2)
i.e. the sum of the delay due to propagation t
pp
, transmission t
t
, processing
t
pr
and queueing t
q
. This allows to formulate the minimum cost optimization
problem:
∀r ∈ R : min
d
∈D
(i,j)
∈L
a[i, j] · x[r, d, i, j] · qnt[d]
(3)
subject to the placement of all demands
∀d ∈ D :
r
∈R
(src[d],j)
∈L
x[d, src[d], j] = k
(4)
at the source node and all requests at the destination node:
∀d ∈ D :
r
∈R
(i,dst[d])
∈L
x[d, i, dst[d]] = k
(5)
To ensure flow continuation, it needs to be ensured that all required flows are
forwarded:
∀r ∈ R : ∀d ∈ D : ∀s ∈ S :
(j,s)
∈L
x[r, d, j, s] + (if s = src[d] then 1)
−
(s,j)
∈L
x[r, d, s, j] − (if s = dst[d] then 1) = 0
(6)
Furthermore, the maximum available capacity c
max
at the node
∀s ∈ S :
r∈R
d∈D
(s,j)∈L
x[r, d, n, j] · qnt[d] +
r∈R
d∈D
(i,s)∈L
x[r, d, i, s] · qnt[d] ≤ c
max
(7)
and the maximum capacity bw
max
at each link
∀(i, j) ∈ L :
r
∈R
d
∈D
x[r, d, i, j] · qnt[d] ≤ bw
max
[i, j]
(8)
Network Optimization for Safety-Critical Systems
131
must not be exceeded. As a full duplex link is assumed in this case, the limit
applies to each direction. Since the internal memory for forwarding rules in the
SDN switches is limited, the number of flow table entries needs to be constrained
likewise:
∀s ∈ S :
r
∈R,d∈D
( s,j)
∈L
x[ r, d, n, j] ≤ r
max
(9)
Additionally, (
10
) and (
11
) ensure that the maximum latency for each demand
is not exceeded
∀r ∈ R, d ∈ D :
( i,j)
∈L
t
q
[ d] + t
pp
+ t
t
s
∈S
t
pr
≤ d
Δt
(10)
and that no links are shared between resilient flows:
∀d ∈ D : ∀( i, j) ∈ L :
r
∈R
x[ r, d, i, j] +
r
∈R
x[ r, d, j, i] ≤ 1
(11)
Both requirements follow from the application to safety-critical traffic, where the
formulation of (
11
) assumes that a failure affects both flow directions. In that
context, (
9
) is specific to the utilization of SDN and would need to be adapted
accordingly for non-SDN networks.
4
Experimental Setup
To begin with, the networks and traffic parameters under study are described.
Two different types of network topologies were used: critical and standard net-
works. In this context, standard means that they are not commonly associated
with critical traffic demands. To this end, the PDH and DI-YUAN networks
(see Figs.
1
a and b) with the associated traffic demands and link costs were
investigated a as well as the AFDX [
16
] and NOBEL-EU (see Figs.
1
c and d)
networks as examples for critical networks. For all but the AFDX network, this
information has been obtained from the SND-LIB [
17
] library. In those figures,
the circles represent network switches where flows may enter or leave the net-
work, while the arrows represent bidirectional links between switches. Attached
to the switches are end-systems (not shown) which generate traffic demands, e.g.
a control computer communicating with an actuator.
Due to the additional constraints of our approach, the maximum capacity
was selected from each definition. Since maximum latency or resilience was not
Do'stlaringiz bilan baham: |
