Network based service composition with variable conditions

Network based service composition with variable distance conditions may be provided. A workflow definition may be received and a network topology may be built based on the workflow definition. Relational data may be received and a network instance may be built based on the network topology and the distance measurement. A plurality of network instances may be built, for example, for different distance conditions. One or more paths may be determined for a pair of services based on one or more of the network instances.

FIELD

The present application relates generally to computers and computer applications, and more particularly to computer-implemented service operations and programming interfaces, e.g., World Wide Web (Web) services and Web application programming interfaces (APIs), and compositions thereof.

BACKGROUND

The current service composition approaches lack a mechanism to identify and efficiently use relevant services or process workflows that span multiple services. This problem may arise generally as a result of two main factors: First, composition approaches are not aware of the existence of the relevant services and workflows from which to compose the service composition; Second, composition approaches do not know how to use the services or workflows, while considering the possible set of best practices associated with the services or workflows.

BRIEF SUMMARY

A computer-implemented method and system of providing a network-based service composition may be provided. The method, in one aspect, may include receiving a plurality of workflow definitions. A workflow definition may comprise computer-implemented service operations and relational flows that connect the computer-implemented service operations. The method may also include building a network topology based on the workflow definitions. The method may also include receiving distance measurements that measure distance from a computer-implemented service operation to another computer-implemented service operation, the distance measurements determined according to a selected metric. The method may also include building a network instance based on the network topology and the distance measurements.

In another aspect, the method may include receiving identification of at least two computer-implemented services. The method may also include determining a shortest path between the two computer-implemented services based on the network instance. The method may also include retrieving, from the workflow definitions, workflow snippets that form the shortest path. The method may also include constructing the workflow snippets into a new workflow.

A system of providing a network based service composition, in one aspect, may include a memory device and one or more hardware processors operatively coupled to the memory device. One or more of the hardware processors may be operable to receive a plurality of workflow definitions, a workflow definition comprising computer-implemented service operations and relational flows that connect the computer-implemented service operations. One or more of the hardware processors may be further operable to build a network topology based on the workflow definitions. One or more of the hardware processors may be further operable to receive distance measurements that measure distance from a computer-implemented service operation to another computer-implemented service operation, the distance measurements determined according to a selected metric. One or more of the hardware processors may be further operable to build a network instance based on the network topology and the distance measurements, and store the network instance in the memory device.

In one aspect, one or more of the hardware processors may include a search engine operable to receive identification of at least two computer-implemented services. The search engine may be further operable to determine a shortest path between the two computer-implemented services based on the network instance. The search engine may be further operable to retrieve from the workflow definitions, workflow snippets that form the shortest path. The search engine may be further operable to construct the workflow snippets into a new workflow.

DETAILED DESCRIPTION

A system, method and/or techniques in the present disclosure in one embodiment may utilize network information around Web services to foster service composition. In the present disclosure, an embodiment of a system, method and/or technique may use historic workflow data and custom conditions for distance measures to obtain such network information. An embodiment of a system, method and/or technique may then use this information to propose new workflows that comprise a set of desired services. Services, for example, can be of diverse type, spanning Web Services Description Language (WSDL)/Simple Object Access Protocol (SOAP)—based services and Representational State Transfer (REST) services. By leveraging a broad set of historic workflows, the proposed workflows contain services and usage patterns of services and/or workflows, and are able to address or incorporate best practices (e.g., customize commonly used services and workflows in a particular community, among particular group of users, and in particular patterns), which may otherwise be missed in composition.

In one aspect, a system, method and/or technique of the present disclosure may provide a search engine capability for finding Web services and/or interfaces on the Internet.

An aspect of an embodiment of a system, method and/or technique may start by building a network topology from existing service definitions and historic workflow definitions. This topology may be then transferred into a single or multiple network instances, each using any of a set of proposed conditions or criteria, for example, referred to as distance conditions or measures. These measures, for example, consider the number of appearances of an edge in the provided historical workflows as weights. In one embodiment, the first two steps of a system, method and/or technique outlined above, may be performed offline once. Next, in an online phase, the derived network instance may be used to propose suited workflows for given tasks. Tasks are expressed in terms of a set of services (e.g., two services or more) to be used. In one embodiment, for the service network reflecting the desired distance measure, the shortest path between the nodes representing these services is calculated. In one embodiment, the historic workflows contributing to this path are extracted and combined to form an overall, proposed workflow. For instance, a new workflow connecting two services may be identified that crosses the least number of services, crosses the least number of existing workflows, or incurs the least cost.

Web services are used in Software-as-a-Service (for example, in API graph), mobile technologies, cloud computing, and service automation. Cognitive computing, for example, also may include Web services, e.g., for recommending and composing services. For example, a workflow generated as output according to an embodiment of the present disclosure may be treated as inputs to a placement algorithm that may physically place components in a computer environment, e.g., cloud environment. For example, in that scenario, the workflow output may control physical placement or migration of computer components. In one aspect, a system, method and/or techniques of the present disclosure address a design of a system and automatically creating an appropriate workflow. A system, method and/or techniques of the present disclosure in one embodiment may generate new workflows at design time based on knowledge of other existing workflows. Existing workflows may be used to derive a network, for example, without requiring semantic annotation.

A system, method and/or techniques of the present disclosure may provide a network based service composition, for example, for both WSDL and REST services, for example, utilizing variable conditions or criteria, e.g., distance measurements for determining the compositions. The system, method and/or technique of the present disclosure may be extended to generic tasks and solutions. In one aspect, a system, method and/or techniques of the present disclosure may derive a network made up of services and their linkages from a collection of existing workflows. A graph in one embodiment of the present disclosure represents relationships among services. Edges of the graph may be derived from historic workflows and may represent data or control flow. In this way, a global map from existing workflows or service compositions (e.g., obtained from workflow repositories) may be built, for example, considering both data and control flow, and considering quality of service (QoS) and other metrics for composition. The connectivity in the map may be derived from past usage and may reflect best practices. The map may also reveal cross-workflow connectivity.

FIG. 4shows a network of services such as Web services and/or Web APIs on one embodiment of the present disclosure. The Web services and/or Web APIs402a,402b,402c,402nmay exist in the Internet, for example, and may be located at different computers or processors404a,404b,404c,404n. The Web services and/or Web APIs402a,402b,402c,402nmay be hosted by different companies or enterprises, providing a physical network of services over a network. Invoking a service (e.g.,402a) hosted by an enterprise in one or more computers (e.g.,404a) may be actuated by sending or transmitting a hypertext transfer protocol (HTTP) request with input content via a communication network (e.g., the Internet)408from a user computer or device (e.g.,406). The service (e.g.,402a) returns an HTTP response with output content.

Distance between the nodes in this network may be derived and an optimal path between the nodes in this network may be computed. For example, given a collection of workflows made up of services, a combined network may be derived that is made up of services and their linkages. Given a pre-defined relational data or distance measurement, the distance between services in this network may be derived from the distance between these services in individual workflows. Given two services, an optimal path may be computed with the pre-defined relational data or distance measurement from the network, in which relationship or distance between any pair of services has been computed.

In one embodiment, a distance measurement may be determined as follows: if two services are adjacent (invoked one after another) in any workflow, the distance between the two services may be measured as being 1; or, if two services are reachable in any workflow, the distance between the two services may be measured as being 1. The distance between two services may be computed as 1 divided by the number of occurrences where the two services are adjacent to each other in all workflows. According to this metric, the more occurrences there are of a pair of services directly connected to one another, the shorter the distance. In one embodiment, the function is reciprocal, so the first few such occurrences contribute more to reducing the distance than subsequent occurrences. If there are no such occurrences, the distance is infinite. In one embodiment, the domain of this metric is between 0 and 1 (excluding the infinite case), which makes it possible to sum the distances of different pairs of services without being skewed by the distance of a single pair.

In one aspect, the distance may be defined on nodes instead of edges, for example, the value that represents the cost of using that particular service. As another example, the distance may be defined on nodes rather than edges, for example, based on the value that represents the quality of service (QoS) value of using that particular service. QoS may be associated with invocation time, reliability and other factors.

In one aspect, services may include general tasks and workflows may include general solutions including many tasks.

FIG. 1is a flow diagram illustrating an overview of a method of a framework for composing a network-based service in one embodiment of the present disclosure. Workflow definitions and service flow definition102that may include a collection of past workflows may be obtained, and at104, service network topology is built based on the collection of past workflows. A service definition is a description of an individual service, which may include the inputs and output schema of the service and service level agreement (SLA) properties. A workflow definition is a description that captures the composition of a set of services, including the control edges, and conditions under which the edges are traversed. A system and method of the present disclosure may utilize workflow definition as well as service definition.

Workflow definition may be generated explicitly or implicitly. For example, when a user uses multiple services in a given sequence, the user is creating a “workflow”. Online workflow repositories may allow a user to submit his/her workflow definitions and store them. Workflow definition may be received or harvested from one or more of such repositories. In another aspect, workflow definition may be implicit. For example, a workflow may be retrieved from a sequence of service invocations. This sequence may be embedded in a computer program, or a textual description from a message, a blog, or the like: for instance, a blog may state that “a developer built an application that first invokes A, and then invokes B, and finally invokes C”). Such implicit workflow may be retrieved by performing data mining analysis and/or natural language processing analysis to create workflow definition of services.

Relational data or distance measurements may use workflow definition. Some distance measurements may use the service definition information. For example, there may be a distance measurement that favors services that have better SLA guarantees. Services and operations may be represented as nodes and connections between individual workflows may be represented as edges connecting the nodes. For instance, the edges of the nodes may represent relational flow between the nodes, for example, functional, control or data flows between the nodes. As another example, the nodes may represent service operations and a directed edge may represent a data link between two operations in a workflow.

Relational data also referred to as distance measurements computed between the edges106may be received and used to build a network instance at108from the network topology built at104. For example, one or more service network instances may be derived from the service network topology. In one embodiment, the service network instance is built as a graph that is the union of the graphs in the input workflows. The edges of this graph are annotated with the relational data (e.g., distance measurements) computed above. From the same network topology, each network instance may be associated with a different relational data or distance measurement on edges. For instance, a separate service network instance can be created for each relational or distance condition (e.g., distance measurement metric or criteria). The service network instance may be stored in one or more storage or memory devices. Each network instance may share the same topology but has a different data or measurement on edge weights. Edge weights may be derived from individual workflows that form this service network.

FIG. 2is a diagram illustrating an example network topology built from workflows and an example network instance built from the network topology in one embodiment of the present disclosure. In the example shown inFIG. 2, there are four services A, B, C and D, and three workflows A→C→B (202), D→C (204), and A→C (206). A network topology208is built from the three workflows202,204,206. In this example, the network topology208includes the union of all three workflows202,204,206. Starting from this network topology208, a network instance210may be built, e.g., by adding distance values to the directed edges. In the example shown inFIG. 2, the following distance measure is computed and used: 1/(number of occurrences where the two services are adjacent to each other in all workflows). For example, the directed edge A→C occurs in two workflows (A→C→B (202), and A→C (206)), therefore the distance is 1/2=0.5. As another example, the directed edge C→A does not occur in any workflow, therefore the distance is 1/0=∞.

Referring toFIG. 1, given two nodes110representing, for example, two services (e.g., Web services), a path between the nodes may be determined. For example, to find a path between any two services, based on one distance measurement, the network instance associated with that measurement may be used. For example, in one embodiment of the system and method of the present disclosure, there is a separate service network instance for each distance measurement. When finding a path between a pair of services based on a given relational data (e.g., distance measurement), the corresponding service network instance is used. For example, a user input query of two nodes and a given distance condition may be received for determining the shortest or optimal path between the two nodes based on the given relationship condition. At112, the path with the shortest distance may be calculated. The path is calculated based on the service network instance built with the “shorted distance” distance measurement. For example, a known shortest path graph algorithm may be used to compute the path based on the distances in the given service network. At114, path snippets are retrieved from individual workflows (e.g., received at102) and are stitched. If there are multiple available snippets, several options are available, e.g., including choosing the most common snippet, or the one from the most popular workflows. Implementation details may be embedded in individual workflows such as how a pair of adjacent services in a workflow are wired, e.g., mapping of the output parameters of one service to the inputs of another, any data transformations therein, the protocol used (SOAP, REST, and/or others), and how access credentials are passed. Only topology and distance information may be extracted to the network instance in one embodiment.

Identification of at least two nodes may be received, e.g., at110, via a computer-implemented user interface that allows a user to enter inputs. A distance condition may also be received from user input, for example, based on which a network instance is selected. In another aspect, if a distance condition is not input, the methodology of the present disclosure may compute paths for each distance condition or criteria. A search engine browser or like user interface may be provided for receiving inputs.

As described above, a method in one embodiment receives workflows {w1, w2, . . . , wn} as input. Each workflow wi is a graph {Ni, Ei} in which Ni is the set of nodes (services/operations) and Ei is the set of links between two nodes. The method may also receive service network topology SN={N, E}=w1+w2+ . . . +wn={N1+N2+ . . . +Nn, E1+E2+ . . . +En} as input. In one embodiment, the nodes and edges in the service network include a union of the nodes and edges in the individual input workflows. The method also receives as input distance measurement, DM. The method in one embodiment outputs a network instance.

Different algorithms may be used to measure distance, DM. In one embodiment, the distance measurement may be computed offline and used in computing the optimal path between a pair of given services.

For example, for shortest distance DM, in any workflow wi, D(nij,nik)=1 if there is an edge eijk; D(nij,nik)=infinite otherwise. This DM algorithm can find the shortest route between any two nodes.

Another example DM may include the number of least transfer. In any workflow wi, D(nij,nik)=1 if nij can reach nik in wi; D(nij,nik)=infinite otherwise. This DM algorithm can find the least transfer route between any two nodes.

Still another example DM may include shortest weighted distance. In any workflow wi, D(nij,nik)=1 if there is an edge eijk; D(nij,nik)=infinite otherwise. Each edge can be assigned a weight with a special meaning. For example, to calculate the most frequently used path: D(nj,nk)=1/Σi{D(nij,nik)=1}. The summation counts the number of times a pair of services are adjacent in the input workflows. Therefore, in this distance measurement, the more such occurrences, the shorter the distance.

Other distance measurements can be defined. Optimal path can be calculated using shortest path algorithm, for example, using known algorithms from graph theory to compute the shortest path between a pair of nodes.

Extension may be implemented based on duality. In the above distance measurement computations, the distance measurements have assigned weights to the edges of the service network graph. In another embodiment, weights on the nodes may be assigned. Known graph theory algorithms that compute the shortest distance based on node and/or edge weights may be used to compute shortest path, e.g., also based on node weights. Duality 1 example: in a network graph <N, E>, weight can also be defined on nodes N, rather than edges E. Nodes represent services which have different value (e.g., price, QoS, and/or other). Different distance measurements can be based on the value (e.g., price, QoS, and/or other). This technique may find an optimal service chain with best value (e.g., price, QoS, and/or other).

Distance calculation is similar to the case in which weights are defined on edges.

Duality 2 example: rather than a task network, a data-flow network <N, E> may be built where N is the set of data items, E represents the data flows. Distance may be defined on either nodes or edges.

In one aspect, the output (e.g., the new workflow having shortest or optimal path) that is computed in online phase, is transmitted to the user who queried using two services (e.g.,FIG. 1, 110). This output workflow, with one or multiple paths, forms the recommendations sent to one or more users upon request. The workflow, for instance, defines the transition among different services, for example, transitioning of executing of one service to a next service in a computer network. Users may run one or many of the workflows with or without modification. The workflows provide one or more services, which the user may run in the given sequence(s). The recommended workflows represent the “optimal execution” according to a given criteria or condition, for example, the number of services, cost, popularity. Executing the workflow(s) in the given sequence(s) in one aspect controls the routing of invocations based on the path. A physical workflow engine, executable on a computer processor, may read the new workflow (workflow definition) and control the routing based on the definition.