- Email: [email protected]

Contents lists available at ScienceDirect

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

Traﬃc engineering in hybrid SDN networks with multiple traﬃc 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: Traﬃc engineering Software Deﬁned Networking Multiple traﬃc matrices Routing optimization

a b s t r a c t Traﬃc engineering (TE) is an eﬃcient tool for optimizing traﬃc routing and balancing the ﬂows in networks. Traﬃc is dynamic, previous TE optimization over a single traﬃc matrix (TM) have some limitations, because a single TM can have big measurement errors and is insuﬃcient to depict the traﬃc ﬂucuations. Thus, we consider using multiple TMs to overcome these limitations. With the emergence of Software Deﬁned Networking (SDN), we can route ﬂows more ﬂexibly and better balance the ﬂows over multiple TMs. However, due to the diﬃculties 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 ﬁrst 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 oﬄine 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 traﬃc 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, traﬃc 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 traﬃc delivered over networks. Therefore, how to avoid network congestions and achieve load balance of traﬃc have attracted worldwide attention. As an eﬃcient tool for balancing the ﬂows in a network, traﬃc engineering (TE) adjusts the routing conﬁguration of a network to control how traﬃc 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 traﬃc 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 oﬄine over a single traﬃc matrix (TM) based on shortest path routing protocols [1]. However, the optimization of routing over a single TM has limitations. First, due to the diﬃculty of measuring TMs accurately, considering only a single TM may lead to errors when we optimize routing in TE. Second, the traﬃc in a network is dynamically changing all the time [2]. Thus, a single TM is insuﬃcient to depict the frequent ﬂuctuations of the traﬃc 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 traﬃc 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 traﬃc better, because multiple TMs cannot only be robust to the errors in measurement, but also depict the ﬂuctuations of dynamic traﬃc. In previous studies of TE, a common method for dealing with multiple TMs involves optimizing the OSPF link weights oﬄine 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 ﬂuctuating traﬃc demands. Software Deﬁned 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 ﬂexibly control the splitting ratio of the traﬃc to any outgoing link of the SDN switches. To achieve high network performance over multiple TMs, TE may require frequently adjusting the routing conﬁguration to accommodate the changing traﬃc. SDN can handle the routing over dynamic traﬃc eﬃciently and schedule the ﬂows ﬂexibly 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 ﬂows 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 ﬂexibility of SDN with the robustness of Interior Gateway Protocols (IGP), such as OSPF. Studies in [8–11] are previous traﬃc engineering studies in hybrid SDN network. However, these studies are routing optimization under a single TM and ignore the ﬂuctuations of the traﬃc 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 oﬄine weight optimization for legacy nodes with online splitting ratio optimization for a small proportion of SDN nodes in order to accommodate changeable traﬃc. The method for dealing with multiple TMs in oﬄine weight optimization is also different from that employed in previous studies. To be speciﬁc, we ﬁrst consider clustering all the historical TMs by using a data mining algorithm and we then compute the weight coeﬃcient 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 trafﬁc 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 oﬄine 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 traﬃc 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 classiﬁed into two main categories: oﬄine and online. In the oﬄine category, the topology and TMs are known in advance and TMs remain static. The routing conﬁguration is computed ofﬂine based on historical traﬃc information. The traﬃc is then routed according to the computed routing conﬁguration [1,2]. In the online category, traﬃc is changing and routing has to be optimized in a dynamic scenario. Vallet and Brun [12] optimized routing according to the changing traﬃc 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 ﬂooding 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 traﬃc ﬂows more ﬂexibly 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 traﬃc can be routed more ﬂexibly and eﬃciently. There are three main methods for dealing with changing traﬃc in MPLS network. The ﬁrst method involves optimizing routing in an oﬄine manner over multiple TMs. A previous study [3] considered the minimization of the expected cost of multiple TMs. They aimed to ﬁnd 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 ﬂows and reacted to network failures or unexpected traﬃc demands eﬃciently. However, it increased the overheads when disseminating information to probe the link state. The third method for dealing with changing traﬃc is oblivious routing, which considers all possible TMs but degrades the performance for individual TMs. In [15], Applegate and Cohen discussed how to route ﬂows 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 eﬃcient method for routing the ﬂows in a network. Microsoft [4] and Google [5] have built inter-datacenter wide area networks (WANs), which fully utilized the ﬂexibility 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 Deﬁnition 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 ﬂexibility of centralized routing with the robustness of distributed routing to balance the load and managed the network more eﬃciently, however, they did not take multiple TMs into considerations. In [8], Agarwal et al. obtained traﬃc demand matrices by measuring traﬃc information online. They optimized the routing for SDN nodes by optimizing the splitting ratio of traﬃc, but they did not consider OSPF weight optimization. In summary, we can utilize SDN to route the ﬂows more ﬂexibly 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 oﬄine TE algorithms. In a hybrid SDN network, splitting ratio for SDN nodes and OSPF weight setting both inﬂuence the routing of traﬃc. In online traﬃc 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 oﬄine OSPF weight setting (Ofﬂine method) over multiple TMs. With the oﬄine weight optimization, we can optimize the routing for legacy nodes; with the online splitting ratio optimization, we can adjust the routing of traﬃc for SDN nodes ﬂexibly with changing traﬃc. In this manner, we can balance the ﬂows 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 openﬂow [19]. The centralized external SDN controller controls the forwarding behavior of SDN elements. It distributes the ﬂow entries into the ﬂow 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 Traﬃc demands from node u to node v in Di The weight coeﬃcient 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 ﬂexibly 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 ﬁrst measures the network traﬃc information based on the ﬂow statistical messages from the SDN elements or by collecting load information with Simple Network Management Protocol (SNMP). The routing conﬁguration is then optimized by our proposed routing optimizer. Finally, we can deploy the computed routing conﬁgurations 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 ﬁrst give deﬁnitions 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 Deﬁnition. Before formulating the problem, we give deﬁnitions 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 traﬃc demands from u to v (i = 1, 2, . . . , n, u, v ∈ V). Each TM Di is assigned a positive weight coeﬃcient ri (i = 1, 2, . . . , n), which reﬂects the frequency of its corresponding traﬃc 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 traﬃc 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 traﬃc 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 ﬂows 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 ﬂow graph. C1 , C2 , . . . , Cn are SDN nodes. All ﬂows are unit ﬂows.

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 traﬃc destined to node t ﬂowing on the ingress or egress links e of SDN nodes with the weight setting ω and TM Di . Eq. (2) denotes that the traﬃc ﬂowing into the SDN node pluses the traﬃc that originates from this node equals the traﬃc ﬂowing out of this node. Eq. (2) is the ﬂow conservation constraint and this equation also implies that the traﬃc demand is met. Inequality (3) indicates that the total ﬂows 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 ﬂow 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 ﬁnd 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 deﬁnitely an NP-hard problem. Therefore, we should ﬁrst 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 ﬂow 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 ﬂow graph [22] for TE in a hybrid SDN network. s and t are the source and destination nodes, respectively. The ﬂows generated from node s are all unit ﬂows. 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 ﬂow 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 ﬂows 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 ﬁnd that the MLU is 1 and the ﬂow from s to t is q. Conversely, if the ﬂow from s to t is q, then there should be q unit ﬂows originated from s. Since the MLU is 1, then for the ﬂow arrives at Ci , i = 1, 2, . . . , q, the ﬂow should be evenly split, the ﬂow on the link (Ci , xj ) should be exactly 1/3 and for any xj , Ci always satisﬁes xj ∈ Ci and ∀i, j, i = j, Ci ∩ C j , . . . = ∅. For if Ci ∩ C j = xm , then the ﬂow 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 conﬁguration in a hybrid SDN network. In this section, we ﬁrst 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 ﬁxed, we optimize the splitting ratio of the ﬂows online for multiple TMs (splitting ratio optimizer). Finally, we obtain a near optimal routing conﬁguration. 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 traﬃc demand matrices D = {Di }, i = 1, . . . , n that reﬂect the variations in traﬃc 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 ﬁxed 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 ﬁrst 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 ﬂooding 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 ﬂexible manner to accommodate traﬃc ﬂuctuations. Therefore, we combine the oﬄine 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 coeﬃcients 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 coeﬃcients 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 oﬄine over the expected TM for ﬁnd-

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 | deﬁnes 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 traﬃc patterns, we aim to obtain an expected TM which reﬂects the overall traﬃc patterns in a day. More speciﬁcally, we ﬁrst 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 coefﬁcient reﬂects the frequency of its corresponding traﬃc 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 traﬃc under different traﬃc patterns by linearly combining the TMs with the weight coeﬃcients: exp_T M = ni=1 ri Di . 5.1.2. SDN_placement We ﬁrst 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 satisﬁed (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. Traﬃc clustered by K-means. This ﬁgure shows the traﬃc volume varies with the time of one day in CERNET. The traﬃc is measured every ﬁve 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 = ﬂoydwarshall (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 ﬁnd a single weight setting works well under multiple TMs D. We employ the reﬁned local search heuristic algorithm described in [1] to search for the optimal weight setting oﬄine. 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 ﬁxed, we optimize the splitting ratio of the SDN nodes in Algorithm 4. In this algorithm, we ﬁrst 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 speciﬁcally, 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 deﬁne 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 veriﬁed in Section 5.3. Given these DAGs, we can form Linear Programs (LP) based on the multi-commodity ﬂow constraints (2)–(7) (lines 8– 10) and solve them with the LP solver CPLEX (line 12). Finally, we obtain the traﬃc on each link and MLU. To make a summary, in the proposed routing optimizer, we combine oﬄine weight optimization with online splitting ratio optimization. We optimize the weight setting oﬄine 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 ﬁrst 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 ﬂoydwarshall, neighbor_search functions are both O(|V|3 ), so the complexity of the oﬄine 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 deﬁne 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 deﬁned on the set S, and t is a node in S. We deﬁne 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 reﬂexive: 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 ﬁrst 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 satisﬁed. 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 reﬂexive,anti-symmetric and transitive. According to the previous proof, we can observe that is reﬂexive,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 satisﬁes 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 deﬁne 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 satisﬁes 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 ﬂows. 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. Deﬁnition 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 ﬂow on each link with D1 is no more than the ﬂow 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 traﬃc. 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. Traﬃc matrices The TMs datasets for Abilene are provided by the TOTEM project [26]. The TMs are measured every ﬁve 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 ﬁve 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 ﬁfteen 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 ﬁrst 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 ﬂat 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 beneﬁt 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 ﬁrst cluster eight representative TMs based on one-day historical TMs. We then use our proposed algorithm to compute the weight setting oﬄine 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 ﬁve minutes for Abilene, CERNET and ﬁfteen minutes for GEANT) to demonstrate the effectiveness of our algorithm. We denote our routing optimizer framework as OORO (Online Oﬄine Routing Optimizer). OSPF denotes the algorithm described in [2]. The weight setting in [2] is optimized on the eight clustered TMs of the ﬁrst 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 ﬁrst 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 ﬁnd that OORO obtains a lower MLU on one-day traﬃc 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 traﬃc. The traﬃc splitting ratio cannot be adjusted ﬂexibly 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 ﬂexibly adjusted with dynamic traﬃc 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 traﬃc patterns. Therefore, our algorithm outperforms Upper on average. The Online method proposed in [8] only optimizes the splitting ratio of the traﬃc for SDN nodes, but ignores the optimization of routing for trafﬁc through OSPF nodes. In hybrid SDN network, both the routing for the traﬃc through OSPF nodes and the routing for the traﬃc through SDN nodes affect the performance of traﬃc 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 oﬄine 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 traﬃc pattern (OORO(single)) may not perform well over other traﬃc patterns. In our proposed method, we optimize the routing over different trafﬁc 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 traﬃc 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

Oﬄine

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 oﬄine 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 oﬄine and online parts of the algorithm both increase with the increasing of topology size. We can ﬁnd that the oﬄine weight optimizer takes the most time and the online splitting ratio optimizer in the framework works eﬃciently with the changing of traﬃc 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 traﬃc. 7. Conclusion In hybrid SDN network, previous studies mainly focus on optimizing the routing over a single TM. However, the traﬃc is uncertain and changeable. It is diﬃcult to optimize the routing of TE under dynamic traﬃc. Compared with a single TM, multiple TMs can better represent the dynamic traﬃc. 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 oﬄine and online over multiple TMs. Through extensive experiments, we can ﬁnd 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 traﬃc 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 traﬃc 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 deﬁned 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 deﬁned 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, Traﬃc engineering in software deﬁned networks, in: Proceedings IEEE INFOCOM, IEEE, 2013, pp. 2211–2219. [9] Y. Guo, Z. Wang, X. Yin, X. Shi, J. Wu, Traﬃc 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 traﬃc engineering in hybrid software deﬁned 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 traﬃc 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 traﬃc engineering, ACM SIGCOMM Comput. Commun. Rev. 35 (2005) 253–264. [15] D. Applegate, E. Cohen, Making intra-domain routing robust to changing and uncertain traﬃc 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: traﬃc 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 traﬃc 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 traﬃc 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, Openﬂow: 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 ﬁrst related network optimisation problems, Perform. Eval. 48 (1) (2002) 201–223. [23] J. MacQueen, et al., Some methods for classiﬁcation 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 eﬃcient 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 Traﬃc Matrices and Topology of the Abilene Network, (http://totem.run.monteﬁore.ulg.ac.be/datatools.html). [27] B. Zhang, J. Bi, J. Wu, F. Baker, Cte: cost-effective intra-domain traﬃc engineering, ACM SIGCOMM Comput. Commun. Rev. 44 (2014) 115–116. [28] S. Uhlig, B. Quoitin, J. Lepropre, S. Balon, Providing public intradomain traﬃc 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 traﬃc engineering, routing optimization and Software Deﬁned 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, Oﬃce 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.

Copyright © 2018 KUNDOC.COM. All rights reserved.