Study On Congestion-free Consistent Data Plan Update Strategy In Software Defined Network

Software Defined Network(SDN)has been widely used in traffic engineering and fault recovery within the controller in SDN has a global view of the network state and can provide flexible management and control.Although the control plane of SDN architecture is logically centralized,the data plane is still a distributed system.During flow migration,forwarding rules update in the data plane may be inconsistent due to asynchronous update of switches.The inconsistent update can cause black holes,loops,and transient congestion during the update.Unfortunately,the occurrence of black holes,loops,and transient congestion may result in temporary interruption of flows and reduction of throughput.Therefore,in order to solve the above problem,the order of the rules update must be carefully considered to ensure the consistency of the rules update.Moreover,in most cases,workloads on the network change over time.If a route update takes a long delay,the final routing configuration may be invalid for the updated workload.Therefore,how to reduce the update delay becomes an urgent problem in the case of avoiding black holes,loops and transient congestion at the same time.In this thesis,the main research content is how to update the forwarding rules of the data plane in SDN network for the purpose of quickness and consistency.First,a rule update method from the perspective of updating scheduling is proposed to shorten the time of rule update while avoiding black holes,loops and transient congestion simultaneously.Then,considering the issue of combination of routing selection and update scheduling,an update mechanism is proposed for joint optimization of path selection and update scheduling to maximize the number of updated flows.Main research contents are described as follows.(1)This thesis proposes a rule update method that can avoid black holes,loops and transient congestion simultaneously.First,this paper analyzes how to avoid black holes,loops,and transient congestion,and builds three corresponding avoidance models.In order to avoid black holes and loops,the method constructs black hole-free and loop-free rule update dependency graphs,and maximizes the number of nodes that can be updated simultaneously in each segment to shorten the time of rule update.To avoid transient congestion,a congestion-free dependency graph is constructed to delay the updating of some of flows that need to be moved into the potential congestion link,and to minimize the number of delayed updating flows to reduce the queue time for rules update.Subsequently,three novel black holes avoidance algorithm,loops avoidance algorithm and congestion avoidance algorithm are respectively proposed.Furthermore,this paper proposes a rule update(RU)algorithm which integrates the above three algorithms to update the rules to avoid black holes,loops and transient congestion simultaneously.Simulation results show that,compared with the existing work,RU algorithm can significantly reduce the number of directly updated flows on a single congestion link and the completion time of the rules update.(2)This thesis proposes an update mechanism for joint optimization of path selection and update scheduling.The update mechanism reduces the complexity of dependencies between updates by segmentally updating nodes in the new path of a flow,and each flow can save up to one flow entry in the flow table of the same switch to reduce TCAM overhead.Specifically,the paper first formulates the path selection problem as a minimum maximum link utilization problem,which subjects to link capacity constraint and update delay constraint.Secondly,the models of avoiding black holes,loops and transient congestion are constructed.Then,the corresponding path selection algorithm and update scheduling algorithm are proposed.Furthermore,this paper proposes a joint optimization algorithm for routing selection and update scheduling,which combines the above two algorithms to reduce the overhead of TCAM and increase the number of updated flows.Finally,the algorithm is analyzed in terms of TCAM overhead,link utilization and the number of updated flows.Simulation results show that the proposed solution reduces the overhead of TCAM and increases the number of updated flows compared with the existing work.