Control-Data Plane Consistency Verification In Software-Defined Networks

Traditional IP networks distribute control logic to each network device to provide high re-liability,which brings two major drawbacks when networks grow larger with more and more applications.First,distributed control plane makes networks hard to manage.Second,network innovations are impeded due to the deep coupling of control and data plane.To overcome the two drawbacks,software-defined networking(SDN)decouples the control logic from underly-ing forwarding equipments.Thus,data plane is only responsible for traffic forwarding while control logic is maintained by the logically centralized controller.Besides,the controller pro-vides programmable interface to network operators to enable flexible network management.New network services and applications could be added to the controller as modules,which ac-celerates network innovations.As an emerging networking technology,SDN faces many problems and challenges when being deployed.We focus on an important one:control-data plane inconsistency,i.e.,the desired forwarding behavior on control plane is inconsistent with the actual forwarding behavior on data plane.To be more specific,network policies required by network operators may not be enforced by underlying network devices.Such inconsistency results from data plane,e.g.,software bugs or hardware failures on network devices,and could result in severe network issues like violation of network invariants and performance degradation.Therefore,it is important to verify the consistency between control and data plane.Normally,control-data plane consistency verification requires three steps:1)measure the actual forwarding behavior from data plane;2)detect the inconsistency by comparing the desired and the actual forwarding behavior;3)locate the inconsistency if any.Based on the above three steps,we make four specific proposals.First,we focus on measure:measure the actual forwarding behavior on data plane in a passive way.We choose sFlow,which is widely supported in commodity switches,to provide sampled packets for measurements.To handle the large volume of sFlow packets,we employ an existing streaming processing framework to process those packets in real time.However,the sampling mechanism complicates our measurements.First,complete flow paths are unable to be inferred because sFlow can miss sampling packets of those flows on certain nodes.Second,using simple scaling,flow rate estimation could be inaccurate when the number of sampled packets is small.Therefore,for flow path inference,we propose the Tapco(Topology-assisted Path Computation)algorithm to incorporate network topology information;for flow rate esti-mation,we leverage the protocol-specific information included in packet headers to accurately estimate flow rates.Second,we combine measure and locate:when knowing the existence of control-data plane inconsistency,locate such inconsistency by measuring the packet histories of probes.Control-data plane inconsistency can result in severe network issues,which affect certain packets.If we can observe how those packets are handled(i.e.,packet histories),the inconsistency could be identified as well.We define the packet history of one packet as the list of rules the packet matches along it path across the network as well as the packet headers after each rule.Based on that,our our troubleshooting procedure is:first,inject probes pretending to be the packets affected by network issues to edge switches;second,measure the packet histories of probes;third,locate the inconsistency by analyzing packet histories.We have implemented the method of obtaining packet histories,and validated the practicability of leveraging packet histories to locate control-data plane inconsistency.Third,we combine all the three steps together to systematically propose the rule verification method for control-data plane consistency verification.Network issues,caused by software bugs and hardware failures inside network devices,usually manifested themselves as failed rules.Thus,by checking the effectiveness of all the rules,control-data plane consistency can be verified accordingly.Previous efforts focus on end-to-end probing for such verification,which falls short on timely locating the inconsistency.By adopting the out-band channel widely used in SDN,per hop probing could be employed to enable per rule comparison between desired and actual forwarding behavior,thus verifies all the rules.Based on that,we model each network device as a stateful multi-rooted tree(SMRT),and generate a small number of probes to cover all the rules of that device by traversing the corresponding SMRT.We have implemented a prototype,conducted the performance evaluation on probe generation,and validated the effectiveness of our approach in a small deployment.At last,we focus on the probe generation problem in rule verification in the last proposal.Probe generation is vital to rule verification,which has two drawbacks in the last proposal.First,per device probe generation can produce extra probes because some rules could be verified by a single probe along its path.Second,when facing rule updates,re-generating probes from scratch is certainly not viable considering the hundreds of thousands of rules in the network.Therefore,we extent the SMRT model in the last proposal to the whole network,i.e.,a new network model called sDAG(stateful Directed Acyclic Graph),and propose two new approaches based on the new model to overcome the two drawbacks.One is the offline FPG(Fast Probe Generation),the other is the online iFPG(incremental FPG).The evaluation results show that FPG is better than other existing works considering probe generation time and the number of generated probes,and iFPG outperforms all the non-incremental approaches including FPG.