面向NFV中间盒依赖关系的有效路由策略

孙 立,史久根

(合肥工业大学 计算机与信息学院, 安徽 合肥 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的,但是只考虑了服务链有序的情况,对于服务链部分有序以及无序并没有考虑。

本文将在链路带宽以及中间盒的依赖关系约束条件下,针对联合中间盒部署以及路由问题,提出服务链感知精准算法(service chain aware exact algorithm,SCAEA)用于解决该问题。该算法首先是根据网络拓扑图和中间盒依赖关系来构建有向层级图,进而消除中间盒的依赖约束。之后在该有向层级图中采用k-shortest paths算法[10]来筛选出带宽满足用户请求的链路。仿真结果表明,本文所提出的SCAEA在真实网络拓扑下具有很好的应用前景。

1 问题描述与模型构建

1.1 问题描述

联合中间盒部署与路由如图1所示。图1a中节点v0为请求的源点,v5为终点,{v1,v2,v3,v4}为部署中间盒{m1,m2,m3}的候选节点,也就是说,在节点v1上,既可以部署中间盒m1,也可以部署中间盒m2,还可以部署中间盒m3。不失一般性,假设每个候选节点的放置容量为1,即最多只能部署一个中间盒。当中间盒m1部署在候选节点v1上,m2部署在候选节点v3上,m3部署在v2上时,如图1b所示,从源点v0到目的点v5的数据流按照m1到m2,再到m3的顺序来获取相应的功能服务,可以得到该图所示的路由路径。在路径中,边(v2,v3)被重复路由了3次,这是因为数据流第1次从节点v2到节点v3是为了获取部署在节点v3上的中间盒m2的服务;而第2次经过是为了获取部署在节点v2上的中间盒m3的服务;第3次是因为数据流此时已经获取了所有的功能服务,接下来将向目的点进行路由,所以又从节点v2到节点v3经过一次。当考虑到链路带宽资源的约束时,显然,在这种情况下对边(v2,v3)的带宽资源需求是对只经过一次边的3倍多,例如对(v2,v3)的带宽资源需求将是对边(v0,v1)的3倍。

图1 联合中间盒部署与路由

若按照这种中间盒编排、部署的位置以及路由选择这种方式,只有边(v2,v3)对链路资源的需求比较高。

首先，若将中间盒m1部署在候选点v4处,m2部署在候选点v3处,m3部署在候选点v2处时,如图1c所示,在从源点到目的点的路由路径中,边(v2,v3)和(v3,v4)都被路由了3次。因此,若按照这种方式进行部署,将会对网络的带宽资源有较高的要求。其次,当中间盒{m1,m2,m3}之间不存在依赖关系时,即该服务链是无序性的,则中间盒可能存在多种编排方式,例如从m1到m3再到m2,或者是从m3到m2再到m1……。因此,在这些编排以及放置策略中,如何选择出总成本最低的路由具有重要的研究意义,同时也具有巨大的挑战性。

1.2 系统模型

用无向有权图G=(V,E)表示网络拓扑结构,其中V为节点集合,E为无向边集合。然后用src∈V表示请求的发送方,dst∈V表示请求的接收方,M表示请求所需的中间盒集合。对于任意的2个中间盒m∈M和m′∈M规定:若m′依赖于m,即数据包必须首先获取中间盒m的服务后才能再来获取m′的服务,m→m′;若中间盒m反依赖于m′,即数据包必须首先获取到m′的服务后才能再来获取m的服务,m←m′;若中间盒m不依赖也不反依赖于m′,即数据包不必优先获取到m′的服务后才能再来获取m的服务,或是先获取到m的服务后才能再来获取m′的服务,m∞m′。此外,还需要规定中间盒之间的依赖关系具有不可逆性:若m→m′,则有m′→/m;依赖关系也具有传递性:若m→m′并且m′→m″,则有m→m″。本文不考虑一条服务链中存在多个同种功能的中间盒的情况,也就是说请求对某种网络功能的需求只需要获取一次服务即可。

接下来对所需要用到的一些常量进行定义。定义一个整型常量depend[m,m′]用于表示2个中间盒之间是否存在依赖关系,即对于∀m,m′∈M,当m→m′时,常量depend[m,m′]=1,并且depend[m′,m]=-1;否则其值为0。定义一个二进制常量candidate[u,m]用于表示节点u是否是部署中间盒m的候选节点,即对于任意的节点∀u∈V,若节点u是部署中间盒m的候选节点,则常量candidate[u,m]=1;否则其值为0。对于边(u,v)∈E的带宽容量本文定义一个正实数常量capacity[u,v]表示。为了方便计算,本文采用i=1表示服务链的起始,用标识中间盒ms占位;采用i=n表示服务链的终止,用标识中间盒md占位。并且，定义{ms,md}⊆M,ms→md。对于任意的功能中间盒∀m∈M-{ms,md}都存在这种依赖关系:起始中间盒ms必须被编排在功能中间盒之前,ms→m;终止中间盒md必须被编排在功能中间盒之后,m→md。另外定义成本函数:对边(u,v)∈E的传输成本用正实数C[u,v]表示,功能中间盒m在节点u上的部署成本用正实数C[u,m]表示。

接下来定义一个二进制变量place(m,i)用于表示是否将中间盒m编排为第i个。为了方便进行阐述,本文将数据包转发到编排序号为第i个中间盒的过程称为第i跳。定义二进制变量branch(u,m,i)用于表示是否将编号为i(1≤i≤n)的中间盒m∈M部署在节点u∈V上。定义一个二进制变量route(u,i)用于表示数据包的第i(1≤i≤n)跳是否将会路由到节点u∈V上。用二进制变量link(u,v,i)表示边(u,v)∈E是否存在于数据包从第i跳到第i+1跳的路由路径中(1≤i≤n-1)。为了将起始中间盒ms编排为第1个,将终止中间盒md编排为最后一个,分别作如下定义：

place(ms,1)=1

(1)

place(md,n)=1

(2)

(3)

(4)

(3)式保证了对于每一个中间盒m∈M都必须被编排上序号,并且最多只能被编排一次。(4)式确保了对于每一个编排序号i(1≤i≤n)都能对应的上一个中间盒。

depend[m′,m]≥0,∀m,m′∈M

(5)

(5)式表示根据每一对中间盒之间的依赖关系,按序编排这两个中间盒的序号。例如,当中间盒m和m′满足m→m′时,常量depend[m,m′]=1,则这就要求中间盒m的编排序号要小于中间盒m′的;当m←m′时,常量depend[m,m′]=-1,则m的编排序号要大于中间盒m′的;当m∞m′时,depend[m,m′]=0,则m与m′可以任意编排序号。

branch(src,ms,1)=1

(6)

branch(dst,md,n)=1

(7)

(6)式确保将编号为1的起始中间盒ms部署在请求的源点src∈V处。(7)式确保将编号为n的终止中间盒md部署在请求的目的点dst∈V处。

branch(u,m,i)=0,∀m∈M,1≤i≤n

(8)

(8)式表示将每一个被编排上序号的中间盒都要被部署在对应的某一个候选点上。如当u是中间盒m的部署候选点,则candidate[u,m]=1,且中间盒m也被编排为第i个,即place(m,i)=1,因此变量branch(u,m,i)=1必须存在,也就是说,要将编号为i的中间盒m部署在节点u上。

(9)

因为网络中的有些节点可以是多种中间盒的部署候选点,根据之前的前提假设,每个候选点最多只能部署一个中间盒,所以(9)式确保了这个前提假设的成立,即将候选点的部署容量设置为1,并且对每一个节点∀u∈V都满足约束条件。

∀u∈V,1≤i≤n

(10)

(11)

(10)式、(11)式联合保证了对数据包的每一跳都有唯一的网络节点作为对应,即将中间盒的编排次序映射成网络拓扑上的部署位置。

route(u,i)-route(u,i+1),

∀u∈V,1≤i≤n-1

(12)

(12)式用于保证数据包从第i跳到第i+1跳满足流守恒约束条件,其中符号Nu表示u∈V在图G中的邻接节点集合。

(13)

(14)

(15)

(14)式为所有的中间盒部署成本之和,其中编号i从2开始计数到n-1为止,是因为起始中间盒ms和终止中间盒md只是一个占位符号,因此其部署成本为0。(15)式表示路由中的路径传输成本之和,从数据包的第1跳到第2跳再到第3跳,一直累加到目的点。接着定义本问题的优化目标C,该目标是由中间盒部署成本和链路的传输成本组成的,是用来最小化总路由成本。

minC=Z+N

(16)

2 算法设计

为了能够快速精准地解决受中间盒依赖关系约束以及链路带宽资源约束的路由成本最小化问题,本小节提出服务链感知精准算法(service chain aware exact algorithm, SCAEA)。该算法由有向层级图构造和路由路径选择2个部分组成。

2.1 有向层级图构造

在层级图中,数据包每跨一级路由,意味着它可以再次获取一种中间盒服务,依次类推,只要数据包可以连续地跨越n-1级,就可以获得所有功能中间盒的服务。假设第i级内的第j层为Li,j,其所代表的中间盒组合为A第i+1级内的第k层为Li+1,k,其所代表的中间盒组合为B,若A⊆B,则数据包可从Li,j层跨级路由到Li+1,k层。需要注意的是,跨级路由的交叉点需为中间盒m=B-A的候选部署节点。此外,跨层间的有向边权值是C[u,v]与C[u,m]之和,而同层内的有向边权值为C[u,v]。

例如,假设中间盒{m1,m2,m3}只存在唯一的依赖关系为m3→m2,由图1a所构造的层级图如图2所示,其中每个虚线框代表一级,每一级由多层拓扑组成。因为数据包获取的第1个中间盒服务必须为ms,因此第1级只有一层,所代表的中间盒组合为{ms}。第2级表明数据包已经获取过某2种中间盒服务,因此,由任意的2种中间盒所产生的组合为{ms,m1}、{ms,m2}、{ms,m3}、{m1,m2}、{m1,m3}以及{m2,m3},在排除不符合依赖关系的组合后为{ms,m1}和{ms,m3},因此在第2级中,可分为2层,分别代表{ms,m1}和{ms,m3}。

图2 有向层级图

依此类推,在第3级中,存在2层,分别代表{ms,m1,m3}和{ms,m2,m3};第4级只有一层,代表{ms,m1,m2,m3},同时也表明,当数据包路由到这一层时,已经获取到所有所需的功能服务了。当数据包从第1级的第1层L1,1跨级路由到第2级的第2层L2,2,首先有{ms}⊆{ms,m3},这满足跨级路由条件;其次,L2,2层的第2列、第3列、第4列以及第5列节点都为中间盒m3的部署节点,因此通过将m3放置于该点处后,数据包可以在已获取过{ms}服务的基础上跨到L2,2层来继续获取m3的服务。

算法1为中间盒组合算法的伪代码。其中第4行表示集合J只有一个{ms}是大小为1的元素。第6行到第11行用于判断集合Qi中的所有元素与未包含的其他元素的依赖关系,若Qi中存在一个元素依赖于Qi之外的元素,则Qi不能作为J的元素,并且要求ms必须是Qi的一个元素,否则Qi也不能作为J的元素。算法1步骤如下。

输入:中间盒集合M,依赖关系depend(m,m′)∈{-1,0,1} 。

输出:M-{md}的所有满足依赖关系的子集J。

1. 获取M-{md}中的所有元素的全组合集合Q;

2. 将J初始化为含有{ms}的集合;

3. forQiinQdo

4. ifQi只有一个元素then continue;

5.k=true;

6. forminQido

7. form′ inM-{ms,md}-Qido

8. if depend(m′,m)=1 orms∉Qithen

9.k=false

10. ifk=true then

11. 将集合Qi作为J的一个元素;

12. returnJ;

算法2为构造层级图的伪代码,结合图2来说明下该伪代码中的一些符号含义。Pi是由所有J中元素个数为i个的子集组成的集合,例如,当i=2时,P2={{ms,m1},{ms,m3}};当i=3时,P3={{ms,m1,m3}, {ms,m2,m3}}。此外P2,1={ms,m1},P2,2={ms,m3},因此P3,1-P2,2=m1。节点ui,j表示第i级第j层节点。算法2步骤如下。

输入:网络拓扑图G,中间盒组合J。

1. fori=1 ton-1 do

2.Pi是由所有J中元素个数为i个的子集组成的集合;

3. forj=1 to |Pi| do

4. foruin do

6. for (u,v) inEdo

8.C[ui,j,vi,j] =C[vi,j,ui,j] =C[u,v];

9. fori=1 ton-2 do

10. forj=1 to |Pi| do

11. fork=1 to |Pi+1| do

12.m=Pi+1，k-Pi,j;

13. foruinVdo;

14. ifu是部署中间盒m的候选节点then

15. forvinNudo

17.C[ui,j,vi+1,k] =C[u,v]+C[u,m];

2.2 路由路径选择

算法3为路由路径选择的伪代码。首先通过Eppstein算法不断迭代出第k条最短路径,并对该路径进行如下判断:① 第2～3行用remainder表示当前链路带宽剩余量,并在第7～8行将链路p中的〈ux1,y1,vx2,y2〉映射为图G中所对应的边(u,v),根据这条边被路由到的次数,在remainder[u,v]中减去消耗量,当remainder[u,v]<0时,说明边(u,v)的带宽容量不够支撑路由所需,因此剔除这条路由;② 变量visited用于记录图G中的点是否已经被部署过了中间盒,代码第11行对边〈ux1,y1,vx2,y2〉进行判断是否为跨级边,若为跨级边则节点v应为部署中间盒的节点,并在第12行对该节点进行判断是否之前已经部署过了中间盒,若已经部署过了,则剔除这条路由。最终能满足以上条件的路由,则为最终最优的可行路由。算法3步骤如下。

输出:从源点到目的点的路由路径L。

2. for (u,v) inEdo

3. remainder[u,v] = capacity(u,v);

4. foruinVdo

5. visited[u] = false;

6. success =true;

7. for〈ux1,y1,vx2,y2〉 inpdo

8. 将〈ux1,y1,vx2,y2〉 映射为图G中的边(u,v);

9. remainder[u,v] = remainder[u,v] - demand;

10. if remainder[u,v]<0 then success=false;

11. ifx1

12. if visited[v]=true then success=false;

13. visited[v] = true;

14. if success=true then returnp;

15. return不存在满足条件的路由;

3 算法分析

3.1 算法正确性分析

证明取链路l上的任意一个跨级有向边〈ui,j,vi+1,k〉,ui,j位于第i级,vi+1位于i+1级,假设Pi,j为i级j层所对应的中间盒组合,Pi+1,k为i+1级k层所对应的中间盒组合,则m=Pi+1,k-Pi,j且Pi,j.⊆Pi+1,k。对于∀m′∈Pi,j,根据依赖关系的传递性和不可逆性,有m′→m或m′∞m。因此根据数学归纳法可证得定理1成立。

3.2 算法时间复杂度分析

4 实验仿真

本文仿真实验所采用的系统为Intel Celeron CPU 1005M,RAM 10 GB的Win7 64位专业版;采用Java 8作为仿真编程语言;对于混合整数线性模型(1)～(16)式,采用GLPK求解[11]。假设中间盒的部署成本服从正态分布N(μlG,σ2),其中μ∈{1,3},σ=lG/4,lG为从源点src到目的点dst的最短路径成本[12]。网络拓扑sun(|V|=27,|E|=51)、链路成本、链路带宽以及用户请求均采用SNDlib网站所提供的真实数据[13],其中用户请求选取前3条(D1,D2,D3)。对于每一条请求,随机选取网络中50%的节点作为所有中间盒部署候选点,并且源点和目的点不作为部署候选点。

设置4个中间盒{m1,m2,m3,m4},根据中间盒的依赖关系做以下仿真实验。

(1) 服务链有序:m1→m2→m3→m4。仿真实验结果见表4所列。

表4 服务链有序实验对比

(2) 服务链部分有序:m1→m2且m3→m4。仿真实验结果见表5所列。

表5 服务链部分有序实验对比

(3) 服务链无序:m1∞m2∞m3∞m4。仿真实验结果见表6所列。

表6 服务链无序实验对比

3个仿真实验中,中间盒都严格按照其依赖关系进行部署。例如在服务链为有序时,SCAEA为D1请求规划的路由为12→14→15(m1) →16(m2)→12→11(m3)→9(m4)→8,将中间盒m1部署在v15上,m2部署在v16上,m3部署在v11上,m4部署在v9上。虽然SCAEA规划的路由不能与GLPK始终保持一致,如在实验(2)的D3请求中,GLPK对数据包规划的路由方式与SCAEA的不一致,但是总体路由成本都是最低的。此外,GLPK采用的是C语言实现的一个线性规划求解器[11],而本文的算法实现采用Java编写,因此,SCAEA在该网络拓扑下还是可以较快地计算出最优解,为用户请求及时规划出最优路由。

5 结 论

本文在受中间盒依赖关系以及链路带宽约束下,研究了NFV中间盒的最佳部署位置,进而来降低总路由成本,据此提出一种精准算法SCAEA。通过实验仿真,验证了该算法具有较好的应用前景。但是本文所研究的对象是一对一的用户请求,考虑到当前视频会议、软件更新以及新闻推送等应用都是基于多播方式实现的,因此可以根据本文的研究成果进一步针对SDN/NFV多播开展深入的研究。