一种基于MapReduce的OpenFlow网络属性并行验证算法

针对OpenFlow网络中流表配置错误引起转发回路、路由黑洞和访问控制规则失效等问题，提出一种并行的基于MapReduce的OpenFlow网络属性验证算法。通过在Map阶段划分规则等价类，在Reduce阶段为规则等价类构建基于交换机端口谓词的网络转发图并分析可达性，实现对网络属性的并行验证。同时，通过采用原子谓词将传统可达性分析中的规则匹配域多维集合运算转换为整数集合运算，以进一步提高可达性分析效率。此外，基于原子谓词的谓词表达方式可消除交换机端口谓词集合中的冗余项，降低存储开销。最后，通过理论分析和仿真实验验证了算法的正确性及在时间和存储开销方面的优越性。

MapReduce-based network property parallel verification algorithm for OpenFlow network

For flow table misconfiguration leading to loops, black-holes and failure of access control rules in OpenFlow network, this paper proposed a MapReduce-based network property parallel verification algorithm. The algorithm sliced network into equivalence classes in map phase and built forwarding graphs using switch port predicates and computed reachability in reduce phase, which could verify network properties in parallel. To improve the speed of verification, it used atomic predicates to convert the conjunction and disjunction of predicates to the intersection and union of sets of integers respectively, resulting in efficient computation of network reachability. Meanwhile, the method of representing predicates with atomic predicates could eliminate redundancy of sets of switch port predicates leading to reduction of storage overhead. Theoretical analysis and simulation results show that the proposed algorithm is much more time and space efficient than existing ones.