| Paper Abstract and Keywords |
| Presentation |
2013-03-15 16:30
[Invited Talk]
[Invited PhD Talk] Applied and Scalable Optimization of Long-term and Network-aware Service Compositions
Adrian Klein (Univ. of Tokyo) |
| Abstract |
(in Japanese) |
(See Japanese page) |
| (in English) |
Computing optimal service compositions in terms of their non-functional, Quality of Service (QoS), properties, is one of the key problems in realizing the vision of Service-Oriented Computing (SOC), and is known as the NP-hard QSC problem. The spread of Service-Orientation and the rapid increase in the number of available services have spurred various research investigations over the last 10 years. Once software components are defined as services, they can be easily combined to achieve more complex functionality, even by less technical users. Services provide loosely coupled access over the network through clearly defined APIs. This enables robust coupling of software components across both network and company borders. It also makes the SOC paradigm a natural fit for the recent trend of moving an increasing number of software components into the cloud.
This thesis investigates the problem of effectively and efficiently computing near-optimal service compositions for long-term and network-aware settings. By extending the QSC problem for these settings, we close the increasing gap between the standard formalization and the current reality of service compositions. As both the problem's complexity and its search space increase for these extensions, we also build and improve upon ongoing research to achieve a good scalability by using domain knowledge to guide our optimization for the QSC problem.
As service compositions become a crucial part of the software landscape, compositions are often carefully specified and then used over an extended period of time. In such long-term settings, optimizing for multiple executions at once allows our approach to provide significant QoS benefits to users, especially, when users specify tight QoS constraints such as a monthly budget or a high minimum reliability. For this purpose, we compute probabilistic and time-dependent execution policies through Linear Programming and a custom Genetic Algorithm (GA), which extend the standard static mapping between the parts of a composition and concrete services. Through an adaptive GA we achieve a reasonable scalability for the latter even though the complexity of the QSC problem increases due to the number of time-dependent choices.
With the growing distribution of services within compositions, e.g. in the context of clouds, the influence of the network on the overall QoS of compositions keeps increasing. We propose both a network-aware modeling of QoS and a network-aware optimization. This includes a formalized distributed architecture, a generic network model and a customized self-adaptive GA. Modeling QoS in a network-aware manner requires distinguishing even between different physical instances of the same service by the same provider, as users will have different experiences depending on the QoS of the network between them and these instances. Thus, the number of optimization choices increases. Furthermore, considering the network also introduces strong dependencies between connected services within compositions. Therefore, the complexity of the problem increases significantly and exploring the search space in an uninformed way becomes less effective. In order to solve this challenge, our optimization approach is aware of the network and its custom GA operators make informed probabilistic decisions by using domain knowledge about the network. As other QoS properties unrelated to the network, such as price or reliability, still have to be optimized as well, this supports our choice of a GA which allows our approach to seamlessly use both domain-specific and general operators at the same time. Our custom self-adaptation rules assure that the most appropriate operators are chosen depending both on the concrete problem instance and the user's QoS preferences, thus, guaranteeing the generality of our approach for the QSC problem. We evaluate our approach based on an extensive (externally provided) network dataset against standard GAs which represent state-of-the-art algorithms for the QSC problem and against a Dijkstra algorithm exclusively optimizing the network latency. In terms of network latency, our approach consistently achieves a good approximation ratio for all evaluated problem sizes compared to the optimal latency computed by Dijkstra, while the approximation ratio of the standard GAs deteriorates with increasing problem size. In terms of other QoS, it is on par with or slightly better than standard GA approaches. The scalability of our approach beats standard GAs, and in case of an increasing number of services instances, Dijkstra is outperformed by several orders of magnitude. |
| Keyword |
(in Japanese) |
(See Japanese page) |
| (in English) |
Services Computing / Service Selection / Service Composition / QoS / SLA / Optimization / Genetic Algorithms / |
| Reference Info. |
IEICE Tech. Rep., vol. 112, no. 497, SC2012-23, pp. 33-34, March 2013. |
| Paper # |
SC2012-23 |
| Date of Issue |
2013-03-08 (SC) |
| ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
| Download PDF |
|
| Conference Information |
| Committee |
SC |
| Conference Date |
2013-03-15 - 2013-03-15 |
| Place (in Japanese) |
(See Japanese page) |
| Place (in English) |
|
| Topics (in Japanese) |
(See Japanese page) |
| Topics (in English) |
|
| Paper Information |
| Registration To |
SC |
| Conference Code |
2013-03-SC |
| Language |
English (Japanese title is available) |
| Title (in Japanese) |
(See Japanese page) |
| Sub Title (in Japanese) |
(See Japanese page) |
| Title (in English) |
[Invited PhD Talk] Applied and Scalable Optimization of Long-term and Network-aware Service Compositions |
| Sub Title (in English) |
|
| Keyword(1) |
Services Computing |
| Keyword(2) |
Service Selection |
| Keyword(3) |
Service Composition |
| Keyword(4) |
QoS |
| Keyword(5) |
SLA |
| Keyword(6) |
Optimization |
| Keyword(7) |
Genetic Algorithms |
| Keyword(8) |
|
| 1st Author's Name |
Adrian Klein |
| 1st Author's Affiliation |
The University of Tokyo (Univ. of Tokyo) |
| 2nd Author's Name |
|
| 2nd Author's Affiliation |
() |
| 3rd Author's Name |
|
| 3rd Author's Affiliation |
() |
| 4th Author's Name |
|
| 4th Author's Affiliation |
() |
| 5th Author's Name |
|
| 5th Author's Affiliation |
() |
| 6th Author's Name |
|
| 6th Author's Affiliation |
() |
| 7th Author's Name |
|
| 7th Author's Affiliation |
() |
| 8th Author's Name |
|
| 8th Author's Affiliation |
() |
| 9th Author's Name |
|
| 9th Author's Affiliation |
() |
| 10th Author's Name |
|
| 10th Author's Affiliation |
() |
| 11th Author's Name |
|
| 11th Author's Affiliation |
() |
| 12th Author's Name |
|
| 12th Author's Affiliation |
() |
| 13th Author's Name |
|
| 13th Author's Affiliation |
() |
| 14th Author's Name |
|
| 14th Author's Affiliation |
() |
| 15th Author's Name |
|
| 15th Author's Affiliation |
() |
| 16th Author's Name |
|
| 16th Author's Affiliation |
() |
| 17th Author's Name |
|
| 17th Author's Affiliation |
() |
| 18th Author's Name |
|
| 18th Author's Affiliation |
() |
| 19th Author's Name |
|
| 19th Author's Affiliation |
() |
| 20th Author's Name |
|
| 20th Author's Affiliation |
() |
| Speaker |
Author-1 |
| Date Time |
2013-03-15 16:30:00 |
| Presentation Time |
60 minutes |
| Registration for |
SC |
| Paper # |
SC2012-23 |
| Volume (vol) |
vol.112 |
| Number (no) |
no.497 |
| Page |
pp.33-34 |
| #Pages |
2 |
| Date of Issue |
2013-03-08 (SC) |
|