V-Sketch: A Sketch-Based Verification Mechanism for Logical-Physical Rule Consistency in SDN
摘要
Software-defined networking (SDN) decouples the control plane from the data plane, increasing network flexibility but leading to potential inconsistency in the translation process from operator intent to packet forwarding behaviours. The inconsistency between the logical rules in the controller and the physical rules in the switch is of particular concern because it directly correlates to forwarding behavior errors and network attacks. However, current works cannot effectively verify this consistency, primarily because modern networks are dynamically changing and contain a large number of rules, making it challenging to conduct timely and efficient verification. This paper presents V-Sketch, a novel logical-physical rule verification mechanism designed to verify consistency and localize inconsistency between logical and physical rules with minimal storage and communication resource consumption. V-Sketch deploys a Bloom Filter-inspired data structure in the switch to summarize physical rules, sending the summary to the controller for verification with logical rules periodically or on demand. Using bitwise XOR operation, the summary is designed as a compact fixed-size array to store the fingerprints of physical rules, which is small enough to fit in a packet, thereby reducing memory usage and communication overhead. We conducted a mathematical analysis of V-Sketch regarding precision, time complexity, memory usage, and communication overhead. We also performed experimental evaluations using rule datasets generated from real traffic data. The experimental results demonstrate that, in the presence of 300 inconsistent rules within a single verification period, V-Sketch achieved over 99% precision and recall in localizing inconsistent rules.