超分散コンピューティング基盤に向けたEnd-to-End 時間制約付きマイクロサービスの最適配置アルゴリズムの検討

情報処理学会

書誌事項

タイトル別名
  • Placement Algorithm for End-to-End Time-Constrained Microservices on Geographically Distributed Post-5G Infrastructure

説明

エッジコンピューティングにおけるアプリケーション配置は，リアルタイムなデータ処理を要求するアプリケーションにおいて特に重要であり，ノード間の通信遅延や処理時間を考慮した最適な配置アルゴリズムが必要である．マイクロサービスで構成されEnd-to-End (E2E) 時間制約を含むアプリケーションを，地理的に分散した拠点間に，効率的に配置する手法を提案する．まず，計算基盤リソースとアプリケーションをそれぞれグラフ構造に抽象化する手法を考案し，そのグラフを用いて，アプリケーションの最適配置問題を整数線形最適化問題としての定式化を行った．新たな最適配置手法として逐次サブパス写像法を開発し，厳密解法や既存の遺伝的アルゴリズム，ヒューリスティクス手法であるRandom walk Max-Matchとの比較を行った．提案手法は，NP困難であるグラフ写像問題を線形時間で近似的に解くことができ，要求するリソース制約とE2E時間制約を満たしたアプリケーション構成グラフの配置解を算出した．オフライン問題では，提案手法が，アプリケーション構成グラフのノード数が増えた場合でも他手法に比べて安定して解を算出可能であり，配置解の基盤ノードの利用コストにおいて他手法と比較して優れた性能であることを示した．

収録刊行物

詳細情報 詳細情報について

問題の指摘

ページトップへ