A Scalable Approach for QoS-Based Web Service Selection

Mohammad Alrifai, Thomas Risse, Peter Dolog, Wolfgang Nejdl

Research output: Contribution to journalConference article in JournalResearchpeer-review

45 Citations (Scopus)

Abstract

QoS-based service selection aims at finding the best component services that satisfy the end-to-end quality requirements. The problem can be modeled as a multi-dimension multi-choice 0-1 knapsack problem, which is known as NP-hard. Recently published solutions propose using linear programming techniques to solve the problem. However, the poor scalability of linear program solving methods restricts their applicability to small-size problems and renders them inappropriate for dynamic applications with run-time requirements. In this paper, we address this problem and propose a scalable QoS computation approach based on a heuristic algorithm, which decomposes the optimization problem into small sub-problems that can be solved more efficiently than the original problem. Experimental evaluations show that near-to-optimal solutions can be found using our algorithm much faster than using linear programming methods.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume5472
Pages (from-to)190-199
ISSN0302-9743
DOIs
Publication statusPublished - 2009
EventService-Oriented Computing - ICSOC 2008 Workshops, ICSOC 2008 International Workshops - Sydney, Australia
Duration: 1 Dec 20085 Dec 2008
Conference number: 6

Conference

ConferenceService-Oriented Computing - ICSOC 2008 Workshops, ICSOC 2008 International Workshops
Number6
CountryAustralia
CitySydney
Period01/12/200805/12/2008

Fingerprint

Service Selection
Linear programming
Web services
Web Services
Quality of service
Heuristic algorithms
Scalability
Multi-dimension
Requirements
Knapsack Problem
Linear Program
Experimental Evaluation
Heuristic algorithm
Fast Algorithm
NP-complete problem
Optimal Solution
Optimization Problem
Decompose

Cite this

Alrifai, Mohammad ; Risse, Thomas ; Dolog, Peter ; Nejdl, Wolfgang. / A Scalable Approach for QoS-Based Web Service Selection. In: Lecture Notes in Computer Science. 2009 ; Vol. 5472. pp. 190-199.
@inproceedings{bc90dfb0fecf11de9a61000ea68e967b,
title = "A Scalable Approach for QoS-Based Web Service Selection",
abstract = "QoS-based service selection aims at finding the best component services that satisfy the end-to-end quality requirements. The problem can be modeled as a multi-dimension multi-choice 0-1 knapsack problem, which is known as NP-hard. Recently published solutions propose using linear programming techniques to solve the problem. However, the poor scalability of linear program solving methods restricts their applicability to small-size problems and renders them inappropriate for dynamic applications with run-time requirements. In this paper, we address this problem and propose a scalable QoS computation approach based on a heuristic algorithm, which decomposes the optimization problem into small sub-problems that can be solved more efficiently than the original problem. Experimental evaluations show that near-to-optimal solutions can be found using our algorithm much faster than using linear programming methods.",
author = "Mohammad Alrifai and Thomas Risse and Peter Dolog and Wolfgang Nejdl",
note = "Titel: Service-Oriented Computing - ICSOC 2008 Workshops Oversat titel: Oversat undertitel: Forlag: Springer Publishing Company ISBN (Trykt): 978-3-642-01246-4 ISBN (Elektronisk): Publikationsserier: Lecture Notes in Computer Science, 0302-9743, 1611-3349, 5472 Redakt{\o}rer: George Feuerlicht Winfried Lamersdorf",
year = "2009",
doi = "10.1007/978-3-642-01247-1_20",
language = "English",
volume = "5472",
pages = "190--199",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Physica-Verlag",

}

A Scalable Approach for QoS-Based Web Service Selection. / Alrifai, Mohammad; Risse, Thomas; Dolog, Peter; Nejdl, Wolfgang.

In: Lecture Notes in Computer Science, Vol. 5472, 2009, p. 190-199.

Research output: Contribution to journalConference article in JournalResearchpeer-review

TY - GEN

T1 - A Scalable Approach for QoS-Based Web Service Selection

AU - Alrifai, Mohammad

AU - Risse, Thomas

AU - Dolog, Peter

AU - Nejdl, Wolfgang

N1 - Titel: Service-Oriented Computing - ICSOC 2008 Workshops Oversat titel: Oversat undertitel: Forlag: Springer Publishing Company ISBN (Trykt): 978-3-642-01246-4 ISBN (Elektronisk): Publikationsserier: Lecture Notes in Computer Science, 0302-9743, 1611-3349, 5472 Redaktører: George Feuerlicht Winfried Lamersdorf

PY - 2009

Y1 - 2009

N2 - QoS-based service selection aims at finding the best component services that satisfy the end-to-end quality requirements. The problem can be modeled as a multi-dimension multi-choice 0-1 knapsack problem, which is known as NP-hard. Recently published solutions propose using linear programming techniques to solve the problem. However, the poor scalability of linear program solving methods restricts their applicability to small-size problems and renders them inappropriate for dynamic applications with run-time requirements. In this paper, we address this problem and propose a scalable QoS computation approach based on a heuristic algorithm, which decomposes the optimization problem into small sub-problems that can be solved more efficiently than the original problem. Experimental evaluations show that near-to-optimal solutions can be found using our algorithm much faster than using linear programming methods.

AB - QoS-based service selection aims at finding the best component services that satisfy the end-to-end quality requirements. The problem can be modeled as a multi-dimension multi-choice 0-1 knapsack problem, which is known as NP-hard. Recently published solutions propose using linear programming techniques to solve the problem. However, the poor scalability of linear program solving methods restricts their applicability to small-size problems and renders them inappropriate for dynamic applications with run-time requirements. In this paper, we address this problem and propose a scalable QoS computation approach based on a heuristic algorithm, which decomposes the optimization problem into small sub-problems that can be solved more efficiently than the original problem. Experimental evaluations show that near-to-optimal solutions can be found using our algorithm much faster than using linear programming methods.

U2 - 10.1007/978-3-642-01247-1_20

DO - 10.1007/978-3-642-01247-1_20

M3 - Conference article in Journal

VL - 5472

SP - 190

EP - 199

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -