Traffic engineering in hybrid SDN networks with multiple traffic matrices

Traffic engineering in hybrid SDN networks with multiple traffic matrices

Computer Networks 126 (2017) 187–199 Contents lists available at ScienceDirect Computer Networks journal homepage: www.elsevier.com/locate/comnet T...

2MB Sizes 0 Downloads 3 Views

Recommend Documents

SOFTmon - Traffic Monitoring for SDN
Software Defined Networking (SDN) substrates are basic enabler for the network virtualization. They provide many opportu

Traffic engineering in segment routing networks
Segment routing (SR) has been recently proposed as an alternative traffic engineering (TE) technology enabling relevant

Edge-based traffic engineering for OSPF networks
This paper proposes and evaluates a novel, edge-based approach, which we call the k-set Traffic Engineering (TE) method,

Load aware traffic engineering for mesh networks
Wireless Mesh Network (WMN) is a multi-hop mesh network that consists of mesh routers and mesh clients, where mesh route

Combined Analysis of Cost and Traffic Grooming Policies for Hybrid Networks Under Dynamic Traffic Requests
The benefit of a two-layer hybrid IP/MPLS (multi-protocol label switching) over a wavelength division multiplexing netwo

Interdomain traffic engineering with redistribution communities
Various traffic engineering techniques are used to control the flow of IP packets inside large ISP networks. However, fe

Route swapping in dynamic traffic networks
A dynamic traffic assignment (DTA) model typically consists of a traffic performance model and a route choice model. The

Control traffic balancing in software defined networks
To promise on-line and adaptive traffic engineering in software defined networks (SDNs), the control messages, e.g., the

Shortest paths in traffic-light networks
The time-constrained shortest path problem (TCSPP) is an important generalization of the shortest path problem (SPP) and

Computer Networks 126 (2017) 187–199

Contents lists available at ScienceDirect

Computer Networks journal homepage: www.elsevier.com/locate/comnet

Traffic engineering in hybrid SDN networks with multiple traffic matrices Yingya Guo a,c, Zhiliang Wang b,c,∗, Xia Yin a,c, Xingang Shi b,c, Jianping Wu a,c a

Department of Computer Science and Technology, Tsinghua University, Beijing 100084, PR China Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing 100084, PR China c Tsinghua National Laboratory for Information Science and Technology (TNLIST), Beijing 100084, PR China b

a r t i c l e

i n f o

Article history: Received 20 October 2016 Revised 14 July 2017 Accepted 18 July 2017 Available online 18 July 2017 Keywords: Traffic engineering Software Defined Networking Multiple traffic matrices Routing optimization

a b s t r a c t Traffic engineering (TE) is an efficient tool for optimizing traffic routing and balancing the flows in networks. Traffic is dynamic, previous TE optimization over a single traffic matrix (TM) have some limitations, because a single TM can have big measurement errors and is insufficient to depict the traffic flucuations. Thus, we consider using multiple TMs to overcome these limitations. With the emergence of Software Defined Networking (SDN), we can route flows more flexibly and better balance the flows over multiple TMs. However, due to the difficulties of full SDN deployment, hybrid SDN networks will be the prevailing architectures in the near future. Therefore, optimizing the routing over multiple TMs in a hybrid SDN network is of great interest. In this paper, we first formulate the problem of TE over multiple TMs and prove its NP-hardness. Next, we propose a heuristic algorithm for optimizing routing over multiple TMs by combining offline weight setting optimization with online splitting ratio optimization. Furthermore, we prove that the routes obtained in our algorithm are loop-free, and we provide an upper and lower bound of our proposed algorithm. Finally, we evaluate our method on measured traffic datasets with three network topologies. The results of extensive experiments demonstrate that the maximum link utilization of a network can be optimized better using our proposed algorithm. © 2017 Elsevier B.V. All rights reserved.

1. Introduction Due to the rapid development of Internet applications, such as games, videos, and chatting tools, traffic has been growing explosively in Internet Service Provider (ISP) networks over the past few decades. However, user experience and satisfaction cannot be guaranteed due to the frequent congestions, which are caused by the large amount of traffic delivered over networks. Therefore, how to avoid network congestions and achieve load balance of traffic have attracted worldwide attention. As an efficient tool for balancing the flows in a network, traffic engineering (TE) adjusts the routing configuration of a network to control how traffic is routed across the network and thus can greatly improve the network performance. In a traditional IP network, each link is assigned a weight and traffic is routed along the shortest paths between the source and destination nodes based on shortest path routing protocols, such as the Open Shortest Path First (OSPF) protocol. Therefore, the performance of TE is closely related to the weight setting of the network. ∗ Corresponding author at: Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing 10 0 084, PR China. E-mail addresses: [email protected], [email protected] (Z. Wang).

http://dx.doi.org/10.1016/j.comnet.2017.07.008 1389-1286/© 2017 Elsevier B.V. All rights reserved.

The classical TE method centrally computes a weight setting offline over a single traffic matrix (TM) based on shortest path routing protocols [1]. However, the optimization of routing over a single TM has limitations. First, due to the difficulty of measuring TMs accurately, considering only a single TM may lead to errors when we optimize routing in TE. Second, the traffic in a network is dynamically changing all the time [2]. Thus, a single TM is insufficient to depict the frequent fluctuations of the traffic over an entire day. Therefore, a weight setting optimized for a single TM may not work well for other TMs, thereby resulting in network congestion and degrading the network performance to a great extent [3]. Considering the above mentioned limitations, it is necessary to model the changing traffic with multiple TMs and optimize routing over multiple TMs instead of a single TM. Compared with a single TM, multiple TMs can represent the changing traffic better, because multiple TMs cannot only be robust to the errors in measurement, but also depict the fluctuations of dynamic traffic. In previous studies of TE, a common method for dealing with multiple TMs involves optimizing the OSPF link weights offline and setting the weights static over multiple TMs to maintain routing stability [2]. However, the static link weights and shortest paths

188

Y. Guo et al. / Computer Networks 126 (2017) 187–199

limitation degrade the performance of TE with fluctuating traffic demands. Software Defined Networking (SDN) is an established network architecture with separated control plane and data plane, and has attracted much attention from worldwide in recent years. We can implement routing algorithms or policies in the control plane to flexibly control the splitting ratio of the traffic to any outgoing link of the SDN switches. To achieve high network performance over multiple TMs, TE may require frequently adjusting the routing configuration to accommodate the changing traffic. SDN can handle the routing over dynamic traffic efficiently and schedule the flows flexibly in a timely manner in TE [4,5]. Therefore, with the introduction of SDN, we can better optimize the routing over multiple TMs and balance the flows in the network. However, a full SDN deployed network is impractical in the short term because of economical, organizational and technical challenges [6,7]. Thus, hybrid SDN networks, with partial SDN deployment, will be the prevailing architectures for a long time. It combines the flexibility of SDN with the robustness of Interior Gateway Protocols (IGP), such as OSPF. Studies in [8–11] are previous traffic engineering studies in hybrid SDN network. However, these studies are routing optimization under a single TM and ignore the fluctuations of the traffic in the network. In this paper we propose a routing optimizer framework for optimizing the routing over multiple TMs in a hybrid SDN network. Our basic idea is to combine offline weight optimization for legacy nodes with online splitting ratio optimization for a small proportion of SDN nodes in order to accommodate changeable traffic. The method for dealing with multiple TMs in offline weight optimization is also different from that employed in previous studies. To be specific, we first consider clustering all the historical TMs by using a data mining algorithm and we then compute the weight coefficient of every representative TM. Next, we calculate an expected TM by linearly combining the representative TMs and optimizing the OSPF weights over the obtained expected TM. To evaluate the validity and superior performance of our proposed algorithm, we implemented comparative experiments on a set of measured traffic datasets from three real networks: American Research and Education Network (Abilene), China Education and Research Network (CERNET), and Europe Research and Education Network (GEANT). The results of our extensive experiments demonstrate the effectiveness of our proposed algorithm. In summary, the main contributions of our paper are as follows.

• We propose a routing optimizer framework, which combines offline weight setting with online splitting ratio optimization over multiple TMs. • We employ routing algebra to prove that our proposed algorithm guarantees the loop-freeness of the routes. Moreover, we give an upper and lower bound of the proposed algorithm. • Through extensive experiments, we demonstrate that our algorithm can improve the network performance by 13% ∼ 55% compared with static OSPF weight setting [2] and the performance of our proposed algorithm is within 10% of the lower bound.

The rest of the paper is organized as follows. Section 2 introduces the related work. Section 3 depicts the hybrid SDN system. Section 4 presents the formulation of the problem and proves the NP-hardness of the problem. In Section 5, we propose a routing optimizer framework which guarantees the loop-freeness of the routing and discuss the upper and lower bound of the algorithm. In Section 6, we provide the datasets of the traffic and evaluate our proposed algorithm on three network topologies. Finally, we make conclusion in Section 7.

2. Related work In this section, we review some previous related studies of intra-domain TE algorithms and the mechanisms used in traditional IP networks, Multi-Protocol Label Switching (MPLS) networks and SDN networks, i.e, OSPF-TE, MPLS-TE, SDN-TE. OSPF-TE: The TE algorithms used in traditional IP network have been investigated extensively in the past few decades and they can be classified into two main categories: offline and online. In the offline category, the topology and TMs are known in advance and TMs remain static. The routing configuration is computed offline based on historical traffic information. The traffic is then routed according to the computed routing configuration [1,2]. In the online category, traffic is changing and routing has to be optimized in a dynamic scenario. Vallet and Brun [12] optimized routing according to the changing traffic by adjusting the OSPF link weights. However, frequent changes in the weight settings should be avoided to ensure routing stability, because these changes might lead to information flooding and transient routing loops in the network convergence process. Therefore, the network performance in traditional IP network deviates far from optimal due to the shortest path routing limitation of the OSPF protocol. By introducing SDN in our work, we can route the traffic flows more flexibly to improve the network performance and overcome the shortest path routing limitations. MPLS-TE: In MPLS-based TE, tunnels are established between the source and destination node pairs, so the traffic can be routed more flexibly and efficiently. There are three main methods for dealing with changing traffic in MPLS network. The first method involves optimizing routing in an offline manner over multiple TMs. A previous study [3] considered the minimization of the expected cost of multiple TMs. They aimed to find an optimal route for an expected TM, which was the weighted sum of the multiple TMs, and they evaluated the routes over multiple representative TMs. The second method employs online TE. MATE [13] and TEXCP [14] were two novel online TE protocols, which adaptively balanced the network flows and reacted to network failures or unexpected traffic demands efficiently. However, it increased the overheads when disseminating information to probe the link state. The third method for dealing with changing traffic is oblivious routing, which considers all possible TMs but degrades the performance for individual TMs. In [15], Applegate and Cohen discussed how to route flows with limited knowledge or no knowledge of the TMs. In theory, they proved that when using oblivious routing, the optimal oblivious ratio was bounded by 2. Oblivious routing considered all possible TMs in a TMs space but degraded the performance of the individual TMs. In [16], the authors proposed to combine prediction-based routing with oblivious routing to optimize the normal network conditions and bounded the worst-case performance penalty for unexpected changes. However, all of the aforementioned algorithms had to exploit established MPLS tunnels, thereby increasing the overheads and decreasing the scalability of the network. By contrast, in our work, we need no MPLS tunnels and we only need to deploy SDN on a small proportion of the network nodes. Our proposed method performs almost as well as the optimal routing [17] with a few nodes deployed SDN. SDN-TE: The emergence of SDN provides a more efficient method for routing the flows in a network. Microsoft [4] and Google [5] have built inter-datacenter wide area networks (WANs), which fully utilized the flexibility of SDN to achieve high network utilization. In [18], Zhang et al. achieved load balance with multiple TMs by combining explicit routing and destination routing in a SDN network. They formed an element-wise TM by selecting the maximum element among the multiple TMs and optimized the routes according to this maximum TM. For hybrid SDN networks, the authors proposed novel TE algorithms over a single TM

Y. Guo et al. / Computer Networks 126 (2017) 187–199

189

Table 1 Definition of notations. G = (V, E ) C(e) DH D Di (u, v) ri In(v) Out(v)

ω

Ns Nl Ui N n

φ

Fig. 1. System architecture.

in [9,11]. They combined the flexibility of centralized routing with the robustness of distributed routing to balance the load and managed the network more efficiently, however, they did not take multiple TMs into considerations. In [8], Agarwal et al. obtained traffic demand matrices by measuring traffic information online. They optimized the routing for SDN nodes by optimizing the splitting ratio of traffic, but they did not consider OSPF weight optimization. In summary, we can utilize SDN to route the flows more flexibly to overcome the restrictions of shortest path routing in IP networks and avoid the establishment of MPLS tunnels in MPLS networks. Previous methods for dealing with multiple TMs were either online or offline TE algorithms. In a hybrid SDN network, splitting ratio for SDN nodes and OSPF weight setting both influence the routing of traffic. In online traffic engineering [8] for hybrid networks, they only optimize the splitting ratio of SDN nodes for each online TM, but ignore the optimization of the OSPF weight setting. However, ingnoring the optimization of OSPF weight setting may impair the network performance [9]. Therefore, we propose to combine the optimization of online splitting ratio optimization (Online method) with the offline OSPF weight setting (Offline method) over multiple TMs. With the offline weight optimization, we can optimize the routing for legacy nodes; with the online splitting ratio optimization, we can adjust the routing of traffic for SDN nodes flexibly with changing traffic. In this manner, we can balance the flows better and achieve high performance in a hybrid SDN network.

3. System description In this section, we describe the hybrid SDN network system considered in our paper. As shown in Fig. 1, the hybrid SDN system comprises three components: legacy elements, SDN elements, and an SDN controller. Legacy elements are legacy routers that support distributed routing protocols, such as OSPF. They forward packets to the next hops on shortest paths determined by the OSPF protocol metric. SDN elements are SDN switches in the hybrid mode, which simultaneously support OSPF and SDN protocols, such as openflow [19]. The centralized external SDN controller controls the forwarding behavior of SDN elements. It distributes the flow entries into the flow table of SDN elements and SDN elements forward the packets according to the indications in the installed rules.

Undirected graph with nodes V and edges E Capacity of edge e Historical measured TMs set Multiple TMs set Traffic demands from node u to node v in Di The weight coefficient for TM Di The set of ingoing edges of node v The set of outgoing edges of node v The OSPF weight setting matrix The set of SDN nodes The set of legacy nodes The maximum link utilization under TM Di Positive integer set The number of representative TMs The weighted maximum link utilization

Therefore, routing can be controlled flexibly by implementing the routing policy in the centralized controller. In the following, we explain the overall process for the TE framework implemented in the SDN controller. As shown in Fig. 1, the controller first measures the network traffic information based on the flow statistical messages from the SDN elements or by collecting load information with Simple Network Management Protocol (SNMP). The routing configuration is then optimized by our proposed routing optimizer. Finally, we can deploy the computed routing configurations to control the network by adjusting the OSPF weight settings and by installing the forwarding rules in the SDN elements to control the forwarding behaviors of SDN elements.

4. Network model In this section, we first give definitions of the notations employed. We then formulate the problem of routing optimization over multiple TMs. Finally, we analyze the complexity of the problem and prove its NP-hardness.

4.1. Notations and problem formulation Definition. Before formulating the problem, we give definitions of the notations employed, summarized in Table 1. An Autonomous System (AS) is represented by G = (V, E ), where V is the node set and E is the edge set. The capacity of edge e is C(e). The TM set is denoted by D = {D1 , D2 , . . . , Dn }. Di is a matrix and its elements Di (u, v) represent the traffic demands from u to v (i = 1, 2, . . . , n, u, v ∈ V). Each TM Di is assigned a positive weight coefficient ri (i = 1, 2, . . . , n), which reflects the frequency of its corresponding  traffic pattern in all historical TMs DH . ni=1 ri = 1 and the value of ri is determined as the description in Section 5. The OSPF weight setting ω determines the routing for all legacy nodes Nl . The traffic splitting for Nl follows the Equal Cost Multi-Path (ECMP) principle. In hybrid SDN network, optimizing both the OSPF weight setting and the splitting ratio of traffic through SDN nodes improve the network performance when TM changes. However, for the sake of routing stability, the OSPF weight setting should be avoided being changed as much as possible [2,3,20]. Therefore, we propose to obtain a weight setting that has a good performance under multiple TMs to avoid changing OSPF weight setting frequently. The splitting flows for each SDN node Ns are variables x. In(v) and Out(v) denote the ingoing and outgoing links of node v, respectively. To achieve the goal of TE, we aim to search for ω under multiple TMs and splitting ratios for Ns so that we can minimize the weighted sum of maximum link utilization (MLU) over TM set D.

190

Y. Guo et al. / Computer Networks 126 (2017) 187–199

Problem Formulation. Our TE problem over TM set D can be formulated as follows.

Objective:

φ = minimize

n 

riUi

(1)

xtei (ω )

(2)

i=1



xtei (ω ) + Di (c, t ) =

e∈In(c )

 e∈Out (c )

c ∈ Ns , t ∈ V, i ∈ [1, n] 

xtei (ω ) ≤ UiC (e ),

e ∈ E, i ∈ [1, n]

(3)

t∈V n 

ri = 1,

0 ≤ ri ≤ 1

(4)

Fig. 2. A flow graph. C1 , C2 , . . . , Cn are SDN nodes. All flows are unit flows.

e∈E

(5)

Next, we prove that the exact cover by 3-sets (X3C) problem can be reduced to our problem in polynomial time. The X3C problem is known to be NP-complete [21,22] and the problem is stated as follows.

i=1

ω (e ) ∈ N

0 ≤ Ui ≤ 1, xtei (ω ) ≥ 0,

i ∈ [1, n] e ∈ E, t ∈ V, i ∈ [1, n]

(6) (7)

Eq. (1) is the objective function of the problem. We aim to opti mize the routing over multiple TMs. ni=1 riUi is the weighted sum of maximum link utilization (MLU), ri is a constant. (2)–(7) are the constraints. xtei (ω ) denotes the traffic destined to node t flowing on the ingress or egress links e of SDN nodes with the weight setting ω and TM Di . Eq. (2) denotes that the traffic flowing into the SDN node pluses the traffic that originates from this node equals the traffic flowing out of this node. Eq. (2) is the flow conservation constraint and this equation also implies that the traffic demand is met. Inequality (3) indicates that the total flows on an edge cannot exceed its capacity and this inequality is the capacity constraint. Eq. (4) restricts the total sum of ri to equaling 1. Eq. (5) requires that the OSPF weights are positive integers. Eqs. (6) and (7) restrict the MLU over each TM to not exceeding 1. Moreover, MLU and the flow on a link must be non-negative. Eqs. (2)–(7) form a constrained multi-commodity problem. The introduction of ω makes the problem a nonlinear programming problem. We expect to obtain ω and xtem (ω ) that minimize the weighted sum of MLU (1) over TM set D. 4.2. Problem complexity In previous section, we have formulated the problem of routing optimization over multiple TMs. In this section, we will analyze and discuss the complexity of the optimization problem. Theorem 1. Minimizing the weighted sum of MLU (φ ) over multiple TMs is an NP-hard problem. Proof. Minimizing the MLU over a single TM aims to find the weight setting and splitting ratio with the minimum MLU. Obviously, since the optimization over a single TM can be treated as a special case of the optimization over multiple TMs, the latter problem is harder than the former. If the former problem can be proved to be an NP-complete problem, then the latter, which is harder, is definitely an NP-hard problem. Therefore, we should first verify that minimizing the MLU over a single TM is an NP-complete problem. First, given a hybrid SDN network, if the link weights and splitting ratio are provided for the SDN elements, then we can compute the MLU of the network in polynomial time and check whether the MLU is less than a threshold U.

1. Instance: set X = x1 , x2 , . . . , x p of p elements ( p = 3q) and a family C of n 3-subsets of X (C = C1 , C2 , . . . , Cn , Ci ⊆ X, |Ci | = 3, i = 1, 2, . . . , n ), n ≥ q. 2. Question: does C contain a subfamily C ⊆C, of q(|C  | = q ) pairwise disjoint subsets of X? We construct a flow graph in Fig. 2. We assume that the instance of the X3C problem is the subgraph that is composed of C1 , C2 , ...,Cn and x1 , x2 , ...,xp . The edges between Ci and xj denote that xj ∈ Ci in the X3C problem. We then add some nodes to construct a flow graph [22] for TE in a hybrid SDN network. s and t are the source and destination nodes, respectively. The flows generated from node s are all unit flows. We assume that Ci (i = 1, 2, . . . , n ) are SDN nodes, whereas the others are legacy nodes. The link capacities are shown in Fig. 2. We prove that the answer to the question in X3C is positive if and only if the MLU in Fig. 2 is equal to 1 and the flow from s to t is q. Assume that the subfamily C  = Ci(1 ) , Ci(2 ) , . . . , Ci(q ) exactly covers the set X and that it is a positive answer to X3C. We assign unit flows to all edges (s, Ci(j) ) for j = 1, 2, . . . , q. We set the link weights to 1 and we can obtain a splitting ratio of 1/3 for all the outgoing links of the nodes Ci(j) and f (xk , u ) = 1/3 for k = 1, 2, . . . , p. Finally, we find that the MLU is 1 and the flow from s to t is q. Conversely, if the flow from s to t is q, then there should be q unit flows originated from s. Since the MLU is 1, then for the flow arrives at Ci , i = 1, 2, . . . , q, the flow should be evenly split, the flow on the link (Ci , xj ) should be exactly 1/3 and for any xj , Ci always satisfies xj ∈ Ci and ∀i, j, i = j, Ci ∩ C j , . . . = ∅. For if Ci ∩ C j = xm , then the flow outgoing from xm is more than 1/3, which results the overloading of link (xm , u). Therefore, x j , j = 1, 2, . . . , p are covered by Ci , i = 1, 2, . . . , q and for ∀Ci , Cj , Ci ∩ C j , . . . = ∅. Then, we can combine the disjoint sets Ci ⊆C, which comprise subfamily C , and thus we have a positive answer to X3C. By reducing the X3C problem to our problem, we can prove that minimizing the MLU under a single TM is an NP-complete problem. As a result, our optimization problem, which is harder than minimizing the MLU over a single TM, is NP-hard.  5. Routing optimizer Given the NP-hardness of the optimization problem, we propose a heuristic algorithm for optimizing the routing configuration in a hybrid SDN network. In this section, we first present the

Y. Guo et al. / Computer Networks 126 (2017) 187–199

191

ing a weight setting with the minimum MLU (weight optimizer). With the weight setting fixed, we optimize the splitting ratio of the flows online for multiple TMs (splitting ratio optimizer). Finally, we obtain a near optimal routing configuration. Algorithm 1 is routing optimizer. Now, we introduce each part of the routing optimizer in details. Algorithm 1 Routing optimizer Require: G = (V, E ), Ns , C, DH 1: (r, D) = TMs_analyzer() 2: S = SDN_ placement() 3: weight_optimizer() 4: while j < num_o f _tm do 5: U j = splitting_ratio_optimizer () 6: end while

Fig. 3. Routing optimizer framework.

whole framework of our proposed algorithm, i.e., the routing optimizer in Fig. 3. We then discuss the complexity of the routing optimizer. Next, we prove that the routing optimizer guarantees the loop-free property of the routes. Finally, we provide an upper and lower bound of the proposed routing optimizer.

5.1.1. TMs_analyzer The details of the TMs_analyzer are described as follows. We cluster all the historical TMs and treat the cluster centroids as our representative TMs. In order to obtain a few representative traffic demand matrices D = {Di }, i = 1, . . . , n that reflect the variations in traffic demand during the whole day, we propose to use the classical data mining clustering algorithm, K-means, to automatically cluster the historical TMs into n clusters S = {Si }, i = 1, . . . , n. We obtain the cluster centroid TMs by computing Eqs. (8) and (9) iteratively:

S = argmin S

Di =

5.1. Proposed routing optimizer framework The formulated problem in Section 4 is a nonlinear programming problem. But if we fixed the weight setting ω, then the problem can be transformed into a linear programming problem, which is easy to solve by LP solvers in polynomial time. Therefore, we first determine the OSPF weight settings and then solve the linear programming problem to obtain the splitting ratios for SDN nodes. Because in the process of routing convergence, it may lead to information flooding and transient routing loops. For the sake of routing stability, the OSPF weight settings should remain static over different Di . Therefore, the optimized ω should work well over all the TMs in D. The splitting ratio of SDN nodes can be adjusted and changed in a flexible manner to accommodate traffic fluctuations. Therefore, we combine the offline weight setting optimization with online splitting ratio optimization in our proposed routing optimization method. The framework of our proposed algorithm is shown in Fig. 3. First, we obtain multiple representative TMs D = {D1 , D2 , . . . , Dn } from the historical measured TMs and compute their corresponding weight coefficients r = {r1 , r2 , . . . , rn } by clustering the historical TMs set DH with K-means [23] algorithm. Then, we can obtain an expected TM by linearly combining multiple TMs with weight  coefficients ri : exp_T M = ni=1 ri Di (TMs analyzer). The TM with a large ri means being put more emphasis on when we optimize the routing, and thus the performance of our routing algorithm can be improved greatly. We then deterimine the placement of the SDN nodes using greedy algorithm under the expected TM (SDN placement). In the greedy algorithm, we choose to deploy the node that gives the minimum MLU during each iteration. After that, we begin the routing optimization. We heuristically and iteratively search the weight setting offline over the expected TM for find-

n  

dist (t j , Di )

(8)

i=1 t j ∈Si

1 

|Si | t ∈S j

tj

(9)

i

where dist(tj , Di ) denotes the Euclidean distance between two matrices tj , Di . |Si | defines the number of elements in set Si . After iteration, we treat the optimal centroid matrices {D1 , D2 ...Dn } as our representative TMs. We compute the weight ri for each centroid matrix Di by counting the number of TMs in its corresponding cluster Si , i.e., ri =   |Si| S ∈S |Si | is a constant, which equals the num|S | , i = 1, . . . , n. Si ∈S

i

i

ber of all the historical TMs. To optimize the routing so that it can work well over different traffic patterns, we aim to obtain an expected TM which reflects the overall traffic patterns in a day. More specifically, we first employ K-means to obtain the distribution of historical TMs by clustering all the measured TMs (Fig. 4). The weight ri for each cluster centroid TM can be obtained by counting the number of TMs in the corresponding cluster. The value of the weight coefficient reflects the frequency of its corresponding traffic pattern in all measured TMs. And, a larger weight means more consideration of its corresponding representative TM when optimizing the network settings. We can then obtain an expected TM, which can better depict the average traffic under different traffic patterns by linearly combining the TMs with the weight coefficients:  exp_T M = ni=1 ri Di . 5.1.2. SDN_placement We first determine the number and locations of the SDN nodes in the network. We employ a greedy algorithm to determine the placement of the SDN nodes. As shown in Algorithm 2, we deploy the node that gives the minimum MLU during each iteration (line 2-8) until the deployment ratio is satisfied (lines 1–11). Finally, we obtain the deployment sequence B (line 12).

192

Y. Guo et al. / Computer Networks 126 (2017) 187–199

Fig. 4. Traffic clustered by K-means. This figure shows the traffic volume varies with the time of one day in CERNET. The traffic is measured every five minutes. Through K-means method, TMs are clustered into eight clusters.

Algorithm 2 SDN_placement Require: G = (V, E ), C, ω, exp_T M 1: while i < N ∗ deployment _ratio do for every node a ∈ V, a ∈ / B do 2: 3: util = splitting ratio optimizer() if ut il < best ut il then 4: b=a 5: 6: best ut il = ut il end if 7: end for 8:  B=B b 9: 10: i++ 11: end while 12: Return B

Algorithm 3 Weight_optimizer Require: G = (V, E ), Ns , C, D 1: Initial weight setting matrix ω, U 2: cur r util = floydwarshall (G, ω, D ) 3: best ut il = cur r util 4: for iteration times increase by one do ωcurr =neighbor_search (G, ω ) 5: for j < num_o f _tm do 6: 7: U j = splitting ratio optimizer () φ + = r j *U j 8: 9: end for if φ < best ut il then 10: best ut il = φ 11: 12: ωbest = ωcurr end if 13: 14: end for 15: return ωbest

5.1.3. weight_optimizer The weight optimizer is described in Algorithm 3. We aim to find a single weight setting works well under multiple TMs D. We employ the refined local search heuristic algorithm described in [1] to search for the optimal weight setting offline. We search for the optimal weight setting under the expected TM (line 5) and evaluate the weight setting under the TMs set D to minimize the weighted MLU φ (line 6-9). Finally, we obtain the optimized OSPF weight setting (line 15).

5.1.4. splitting_ratio_optimizer With the weight setting fixed, we optimize the splitting ratio of the SDN nodes in Algorithm 4. In this algorithm, we first conAlgorithm 4 splitting_ratio_optimizer Require: G = (V, E ), C, ωcurr , Ns , Di 1: for vertex d ∈ V do DAG =Dijkstra_Shortest_Path(ωcurr , d ) 2: for arc (i, j ) in outgoing_links(Ns ) do 3: if i, j are not comparable then 4: DAG(i, j ) = 1 5: end if 6: end for 7: for vertex v in Topological_Sort(V ) do 8: expr = Multi_Commodity (A, V, Di ) 9: end for 10: 11: end for 12: Ui = cplex_solve (expr ) struct a Directed Acyclic Graph (DAG) for each destined node (line 2). More specifically, for each legacy node destined to a given node, we add all the adjacent edges on the shortest path trees destined to this node with Dijkstra algorithm. For each SDN node i, we add all the adjacent edges that are on the shortest path trees as well as the adjacent edges (i, j) ∈ E for which i and j are uncomparable (lines 4–6, we define i and j as not comparable when there are no paths between i and j in the current DAG, the details are shown in Section 5.3). A simple example of DAG construction is shown in Fig. 5. The loop-free correctness of the routes is verified in Section 5.3. Given these DAGs, we can form Linear Programs (LP) based on the multi-commodity flow constraints (2)–(7) (lines 8– 10) and solve them with the LP solver CPLEX (line 12). Finally, we obtain the traffic on each link and MLU. To make a summary, in the proposed routing optimizer, we combine offline weight optimization with online splitting ratio optimization. We optimize the weight setting offline in Algorithm 3 and then our problem can be transformed to a linear programming problem. We solve the linear programming problem to obtain the optimal splitting ratio in Algorithm 4. 5.2. Algorithm complexity The routing optimizer comprises three main parts. The TMs_analyzer is a data mining algorithm and its complexity is

Y. Guo et al. / Computer Networks 126 (2017) 187–199

193

Fig. 5. Construct the DAG destined to D. C is a SDN node. (a) is the topology and the number beside the edge is the OSPF weight. (b) is the shortest path tree to D. (c)–(e) shows the process of constructing the DAG. For node C, we first add (C, D). (C, A) is the adjacent link of C and C, A are uncomparable, we add (C, A). For other nodes, we add the edges on the shortest paths.

O(tnm) (t is the number of iteration, m is the number of sample). The complexity of Dijkstra’s Shortest Path algorithm is O(|V|2 ); therefore, the complexity of the online Splitting_ratio_optimizer (Algorithm 4) is O(|V|3 ). Therefore, the complexity of the greedy algorithm in Algorithm 2 is O(|V|4 ). The complexity of floydwarshall, neighbor_search functions are both O(|V|3 ), so the complexity of the offline weight_optimizer (Algorithm 3) is O(t1 |V|3 ) (t1 is the number of iterations). Thus, the complexity of routing optimizer is O(|V|4 ). 5.3. Loop-free correctness Given a routing algorithm, it is necessary to prove the loopfree correctness of the algorithm. Now we introduce routing algebra theory [24,25] to prove the loop-free correctness of the routes generated by the routing optimizer. First, we define some notations and semantics. The algebra is in the structure of three-tuple form (S, , t), where S is the nodes set, is the order defined on the set S, and t is a node in S. We define the relation as follows: for a shortest path tree destined to node t in G, if there exists a path from node u to node v in the shortest path tree, then we say that u v for the tree destined to t; if there is no path from u to v or path from v to u, then we say that u and v are not comparable. The order has following properties: 1. is reflexive: a a for all a ∈ S 2. is anti-symmetric: if a b and b a then a = b 3. is transitive: if a b and b c then a c For Property 1, we can easily get that there is always a path from a to a in a shortest path tree. For Property 2, we first assume that a = b. Given the conditions that there are paths between a and b and b and a, then there is a loop between a and b, which contradicts the fact that the paths are all on a tree, therefore, a = b must be satisfied. For Property 3, if there is a shortest path from a to b, and from b to c, then we can concatenate the two paths and obtain a shortest path from a to c. Therefore, we must have a c. Lemma 1. is a partial relation. Proof. A partial relation should satisfy three constraints, i.e., it must be reflexive,anti-symmetric and transitive. According to the previous proof, we can observe that is reflexive,anti-symmetric and transitive. Therefore, is a partial relation.  For every a, b ∈ S, destined to t, the relations between a and b are: a b or b a or a and b are not comparable. As depicted in Fig. 5 (b), the relations for A, B, C and D are: A B D, C D, A and C, B and C are not comparable. Lemma 2. If every edge (u, v) in the path p satisfies that u v for a destined node t, then the path is loop free. Proof. If the edges of p are (u0 , v1 ), (v1 , v2 ), ...,(vn , v0 ), which satisfy that u0 v1 , v1 v2 , ...,vn v0 . We then can obtain that u0 v1

v2 , . . . , v0 . Thus, we can conclude that path p is on the shortest path tree to a destination node t. Therefore, the path is loopfree.  Neighbor nodes. If there is a directed edge from node u to node v in graph G, then we say v is the neighbor node of u. Available Next Hop. We denote the available next hops of node u destined to node d as N(u, d), which are the nodes depicted in (10). If u ∈ Nl , N(u, d) are the neighbor nodes v that satisfy u v for the shortest path tree destined to d. If u ∈ Ns , N(u, d) are the neighbor nodes v that satisfy u v or they are not comparable to u for the shortest path tree destined to d. In addition, if v is not comparable to u and it is chosen as the next hop for node u, we then define the relation between u and v as u v.



N (u, d ) =

v, u ∈ Nl , u v

p, u ∈ Ns , u p or p, u not comparable

(10)

Theorem 2 Loop-Free Condition (LFC). The routes are loop-free provided that every node u chooses the next hop from N(u, d). Proof. First, for a tree destined to node d and any node u ∈ V, if we choose the next hop v from N(u, d) that satisfies u v, then according to Lemma 2, the path is loop-free. If node u ∈ Ns , for a node v that is not comparable to u, then there will not be a path from u to v or from v to u in the tree destined to d. Thus, there will not be a loop every time we select the next hop from N(u, d).  In Algorithm 4, to construct the DAG, we choose the nodes in N(u, d) as the next hops to balance the flows. According to Theorem 2, the routing optimizer guarantees the loop-freeness of the routes, which is a requisite for the routing algorithm. 5.4. An upper and lower bound In this part, we give an upper and lower bound of the proposed algorithm. Let ψ (f, D) be the mapping from splitting ratio f and a TM D to the MLU of the network. Definition 1. We say matrix D1 ≤ D2 , if for any i, j ∈ V, D1 (i, j) ≤ D2 (i, j). Lemma 3. Given two TMs D1 and D2 , if D1 ≤ D2 , then ψ (f, D1 ) ≤ ψ (f, D2 ). Proof. Given a splitting ratio f, if D1 ≤ D2 , then the flow on each link with D1 is no more than the flow on the same link with D2 . As a result, the MLU under D1 is no more than D2 , that is ψ (f, D1 ) ≤ ψ (f, D2 ).  Lemma 4. Given a TM D and constant ratio α , we can get ψ ( f, α D ) = αψ ( f, D ). Proof. Let f(i, j, e) denote the splitting ratio of D(i,  j) on link e. ψ ( f, α D ) = max∀e i, j∈V f (i, j,eC)(∗eα)D(i, j ) =  (i, j ) max∀e α i, j∈V f (i, j,eC ()e∗D = αψ ( f, D )  )

194

Y. Guo et al. / Computer Networks 126 (2017) 187–199

Table 2 Three network topologies: Abilene, CERNET, and GEANT.

6.2. Parameters

Topologies

Nodes

Links

Abilene CERNET GEANT

12 14 23

30 32 74

Lemma 5. Given two TMs D1 and D2 , we can get ψ ( f, D1 + D2 ) = ψ ( f, D1 ) + ψ ( f, D2 ). Proof. Let f(i, j, e) denote the splitting ratio of D(i, j) on  link e. ψ ( f, D1 + D2 ) = max∀e i, j∈V f (i, j,e)∗(DC1 ((i,e)j )+D2 (i, j )) =   f (i, j,e )∗D1 (i, j ) f (i, j,e )∗D2 (i, j ) maxe i, j∈V + maxe i, j∈V = ψ ( f, D1 ) + C (e ) C (e ) ψ ( f, D2 )  Theorem 3 Upper and Lower Bounds. Let Dmax (i, j ) = n o maxy∈n Dy (i, j ) and Uyo = minψ ( f, Dy ), we can get y=1 ryUy ≤ n r ψ ( f, D ) ≤ ψ ( f, D ) y max y=1 y Proof. For the left side, Uyo = minψ ( f, Dy ) ≤ ψ ( f, Dy ), we can eas  ily get ny=1 ryUyo ≤ ny=1 ry ψ ( f, Dy ). n For the right side, i=1 ri = 1, Di ≤ Dmax , r1 D1 + r2 D2 + · · · + rn Dn ≤ r1 Dmax + r2 Dmax + · · · + rn Dmax = Dmax . According to lemma 3, we can get ψ ( f, r1 D1 + r2 D2 + · · · rn Dn ) ≤ ψ ( f, Dmax ). Based on Lemma 4,5, we can get ψ ( f, r1 D1 + r2 D2 + · · · + rn Dn ) =  ψ ( f, r1 D1 ) + ψ ( f, r2 D2 ) + · · · + ψ ( f, rn Dn ) = ny=1 ry ψ ( f, Dy ). n Therefore, y=1 ry ψ ( f, Dy ) ≤ ψ ( f, Dmax ).  Upper bound is the MLU that we compute based on the maximum TM [18]. Lower bound is the optimal weighted MLU that we compute over multiple TMs. We will evaluate these two algorithms in Section 6. 6. Evaluation In this section, we evaluate the algorithms by conducting experiments on three network topologies. First, we present the topology datasets based on existing topologies and TM datasets based on measured traffic. Then, we carry on the experiments to determine the value of the two parameters in our algorithm: the SDN deployment ratios and number of representative TMs. Next, we evaluate our algorithm under various topologies with different time periods, different SDN deployment ratios and different number of representative TMs. Finally, we provide the CPU times of different algorithms. 6.1. Dataset 6.1.1. Topologies We evaluate our algorithm on three network topologies: Abilene, CERNET, and GEANT. Detailed information for the three topologies is shown in Table 2. 6.1.2. Traffic matrices The TMs datasets for Abilene are provided by the TOTEM project [26]. The TMs are measured every five minutes and the time of the evaluated TMs ranges from 2003-03-01 00:00:00 to 2003-03-14 23:59:59. The TMs datasets for CERNET are provided by Zhang et al. [27], which collects a range of node-granularity TMs using NetFlow. The TMs are measured every five minutes. The dates for the TMs range from 2013-02-19 22:10:00 to 2013-03-26 15:20:00. The TMs datasets for GEANT are provided by Uhlig [28]. The TMs are measured every fifteen minutes. The dates for the collected TMs range from 2005-05-04 15:30:00 to 2005-08-31 07:50:00.

In our proposed algorithm, we first determine the number of representative TMs and the deployment ratio for SDN nodes. To analyze the impact of the number of representative TMs on the performance of our proposed method, we set the number of the representative TMs at different values. Here, for conveniently analyzing the impact of the number of the representative TMs, we set the deployment ratio at a constant ratio, e.g., 40%. From the curves of MLU in Fig. 6, the average MLU decreases with the increasing of the number of representative TMs. In addition, when the number of representative TMs is less than eight, the average MLU decreases rapidly. The curve stays stable when the number of representative TMs is larger than 8. Thus, we set the number of representative TMs to 8 in the following experiments. To analyze the impact of the deployment ratio on the performance of our proposed method, we set the deployment ratios at different values. From the curves in Fig. 7, we can observe that the average MLU decreases with the increasing of deployment ratio. The average MLU decreases rapidly when the deployment ratio of SDN nodes is smaller than 40% and becomes approaching flat when the deployment ratio of SDN nodes is large than 40%. We can obtain that at deployment ratio of 40%, we can reap the most of benefit for the three topologies. Therefore, in the following experiments we choose to deploy 40% of the nodes. 6.3. Minimizing MLU In simulations, we propose a novel TE evaluation method and evaluate our routing optimizer. We divide the TMs dataset into two parts: a training set and a testing set. We employ the training set to obtain a weight setting and the testing set to validate the effectiveness of our optimized weight setting and online splitting ratio optimization. To be concrete, we first cluster eight representative TMs based on one-day historical TMs. We then use our proposed algorithm to compute the weight setting offline based on the eight clustered representative TMs. Next, we apply the weight setting to the network for other days and keep it static. Finally, we optimize the splitting ratio for SDN elements online (every five minutes for Abilene, CERNET and fifteen minutes for GEANT) to demonstrate the effectiveness of our algorithm. We denote our routing optimizer framework as OORO (Online Offline Routing Optimizer). OSPF denotes the algorithm described in [2]. The weight setting in [2] is optimized on the eight clustered TMs of the first day and remains static during the following days. Upper and Lower are the algorithms that we mentioned in Section 5.4. Upper [18] is the algorithm that optimizes the routing under Dmax . Online method is the algorithm mentioned in [8] and this method only optimizes the splitting ratio for SDN nodes online. Lower is the online routing algorithm that optimizes the weight setting and splitting ratio online simultaneously for each TM. All of the initial weight settings of the network are set to 1. We first plot the Cumulative Distribution Function (CDF) curves for Abilene, CERNET and GEANT in Fig. 8. The algorithms optimize the OSPF weight over eight representative TMs clustered from 288 TMs (96 TMs for GEANT) and optimize the splitting ratio online with the 288 TMs (96 TMs for GEANT) of a new day. As shown in Fig. 8, the MLU of OORO under three topologies mainly concentrates on 0.04–0.06, 0.2–0.3, and 0.05–0.15, while the MLU of Upper and OSPF mainly concentrate on 0.08–0.1, 0.3– 0.5, 0.15–0.2, and the MLU of Online mainly focuses on 0.05–0.06, 0.3–0.4, 0.1–0.15. We can find that OORO obtains a lower MLU on one-day traffic compared with OSPF, Upper and Online. For in the OSPF method, they just optimize the OSPF weight setting over multiple TMs and keep the weight setting static under dynamic traffic. The traffic splitting ratio cannot be adjusted flexibly due

Y. Guo et al. / Computer Networks 126 (2017) 187–199

195

Fig. 6. The average MLU under different number of representative TMs.

Fig. 7. The average MLU under different deployment ratio of SDN.

Fig. 8. The CDF curves of MLU on the one-day 288 TMs. OORO performs better than the other algorithms.

to shortest path routing limitation. However, in our algorithm, we can optimize the OSPF weight setting as well as the splitting ratio for the SDN nodes. The splitting ratio for SDN nodes can be flexibly adjusted with dynamic traffic and our method breaks the constraints of the shortest path routing. Therefore, our algorithm performs better than the OSPF method. For the Upper method in the curves, the routing is optimized only over the maximum TM and ignore the TMs at other time. In our method, we optimize the routing to work well over different traffic patterns. Therefore, our algorithm outperforms Upper on average. The Online method proposed in [8] only optimizes the splitting ratio of the traffic for SDN nodes, but ignores the optimization of routing for traffic through OSPF nodes. In hybrid SDN network, both the routing for the traffic through OSPF nodes and the routing for the traffic through SDN nodes affect the performance of traffic engineering. Therefore, the network performance of the online method [8] is

limited due to only considering splitting ratio optimization. Taking the adjustment of OSPF weight setting into consideration, our proposed method can obtain superior network performance. Therefore, in our proposed method, we adopt to combine the offline optimization of OSPF weight setting with the online splitting ratio optimization for SDN nodes. The results in Fig. 8 demonstrate that our algorithm outperforms the online splitting ratio optimization implementation in [8]. OORO (single) is the implementation of our algorithm that optimizes routing over a single TM, which is the cluster centroid when clustering all the TMs into one cluster. We can also obtain from the CDF curves that routing optimized over multiple TMs performs better than that over a single TM. The reason is that the routing optimized over a traffic pattern (OORO(single)) may not perform well over other traffic patterns. In our proposed method, we optimize the routing over different traffic patterns and obtain a routing working well on average. In sum-

196

Y. Guo et al. / Computer Networks 126 (2017) 187–199

Fig. 9. The CDF curves of MLU for ten days. We can observe that our algorithm can obtain a lower MLU compared to Upper and OSPF on each day.

Fig. 10. Average MLU for ten days.

Fig. 11. CDF curves under different deployment ratios of SDN nodes in Abilene.

mary, our algorithm obtains a lower MLU than other algorithms with changing traffic demands of one day. Moreover, in Figs. 9 and 10, we show the curves for the algorithms evaluated on the TMs during ten days to demonstrate the superior performance of our algorithm. Clearly, OORO can achieve a lower average MLU than Upper, OSPF and Online. Next, we verify that our algorithm performs well under other deployment ratios of SDN and other number of representative TMs. We plot the CDF curves of MLU under different SDN deployment ratios and different number of representative TMs in Figs. 11 and 12. We only plot the curves obtained using Abilene, because the results are similar for the other two topologies. Figs. 11 and 12 show that with different deployment ratios of SDN nodes (20%, 30%, 60% and 80%) and different number of TMs (4 TMs, 6 TMs, 10 TMs, and 20 TMs), the MLU obtained by our proposed algorithm is better than that obtained by the other algorithms Therefore, based on the results of the simulations, we can get the conclusion that the MLU of the network can be optimized better by our proposed algorithm. In particular, to determine the improvement ratios, we analyze the average MLU of ten days in

Table 3 Average MLU under different algorithms. Name

OSPF

Upper

Online

OORO

Lower

Abilene CERNET GEANT

0.084 0.260 0.174

0.073 0.287 0.164

0.058 0.32 0.16

0.053 0.225 0.077

0.050 0.210 0.072

Table 4 The improvement ratio of OORO. OORO OSPF

Name

1−

Abilene CERNET GEANT

36.9% 13.4% 55.7%

1−

OORO U pper

27.4% 21.6% 53.0%

1−

OORO Online

8.6% 29.7% 51.9%

1−

OORO Lower

−6.0% −7.1% −7.0%

Table 3 and we compare the improvement ratios for OORO compared with OSPF, Upper, Online and Lower in Table 4. We can obtain that OORO improves the network performance by 13.4–55.7% compared with OSPF, 21.6–53.0% compared with Upper and 8.6–

Y. Guo et al. / Computer Networks 126 (2017) 187–199

197

Fig. 12. CDF curves under different number of representative TMs in Abilene.

Table 5 The CPU time of OORO with different topologies. Name

Offline

Online

Abilene CERNET GEANT

24.382 s 50.621 s 18.5 min

0.0025 s 0.0035 s 0.026 s

Nos. 2015AA016105 and 2015AA015603, the National Natural Science Foundation of China (Grant no. 61202357), and the Project for 2012 Next Generation Internet technology research and development, industrialization, and large scale commercial application of China (No. 2012 1763).

References 51.9% compared with Online. In addition, the results obtained by OORO are within 10% deviation from the solutions produced by Lower. The results of the extensive experiments demonstrate the effectiveness of our routing optimizer. 6.4. CPU time Finally we determine the CPU time of the experiments. In our simulations, the experiments are implemented on a computer with an Intel Core i5, CPU at 2.6 GHz and with 4 GB of memory. The CPU times required by the offline and online parts of our proposed algorithms under the three different topologies are shown in Table 5. The CPU time for the online part is the average online optimization time for each TM. As shown in Table 5, the CPU times required by the offline and online parts of the algorithm both increase with the increasing of topology size. We can find that the offline weight optimizer takes the most time and the online splitting ratio optimizer in the framework works efficiently with the changing of traffic demand. Therefore, our algorithm is suitable for implementation in an SDN controller to set the optimized weight setting static and optimize the routing online with the dynamic traffic. 7. Conclusion In hybrid SDN network, previous studies mainly focus on optimizing the routing over a single TM. However, the traffic is uncertain and changeable. It is difficult to optimize the routing of TE under dynamic traffic. Compared with a single TM, multiple TMs can better represent the dynamic traffic. Therefore, it is meaningful and practical to optimize the routing over multiple TMs. In this paper, we tackle the problem of optimize the routing over multiple TMs in a hybrid SDN network. We propose a framework for simultaneously optimizing routing offline and online over multiple TMs. Through extensive experiments, we can find that our proposed framework performs better than other algorithms. In future research, we will consider implementing the routing optimizer in the SDN controller and evaluating it in the testbed. Acknowledgment This work is partially supported by the National High Technology Research and Development Program of China (863 Program)

[1] B. Fortz, M. Thorup, Internet traffic engineering by optimizing OSPF weights, in: Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 20 0 0, 2, IEEE, 20 0 0, pp. 519–528. [2] B. Fortz, M. Thorup, Optimizing OSPF/IS-IS weights in a changing world, IEEE J. Sel. Areas Commun. 20 (4) (2002) 756–767. [3] C. Zhang, Y. Liu, W. Gong, J. Kurose, R. Moll, D. Towsley, On optimal routing with multiple traffic matrices, in: Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2005, 1, IEEE, 2005, pp. 607–618. [4] C.-Y. Hong, S. Kandula, R. Mahajan, M. Zhang, V. Gill, M. Nanduri, R. Wattenhofer, Achieving high utilization with software-driven wan, in: Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM, ACM, 2013, pp. 15–26. [5] S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh, S. Venkata, J. Wanderer, J. Zhou, M. Zhu, et al., B4: experience with a globally-deployed software defined wan, in: Proceedings of the ACM SIGCOMM 2013 Conference on SIGCOMM, ACM, 2013, pp. 3–14. [6] S. Vissicchio, L. Vanbever, O. Bonaventure, Opportunities and research challenges of hybrid software defined networks, ACM SIGCOMM Comput. Commun. Rev. 44 (2) (2014) 70–75. [7] D. Levin, M. Canini, S. Schmid, A. Feldmann, Incremental sdn deployment in enterprise networks, ACM SIGCOMM Comput. Commun. Rev. 43 (2013) 473–474. [8] S. Agarwal, M. Kodialam, T. Lakshman, Traffic engineering in software defined networks, in: Proceedings IEEE INFOCOM, IEEE, 2013, pp. 2211–2219. [9] Y. Guo, Z. Wang, X. Yin, X. Shi, J. Wu, Traffic engineering in SDN/OSPF hybrid network, in: Proceedings of the 2014 IEEE 22nd International Conference on Network Protocols, ICNP, IEEE, 2014, pp. 563–568. [10] M. Caria, T. Das, A. Jukan, M. Hoffmann, Divide and conquer: partitioning ospf networks with sdn, in: Proceedings of the IFIP/IEEE International Symposium on Integrated Network Management, 2015. [11] J. He, W. Song, Achieving near-optimal traffic engineering in hybrid software defined networks, in: Proceedings of the IFIP NETWORKING Conference, 2015. [12] J. Vallet, O. Brun, Online ospf weights optimization in IP networks, Comput. Netw. 60 (2014) 1–12. [13] A. Elwalid, C. Jin, S. Low, I. Widjaja, Mate: MPLS adaptive traffic engineering, in: Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2001, 3, IEEE, 2001, pp. 1300–1309. [14] S. Kandula, D. Katabi, B. Davie, A. Charny, Walking the tightrope: responsive yet stable traffic engineering, ACM SIGCOMM Comput. Commun. Rev. 35 (2005) 253–264. [15] D. Applegate, E. Cohen, Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs, in: Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, ACM, 2003, pp. 313–324. [16] H. Wang, H. Xie, L. Qiu, Y.R. Yang, Y. Zhang, A. Greenberg, Cope: traffic engineering in dynamic networks, ACM SIGCOMM Comput. Commun. Rev. 36 (4) (2006) 99–110. [17] Y. Guo, Z. Wang, X. Yin, X. Shi, Incremental deployment for traffic engineering in hybrid sdn network, in: Proceedings of the IEEE International PERFORMANCE Computing and Communications Conference, 2015, pp. 1–8. [18] J. Zhang, K. Xi, M. Luo, H.J. Chao, Load balancing for multiple traffic matrices using sdn hybrid routing, in: Proceedings of the 2014 IEEE 15th International Conference on High Performance Switching and Routing, HPSR, IEEE, 2014, pp. 44–49.

198

Y. Guo et al. / Computer Networks 126 (2017) 187–199

[19] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, J. Turner, Openflow: enabling innovation in campus networks, ACM SIGCOMM Comput. Commun. Rev. 38 (2) (2008) 69–74. [20] S. Raza, Y. Zhu, C.-N. Chuah, Graceful network operations, in: Proceedings of the INFOCOM 2009, IEEE, IEEE, 2009, pp. 289–297. [21] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, LA, 1979. [22] M. Pióro, A. Szentesi, J. Harmatos, A. Jüttner, P. Gajowniczek, S. Kozdrowski, On open shortest path first related network optimisation problems, Perform. Eval. 48 (1) (2002) 201–223. [23] J. MacQueen, et al., Some methods for classification and analysis of multivariate observations, in: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1, Oakland, CA, USA., 1967, pp. 281–297. [24] J.L. Sobrinho, Algebra and algorithms for QoS path computation and hop-by-hop routing in the internet, in: Proceedings of the Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM 2001, 2, IEEE, 2001, pp. 727–735.

[25] H. Geng, X. Shi, X. Yin, Z. Wang, H. Zhang, Algebra and algorithms for efficient and correct multipath QoS routing in link state networks, in: Proceedings of the 2015 IEEE 23rd International Symposium on Quality of Service, IWQoS, IEEE, 2015, pp. 261–266. [26] S. Balon, G. Monfort, The Traffic Matrices and Topology of the Abilene Network, (http://totem.run.montefiore.ulg.ac.be/datatools.html). [27] B. Zhang, J. Bi, J. Wu, F. Baker, Cte: cost-effective intra-domain traffic engineering, ACM SIGCOMM Comput. Commun. Rev. 44 (2014) 115–116. [28] S. Uhlig, B. Quoitin, J. Lepropre, S. Balon, Providing public intradomain traffic matrices to the research community, ACM SIGCOMM Comput. Commun. Rev. 36 (1) (2006) 83–86.

Y. Guo et al. / Computer Networks 126 (2017) 187–199

199

Yingya Guo received the B.S. degree in computer science from Xiamen University, China, in 2013. She is currently a Ph.D. candidate at the Department of Computer Science and Technology, Tsinghua University. Her research interests include traffic engineering, routing optimization and Software Defined Networking.

Zhiliang Wang received the B.E., M.E. and Ph.D. degrees in computer science from Tsinghua University, China in 20 01, 20 03 and 20 06, respectively. Currently he is an Associate Professor in the Institute for Network Sciences and Cyberspace at Tsinghua University. His research interests include formal methods and protocol testing, next generation Internet, network measurement.

Xia Yin received the B.E., M.E. and Ph.D. degrees in computer science from Tsinghua University in 1995, 1997 and 20 0 0, respectively. She is a Full professor in Department of Computer Science and Technology at Tsinghua University. Her research interests include future Internet architecture, formal method, protocol testing and large-scale Internet routing.

Xingang Shi received the B.S. degree from Tsinghua University and the Ph.D. degree from The Chinese University of Hong Kong. He is now working in the Institute for Network Sciences and Cyberspace at Tsinghua University. His research interests include network measurement and routing protocols.

Jianping Wu received his B.S., M.S., and Ph.D. from Tsinghua University. He is a Full professor and director of Network Research Center, Ph.D. Supervisor of Department of Computer Science, Tsinghua University. From 1994, he has been in charge of China Education and Research Network (CERNET). He is a member of Information Advisory Committee, Office of National Information Infrastructure, Secretariat of State Council of China, and is also a vice president of Internet Society of China (ISC). His research interests include next generation Internet, IPv6 deployment and technologies, Internet protocol design and engineering.