许宜诚团队提出一种异构服务器虚拟网络功能在线调配算法

中国科学院深圳先进技术研究院高性能计算技术研究中心许宜诚团队在异构服务器虚拟网络功能在线调配算法取得进展。相应成果“Online joint placement and allocation of virtual network functions with heterogeneous servers(异构服务器的虚拟网络功能在线调配算法)”于 2020 年 4 月 27 日发表在IEEE Internet of Things Journal上。

网络功能虚拟化(Network Function Virtualization，NFV)是基于软件定义网络(SDN)的一种网络架构概念，即利用虚拟化技术将网络节点阶层化，以软件运作的方式使网络服务摆脱硬件架构的拘束。NFV 技术涵盖的网络功能十分广泛，包括家庭路由、机顶盒业务、流量分析、SLA 监测、测试与诊断、应用程序优化、安全功能等。然而在 NFV 技术的实现中，虚拟网络功能(Virtual Network Function，VNF)的调配一直是非常棘手的难点和热点问题。近年来，网络顶级会议相继披露了多项相关研究成果：(1)使用最少的预算在网络节点中配置 VNF 节点，使得所有用户的需求都能被满足(Sang et al. INFOCOM’17)；(2)使用有限的预算在网络节点中配置 VNF 节点，使得尽可能满足最多用户的需求(Sallam and Ji, INFOCOM’19)。然而，他们都假设了一种理想状态，即网络中的服务器节点都是同构的且可以无限配置 VNF(只要预算足够)，然而现实并不是这样。

该研究采用动态规划、随机算法等移除了上述不合理假设，首次引进一种非常宽泛的左连续函数描述了所有可能的服务器性能函数的种类，并发现所提出的模型涵盖了包括但不限于上述两种模型在内的多种场景。其次，针对新提出的模型，构造了一个非常有意思的对手实例，细致地分析了其复杂度，并在此条件下基于动态规划提出了一种精确算法。虽然该算法在精确度上已经优于前人的算法，但其运行时间却仍未达到团队的要求。因此，提出了两类定制化随机加速算法，分别是拉斯维加斯(LV)算法和蒙特卡罗(MC)算法。最后，大量试验表明，算法不但在运行时间和占用内存方面明显优于精确算法，在精准度上也可与精确算法媲美。此外，由于 MC 算法的特性，可以很容易地通过控制参数来平衡服务质量(QoS)和运行时间，此技术将在大数据场景具有非常大的应用潜力。

该研究为 NFV 提供了新的技术和视野，也为网络方案供应商提供了新的平衡预算和服务质量的方案。

精确算法(红)与随机算法(蓝)的精度对比[1]

[1] Xu YC, Chau V, Wu CC, et al. Online joint placement and allocation of virtual network functions with heterogeneous servers [J]. IEEE Internet of Things Journal, 2020, 7(9): 8049-8058.