コンポーネント連携によるサービスをオーバレイネット

Higashino Lab.
コンポーネント連携によるサービスを
オーバレイネットワーク上で
実現するためのサービス設計技法の提案
大阪大学大学院情報科学研究科
中村嘉隆，山口弘純，廣森聡仁，東野輝夫
Higashino Lab.
サービスオーバレイとは

複数のサーバ（サービスノード）が連携して
サービスを提供




入力：
モバイルカメラによる
低品質動画
サービスノード同士で仮想リンク（オーバレイネッ高品質化サービス
トワーク）を構築
サービスノードは一定のプロトコルに従って協調
動作
高品質動画
例：動画トランスコーディング，プロキシサービス
ユーザの要求に応じた品質保証が必要
→QoS 制御，資源割り当て，負荷分散手法
が必要
音楽付加サービス
出力：
音楽が付加された
高品質ビデオ
（PC ユーザ向け）
オーバレイネットワーク
2005/3/23
DPS122/CSEC28
2
Higashino Lab.
既存のサービスオーバレイ構築アルゴリズム

従来法



コンポーネントの線形結合による仕様記述で
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.
[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
音楽付加サービス
出力：
音楽が付加された
高品質ビデオ
（PC ユーザ向け）
3
Higashino Lab.
提案するサービスオーバレイ構築アルゴリズム
S1

S2
S3
提案手法の概要

対象とするサービス
動画配信などの大容量マルチメディアデータ
 多数のユーザが同時に使用
 ある程度の時間利用が継続される
→サービスフローが複雑になる


仕様記述クラス

従来手法の
対象とするフロー
S1
S2
S3
Pr/T ネット（拡張ペトリネットの一種）
 線形結合，DAG に比べ複雑な記述ができる
提案手法の
対象とするフロー
2005/3/23
DPS122/CSEC28
4
Higashino Lab.
対象とするサービス例

キーワードと再生可能ビットレートに応じたビデオコ
ンテンツを返すサービス
複数ユーザが同時に利用する
ビデオレポジトリ
インデックス
PC 用
ビデオレポジトリA
モバイル端末用
ビデオレポジトリ B
2005/3/23
DPS122/CSEC28
5
Higashino Lab.
提案手法

入力

Pr/T ネットによるサービス記述
<INDEX>




サービス仕様
サービスリソースをプレース
サービスをトランジション
で表現
サービスオーバレイアーキテク
チャ
P1:サービス入力
P5:ビデオ
リポジトリ索引
T2:リポジトリA P7:ビデオ
から画像取得& リポジトリB
<A> トランスコード(携帯用キャッシュ)
<B>
P6:ビデオ
リポジトリA
(PC用)
P2
T1:ビデオ
インデックス検索
T4:リポジトリB
から動画送信
P3
T3:トランスコード済み動画を
索引とリポジトリBに登録して送信
T5:ビデオ
該当無し
P4:サービス出力
割り当て
出力

2005/3/23
与えられたノードへのサービス
割り当てのもとでの，各ノード
で実行すべきプログラム群（動
作記述）
DPS122/CSEC28
オーバレイネットワーク
6
Higashino Lab.
入力（サービス記述）

Pr/T ネットで記述

リソースプレース



サービスリソース
（データベースの
ような恒久的なリ
ソース）を表す
内部でトークンの
増減を行わない
サービスフロープ
レース

2005/3/23
その他のプレース
DPS122/CSEC28
7
Higashino Lab.
入力（サービスオーバレイアーキテクチャ）

サービスノード

計算能力についての制限
（サービス制限）を与えられる


サービス制限=10
サービス制限=2
サービス制限=5
CPU，メモリの性能から推定
オーバレイチャネル


サービスノード間の仮想チャネ
ル
オーバレイチャネルコストを与
えられる


2005/3/23
4
サービス制限=7
サービス制限=12
遅延，帯域の逆数から推定
遅延，帯域，ネットワーク利用
率に関するコスト
DPS122/CSEC28
8
Higashino Lab.
入力（サービスノードへのプレース配置）

各サービスノードへのサービスプレース配置
P2:Index Search Result
P1:Service Input
SN1
SN2
P5:Video Repository Index
SN3
2005/3/23
SN4
DPS122/CSEC28
9
Higashino Lab.
出力（サービスノードの動作記述）

各サービスノードがどのように動作するかの記述

通信プレース（点線で表されたプレース）


オーバレイチャネルを表現
共通する名前の通信プレースはサービスノード間の通信を表す
トランジション T1 に
対応する部分の動作記述
2005/3/23
DPS122/CSEC28
10
Higashino Lab.
導出アルゴリズム（トランジションの分解）

配置されたサービスプレースのもと，トランジション実行プロト
コルに従ってトランジション t を各サービスノードに分解

トランジション実行プロトコル：任意のトランジションの振る舞いを，
サービスノード群によってシミュレートする手順を汎用的に記述したプ
ロトコル
P1
P5
P5
P1
T2
P6 P7
P3
P2
T4
T5
T3
2005/3/23
T1
T1
P2
DPS122/CSEC28
P4
11
Higashino Lab.
導出アルゴリズム（トランジションの分解）

配置されたサービスプレースのもと，トランジション実行プロト
コルに従ってトランジション t を各サービスノードに分解

トランジション実行プロトコル：任意のトランジションの振る舞いを，
サービスノード群によってシミュレートする手順を汎用的に記述したプ
ロトコル
トランジション T1 に
対応する部分
2005/3/23
DPS122/CSEC28
12
Higashino Lab.
導出アルゴリズム（動作記述の導出）

全てのトランジションを分解し，各サービスノードに動
作記述の組み合わせが割り当てられる
2005/3/23
SN1
SN2
SN3
P1
T1
P5
T1
P2
T1
T5
P3
P4
T3
DPS122/CSEC28
13
Higashino Lab.
サービスオーバレイ最適化

対象とするアプリケーションにおいて，あるサービスは一般に


複数ユーザにより同時並行的に利用
各ユーザのサービスインスタンスは他のユーザのサービスインスタン
スと独立に処理
複数のサービスコンポーネントによってオーバレイチャネルが
同時に利用される可能性がある
→全サービスコンポーネントが複数ユーザにより同時に実行さ
れた場合に各オーバレイチャネルの負荷がピーク値に達する
＝各オーバレイチャネルのサービスコスト


オーバレイチャネル全体でサービスコストを最小化
プレース配置を最適化することで実現
2005/3/23
DPS122/CSEC28
14
Higashino Lab.
サービスオーバレイ最適化

オーバレイチャネル (i,j) のサービスコストを以下のように定
義する
scost(i,j)
=cost(i,j)*St∊TSv∊var(T)size(v)*(ati,j[v]+bti,j [v])





2005/3/23
cost(i,j) : (i,j) のオーバレイチャネルコスト
T：トランジション集合
var(T)：t のアークで用いられる変数集合
size(v)：変数 v のサイズ
ati,j[v]（ bti,j [v]）：t において変数 v がメッセージを用いて送信される
かどうかを表す（Boolean）
DPS122/CSEC28
15
Higashino Lab.
サービスオーバレイ最適化

サービスオーバレイのコストは全オーバレイチャネル
のサービスコストの最大値として定義
max(i,j)∊E scost(i,j)

E：すべてのオーバレイチャネル集合
scost の最大値を最小化することでチャネル利用の
ピーク値を抑え，全体のレスポンスを改善
→コストを最小化するようなプレースの最適配置問題
を整数線形計画問題に帰着して求める

2005/3/23
DPS122/CSEC28
16
Higashino Lab.
実験環境

目的：導出された最適なプレース配置によって，どの程度性能が改善され
たかをサービス要求に対する平均レスポンス時間で評価

使用したアプリケーション例



与えられたキーワードに基づき，映像にオープニングとエンディングを付加
MPEG4 及び MPEG2 フォーマットに圧縮
実験過程



カラーペトリネット記述解析支援ツール（CPNtools）と協調して最適化された動
作記述導出を支援するツールを使用
これらによって，上記のアプリケーション例について，5 つのサービスノードの
動作記述集合を導出
導出した動作記述集合から高レベルペトリネットシミュレータ（Maria）とネット
ワークシミュレータ（GTNetS）を連携して動作させる
→実時間シミュレーションにおける最適化動作記述のユーザあたりの平均レスポ
ンス時間を計測
2005/3/23
DPS122/CSEC28
17
Higashino Lab.
使用したアプリケーション例
オープニング，
エンディング付加
PCM→
MPEG audio layerII 変換
（音声）
DV→MPEG4圧縮
（画像）
音声,画像の結合
MPEG2 変換
2005/3/23
DPS122/CSEC28
18
Higashino Lab.
実験結果

ランダムなプレース配置から導出した動作記述，手動配置に
基づき導出した動作記述と提案手法を比較
手動配置
ランダム配置
提案手法
2005/3/23
DPS122/CSEC28
19
Higashino Lab.
まとめ

サービスオーバレイ分散協調システムの最適自動
設計手法の提案



Pr/T ネットを利用して複雑なサービスフローを表現し，そ
れらから各サービスノードの動作記述を自動導出
サービスプレースの最適化配置を行うことにより，サービ
ス品質の向上を実現
今後の課題

2005/3/23
オーバレイチャネル上での利用可能帯域変化に応じた
QoS 制御機構の導入
DPS122/CSEC28
20

Download Report