The step-wise service matching algorithm

Our matching algorithm, shown in Figure C.3, is based on a two step approach; the first step being a simple functional matching based on input and output parameters, while the second step

STEP ONE: Input/output matching

a) create a list of all available services where input and output match the client’s needs b) if the list is empty: perform an orchestration

- if the list is still empty: failure - if the list is not empty, goto 1c

c) if we do not have QoS information about the client, return first list item, if we have the client’s QoS requirements, provide list as input for step 2)

STEP TWO: QoS matching

a) sort the services list according to the client’s QoS demands

b) if the top list item does not fulfill the full QoS requirements, perform step 1b - if result from 1b is the same as the list just evaluated in 2a: failure

- if new matches were added to the list returned from 1b, goto 2a

c) choose the service (or orchestrated service) at the top of the list, and let the client invoke it

Figure C.3 Step-wise service matching algorithm

considers the QoS needs of the client and matches it with the QoS offered by the services.

The simple parameter matching performed in step one allows for a quick elimination of services that do not fit the request at all. Once this is completed we will have a list of available services ranked according to match type, exact matches being ranked first. We then consider the QoS matching:

In order to be able to compare the QoS requirements of a user to the QoS offered by a service, a minimum amount of knowledge about the QoS parameters is required. The parameters need to be agreed upon up front, so that both user and service know which parameters will be understood by the other party, how to interpret the parameters, and how to use the parameters in an orchestration.

This means that a standardized way of describing QoS parameters will be needed before large-scale QoS support can be integrated into an operational network.

For the algorithm we are proposing in this paper, we have not created a full classification scheme for parameters, but rather concentrated on the type of information we need about the parameters, and applied this to some example parameters. Common to them all is that we, in addition to knowing the parameter name, range of allowed values and the parameter’s actual value, need to know the type of the parameter, how to evaluate the parameter and how to use that parameter in a composition. Table C.1 gives an overview of the parameter types we considered when evaluating our algorithm, along with the possible match criteria and composition calculations that we identified for our example parameters. This list is in no way a complete listing of all possible parameter types and evaluation criteria, but serves to illustrate the type of information that is required to be able to perform automatic selection and matching based on QoS.

After having done this QoS matching, we determine if the highest ranked service match found is sufficient to meet the client’s requirements. In our algorithm only exact matches that fulfill both the optional and required QoS of the client are considered a sufficient match, but it is possible to extend this to include other types of matches as well. If we can determine that a good enough match has been found, the best match found is returned. Otherwise, we enter the orchestration

Type Match Criteria Composition

Range Within, Smallest common range,

Within or same as, Added ranges,

Outside etc.

Set Full set match, Union of sets, Element in set, Intersection of sets, Does not Exist Required for at least one service,

etc.

Table C.1 QoS matching

phase, where we find new service matches by combining the simple services into more complex ones. After having populated our match list with these “new” matches, we perform the two steps of our service matching algorithm a second time to ensure that the orchestrated services are ranked correctly.

C.8 Conclusion and future work

In this paper we have presented our algorithm for automated QoS-aware Web services selection and orchestration. We have discussed how we can match a client’s QoS demands with an appro-priate available Web service in a highly dynamic environment such as a military mobile tactical network. By using a specially tailored mechanism for service advertisement distribution, we are able to provide each network node with an up-to-date view of available Web services and corresponding QoS data. Using these data as input in our novel algorithm, we are able to leverage semantic technologies to automatically choose between the available Web services based on input and output matches while at the same time satisfying QoS demands. In our experiments we have expressed QoS in a proprietary language, in order to test a proof-of-concept implementation. We have shown that it is feasible to employ semantic technology to achieve automated QoS-aware service selection. When single services do not match the requirements, performing an orchestra-tion of services in an attempt to create a new service invocaorchestra-tion flow that, when considering the aggregated QoS values, satisfies the client’s demands.

In the future, our work could be expanded in a number of ways. We are planning experiments in an actual tactical environment, now that our solution has shown promise in the lab. Furthermore, a standardized way of expressing QoS for Web services needs to be developed. The suggestions we make in this paper cannot be adopted by NATO unless one has a common understanding

as admission control, which should preferably be solved using a standard, e.g. WS-Security.

These and other issues must be addressed before one is able to create a complete, secure and interoperable system. The contribution of this paper is to provide one specific building block of such a system, i.e. the algorithm needed to match information about services and QoS to a client’s specific needs, and automatically select the “best” service according to a set of pre-defined selection criteria.

Appendix D Cross-layer Quality of Service Based Admission