容量制約付き最短経路ツアーとラグランジュ緩和を用いたNFVネットワークにおけるオンラインサービスチェイニング

原 崇徳 笹部 昌弘

In 日本学術振興会産学協力研究委員会インターネット技術第 163 委員会meet50, 2021

Abstract

ネットワーク機能仮想化 (Network function virtualization: NFV) は専用のネットワーク機器を汎用ハードウェア上の仮想ネットワーク機能(Virtual network function: VNF) に置き換えることで，迅速かつ柔軟にネットワークサービスを展開できる．あるネットワークサービスは複数のVNFの列からなるサービスチェインとして構成できる．NFVネットワークにおける資源割当問題の一つであるサービスチェイニングは，ノードやリンクにおける資源制約と中継ノード上でのVNFの所望の実行順を保証した上で，始点ノードから終点ノードへと至る経路（サービスパス）を構築する問題である．先行研究では，最短経路ツアー問題(Shortest path tour problem: SPTP)との類似性に着目し，サービスチェイニングを容量制約付きSPTP (Capacitated SPTP: CSPTP)に基づく整数線形計画問題として定式化している．本発表ではこの問題に対し，ラグランジュ緩和と既存の最短経路ツアー・アルゴリズムを組み合わせることで，最適性と計算量のバランスを考慮した解法を提案する．シミュレーション評価より，資源割当の最適性と計算量の観点から提案方式の基本特性を示す．

Downloads

    Text Reference

    原 崇徳, 笹部 昌弘, 容量制約付き最短経路ツアーとラグランジュ緩和を用いたNFVネットワークにおけるオンラインサービスチェイニング, 日本学術振興会産学協力研究委員会インターネット技術第 163 委員会meet50, November 2021.

    BibTex Reference

    @article{hara21itrc,
    author = "原, 崇徳 and 笹部, 昌弘",
    title = "{容量制約付き最短経路ツアーとラグランジュ緩和を用いたNFVネットワークにおけるオンラインサービスチェイニング}",
    year = "2021",
    month = "November",
    journal = "日本学術振興会産学協力研究委員会インターネット技術第 163 委員会meet50"
}