关键词:
形式化验证
增量验证
混合多域软件定义网络
图算法
摘要:
随着全球信息化进程的加速与网络服务的快速增长,网络的规模呈现出指数级的扩张,网络的结构也变得越来越复杂多样,网络配置设置的难度和风险也随之增加,目前网络配置错误已经成为了导致频繁网络故障和业务中断的主要原因之一。网络形式化验证是保证网络的正确运行的重要手段,自其被提出以来,已有诸多学者针对不同类型的网络进行了不同层面的形式化验证工作。然而,现有的工作存在以下问题:1.在验证方法上,现有验证工作大多采用两次全局验证的方法应对网络配置更新的验证,尽管这种方法的验证效率较低且运算开销较高。目前增量验证方法存在的扩展性低、配置输入困难等问题导致其并不被行业所应用。2.在验证网络类型上,现有的验证工作都只针对于路由交换网络或纯粹的软件定义网络进行验证,而忽视了软件定义网络的主要应用场景之一:混合多域软件定义网络。混合多域软件定义网络是包含有路由交换设备与软件定义网络设备的网络。这种场景涉及对多个不同网络域中策略的管理,给形式化验证工作带来了挑战。针对配置更新场景下的验证问题,本文进行了对配置更新快速验证的研究,提出了基于转发信息表对比的快速网络配置更新验证方法。本文采用形式化方法将网络数据流构建为流模型,将转发信息表项与网络拓扑结合以构建图模型,通过所提出的两种模型对网络中数据包的具体转发路径进行了抽象表述。本文讨论了不同配置段更新对转发设备转发信息表的影响,并根据所验证属性的不同确定了需要重新验证的方案。结合以上所提出内容,本文提出了针对配置更新场景下的验证算法Fast CUV,它通过网络配置更新前后配置信息所生成的网络快照分析转发信息表差异,进而发现在配置更新后转发属性的违反,实现网络配置更新的快速验证。针对混合多域软件定义网络的验证问题,本文对混合多域软件定义网络的转发策略验证方法进行了研究,提出了基于图算法的混合多域软件定义网络转发策略验证方法。本文在考虑到多域软件定义网络特性的基础上,设计了用以描述混合多域软件定义网络的通用形式化模型HM-SDN,该模型实现了从拓扑、转发路径、策略等方面对混合多域软件定义网络的描述。为了让所提出的模型便利验证过程,本文按照HMSDN构建了软件定义网络信息图SDNIG,该信息图是一种数据结构,在该数据结构上实现了基于图算法的混合多域软件定义网络转发策略验证算法VeriGraph的设计,实现了多种转发策略的验证工作。实验结果显示,本文所提出的快速网络配置更新验证方法在配置变更行数较少时可以较高效的实现大规模网络环境中网络配置更新时的验证,同时混合多域软件定义网络转发策略验证方法可以完成不同网络拓扑上的验证工作。