基于Q-learning的跨域服务链映射机制

2019-01-31 02:34张红旗黄睿杨英杰常德显张连成

通信学报 2018年12期

张红旗，黄睿，杨英杰，常德显，张连成

（中国人民解放军战略支援部队信息工程大学密码工程学院，河南郑州 450001）

1 引言

软件定义网络（SDN, software defined network）将复杂的控制功能从传统网络设备中剥离出来，使数据平面仅负责高速转发，而网络的控制与管理由逻辑集中的控制平面基于全局网络视图与状态进行统一决策，有效简化了网络管理[1-2]。网络功能虚拟化（NFV，network function virtualization）是针对运营商网络中网络功能静态僵化问题而提出的SDN解决方案[3-4]。NFV将以专有硬件形式部署的网络功能转变为在通用服务器上运行的虚拟网络功能（VNF, virtual network function），解耦传统网络设备的软件功能和硬件载体，减少了在网络特定位置部署中间件的开销，增加了网络设备部署的灵活性。由此，借助SDN/NFV的软件定义网络功能虚拟化（SDNFV, software defined network function virtualization）技术应运而生[5]。

作为SDNFV技术的典型应用，服务链近年来颇受关注[6]。服务链在利用NFV技术将传统网络功能虚拟化并部署在服务节点的基础上，借助 SDN的流量集中管控功能，依据用户/业务的服务请求引导流量按序经过服务节点上的 VNF实例，进而为用户/业务提供可定制的网络服务。每条服务链可看作由一个或多个 VNF实例按照既定次序连接而成的逻辑视图。因此，如何设计合理的服务链映射方法完成逻辑视图向物理拓扑的映射已成为该领域的研究热点。

文献[7]提出一种可重构的服务链映射机制，采用两阶段映射方法，分别基于物理节点的服务能力和物理链路的容量约束设计优化算法选择可映射的服务节点和路由路径，但未考虑分阶段映射过程中由于服务节点间距离过大而引入的时延开销。为此，文献[8]采用一阶段映射方法，以最大化平均资源利用率和最小化平均响应时间为目标建立服务链映射多目标优化模型，并根据网络情况和映射请求联合优化服务链映射问题。为进一步提高服务链的映射效率，文献[9]在文献[8]的基础上引入带有回溯机制的启发式算法联合优化 VNF组合和服务链映射问题，有效降低了网络整体的带宽消耗。为实现传统网络功能向VNF的平滑过渡，文献[10]研究了硬件设备和虚拟机混合场景下的服务链映射问题，基于软件工程流水线的理念，提出一种定制化的服务链映射算法。文献[11]研究了多网络服务供应商条件下的服务链映射问题，并基于整数线性规划和图分割的方法给出了解决方案。由此可见，研究人员已对服务链映射问题进行了诸多有益的探索，但是相关研究仅局限于单域条件下的服务链映射，尚未对跨域条件下服务链的映射问题开展深入细致的讨论。

国内清华大学毕军教授团队率先对SDN“东西向”问题展开研究，提出一种协作式的域间 SDN互联技术WE-Bridge[12]，并基于WE-Bridge技术构建跨洲际的域间SDN实验床[13]，解决了目前SDN的研究集中在单个自治域内采用逻辑集中的控制平面而自治域的数量呈现出超线性增长的矛盾冲突[14]。受此启发，笔者认为服务链映射问题的研究不应局限于某一特定的OpenFlow自治域内。实际中受地理位置等客观条件的影响，VNF往往由不同的供应商在各自治域内进行相应的维护和管理，而用户/业务的需求愈发呈现出多样化的趋势，因此，一条服务链可能需要跨越多个OpenFlow自治域进行映射。此时，由于各个OpenFlow自治域内网络拓扑连接信息及虚拟服务资源信息的独立性和封闭性，传统的单域服务链映射方法已不再适用。为此，本文基于SDN/NFV的典型实现方式，提出一种区域集中管理、全局协同调度的虚拟服务资源管控架构，在此基础上，建立一种有效的跨域服务链映射框架，对涉及跨域映射的服务链构建请求，以最小化映射开销为目标，设计基于Q-learning的跨域服务链构建请求分割算法进行优化求解，从而有效完成跨域服务链的映射。本文贡献主要包含以下3个方面。

1) 基于SDN的典型实现方式，提出一种分层分域的虚拟服务资源管控架构，纵向包含基础设施平面、逻辑控制平面和应用管理平面，横向包含各OpenFlow自治域、区域服务代理和全局服务代理，共同实现虚拟服务资源的区域集中管理和全局协同调度。

2) 在上述虚拟服务资源管控架构的基础上，建立一种基于轮询机制的跨域服务链映射框架。该框架下，全局服务代理采用轮询方式接受各区域服务代理上报的跨域服务链映射请求，在保证系统公平性的同时有效避免基础设施平面资源分配的冲突。

3) 针对需要进行跨域映射的服务链构建请求，设计一种基于Q-learning机制的跨域服务链构建请求分割算法，以最小化映射开销为目标，采用智能化的方法进行优化求解，实现跨域服务请求的及时响应及跨域服务链的高效映射。

2 虚拟服务资源管控架构

SDNFV环境下网络功能的硬件载体和软件功能改变了以往紧密耦合的特点，实现了虚拟服务资源的灵活管控，分离形成基础设施平面、逻辑控制平面和应用管理平面，如图1所示。

2.1 基础设施平面

传统物理网络的基础设施平面是由各种异构网络体系相互融合形成的复杂巨网络，其具有覆盖范围广、组成结构复杂的特点，要实现如此大规模的资源管理和维护是相当困难的。本文提出了虚拟服务资源管控架构，将基础设施平面划分为多个OpenFlow自治域（如图1中OPNFV-D1～OPNFV-D3），每个自治域由各自的SDN控制器和NFV编排器进行区域控制，管理和维护区域内的网络通信资源和虚拟服务资源。各个自治域之间相对独立，共同协作以实现为用户/业务的多样化服务链映射请求提供及时有效的响应。

2.2 逻辑控制平面

逻辑控制平面是上层应用管理平面和底层基础设施平面之间的“桥梁”。本文构建的SDNFV环境下的虚拟服务资源管控架构旨在实现虚拟服务资源的区域集中管理、全局协同调度。区域服务代理实时掌握本区域的状态信息（包括拓扑、虚拟资源的使用情况等），同时，接受区域内用户/业务的服务链映射请求，完成其向底层物理资源的映射。按照各自实现的功能和职责的不同，可将区域服务代理划分为SDN控制器和NFV编排器2种类型。SDN控制器负责管理对应OpenFlow自治域内的交换机，实现流量的动态牵引。NFV编排器负责管理对应OpenFlow自治域内提供VNF的X86服务器（也称服务节点），实现虚拟服务资源的动态调度。二者结合，为构建灵活的基础设施平面提供了保证。

2.3 应用管理平面

应用管理平面是位于逻辑控制平面之上的扩展平面，可根据需要进行扩充。本文构建了由全局服务代理、服务信息数据库、服务链分割算法和单域映射算法组成的管理中心以满足跨域服务链映射的需求。全局服务代理是为了实现分布式协同调度的需要，负责管理区域服务代理的加入或退出，并实时掌握域内边界节点以及域间链路的拓扑连接关系及使用情况。当出现跨域服务链映射请求时，统一协调各区域服务代理进行协同处理。服务信息数据库负责存储域内的虚拟服务资源信息及域间的状态连接信息，为算法提供计算依据。服务链分割算法是解决跨域服务链映射问题的核心，当服务链不需要进行分割时即转化为单域服务链映射问题，可采用相应的单域映射算法进行求解。

3 跨域服务链映射问题描述

在第2节的架构中，基础设施平面为满足区域集中管理、全局协同调度的需求被划分为不同的OpenFlow自治域，本节的跨域服务链映射问题研究正是基于此进行的。服务代理依据用户/业务的服务链映射需求及网络资源状态完成服务链的构建，从而实现逻辑映射需求与物理网络资源之间的有效匹配，如图2所示。

3.1 底层物理网络

如图2所示，底层物理网络被划分为DN个不同的 OpenFlow自治域（此处DN=3），可用有权无向图表示。其中，NS代表底层物理节点集合，包括域内节点集合NSi和边界节点集合NSb，域内节点集合NSi又可细分为服务节点集合NSi_S和转发节点集合NSi_F，对表示服务节点ns的I类资源的容量，代表底层物理链路集合，包括域内链路集合LSi和域间链路集合表示其带宽资源容量。依据第2节的虚拟服务资源管控架构，可将整个底层物理网络视图划分为全局视图和区域视图。全局视图用表示，描述了全网边界节点和域间链路的分布状况，而区域视图描述了每个OpenFlow自治域内的物理拓扑连接情况。

图2 跨域服务链映射问题描述

3.2 服务链构建请求

对于包含p个原子服务功能的服务链映射请求可将其抽象为一个有权无向图其中，NR为服务链中VNF实例节点构成的集合，LR为VNF实例链路构成的集合。对 ∀nr∈NR，用rvI(nr)表示VNF实例节点nr的I类资源需求；对 ∀lr∈LR，用rb(lr)表示VNF实例链路lr的带宽资源需求。

3.3 服务链映射

服务链映射问题可形式化表示如下。Mapping:，按照映射区域的不同可将其划分为单域映射和跨域映射。单域服务链映射是将VNF实例和VNF链路根据一定的约束条件及目标函数映射到某一OpenFlow自治域范围内的底层物理网络上，而跨域服务链映射不同于单域服务链映射。因为在单域映射问题中，域内的拓扑连接情况及虚拟资源状态都是已知的，而对于跨域映射，不同的OpenFlow自治域之间信息都是不对外公开的。因此，需要采取分布式映射机制，实现域间映射和域内映射的协同，有效满足映射需求，并实现网络资源的充分使用。

4 跨域服务链映射策略

针对跨域服务链映射问题的特殊性，本文提出一种基于请求分割的分布式跨域服务链映射策略。首先，在第2节虚拟服务资源管控架构的基础上建立跨域服务链映射框架，描述服务链映射的具体流程。在此基础上，基于Q-learning机制设计跨域服务链构建请求分割算法，以实现跨域服务链构建请求在域间和域内的协同映射。

4.1 跨域服务链映射框架

如图3所示，为提高服务链构建请求的映射成功率，简化处理流程，可将映射框架设置如下。

1) 用户/业务依据就近原则向区域服务代理发出服务链构建请求，区域服务代理将其转化为服务链逻辑视图，判断其需要进行单域映射还是跨域映射，并将其划归于相应的集合

3) 由于各个OpenFlow自治域中的网络信息是不对外公开的，因此跨域映射请求需要由全局服务代理完成。全局服务代理根据其掌握的全局资源信息及域间资源约束进行规划，将跨域服务链映射请求分割为多个单域服务链映射请求，并交由各区域服务代理进行处理。

4) 全局服务代理周期性地对各个区域服务代理进行轮询，只有轮询到的区域服务代理才能向全局服务代理发出跨域映射请求，以避免跨域映射请求处理出现冲突和全局服务代理发生过载。

4.2 基于Q-learning的跨域服务链构建请求分割

单域服务链构建请求的映射算法很多，这里不再赘述。本文关注的重点在于跨域服务链构建请求的映射。依据图3提出的跨域服务链映射框架，跨域映射需要被分割为多个不同的单域映射进行处理，而如何进行合理分割正是本文研究的重点。文献[15]从理论上证明了虚拟网络分割问题是非确定性多项式（NP，non-deterministic polynomial）难问题，而跨域服务链构建请求分割问题可以看作是虚拟网络分割问题的特例，因此，也难以在多项式时间内得到解决。为此，本文首先建立跨域服务链构建请求分割问题模型，然后设计基于Q-learning的智能优化算法求取问题的近似最优解。

4.2.1 模型建立

跨域服务链构建请求分割问题是指以降低跨域服务链映射开销为目标，根据各OpenFlow自治域的资源匹配状况和边界节点的相关信息，将跨域服务链映射请求分割为多个单域服务链映射请求，从而形成一套有效的服务链映射方案。

跨域服务链映射开销用Cost表示，主要包含3个部分：节点映射开销（Node_cost）、域间链路映射开销（Link_cost）和域内链路映射开销。对于一条固定的服务链，节点映射开销是一定的，不同的是承载路径不同而导致的不同链路映射开销。当分别位于两个OpenFlow自治域中的VNF实例节点间需要建立域间链路时，选择不同的边界节点会产生不同的Link_cost。因此，在某一服务链分割方案中，既需要为每个 VNF实例节点指明承担其映射的OpenFlow自治域，还需要指明经由域中具体哪一个边界节点完成域间链路的连接。由于各OpenFlow自治域的链路连接信息不会完全对外公开，且域间链路映射开销与域内链路映射开销相差较大。因此，本文着重考虑节点映射开销和域间链路开销。将跨域服务链映射的总开销Cost表示为

跨域服务链构建请求分割问题可看作是满足以下映射条件，以最小化跨域服务链映射开销为目标的最优化问题。

式(2)中的fn表示VNF实例节点映射，即把VNF实例节点映射到某个OpenFlow自治域的边界节点上，满足 VNF实例节点nr映射条件的所有边界节点构成的集合用MS(nr)表示。值得注意的是，边界节点不承载具体的 VNF实例节点映射，本文提到的将某一VNF实例节点映射到某一边界节点上仅表示将该VNF实例节点划分到该边界节点所在的OpenFlow自治域；式(3)中的fl表示 VNF实例链路映射，有权无向图GSb中边界节点i′和j′间的所有可行映射路径构成的集合用Path(i′ ,j′)表示。当VNF实例链路lr(i,j)的两个端点i和j分别映射到边界节点i′和j′上时，lr(i,j)必须映射到集合Path(i′ ,j′)中的路径上以完成服务链映射请求的有效分割。

1) 变量定义

定义1分割方案矩阵Hm×n。服务链构建请求中 VNF实例节点的数目用m表示，物理网络中边界节点的数目用n表示。如式(4)所示，矩阵项H[i] [j]的取值表示 VNF实例节点i和边界节点j之间的映射关系。

图3 跨域服务链映射框架

以图2中的请求分割方案为例，可将其分割方案矩阵表示为表1。

表1 请求分割方案的矩阵表示

定义 2链路类型变量Xi,j。其中，i和j为VNF实例链路lr(i,j)的2个端点，可以根据矩阵H的值判断VNF实例链路lr(i,j)的类型，如式(5)所示，变量Xi,j的值代表链路的不同类型。

2) 约束条件

跨域服务链构建请求分割问题需满足以下约束条件。

式(6)表示矩阵H中的每一行之和小于或等于1，因为每个VNF实例节点只能被映射到一个OpenFlow自治域。式(7)确保了 VNF实例链路的带宽资源需求不超过物理链路的带宽资源容量。

3) 目标函数

跨域服务链构建请求分割问题的求解目标找到使得服务链映射开销最小的分割方案，其目标函数Obj可表示为

目标函数Obj中的3个参数具体含义如下。

Hm×n：VNF实例节点与物理网络边界节点的映射关系矩阵。

FMm×m：服务链构建请求的流量矩阵，表示VNF实例节点i和VNF实例节点j之间的带宽资源需求。

BMn×n：连接边界节点间链路的最小单位开销矩阵，表示通过Floyd算法[16]计算得出的边界节点i和j之间所有链路的单位开销的最小值。

为便于目标函数Obj的计算，本文定义一种特殊的运算，用符号⊙表示。

由于服务链的节点映射开销是一定的，而服务链的域间链路映射开销随边界节点选取的不同而不同。因此，用常数C表示节点映射开销Objn，用表示域间链路映射开销表示VNF实例节点i映射到了边界节点u，而VNF实例节点j映射到了边界节点v。目标函数Obj中的系数α和β用于调节节点映射开销Objn和域间链路映射开销Objl的权重。

4.2.2 算法准备

强化学习是人工智能领域机器学习技术中的重要方法之一。作为一种交互式学习方法，其强调在与环境的作用中学习获得评价性的反馈信号，并据此改进行动方案以适应环境，从而达到预期的目的。

作为强化学习的典型实现方式，Q-learning算法常用于求解先验知识较少的复杂决策优化问题。如图4所示，Q-learning算法模型是一个自适应闭环控制系统。智能体Q-A gent 首先通过感知环境状态，在当前状态s的基础上依据Q值函数选择一个动作a并执行，当迁移到下一状态s′时，智能体Q-A gent 依据环境的反馈计算收益函数R(s,a)并据此更新Q值函数Q(s,a)，然后依据新的Q值和当前环境状态选择下一个动作，迭代进行直至得到问题的最优策略。

图4 Q-learning算法模型

Q-learning算法中Q值函数是状态和行为的评价值，可用瞬时回报和未来回报来表示。

其中，st和at表示当前状态和行为，st+1和at+1表示下一个状态和行为，折扣系数γ是满足0＜γ＜1的常数，用于调节智能体Q-A gent对未来回报的关注程度。

当系统处于状态st时，依据式(11)来选择行为at。

为了避免算法落入局部最优，本文采取ε- g reedy[17]的动作选取方式，即以小概率ε随机选择一个动作进行探索，以1-ε的概率根据Q值选取当前最佳动作，ε可动态改变，将其设置为其中E表示学习循环的次数。其目的在于，智能体Q-A gent在学习前期可采用随机方式进行更好地探索，而在学习后期更偏向于根据Q值指导下一步的动作选择。

当选定并执行该动作后，系统进入下一状态at+1，同时系统也得到相应的收益函数R(st,at)，可依据式(12)对Q值函数进行迭代更新。

其中， λ ( 0 ＜ λ≤ 1 )是智能体Q- Agent 的学习因子，可表示为表示经过num次行为选择后，行为at被选择的次数。如果在迭代过程中，某个行为被选中次数少，则在接下来的选择中偏向选择该行为，从而确保智能体Q-A gent拥有较好的探索特性。

在利用 Q-learning算法解决现实问题的过程中，最重要的是将一个实际的问题转化成为Q-learning算法模型并以此得到优化的策略结果。即根据所要解决的实际问题，定义环境中的状态空间、动作集合和收益函数。结合本文所提的跨域服务链构建请求分割问题，可分别将其定义如下。

定义 3状态空间S。跨域服务链构建请求分割问题的关键在于确定 VNF实例节点和边界节点的映射关系。因此，将VNF实例节点i和边界节点j组成的二元组(i,j)定义为一个状态s，如果服务链中VNF实例节点数目为m，物理网络中边界节点数目为n，则共有m×n个状态，记为SN。因此，状态空间可表示为S= {s1,s2,… ,sSN}。

定义4动作集合A。对每一个VNF实例节点i和边界节点j组成的状态二元组s(i,j)，可对其进行映射、不映射和不在映射范围3种操作，分别对应动作a1、a0和a-1。因此，动作集合可表示为

定义5收益函数R(s,a)。对某状态s(i,j)执行不同的动作a将会获得不同的收益，此处，利的式(8)计算当前方案的映射开销，取其相反数作为对应的收益，即R(s,a)= - ( αObjn+ βObjl)。

Q-learning算法收敛的本质在于Q值函数的收敛[18]。此处对算法的收敛性进行分析，将最优Q值表示为Q*(s,a)。

定理1由式(8)定义的收益函数R的值在不同系统状态下有界。

证明见附录A。

定理 2对于有界收益函数R的Q值迭代问题，学习因子0＜λ≤1，且满足

则当t→∞时，有

证明见附录B[19]。

4.2.3 算法描述

如表2所示，在上述准备工作的基础上，可将基于Q-learning的跨域服务链构建请求分割算法描述如下。需要注意的是该算法将针对某一特定的跨域服务链构建请求中 VNF实例节点与边界节点的映射关系进行说明。

算法1首先对相关参数进行初始化，随后利用ε- g reedy[17]方法指导智能体Q-A gent的行为选择，并依据式(12)进行Q值函数的更新，迭代进行，直至Q值函数收敛，从而据此为跨域服务链构建请求分割方案做出决策。

5 方案分析与评估

为全面评估本文所提跨域服务链映射策略的有效性，本文从以下两方面开展仿真实验。

1) 由于现有研究仅对单域服务链映射问题进行探讨，而未对跨域服务链映射问题开展深入研究，故现有算法都不便与本文方法直接进行比较。虚拟网络映射（VNE）问题中，有研究者专门对跨域条件下的虚拟网络映射问题进行了研究，其中，2种较为经典的算法分别为基于二元整数规划的跨域虚拟网络映射算法（LID-partition）[20]和基于人工蜂群算法的跨域虚拟网络映射算法（ABC- partition）[21]。本文分别对这两种算法进行改造，使其适用于跨域服务链映射问题，并将它们与本文所提的基于Q-learning的跨域服务链构建请求分割算法（Q-partition）进行比较，以验证本文方法的性能优势。

2) 在不同物理网络拓扑连接条件下，比较本文算法在平均分割时间和平均映射开销方面的变化，以验证本文方法（Q-partition）的适应性。

5.1 实验设置

仿真实验在配置Ubuntu 14.04 64位操作系统的Intel Core i7-6300HQ @3.40 GHz、8 GB内存的PC机上进行。以Mininet模拟器为基础，采用开源的Floodlight控制器，使用Java语言编写实验代码并利用Matlab工具对实验结果进行分析。每次实验运行50 000个时间单位。

将底层物理网络划分为10个OpenFlow自治域，每个域内用GT-ITM[22]工具生成物理网络拓扑，拓扑由50个节点组成，包括6个服务节点、40个转发节点和4个边界节点，边界节点之间采用全连接的方式，域内节点以0.5的概率相连。为评估算法的自适应性，假设跨域服务链构建请求动态到达，且服从时间单位为1 000，强度为pA的泊松过程，请求的生命周期服从均值为60个时间单位的指数分布。假设网络中有8种VNF，每种VNF有3种不同的VNF实例，每个构建请求由一个或多个 VNF实例组成，数量服从的均匀分布。为便于讨论，目标函数Obj中的系数α和β均取1，折扣系数γ取0.8。

5.2 实验结果分析

5.2.1 算法性能对比

将本文算法（Q-partition）与LID-partition算法和ABC-partition算法进行对比，几种算法域内映射统一采用文献[23]中的算法，从平均分割时间、平均映射开销和服务链构建请求接受率3个方面进行分析。

1) 对比3种算法的平均分割时间。观察当服务链构建请求长度增加时，各算法平均分割时间的变化趋势。如图5所示，3种算法的平均分割时间都随着服务链构建请求长度的增加而增加。LID-partition算法的平均分割时间要明显高于其他2种算法，且随着问题规模的增大呈指数增长，在服务链构建请求长度为 8时，平均分割时间高达

3.8× 104ms。这是因为 LID-partition算法的二元整数规划中还涉及虚拟链路的分割，其中二元变量的数目要多于另外2种算法，故计算时间较长。Q-partition算法和ABC-partition算法的平均分割时间要明显小于LID-partition算法，且随着服务链构建请求长度的增加呈线性增长，即使在问题规模较大时，也能够在可接受的时间范围内收敛。图5(b)中，Q-partition算法采用智能化的方法，不断地朝着最大收益方向调整算法的搜索方向，避免了盲目遍历全部状态空间，相较于ABC-partition算法表现出更好的寻优能力，因而具有最小的平均分割时间。

2) 对比3种算法的平均映射开销。观察当服务链构建请求长度增加时，各算法平均映射开销的变化趋势。为便于表述，对3种算法的平均映射开销进行“归一化”处理，假设一定请求长度下，某种算法的映射开销为Cost(A)，最大映射开销为Cost(M)，则可依据式(15)评估算法的平均映射开销。

图5 服务链构建请求平均分割时间

如图 6所示，3种算法的平均映射开销都随着服务链构建请求长度的增加而增加。LID-partition算法在服务链构建请求长度较小时（长度在1～4之间），就呈现出较高的平均映射开销值（平均映射开销在58%左右），而随着构建请求长度的增加，平均映射开销高达87%。是因为LID-partition算法中的虚拟链路分割是二次规划问题，因此在问题规模较大时，显著增加了映射的开销。Q-partition算法和ABC-partition算法的平均映射开销相差不大，在实验请求长度的范围内，两者映射开销均小于 25%，并且 Q-partition算法略优于 ABC-partition算法，这是因为Q-partition算法具有更加智能的寻优能力，保证了开销的最小化。

3) 对比3种算法的服务链构建请求接受率。观察当服务链构建请求强度增加时，各算法服务链构建请求接受率的变化趋势。为便于观察，将服务链构建请求强度pA分别设置为(0 ,2,4,8,16,32,64)。如图7所示，Q-partition算法具有最优的服务链构建请求接受率，这得益于本文提出的跨域服务链映射框架。该框架下，全局服务代理采用轮询方式接受跨域服务链映射请求，在保证公平性的同时，避免了基础设施平面资源分配的冲突，因此能够更好地完成服务链构建请求的映射任务。此外，基于 Q-learning的Q-partition算法能够高效地完成构建请求的映射任务，因此可以在有限时间内接受更多的服务链构建请求。

图6 服务链构建请求平均映射开销

图7 服务链构建请求接受率

5.2.2 算法适应性评估

针对本文所提Q-partition算法，在不同物理网络拓扑连接条件下，从平均分割时间和平均映射开销2个方面分析算法的适应性。

上述实验中，边界节点间采用全连接的方式进行。但应指出的是，全连接的物理网络在实际运用中并不具有代表性。参考文献[24]中的实验参数设置，本节将连接概率设置为 0.2、0.5和 1.0，分别对应topology1、topology2和topology3，体现边界节点低概率、中概率和全连接的3种方式，从而有效评估算法的适应性。

如图8所示，Q-partition算法并没有受物理网络拓扑变化的影响，拥有较好的适应性。

图8 不同拓扑下的算法稳定性

6 结束语

本文研究了 SDNFV环境下跨域服务链映射问题。提出了一种分层分域、区域集中管理与全局协同调度相结合的虚拟服务资源管控架构。在此基础上，针对跨域服务链映射问题，建立了一种采用轮询机制的请求响应框架，在此框架下设计了一种基于 Q-learning机制的跨域服务链构建请求分割算法。仿真实验表明，本文方法相较传统方法在平均分割时间、平均映射开销和服务链构建请求接受率等方面具有更好的优化效果。后续工作中将针对可靠性条件下的跨域服务链映射问题进行进一步研究。