Zachary Oster

Syed Adeel Ali

This work is supported in part by US National Science Foundation grants CCF 1143734 and CCF 0702758.


Zachary J. Oster, Syed Adeel Ali, Ganesh Ram Santhanam, Samik Basu, and Partha Roop

Mr. Oster, Dr. Santhanam, and Prof. Basu are affiliated with the Formal Methods Group in the Department of Computer Science at Iowa State University

Mr. Ali and Dr. Roop are affiliated with the Department of Electrical and Computer Engineering at the University of Auckland.


To provide an effective service-oriented solution for a business problem by composing existing services, it is necessary to explore all available options for providing the required functionality while considering both the users’ preferences between various non-functional properties (NFPs) and any low-level constraints. Existing service composition frameworks often fall short of this ideal, as functional requirements, low-level behavioral constraints, and preferences between non-functional properties are often not considered in one unified framework. We propose a new service composition framework that addresses all three of these aspects by integrating existing techniques in requirements engineering, preference reasoning, and model checking. We prove that any composition produced by our framework provides the required high-level functionality, satisfies all low-level constraints, and is at least as preferred (w.r.t. NFPs) as any other possible composition that fulfills the same requirements. We also apply our framework to examples adapted from the existing service composition literature.


Implementation information

We have implemented our service composition framework as a Java-based tool. Each module (NextPref, ServSelect, OrchAndVerif) is based on an existing tool developed by our group:

Case studies used in our paper

Each of these goal models has been modified from the original version cited in the paper and on this page. Our intent was to be as faithful as possible to the original semantics of each goal model while adapting the models to better demonstrate the effectiveness of our framework. These case studies are primarily meant to serve as a "proof of concept" and an initial exploration of the applicability of our service composition framework.

Case study 1: HelpMeOut service
Included in paper as running example (Figure 1)
Case study 2: Online Bookseller (adapted from Oster et al., ASE 2011)

In this case study, each leaf-level functional requirement (blue hexagon) is satisfied by exactly one available service. The choice of leaf-level requirements directly determines the services to be included in the composition.

The case study in our ASE 2011 paper is itself adapted from an example in Liaskos et al., RE 2010.

Goal model (functional requirements and NFPs):

Goal model adapted from Oster et al., ASE 2011 (which in turn was adapted from Liaskos et al., RE 2010)

CI-net (NFP preferences):

LTSs for services in repository:

LTSs for example adapted from Oster et al., ASE 2011

Behavioral constraints:

  1. !(BooksDeliveredWithReceipt) || AF(SendPrintedReceipt)
    If books will be delivered with a receipt included, then a printed receipt must be sent.
  2. A(!(BooksDelivered) U PaymentReceived)
    Books must not be delivered until payment is received.

Case study 3: Multimedia Delivery (adapted from Oster et al., ICWS 2011)

This case study provides two services for almost every leaf-level functional requirement (blue hexagon). The services for each FR provide the same functionality, but contribute differently to the NFPs under consideration. The objective in this case study is to choose component services in order to get the NFP profile that is most preferred by the user(s). As you will see in the goal-model diagram, this is a complex task even for a problem of relatively small size such as this one.

The case study in our ICWS 2011 paper is itself adapted from an example in Wagner and Kellerer, ACM Multimedia 2004.

Goal model (functional requirements and NFPs):

Download a higher-quality PDF of this goal model (approx. 14K)

Goal model adapted from Oster et al., ICWS 2011 (which in turn was adapted from Wagner and Kellerer, ACM Multimedia 2004)

CI-net (NFP preferences):

LTSs for services in repository:

Download a higher-quality PDF of these LTS diagrams (approx. 15K)

LTSs for example adapted from Oster et al., ICWS 2011

Behavioral constraint:

  1. !(w32) || (AF w61 && AF w81)
    If service w32 is used in the composition, then neither service w61 nor service w81 must appear in the composition.

Ongoing work

Because there is a lack of testbeds or large-scale case studies that fit well with our model of the service composition problem, we are currently working on characterizing the scalability of our framework with randomly-generated services and composition specifications. There are, of course, several important problems to address with such an approach, including:

Our objective is to explore the space of possible service composition problems that can be handled by our framework to develop an accurate model of its effectiveness for composition problems with different characteristics. Ideally, we will be able to develop our problem generator into a testbed that will be useful for the growing community of services scientists to empirically test their ideas about service composition.