# Scalable Node-Centric Route Mutation for Defense of Large-Scale Software-Defined Networks

Authors: Yang Zhou; Wei Ni; Kangfeng Zheng; Ren Ping Liu; Yixian Yang
Journal: Security and Communication Networks
 (2017)

---

## Abstract

Exploiting software-defined networking techniques, randomly and instantly mutating routes can disguise strategically important infrastructure and protect the integrity of data networks. Route mutation has been to date formulated as NP-complete constraint satisfaction problem where feasible sets of routes need to be generated with exponential computational complexities, limiting algorithmic scalability to large-scale networks. In this paper, we propose a novel node-centric route mutation method which interprets route mutation as a signature matching problem. We formulate the route mutation problem as a three-dimensional earth mover’s distance (EMD) model and solve it by using a binary branch and bound method. Considering the scalability, we further propose that a heuristic method yields significantly lower computational complexities with marginal loss of robustness against eavesdropping. Simulation results show that our proposed methods can effectively disguise key infrastructure by reducing the difference of historically accumulative traffic among different switches. With significantly reduced complexities, our algorithms are of particular interest to safeguard large-scale networks.


---

## Body

## 1. Introduction

Instantly mutating route is a promising technique to provide the integrity of large data networks [1]. It can disguise strategically located important network infrastructures and delay or prevent potential reconnaissance attacks [2]. This is of particular interest to many practical networks delivering security-sensitive data, such as military networks [3] and banking systems [4]. On the other hand, software-defined network (SDN) has been increasingly deployed. Centralized control in SDN facilitates mutating routes to disguise the strategically important switches and protect the network.In general, route mutation is NP-complete constrained path selection in the presence of quality-of-service (QoS) consideration [5]. It has been formulated to be a constraint satisfaction problem and solved by using the satisfiability modulo theory (SMT) [6]. The constraints include the QoS of traffic flows and physical bandwidth of routers [6]. The final routes are randomly chosen from the results of SMT that satisfy constraints. However, the routes can hardly claim optimality in any sense, and the complexity of SMT is prohibitively high [7]. Although some heuristics have been developed to solve this problem within pseudo-polynomial-time [8–11], these algorithms concern network optimality rather than security.In this paper, we propose new node-centric route mutation methods which are able to effectively change routes of flows at substantially reduced complexities. The key idea is that we propose interpreting route mutation as a signature matching problem and developing a three-dimensional earth mover’s distance (EMD) model with network connectivity and QoS constraints to suppress the traffic difference among switches. Another important aspect of our algorithm is that we solve the new node-centric problem as a three-dimensional transportation problem and develop suboptimal algorithms with polynomial time-complexities. Simulation results show that our algorithms are able to suppress the traffic difference among strategically important switches and also achieve fast convergence with substantially reduced complexities.The rest of paper is organized as follows. Section2 presents related work. Section 3 describes the system and network model. In Section 4, we discuss the details of designed algorithm. We present the computational efficient heuristics that can apply to large-scale networks in Section 5. Section 6 evaluates the experiment results and performance of our algorithm. In Section 7, we conclude the paper.


## 2. Related Work

In [12], randomly mutating route or host address was proposed to protect key network infrastructures from exposure to attackers and prevent potential attacks. Only a few structured algorithms have been designed for route or host address mutation, all of which formulated NP-complete constrained satisfaction problems under the constraints of the mutation rate [13], the address range [14], and the range distribution for host address mutation [6, 15]. These algorithms were solved by using SMT [6, 13–15]. However, constraint satisfaction problems are NP-complete with exponential complexities [16]. As far as the routing problem is concerned, there are N=∑j=1n-1‍n-2!/n-j-1! possible routes with lengths shorter than j hops in an n-node complete network [17]. Choosing k routes out of N yields a complexity of N!/N-k!k!, limiting the scalability of the designs to large-scale networks.More efforts have been spent demonstrating the concept of route mutations. Route mutation was first implemented under IPv6, referred to as “Moving Target IPv6 Defense (MT6D),” by continually rotating the IPv6 addresses between the senders and recipients [18]. A new transport layer protocol was designed to enable multiple addresses per network socket and support the rotations of IPv6 addresses [19]. Route mutation was later applied to mobile ad hoc networks [20], by repurposing a classic attack mechanism, the Sybil attack, for effective defense. Most recently, route mutation was demonstrated using Cisco’s SDN platform, One Platform Kit [21]. With the flexibility of SDN, a deception system that mutates the topologies virtually was proposed to defend against reconnaissances [22]. A double hopping communication approach was designed to combine the IP address mutation and the route mutation methods in SDN [23], in which routes were selected from all paths within even lengths between sources and destinations. Game theory was adopted for route mutation in [24]. Route mutation was proposed to apply to traditional networks where links were selected using stochastic game routing policies of next-hop probability distribution. In [25], a virtual network embedding framework was proposed to satisfy the capacity, delay, and cycle-free constraints when mutating links by game theoretic routing policies. In [1], a randomized multipath routing method was developed to circumvent black holes and minimize the overall energy consumption in wireless sensor networks.


## 3. System Model

Figure1 illustrates the software-defined network under consideration, where there are N number of switches connected in a network topology and forwarding traffic. We assume that all the switches are connected to a SDN controller in a star topology. The SDN controller is responsible for route discovery and mutation. The switches forward traffic along the routes specified by the SDN controller. The bandwidth of each switch, that is, switch i, is Bi.Figure 1
An illustration of SDN topology.Each of the switches is also connected to end-hosts which generate routing requests through the switch to the SDN controller. An end-host can request sending traffic flows to any other end-host. Each traffic flow is assumed to be randomly generated and last for a certain period of time. Without loss of generality, we assume that there are at mostK routing requests at any instant. The data rate of the kth flow is denoted by fkk=1,…,K.Consider a practical network with hundreds of switches and nontrivial topologies (as opposed to fully connected complete graphs). Some of the switches have more connections than the others. These switches are strategically located and handle more traffic than other switches. In the example of Figure1, switches D and H are such strategically located nodes. The exposure of these switches to adversaries poses critical threats to the integrity of the network.The topology of the network can be described by an undirected graphGN,E, where N collects the vertexes (i.e., switches) and E collects the edges (i.e., the links connecting the switches). The size of N is |N|=N, where · stands for cardinality. Also define A to be the adjacent matrix of G. A(i,j)=1(i≠j), if vertices i and j are connected; or Ai,j=0, otherwise.Reconnaissance attacks [26] are considered, where an adversary keeps monitoring (or eavesdropping) the switches until strategically located switches are identified and attacks (such as DDoS) are initiated. The difference of historically accumulative traffic among switches is typically used by the adversary to identify strategically located switches, for example, D and H in Figure 1. The exposure of the strategically located switches would facilitate the potential attacks. Consider the worst-case scenario that the adversary is able to access each individual switch, install invasive software, accumulate the traffic volume handled at the switch, and collect the traffic volumes of all the switches. In practice, this can be implemented by remotely installing monitoring software, such as Cacti [27], to get the switches to collect and report the SNMP information to the adversary.


## 4. The Proposed Route Mutation for Large-Scale Networks

In this section, we propose mutating routes on a node basis to leverage between the robustness against reconnaissance attacks and the computational complexity. Particularly, routing requests from end-hosts are responded to independently from one another using classical routing techniques, such as OSPF [28]. The exponentially increasing complexity of joint routing, such as the one proposed in [6], can be avoided.Given the routes, we propose that the SDN controller identifies historically heavily loaded nodes with high exposure risks and detours their traffic flows via other historically lightly loaded nodes. A node is identified to be historically heavily or lightly loaded, based on the accumulative traffic of the node. By this means, the strategically located nodes can be disguised and protected, delaying or even preventing potential attacks.The detours bypassing a historically heavily loaded node can be multihop. Figure2 gives the examples of two-, three-, and four-hop detours that are considered, where node B is a strategically located node. The possible detours for a traffic flow currently passing node B must connect the nodes one hop away from node B along the traffic flow, that is, nodes A and C. Such detours can be readily obtained using depth-first search (i.e., search for the closed loops passing node B) [29]. The lengths of the detours are 2, 3, and 4 (in numbers of hops) in Figures 2(a), 2(b), and 2(c), respectively.Figure 2
Illustrations of multihop detours around a strategically located node, say nodeB in this example, where the lengths of the detours are 2, 3, and 4, respectively.
(a)
(b)
(c)We also propose interpreting the route mutation as a signature matching problem. The accumulative traffic loads of the nodes are visualized as a signature, and routes are mutated to conform the signature to the one with even loads across all the nodes. Widely used to measure the difference of two images [30], EMD [31] is extended to measure the difference between the two signatures. The difference, or more specifically, the EMD, is reduced recursively by detouring flows around historically heavily loaded nodes, as described earlier.The proposed route mutation is able to substantially reduce the computationally complexity. Assume that the detours are limited to two hops. The worst-case complexity isO(n22n), consisting of detour discovery for every switch and redirecting at most K traffic flows from every switch, where n represents for the number of variables. In this case, n⩽KNN-3. In contrast, the state-of-the-art joint mutation of all routing paths, using SMT [6], would result in prohibitive exponential complexity and limited scalability to networks with hundreds of nodes.


### 4.1. Nodewise Route Mutation for Delay-Tolerant Traffic

First consider delay-tolerant traffic. The total number of current traffic flows isK, consisting of existing ongoing flows collected in the set Ke and new flows collected in the set Kn. K=Ke∪Kn. K=K. Denote vi′, i∈N, and v¯′ (in bytes) to be the accumulative traffic of each individual node i and their average, respectively, before a round of route mutation. v¯′=1/N∑i=1N‍vi′. vi and v¯ are the accumulative traffic of node i, i∈N, and the average, respectively, after the round of route mutation. v¯=1/N∑i=1N‍vi.The proposed route mutation redirects theK traffic flows, attempting to conform the pictorial signature of the accumulative traffic of the nodes to a uniform signature with even traffic of v¯ at every node. To do this, we construct two signatures, that is, two one-dimensional distributions: vi-vi′,∀i∈N and v¯-vj′,∀j∈N. The first signature vi-vi′,∀i∈N provides the traffic volumes that can detour. The second signature v¯-vj′,∀j∈N denotes the demand of each node to achieve traffic uniformity among the nodes, as illustrated in Figure 3.Figure 3
An illustration of the proposed application of signature matching to route mutation, wherevj and vj′ are the historically accumulative traffic volumes of node i at the current and the previous instants, respectively, and v¯ and v¯′ are the averages of the historically accumulative traffic volumes at the current and the previous instants, respectively. vi′ and v¯′ are the results of the route mutation at the previous instant. vi and v¯ are the values before the current route mutation is executed.
(a)
Historically accumulative traffic volumes of nodes when Algorithm1 starts
(b)
Historically accumulative traffic volumes of nodes before Algorithm1 terminates
(c)
Historically accumulative traffic volumes of nodes after Algorithm1 terminatesAlgorithm 1:Route mutation for delay-tolerant traffic.
Input:  GN,E; A; R; the accumulative traffic of each node
v
i
′; the current route of each flow k∈K; fk; and the
initial θik (i∈N;k∈K).
Output:  θik,∀i∈N,k∈K
(1) Let vi=vi′+∑k∈K‍θikfk.
(2) repeat
(3) for  i=1,…,N  do
(4) for  k=1,…,K  do
(5) if  θik=1  then
(6) construct Lri,k,r=1,…,R, using depth-first search, and calculate δjj.
(7) end if
(8) end for
(9) end for
(10) calculate v-=1/N∑i=1N‍vi, and cij using (3);
(11) substitute vi, v-, vi′ (i∈N), v-′, cij and θik into the EMD problem (4a), (4b), (4c), (4d), (4e), and (4f),
and solve the problem optimally using the binary branch and bound/cut method;
(12) update
θ
i
k
⟵
∑
j
∈
N
∑
r
=
1
R
∑
j
∈
L
r
(
j
,
k
)
θ
j
k
δ
i
j
x
j
i
k;
v
i
⟵
v
i
′
+
∑
k
∈
K
θ
i
k
f
k;
i
∈
N
;
k
∈
K
(13) untilθik stops changing; or in other words, Δv-≤ϵ.The EMD can be defined to quantify the difference between the two signatures, as given by(1a)ϵ∗=arg⁡minϵτ⁡τ,(1b)ϵτ=∑i∈N∑k=1K∑r=1R∑j∈Lri,kcijθikfkxijkminR∑i∈Nvi-vi′,∑j∈Nv--vj′+-τ,where ·+=max⁡·,0; R is the maximum allowed length of a detour (in numbers of hops); xijk=1 if the current flow k is to be offloaded from node i to detour j, or xijk=0, otherwise; θik=1, if flow k currently goes through node i, or θik=0, otherwise; δjj is given by (2)δjj=1,ifj∈j;0,otherwise.Lri,k is the set of detours with length of r≤R, and each of the detours connects to the two nodes one hop away from node i along the current route of flow k. For any j∈Lr(i,k), j∈Nr×1; that is, j=r. Let jll=1,…,r denote the lth element of j. We have Aj1,j2=⋯=Ajr-1,jr=1.Here,cij is the cost of offloading traffic flows from node i to detour j∈Lr(i,k). Keep in mind that our goal is to minimize the difference of accumulative traffic among the nodes. Meanwhile, the EMD is inherently defined to minimize the difference. For this reason, cij is defined as the normalized total difference of node i and detour j from v¯, as specified by(3)cij=1r+1vi-v¯2+∑j∈jvj-v¯2forj∈Nr×1.Our EMD has a different form to the conventional definition for image processing applications [31]. An auxiliary variable τ is defined to indicate the gap between the total traffic load that is expected to detour and the total traffic that can detour, whereas there is no such gap for image applications. This is due to the fact that route mutation (or, in other words, route reselection) is discrete and these two loads do not equate in most cases. (1a) and (1b) provide the average cost to minimize the difference between the total traffic load expected to be detoured and the total traffic load that can be detoured.Predicted before a round of mutation,v¯ is unnecessarily equal to the one actually achieved after the mutation. This is due to the dependence of traffic between the nodes imposed by traffic flows. Particularly, a detour needs to be taken across multiple nodes and increases the traffic of the nodes evenly. Therefore, the average traffic load is expected to increase as a result of mutation. However, the difference of v¯ before and after a round of mutation can be iteratively reduced by increasing the rounds and diminishes as the routes stabilize. Once stabilized, the routes are implemented into the network. The convergence of the iterations can be guaranteed, since v¯ does not decrease during the iterations while it is also obviously bounded. Figure 3 gives a detailed illustration on our signature matching method.Givenvj′, v¯′, vj, and v¯, we can formulate a binary linear programming problem to minimize the EMD of the two signatures, as given by(4a)minxijk,τ,∀i,k∈Sj∈Lri,k∑i∈N∑k=1K∑r=1R∑j∈Lri,kcijθikfkxijk,(4b)s.t.∑r=1R∑j∈Lri,kθikxijk≤1,foranyk;(4c)∑k=1K∑r=1R∑j∈Lri,kθikfkxijk≤vi-vi′,foranyi∈N;(4d)∑i∈N∑k=1K∑r=1R∑j∈Lri,kδjjθikfkxijk≤v--vj′+,foranyj∈N;(4e)minR∑i∈Nvi-vi′,∑j∈Nv--vj′+-∑i∈N∑j∈N∑k=1K∑r=1R∑j∈Lri,kδjjθikfkxijk≤τ;(4f)xijk∈0,1,where S is the set of nodes that can be detoured. S needs to be preselected so that at most one of two consecutive nodes along a traffic flow, for example, nodes B and C in Figure 2, detours. This is to prevent Lri,k from changing during solving (4a), (4b), (4c), (4d), (4e), and (4f). We can label the nodes along a traffic flow before running (4a), (4b), (4c), (4d), (4e), and (4f). S can be first set to collect the nodes with even labels and input to (4a), (4b), (4c), (4d), (4e), and (4f). Then S is reset to collect the remaining nodes with odd labels to run (4a), (4b), (4c), (4d), (4e), and (4f) again.Here, constraint (4b) restricts a flow that can only be offloaded from a node to one detour; (4c) and (4d) restrict the amounts of traffic that can be supplied and demanded by the first and the second signatures, respectively; (4e) specifies the total maximum traffic amount that can detour; and (4f) specifies the variables to be binary.Givenτ, (4a), (4b), (4c), (4d), (4e), and (4f) are integer linear program and can be optimally solved using a branch and bound/cut algorithm [32]. Specifically, we first relax (4f) and evaluate the upper and lower bounds of (4a) by increasingly setting the variables to “0” or “1” and using the Simplex method [33] to optimize the remaining variables. At any instant, the settings whose lower bounds are higher than the upper bound of another setting are discarded. The final remaining integer results are the solution for (4a), (4b), (4c), (4d), (4e), and (4f).A bisection method can be taken to recursively search for the minimum feasible value ofτ. When τ is too small, (4a), (4b), (4c), (4d), (4e), and (4f) can become infeasible. When τ is large, (4e) becomes inactive and (4a), (4b), (4c), (4d), (4e), and (4f) becomes always feasible. To this end, (4a), (4b), (4c), (4d), (4e), and (4f) is an on-off function of τ preserving monotonicity and can be readily solved bisectionally.Algorithm1 summarizes the proposed route mutation, where ϵ≪1 is a predetermined positive threshold for the termination of the algorithm. This algorithm resides in the SDN controller and runs periodically or on-demand. As described, the kernel of the algorithm is the EMD problem (4a), (4b), (4c), (4d), (4e), and (4f) solved using the binary branch and bound/cut method in Step (11). The optimal solution for (4a), (4b), (4c), (4d), (4e), and (4f) is used to update θik, or, in other words, to find the detours of the routes, as depicted in Step (12). By repeating these steps, the existing routes gradually move away and increase lengths, until the uniformity of all the nodes as regards accumulative traffic cannot be further improved; see the loop from Steps (2) to (13).The majority of the complexity in Algorithm1 lies in Step (11), that is, binary branch and bound/cut. Given a network GN,E, we can precompute all possible loops using depth-first search. Consider the worst-case scenario where the network is a complete graph. Let L denote the maximum number of detours that a node can take, and L=N-3+∑r=2R‍(N-3)!/2N-3-r!, where r is the length of detours in node numbers. As a result, the complexity of Steps (3) to (9) is OKNL. In the best-case and worst-case of branch and bound/cut, the members of branches are ∑k=1nk and ∑k=1nk2k, respectively, where n=KNL. As per each branch, the complexity is Ominm2,n2, where m is the number of constraints [34, 35]. m⩾n, as (4f) limits each variable to be smaller than 1. Thus, the complexity is On2. As a result, the lower bound complexity of Algorithm 1 is O(n2)O(∑k=1n‍k)=OK4N4L4, and the upper bound is OK2N2L2∑k=1n‍k2k=OK2N2L22KNL.


### 4.2. Route Mutation for Delay-Bounded Traffic

Algorithm1 can be extended to the case with QoS constraints on traffic flows. For illustration convenience, we assume that the QoS requirement of a traffic flow, say flow, is characterized by the maximum allowed route length of the flow, denoted by Lk (in numbers of hops). To this end, the following constraint is added to (4a), (4b), (4c), (4d), (4e), and (4f):(5)∑i∈N∑r=1R∑j∈Lri,krxijk≤Δlk,foranyk=1,…,K,where Δlk=Lk-lk.  lk is the route length of traffic flow k∈Ke or is the length of the route discovered using OPSF for a new flow k∈Kn. Equation (5) limits the total length of the detours that each flow k can take.The finite bandwidth of switches can also be considered in the proposed algorithm. We can incorporate a new constraint of the bandwidth of each link into a node-centric optimization problem, as shown as follows:(6a)Bi=minBi,u,foranyu∈N,Ai,u=1;(6b)∑k=1Kθikfk-∑j∈Lri,k∑k=1Kθikfkxijk+∑j∈Lri,k∑j=1N∑k=1Kδijθjkfkxjjk≤Bi,foranyi∈N,where Bi,u denotes the maximum bandwidth of link i,u, and u is connected to node i in one hop; that is, Ai,u=1. For any node i in the network, Bi denotes the link bandwidth, which is computed as the minimum one among all bandwidths of the links connecting node i. ∑k=1Kθikfk accounts for the traffic load of node i before mutation; after we mutate the flows out of node i, that is, ∑j∈Lr(i,k)∑k=1Kθikfkxijk, and move flows to it, that is, ∑j∈Lr(i,k)∑j=1N∑k=1Kδijθjkfkxjjk, its traffic load is within the range of bi.In practice, the maximum number of flow entries on an SDN switch is limited by the physical resources of the switch, such as CAM and SRAM. We can add constraint (7) into Algorithm 1 to restrain the maximum number of flow rules that the switches can install. Without loss of generality, we denote the average size of a flow rule as a. The number of flow rules at each switch depends on the total number of flows passing through it, as given by(7)∑k=1Kθik-∑j∈Lri,k∑k=1Kθikxijk+∑j∈Lri,k∑j=1N∑k=1Kδijθjkxjjk≤tia,foranyi∈N,where, for any switch i in the network, the size of its flow table is bounded by ti. Thus, the maximum number of flow entries that a switch can install is ti/a. The left-hand side of inequality (7) shows the number of flow rules of switch i after mutation, which is bounded by ti/a.GivenΔlk and the constraints (5), (6a), (6b), and (7), (4a), (4b), (4c), (4d), (4e), and (4f) can be optimally solved using binary branch and bound/cut in the same way, as described in Algorithm 1. After that, both v¯ and lk need to be updated until lk cannot be further increased. Algorithm 2 summarizes the proposed route mutation approach in the presence of QoS constraints. The key difference from Algorithm 1 is Step (4), implementing (5), (6a), (6b), and (7). The only other changes are in Steps (1) and (5), where Δlk is initialized and updated, respectively.Algorithm 2:Route mutation for delay-bounded traffic.
Input:  G(N,E); A; R; the accumulative traffic of each node
v
i
′; the current route of each flow k∈K; fk; the initial
θ
i
k; Lk; and the initial lk(i∈N;k∈K).
Output:  θik,∀i∈N,k∈K
(1) Let vi=vi′+∑k∈K‍θikfk and Δlk=Lk-lk.
(2) repeat
(3) Run Steps (3) to (10) of Algorithm 1.
(4) substitute vi, v-, vi′(i∈N), v-′, cij, θik and Δlk into the EMD problem (4a), (4b), (4c), (4d), (4e), and (4f)
incorporating (5), and solve the problem optimally using the binary branch and bound/cut method;
(5) update
θ
i
k
⟵
∑
j
∈
N
∑
r
=
1
R
∑
j
∈
L
r
(
j
,
k
)
θ
j
k
δ
i
j
x
j
i
k;
v
i
⟵
v
i
′
+
∑
k
∈
K
θ
i
k
f
k;
Δ
l
k
⟵
Δ
l
k
-
∑
i
∈
N
∑
r
=
1
R
∑
j
∈
L
r
(
i
,
k
)
r
x
i
j
k;
(
i
∈
N
;
k
∈
K
)
(6) until  θik stops changing; or in other words, |Δv-|≤ϵ.


## 4.1. Nodewise Route Mutation for Delay-Tolerant Traffic

First consider delay-tolerant traffic. The total number of current traffic flows isK, consisting of existing ongoing flows collected in the set Ke and new flows collected in the set Kn. K=Ke∪Kn. K=K. Denote vi′, i∈N, and v¯′ (in bytes) to be the accumulative traffic of each individual node i and their average, respectively, before a round of route mutation. v¯′=1/N∑i=1N‍vi′. vi and v¯ are the accumulative traffic of node i, i∈N, and the average, respectively, after the round of route mutation. v¯=1/N∑i=1N‍vi.The proposed route mutation redirects theK traffic flows, attempting to conform the pictorial signature of the accumulative traffic of the nodes to a uniform signature with even traffic of v¯ at every node. To do this, we construct two signatures, that is, two one-dimensional distributions: vi-vi′,∀i∈N and v¯-vj′,∀j∈N. The first signature vi-vi′,∀i∈N provides the traffic volumes that can detour. The second signature v¯-vj′,∀j∈N denotes the demand of each node to achieve traffic uniformity among the nodes, as illustrated in Figure 3.Figure 3
An illustration of the proposed application of signature matching to route mutation, wherevj and vj′ are the historically accumulative traffic volumes of node i at the current and the previous instants, respectively, and v¯ and v¯′ are the averages of the historically accumulative traffic volumes at the current and the previous instants, respectively. vi′ and v¯′ are the results of the route mutation at the previous instant. vi and v¯ are the values before the current route mutation is executed.
(a)
Historically accumulative traffic volumes of nodes when Algorithm1 starts
(b)
Historically accumulative traffic volumes of nodes before Algorithm1 terminates
(c)
Historically accumulative traffic volumes of nodes after Algorithm1 terminatesAlgorithm 1:Route mutation for delay-tolerant traffic.
Input:  GN,E; A; R; the accumulative traffic of each node
v
i
′; the current route of each flow k∈K; fk; and the
initial θik (i∈N;k∈K).
Output:  θik,∀i∈N,k∈K
(1) Let vi=vi′+∑k∈K‍θikfk.
(2) repeat
(3) for  i=1,…,N  do
(4) for  k=1,…,K  do
(5) if  θik=1  then
(6) construct Lri,k,r=1,…,R, using depth-first search, and calculate δjj.
(7) end if
(8) end for
(9) end for
(10) calculate v-=1/N∑i=1N‍vi, and cij using (3);
(11) substitute vi, v-, vi′ (i∈N), v-′, cij and θik into the EMD problem (4a), (4b), (4c), (4d), (4e), and (4f),
and solve the problem optimally using the binary branch and bound/cut method;
(12) update
θ
i
k
⟵
∑
j
∈
N
∑
r
=
1
R
∑
j
∈
L
r
(
j
,
k
)
θ
j
k
δ
i
j
x
j
i
k;
v
i
⟵
v
i
′
+
∑
k
∈
K
θ
i
k
f
k;
i
∈
N
;
k
∈
K
(13) untilθik stops changing; or in other words, Δv-≤ϵ.The EMD can be defined to quantify the difference between the two signatures, as given by(1a)ϵ∗=arg⁡minϵτ⁡τ,(1b)ϵτ=∑i∈N∑k=1K∑r=1R∑j∈Lri,kcijθikfkxijkminR∑i∈Nvi-vi′,∑j∈Nv--vj′+-τ,where ·+=max⁡·,0; R is the maximum allowed length of a detour (in numbers of hops); xijk=1 if the current flow k is to be offloaded from node i to detour j, or xijk=0, otherwise; θik=1, if flow k currently goes through node i, or θik=0, otherwise; δjj is given by (2)δjj=1,ifj∈j;0,otherwise.Lri,k is the set of detours with length of r≤R, and each of the detours connects to the two nodes one hop away from node i along the current route of flow k. For any j∈Lr(i,k), j∈Nr×1; that is, j=r. Let jll=1,…,r denote the lth element of j. We have Aj1,j2=⋯=Ajr-1,jr=1.Here,cij is the cost of offloading traffic flows from node i to detour j∈Lr(i,k). Keep in mind that our goal is to minimize the difference of accumulative traffic among the nodes. Meanwhile, the EMD is inherently defined to minimize the difference. For this reason, cij is defined as the normalized total difference of node i and detour j from v¯, as specified by(3)cij=1r+1vi-v¯2+∑j∈jvj-v¯2forj∈Nr×1.Our EMD has a different form to the conventional definition for image processing applications [31]. An auxiliary variable τ is defined to indicate the gap between the total traffic load that is expected to detour and the total traffic that can detour, whereas there is no such gap for image applications. This is due to the fact that route mutation (or, in other words, route reselection) is discrete and these two loads do not equate in most cases. (1a) and (1b) provide the average cost to minimize the difference between the total traffic load expected to be detoured and the total traffic load that can be detoured.Predicted before a round of mutation,v¯ is unnecessarily equal to the one actually achieved after the mutation. This is due to the dependence of traffic between the nodes imposed by traffic flows. Particularly, a detour needs to be taken across multiple nodes and increases the traffic of the nodes evenly. Therefore, the average traffic load is expected to increase as a result of mutation. However, the difference of v¯ before and after a round of mutation can be iteratively reduced by increasing the rounds and diminishes as the routes stabilize. Once stabilized, the routes are implemented into the network. The convergence of the iterations can be guaranteed, since v¯ does not decrease during the iterations while it is also obviously bounded. Figure 3 gives a detailed illustration on our signature matching method.Givenvj′, v¯′, vj, and v¯, we can formulate a binary linear programming problem to minimize the EMD of the two signatures, as given by(4a)minxijk,τ,∀i,k∈Sj∈Lri,k∑i∈N∑k=1K∑r=1R∑j∈Lri,kcijθikfkxijk,(4b)s.t.∑r=1R∑j∈Lri,kθikxijk≤1,foranyk;(4c)∑k=1K∑r=1R∑j∈Lri,kθikfkxijk≤vi-vi′,foranyi∈N;(4d)∑i∈N∑k=1K∑r=1R∑j∈Lri,kδjjθikfkxijk≤v--vj′+,foranyj∈N;(4e)minR∑i∈Nvi-vi′,∑j∈Nv--vj′+-∑i∈N∑j∈N∑k=1K∑r=1R∑j∈Lri,kδjjθikfkxijk≤τ;(4f)xijk∈0,1,where S is the set of nodes that can be detoured. S needs to be preselected so that at most one of two consecutive nodes along a traffic flow, for example, nodes B and C in Figure 2, detours. This is to prevent Lri,k from changing during solving (4a), (4b), (4c), (4d), (4e), and (4f). We can label the nodes along a traffic flow before running (4a), (4b), (4c), (4d), (4e), and (4f). S can be first set to collect the nodes with even labels and input to (4a), (4b), (4c), (4d), (4e), and (4f). Then S is reset to collect the remaining nodes with odd labels to run (4a), (4b), (4c), (4d), (4e), and (4f) again.Here, constraint (4b) restricts a flow that can only be offloaded from a node to one detour; (4c) and (4d) restrict the amounts of traffic that can be supplied and demanded by the first and the second signatures, respectively; (4e) specifies the total maximum traffic amount that can detour; and (4f) specifies the variables to be binary.Givenτ, (4a), (4b), (4c), (4d), (4e), and (4f) are integer linear program and can be optimally solved using a branch and bound/cut algorithm [32]. Specifically, we first relax (4f) and evaluate the upper and lower bounds of (4a) by increasingly setting the variables to “0” or “1” and using the Simplex method [33] to optimize the remaining variables. At any instant, the settings whose lower bounds are higher than the upper bound of another setting are discarded. The final remaining integer results are the solution for (4a), (4b), (4c), (4d), (4e), and (4f).A bisection method can be taken to recursively search for the minimum feasible value ofτ. When τ is too small, (4a), (4b), (4c), (4d), (4e), and (4f) can become infeasible. When τ is large, (4e) becomes inactive and (4a), (4b), (4c), (4d), (4e), and (4f) becomes always feasible. To this end, (4a), (4b), (4c), (4d), (4e), and (4f) is an on-off function of τ preserving monotonicity and can be readily solved bisectionally.Algorithm1 summarizes the proposed route mutation, where ϵ≪1 is a predetermined positive threshold for the termination of the algorithm. This algorithm resides in the SDN controller and runs periodically or on-demand. As described, the kernel of the algorithm is the EMD problem (4a), (4b), (4c), (4d), (4e), and (4f) solved using the binary branch and bound/cut method in Step (11). The optimal solution for (4a), (4b), (4c), (4d), (4e), and (4f) is used to update θik, or, in other words, to find the detours of the routes, as depicted in Step (12). By repeating these steps, the existing routes gradually move away and increase lengths, until the uniformity of all the nodes as regards accumulative traffic cannot be further improved; see the loop from Steps (2) to (13).The majority of the complexity in Algorithm1 lies in Step (11), that is, binary branch and bound/cut. Given a network GN,E, we can precompute all possible loops using depth-first search. Consider the worst-case scenario where the network is a complete graph. Let L denote the maximum number of detours that a node can take, and L=N-3+∑r=2R‍(N-3)!/2N-3-r!, where r is the length of detours in node numbers. As a result, the complexity of Steps (3) to (9) is OKNL. In the best-case and worst-case of branch and bound/cut, the members of branches are ∑k=1nk and ∑k=1nk2k, respectively, where n=KNL. As per each branch, the complexity is Ominm2,n2, where m is the number of constraints [34, 35]. m⩾n, as (4f) limits each variable to be smaller than 1. Thus, the complexity is On2. As a result, the lower bound complexity of Algorithm 1 is O(n2)O(∑k=1n‍k)=OK4N4L4, and the upper bound is OK2N2L2∑k=1n‍k2k=OK2N2L22KNL.


## 4.2. Route Mutation for Delay-Bounded Traffic

Algorithm1 can be extended to the case with QoS constraints on traffic flows. For illustration convenience, we assume that the QoS requirement of a traffic flow, say flow, is characterized by the maximum allowed route length of the flow, denoted by Lk (in numbers of hops). To this end, the following constraint is added to (4a), (4b), (4c), (4d), (4e), and (4f):(5)∑i∈N∑r=1R∑j∈Lri,krxijk≤Δlk,foranyk=1,…,K,where Δlk=Lk-lk.  lk is the route length of traffic flow k∈Ke or is the length of the route discovered using OPSF for a new flow k∈Kn. Equation (5) limits the total length of the detours that each flow k can take.The finite bandwidth of switches can also be considered in the proposed algorithm. We can incorporate a new constraint of the bandwidth of each link into a node-centric optimization problem, as shown as follows:(6a)Bi=minBi,u,foranyu∈N,Ai,u=1;(6b)∑k=1Kθikfk-∑j∈Lri,k∑k=1Kθikfkxijk+∑j∈Lri,k∑j=1N∑k=1Kδijθjkfkxjjk≤Bi,foranyi∈N,where Bi,u denotes the maximum bandwidth of link i,u, and u is connected to node i in one hop; that is, Ai,u=1. For any node i in the network, Bi denotes the link bandwidth, which is computed as the minimum one among all bandwidths of the links connecting node i. ∑k=1Kθikfk accounts for the traffic load of node i before mutation; after we mutate the flows out of node i, that is, ∑j∈Lr(i,k)∑k=1Kθikfkxijk, and move flows to it, that is, ∑j∈Lr(i,k)∑j=1N∑k=1Kδijθjkfkxjjk, its traffic load is within the range of bi.In practice, the maximum number of flow entries on an SDN switch is limited by the physical resources of the switch, such as CAM and SRAM. We can add constraint (7) into Algorithm 1 to restrain the maximum number of flow rules that the switches can install. Without loss of generality, we denote the average size of a flow rule as a. The number of flow rules at each switch depends on the total number of flows passing through it, as given by(7)∑k=1Kθik-∑j∈Lri,k∑k=1Kθikxijk+∑j∈Lri,k∑j=1N∑k=1Kδijθjkxjjk≤tia,foranyi∈N,where, for any switch i in the network, the size of its flow table is bounded by ti. Thus, the maximum number of flow entries that a switch can install is ti/a. The left-hand side of inequality (7) shows the number of flow rules of switch i after mutation, which is bounded by ti/a.GivenΔlk and the constraints (5), (6a), (6b), and (7), (4a), (4b), (4c), (4d), (4e), and (4f) can be optimally solved using binary branch and bound/cut in the same way, as described in Algorithm 1. After that, both v¯ and lk need to be updated until lk cannot be further increased. Algorithm 2 summarizes the proposed route mutation approach in the presence of QoS constraints. The key difference from Algorithm 1 is Step (4), implementing (5), (6a), (6b), and (7). The only other changes are in Steps (1) and (5), where Δlk is initialized and updated, respectively.Algorithm 2:Route mutation for delay-bounded traffic.
Input:  G(N,E); A; R; the accumulative traffic of each node
v
i
′; the current route of each flow k∈K; fk; the initial
θ
i
k; Lk; and the initial lk(i∈N;k∈K).
Output:  θik,∀i∈N,k∈K
(1) Let vi=vi′+∑k∈K‍θikfk and Δlk=Lk-lk.
(2) repeat
(3) Run Steps (3) to (10) of Algorithm 1.
(4) substitute vi, v-, vi′(i∈N), v-′, cij, θik and Δlk into the EMD problem (4a), (4b), (4c), (4d), (4e), and (4f)
incorporating (5), and solve the problem optimally using the binary branch and bound/cut method;
(5) update
θ
i
k
⟵
∑
j
∈
N
∑
r
=
1
R
∑
j
∈
L
r
(
j
,
k
)
θ
j
k
δ
i
j
x
j
i
k;
v
i
⟵
v
i
′
+
∑
k
∈
K
θ
i
k
f
k;
Δ
l
k
⟵
Δ
l
k
-
∑
i
∈
N
∑
r
=
1
R
∑
j
∈
L
r
(
i
,
k
)
r
x
i
j
k;
(
i
∈
N
;
k
∈
K
)
(6) until  θik stops changing; or in other words, |Δv-|≤ϵ.


## 5. Computationally Efficient Heuristics

As described in Section4, binary linear programming is formulated and the binary branch and bound/cut method is required. This has the worst-case complexity of Omin⁡m2,n2∑k=1n‍k2k.In this section, we propose a simplified version of Algorithms1 and 2, which decouples traffic allocation and flow selection into two concatenated subproblems. The traffic allocation can be formulated as a linear programming transportation problem. The flow selection can be achieved by using the aforementioned binary branch and bound/cut algorithm, but with a substantially smaller number of variables, that is, less than K. As a result, the complexity can be significantly reduced to the complexity of solving (8a), (8b), (8c), and (8d).First consider delay-tolerant traffic. We begin with optimizing the total trafficyij, i∈N, j∈⋃r=1R⋃k=1KLri,k, which needs to move from one of the nodes, that is, node i, to a detour, that is, detour j(i∉j). Following the EMD criterion, a linear programming problem can be formulated to determine the total traffic that needs to detour from the heavily loaded nodes, as given by(8a)minyij,∀i∈S,j∑i∈N∑r=1R∑j∈⋃k=1KLri,kcijyij,(8b)s.t.∑r=1R∑j∈⋃k=1KLri,kyij≤vi-vi′,foranyi∈N;(8c)∑i∈N∑r=1R∑j∈⋃k=1KLri,kδjjyij≤v--vj′+,foranyj∈N;(8d)minR∑i∈Nvi-vi′,∑j∈Nv--vj′+-∑i∈N∑j∈N∑r=1R∑j∈⋃k=1KLri,kδjjyij≤τ;which can be solved using the Simplex method [36]. The optimal solution for (8a), (8b), (8c), and (8d) is denoted by yij∗,∀i∈N;j∈⋃r=1R⋃k=1KLri,k, or yij∗ for short. A bisection search can also be taken to identify the minimum value of τ to preserve the feasibility of (8a), (8b), (8c), and (8d).Givenyij∗, we proceed to select the traffic flows for redirecting from node i to detour j and formulate a binary linear program, as given by(9)maxϕijk,∀k∈K∑k=1Kϕijkfk,s.t.∑k=1Kϕijkfk≤yij∗;ϕijk∈0,1,∀k∈K,which can be readily solved using binary branch and bound/cut.We start by offloading the traffic flows of the node withmaxi∈Nvi. And (9) is used to offload the flows first to the detour with minj∈⋃k=1KLji,k1/j∑j∈jvj and then to the other detours in increasing order of 1/j∑j∈jvj. This repeats for the other nodes in decreasing order of vi.Algorithm3 summarizes the proposed computationally efficient heuristic approach for route mutation under delay-tolerant traffic. Steps (3) and (4) execute the traffic allocation, following the EMD criterion and using (8a), (8b), (8c), and (8d). Steps (5) to (13) conduct the flow selection, using (9). These two parts concatenate to reduce the complexity.Algorithm 3:Heuristic route mutation for delay-tolerant traffic.
Input:  GN,E; A; R; the accumulative traffic of each node
v
i
′; the current route of each flow k∈K; fk; and the
initial θik(i∈N;k∈K).
Output:  θik,∀i∈N,k∈K
(1) Let vi=vi′+∑k∈K‍θikfk.
(2) repeat
(3) Run Steps (3) to (10) of Algorithm 1.
(4) substitute vi, v-, vi′ (i∈N), v-′, and cij into (8a), (8b), (8c), and (8d), and solve the optimal
solution yij∗ using the Simplex method;
(5) Arrange {vi,∀i∈N} in decreasing order so that vπ(1)≥vπ(2)≥⋯≥vπ(N).
(6) for  i=1,…,N  do
(7) Let Q=⋃r=1R⋃k=1KLrπi,k.
(8) repeat
(9) Let j∗=minj∈Q1/j∑j∈j‍vj;
(10) Offload traffic flows from node π(i) to detour j∗ by solving (9) for ϕπ(i)j∗k, given yij∗;
(11) Update
Q
⟵
Q
∖
j
∗;
v
π
(
i
)
⟵
v
π
(
i
)
-
∑
k
=
1
K
∑
j
∈
j
∗
ϕ
π
(
i
)
j
∗
k
f
k;
v
j
⟵
v
j
+
∑
k
=
1
K
ϕ
π
i
j
∗
k
f
k
,
∀
j
∈
j
∗.
(12) untilno traffic flow can be further offloaded from node π(i), or Q=∅.
(13) end for
(14) untilΔv-≤ϵ or yij∗=0∀i,j.The major complexity of Algorithm3 lies in solving (8a), (8b), (8c), (8d), and (9). Solving (8a), (8b), (8c), and (8d) requires the complexity of Ominm2,d2, as discussed in Section 4.1, where m=2N+1 here. In the worst-case scenario with a complete graph, d=NL, where L=N-3+∑r=2R‍(N-3)!/2(N-3-r)!, as given earlier, N is large, and the number of variables is larger than the number of constraints. Therefore, the complexity of (8a), (8b), (8c), and (8d) is ON2. Given each nonzero solution yij∗, (9) implements branch and bound/cut. The best-case complexity of solving (9) is O(k4), where k is the number of variables in (9), and k is substantially smaller than K. The worst-case complexity is O(k22k). Suppose all of the solutions from (8a), (8b), (8c), and (8d) are nonzero. The best-case and worst-case complexities of Algorithm 3 are Ok4N2 and Ok22kN2, respectively.Proceed with delay sensitive traffic, where the route lengths of traffic flows are strictly bounded. Algorithm3 can be readily extended to this case by evaluating the route lengths on-the-go. The constraints of bandwidth and switch capacity can also be considered in the same way in Algorithm 2, as discussed in Section 4.2.To be specific, we can attach (10) to (8a), (8b), (8c), and (8d) to capture the bandwidth constraint.(10)vi-vi′-∑j∈⋃k=1KLri,kyij+∑j∈N∑j∈⋃k=1KLri,kδijyjj≤Bi,foranyi∈N;we can also add (11) to (9) to restrain the number of flow entries per switch i.(11)∑k∈Kθik-∑k∈K∑j∈⋃k=1KLri,kθikϕijk+∑j∈N∑j∈⋃k=1KLri,k∑k∈Kδijθjkϕjjk≤tia,foranyi∈N.The extension is summarized in Algorithm4, where only the differences between the two algorithms are highlighted.Algorithm 4:Heuristic route mutation for delay-bounded traffic.
Input:  G(N,E); A; R; the accumulative traffic of each node
v
i
′; the current route of each flow k∈K; fk; the initial
θ
i
k; Lk; and the initial lk (i∈N;k∈K).
Output:  θik,∀i∈N,k∈K
(1) Let vi=vi′+∑k∈K‍θikfk and Δlk=Lk-lk.
(2) repeat
(3) Run Steps (3) to (5) of Algorithm 3
(4) for  i=1,…,N  do
(5) Let Q=⋃k=1K⋃r=1minR,ΔlkLrπi,k.
(6) repeat
(7) Run Steps (9) and (10) of Algorithm 3
(8) Update
Q
⟵
Q
∖
j
∗;
v
π
i
⟵
v
π
i
-
∑
k
=
1
K
∑
j
∈
j
∗
ϕ
π
(
i
)
j
∗
k
f
k;
v
j
⟵
v
j
+
∑
k
=
1
K
ϕ
π
(
i
)
j
∗
k
f
k
,
∀
j
∈
j
∗;
Δ
l
k
⟵
Δ
l
k
-
ϕ
π
i
j
∗
k
j
∗
,
∀
k
∈
K
.
(9) untilno traffic flow can be further offloaded from
node π(i), or Q=∅.
(10) end for
(11) untilΔv-≤ϵ or yij∗=0∀i,j.


## 6. Simulation and Evaluation

In this section, simulations are carried out to evaluate the proposed algorithms. We generate different randomk-regular graphs by using Python package NetworkX (NX) [37], where the degrees of all the nodes are k. Nodes have the same probabilities of requesting new routes at any instant. The routes between these nodes are initially generated by the Dijkstra algorithm [38] before our algorithms are carried out. The traffic loads of the routes are randomly and uniformly distributed within [0,1]. The simulations run in a computer with 32 GB RAM and 6 cores of Intel Xeon CPU. We use IBM-CPLEX to solve linear programming problems.We assume that adversaries can identify strategically important nodes by monitoring historically accumulative traffic of the nodes. Dynamic eavesdropping or interception is considered where, after every interval of monitoring, the eavesdropper acquires network information and updates the identification of targets accordingly. Under this eavesdropping model, we consider different numbers of nodes that the eavesdroppers can identify and the upper bound of traffic difference that eavesdroppers use to identify strategically important nodes. The upper bound reflects the eavesdropping capability and therefore is referred to as “node interception probability.” We also consider different time intervals for the eavesdroppings.The performance of the algorithms are measured by two metrics.(1) Coefficient of Variation (CV). A more disperse distribution of traffic can facilitate eavesdroppers recognizing heavily loaded nodes in network. Coefficient of variation is a metric to evaluate the dispersion of distribution, which is defined as the ratio of standard deviation σ to the mean μ,(12)cv=σμ.(2) The Percentage of Traffic That Bypasses Any Node Being Eavesdropped or Monitored. Figure 4 compares the CV of accumulated traffic between the proposed Algorithms 1, 2, 3, and 4, in a 50-node network with topology of 6-regular graph. The CV changes as the time elapses. In Algorithms 2 and 4, different upper bounds of QoS constraints are considered, that is, 1, 2, and 3 in number of nodes. We see that after routes mutations, the network and variations exhibit significantly reduced variance of accumulative traffic. In other words, the difference of traffic loads among the nodes fast diminishes. Moreover, with the increasing upper bounds of QoS constraints, Algorithm 2 approaches Algorithm 1.Figure 4
Results of four algorithms that we proposed, with and without QoS constraints. The networks are all generated as 6-regular graph with 50 nodes. The probability of initiating requests is 10%. There are 5000 instants and 50 rounds of iterations.Figure5 compares Algorithms 2 and 4. For comparison purpose, we also simulate the random route mutation proposed in [6]. Two cases are considered. The first case is to choose the optimal combination of routes to minimize the CV of traffic at any instant, referred to as “RRM-O.” The second case is to randomly choose routes as long as the QoS requirements are met and therefore referred to as “RRM-R.” Clearly, RRM-O is optimal in the sense of minimized CV of accumulative traffic. Unfortunately, RRM-O requires exhaustive search of all possible combinations of routes, with a prohibitive complexity. Figure 5 also demonstrates that Algorithm 2 outperforms Algorithm 4 and RRM-R. This is due to the fact that Algorithm 2 carefully designs the routes in a structured way to reduce the CV, where RRM-R does not.Figure 5
Results of Algorithms2 and 4; random route mutation methods proposed in [6]. The configurations of this simulation are the same as Figure 4.Table1 shows the average running time for each instant of the proposed algorithms with 50-node 6-regular graph, and the probability to request new routes is 10%. In this table, j represents the length of detour j, that is, the upper bound of QoS. As Algorithms 1 and 3 are designed without QoS constraints, we marked their j as ∖. Comparing the proposed heuristic methods with the method of [6], Table 1 shows that the increase of the upper bounds of QoS constraints has less influence on our algorithms. RRM-R degrades, when the length of a detour increases from a single hop to two hops. Here, we only plot the tightest QoS constraints of RRM-O in Table 1. This is because the complexity of RRM-O becomes too high to be practical, when the maximum allowed detour length is longer than L+1 hops.Table 1
Average computational time for different algorithms.
Algorithms
j
Computational time (s)
Algorithm1
∖
0.4870
Algorithm2
3
0.5370
Algorithm2
2
0.2826
Algorithm2
1
0.1132
Algorithm3
∖
0.0775
Algorithm4
3
0.1048
Algorithm4
2
0.0218
Algorithm4
1
0.0190
RRM-O
1
0.0363
RRM-R
3
0.2379
RRM-R
2
0.0518
RRM-R
1
0.0131As mentioned in Section3, the eavesdroppers can identify nodes by the differences of accumulative traffic. Figure 6 plots the distribution of “safe” traffic, that is, the traffic that does not pass through any compromised node, under the aforementioned dynamic interception model. In this figure, Algorithm 4 with the constraints of QoS of one-hop increment performs worst. This is because the first step of computing the traffic value to move, as given by (8a), (8b), (8c), and (8d), overlooks flows. As a result, a scenario that, for any i∈yij∗, there is no detour, that is, j, to move, may occur. When the number of flows increases, for example, the curve of “Algorithm 4-QoS 3” in Figure 6, the probability of flows to move also increases. Therefore it can outperform RRM-R with the upper bound of QoS constraint is three hops, that is, the line of “RRM-R-QoS 3.” We can also conclude from this figure that the results of this metric are consistent with Figure 5.Figure 6
The CDFs of the probabilities of traffic that do not pass through any node which is monitored or eavesdropped. The difference of traffic to identify strategically located nodes is 0.01. The interval of monitoring or eavesdropping is 10.Figure7 shows the convergent variance for networks with increasing numbers of nodes. The topologies of the networks are 5-regular random graphs. Each line in Figure 7 corresponds to a different probability that nodes are assigned as sources or destinations for some route. We see that, with the increasing network size and the increasing number of routes to mutate, the difference of nodes traffic becomes smaller. Algorithm 3 increasingly approaches Algorithm 1. In other words, the low-complexity heuristic, Algorithm 4, becomes increasingly robust against eavesdroppings.Figure 7
Results of Algorithms1 and 3 with different networks and different probabilities to choose nodes, where the connectivities of networks are all five.Figure8 shows the convergent CV in the networks with different connectivities. The probability of nodes initiating or receiving routing requests is all set to be 10%. Each line corresponds to the nodes having the same degree. As the network size gets larger, the difference of nodes traffic reduces. Figure 9 shows the CV of 40 nodes with connectivities of 3, 4, 5, and 6, respectively. With the increasing of network connectivities, there are more available detours to move to for sources, and the variations are getting smaller.Figure 8
Results of Algorithms1 and 3 with different sizes of networks and different connectivities.Figure 9
Results of Algorithms1 and 3 with 40 nodes and different connectivities.Figure10 shows the average running time of the algorithms corresponding to Figure 7. As compared with RRM, our proposed algorithms are far more tolerant against the growth of the network size. As a matter of fact, the convergence time of the proposed algorithms remains almost unchanged, as the network grows. In contrast, the RRM algorithms suffer from exponentially increasing complexity and convergence delay. Our methods are time efficient and suitable to larger-scale networks.Figure 10
Computational time of algorithms that have QoS constraints limitation. The upper bound of QoS constraints is one hop. The probability of nodes to request routes is 20%.


## 7. Conclusions

In this paper, we propose a node-centric route mutation method which interprets route mutation as a signature matching problem. A three-dimensional EMD model is formulated to match signatures. By this means, routes are mutated by increasingly taking detours, balancing historically accumulated traffic among switches. Heuristic approaches are also developed to significantly reduce the computational complexities of signature matching, enhancing the scalability of route mutation to defend large-scale SDNs. Simulation results show that our methods can disguise strategically located, important switches and increase the difficulties for eavesdroppers to identify the switches, thereby delaying or preventing malicious attacks. Significantly reduced complexities also indicate the suitability of our algorithms to large-scale networks.



---

*Source: 4651395-2017-12-25.xml*