面向SDN/NFV中间盒依赖关系的路由研究

作     者：孙立 

作者单位：合肥工业大学 

学位级别：硕士

导师姓名：史久根;徐建生

授予年度：2020年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：软件定义网络 网络功能虚拟化 中间盒 服务链 网络算法 

摘      要：软件定义网络与网络功能虚拟化是当前的研究热门方向。通过将软件定义网络与网络功能虚拟化技术相结合虽然能够为运营商提供便捷高效灵活的管理模式,但是对中间盒不合理的部署将会影响到对数据包路由的规划,进而还是为运营商带来了不必要的路由成本。该文在此基础上研究了在单播和多播中受多目标约束的联合中间盒部署与路由问题以优化总路由成本。首先该文针对中间盒的依赖关系约束、链路带宽约束来最小化路由成本,首次提出联合优化虚拟中间盒部署与路由问题,并证明了该问题是NP-hard。该路由成本包括了链路传输成本与中间盒部署成本。之后设计一种面向小型拓扑网络的服务链感知精准算法（Service Chain Aware Exact Algorithm,SCAEA）,该算法可以根据给定的中间盒依赖关系和链路带宽约束条件较快地计算出最优的中间盒部署方案,并规划出成本最低的路由。在实验仿真部分通过与混合整数线性规划数学模型所求得的最优解进行对比后,验证了SCAEA的有效性,并具有良好的应用前景。考虑到问题的复杂性,该文之后也是首次研究了多播中的中间盒的有序约束、时延约束来最小化总路由成本问题,提出一种近似比为O（k）的受时延约束的服务链感知多播路由近似算法（Delay-constrained for SC-aware Multicast Routing Algorithm,DSCMRA）。其中时延包括了链路传输时延和中间盒处理时延,成本包括了链路传输成本和中间盒部署成本。该算法通过将复杂的中间盒有序约束转变为只受时延和成本约束的图论问题后,进而再采用拉格朗日松弛方式将时延约束松弛到成本约束中,以消除多约束条件。在用户组动态变化的情况下,该文据此也设计出一种动态的多播算法用于解决这类问题,在保证有新用户在时延阀值内能够及时加入会话组的前提下,以降低总路由成本。