Network and QoS-based selection of complementary services

Guisselle A.Garcia Llinas, Rakesh Nagi

Research output: Contribution to journalArticle

Abstract

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
Volume8
Issue number1
DOIs
StatePublished - Jan 1 2015

    Fingerprint

Keywords

  • 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

Cite this