Abstract: Software-Defined Networking (SDN) brings excellent opportunities to improve network performance by flexible flow control with a centralized network view. However, due to budget constraints and technique limitations, ISPs can upgrade only a limited number of conventional switches in real backbone networks to SDN devices at one time. In this paper, we propose one heuristic scheme to increase the deployment of SDN switches in hybrid SDNs, which are composed of conventional and SDN switches. Our scheme works for two different cases: (1) maximizing the network control ability with a given upgrading budget constraint, and (2) minimizing the upgrading cost to achieve the best network control ability. The results show that our scheme can achieve 95\% of the number of flows controlled with only 10% upgrading cost. We evaluate our scheme in two topologies, the ISP 1755 and the ISP 3967 from the real network..

Key words: Software-Defined Networking, Switch deployment, Flow control, Network management.

1 Introduction

Software-Defined Networking (SDN) technique is widely used in recent years, and it separates the network control plane from the packet forwarding plane and provides applications with an abstracted centralized view of the distributed network state [1]. Microsoft, Google, Amazon and other companies deploy their SDNs and obtain a lot of benefits [2]. However, in the global Internet environment, the deployment of SDN requires an extended period. Therefore, the hybrid SDNs, which are composed of SDN devices and traditional network equipment, will exist during a long time [3]. Network operators must be able to incrementally deploy SDN switch in order to control and manage the network more flexibly.

In BTSDN [4], it states that the SDN switches and the current Internet can coexist with each other, and the SDN networks can be incrementally deployed to the Internet.

Generally speaking, the network upgrade is a complex operation. ISPs consider not only the budget constraints but also the normal network operation [5][6]. Thus, it is not practical to upgrade all network devices (e.g., switches and routers) in real networks to SDN devices at one time. Therefore, ISPs should trade off financial consideration and the network control ability (NCA) to deploy\footnote{In this paper, we use deploy and upgrade interchangeably.} SDN switches in existing networks [7]. To achieve the efficient upgrade, we are faced with two real problems: (1) given the requirement to improve NCA, how to determine the number and the location of nodes in a network to be upgraded to SDN switches? (2) given a limited number of SDN switches, how to place them to achieve the maximum NCA improvement?

In order to solve the problem of SDN switch incremental deployment, %Intelligent Timeout Master (ITM) \cite{zhu2015intelligent}

some studies \cite{Sugam-18}\cite{guo2015incremental} try to formulate it as a dynamic routing problem, which minimizes the maximum link utilization by dispatching the controllable flow to pass through at least one SDN switch. However, those schemes may increase the path stretch.

Alternatively, some studies [1][8] aims to solve the resilience issue in a hybrid SDN network by providing mechanisms to redirect traffic and recover from any single link failure. Besides guaranteeing reachability in the presence of single link failures, the proposed approaches also try to avoid having congested links in the post-recovery network. But those schemes are not applicable to real networks because they cause overload on the SDN controller.

In this paper, we propose a heuristic scheme to solve the problem of incremental deployment SDN switch. First, we formulate an optimization problem to achieve the maximum NCA with little upgrading cost. Due to the high complexity of the problem, we transform it into two problems with real constraints: Max-NCA problem, which aims to maximize the NCA improvement with a given upgrading cost, and Min-Cost problem, whose objective is to deploy the minimum number of SDN switches to achieve the maximum NCA improvement in a network. We prove that the two problems are NP-hard, and give a heuristic algorithm to solve the two problems with low complexity. We evaluate the performance of our scheme in two existing networks topologies, the ISP 1755 and the ISP 3967 from the Rocketfuel [10]. Simulation results show that our scheme is much better than the baseline scheme and is comparable to the near-optimal solution. Results from the simulations show that our scheme can achieve 95\% NCA improvement with only 10\% upgrading cost.

The rest of the paper is organized as follows. The related works are discussed in section 2. Section 3 describes the problem and formulates the problem as an optimization problem. Section 4 transforms the optimization problem to two sub-problems with different objectives and constraints. We prove that the two sub-problems are NP-hard, and also present a heuristic scheme to solve the two sub-problems. In Section 5, by comparing with the previous algorithms, our scheme can achieve better performance with few footprints. %The results show that our scheme can achieve 95\% of the number of flows be controlled with only 10\% upgrading cost.

In Section 6, we conclude the paper..

2 Related Works

Some existing works propose deploying SDN switches to achieve network security, load balancing and traffic scheduling[9][10][12]. Dan Levin et al. [13] deploy SDN switches in enterprise networks using VLANs and switch ports to enable each flow to go through at least one SDN switch. The scheme is limited by the number of VLANs, and needs to set the switch ports. In [11], the objective of the authors is to develop a SDN deployment scheme that can adaptively and dynamically manage traffic in a network to accommodate different traffic patterns. The solution has high complexity and is not feasible to use in real networks. Chu et al. [9] propose an approach to guarantee traffic reachability in the presence of any single link failure. By redirecting traffic on the failed link to SDN switches through pre-configured IP tunnels, the proposed approach is able to react to the failures fast. With the help of coordination among SDN switches, it is able to explore multiple backup paths for the failure recovery. However, it increases the controller burden for pre-computed and wastes the flow table entries for pre-configured.

In [8], the authors focus on the hybrid SDN network scenario and discuss about the migration algorithms from the perspective of traffic engineering in an ISP network. It mainly concentrates on searching for an optimized migration sequence of the routers in the traditional IP network to minimize the maximum link utilization. But it did not give a specific SDN switch deployment plan. In [7], Chu et al. summarize different types of hybrid SDN networks including topology-based, service-based and class-based hybrid SDN networks. They show a number of use cases in which hybrid models can mitigate the respective limitations of traditional and SDN approaches, providing incentives to (partially) transition to SDN.

A premise is that we do not modify the flow path of traditional networks. Hence, there is not additional path stretch in our scheme. We deploy the minimum number of SDN switches within budget and achieve almost all of the flows go through at least one SDN switch. The results show that our scheme can control almost all the flows by deploying only a small number of SDN switches..

3 Problem Formulation

3.1 System call

We assume that the SDN forwarding elements are a subset of the nodes in the network. The rest of the nodes in the network run some standard hop-by-hop routing protocol like OSPF [1][14]. Using the information collected by each SDN switch, the SDN controller is able to peer the entire network and be aware of the workload on each link as well as the traffic volume between different source-destination pairs [9]. The cost of incremental deployment SDN switch is related to the switch port number, the traffic processing speed, and the capacity of TCAM.

3.2 Notation

We formulate a network as a graph G= (V,E ), where V is the set of nodes, and E is the set of links. Let F denote the set of traffic flows. We use v_i to represent a node in the network, l_{ij} to represent the link between nodes v_i and v_j. Let C_{ij} denote the capacity of link l_{ij}, andf^k_{ij} (f^k_{ij}\in \mathcal{F}) be the size of the k-th flow on link l_{ij}. Let the source and destination nodes of flow f^k_{ij} be s^k and d^k. We use F_{v_i} to denote the set of flows passing through node v_i. The notations for this paper are listed in Table 1.

3.3 Objective function

The goal of the problem is to improve the network control ability (NCA) by upgrading switches at little cost. Typically, the NCA of a network is associated with the number of controlled flows in the network. In [9], the authors show that the hybrid SDN network can achieve fast recovery and guarantee reachability from any single link failure if the flows pass through at least one designated SDN switch. In [13][15], it shows that it becomes possible to operate the most of an enterprise network for every source-destination path that includes at least one SDN switch. Therefore, the flow can be monitored or flexibly scheduled if it traverses at least one SDN switch in hybrid networks. In other words, the more flows can be controlled, the more NCA can be improved. To quantify the performance of a network, we introduce some definitions below.

Definition 1. Flow control ability: Since an SDN switch can flexibly control all flows that traverse it \cite[4][6], we assume that if node $v_i$ is updated to an SDN switch (e.g., \delta_i = 1), the flow control ability of it equals to the total size of flows that pass through the node; otherwise (e.g., \delta_i = 0), its flow control ability is zero. For node v_i (v_i in V), the flow control ability of it is formulated as follows:

Definition 2. Network control ability (NCA): The network control ability is defined as the flows that can be flexibly managed by deploying SDN switches in the network. In other words, the network control ability is the sum of the flow control ability of nodes in the network [17]. Therefore, for Q, a sub-set of V, we have its network control ability:

Definition 3. Upgrading cost: The upgrading cost of a network is the total cost for upgrading conventional switches to SDN switches in the network. For switch v_i, its cost depends on many factors, such as p_{i}, the number of forwarding ports in the node, and s_{i}, the traffic processing speed in the node [18]. For simplicity, we use the degree of the node in topology to represent the number of forwarding ports. Moreover, we assume that s_i is linear with the size of flow that pass through the SDN switch v_i. We assume the cost of switch v_i is c_i, c_i=q(p_{i}, s_{i})=a_1\cdot p_i +a_2\cdot s_i, where a_1 and a_2 are constant. Therefore, the upgrade cost of the network is formulated as

3.4 Problem formulation

The problem of the incremental switch deployment for a hybrid SDN is formulated as below:

Constraint (5b) ensures that the cost of a feasible deployment is less than or equal to a given upgrading budget. Equation (5c) indicates that the total size of incoming flows of a node equals to the total size of outgoing flows of the node except the source and destination nodes. Equation (5d) represents the set of nodes which are upgraded to SDN switches. Constraint (5e) states that the traffic load of a link can not exceed its capacity. Equation (5f) describes the flow control ability of a node, and it only contains the forwarding and generating traffic of the node rather than the received traffic as the destination node, because the node only can schedule the forwarding and generating traffic.

3.5 Complexity analysis and near-optimal solution

Since the cost function of a switch, , is non-linear to and the function is a non-linear function [19]. Considering variable is binary, the proposed model is an Integer Non-Linear Programming problem [20], and its complexity is , where M is the number of nodes in the network. Typically, a backbone network consists of a large number of nodes [21]. For example, the topologies of ISP 1755 and ISP 3967 are composed of more than 320 nodes [10]. Thus, it is not feasible to solve the problem by the simple method of brute force enumeration.

分享让更多人看到