We present a model of a Software De ned Network (SDN) where frequent changes in routing and tra c rates at routers are needed to respond to the security, quality of service (QoS), and energy savings requirements of applications such as the Internet of Things. Such frequent path and tra c changes introduce time-dependent network behaviours, and standard queueing models are not well adapted to analyse the transient regime, we propose a tractable di usion approximation for both the transient and steady-state behaviour. Our model can represent any network topology transmitting time-dependent ows with routing changes, and computes queue length and delay distributions at each network node and along complete paths between senders and receivers. Using realistic router parameters, we show that transients occupy a signi cant fraction of system time, so that the optimisation conducted with SDN controllers needs to include the e ect of time-dependent behaviours.
The Internet of Things (IoT) and its increasing volumes of tra c for new services such as video related to security, server virtualisation of the Cloud and Fog [38,8] and highly distributed data storage [22,9], create new challenges for the Internet [26,35]. Indeed, expanding IoT applications such as Health Monitoring [32], Smart Homes [3] and Smart Vehicles [18], create large volumes of intermittent tra c with stringent security, QoS and energy minimisation needs [6].
Thus network structures based on static switches are not well suited to deliver high performance, energy e ciency and reliability in such dynamically changing environments, and are not exible enough to maintain Quality of Service (QoS) for increasingly complex networks. On the other hand, SDN [34,39] with intelligent programmable controllers can be aware of the overall state of nodes and links, and dynamically manage the network and adapt to new conditions [25]. Indeed, SDN provides exible and scalable routing for intelligent networks [14] by separating the control and data planes for tra c engineering, link failure recovery, load balancing [40] and security issues [41]. Thus the concentration of network intelligence and management in SDN controllers enables innovative smart cognitive routing [17,21] to respond by changing network paths and tra c levels to meet the dynamic security, QoS and energy savings requirements of the IoT.
Earlier studies of SDN switches have used steady-state queueing models such as M=M=1, M=H2=1, M=G=1, M=Geo=1, GI=M=1=K, based on Markov chains, embedded Markov chains [29,2,36,28,16,31] or network calculus [4,5]. Thus they do not consider the frequent tra c changes due to controller decisions. To address this concern, we recently considered a single SDN forwarder and modelled it with a di usion approximation [13], and considered a network of forwarders [12] to determine its transient behaviour. These studies have shown that under certain conditions, the transient regime can become dominant so that SDN based optimisation should consider the e ect of transients.
In SDN, paths are selected by a controller, and the SDN data plane routers are then simple forwarding devices that follow the rules given by the controller. An analysis of the performance of SDN switches and their cooperation with the controller may be found in [33,27,40].
Therefore this paper, we extend these studies to address a SDN based network that supports IoT applications, and modi es its paths and tra c levels to respond to unpredictable changes in security and QoS, so that the network has time-dependent routing. To address this challenge we apply a di usion approximation [24,20,30] which is well suited to investigate transient queueing problems with general interarrival and service time distributions for realistic network data.
The next section details the method for a single network node, while the
mathematical model of time-dependent routing in the network is presented in
Section 3 where the system equations such as (
Single Node Transient Analysis The di usion approximation replaces the number of packets in a queueing system by the real-valued di usion process fX(t)g 2 [0; N ] where N is the maximum size of the queue. Following the approach in [19,23], at the extremities x = 0 and x = N of the di usion interval, two absorbing barriers are placed so that when fX(t)g reaches a barrier, it stays there for a random time and jumps from x = 0 to x = 1 with intensity and from x = N to x = N 1 with intensity . The resulting di usion equation is: dp0(t)
dt dpN (t) dt = = lim [
x!0 2 = lim [ x!N 2 +
N + 1) ; f (x; t; x0)]
p0(t) ;
+ f (x; t; x0)]
pN (t) ;
(
X(t) < x + dx j X(0) = x0]:
The incremental changes of fX(t)g, dX(t) = X(t + dt) X(t) are normally distributed with the mean dt and variance dt where , are coe cients of the di usion equation. The changes of the process fN (t)g during an interval tend to normal distribution with mean ( ) and variance ( A2 3 + B2 3) where 1= and 1= are the mean interarrival and service times, and A2, B2 are the variances of the interarrival and service times, respectively. The choice = and = A2 3 + 2 3 = CA2 B + CB2 ; where CA2, CB2 are squared coe cients of variation of interarrival and service times, assures that the changes of both processes fX(t)g and fN (t)g have normal distributions with the same parameters.
To determine the solution of (
Z N
0 (x; t; ) =
(x; t; ) ( )d :
The probability density function f (x; t; ) of the di usion process with jumps from the boundaries is composed of the function (x; t; ) referring to the diffusion process before it reaches any barrier and of a spectrum of functions t)2 t)2 o for t = 0 for t > 0 ;
(
Z t
0
(x; t ; 1), (x; t ; N 1) representing di usion processes with
absorbing barriers at x = 0 and x = N , started with densities g1( ) and gN 1( ) at
time < t at points x = 1 and x = N 1 due to jumps from the barriers:
f (x; t; ) = (x; t; )+
g1( ) (x; t
; 1)d +
gN 1( ) (x; t
; N
1)d ;
(
First, we compute densities 0(t), N (t) of probability that at time t the process enters to x = 0 or x = N are gN 1( ) N 1;0(t
)d ; gN 1( ) N 1;N (t )d ;
Z t 0 Z t
0 Z 0 0(t) = p0(0) (t) + [1 p0(0) pN (0)] ;0(t) + g1( ) 1;0(t )d N (t) = pN (0) (t) + [1 p0(0) pN (0)] ;N (t) + g1( ) 1;N (t )d +
Z t
0 +
Z t
0
Z
0
(
Finally, we may express g1(t) and gN (t) with the use of functions 0(t) and N (t): where 1;0(t), 1;N (t), N 1;0(t), N 1;N (t) are densities of the rst passage time between corresponding points, e.g.
1;0(t) = lim [ x!0 2 (x; t; 1)] : g1( ) = 0(t)l0( t)dt ; gN 1( ) =
N (t)lN (
t)dt ;
(
Technicaly, it is easier to compute this solution in Laplace domain where
convolutions of functions become products. For any function h(t) we denote
by h(s) its Laplace transform. The Laplace transform f (x; s; ) of the density
function f (x; t; ) is
f (x; s; ) = (x; s; ) + g1(s) (x; s; 1) + gN 1(s) (x; s; N
1) ;
(
1(x x0) exp exp[ (x x0) ]
A(s) + 1(x0<x) exp 2 sinh xA(s) x0A(s) 2 sinh
2 sinh x0A(s) xA(s)
x0A(s) 2 sinh xA(s) 1 X exp n=1 2nN
A(s)
H f (t) = ln 2 X Vi f 2 where
Vi = (
X k=b i+21 c
kH=2+1(2k)!
(H=2
k)!k!(k
1)!(i
k)!(2k
i)!
H is an even integer; we used H = 16, following Stehfest's recommendations.
Theoretically (
Note that the presented transient solution is valid for constant di usion
parameters. However, the values of ows, hence also model parameters, may vary
with time. Therefore in computations, we x model parameters during small
intervals (of the order of a single mean service time) and the solution at the
end of one interval determines the initial conditions (i.e. function in Eqs. (
The delay through the queue, including waiting and service time, is obtained as a rst passage time from an initial point taken with probability density f (x; t; ) to the absorbing barrier placed at x = 0, see [13].
It is known that lims!0 sf (s) = limt!1 f (t) if sf (s) is an analytic function for <(s) 0, therefore the above solution in form of Laplace transforms is convergent to steady-state solution for real domain. 3
Network of Nodes, Transient Analysis Consider a network of M stations type G/G/1/N with routing probabilities rij (t). We follow the approach of [24] developed for the steady-state network model, then adapted to transient analysis in [15]. Here we introduce additionally, for the needs of SDN, the time-depending routing.
The rst objective of the network model is to decompose the network: to determine the input ows at every station and then apply the single server model of the previous section to each station separately.
In the transient state, we should distinguish at any station i the input ow i in(t) and the output ow i out(t) i out(t) = [1 p0i(t)] i; which are di erent. p0i(t) denotes probability that the station i is idle at time t, i.e. the di usion process related to this station is inside the barrier at x = 0. The term 1 p0i(t) = %i presents probability that the station i is busy and customers are leaving it with the rate i.
The tra c equations balancing the ows of stations are
i in(t) =
j out(t)rji(t) ;
i = 1; : : : ; M;
(
M 0i(t) + X where the rst term 0i represents tra c ow coming from the outside of the network directly to station i.
As mentioned earlier, routing probabilities rji(t) are changing each interval
following decisions of the controler, remaining constant inside the interval,
and ow parameters may change every interval < ; we assume for simplicity
= n , in numerical examples below n = 10. This way all model parameters
are constant witin intervals when the solution (
Denote by fAj (x; t) and fBj (x; t) the density functions of interarrival and
service times distributions at station j. The pdf fDj (x; t) of the interdeparture
times from this node at time t may be expressed as
fDj (x; t) = %j (t)fBj (x; t) + [1 %j (t)]fAj (x; t) fBj (x; t) ;
j = 1; : : : ; M; (
rji(t))2rji + = 1 rji(t)fi(s; t) [1 rji(t)]fi(s; t) ; and we compute the squared coe cient of variation
Cj2i(t) = rji(t)[CD2j (t)
and then the parameters of the input ow at station i are given by (
X rji(t) i out(t)[(CD2i(t) 1)rji(t)+1] +
i in(t) j=1
C02i(t) 0i(t)
i in(t)
; (
Eqs. (
The pdf fRi(x; t) of the current response time (waiting time plus service) is determined using the rst passage time from the end of the queue to zero.
The rst passage time of the di usion process from x0 to x = 0 has the density function [10] x0;0(t) = p 2 x0 t3 e ( t+1)2
2 t ; x0;0(s) = e x0 + p 2+2 s : with the Laplace transform The starting point x0 is determined by the function fi(x; t; i) hence Z N
0 fRi(x; t) =
;0(x)fi( ; t; i)d :
If fRi(x; t) is the response time pdf at node i, then the response time pdf
fR(x; t) for the path 1; : : : ; n of n stations is
fR(x; t) = fR1(x; t) fR2(x; t) fR3(x; t)
fRn(x; t);
or
fR(x; s) =
n
Y fRi(x; s):
i=1
The loss probability ploss(t) for same entire path may be computed from
1
ploss(t) = (1
pN1(t))(1
pN2(t))(1
pN3(t)) : : : (1
pNn(t));
(
Application to a SDN and a Numerical Experiment Since the input and output hardware of a SDN forwarder is fast, the main component to be considered is the queue of packets waiting until the node identi es to which ow they belong and to what output port they are to be sent. Suppose that the identi cation requires a linear search in a ow table with K entries, and T is the constant time to check one entry.
Ler p be the probability that the router's ow table does not contain the ow rule for a given packet; this will be discovered after going through all K positions, i.e. after time KT . In this case, the service time is constant, with zero variance.
Otherwise, with probability (1 p), the time to nd the existing entry is uniformly distributed in [T; KT ] and having mean (K + 1)T =2 and variance (K2 1)T 2=12: The two cases de ne the rst two moments 1= and B2 of service time distribution in our G=G=1=N di usion model.
We consider a network composed of four switches, represented in Fig. 1. The network performance is investigated during 1 second. Host 1 is sending a ow of 01 packets to Host 2. The intensity of the ow is changing in the range 500 2500 packets/sec, see Fig. 2. If the ow is below 1000 packets per second, it is sent by the direct link S1 S4, and if it exceeds the maximum capacity of this link, the surplus is sent in equal share by paths S1 S2 S4 and S1 S3 S4.
We assume at each station the bu ers of N = 100 packets; in case of S1, S2, S3 the time to check one entry in the list of connections is T = 8 10 7 sec, and in S4 this time is twice shorter T = 4 10 7 sec. The number of entries K = 950, p = 0. It results in 1 = 2 = 3 = 2628:8 packets/sec and 4 = 5257:6 packets/sec. Squared coe cient of variation of service time CB2i is in all stations equal 0.33.
In the interval [t = 0:450 sec, t = 0:705 sec], an additional ow 02 of the intensity 1500 packets per second appears at station S2 and is also sent to Host 2 via S2 S4. We consider three values of the squared coe cient of variation of interarrival times in the rst ow: CA21 = C021 = 1:02; 4:08 and 8:16. The rst value is obtained from our analysis of CAIDA data [1], and the others were chosen to see the network behaviour if the ow is more irregular. For the second ow, C022 = 1:02.
The SDN controller alters the routing to balance the load of nodes every 100
msec, hence at t = 500 msec it reacts on the presence of the second ow and
changes the routing r12 and r13, see Fig. 3. In consequence, the load of stations
S2 and S3 is changed, Fig. 4. After the end of the ow 02 the initial routing
is reestablished. The change of the utilisation in uences the parameters of the
output ows: as it is expressed by Eq. (
The transient solution of di usion equations is computed in intervals of the
length 10 msec, i.e. we have 100 intervals with xed di usion parameters; at the
end of each the equations (
The model helps us to analyse the dynamics of every node. In Fig. 6 we see how the distribution of queue length (the queue is empty at the beginning, and it starts to be lled) at station S1 evolves with time. Even minimal values of the distributions are computed without numerical problems. As mentioned above, we used three di erent values of CA21(t), the squared coe cient of variation of interarrival times at station S1. In Fig. 7 the density function for S1 queue distribution is displayed for these values and makes evident their impact on the queue, note that the scale in Figs. 6, 7 is logarithmic.
The next gures display the impact of CA21 on loss probability due to the full bu er at station S1, Fig. 8, and on the mean queue at this station, Fig. 9, following the changes of the ow intensity.
The next curves compare the loss probability, Fig. 10 (note here minimal values computed by the model), and mean queues for all four stations, Fig. 11, in case of CA21 = 1:04. We may observe the changes in mean queues in S2 and S3 due to load balancing after the second ow becomes active. We see also, observing mean queues at S1 and S2, that transient periods may be longer than the time between the controller's decisions. The length of the transient time increases with a load of a station and variability of the input ow.
Figures 12 and 13 refer to station S2. We see here a weak impact of CA21 on the mean queue. It is evident: as this station is mainly supplied by the second ow. However, if we consider loss probabilities which have here very small values and are displayed in logarithmic scale, the impact of CA21 may be observed. It is better seen at station S3, Fig. 14, and in station S4, Fig. 15, because they receive much more of the rst ow. Note that for greater variabilities of the rst ow, the path S1 S3 S4 becomes saturated, Fig. 16.
Let us also consider a simple example of optimization. Suppose as previously that station S1 is forwarding a ow 01 packets to nodes S2 and S3. Station S2 is additionally receiving a ow of (0l2oc) packets directly from the outside of the network. The controller is changing routing every = 100 msec and needs do determine routing probabilities for the nearest , knowing current parameters of ows at the beginning of the interval, as well as the current queue distributions at S1, S2, S3, representing previous behaviour of the network. The goal is to minimise the mean backlog at S2 and S3 during The IoT provides large volumes of highly capillary tra c that includes data and video, which has stringent QoS and security constraints. These large volumes of tra c also create additional energy consumption in networks. Thus means are needed to distribute tra c dynamically so that security and QoS are assured, and energy consumpton is minimised.
Fortunately, the advent of SDN allows the implementation of smart adaptive routing [25] which allows network paths to change so that security incidents and tra c overloads can be accomodated by taking advantage of alternate paths. However this leads to an ineresting paradigm shift in network modeling which has been traditionally addressed via steady-state \long term" modelling techniques. However, when SDN intervenes dynamically to change paths and tra c levels, the network is seldom at steady-state so that optimisation must take transients into account.
To achieve this, this paper uses di usion approximations for the performance evaluation of a network of SDN data plane switches with time-dependent routing. We show that this method is computationally operational, and that it can provide quantitative results for models with realistic parameter values.
Our analysis captures the interactions among the main parameters of the network, and numerical examples display the dependence of the queue lengths and queueing delays and their changing dynamics, on the ow intensity and variance of interarrival times.
Our approach con rms the fact that transient periods play a signi cant role in the performance of SDN networks, and in future work we will use it to analyse much larger networks.
Fig. 4: i(t)= i for all stations Fig. 5: S1, S2, S3: squared coe cient of variation CD2i(t) for the output ow,
CA21 = 1:02
Fig. 9: S1: mean queue for di erent CA21 Fig. 13: Station S2: mean queue for di erent CA21 Acknowledgements during
as a function of routing probabilities r12, r13 = 1 r12 The work presented in this paper was partially supported by the SerIoT Research and Innovation Action, funded by the European Commission under the H2020IoT-2016-2017 (H2020-IoT-2017) Program through Grant Agreement 780139. 25. Gelenbe et al., E.: Self-aware networks that optimize security, qos and energy.
Proceedings of the IEEE, accepted for publication 108(