论文部分内容阅读
随着互联网的普及和发展,当今网络系统变得越来越复杂并愈加难以管理和扩展应用。软件定义网络(Software-Defined Networking,SDN)是一种有望改变现有网络困局的新型网络架构,已经引起了业界的广泛关注和研究。软件定义网络的核心思想是采用控制平面和数据平面相分离的架构,实现网络数据转发的灵活控制。与传统网络不同,控制平面作为SDN网络的核心,控制器的优化部署牵涉到网络时延、负载和网络安全性等各方面;与传统网络类似,SDN网络在突发事件下同样面临着网络节点或链路失效的网络鲁棒性问题。因此,研究应对事件提升SDN网络鲁棒性的控制器优化部署问题具有重要意义。本论文关注SDN网络在链路失效情境下兼顾网络时延和负载均衡的最优控制器部署问题,简称面向k链路失效的鲁棒控制器优化部署(Robust Control Placementfor h-links-failure,k-RCP)问题。为求解k-RCP问题,我们首先提出了一种算法时间复杂度非常有优势的启发式方法来解决k-RCP问题,为进一步提升解决k-RCP问题的性能,随后提出了基于原始-对偶算法的鲁棒的控制器优化部署方法。本论文的主要研究工作包括以下几方面:(1)首次提出k-链路失效情境下兼顾网络时延和负载均衡的最优控制器部署问题。针对本文提出的k-RCP问题建立整数线性规划模型(Integer linear programming,ILP),该模型通过优化配置控制器资源,使得控制器的代价最小、控制信息的传输效率最高、同时满足任意k-链路失效情况下SDN网络中控制器的控制覆盖率。(2)提出了控制器鲁棒性和控制器信息传播有效性的度量指标。在SDN网络k-链路失效情况下,衡量控制器覆盖率的Cpr指标。Cpr越高,控制器部署结果的鲁棒性越高;度量控制信息传输效率的TE指标,TE值越高,控制信息越容易传输。(3)提出了基于GN算法的有限控制器资源重构的启发式算法,该算法兼顾控制器连通性以及控制信息传输的有效性,并且显著降低了求解k-RCP问题的分支定界算法的时间复杂度。仿真实验表明,该启发式算法可以显著降低求解k-RCP问题复杂度的同时有效提升SDN网络的可生存性。(4)为了进一步提升启发式算法的性能,本文使用偏远节点提取、聚类以及原始对偶算法相结合,提出求解k-RCP问题的k-RCP近似算法。k-RCP近似算法首先修改实例,在已知的SDN网络中提取outliers节点并模拟链路失效的最坏情景,然后对本文建立的整数线性规划模型松弛为线性规划,进而得到其对偶规划,利用原始-对偶近似算法(Primal-Dual Approximate Algorithm)得到控制器最优部署策略。仿真实验表明,k-RCP算法能有效实现兼顾网络时延和负载均衡的SDN网络控制器的最优部署,并能显著降低控制器优化部署问题的计算复杂性。为有效求解SDN网络面对链接失效时的可用性,本文提出有限控制器资源重构的启发式算法以及k-RCP近似算法。经过算法分析以及对比实验发现,本文提出的启发式算法可以有效降低k-RCP问题整数规划模型的复杂性,在此基础上k-RCP近似算法进一步提高了启发式算法的性能,以实现SDN控制器部署的鲁棒性、效率和负载均衡功能。