Forwarding Rule Configuration And Flow Scheduling In Software-defined Networks

To provide high reliability,legacy networks have adopted fully distributed architectures by design,in which,the network's control plane is tightly coupled with its data plane and distributed among devices.With networks scaling up,usage scenarios and traffic types becoming more and more complicated,such a design comes up with many shortcomings on network management,function customization,and protocol deployment,and prevents the network from evolving.To overcome these issues,recent trends toward Software Defined Networking(SDN)seem to provide a promising solution.By decoupling the network's control plane from forwarding devices and aggregating it at a logical controller to build a global network operating system,SDN provides high-level application program interfaces(APIs)for management.With these APIs,operators are able to “ define ” their own networks by writing software applications.Because of these advantages,SDN has attracted a lot of attention from both industry and academia,and is being deployed in many networks including these of enterprises,service providers,and data centers.As an emerging technology,to let SDN work well,many challenges must be addressed.For instance,on configuring forwarding rules as well as scheduling flows,current SDN meets with three problems: 1)high-speed OpenFlow switches suffer from limited concrete flow table size,which seriously restricts SDN's employments;2)as an asynchronous system,SDN is afflicted by inconsistent forwarding and transient congestion during updates;3)today's data centers require application-aware flow scheduling yet existing centralized solutions can not scale.In this dissertation,we focus on these issues and propose a couple of suggestions,respectively.1)Towards efficient snapshot and incremental flow table aggregationTo address the problems caused by small flow table sizes,we introduce an effective snapshot algorithm,FFTA,along with its incremental supplement,iFFTA,for flow table aggregation.Given a set of forwarding rules,FFTA analyzes their redundancy then aggregates them into fewer entries effectively.Once the original rules are updated,iFFTA incorporates the update immediately by leveraging the order-independent relationship and structure of rules,so that no inconsistency would occur.Such a solution guarantees that the flow table's forwarding semantics is unchanged;and meanwhile,it is easy to be implemented as an optional service residing in SDN controllers without modifying the OpenFlow protocol.Extensive experiments demonstrate that the proposed solution significantly outperforms prior art on both efficiency and effectiveness.2)Consistent and congestion-free network reconfiguration in SDNDuring a network's update process,in-flight packets might misuse different versions of rules,and “hot” links could be overloaded due to the unplanned updating order.To avoid inconsistent forwarding,we propose a simple yet generic solution based on the original two-phase-commit update proposal,which suggests each packet to carry with a version number along its journey.By employing well-designed wildcard rules for the matching of version number,we simplify the update procedure,make a stream of updates easy to be processed in parallel,and avoid all unwanted rule-space overheads.To deal with transient congestions,we propose a customizable update planner,which introduces generic linear programming models to formulate user-specified requirements and the update planning problem.By solving customized models,the planner is able to arrange updates according to a large fraction of user requirements while avoiding transient congestions.Simulation results confirm the flexibility of our solutions and imply that they outperform prior art.3)Application-aware flow scheduling in a decentralized mannerTo avoid performance bottlenecks met by centralized proposals,we design efficient,decentralized solutions for the schedule of coflows(aka,application-aware flow scheduling).Respecting to the diversity among applications,different data centers would pursue distinct scheduling goals,among which,two types are most common: i)minimizing the average coflow completion time to optimize data center utilizations,if applications run latency-insensitive jobs;ii)minimizing the ratio of deadline-missed coflow to optimize data center revenues in case applications provide online time-sensitive services.In this dissertation,we analyze the general model of coflow scheduling.Inspired by the characteristic of data center network and insights borrowed from the well-known concurrent open shop scheduling problem,we propose two decentralized coflow scheduling solutions,named D-CAS and D2-CAS.By decoupling the schedule computation from the controller and distributing it among end hosts,our solutions eliminate bottlenecks and are highly reliable.Simulation results suggest that our proposals perform better than prior decentralized solutions and even outperform centralized solutions in some cases.