Method and system for transitive traversal service discovery

Patent metadata

Field	Value
Publication number	US-9690546-B2
Application number	US-201414226348-A
Country	US
Kind code	B2
Filing date	Mar 26, 2014
Priority date	Mar 26, 2014
Publication date	Jun 27, 2017
Grant date	Jun 27, 2017

Abstract

A computer system includes a processor and an electronic storage. The processor provides a service composition tree of services which are offered, wherein the tree is hierarchical and specifies relationships of the services which are offered within the service composition tree to each other; translates service composition trees and the relationships of the services represented in the trees into a directed acyclic graph (DAG) that represents the service composition trees, the DAG being redundancy-free; and performs a transitive traversal within the DAG among the services represented in the DAG to locate information, within the DAG, regarding the services, in relation to each other. The electronic storage stores the DAG accessed by the processor. A method according to the above will perform a transitive traversal service discovery of a DAG that is redundancy-free, and optionally is minimal weighted. A non-transitory computer-readable medium can perform the method.

First claim

What is claimed is:

1. A computer system, comprising:
a processor, the processor is configured to:
provide a service composition tree of services which are offered, wherein the tree is hierarchical and specifies relationships of the services which are offered within the service composition tree to each other;
translate plural trees of service composition and the relationships of the services represented in the plural trees into a directed acyclic graph (DAG) that represents the plural trees of service composition, the DAG being redundancy-free; and
perform a transitive traversal within the DAG among the services represented in the DAG to locate information, within the DAG, regarding the services, in relation to each other; and

an electronic storage cooperatively operable with the processor, and configured to store the DAG,
wherein a service composition is a collection of interdependent services, each of the services in the service composition is represented as its own separate structure which is separate from other services in the service composition,
wherein links in the DAG are weighted with regard to performance characteristics of the services.

2. The computer system of claim 1 , wherein
the services which are in the service composition tree are formatted according to a service description language format, and data of the services contained in the service description language format in the service composition tree are translated into the DAG, and
a direction among nodes representing services within the DAG is prescribed from interdependencies of the services which are determined from the plural trees of service composition.

3. The computer system of claim 1 , wherein the DAG is further structured to conserve links that already associate services represented by nodes in the service composition tree with each other, interpreted through a transitive path traversal of the links.

4. The computer system of claim 1 , wherein the processor is further configured to
receive a search query that specifies a requested service;
propagate, in response to the search query, in the DAG, the search query for the requested service; and
return a query result from the search query that was propagated in the DAG.

5. The computer system of claim 1 , wherein the processor is further configured to
perform service discovery in the DAG using query filter criteria and selective conditions.

6. The computer system of claim 1 , wherein the processor is further configured to
orchestrate services in the DAG to keep a consistency in a service composition throughout the DAG.

7. The computer system of claim 1 , wherein the processor is further configured to
determine a closest path connecting involved services with each other.

8. The computer system of claim 1 , wherein the DAG G is a tuple G=(N, L, F, W) which includes:
a finite set of vertices or nodes N,
a finite set of vertices connecting transitions or links L,
a set of functions F describing a general dynamic behavior of a defined graph, such as bidirectional relationship like ancestor, predecessor or adjacency matrix, and
a weighting function W: L→ , where is a real number, of the DAG is defined consistent with the following:
for s sequential, p parallel, i iterative, b boolean, c a total amount of service calls, e kpi an empirical coefficient, and d a distance between a source node and a destination node of a traversal of a one of the service calls,

w
⁡

(
l
)

=

∑
source
destination

⁢

(

(

s
+
p
+
i
+

b
2

)

*
c
*

e
kpi

)

d
⁡

(

source
,
destination

)

.

9. A method to perform a transitive traversal service discovery, comprising:
providing, by a processor, a service composition tree of services which are offered, wherein the tree is hierarchical and specifies relationships of the services which are offered within the service composition tree to each other;
translating, by the processor, plural trees of service composition and the relationships of the services represented in the plural trees into a directed acyclic graph (DAG) that represents the plural trees of service composition, the DAG being redundancy-free; and
performing, by the processor, a transitive traversal within the DAG among the services represented in the DAG to locate information, within the DAG, regarding the services, in relation to each other,
wherein the DAG is stored in an electronic storage that is accessed by the processor,
wherein a service composition is a collection of interdependent services, each of the services in the service composition is represented as its own separate structure which is separate from other services in the service composition,
wherein links in the DAG are weighted with regard to performance characteristics of the services.

10. The method of claim 9 ,
wherein the services which are in the trees of service composition are formatted according to a service description language format,
further comprising translating data of the services contained in the service description language format in the service composition tree are translated into the DAG, and
prescribing a direction among nodes representing services within the DAG from interdependencies of the services which are determined from the plural trees of service composition.

11. The method of claim 9 , further comprising structuring the DAG to conserve links that already associate services represented by nodes in the service composition tree with each other, interpreted through a transitive path traversal of the links.

12. The method of claim 9 , further comprising
receiving a search query that specifies a requested service;
propagating, in response to the search query, in the DAG, the search query for the requested service; and
returning a query result from the search query that was propagated in the DAG.

13. The method of claim 9 , further comprising
performing service discovery in the DAG using query filter criteria and selective conditions.

14. The method of claim 9 , further comprising
orchestrating services in the

Assignees

• Software Ag

Inventors

• Ben Jemaa Jameleddine
• Dorchain Marc

Classifications

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F8/10 Primary

  Requirements analysis; Specification techniques · CPC title

• G06F17/30958

  Physics · mapped topic