孙 立,史久根

(合肥工业大学 计算机与信息学院, 安徽 合肥 230601)

0 引 言

网络功能虚拟化(network function virtualization,NFV),也称为“中间盒”,将网络功能的实现方式从基于专有硬件的设备转为可在标准服务器中运行的虚拟机(virtual mechine,VM)中[1]。基于虚拟化技术来灵活部署网络功能可以为运营商获得更好的收益,降低运营成本[2]。但是中间盒之间的依赖关系约束使得中间盒部署充满了挑战。例如,IPSec通常被部署在NAT(network address translation)之前[3];IDS(intrwsion detection system)需要部署在Firewall之后,作为系统防御的第2道防线[4];VPN(virtual private network)可以部署在Firewall之前或之后[5]。因此不当的中间盒部署策略将会给运营商产生不必要的路由成本,降低路由效率。将由多个网络功能组合而成的功能集称为服务链(service chain,SC)[6]。在服务链中,若所有的功能都存在依赖关系,则称为服务链的有序性;若存在部分功能有依赖性,则称为服务链的部分有序性;若无存在依赖关系的功能,则称为服务链的无序性。

文献[7]基于服务链的3种状态研究了流率的变化对路由的影响,提出了一种基于动态规划的算法来部署一条有序服务链,并提出了一种最优的贪婪解决方案,用于部署一个无序服务链,此外也证明了对于部分有序性服务链的部署是NP-hard问题,但是他们所研究的目标是负载均衡而不是成本优化。文献[8]也是基于服务链的3种状态研究了流率的变化对路由的影响,同时考虑到了中间盒的部署成本,但是研究只适用于树状网络拓扑,对更为一般的图状网络拓扑并不适用。文献[9]在受链路带宽约束的条件下提出一种启发式算法用于解决联合中间盒部署和路由优化问题,并证明了有序性服务链的部署是NP-hard的,但是只考虑了服务链有序的情况,对于服务链部分有序以及无序并没有考虑。……