ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (11): 2500-2511.doi: 10.7544/issn1000-1239.2016.20150521

• 信息安全 • 上一篇    下一篇



  1. (解放军信息工程大学 郑州 450001) (河南省信息安全重点实验室(解放军信息工程大学) 郑州 450001) (
  • 出版日期: 2016-11-01
  • 基金资助: 
    国家“八六三”高技术研究发展计划基金项目(2012AA012704);郑州市科技领军人才项目(131PLJRC644) This work was supported by the National High Technology Research and Development Program of China (863 Program) (2012AA012704) and Zhengzhou Science and Technology Talents Project (131PLJRC644).

MapReduce-Based Network Property Verification Technique for OpenFlow Network

Liu Yi, Lei Cheng, Zhang Hongqi, Yang Yingjie   

  1. (PLA Information Engineering University, Zhengzhou 450001) (Henan Key Laboratory of Information Security (PLA Information Engineering University), Zhengzhou 450001)
  • Online: 2016-11-01

摘要: 针对OpenFlow网络中由程序自动改变数据平面状态方式引起的流表配置错误问题,提出1种基于MapReduce的OpenFlow网络属性验证技术.首先,利用OpenFlow网络控制转发分离的特点,设计支持实时与非实时2种验证方式的技术架构.其次,提出基于MapReduce模型的非实时验证算法,在Map阶段划分规则等价类,在Reduce阶段构建基于交换机端口谓词的网络转发图并分析可达性,以实现对网络属性的并行验证.与此同时,利用原子谓词消除谓词集合冗余项和规则匹配域转换的方法,提高可达性分析效率.此外,在非实时验证算法的基础上,结合网络更新事件提出实时验证算法,实现网络状态改变时的增量式网络属性验证.最后,理论分析和仿真实验验证了该技术的运行效率和存储开销,并分析了其对TCP连接建立时间的影响.

关键词: 流表配置, 网络可达性分析, 网络属性验证, MapReduce模型, OpenFlow网络

Abstract: Aimed at the problem of configuration errors of flow tables resulting from automatic change of data-plane state by software in OpenFlow network, a MapReduce-based network property verification technique is proposed. Firstly, by exploiting the separation of logic control from data forwarding in OpenFlow network, a novel technical framework providing non-real-time and real-time verification is designed. Further, on the basis of the advantage of parallel computing in MapReduce, a non-real-time verification algorithm is presented, which can verify network properties in parallel in two phases. In Map phase, it slices network into equivalence classes. In Reduce phase, it builds network forwarding graph with switch port predicates and conducts network reachability analysis. Meanwhile, with the help of atomic predicates, it can not only eliminate the redundancy of the set of switch port predicates, but also convert highly computation-intensive operations on predicates to those on sets of integers, speeding up computation of network reachability further. Based on it, a real-time verification algorithm is proposed. According to different network update events, it applies different changes to the results of non-real-time verification in order to incrementally verify properties. Finally, theoretical analysis and experimental results show the low time and storage overhead of the proposed technique. Additionally, its effect on the time of building TCP connection is also analyzed.

Key words: flow table configuration, network reachability analysis, network property verification, MapReduce model, OpenFlow network