基于Petri网的网络服务自动组合方法研究

基于Petri网的网络服务自动组合方法研究

徐金卯， 马丁， 宋玉， 庄雷

(郑州大学 信息工程学院， 郑州 450001)

摘要：针对网络服务的自动组合问题，提出了一种考虑端系统输入/输出请求的自动组合方法。将网络服务功能转化为Petri网中的变迁，输入请求与输出期望转化为库所；构建3种网络服务组合模型，通过对这些基础组合模型的再组合及分析，可以实现更复杂、功能更优的网络服务组合。通过T向量技术可判定是否存在满足用户需求的网络服务组合。

关键词：网络服务；服务组合；Petri网；T向量

收稿日期：2015-05-20

基金项目：国家自然科学基金项目(61379079)；河南省科技攻关项目(122102210042)；河南省科技厅基础研究计划项目(142300410231；142300410308)

作者简介：徐金卯(1987-)，男，河南信阳人，硕士，主要研究方向为下一代互联网体系结构。

文章编号：1671-6906(2015)04-0042-05

中图分类号：TP393

文献标志码：A

DOI:10.3969/j.issn.1671-6906.2015.04.011

Abstract:A Petri Net-based network service automatic composition method is proposed to composite the network service. Network service function is translated into the transition of Petri Net, which serves as the input place and out place of the corresponding input request and output expectation. Three types of network service composited models are presented, from which complexity network service composition can be realized through further combination and analysis. The T-vector can be used to determine whether there is a combination which satisfy the user’s input/output requirements.

传统的TCP/IP网络内在能力与结构相对简单，功能过于单一,网络设计者倾向于将更多的网络功能添加到网络层与传输层[1]，以适应用户不断增长的业务需求。

为了实现底层网络功能的可扩展性，协议特征以及网络功能通常被细粒度化为“网络服务”。“网络服务”一般由路由器节点实现。随着可编程路由技术的发展，路由器的种类及功能不断增加，如工作站路由器[2]、可编程路由器[3]、虚拟化路由器[4]等都可以实现网络级服务(数据传输、入侵检测、时延保障、身份验证等)，并且路由器提供的服务在网络中可以被定位，使得网络服务“中心化”的思想在技术上得到有力的支持，原本在应用层实现的功能可以“下移”至网络传输层中去实现。

但是，这些单一的细粒度的“网络服务”往往不能满足用户的请求。因此如何高效地对其进行组合，通过规则的匹配和约束，形成能够满足用户需求的服务组合，是一个亟待解决的问题，也是下一代网络体系结构适应性和可扩展性的重要体现。

当端系统对一个网络控制器下的节点发出服务请求时，网络控制器会根据端系统请求的网络服务以及这些服务的内在关系，为端系统发送的数据包指定一条“数据路径”[5]。端系统请求的服务会在这条“数据路径”上依次被所经过的节点执行，到达最终的目的节点时，所有服务都会被执行完毕，生成满足端系统请求的数据包。因此，如何自动地得出一组可以满足端系统需求的服务序列，将是本文主要研究的问题。服务序列的生成将为路由算法提供必要的依据，同时也为“数据路径”的生成提供必要的条件。

1相关工作

在国内外所进行的下一代互联网的体系结构研究中，“服务中心化”的趋势愈加明显。马萨诸塞大学的Wolf T提出的“网络服务(In-Network service)”概念，将诸如数据压缩、身份认证等服务添加到网络核心层，将其统一视为细粒度的Network service，丰富了核心网络层的功能，同时增加了网络的可扩展性[6]；美国NSF项目SILO中，将细粒度的网络功能作为可重用的构件[7]，通过构件的重用来丰富核心网络的功能；欧盟项目AutoI设计开发出一个开源框架，用来构建可靠性更高的服务组合。在国内，信息工程大学进行的国家“973”计划项目“可重构信息通信基础网络”[8]，将原有TCP/IP体系结构各层协议细粒度化为网络“元能力”，通过对元能力的组合形成“元服务”，进而满足用户所提出的业务需求。

在现行互联网体系结构以及下一代互联网体系结构中，协议和服务的组合机制都已经有所研究。可配置的协议栈可以视为组合问题的静态解决方法[9]；SILO项目中的协议栈构建模块，可以动态地构成网络服务组合。Wolf T利用AI Planning方法自动推理服务组合[6]。

本文提出了一种基于语义Petri网的服务组合方法，Petri网中的变迁用来表示网络服务可以实现的功能，库所代表网络服务的输入/输出状态。Petri网作为一种基于状态的形式化建模方法，具有直观、形象且有严格语义和数学分析等优点，可以广泛应用于描述具有并发、异步、分布、并行、非确定性等性质的系统。相对于可配置协议栈，利用Petri网进行网络服务自动组合，不需要人工参与，即可实现自动化的服务组合。对同一网络控制器下的网络服务进行Petri网的表示，避免了AI Planning方法对于每次用户需求均需逐一推理的缺陷，降低了服务方案的“构造成本”[10]。

2服务组合的Petri网建模

首先对网络服务组合以及端系统请求进行形式化定义。根据对网络服务组合及端系统请求的描述，利用Petri网对网络服务组合进行建模。最后根据Petri网的状态方程、结构性质来推导出特定的服务组合序列。

2.1网络服务组合

网络服务组合，实质上可以描述为：在网络自治域内部，路由节点可以提供一系列的网络服务；根据端系统提出的特定通信需求，网络控制器首先需要检查自治域内是否存在满足端系统通信需求的网络服务副本，然后计算出满足需求的网络服务组合序列。

网络服务组合可形式化定义为：假定S={S1，S2,…，Sn}为网络控制器域内的一系列可用网络服务的集合，服务Si(I,O)：I→O。 对于一个网络服务Si可以接收的输入I，经过网络服务Si的处理，可以产生一个输出O。

本文的目标是，针对给定的网络服务请求R，找到一组有序的网络服务组合(Sx1>>Sx2>>…>>Sxk),其中Sxi∈S(1≤i≤k)，且R⟺(Sx1>>Sx2>>…>>Sxk)。

2.2端系统请求

定义1将用户请求定义为一个二元组：Ruser=(Iuser,Ouser)。

2.3网络服务组合的Petri网表示

定义2将网络服务组合的Petri网定义为四元组：PN=(P,T；F,M)。

(1)P={p1,p2,…,pn},pn∈I∪O

P为所有库所的集合，在网络服务的功能模型中，表示网络服务的输入状态和输出状态，即P⟺Iuser∪Ouser。

(2)T={t1,t2,…,tn},tn∈S

T为所有变迁的集合，在网络服务功能模型中，表示网络服务所具有的一种可以为用户提供的功能，即T∈S。

(3)F⊆(P×T)∪(T×P)

F为P与T之间的弧集，称为Petri网的流关系集合。

(4)M：P→{0,1,2,…}

M为库所元素对应的标记函数，M0记为P上的初始标识。

2.4Petri网的状态方程、结构性质

定义3Petri网的网状结构可以利用关联矩阵来表示。

(1)C:P×T→Z，矩阵元素为C(si,tj)=C+(tj,si)-C-(si,tj)。该矩阵C是以P×T为序标集的矩阵，矩阵C称为网系统的关联矩阵；其中C+(tj,si)是从变迁tj到它的输出位置si的弧的权值；C-(si,tj)是从变迁tj的输入位置si到变迁tj的弧的权值。

(2)V={v1,v2,…,vn},vn∈N。以库所集P为序标集的列向量V:P→Z叫作网系统的S_向量，Z为整数集。在网络服务组合模型中，该向量代表了一系列网络服务输入端口或者输出端口的状态。

(3)∃U={u1,u2,…,un}(un∈N)，M0+C·U=M；以变迁集T为序标集的列向量U:T→Z叫作网系统的T向量。

可以将M0[α>M这一事实写成等式M0+C·U=M，其中α是把M0变为M的变迁序列。这里将α定义为将初始用户请求序列M0转化为用户期待输出序列M的一系列网络服务处理序列。

3网络服务的自动组合模型

这里定义3种常见的网络服务组合模式：顺序组合、并行组合、冲突组合。通过对这3种网络服务组合规则进行再组合，可以得到更复杂、功能更优的网络服务组合。

单一网络服务在Petri网中的具体模型如图1所示。

图1　单一网络服务

如果存在一个满足网络服务输入操作的用户请求，可以利用Petri网将其转化为一个输出。将这一规则称之为网络服务ti的使能条件。

3.1网络服务的顺序组合

在满足规则1的条件下，网络服务ti、tj的组合方式为顺序执行，表示为ti·tj，即执行完ti后才能执行tj，如图2所示。

规则1∃ti,tj∈T，p[ti>p｀∧p｀[tj>∧┐p[tj>。

图2　顺序组合

3.2网络服务的并行组合

在满足规则2的条件下，网络服务ti、tj的组合方式为并行执行，如图3所示。

图3　并行组合

3.3网络服务的冲突组合

在满足规则3的条件下，网络服务ti、tj的组合方式为冲突执行，如图4所示。

规则3∃ti,tj∈T，M[ti>M1⟹

┐M1[tj>∧M[tj>M1⟹┐M1[ti>。

图4　冲突组合

在这种情况下，网络服务ti、tj组合的关系是冲突关系，即ti、tj之中只要有一个发生，就会导致另一个无法触发，这种关系可表示为ti/tj。在输出库所后，各增加一个变迁，使冲突状态下的网络服务ti、tj到达一个“ti/tjFinished”库所。

根据网络服务模型S=，网络控制器可以感知到节点内网络服务的集合，对于节点内的每一条网络服务的描述，都可以将其对应建模为Petri网中的一条规则。同时，将网络服务对应的输入、输出请求建模为库所，根据节点内的可用网络服务以及这些网络服务的相互关系(如上述所列的顺序、并发、冲突关系)，并结合关联矩阵，把整个节点内的网络服务建模为一个Petri网。

在得到节点内的Petri网模型之后，可以根据用户的请求，通过求解T向量得到的服务组合变迁序列，即可得知该节点内是否存在能够满足用户需求的服务序列。然后根据Petri网的常用分析方法，进行可达性分析，得到具体的网络服务的执行步骤，即可以得出一个网络服务组合序列，满足用户的需求。

4示例

在下一代互联网中，用户对网络的安全性、可用性、异构终端的支持等要求越来越高。这里通过一个实时加密视频聊天的例子来说明基于Petri网的自动服务组合过程，如图5所示。

图5　视频聊天数据传输过程

由图5可以看出，网络控制器可以接收端系统的输入请求，为用户自动组合网络服务，产生满足用户期待的输出需求。以上示例中，核心网络的路由节点能够提供的可用网络服务如表1所示。

表1　可用网络服务

根据上一节的建模规则，对于上述所列网络服务，将输入、输出端口以及网络服务分别建模为Petri网模型中的库所和规则，如下：

P1:Type-video(HDTV-1080P)；转码请求;

P2:Unencrypted；加密请求;

P3:Type-video(H.263)；转码请求完成;

P4:Type of encrypted；加密请求完成;

P5:t3/t4finished；

P6:RTP request；RTP请求；

P7:RTP packet；RTP封装完;

P8:end；终结状态;

t1:Transcoder,HDTV→H.263;转码网络服务；

t2:EncrypTion,uncrypTed||Type of video→Type of encrypTed;加密网络服务；

t3/t4:→finished;

t6:RTP，t3/t4||real-Time quest→RTP packet;RTP协议；

t5/t7:→finished;

根据上述规则列表，可以得出该网络服务集合的Petri网关联矩阵A。利用关联矩阵，可以得到本次网络服务组合的Petri网模型，如图6所示。

图6　Petri网模型

此次服务请求端系统向网络控制器发送输入请求与期待输出，如表2所示。

表2　用户输入/输出

网络控制器在接收到端系统服务请求之后，首先要进行服务规格验证、语义映射两部分工作，然后再进行服务选择以及服务组合。本文着重对后两部分机制进行研究。

首先，对网络服务输入请求进行形式化处理：Ruser=(Iuser,Ouser)，Iuser=(Type-video(HDTV-1080P)，Unencrypted，RTP)，Ouser=(Type-video(H.263)，Type of encrypted，RTP packet)。

与此同时，网络服务器会加入一些必要的基础传输服务来保证数据传输的完成，例如P协议、UDP协议、PPP协议等。

对于用户请求Iuser=(Type-video(HDTV-1080P)，Unencrypted，RTP)，进行语义映射之后得到Iuser=(1,1,0,0,0,1,0,0)T请求序列；序列中的“1”表示对P1、P2、P6库所赋予Token，从而激活这3个库所所对应的网络服务。对于用户期望输出序列Ouser=(Type-video(H.263)，Type of encrypted，RTP packet)，进行语义映射之后得到Ouser=(0,0,0,0,0,0,1)；序列中的“1”表示终结状态。

通过状态方程Iuser+Aα=Ouser计算可知，α=(1,1,0,1,0,1,1)T。从α的计算结果可知，变迁t1、t2、t4、t6、t7触发。通过可达树的分析(这里从略)可得到变迁序列为t1·t2·t4·t6·t7。

进一步对该Petri网进行多次不同服务请求，如表3所示。

表3　用户请求数据

通过服务请求测试样例可以得知，端系统提出不同的服务请求时，该模型均可以成功地计算出准确的变迁序列。当端系统提出的业务需求不合法时，如没有请求转码服务，而期望输出要求数据被转码，系统会计算出不可读的变迁序列，并返回错误的结果。

5结语

本文以Petri网为工具，针对下一代互联网中的网络服务组合问题，利用Petri网对其进行建模，定义了3种网络服务的组合方法，并对网络控制器域内的服务进行建模，实现网络服务的自动化组合。在用户提出需求后，能够准确地计算出满足用户需求的服务组合，自动生成服务序列。下一步工作可以根据网络服务的特点在T向量算法上进行改进，找到更加行之有效的算法；也可以在网络服务Petri网的结构上做出优化，根据网络服务功能结构的分类，构建出结构更加合理的Petri网。

参考文献：

[1]Blumenthal M S, Clark D D. Rethinking the Design of the Internet: The End-to-End Arguments vs. the Brave New World[J]. ACM Transactions on Internet Technology (TOIT), 2001, 1(1): 70-109.

[2]Hutchinson N C, Peterson L L. The X-kernel: An Architecture for Implementing Network Protocols[J]. IEEE Transactions on Software Engineering, 1991, 17(1): 64-76.

[3]Ruf L, Farkas K, Hug H, et al. Network Services on Service Extensible Routers[M]. Berlin:Springer, 2009:53-64.

[4]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.

[5]Shanbhag S, Wolf T. Automated Composition of Data-path Functionality in the Future Internet[J]. IEEE Network, 2011, 25(6): 8-14.

[6]Wolf T. In-network Services for Customization in Next-generation Networks[J]. IEEE Network, 2010, 24(4): 6-12.

[7]Dutta R, Rouskas G N, Baldine I, et al. The SILO Architecture for Services Integration, Control, and Optimization for the Future Internet[J].Communications International Conference on IEEE, 2007,3(1): 1899-1904.

[8]兰巨龙, 程东年, 胡宇翔. 可重构信息通信基础网络体系研究[J]. 通信学报, 2014, 35(1): 128-139.

[9]Braden R, Faber T, Handley M. From Protocol Stack to Protocol Heap: Role-based Architecture[J]. ACM SIGCOMM Computer Communication Review, 2003, 33(1): 17-22.

[10]王忠杰,徐飞,徐晓飞,等. 支持大规模个性化功能需求的服务网络构建[J]. 软件学报,2014(6):1180-1195.

(责任编辑：张同学)

Study on a Petri Net-Based Network Service Automatic Composition Method

XU Jin-mao, MA Ding, SONG Yu, ZHUANG Lei

(Zhengzhou University, Zhengzhou 450001, China)

Key words:network service; service composition; Petri net; T-vector