| 講演抄録／キーワード |
| 講演名 |
2013-03-15 16:30
［招待講演］[招待博士講演]ネットワークを考慮した長期間に渡るサービス合成におけるスケーラブルな最適化の適用
○Adrian Klein（東大） |
| 抄録 |
（和） |
(まだ登録されていません) |
| （英） |
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. |
| キーワード |
（和） |
/ / / / / / / |
| （英） |
Services Computing / Service Selection / Service Composition / QoS / SLA / Optimization / Genetic Algorithms / |
| 文献情報 |
信学技報, vol. 112, no. 497, SC2012-23, pp. 33-34, 2013年3月. |
| 資料番号 |
SC2012-23 |
| 発行日 |
2013-03-08 (SC) |
| ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
SC |
| 開催期間 |
2013-03-15 - 2013-03-15 |
| 開催地（和） |
国立情報学研究所 (NII) |
| 開催地（英） |
|
| テーマ（和） |
「サービスおよびクラウドのQoS・SLA・ポリシー」および一般 |
| テーマ（英） |
|
| 講演論文情報の詳細 |
| 申込み研究会 |
SC |
| 会議コード |
2013-03-SC |
| 本文の言語 |
英語（日本語タイトルあり） |
| タイトル（和） |
[招待博士講演]ネットワークを考慮した長期間に渡るサービス合成におけるスケーラブルな最適化の適用 |
| サブタイトル（和） |
|
| タイトル（英） |
[Invited PhD Talk] Applied and Scalable Optimization of Long-term and Network-aware Service Compositions |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
/ Services Computing |
| キーワード(2)（和/英） |
/ Service Selection |
| キーワード(3)（和/英） |
/ Service Composition |
| キーワード(4)（和/英） |
/ QoS |
| キーワード(5)（和/英） |
/ SLA |
| キーワード(6)（和/英） |
/ Optimization |
| キーワード(7)（和/英） |
/ Genetic Algorithms |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
Adrian Klein / Adrian Klein / |
| 第1著者 所属（和/英） |
東京大学 (略称： 東大)
The University of Tokyo (略称： Univ. of Tokyo) |
| 第2著者 氏名（和/英/ヨミ） |
/ / |
| 第2著者 所属（和/英） |
(略称： )
(略称： ) |
| 第3著者 氏名（和/英/ヨミ） |
/ / |
| 第3著者 所属（和/英） |
(略称： )
(略称： ) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 第21著者 氏名（和/英/ヨミ） |
/ / |
| 第21著者 所属（和/英） |
(略称： )
(略称： ) |
| 第22著者 氏名（和/英/ヨミ） |
/ / |
| 第22著者 所属（和/英） |
(略称： )
(略称： ) |
| 第23著者 氏名（和/英/ヨミ） |
/ / |
| 第23著者 所属（和/英） |
(略称： )
(略称： ) |
| 第24著者 氏名（和/英/ヨミ） |
/ / |
| 第24著者 所属（和/英） |
(略称： )
(略称： ) |
| 第25著者 氏名（和/英/ヨミ） |
/ / |
| 第25著者 所属（和/英） |
(略称： )
(略称： ) |
| 第26著者 氏名（和/英/ヨミ） |
/ / |
| 第26著者 所属（和/英） |
(略称： )
(略称： ) |
| 第27著者 氏名（和/英/ヨミ） |
/ / |
| 第27著者 所属（和/英） |
(略称： )
(略称： ) |
| 第28著者 氏名（和/英/ヨミ） |
/ / |
| 第28著者 所属（和/英） |
(略称： )
(略称： ) |
| 第29著者 氏名（和/英/ヨミ） |
/ / |
| 第29著者 所属（和/英） |
(略称： )
(略称： ) |
| 第30著者 氏名（和/英/ヨミ） |
/ / |
| 第30著者 所属（和/英） |
(略称： )
(略称： ) |
| 第31著者 氏名（和/英/ヨミ） |
/ / |
| 第31著者 所属（和/英） |
(略称： )
(略称： ) |
| 第32著者 氏名（和/英/ヨミ） |
/ / |
| 第32著者 所属（和/英） |
(略称： )
(略称： ) |
| 第33著者 氏名（和/英/ヨミ） |
/ / |
| 第33著者 所属（和/英） |
(略称： )
(略称： ) |
| 第34著者 氏名（和/英/ヨミ） |
/ / |
| 第34著者 所属（和/英） |
(略称： )
(略称： ) |
| 第35著者 氏名（和/英/ヨミ） |
/ / |
| 第35著者 所属（和/英） |
(略称： )
(略称： ) |
| 第36著者 氏名（和/英/ヨミ） |
/ / |
| 第36著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2013-03-15 16:30:00 |
| 発表時間 |
60分 |
| 申込先研究会 |
SC |
| 資料番号 |
SC2012-23 |
| 巻番号（vol） |
vol.112 |
| 号番号（no） |
no.497 |
| ページ範囲 |
pp.33-34 |
| ページ数 |
2 |
| 発行日 |
2013-03-08 (SC) |
|