摘 要： 现有服务承载网的构建方法均未考虑用户请求所属的业务类别，导致业务承载与服务供应缺少有效的串联.针对该问题，提出了一种新型的端到端服务供应模型，从承载同类别业务的角度构建服务承载网，通过在服务承载网上构建服务路径提供可定制的端到端服务.为验证模型的可行性和有效性，设计了一种基于跳数约束的服务承载网构建算法，并使用经典的Layered Graph算法构建服务路径.实验结果体现了在不同的负载压力下，跳数约束对开销、收益、接受率、路径长度等性能评价指标的影响，从而验证了模型和算法的有效性，提供了性价比最优的服务承载网构建决策.当跳数约束等于3时，取得了与跳数约束等于4或5时相近的性能，同时分别节省了约50%或75%的构建开销.
关键词： 可重构网络；元能力；服务承载网；服务供应模型；服务路径
随着互联网规模的增长以及应用范围的扩展，端系统的多样化以及新兴通信模式的不断涌现，互联网内的体系结构“僵化”[1]、可扩展性差等缺点开始逐渐显现，在互联网中增加新的功能和部署新的业务变得非常困难. 在当前互联网的体系结构中，大多数复杂的网络功能和数据通信服务被放置在位于网络边缘的端系统之上，而位于网络核心的路由器只是提供简单的存储转发服务[2]. 这种端到端的数据传输模式虽然简化了互联网的设计，但是却严重限制了其体系结构的灵活性，对新的应用需求适应性极差.
针对上述问题，可重构信息通信基础网络[3]提供了相应的解决方案：
(1)可重构网络在其体系结构中加入了对网络虚拟化技术的支持，通过在共享的底层网络之上构建服务承载网(service carrying network, SCN)的方式为用户提供服务. 现阶段对服务承载网构建问题(虚拟网映射问题)的研究[4-7]，主要考虑在资源有限的可重构网络中如何实现资源的分配，高效地将服务承载网拓扑和资源请求映射到底层网络上，但是均未考虑用户对网络功能的需求.
(2)可重构网络将网络功能分解为细粒度的网络功能单元，称之为元能力(atomic capability, AC). 利用具有可编程特性的路由器基础平台[5]，元能力可以根据需要实现或部署在可重构核心网络的任意节点上. 对于用户的请求，可重构管理服务器运行服务路由算法，构建端到端的服务路径(service path, SP)，使数据流依次经过所需的元能力实例，从而提供可定制的服务. 目前针对可重构网络服务路径构建问题(service path constructing problem, SPC)的研究尚处在初始阶段，在可编程网络、云计算、网络功能虚拟化等网络环境中，现有的研究成果[8-13]均是基于底层网络进行服务实例的部署与路径选择，均未考虑建立中间的服务承载层.
基于上述分析，笔者提出一种新型端到端服务供应模型，其核心思想是基于元能力理论，从承载同类型业务的角度对服务承载网构建问题重新建模，将服务承载网构建为虚拟化的中间抽象层，然后提出了基于跳数约束的服务承载网构建算法，并结合Layered Graph算法对该模型进行仿真验证.
在服务承载网构建问题中[4-5]，请求表示为网络拓扑的形式，链路是非有序的，节点之间只有资源需求的不同而没有顺序的差别，可重构管理服务器通过在底层网络上创建服务承载网提供端到端的服务.
当可重构网络的节点具有实现和部署网络功能的能力之后，请求可以表示为元能力序列和资源需求，体现了端到端服务多样化、可定制的特性. 服务承载网由最终的服务供应形式转变为承载同类别业务的虚拟化中间层，为服务路径构建提供一致性的网络拓扑和资源视图.服务供应的方式则转化为在服务承载网上构建服务路径来提供端到端的服务.这种新型服务供应模式的主要步骤如下：
(1)根据服务请求中的元能力需求，判断请求所属的业务类别；
(2)如果承载该类业务的服务承载网存在，则由其承载服务请求；如果不存在，则在底层网络之上创建一个满足该类业务需求的服务承载网，由其承载服务请求；
(3)在承载服务请求的服务承载网之上运行服务路径构建算法，最终建立一条从源节点到达目的节点的最优路径，使所需的元能力在该路径上被依次执行.
2.1 可重构网络
可重构网络，即底层网络描述为带权无向图
其中NS和LS分别表示底层网络的节点集合和链路集合；
和
分别表示节点和链路所具有的资源属性集合.底层网络节点nS∈NS拥有的资源属性包括：计算能力CS(nS);元能力实例集合ACS(nS)={ackS|节点nS能够提供元能力实例ackS}；元能力实例的处理时间
；使用单位节点资源需要的开销cS(nS). 底层网络链路lS∈LS拥有的资源属性包括：带宽BS(lS)；通信时延dS(lS)；单位链路资源需要的开销cS(lS). 如图1所示的可重构网络中，节点内的数字表示剩余计算能力;ac1等表示元能力实例；链路上的数字表示剩余带宽；h表示接入路径的跳数.
图1 服务供应示例
Fig.1 Example of service provisioning
2.2 服务请求
端系统的服务请求(Service Request, SR)描述为逻辑服务路径的形式，其拓扑标记为带权有向图
其中NR和LR分别表示逻辑节点和逻辑链路的集合；
和
分别表示逻辑节点和逻辑链路所需的资源属性集合. 逻辑节点∀nR∈NR需求的资源属性包括：元能力需求acR(nR)；元能力的计算能力需求μ(nR)；使用单位节点资源需要支付的开销cR(nR). 逻辑链路lR∈LR需求的资源属性包括：逻辑链路的带宽需求μ(lR)；使用单位链路资源需要支付的开销cR(lR). 服务请求所需的元能力集合
}.如图1所示，服务请求SR1、SR2中，逻辑节点内部的ac1和数字表示元能力和计算能力需求，逻辑链路上的数字表示带宽需求.
2.3 服务承载网构建问题
服务承载网描述为带权无向图
其中NV和LV分别表示服务承载网的节点和链路集合；
和
分别表示节点和链路所具有的资源属性集合.ACR所属业务类别的候选节点集合表示为
∅}.
服务承载网的构建过程分为两个步骤：
(1)从底层网络中选择候选节点集合
建立NV与
之间的映射
∀
使服务承载网的每个节点映射在不同的底层节点上.同时建立NV与之间的逆映射
∀
使服务承载网节点和底层网络节点形成一对一映射.然后为节点分配资源：计算能力CV(nV)=θCS(MN(nV)),0lt;θ≤1；元能力实例ACV(nV)=ACS(MN(nV))，元能力的处理时间dV(acV(nV))=dS(acS(MN(nV)))，单位节点资源开销cV(nV)=δcS(nS),0lt;δ≤1.
(2)在节点niV、njV∈NV之间构建链路，建立LV与P S之间的映射ML:LV→P S,∀
⊆
).其中，P S表示底层网络所有路径的集合；PS∈P S表示一条底层网络的路径；h(PS)表示路径PS的跳数
表示链路
所映射路径的跳数；BS(PS)表示路径PS的带宽,为路径上链路带宽的最小值.然后,为链路分配资源：∀nV∈NV,PS∈ML(lV)，链路带宽BV(lV)=φBS(PS),0lt;φ≤1;链路通信时延
;单位链路资源需要的开销cV(lV)=ψh(PS)cS(lS),0lt;ψ≤1.
在图1中，服务承载网链路(B′,E′)上的信息表示：带宽为25，所映射路径跳数为2，路径为(B,D,E).
2.4 服务路径构建问题
服务路径的构建过程分为两个步骤：
(1)逻辑节点映射：MN:NR→NV,∀nR∈NR,MN(nR)∈NV,acR(nR)∈ACV(MN(nR)).
(2)逻辑链路映射：ML:LR→PV,∀
⊆
的表述与底层网络中的类似.
服务路径SP定义为
SP={s,(
,Mi1),(
,Mi2),…,(
,Miω),d}.
ω为服务路径中节点的数量，Mik是节点
上逻辑节点到该节点映射的集合，定义为
}.
同时满足以下资源约束条件：
(1)∀
∅，
).
即服务路径的节点有足够的计算能力执行映射至其上的元能力实例，其中
表示节点
的可用计算能力.
(2)∀
).
即服务路径链路的带宽满足逻辑链路的带宽需求约束,其中
表示链路
的可用带宽.
2.5 评价指标
2.5.1 服务承载网构建问题的评价指标
在底层网络上构建服务承载网的开销主要由分配计算资源和带宽资源产生的开销组成，定义为
C (GV)=
cV(nV)CV(nV)+
cV(lV)BV(lV).
(1)
2.5.2 服务路径构建问题评价指标
服务路径的长度定义为对应底层路径的跳数：
).
与文献[4]类似，服务承载网在t时刻接受一个服务请求的收益定义为
R(GR,t)=
cR(nR)μ(nR)+
cR(lR)μ(lR).
(2)
服务承载网在t时刻接受一个服务请求的开销定义为
C(GR,t)=
cV(MN(nR))μ(nR)+
).
(3)
服务路径的总时延等于服务路径上元能力实例的处理时间与链路时延之和，定义为
).
可重构网络构建服务承载网之后，通过长期运营获取收益，对服务承载网而言，端到端服务供应的长期综合质量可以用以下指标度量.
(1)服务承载网的长期平均运营收益：
(4)
(2)服务承载网的长期平均运营开销：
(5)
(3)平均服务请求接受率：
(6)
(4)服务承载网的长期平均收益开销比定义为
(7)
(5)平均服务路径长度：
(8)
(6)平均服务路径时延：
(9)
式中:SRsuccess表示成功接受的服务请求.
3.1 实验环境设置
为了对所提出模型的可行性和性能进行评价，设计了基于跳数约束的服务承载网构建算法，在候选节点之间建立满足跳数约束hops的链路，并采用Layered Graph[8],简称LG算法构建服务路径，水平边权值设定为链路的h值，垂直边权值设置为1.
与文献[7]和[13]类似，可重构网络和服务请求的设置如下：底层网络拓扑采用GT-ITM工具[12]随机生成，包括50个节点和约120条链路，节点的计算能力和链路的带宽服从[500,1 000]的均匀分布,每个节点拥有随机的1～5种不同类型的元能力.为简化问题，所有链路时延均设定为10个时间单位，所有元能力实例的处理时间均设定为5个时间单位，这样LG算法求出的最短路径也是最小时延路径.单位资源开销cS(nS)、cS(lS)、cR(nR)、cR(lR)均设定为1.0;系数θ和φ设定为0.1;系数δ和ψ设定为1.0.
假设端系统服务请求的到达时间服从泊松分布，为测试算法在不同请求到达率下的表现，考虑平均100个时间单位内请求到达率的均值为4、5、6、7、8的5种情况.请求的业务类别设定为元能力ac1、ac2、ac3的任意组合，元能力的计算能力需求服从[0,25]的均匀分布，逻辑链路的带宽需求服从[0,50]的均匀分布. 每个请求的生命周期服从平均1 000个时间单位的指数分布，每次模拟仿真时间为50 000个时间单位.
3.2 实验设计
仿真实验共分为4组，对应跳数约束h取值为2、3、4、5时的场景. 对于每组实验，首先构建基于跳数约数的服务承载网拓扑GV，记录并分析GV的构建开销；然后随机生成5组服务请求，分别对应请求到达率为4、5、6、7、8的场景，用以测试服务供应质量在不同资源需求压力下的表现；最后对于每组请求，在GV上运行LG算法构建服务路径，记录并计算性能评价指标.
3.3 实验结果与分析
图2为服务承载网的构建开销对比情况.图2表明，服务承载网的构建开销随着跳数约束值的增加而逐渐增加，主要原因在于链路数量的增加导致开销增加. 当跳数约束达到某阈值时，服务承载网拓扑将成为完全图，构建开销收敛. 图3～7显示了服务供应质量的主要评价指标在不同服务承载网和不同请求到达率下的表现. 以请求到达率分别等于4和8时的情况为例，与跳数约束为2时相比，跳数约束为3时的请求接受率分别提高了约7%和18%，平均收益分别提高了约12.2%和51.8%，平均开销分别增加了5.6%和40%；与跳数约束为3时相比，跳数约束为5时的请求接受率分别提高了约0.1%和2%，平均收益分别提高了约0.1%和2.8%，平均开销分别减少了约1.9%和1.8%.当跳数约束为2时，服务承载网构建开销虽然最小，但是链路数量过少，在资源需求增长的压力下，承载能力不足的问题愈加严重，指标急剧下降，难以保证服务供应质量，不适合在请求到达率大于5的环境中使用；而跳数约束为4或5时，虽然链路数量充裕，承载能力增强，在各项评价指标中均表现较好，但是并未和跳数约束为3时的对应值拉开明显的差距，且构建开销分别增加了50%和75%，性价比低.
图2 服务承载网的构建开销对比
Fig.2 Comparison of costof service carrying network
图3 平均服务请求接受率对比
Fig.3 Comparison of average request acceptance ratio
图4 服务承载网长期平均收益对比
Fig.4 Comparison of long-term average revenue
图5 服务承载网长期平均开销对比
Fig.5 Comparison of long-term average cost
图6 服务承载网长期平均收益开销比对比
Fig.6 Comparison of long-term revenue/cost ratio
图7 平均服务路径长度对比
Fig.7 Comparison of average length of service path
笔者根据可重构网络的实际需要，提出了一种基于业务划分的新型端到端服务供应模型，根据请求所属的业务类别构建服务承载网，从而提供一致性的网络拓扑和资源视图.为验证所提出模型的可行性和有效性，设计了基于跳数约束的算法，在底层网络之上构建服务承载网，并使用Layered Graph算法在服务承载网之上构建服务路径. 模拟实验结果验证了服务供应模型和所使用算法的有效性，确定了性价比最优的跳数约束值.当跳数约束为3时，取得了与跳数约束为4或5时接近的性能，同时分别节省了约50%和75%的服务承载网构建开销.
如何在提出的服务承载网之上构建最优服务路径，对同类型业务流进行优化，是下一阶段研究工作中主要解决的问题.
参考文献：
[1] CLARK D D, WROCLAWSKI J, SOLLINS K R, et al. Tussle in cyberspace: defining tomorrow′s internet[J]. IEEE/ACM transactions on networking, 2005, 13(3):462-475.
[2] SALTZER J H, REED D P, CLARK D D. End-to-end arguments in system design[J]. ACM transactions on computer systems, 1984, 2(4):277-288.
[3] 兰巨龙, 程东年, 胡宇翔. 可重构信息通信基础网络体系研究[J]. 通信学报, 2014, 35(1): 128-139.
[4] 王子厚, 韩言妮, 林涛, 等. 可重构网络中基于中心度与拓扑势排序的资源分配算法[J]. 通信学报, 2012, 33(8): 10-20.
[5] HU Y X, LAN J L, WU J X. Providing personalized converged services based on flexible network reconfiguration[J]. Science China information sciences, 2011, 54(2): 334-347.
[6] 梁宁宁, 兰巨龙, 程国振,等. 基于拍卖博弈的可重构服务承载网动态构建算法[J]. 电信科学, 2015, 31(5):82-87.
[7] CHOWDHURY M, RAHMAN M R, BOUTABA R. ViNEYard: virtual network embedding algorithms with coordinated node and link mapping [J]. IEEE/ACM transactions on networking, 2012, 20(1):206-219.
[8] HUANG X, GANAPATHY S, WOLF T. Evaluating algorithms for composable service placement in computer networks[C]//IEEE International Conference on Commu nications. Dresden:IEEE, 2009: 1-6.
[9] TRAN K T, AGOULMINE N, IRAQI Y. Cost-effective complex service mapping in cloud infrastructures[C]//Proceedings of the IEEE Network Operations and Management Symposium. Hawaii: IEEE, 2012: 1-8.
[10] 王宗江, 杨淑慧. 基于动态信任的最优云服务选择算法[J]. 郑州大学学报(工学版), 2015, 36(4):124-128.
[11] MOENS H, TURCK F D. VNF P: A model for efficient placement of virtualized network functions[C]//International Conference on Network and Service Management. Rio de Janeiro: IEEE, 2014:418-423.
[12] LUIZELLI M C, BAYS L R, BURIOL L S, et al. Piecing together the NFV provisioning puzzle: efficient placement and chaining of virtual network functions[C]//IFIP/IEEE International Symposium on Integrated Network Management. Ottawa: IEEE, 2015: 98-106.
[13] SAHHAF S, TAVERNIER W, ROST M, et al. Network service chaining with optimized network function embedding supporting service decompositions [J]. Computer networks, 2015, 93:492-505.
[14] ZEGURA E W, CALVERT K L, BHATTACHAEJEE S. How to model an internetwork[C]//Proceedings of the 15th Annual Joint Conference on IEEE Computer Communications Societies. San Frarciso, CA,USA:IEEE, 1996: 594-602.
Abstract: Current service carrying network mapping algorithms ignored the business category of the service request,which resulted in the disconnection between the business carrying phase and the service provisioning phase. To address this problem, a novel end-to-end service provisioning model was proposed, in which service carrying networks were constructed considering aggregating service requests belonging to the same business category and customized end-to-end services were provided via establishing the corresponding service path over the service carrying network.To evaluate the feasibility and effectiveness of the proposed model, a service carrying network mapping algorithm with hop constraint was and desighed Layered Graph algorithm was used to select service path. Simulation experiments on a large mix of service requests showed the impact the hop constraint had on network performance in terms of cost, revenue, acceptance ratio, length of service path, etc. under different working load, validated the effectiveness of the proposed model and algorithms, and eventually determined the optimal value of hops. When the value of hops equaled 3, compared with the situation in which the value of hops equals 4 or 5, the achieved performance was approximately same,and about 50 percent and 75 percent cost of constructing service carrying network can be saved respectively.
Key words: reconfigurable network;atomic capability;service carrying network;service provision model;service path
收稿日期:2016-08-03；
修订日期：2017-02-21
基金项目：国家重点基础研究发展计划(“973”计划)(2012CB315901)；国家自然科学基金资助项目(61379079)；河南省国际合作项目(152102410021)
文章编号:1671-6833(2017)06-0011-06
中图分类号：TP393
文献标志码：A
doi:10.3969/j.issn.1671-6833.2017.06.003