Network and QoS-based selection of complementary services

Guisselle A.Garcia Llinas, Rakesh Nagi

Research output: Contribution to journalArticlepeer-review


Composite services are widely popular for solving complex problems where the required QoS levels are often demanding. The composite service that provides the best utility while meeting the QoS requirements has to be found. This paper proposes a network model where many complementary candidates could be selected for each service class to improve the benefits, while the conventional model limits the selection to a single service candidate or service level per service class. The selection of services step is NP-hard because it can be reduced to a multi-constraint knapsack problem. Yet, the decision has to be reached rapidly so that it does not increase the overall workflow time. Large-size networks and problems with high restriction levels (strong QoS requirements) are the most problematic. Traditional multiple-constrained-shortest-path (MCSP) heuristics are improved in this paper using the novel concept 'potential feasibility'. When our modified MCSP heuristic algorithms are compared to the CPLEX solver, one of them demonstrates a significantly smaller average runtime. Further, it provides solutions within a 2.6 percent optimality gap on average for small networks, and a 10 percent optimality gap on average for large networks, regardless of the restriction level. Our algorithm uses a general utility function, not derived from the QoS parameters.

Original languageEnglish (US)
Article number6709772
Pages (from-to)79-91
Number of pages13
JournalIEEE Transactions on Services Computing
Issue number1
StatePublished - Jan 1 2015


  • Composite services
  • constrained shortest path problem (CSPP)
  • heuristics
  • service oriented architecture (SOA)
  • workflow optimization

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications
  • Information Systems and Management


Dive into the research topics of 'Network and QoS-based selection of complementary services'. Together they form a unique fingerprint.

Cite this