Waterfall: Fast Network Flow Rules Checking and Conflict Resolution

Software Defined Networking (SDN) enables a centralized manageable framework to control network devices and their policies using device-specific flow rules. When administrators deploy flow rules to support business policies, the network controller checks them against existing rules to detect conflicts and ensure consistency, security, and functionality in the data plane. Existing offline conflict detection methods are not scalable due to state explosion and often lead to networking chaos due to inefficiency. This paper presents Waterfall, designed to minimize the number of flow rule-checking operations. We propose a novel Equivalence Class (EC) creation and prioritization technique that simplifies conflict detection by organizing rules with similar patterns and processing them accordingly. Analogous to a multi-stage waterfall, our algorithm optimizes downstream stages by reducing unnecessary comparisons, ensuring efficient conflict detection. Our comprehensive evaluation demonstrates Waterfall's effectiveness through significant reductions in computation time (O(mKH), where m is the number of matched flow-rules which is far less than the total number of flow-rules, K is the number of attributes (headers) in flow rules, H is the number of hash functions in Bloom filter for attribute matching), making it ideal for real-time flow rule checking and conflict resolution in SDN environments. In our evaluation, Waterfall achieved a remarkable 1.3X improvement in conflict detection and 4.4X improvement for conflict resolution over the state-of-the-art solution for the Stanford topology which is a popular topology to represent real-world networking scenarios. We also evaluate the scalability of the solution using a synthetic dataset containing 15K flow rules that have three virtual network functions. Our solution achieved a 90.53μs conflict detection and resolution time for the large synthetic dataset. This lightweight approach promises substantial benefits for real-time flow rule checking in SDN environments.