コンポーネント連携によるサービスを オーバレイネットワーク上で 実現するためのサービス設計技法の提案 大阪大学 大学院情報科学研究科 中村嘉隆，山口弘純，廣森聡仁，東野輝夫

サービスオーバレイとは 複数のサーバ（サービスノード）が連携してサービスを提供 入力： モバイルカメラによる 低品質動画 複数のサーバ（サービスノード）が連携してサービスを提供 サービスノード同士で仮想リンク（オーバレイネットワーク）を構築 サービスノードは一定のプロトコルに従って協調動作 例：動画トランスコーディング，プロキシサービス ユーザの要求に応じた品質保証が必要 →QoS 制御，資源割り当て，負荷分散手法が必要 高品質化サービス 高品質動画 音楽付加サービス オーバレイネットワーク 出力： 音楽が付加された 高品質ビデオ （PC ユーザ向け） 2005/3/23 DPS122/CSEC28

既存のサービスオーバレイ構築アルゴリズム 入力： モバイルカメラによる 低品質動画 従来法 コンポーネントの線形結合による仕様記述で QoS 要求を処理（Xu ら[1]） DAG による仕様記述により汎用性を高める（Wang ら[2]） 問題点 データベースなどユーザから何度も利用されるようなサービスを表現できない 多数ユーザからの同時並行的なサービス要求を考慮していない 高品質化サービス 高品質動画 音楽付加サービス [1] D. Xu and K. Nahrstedt. Finding service paths in an overlay media service proxy network. In Proc. of Int. Conf. on Multimedia Computing and Networking 2002 (MMCN2002), 2002. 出力： 音楽が付加された 高品質ビデオ （PC ユーザ向け） [2] M. Wang, B. Li, and Z. Li. sflow: Towards resource-efficient and agile service federation in serviceoverlay networks. In Proc. of 24th Int. Conf. on Distributed Computing Systems (ICDCS2004), 2004. 2005/3/23 DPS122/CSEC28

提案するサービスオーバレイ構築アルゴリズム S1 S2 S3 提案手法の概要 対象とするサービス 動画配信などの大容量マルチメディアデータ 多数のユーザが同時に使用 ある程度の時間利用が継続される →サービスフローが複雑になる 仕様記述クラス Pr/T ネット（拡張ペトリネットの一種） 線形結合，DAG に比べ複雑な記述ができる 従来手法の 対象とするフロー S1 S2 S3 提案手法の 対象とするフロー 2005/3/23 DPS122/CSEC28

対象とするサービス例 キーワードと再生可能ビットレートに応じたビデオコンテンツを返すサービス 複数ユーザが同時に利用する ビデオレポジトリ インデックス PC 用 ビデオレポジトリA モバイル端末用 ビデオレポジトリ B 2005/3/23 DPS122/CSEC28

提案手法 入力 出力 Pr/T ネットによるサービス記述 サービスオーバレイアーキテクチャ サービスリソースをプレース サービスをトランジション で表現 サービスオーバレイアーキテクチャ 出力 与えられたノードへのサービス割り当てのもとでの，各ノードで実行すべきプログラム群（動作記述） サービス仕様 <INDEX> P5:ビデオ リポジトリ索引 P1:サービス入力 T1:ビデオ インデックス検索 P2 P4:サービス出力 T5:ビデオ 該当無し <A> <B> P6:ビデオ リポジトリA (PC用) P7:ビデオ リポジトリB (携帯用キャッシュ) T4:リポジトリB から動画送信 P3 T2:リポジトリA から画像取得& トランスコード T3:トランスコード済み動画を 索引とリポジトリBに登録して送信 割り当て オーバレイネットワーク 2005/3/23 DPS122/CSEC28

入力（サービス記述） Pr/T ネットで記述 リソースプレース サービスフロープレース サービスリソース（データベースのような恒久的なリソース）を表す 内部でトークンの増減を行わない サービスフロープレース その他のプレース 2005/3/23 DPS122/CSEC28

入力（サービスオーバレイアーキテクチャ） サービスノード 計算能力についての制限（サービス制限）を与えられる CPU，メモリの性能から推定 オーバレイチャネル サービスノード間の仮想チャネル オーバレイチャネルコストを与えられる 遅延，帯域の逆数から推定 遅延，帯域，ネットワーク利用率に関するコスト サービス制限=10 サービス制限=2 サービス制限=5 4 サービス制限=7 サービス制限=12 2005/3/23 DPS122/CSEC28

入力（サービスノードへのプレース配置） 各サービスノードへのサービスプレース配置 SN1 SN2 SN3 SN4 P1:Service Input P2:Index Search Result SN1 SN2 P5:Video Repository Index SN3 SN4 2005/3/23 DPS122/CSEC28

出力（サービスノードの動作記述） 各サービスノードがどのように動作するかの記述 通信プレース（点線で表されたプレース） オーバレイチャネルを表現 共通する名前の通信プレースはサービスノード間の通信を表す トランジション T1 に 対応する部分の動作記述 2005/3/23 DPS122/CSEC28

導出アルゴリズム（トランジションの分解） 配置されたサービスプレースのもと，トランジション実行プロトコルに従ってトランジション t を各サービスノードに分解 トランジション実行プロトコル：任意のトランジションの振る舞いを，サービスノード群によってシミュレートする手順を汎用的に記述したプロトコル P1 P2 P4 P7 P6 P3 P5 T3 T5 T2 T4 T1 P1 T1 P5 P2 2005/3/23 DPS122/CSEC28

導出アルゴリズム（トランジションの分解） 配置されたサービスプレースのもと，トランジション実行プロトコルに従ってトランジション t を各サービスノードに分解 トランジション実行プロトコル：任意のトランジションの振る舞いを，サービスノード群によってシミュレートする手順を汎用的に記述したプロトコル トランジション T1 に 対応する部分 2005/3/23 DPS122/CSEC28

導出アルゴリズム（動作記述の導出） 全てのトランジションを分解し，各サービスノードに動作記述の組み合わせが割り当てられる SN1 SN2 P1 T1 P5 T1 P2 T1 P4 T5 P3 T3 2005/3/23 DPS122/CSEC28

サービスオーバレイ最適化 対象とするアプリケーションにおいて，あるサービスは一般に 複数ユーザにより同時並行的に利用 各ユーザのサービスインスタンスは他のユーザのサービスインスタンスと独立に処理 複数のサービスコンポーネントによってオーバレイチャネルが同時に利用される可能性がある →全サービスコンポーネントが複数ユーザにより同時に実行された場合に各オーバレイチャネルの負荷がピーク値に達する ＝各オーバレイチャネルのサービスコスト オーバレイチャネル全体でサービスコストを最小化 プレース配置を最適化することで実現 2005/3/23 DPS122/CSEC28

サービスオーバレイ最適化 オーバレイチャネル (i,j) のサービスコストを以下のように定義する scost(i,j) =cost(i,j)*St∊TSv∊var(T)size(v)*(ati,j[v]+bti,j [v]) cost(i,j) : (i,j) のオーバレイチャネルコスト T：トランジション集合 var(T)：t のアークで用いられる変数集合 size(v)：変数 v のサイズ ati,j[v]（ bti,j [v]）：t において変数 v がメッセージを用いて送信されるかどうかを表す（Boolean） 2005/3/23 DPS122/CSEC28

サービスオーバレイ最適化 サービスオーバレイのコストは全オーバレイチャネルのサービスコストの最大値として定義 max(i,j)∊E scost(i,j) E：すべてのオーバレイチャネル集合 scost の最大値を最小化することでチャネル利用のピーク値を抑え，全体のレスポンスを改善 →コストを最小化するようなプレースの最適配置問題を整数線形計画問題に帰着して求める 2005/3/23 DPS122/CSEC28

実験環境 目的：導出された最適なプレース配置によって，どの程度性能が改善されたかをサービス要求に対する平均レスポンス時間で評価 使用したアプリケーション例 与えられたキーワードに基づき，映像にオープニングとエンディングを付加 MPEG4 及び MPEG2 フォーマットに圧縮 実験過程 カラーペトリネット記述解析支援ツール（CPNtools）と協調して最適化された動作記述導出を支援するツールを使用 これらによって，上記のアプリケーション例について，5 つのサービスノードの動作記述集合を導出 導出した動作記述集合から高レベルペトリネットシミュレータ（Maria）とネットワークシミュレータ（GTNetS）を連携して動作させる →実時間シミュレーションにおける最適化動作記述のユーザあたりの平均レスポンス時間を計測 2005/3/23 DPS122/CSEC28

使用したアプリケーション例 オープニング， エンディング付加 PCM→ MPEG audio layerII 変換 （音声） DV→MPEG4圧縮 （画像） 音声,画像の結合 MPEG2 変換 2005/3/23 DPS122/CSEC28

実験結果 ランダムなプレース配置から導出した動作記述，手動配置に基づき導出した動作記述と提案手法を比較 手動配置 ランダム配置 提案手法 2005/3/23 DPS122/CSEC28

まとめ サービスオーバレイ分散協調システムの最適自動設計手法の提案 今後の課題 Pr/T ネットを利用して複雑なサービスフローを表現し，それらから各サービスノードの動作記述を自動導出 サービスプレースの最適化配置を行うことにより，サービス品質の向上を実現 今後の課題 オーバレイチャネル上での利用可能帯域変化に応じた QoS 制御機構の導入 2005/3/23 DPS122/CSEC28