【作者】 高磊；

【导师】 曾广周；

【作者基本信息】 山东大学 ， 计算机应用技术， 2010， 博士

【摘要】 工作流是一类集成业务活动并使其能够自动化或半自动化完成的计算机支持的协同工作技术,是计算机科学、自动控制科学、管理科学和先进制造等多学科领域共同关注与研究的热点问题之一,其核心是通过业务流程,协同网络中分布的计算资源和业务行为,并可进一步引申为对网络计算能力的挖掘。基于对等计算范型构造的工作流系统称为P2P工作流系统。它将工作流模型中的逻辑关系映射到一个活动及其转移规则的集合,使活动所在节点不经过中心化工作流引擎,而直接与其逻辑前驱节点和后继节点进行通信和数据交换,从而将控制流和数据流分布到每一个任务执行节点上,并在工作流网络上展现为自组织的工作流程,体现了工作流的分布特质。P2P工作流是一种去中心化的计算模式,消除了集中式工作流系统中那些由中心化控制结构造成的性能瓶颈,为大规模业务过程协同提供了一种具有高度柔性、可扩展性和容错能力的计算技术,被认为是工作流研究和应用领域最具战略意义的方向之一中心化工作流引擎的消除,使得对等点之间主要以自组织的方式形成工作流网络的控制结构,而支撑这种自治体制的核心即高效的对等点协同策略。因此,对等点之间的协同效率是决定P2P工作流系统性能的关键因素。在实际业务流程运行过程中,协同效率主要体现为工作流实例(Workflow Instance, WI)在系统中的运行时间。从这个角度考虑,基于最短运行时间的WI的最优执行路径规划(The Optimal Path Planning, OPP)成为了制约P2P工作流系统性能优化的关键问题。在没有调度中心且网络拓扑及参数动态变化的对等网环境中,OPP问题体现出三个明显的特点：1.网络中各节点的计算资源、负载状况、通信带宽和网络的拓扑结构动态变化；2.节点信息的局部可视化；3.执行路径的强指向性。具有上述特点的OPP问题标识了一类全新的路径规划问题,称为分布式最优路径规划问题(Distributed Optimal Path Planning, D-OPP),即在大规模动态网络中,根据局部信息求解具有最小执行时间的全局最优路径的问题。由于D-OPP问题的局部可视性和强指向性,WI的运行时间主要由任务的执行时间(Task Execution Time, TET)和对执行节点的搜索时间(Peer Sesearch Time, PST)构成。因此,对路径执行时间的优化问题就可以被分解为两个子问题：1.去中心化P2P工作流网络中的资源搜索问题,即对拥有所需计算资源的执行节点集合的搜索问题,以实现搜索时间最小化为目的；2.去中心化动态负载均衡问题,即在最短时间内实现去中心化的实时任务调度,以找到具有最小任务执行时间的节点,并形成优化的负载分布为目的。上述两个子问题在工作流程各个执行步中的最优解的组合,最终将拟合出D-OPP问题的全局最优解。本文重点研究了P2P工作流系统中的去中心化资源搜索和动态负载均衡的优化问题,其成果不仅使P2P工作流系统同时具备灵活的架构和优异的执行效率,而且在更普遍意义上为分布式计算资源的整合以及分布式计算模式的大范围部署提供了有力的支持。本文的主要工作包括：1.分布式最优路径规划问题(D-OPP)的形式化描述和分析。P2P工作流的主要特征在于完全分布的控制结构,可理解为工作流实例基于服务聚类,在各服务集之间依据局部逻辑约束自治的跳转过程。因此,D-OPP问题本质上具有层次性特征,包括服务集之间和服务集内部两个层次,分别对应去中心化资源搜索问题和去中心化动态负载均衡问题。本文第二章从服务聚类的角度给出了P2P工作流系统的体系结构,并在此基础上,利用Markov链对D-OPP问题进行形式化建模与分析,给出了问题最优解的总体结构,即最优的去中心化资源搜索和负载均衡算法。2.去中心化动态P2P工作流资源搜索网络研究。针对D-OPP问题的第一个子目标,研究去中心化资源搜索问题,给出具有最小搜索步数的最优解。去中心化资源搜索问题要求在没有路由中心的P2P网络环境中快速定位当前工作流程所需的服务集。对于P2P网络,结构化P2P方法较非结构化P2P方法具有更优的路由效率,因此,本文将结构化P2P的设计引入工作流系统,在P2P工作流的域间层次中,通过构建结构化P2P网络组织各服务集合,实现最优的搜索效率。本文第三章分别提出了服务寻址网络(Services Addressed Network, SAN)和基于逻辑映射码(Logic Mapping Coding, LMC)的生成图定位网络(Spanning Graph Location Network, SGLN)。SAN可看作多层CAN网络的叠加,较之当前代表性的P2P工作流网络,它有效提高了搜索效率,降低了路由带宽,获得了100%的路由精度；SGLN根据LMC将工作流程映射为P2P网络拓扑,提供了O(1)的最优路由时间复杂度,并且没有引入任何的额外路由负载以及冗余拓扑结构,同时具有多通道的并行处理能力以及较小的空间复杂度,给出了D-OPP中去中心化资源搜索问题的最优解。本文通过算法和实例分析给出了SAN和SGLN网络的时间和空间复杂度以及构建过程,并与典型的结构化P2P网络和工作流系统进行了对比分析。3.P2P工作负载均衡网络研究。对于去中心化动态负载均衡问题的解决,有两个关键点：(1)具有能够实时表达系统负载状况的基础P2P网络；(2)构建在基础P2P网络之上的最优随机负载分配算法。工作负载均衡网络为高效的去中心化动态负载均衡,提供基础P2P网络支持,同时实现对SGLN和SAN各层子网的链接,即作为服务集合域内拓扑的组织形式。本文第四章提出一种P2P随机网络,称为工作负载均衡网络(Workload Balancing Network, WBN),实现了通过随机网络拓扑映射节点的负载处理能力,当节点负载状况发生变化时网络拓扑保持稳定。大量仿真实验表明,WBN网络展现出三个特性：(1)拓扑结构的能力相关性；(2)高度的能力聚集特性：(3)独立于系统规模的小网络直径。这些特性为去中心化负载分配快速收敛到全局最优提供了直接的支持。4.去中心化动态负载均衡算法研究。针对D-OPP问题的第二个子目标,研究中心化动态负载分配问题,给出具有最小收敛步数的最优解。去中心化动态负载分配问题主要通过构造在基础P2P网络上的随机负载分配算法解决,要求：(1)在没有调度中心的P2P网络环境中实现；(2)快速收敛；(3)以大概率收敛到具有最短执行时间的最优执行节点。本文第五章基于WBN网络,提出一种启发式随机采样算法(Heuristic Randomized Sampling algorithm, HRS algorithm),称为WBN算法,给出了D-OPP中去中心化动态负载分配问题的最优解。在WBN网络上,WBN算法以节点负载比例为基础构造启发因子,通过始终随机采样具有更小负载比的节点,实现负载的实时分配。大量仿真实验表明WBN算法可以概率1将当前负载分配到最优执行节点上,使其获得最快的实时完成时间;而总体上形成正比于节点负载处理能力的最优负载分布,使系统在运行周期内获得最小的总负载处理时间；并且负载分配的期望采样步数,独立于系统规模和负载状态,相对稳定在4-4.5步,这一性能已逼近最优的中心化负载均衡。5.拓扑无关的非结构化路径规划算法研究。对于D-OPP问题,SGLN网络和WBN算法两者都是通过构造特定拓扑结构支持最优性能的实现,若对于任意的网络拓扑,目前已有的非结构化搜索和分配算法很难达到最优性能。因此,需要一种拓扑无关的非结构化路径规划方法作为对D-OPP问题最优解的补充,并且具有以下特点：(1)去中心化方法；(2)不需要维护特定拓扑结构；(3)具有优化的路径规划性能。路径规划实质上是将路由代价转化为其他形式的构造代价,从而从规划的角度看实现了优化。因此,在不能转化为拓扑构造代价的情况下,本文采用反向过程,即资源的主动发布过程,作为转化形式实现D-OPP问题的优化。本文第六章提出一种随机令牌发布(Randomized Token Distribution, RTD)算法,以大概率在较小随机采样步数内将令牌发布到需求程度较高的服务请求节点,实现了在不需要特征拓扑结构支持的情况下,使服务请求节点对目标节点的一步可达。本文通过大量仿真实验验证并支持了RTD算法的性能。6.分布式路径规划问题(D-OPP)的最优解。SGLN网络给出了D-OPP中去中心化资源搜索问题的最优解,WBN算法给出了D-OPP中去中心化动态负载均衡问题的最优解,两者结合给出了D-OPP最优化问题的完整解,使得从当前执行节点只需经过大约5跳就可以找到下一个最优执行节点(SGLN网络1跳,WBN网络4跳)。而SAN网络和拓扑无关的RTD算法可作为对最优解的有效补充。本文工作的创新点主要体现在：1.提出了一种称为服务寻址网络(SAN)的结构化P2P网络,支持优化的去中心化动态域间资源搜索。较已有的P2P网络,SAN可以为工作流系统提供更高的搜索效率,获得100%的路由精度,降低路由的通信带宽,适用于节点数目多且动态变化范围大的系统。2.提出了一种称为生成图定位网络(SGLN)的结构化P2P网络,给出了基于SGLN的去中心化资源搜索问题的最优解。SGLN基于LMC将工作流程映射为P2P网络拓扑,提供了O(1)的最优路由时间复杂度,没有引入任何的额外路由负载以及冗余拓扑结构,同时具有多通道的并行处理能力以及较小的空间复杂度。3.提出一种称为工作负载均衡网络(WBN)的动态随机网络,构建了一种称为WBN的启发式随机采样算法,给出了基于WBN算法的去中心化动态负载分配问题的最优解。WBN网络有效支持负载分配快速收敛到全局最优。WBN算法可以概率1在去中心化环境下将当前负载分配到最优执行节点,总体上形成正比于节点负载处理能力的最优负载分布,并且负载分配的期望采样步数,独立于系统规模及负载状态,相对稳定在4-4.5步。4.提出了一种随机令牌发布(RTD)算法,在不需要特征拓扑结构支持的情况下,给出了D-OPP问题的一个满意解。RTD算法可以较大概率,在较短期望采样步数(主要分布在5步左右)内,以一定的覆盖比例将令牌发布到需求程度较高的服务请求节点,实现了服务请求节点对最终执行节点的一步可达以及优化的负载分布。P2P工作流是一个涉及面很广的研究课题,本文进一步的工作主要包括：在线调度问题研究。当节点需要保存大量缓存数据时,在有限的存储空间中,对索引数据的选择策略可明显影响节点数据索引的效果,即在线调度问题。对于本文所有的搜索算法,可通过建立搜索对象的本地索引,提高搜索性能和系统的容错能力。物理拓扑与逻辑拓扑匹配问题研究。路由时只考虑经过的节点数量是不够的,比较理想的情况是用端到端的延迟来进行路径选择,即覆盖网与物理网络的拓扑匹配问题。对于本文所有的搜索和负载均衡算法,拓扑匹配的改进将有利于进一步提高P2P工作流系统的性能。更多还原

【Abstract】 Workflow is the automation of a business process, in whole or part, during which documents, information or tasks are passed from one participant to another for action, according to a set of procedural rules. Workflow applications are inherently distributed, or even decentralized. That is, workflow can be viewed as an efficient synergetic paradigm, where all kinds of computing resources distributed in the network can be organized by an automatic process to provide a consistent service. So workflow has been one of the most important domains of parallel and distributed computing during the past two decades.However, problems such as potential poor performance, lack of reliability, limited scalability, insufficient user support, and unsatisfactory system openness are largely ignored. These problems are mainly caused by the mismatch between the distributed nature of workflow applications and the centralized management which is used by the tranditional workflow systems based on client-server or migrating agent architecture. Instead, the peer-to-peer (P2P) infrastructure is used to provide genuinely decentralized workflow support, which removes the centralized data repository and control engine from the system. Consequently, both data and control are distributed so that workflow functions are fulfilled through the direct communication and coordination among the relevant peers. With the support of this approach, performance bottlenecks are likely to be eliminated while increased resilience to failure, enhanced scalability, better user support and a more open framework for service-oriented workflow. So P2P workflow systems have been recognized as one of the most strategic future directions of workflow systems.Based on the above discussion, the fact can be revealed that comparing with the centralized systems, the significantly improved performance of P2P workflow systems originates from transforming the potential bottleneck caused by centralized engine into the increased control complexity caused by the full-distributed self-orgnized architecture based on P2P networks. So the coordination efficiency among peers is the key factor restricting the performance of P2P workflow systems, and a kind of efficient peer coordination strategy is the core of supporting P2P workflow functions. The running time of workflow instance (WI) in P2P workflow system is one of the most important measurements of the coordination efficiency. From this perspective, the optimal path planning (OPP) problem which focuses on constructing the optimal running path of WI with the minimum running time is the key problem restricting the performance optimization of P2P workflow. In the P2P network with dynamic parameters and decentralized topology, OPP problem shows three obvious properties: firstly, the computing resource, load status, communication bandwidth and topology of network are dynamically updated; secondly, each peer only keeps the local view about directly connected neighbors and works with each other by means of self-organization, because for the decentralized P2P workflow systems, especially the complex systems with numerous dynamic participants, maintaining the global information in a peer is unrealistic; thirdly, according to the workflow model, there are determinate logical relationships among peers so that all of running pathes have determinate directions.These propertis mentioned above call for new approaches to a new type of OPP problem, which is refered to as distributed OPP (D-OPP) problem. In short, D-OPP problem is to find the global optimal running path from a decentralized and dynamically evolving network with large scale of peers, according to the local views. Because of the partially observable information of peers and determinate logical directions of D-OPP problem, the running time of WI mainly consists of not only the task execution time (TET), but also the peer search time (PST) which can’t be ignored. Thus, D-OPP problem can fall into two sub-problems:firstly, decentralized resource searching problem for P2P workflow systems, corresponding to optimizing PST; secondly, decentralized dynamic load balancing problem, corresponding to optimize TET. The combination of the optimal solutions of above two sub-problems at each execution step yields the global optimal solution of D-OPP problem.This study focuses on the optimization problem of the decentralized resource searching and dynamic load balancing in P2P workflow systems. These research findings of this thesis not only guarantee the outstanding performance and flexible architecture of P2P workflow systems, but also powfully support the integration of distributed computing resources and the deployment of distributed computing systems in large application scale.The main works of this thesis are described as follows: 1. D-OPP problem formulation and analysis.The main characteristic of P2P workflow is the full-distributed control architecture, which can be viewed as a transfer process of WI among all of sets of services by means of self-orgnization according to the local logic relationship, based on service clustering. Thus, D-OPP problem is inherently hierarchical, which consist of inter-domain and intra-domain of set of services, repectively corresponding to the decentralized resource searching problem and decentralized dynamic load balancing problem. In chapter 2, the architecture of P2P workflow systems is described from the perspective of service clustering. Based on the architecture, D-OPP problem is formulated and analyzed by means of Markov chain, and the structure of the optimal solution is provided.2. Research on decentralized dynamic resource searching network for P2P workflow. Aimming at the decentralized resource searching problem, give the optimal solution with the minimum steps.The decentralized resource searching problem call for a new approach to location the exact service set the workflow process requires in P2P network without any routing center. For P2P network, the structured approaches have better routing complexity comparing with the unstructured approaches. So the structured network is introduced into workflow systems to organize the service sets as structured inter-domain network so that the optimal searching complexity can be satisfied. In chapter 3, propose a service addressed network (SAN) and a spanning graph location network (SGLN) based on logic mapping coding (LMC). SAN can be viewed as the superposition of multiple CAN networks and efficiently low searching complexity and bandwidth with 100% location precision, comparing with the representative P2P workflow networks. Based on LMC, SGLN achieves 0(1) routing complexity without any extra routing load and redundant topology by mapping the workflow model into the topology of P2P network, which meets the optimal solution of the decentralized resource searching problem. At the same time, SGLN presents multiple parallel running channels and the less space complexity.3. Research on P2P workload balancing network.To solve the decentralized dynamic load balancing problem, there are two key factors:(1) the foundation network which can reflect the load status of system in real-time; (2) the optimal randomized sampling algorithms based on the foundation network. Workload balancing network satisfies the first factor mentioned above, which directly support the efficient decentralized dynamic load balancing. In chapter 4, a P2P randomized network, called workload balancing network (WBN), is proposed, which avoids the network churn by mapping capacity of peers into the topology of random graph. Extensive simulations show that WBN exhibits three characteristics:firstly, capacity relativity of topology; secondly, high capacity aggregation; thirdly, small network diameter independent on system scale. These characteristics directly support the decentralized dynamic load balancing can converge at the global optimal peers with stable short random walks.4. Research on the decentralized dynamic load balancing algorithm. Aimming at the decentralized dynamic load balancing problem, give the optimal solution with the minimum mixing time (random sampling steps).the decentralized dynamic load balancing problem is solved mainly by a randomized sampling algorithm based on the foundation network, which has to satisfying three conditions:firstly, there is no scheduling center; secondly, least sampling steps; thirdly, converge at the global optimal execution peers with large probability. In chapter 5, based on WBN, a heuristic randomized sampling algorithm (HRS), called WBN algorithm, is proposed, which meets the optimal solution of the decentralized dynamic load balancing problem. Based on WBN network, WBN algorithm is designed to randomly sample the peers with less duty ratio which is the foundation of constructing heuristic factors to distribute loads. Extensive simulations show that this algorithm will converge at the global optimal peers with probability 1 and stable short random walks about 4 expected steps in large-scale networks with a wide spectrum of load status. And the global load distribution is in proportion to the capacity of peers, which leads to the optimal system throughput.5. Research on topology-agnostic unstructured path planning algorithm.Corresponding to two sub-problems of D-OPP problem, SGLN network and WBN algorithm respectively which all belong to structured approaches meet the optimal solutions by constructing specific topologies. But for arbitrary network topology, there is no unstructured searching or load balancing algorithms meeting the optimal solutions of the problems mentioned above. So a new type of topology-agnostic unstructured path planning approaches is required, which has to satisfy three properties:firstly, decentralized approach; secondly, topology-agnostic; thirdly, the optimized path planning. In chapter 6, a randomized token distribution (RTD) algortithm is proposed. RTD algorithm achieves one hop routing from the request peers to the set of target peers on any network topology by actively distributing token which can be view as the advertisements of services to the set of peers which request the services. Extensive simulations test and support the efficiency of RTD algorithm.6. The optimal solution of D-OPP problem.SGLN network meets the optimal solution of the decentralized resource searching problem, WBN algorithm meets the optimal solution of the decentralized dynamic load balancing problem, and the combination of SGLN and WBN provides the optimal solution of D-OPP problem, which achieves 5 hops routing complexity (1 hop on SGLN network and 4 hops on WBN network) at each execution step of P2P workflow system.The main innovations of this thesis are described as follows:1-Propose a structured P2P network, called service addressed network (SAN), to provide optimized decentralized inter-domain resource searching.Comparing with the representative P2P workflow networks, SAN efficiently lows searching complexity and bandwidth with 100% location precision.2. Propose a structured P2P network, called spanning graph location network (SGLN), which meets the optimal solution of the decentralized resource searching problem of D-OPP.Based on LMC, SGLN achieves 0(1) routing complexity without any extra routing load and redundant topology by mapping the spanning graph into the topology of P2P network. At the same time, SGLN presents multiple parallel running channels and the less space complexity.3. Propose a dynamic random network, called Workload Balancing Network (WBN). Based on WBN, propose a heuristic randomized sampling algorithm, called WBN algorithm, which meets the optimal solution of the decentralized dynamic load balancing problem of D-OPP. WBN directly supports the decentralized dynamic load balancing to converge at the global optimal peers with stable short random walks. WBN algorithm will converge at the global optimal peers with probability 1 and stable short random walks about 4 expected steps in large-scale networks with a wide spectrum of load status. And the global load distribution is in proportion to the capacity of peers, which leads to the optimal system throughput.4. Propose a randomized token distribution (RTD) algortithm to provide a topology-agnostic satisfactory solution of D-OPP problem.RTD algorithm achieves one hop routing from the request peers to the set of target peers on any network topology by actively distributing token which can be view as the advertisements of services to the set of peers which request the services.Scince the P2P workflow is a topic in terms of broad research fields, the following future works are proposed to further the study started in this thesis:Online paging problem. But considering the storage of the indices of massive data in limited space, an index selecting strategy has an apparent impact on the system performance, that is, the online paging problem. For all of searching algorithms of this thesis, Local index can be created to improve the searching performance and reliability of system.Topology matching problem. This problem refers to the mismatching between the topology of overlay network and physical network. For all of searching and load balancing algorithms of this thesis, better topology matching will significiently improve the performance of P2P workflow systems.更多还原