容量制約付き最短経路ツアー問題に基づくサービスチェイニング ～ ラグランジュ緩和法と最短経路ツアーアルゴリズムに基づく解法 ～

原 崇徳 笹部 昌弘

In 電子情報通信学会技術研究報告（ネットワークシステム研究会）, 2021

Abstract

ネットワーク機能仮想化 (Network functions virtualization: NFV) は従来のネットワーク機器を汎用ハードウェアと仮想ネットワーク機能 (Vritual network function: VNF) に置き換えることで，ネットワークサービスを迅速かつ柔軟に展開できる．あるネットワークサービスは，複数のVNFを連結したサービスチェインとして構成できる．ここで資源制約の下，中間ノードでVNFを所望の順序で実行しながら，始点ノードから終点ノードへと至るサービスパスを構築する問題はサービスチェイニングと呼ばれる．先行研究では，サービスチェイニング問題と最短経路ツアー問題 (Shortest path tour problem: SPTP) の類似性に着目し，サービスチェイニングを容量制約付きSPTP (Capacitated SPTP: CSPTP) に基づくILPとして定式化している．本稿では，ラグランジュ緩和と既存のSPTPアルゴリズムの組み合わせにより，オンライン型サービスチェイニングを対象としたCSPTPに基づくILPを効率的に解くことのできる手法を提案する．シミュレーション評価より，資源割当の最適性と計算量の観点から提案方式の基本特性を明らかにする．

Downloads

    Text Reference

    原 崇徳, 笹部 昌弘, 容量制約付き最短経路ツアー問題に基づくサービスチェイニング ～ ラグランジュ緩和法と最短経路ツアーアルゴリズムに基づく解法 ～, 電子情報通信学会技術研究報告（ネットワークシステム研究会）, 121(170), pp.18-23, September 2021.

    BibTex Reference

    @article{hara21ns,
    author = "原, 崇徳 and 笹部, 昌弘",
    title = "{容量制約付き最短経路ツアー問題に基づくサービスチェイニング ～ ラグランジュ緩和法と最短経路ツアーアルゴリズムに基づく解法 ～}",
    year = "2021",
    month = "September",
    journal = "電子情報通信学会技術研究報告（ネットワークシステム研究会）",
    volume = "121",
    number = "170",
    pages = "18--23"
}