A Study Of Scalability Problem In The Data Plane Of Software Defined Networks

The growth of Internet services has promoted the popularity of many large-scale data-intensive applications(e.g.,video conferences,cloud services,and financial data analysis).As a result,large-scale networks are increasingly experiencing burst flows and the traditional network architecture exposes three major flaws:complex architec-ture,high resource redundancy,and limited network management.Thus,the concept of Software Defined Networking(SDN)came into being.By separating the control plane and the data plane,SDN can effectively simplify the network architecture,im-prove resource utilization,and achieve fine-grained network management.Software Defined Networking is a reactive flow forwarding architecture.The control plane computes the path based on the newly-arrived flow information and the switches forward the traffic according to the flow entries.In the actual network,on the one hand,as the network scale continues to expand,the reactive flow forwarding model may lead to huge communication load between the data plane and the control plane.Moreover,it may increase the delay of traffic forwarding in the data plane.on the other hand,the flow-table size in the data plane is very limited.If each flow needs to consume a large number of flow entries,it may violate the flow-table size constraints.In other words,the reactive flow forwarding model and limited flow-table size bring great challenges to the scalability in the data plane of the software defined networks.Therefore,this dissertation is dedicated to solving the scalability problem in the data plane of software defined networks.The main research contents and contributions of this dissertation are as follows:1.SDN separates the control plane from the data plane to ease network man-agement and provide flexibility in packet routing.The control plane interacts with the data plane through an interface that configures the forwarding tables,usually in-cluding a flow table and a group table,at each switch.Due to high cost and power consumption of Ternary Content Addressable Memory(TCAM),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 scala-bility problem is to deploy aggregate default paths specified by wildcard forwarding rules.However,the multi-dimensional interaction among numerous system parame-ters 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 chal-lenging.This dissertation 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 approxi-mation factors is proposed to solve the problem.The properties of our algorithm are formally analyzed.We implement the proposed algorithm on an SDN testbed for ex-perimental 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 ECMP while reducing the use of group entries by about 74%.Besides,our method can reduce link load ratio and the number of flow entries by approximately 13%and 60%compared with DevoFlow with 10%additional group entries.2.Fine-grained flow management is useful in many practical applications,e.g.,resource allocation,anomaly detection and traffic engineering.However,it is diffi-cult to provide fine-grained management for a large number of flows in SDNs due to switches' limited flow-table size.While using wildcard rules can reduce the num-ber of flow entries needed,it cannot fully ensure fine-grained management for all the flows without degrading application performance.In this dissertation,we design and implement hybrid rule placement for fine-grained flow management(HiFi).HiFi achieves fine-grained management with a minimal number of flow entries through taking a two-step approach:wildcard entry installment and application-specific exact-match entry installment.How to optimally install wildcard and exact-match flow en-tries,however,is intractable.Therefore,we design approximation algorithms with bounded factors to solve these problems.We consider how to achieve network-wide load balancing via fine-grained flow management as a case study.Both experiment on a testbed built with open virtual switches and extensive simulation show that HiFi can reduce the number of required flow entries by about 45%-69%and reduce the con-trol overhead by about 28%-50%compared with the state-of-the-art approaches for achieving fine-grained flow management.3.The past decades have seen a proliferation of middlebox deployment in var-ious networks,including backbone networks and data centers.Since network 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 con-sume 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 dissertation,we present and implement a scalable and flexible middle-box 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 rout-ing 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 Open vSwitch(OVS),as well as large-scale sim-ulations.Both experimental and simulation results show that SAFE-ME can greatly improve scalability(e.g.,TCAM cost,update delay,and control overhead)in middle-box networks.For example,our system can reduce the control traffic overhead by about 83%while achieving almost the similar middlebox load,compared with state-of-the-art solutions.