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.

様々な機能をネットワーク経由で提供するWebサービスが,多く公開され活用されるようになっている.これに対し,ワークフローに含まれる各機能を実現するサービスの組み合わせを,品質を最適化するように選ぶ問題が盛んに取り組まれている.サービス選択問題においては,サービスを組み合わせた結果のワークフロー全体に対して,利用料金や応答時間などの品質に対する制約充足と最適化を考える.このため,膨大な組み合わせの探索が必要となり,近似解法のスケーラビリティーの実現に重点が当てられてきた.しかしサービス選択問題に対しては,2003年に行われた当初の研究における問題の定義を踏襲してスケーラビリティーを追求している取り組みが多く,現実に必要とされる側面を扱っていない.

そこで本研究においては,問題の定義自体を拡張するとともに,十分なスケーラビリティーを確保できるアルゴリズムを提案している.具体的な拡張としては,第一に長期間の利用における品質の確保,第二にネットワークの影響を考慮した品質の確保を扱っている.

本論文は以下の6つの章から構成されている.

第1章では研究の概要を述べている.次に第2章では前提となる背景知識を説明した後,第3章ではサービス選択問題に対する既存研究を議論し,課題を整理している.

第4章では,長期間の利用における品質を考慮するという方向性に基づき,3つの貢献が議論されている.従来のサービス選択問題においては,毎回の実行において品質の制約を満たしつつ,品質に対する効用関数を最大化することを考えていた.しかし,例えば利用料金など,複数の実行を通した長期間での値が保証できれば十分ということも多い.また,複数の実行を考えると,品質の異なる複数サービスを特定の比率で使い分けるような選択肢も増えてくる.本章ではこれらの動機を踏まえ第一に,長期間にわたる確率的なサービス選択問題として,問題の拡張を形式的に定義している.この問題は,Linear Programmingに対応づけることにより,効率よく解くことができる.加えて,人間による決定プロセスの支援など,提案手法の活用方法を4つ議論している.評価としては,スケーラビリティーの観点に加え,従来の問題定義よりも利用者が得る効用が高くなることも実験的に示している.本章では第二に,技術的には,このアプローチが従来の問題においても活用できるというアイディアを示している.具体的には,上記の効率的に得られる解を,山登り法などのメタヒューリスティックスにおいて改善の対象となる初期解として用いる.これにより従来の問題においても,より最適解に近い解を求めることができ,かつスケーラビリティーのある手法を実現され,またその評価がなされている.本章では第三に,本章で扱う問題の集大成として,品質や利用の時系列の変化パターン,および代替えサービスの選択を含めた問題を定義している.これに対して遺伝アルゴリズムに基づく独自の解法を提案し,利用者における効用の増加,信頼性の保証,およびスケーラビリティーを達成,評価している.

第5章では,ネットワークの影響を考慮するという方向性に基づき,3つの貢献が議論されている.従来のサービス選択問題においては,ネットワークの影響もサービスの品質の一部としてモデル化していたため,ユーザの位置への依存性が扱われていなかった.またクラウドの普及により地理的な分散が拡大し,サービスの配備箇所の選択肢も膨大となるため,ネットワークの影響を考慮し,かつスケーラビリティーを達成することがより重要となっている.本章ではこれらの動機を踏まえ準備段階として,現実的な適用可能性を議論するために,分散アーキテクチャを提案している.このアーキテクチャは標準的な集中型,および完全な分散アーキテクチャのバランスをスレーブノードの導入にてとろうというものである.また加えて,サービス利用の前後関係を踏まえたネットワーク品質の表現モデルを提案している.これらは以降のサービス選択に統合され効果的に活用されている.本章では第二に,遺伝アルゴリズムを問題に応じて拡張し,サービス利用の前後関係やネットワーク品質を踏まえるアルゴリズムにより,効率的な解法を提案,評価している.さらに第三に,ネットワーク品質と一般のサービス品質とのバランスを取る自己適応的なアルゴリズムを提案,評価している.これらの取り組みにより,ネットワークとサービスの双方の品質を踏まえて利用者にとって高い効用,および高いスケーラビリティーも達成,氷解している.

第6章では最後に、本論文の内容をまとめている.

以上のように本論文は,増加するWebサービスの活用という大きな目標に向けて着実に技術を進歩させている.特に従来の問題定義に対して現実を踏まえた拡張を提起した上で,より困難な問題に対して十分にスケーラビリティーを達成する解法を提案している.また実用の観点,技術活用の観点から,非常に様々なアイディアが注意深く論じられている.以上のように本論文は独自かつ先進的な成果を挙げたものであり,審査委員会は,博士号に十分値するものと判断した.よって本論文は博士(情報理工学)の学位請求論文として合格と認められる.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。