容量制約付き最短経路ツアー問題に基づくサービスチェイニング ～ 整数線形計画とラグランジュ緩和による解法 ～

原 崇徳 笹部 昌弘

In 電子情報通信学会技術研究報告(RISING), 2021

Abstract

ネットワーク機能仮想化 (Network functions virtualization: NFV) は従来型のネットワーク機器からネットワーク機能を切り離し，仮想ネットワーク機能 (Virtual network function: VNF) として汎用のハードウェア上で実行することで，ネットワークサービスを迅速かつ柔軟に展開できる． あるネットワークサービスは複数のVNFを連結したサービスチェインとして表現できる． ここで資源制約の下，中間ノードでVNFを所望の順序で実行しながら，始点ノードから終点ノードへと至るサービスパスを構築し，ネットワークサービスを実現する問題はサービスチェイニング問題と呼ばれる． 我々はこれまでに，サービスチェイニング問題と最短経路ツアー問題 (Shortest path tour problem: SPTP) の類似性に着目し，サービスチェイニングを容量制約付きSPTP (Capacitated SPTP: CSPTP) に基づく整数線形計画問題として定式化するとともに，ラグランジュ緩和法に基づく計算量を抑えた解法を提案している． 本発表では，これらの手法を体系的に紹介するとともに，シミュレーション評価により，資源割当の最適性と計算量の観点からCSPTPに基づくサービスチェイニングの基本特性を示す．

Downloads

    Text Reference

    原 崇徳, 笹部 昌弘, 容量制約付き最短経路ツアー問題に基づくサービスチェイニング ～ 整数線形計画とラグランジュ緩和による解法 ～, 電子情報通信学会技術研究報告(RISING), November 2021.

    BibTex Reference

    @article{hara21rising,
    author = "原, 崇徳 and 笹部, 昌弘",
    title = "{容量制約付き最短経路ツアー問題に基づくサービスチェイニング ～ 整数線形計画とラグランジュ緩和による解法 ～}",
    year = "2021",
    month = "November",
    journal = "電子情報通信学会技術研究報告(RISING)"
}