面向SDN/NFV中间盒依赖关系的路由研究
发布时间：2021-12-30 18:39
软件定义网络与网络功能虚拟化是当前的研究热门方向。通过将软件定义网络与网络功能虚拟化技术相结合虽然能够为运营商提供便捷高效灵活的管理模式,但是对中间盒不合理的部署将会影响到对数据包路由的规划,进而还是为运营商带来了不必要的路由成本。该文在此基础上研究了在单播和多播中受多目标约束的联合中间盒部署与路由问题以优化总路由成本。首先该文针对中间盒的依赖关系约束、链路带宽约束来最小化路由成本,首次提出联合优化虚拟中间盒部署与路由问题,并证明了该问题是NP-hard。该路由成本包括了链路传输成本与中间盒部署成本。之后设计一种面向小型拓扑网络的服务链感知精准算法（Service Chain Aware Exact Algorithm,SCAEA）,该算法可以根据给定的中间盒依赖关系和链路带宽约束条件较快地计算出最优的中间盒部署方案,并规划出成本最低的路由。在实验仿真部分通过与混合整数线性规划数学模型所求得的最优解进行对比后,验证了SCAEA的有效性,并具有良好的应用前景。考虑到问题的复杂性,该文之后也是首次研究了多播中的中间盒的有序约束、时延约束来最小化总路由成本问题,提出一种近似比为O（k）的受时...
【文章来源】：合肥工业大学安徽省 211工程院校 教育部直属院校
【文章页数】：63 页
【学位级别】：硕士
【部分图文】：
(a)信源树
树的；PIM-DM通过泛洪多播数据包并剪除来定期更新多播树；MOSPF通过将组成员信息分发给所有具有多播功能的路由器来构建多播树。传统多播是由具有多播功能的路由器维护的，并通过其实现数据流的转发和路由到相应的多个接收方。目前IP网络下的多播转发树主要是以信源树(SourceBasedTree,SBT)和核心转发树(CoreBasedTree,CBT)这两种形式存在[35]。SBT协议通过使用相邻路由器间的已知信息来构建从多播源点到各个目的点间的最短路径，从而形成以源点到目的点的最短路径树(ShortestPathTree,SPT)，有利于对时延敏感的通信，如图2.2(a)。但是这种多播转发树的构造方式需要要求网络中的每个路由器都必须为每个多播组和源点保留状态信息[3]，这无疑大大增加了路由器的额外存储负担，导致多播转发树的伸缩性受到严重的约束。CBT协议通过将一个大的自治区域划分为几个小区域，并且为每一个小区域设置一个汇聚点，这样可以实现从源点到各个汇聚点，再从各个汇聚点到各个区域内的目的点间的转发和路由，如图2.2(b)所示。虽然CBT是通过分治的方式将多播组划分为多个小组，降低了路由器的存储负担，但是这也明显增加路由数据包在链路上的传输成本。在图论中，最佳生成树是Steiner树，但是该问题属于NPC[37-38]，这意味着不可能存在时间复杂度为多项式时间的精准算法来构造该生成树。另一方面，Steiner树的构造需要掌握完整的网络拓扑信息，而传统网络中的每个路由器只能通过“下一跳”的方式来获取相邻路由器的信息，也就是说每个路由器它只能掌握到局部网络拓扑信息，因此难以将其部署在实际应用中。图2.2(a)信源树Fig2.2(a)Sourcebasedtree.图2.2(b)核心转发树Fig2.2(b)Corebasedtree.图2.2SBT与CBT示意图Fig2.2SBTandCBTschematicdiagram.
合肥工业大学硕士学位论文41RPA)作为对比。对于每一条静态多播请求的生成，我们在网络拓扑中随机挑选出一个交换机作为源节点，再挑选出V个交换机作为目的节点。此外，需要保证源节点与目的节点不重合，以及源点到各个目的节点必须是连通的。4.6.2实验结果(1)服务链长度对算法DSCMRA性能的影响。本实验采用真实的网络拓扑图newyork(|V|=16,|E|=49)[54]，将设置为0.3，服务链长度取值为{1,2,3,4,5}。在图4.5(a)中，当服务链长度为3时，算法DSCMRA所得出的近似路由成本比GLPK得出的最优解平均只略高出2.5%；当服务链长度为5时，近似解平均比最优解只略高出3.0%。此外，该图也展示出了，随着服务链的增长，即中间盒个数的增多，DSCMRA的近似解始终接近于最优解。在图4.5(b)中，随着服务链长度的增长，DSCMRA始终在指定时延内将100条多播请求全部都路由成功，成功率达到100%。而RPA的请求成功率呈下降的趋势，例如当服务链长度为5时，其路由成功的请求只有68条，成功率只为68%。因此随着服务链长度的增长，即中间盒数量增加，DSCMRA可以在获取较低的路由成本的同时，能够保持较高的请求成功率。图4.5(a)服务链长度对路由成本的影响Fig4.5(a)Impactofservicechainlengthonroutingcosts.图4.5(b)服务链长度对请求成功的影响Fig4.5(b)Impactofservicechainlengthonrequestsuccessrate.图4.5服务链长度对算法的影响Fig4.5Impactofservicechainlengthonalgorithm.(2)目的节点个数对算法DSCMRA性能的影响。本实验也是采用newyork(|V|=16,|E|=49)作为真实网络拓扑，并将服务链长度设置为3，的取值为{0.1,0.2,0.3,0.4,0.5}，由于DSCMRA的近似比为O(k)，因此，随着目的节点个数的增加，可能会对该算法的性能产生一定的影响。在图4.6(a)中?
【参考文献】：
期刊论文
[1]一种面向运营成本优化的虚拟网络功能部署和路由分配策略[J]. 史久根,张径,徐皓,王继,孙立. 电子与信息学报. 2019(04)
[2]面向多业务需求的NFV和SDN融合的资源优化算法[J]. 朱晓荣,张倩. 通信学报. 2018(11)
[3]基于服务质量与资源约束的服务链部署策略[J]. 海梅生,伊鹏,江逸茗. 计算机工程. 2019(03)
[4]基于OpenFlow的SDN技术研究[J]. 左青云,陈鸣,赵广松,邢长友,张国敏,蒋培成. 软件学报. 2013(05)
本文编号：3558765
【文章来源】：合肥工业大学安徽省 211工程院校 教育部直属院校
【文章页数】：63 页
【学位级别】：硕士
【部分图文】：
(a)信源树
树的；PIM-DM通过泛洪多播数据包并剪除来定期更新多播树；MOSPF通过将组成员信息分发给所有具有多播功能的路由器来构建多播树。传统多播是由具有多播功能的路由器维护的，并通过其实现数据流的转发和路由到相应的多个接收方。目前IP网络下的多播转发树主要是以信源树(SourceBasedTree,SBT)和核心转发树(CoreBasedTree,CBT)这两种形式存在[35]。SBT协议通过使用相邻路由器间的已知信息来构建从多播源点到各个目的点间的最短路径，从而形成以源点到目的点的最短路径树(ShortestPathTree,SPT)，有利于对时延敏感的通信，如图2.2(a)。但是这种多播转发树的构造方式需要要求网络中的每个路由器都必须为每个多播组和源点保留状态信息[3]，这无疑大大增加了路由器的额外存储负担，导致多播转发树的伸缩性受到严重的约束。CBT协议通过将一个大的自治区域划分为几个小区域，并且为每一个小区域设置一个汇聚点，这样可以实现从源点到各个汇聚点，再从各个汇聚点到各个区域内的目的点间的转发和路由，如图2.2(b)所示。虽然CBT是通过分治的方式将多播组划分为多个小组，降低了路由器的存储负担，但是这也明显增加路由数据包在链路上的传输成本。在图论中，最佳生成树是Steiner树，但是该问题属于NPC[37-38]，这意味着不可能存在时间复杂度为多项式时间的精准算法来构造该生成树。另一方面，Steiner树的构造需要掌握完整的网络拓扑信息，而传统网络中的每个路由器只能通过“下一跳”的方式来获取相邻路由器的信息，也就是说每个路由器它只能掌握到局部网络拓扑信息，因此难以将其部署在实际应用中。图2.2(a)信源树Fig2.2(a)Sourcebasedtree.图2.2(b)核心转发树Fig2.2(b)Corebasedtree.图2.2SBT与CBT示意图Fig2.2SBTandCBTschematicdiagram.
合肥工业大学硕士学位论文41RPA)作为对比。对于每一条静态多播请求的生成，我们在网络拓扑中随机挑选出一个交换机作为源节点，再挑选出V个交换机作为目的节点。此外，需要保证源节点与目的节点不重合，以及源点到各个目的节点必须是连通的。4.6.2实验结果(1)服务链长度对算法DSCMRA性能的影响。本实验采用真实的网络拓扑图newyork(|V|=16,|E|=49)[54]，将设置为0.3，服务链长度取值为{1,2,3,4,5}。在图4.5(a)中，当服务链长度为3时，算法DSCMRA所得出的近似路由成本比GLPK得出的最优解平均只略高出2.5%；当服务链长度为5时，近似解平均比最优解只略高出3.0%。此外，该图也展示出了，随着服务链的增长，即中间盒个数的增多，DSCMRA的近似解始终接近于最优解。在图4.5(b)中，随着服务链长度的增长，DSCMRA始终在指定时延内将100条多播请求全部都路由成功，成功率达到100%。而RPA的请求成功率呈下降的趋势，例如当服务链长度为5时，其路由成功的请求只有68条，成功率只为68%。因此随着服务链长度的增长，即中间盒数量增加，DSCMRA可以在获取较低的路由成本的同时，能够保持较高的请求成功率。图4.5(a)服务链长度对路由成本的影响Fig4.5(a)Impactofservicechainlengthonroutingcosts.图4.5(b)服务链长度对请求成功的影响Fig4.5(b)Impactofservicechainlengthonrequestsuccessrate.图4.5服务链长度对算法的影响Fig4.5Impactofservicechainlengthonalgorithm.(2)目的节点个数对算法DSCMRA性能的影响。本实验也是采用newyork(|V|=16,|E|=49)作为真实网络拓扑，并将服务链长度设置为3，的取值为{0.1,0.2,0.3,0.4,0.5}，由于DSCMRA的近似比为O(k)，因此，随着目的节点个数的增加，可能会对该算法的性能产生一定的影响。在图4.6(a)中?
【参考文献】：
期刊论文
[1]一种面向运营成本优化的虚拟网络功能部署和路由分配策略[J]. 史久根,张径,徐皓,王继,孙立. 电子与信息学报. 2019(04)
[2]面向多业务需求的NFV和SDN融合的资源优化算法[J]. 朱晓荣,张倩. 通信学报. 2018(11)
[3]基于服务质量与资源约束的服务链部署策略[J]. 海梅生,伊鹏,江逸茗. 计算机工程. 2019(03)
[4]基于OpenFlow的SDN技术研究[J]. 左青云,陈鸣,赵广松,邢长友,张国敏,蒋培成. 软件学报. 2013(05)
本文编号：3558765
本文链接：https://www.wllwen.com/guanlilunwen/ydhl/3558765.html
