Search

The past decades have seen a proliferation of middlebox deployment in various scenarios, including backbone networks and cloud networks. Since flows have to traverse specific service function chains (SFCs) for security and performance enhancement, it becomes much complex for SFC routing due to routing loops, traffic dynamics and scalability requirement. The existing SFC routing solutions may consume many resources (e.g., TCAM) on the data plane and lead to massive overhead on the control plane, which decrease the scalability of middlebox networks. Due to SFC requirement and potential routing loops, solutions like traditional default paths (e.g., using ECMP) that are widely used in non-middlebox networks will no longer be feasible. In this paper, we present and implement a scalable and flexible middlebox policy enforcement (SAFE-ME) system to minimize the TCAM usage and control overhead. To this end, we design the smart tag operations for construction of default SFC paths with less TCAM rules in the data plane, and present lightweight SFC routing update with less control overhead for dealing with traffic dynamics in the control plane. We implement our solution and evaluate its performance with experiments on both physical platform (Pica8) and Programming Protocol-independent Packet Processors (P4) based data plane, as well as large-scale simulations. Both experimental and simulation results show that SAFE-ME can greatly improve scalability (e.g., TCAM cost, update delay, and control overhead) in middlebox networks, especially for large-scale clouds. For example, our system can reduce the control traffic overhead by about 85% while achieving almost the similar middlebox load, compared with state-of-the-art solutions. [ABSTRACT FROM AUTHOR]

To meet the ever-increasing demands for high-quality network services, a software defined network (SDN) can support various virtual network functions (VNFs) using virtualization technology. Due to network dynamics, an SDN needs to be updated frequently to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new network configuration (e.g., target VNF placement and flow routing) based on the current workload, and then update the VNF placement and routing paths of the existing flows. However, due to massive VNF’s state migration and slow update of the flow table, unacceptable update delay may occur, especially in large or frequently changed networks. In this paper, we address the real-time network update, which jointly considers the optimization of the service function chain (SFC) update and the routing update. We propose the delay-satisfied NFV-enabled network update (DSNU) problem, and prove its NP-Hardness. We design an algorithm with bounded approximation factor to solve this problem. To further reduce the delay, we also design an efficient algorithm for the update scheduling. The experimental results show that our method can reduce the network update delay by about 86% compared with the previous network update methods while preserving a similar network performance, i.e., the VNF instance load ratio increases by less than 5%. [ABSTRACT FROM AUTHOR]

Large software defined networks use a cluster of distributed controllers to process flow requests from a massive number of switches. To cope with traffic dynamics, this paper studies a new problem of how to improve the residual capacity available at the controllers to handle request bursts experienced at the switches. While the total residual capacity is a constant under a given total capacity of all controllers and a given total workload from all switches, this paper considers the residual capacity available to each individual switch, which depends on how the switches are mapped to the controllers for management. We focus on how to maximize the minimum residual capacity available to any switch. The prior work either provides poor residual capacity or incurs heavy synchronization overhead by simulation results. This paper proposes a new method called indirect multi-mapping that achieves both high residual capacity and low synchronization cost. We formally define a non-linear integer optimization problem for max-min residual capacity under indirect multi-mapping. We then approximate the problem as two sub-problems: switch-controller mapping selection and weight assignment for each switch-controller mapping. We solve these sub-problems and formally analyze their approximate factor. We implement the proposed solution on an SDN testbed for experimental studies and use simulations for large-scale investigation. Our evaluation shows that indirect multi-mapping improves the minimum residual capacity by 49.8% on average and reduces the synchronization cost by 41.9-60.3% on average when compared with the alternatives. [ABSTRACT FROM AUTHOR]

In a software defined network, the controller needs to obtain/collect traffic measurement information (i.e., flow statistics) from switches for different applications, such as traffic engineering. Existing solutions seldom consider the per-switch cost, which may lead to heavy statistics collection cost (e.g., high CPU overhead) on some switches. Due to limited computing power on most commodity switches, heavy statistics collection cost on those switches may seriously interfere with the basic rule operations, especially when some switches need to deal with many new-arrival flows or update routes of existing flows. To address this challenge, we design and implement efficient flow statistics collection (FSC) with limited interference on the basic rule operations. We formally propose a cooperative flow statistics collection with per-switch cost constraint (CP-FSC) problem. We prove that the CP-FSC problem is NP-hard and present an efficient algorithm with approximation ratio 1/2, based on dynamic programming. To reduce the time complexity, a greedy-based algorithm with approximation ratio 1/3 is also presented. We implement the proposed FSC algorithms on our SDN platform. The experimental results and the extensive simulation results show 36%-59% performance improvement compared with the existing solutions. [ABSTRACT FROM AUTHOR]

Network Function Virtualization (NFV) is a new paradigm to enable service innovation through virtualizing traditional network functions. To construct a new NFV-enabled network, there are two critical requirements: minimizing server deployment cost and satisfying switch resource constraints. However, prior work mostly focuses on the server deployment cost, while ignoring the switch resource constraints (e.g., switch’s flow-table size). It thus results in a large number of rules on switches and leads to massive control overhead. To address this challenge, we propose an incremental server deployment (INSD) problem for construction of scalable NFV-enabled networks. We prove that the INSD problem is NP-Hard, and there is no polynomial-time algorithm with approximation ratio of $(1-\epsilon) \cdot \ln m$ , where $\epsilon $ is an arbitrarily small value and $m$ is the number of requests in the network. We then present an efficient algorithm with an approximation ratio of $2\cdot H(q\cdot p)$ , where $q$ is the number of VNF’s categories and $p$ is the maximum number of requests through a switch. We evaluate the performance of our algorithm with experiments on physical platform (Pica8), Open vSwitches, and large-scale simulations. Both experimental results and simulation results show high scalability of the proposed algorithm. For example, our solution can reduce the control and rule overhead by about 88% with about 5% additional server deployment, compared with the existing solutions. [ABSTRACT FROM AUTHOR]

Traffic measurement is very important for various applications, such as traffic engineering and attack detection, in software-defined networks. Due to limited resources (e.g., computing, memory) on SDN switches, sketches have been widely used for efficient traffic measurement. Meanwhile, multiple independent sketches are required for different application requirements, such as heavy hitter detection and flow size distribution estimation. To avoid the measurement redundancy, we configure which sketch(es) will measure flow on each switch. If traffic measurement is performed on each switch without considering network routing, due to traffic dynamics, it will cause massive measurement overhead on a switch, which may exceed the switch’s computing capacity. In this paper, we study the joint optimization of flow routing and sketch configuration in SDNs. We formulate this problem as an integer linear programming and prove its NP-hardness. To solve this problem, we propose a rounding-based offline algorithm and a primal-dual-based online algorithm for different application scenarios. To deal with bursty traffic, we also design an adaptive sampling mechanism for high-fidelity traffic measurement. We formally analyze the approximation performance or competitive ratio of the proposed algorithms. The extensive simulation results show the high efficiency of our proposed algorithms. For example, the online algorithm can improve the network throughput 30% compared with the state-of-the-art. [ABSTRACT FROM AUTHOR]

In a software-defined network (SDN), statistics information is of vital importance for different applications, such as traffic engineering, flow rerouting, and attack detection. Since some resources, e.g., ternary content addressable memory, SRAM, and computing capacity, are often limited on SDN switches, traffic measurements based on flow tables or sampling become infeasible. In fact, sketches provide a promising building block for filling this void by monitoring every packet with fixed-size memory. Although many efficient sketches have been designed, our analysis shows that existing sketch-based measurement solutions may suffer from severe computing overhead on switches especially under high traffic load that significantly interferes with switch’s basic functions, such as flow rule setup and modification. In this paper, we present CountMax, a lightweight and cooperative sketch for traffic measurement, which can achieve low-amortized processing overhead and tight estimation bounds, to track large flows in SDNs. We also discuss how to apply CountMax to support a variety of applications. We have implemented the proposed algorithm on our open switches. Testbed experiments and extensive simulation results show that CountMax consumes only 1/3–1/2 computing overhead and reduces the average estimation error by 20%–30%, compared with the existing solutions under the same memory size. [ABSTRACT FROM AUTHOR]

Software-defined networking (SDN) separates the control plane from the data plane to ease network management and provide flexibility in packet routing. The control plane interacts with the data plane through an interface that configures the forwarding tables, usually including a flow table and a group table, at each switch. Due to high cost and power consumption of ternary content addressable memory, commodity switches can only support flow/group tables of limited size, which presents serious challenge for SDN to scale to large networks. One promising approach to address the scalability problem is to deploy aggregate default paths specified by wildcard forwarding rules. However, the multi-dimensional interaction among numerous system parameters and performance/scalability considerations makes the problem of setting up the flow/group tables at all switches for optimal overall layout of default paths very challenging. This paper studies the joint optimization of flow/group tables in the complex setting of large-scale SDNs. We formulate this problem as an integer linear program, and prove its NP-hardness. An efficient algorithm with bounded approximation factors is proposed to solve the problem. The properties of our algorithm are formally analyzed. We implement the proposed algorithm on an SDN test bed for experimental studies and use simulations for large-scale investigation. The experimental results and simulation results show that, under the same number of flow entries, our method can achieve better network performance than the equal cost multipath while reducing the use of group entries by about 74%. Besides, our method can reduce the link load ratio and the number of flow entries by approximately 13% and 60% compared with DevoFlow with 10% additional group entries. [ABSTRACT FROM AUTHOR]

Traditional networks rely on aggregate routing and decentralized control to achieve scalability. On the contrary, software-defined networks achieve near optimal network performance and policy-based management through per-flow routing and centralized control, which, however, face scalability challenge due to: 1) limited ternary content addressable memory and on-die memory for storing the forwarding table and 2) per-flow communication/computation overhead at the controller. This paper presents a novel hybrid switching (HS) design, which integrates traditional switching and software-defined networking (SDN) switching for the purpose of achieving both scalability and optimal performance. We show that the integration also leads to unexpected benefits of making both types of switching more efficient under the hybrid design. We also design the general optimization framework via HS and propose an approximation algorithm for load-balancing optimization as a case study. Testing and numerical evaluation demonstrate the superior performance of HS when comparing with the state-of-the-art SDN design. [ABSTRACT FROM AUTHOR]

Software defined networking (SDN) is becoming increasingly prevalent for its programmability that enables centralized network configuration and management. With the growth of SDNs, a cluster of controllers cooperatively manages more and more switches/flows in a network to avoid the single-controller congestion/failure and improve the control-plane robustness. Under the architecture with multiple controllers, it is expected to minimize the maximum response time on these controllers to provide better QoS for users. To achieve this target, two previous methods are mainly used, the static scheme and the dynamic scheme. However, these methods may lead to an increase of the control-plane communication overhead/delay. In this paper, we propose to minimize the maximum response time on controllers through flow redirecting, which is implemented by installing wildcard rules on switches. We formulate the minimum controller response time problem, which takes the flow-table size and link capacity constraints into account, as an integer linear program, and prove its NP-Hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN testbed. The testing results and extensive simulation results show that our proposed algorithm can reduce the maximum controller response time by about 50%–80% compared with the static/dynamic methods under the same controller cost, or reduce the number of controllers by 30% compared with the dynamic method while preserving almost the same controller response time. [ABSTRACT FROM PUBLISHER]

In a software-defined network (SDN), the control plane needs to frequently collect flow statistics measured at the data plane switches for different applications, such as traffic engineering, QoS routing, and attack detection. However, existing solutions for flow statistics collection may result in large bandwidth cost in the control channel and long processing delay on switches, which significantly interfere with the basic functions, such as packet forwarding and route update. To address this challenge, we propose a cost-optimized flow statistics collection (CO-FSC) scheme and a cost-optimized partial flow statistics collection (CO-PFSC) scheme using wildcard-based requests, and prove that both the CO-FSC and CO-PFSC problems are NP-hard. For CO-FSC, we present a rounding-based algorithm with an approximation factor $f$ , where $f$ is the maximum number of switches visited by each flow. For CO-PFSC, we present an approximation algorithm based on randomized rounding for collecting statistics information of a part of flows in a network. Some practical issues are discussed to enhance our algorithms, for example, the applicability of our algorithms. Moreover, we extend CO-FSC to achieve the control link cost optimization FSC problem, and also design an algorithm with an approximation factor $f$ for this problem. We implement our designed flow statistics collection algorithms on the open virtual switch-based SDN platform. The testing and extensive simulation results show that the proposed algorithms can reduce the bandwidth overhead by over 39% and switch processing delay by over 45% compared with the existing solutions. [ABSTRACT FROM PUBLISHER]

Due to flow dynamics, a software defined network (SDN) may need to frequently update its data plane so as to optimize various performance objectives, such as load balancing. Most previous solutions first determine a new route configuration based on the current flow status, and then update the forwarding paths of existing flows. However, due to slow update operations of Ternary Content Addressable Memory-based flow tables, unacceptable update delays may occur, especially in a large or frequently changed network. According to recent studies, most flows have short duration and the workload of the entire network will vary significantly after a long duration. As a result, the new route configuration may be no longer efficient for the workload after the update, if the update duration takes too long. In this paper, we address the real-time route update, which jointly considers the optimization of flow route selection in the control plane and update scheduling in the data plane. We formulate the delay-satisfied route update problem, and prove its NP-hardness. Two algorithms with bounded approximation factors are designed to solve this problem. We implement the proposed methods on our SDN test bed. The experimental results and extensive simulation results show that our method can reduce the route update delay by about 60% compared with previous route update methods while preserving a similar routing performance (with link load ratio increased less than 3%). [ABSTRACT FROM PUBLISHER]

To explore the advantages of software defined network (SDN), while preserving the legacy networking systems, a natural deployment strategy is to deploy a hybrid SDN incrementally to improve the network performance. In this paper, we address two technical challenges: an incremental deployment strategy and a throughput-maximization routing, for deploying a hybrid network incrementally. For incremental deployment, we propose a heuristic algorithm for deploying a hybrid SDN under the budget constraint, and prove the approximate factor of 1- \frac 1e . For throughput-maximization routing, we apply a depth-first-search method and a randomized rounding mechanism to solve the multi-commodity h -splittable flow routing problem in a hybrid SDN, where h\ge 1 . We also prove that our method has approximation ratio O\left(\frac 1\log N\right) , where N is the number of links in a hybrid SDN. We then show, by both analysis and simulations, that our algorithms can obtain significant performance gains and perform better than the theoretical worst-case bound. For example, our incremental deployment scheme helps to enhance the throughout about 40% compared with the previous deployment scheme by deploying a small number of SDN devices, and the proposed routing algorithm can improve the throughput about 31% compared with ECMP in hybrid networks. [ABSTRACT FROM AUTHOR]