Using Continual Verification to Automate Service Selection in Service-Based Systems

newA new, web-based intelligent proxy generator based on an adaptive model learning method is now available:
- Pre-installed on public Amazon Machine Image WB-IPGen from the us-east-1 (i.e., US East (Northern Virginia)) Amazon EC2 region)
             - As an open-source application for deployment on a local development machine here

Abstract

Over a decade of sustained research into the development of self-adaptive service-based systems
(SBSs) has had little impact on the state of practice. SBSs that select their services dynamically
in response to changes in workload or requirements may be commonplace in academic software
engineering labs, but are rarely encountered in the real world. We introduce a tool-supported
SBS engineering framework that aims to reduce this gap between state-of-the-art research and
the current state of practice by using a three-pronged approach as follows.
  1. First, our COVE (COntinual VErification) framework guarantees that the automated service
    selection complies with the SBS reliability requirements with minimal cost. This is achieved
    by using a combination of continual quantitative verification and adaptive updating of the
    SBS model that is verified at runtime.
  2. Second, COVE generates the software components that provide its model updating, continual verification
    and service selection functionality automatically. Accordingly, COVE can be used by developers
    with limited expertise in the theory underpinning its operation.
  3. Finally, the COVE development workflow resembles current SBS development processes,
    so COVE adopters need not learn a new development paradigm.
Our technical report introduces the three COVE components, and shows their effectiveness using a case study
from the telehealth application domain.

R. Calinescu, K. Johnson, Y. Rafiq (2013) Using Continual Verification to Automate Service Selection in Service-Based-Systems, Technical Report YCS-2013-484, available online at University of York

The source code of the COVE framework is available to download here: COVE-src.zip

Self-Adaptive Service-Based-System COVE Architecture




The architecture of a COVE self-adaptive SBS comprising n >= 1 operations performed by remote third-party services
is depicted in Figure above. The n > 0 COVE service proxies in this architecture interface the SBS workflow with sets of
remote service such that the i-th SBS operation can be carried out by mi ≥ 1 functionally equivalent services.

The runtime selection of the service for each SBS operation and, as in the case of traditional web service proxies, the interactions
with the selected services are handled automatically by the COVE proxies. Whenever an instance of the i-th proxy is created, it is
initialised with a sequence of (promised) service level agreements (SLAs) represent the provider-supplied probability of success and the
cost for an invocation of service sij, respectively.

The n proxies are also responsible for notifying a model updater about each service invocation and its outcome.

The COVE model updater starts from a developer-supplied initial model of the SBS workflow, and uses the COVE online learning technique
to adjust the model parameters in line with these proxy notifications. Finally, the up-to-date SBS model maintained by the model updater is
used by an autonomic manager that controls the services selected by the n proxies, to ensure that the service combination which satisfies the
SBS requirements with minimal cost is selected at all times. Accordingly, the COVE proxies, model updater and autonomic manager implement a
monitor-analyse-plan-execute (MAPE) autonomic computing loop.

A key advantage of our COVE framework is that its model updater and autonomic manager components are SBS- independent and therefore reusable
across applications, while the SBS-specific proxies are generated automatically using a COVE software engineering tool described in Section V.

COVE Experiments: Scalability of the Autonomic Manager

To evaluate the scalability and generality of our approach, we carried out a number
of experiments that assessed the overheads of executing the runtime analysis within
the autonomic manager. 

We selected the following workflows used by a number of projects in this area.

Each problem domain is outlined and a description of each service is given.
QoS requirements are given and formulated as PCTL formulas.
The workflow for each case study is formalised as a parameterised DTMC model based on the PRISM high-level statebased
language and used as input to the autonomic manager.
The parameters are replaced by the autonmic manager in accordance to the observed frequency of transition invocations
in the workflow and the reliability, and costing structure for each concrete service.

Telehealth application domain

The primary case study in our paper is a service-based system for remote medical assistance called TeleAssistance(TA) [1,2].

The system comprises the following three abstract services:

  1. Alarm Service, which provides the operation sendAlarm.
  2. Medical Analysis Service, which provides the operation analyzeData, and
  3. Drug Service, which provides the operations  changeDrug.

Depending on the region offering the TeleAssistance medical service, each of the abstract services listed above will have one ore more implementations --
concrete services offered by telecommunication provides each offering identical functionality. Our case study will be used to show the effectivity of the
Intelligent Proxy in maintaining the following QoS requirements (both reliability and performance):

QoS Requirements

The autonomic manager is used to maintain the following high-level QoS requirements:

  1. The probability that one execution of the workflow ends in a service failure is at most pR1 = 0.08.
  2. The probability that an alarm failure occurs within N = 10 executions of the workflow is at most pR2 = 0.05.
  3. The probability that an invocation of the analysis service is followed by an alarm failure is at most pR3 = 0.0002.
We formalise these requirements in probabilistic computational tree logic: teleassist.pctl
  1. P<=0.08[!(a=10)U(a=7|a=8|a=9)]
  2. P<=0.05[F(a=7)]
  3. filter(forall,P<=0.0002[!(a=10)U(a=7)],a=3)

The expected cost of a single invocation of the workflow is determined by the PCTL formula "R=?[F a=10]", relative
to the rewards structure associating a monetary value to each abstract operation, appropriate to the concrete services provided
by the user of COVE to the autonomic manager.

Formulating a parameterised DTMC model


We formulate a parameterised DTMC model comprising 11 states of the Teleassistant health application in PRISM: teleassist-dtmc.pm
The identifiers that begin with the symbol % are replaced by the autonomic manager with values appropriate to the concrete service implementing each abstract operation.

e-commerce application domain

We tested the scalability on an ecommerce application introduced in [3]. The workflow represents a system in which new or returning customers
log into an ecommerce application to purchase products. Once one or more products have been selected the customer may choose to have their purchases
shipped by an express service or a normal service. The customer logs out and their session with the application is terminated successfully .

The system comprises four abstract services:
  1. Authentication Service, which provides the operation Auth
  2. Payment Service, which provides the operation Payment
  3. Normal Shipping Service, which provides the operation NrmShipping,
  4. Express Shipping Service, which provides the operation ExpShipping.

QoS Requirements

The autonomic manager is used to maintain the following high-level QoS requirements [3]:

  1. Probability of success shall be greater than 0.8
  2. Probability of a ExpShipping failure for a user recognized as a returning customer shall be less than 0.035
  3. Probability of an authentication failure shall be less than 0.06

We formalise these requirements in probabilistic computational tree logic: ecommerce.pctl

  1. P>0.8[F(s=16)]
  2. filter(forall,P<0.035[F(s=13)],s=1)
  3. P<0.06[F s=5]

The expected cost of a single invocation of the workflow is determined by the PCTL formula "R=?[F(s=16)|(s=15)|(s=5)|(s=13)|(s=8)]", relative
to the rewards structure associating a monetary value to each abstract operation named in the ecommerce workflow, appropriate to the concrete
services provided by the user of COVE to the autonomic manager.

Formulating a parameterised DTMC model

The figure, reproduced from [3], depicts the DTMC modelling the reliability of the ecommerce application:  ecommerce.pm


Travel application domain

Our third case study is a travel assistant application whose workflow organises the invocation of services relating to accommodation booking and vehicle rental, based on
the travel planner in [4]. Requests arriving to the workflow can either be invocations to search for flights (90%) or search for tourist attractions at a specific destination (10%),
when accommodation arrangements have otherwise been made. The drive time between the hotel and the attraction is calculated and either a car (70%) or bicycle (30%) is
hired based on the distance between locations.

The workflow comprises the following five services

  1. Attraction information service, which provides the operation Attract
  2. Flight reservation and booking service, which provides the operation Flight
  3. Hotel reservation service, which provides the operation Hotel
  4. Bicycle rental service, which provides the operation Bike
  5. Car hire service, which provides the operation Car

QoS Requirements

The autonomic manager is used to maintain the following high-level QoS requirements:

  1. More than 80% of users invoke the bike rental service.
  2. Less than 25% of invocations end in failure
  3. More than 80% of people who search for attractions rent a bike
Formulated as PCTL formulae: travelassist.pctl
  1. P>0.8 [ F (s=11) ]
  2. P<0.25 [F(s=4|s=5|s=7|s=9|s=12) ]
  3. filter(forall, P>0.8[F(s=11)], s=2)

The expected cost of a single invocation of the workflow is determined by the PCTL formula "R=?[F s=13 ]", relative
to the rewards structure associating a monetary value to each abstract operation named in the travel assistant workflow,
appropriate to the concrete services provided by the user of COVE to the autonomic manager.

Formulating a parameterised DTMC model

travel assist



The figure, depicts the DTMC modelling the reliability of the travel assistant application: travelassist.pm [4]

COVE Performance

We ran experiments that considered between two and six concrete services for each of the abstract operations.
Each experiment measured the time taken to construct the autonomic manager and select the optimal concrete service
configuration in the worst-case scenario whereby all combinations of concrete services satisfied the workflow requirements.

The results of our experiments are averaged over several runs and are summarised in the figure presented below:
(The original logging output is available here: results.zip)



Bibliography

[1] R. Calinescu, L. Grunske, M. Kwiatkowska, R. Mirandola, and G. Tamburrelli, �Dynamic QoS management and optimization in service-based systems,� IEEE Trans. Softw. Eng., vol. 37, pp. 387�409, 2011.
[2] R. Calinescu, C. Ghezzi, M. Kwiatkowska, and R. Mirandola, �Self-adaptive software needs quantitative verification at runtime,� Communications of the ACM, vol. 55, no. 9, pp. 69�77, September 2012.
[3] A. Filieri, C. Ghezzi, and G. Tamburrelli, �A formal approach to adaptive software: continuous assurance of non-functional requirements,� Formal Aspects of Computing, vol. 24, no. 2, pp. 163�186, 2012.
[4] L. Zeng, B. Benatallah, A. H.H. Ngu, M. Dumas, J. Kalagnanam, and H. Chang, �Qos-aware middleware for web services composition,� IEEE Trans. Softw. Eng., vol. 30, no. 5, pp. 311�327, May 2004.

Last updated: October 31st 2013, Kenneth Johnson kenneth.johnson@york.ac.uk