| 講演名 | 2021-09-09 容量制約付き最短経路ツアー問題に基づくサービスチェイニング 原 崇徳(奈良先端大), 笹部 昌弘(奈良先端大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | ネットワーク機能仮想化 (Network functions virtualization: NFV) は従来のネットワーク機器を汎用ハー ドウェアと仮想ネットワーク機能 (Vritual network function: VNF) に置き換えることで，ネットワークサービスを迅 速かつ柔軟に展開できる.あるネットワークサービスは，複数の VNF を連結したサービスチェインとして構成でき る.ここで資源制約の下，中間ノードで VNF を所望の順序で実行しながら，始点ノードから終点ノードへと至るサー ビスパスを構築する問題はサービスチェイニングと呼ばれる.先行研究では，サービスチェイニング問題と最短経路 ツアー問題 (Shortest path tour problem: SPTP) の類似性に着目し，サービスチェイニングを容量制約付き SPTP (Capacitated SPTP: CSPTP) に基づく ILP として定式化している.本稿では，ラグランジュ緩和と既存の SPTP ア ルゴリズムの組み合わせにより，オンライン型サービスチェイニングを対象とした CSPTP に基づく ILP を効率的に 解くことのできる手法を提案する.シミュレーション評価より，資源割当の最適性と計算量の観点から提案方式の基本特性を明らかにする. |
| 抄録(英) | Network functions virtualization (NFV) can speedily and flexibly deploy network services by replacing traditional network appliances with generic hardware and virtual network functions (VNFs). A certain network service can be interpreted as a sequence of VNFs, i.e., service (function) chain. The service chaining problem aims at finding an appropriate service path from the origin to the destination while executing the VNFs at the intermediate nodes in the required order under the resource constraint. In our previous work, focusing on the similarity between the service chaining problem and the shortest path tour problem (SPTP), we formulated the service chaining problem as the capacitated SPTP (CSPTP) based ILP, where CSPTP is an extended version of the SPTP with the node and link capacity constraints. In this paper, to address both computational complexity and optimality of resource allocation, we propose an efficient algorithm for online service chaining by combining the Lagrangian relaxation for the CSPTP-based ILP and the existing SPTP algorithm. Through simulation results, we show the fundamental characteristics of the proposed algorithm in terms of the optimality of resource allocation and the computational complexity. |
| キーワード(和) | ネットワーク機能仮想化 / サービスチェイニング / 整数線形計画問題 / 容量制約付き最短経路ツアー問題 / ラグランジュ緩和 / 劣勾配法 |
| キーワード(英) | Network functions virtualization / service chaining / integer linear programming / capacitated shortest path tour problem / Lagrangian relaxation / subgradient algorithm |
| 資料番号 | NS2021-60 |
| 発行日 | 2021-09-02 (NS) |
| 研究会情報 | |
| 研究会 | IN / NS / CS |
|---|---|
| 開催期間 | 2021/9/9(から2日開催) |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | セッション管理(SIP・IMS)，相互接続技術/標準化，次世代・新世代・将来ネットワーク，クラウド/データセンタネットワーク，SDN(OpenFlow等)・NFV，IPv6，機械学習のネットワーク適用，一般 |
| テーマ（英） | Session management (SIP/IMS), Interoperability/Standardization, NGN/NwGN/Future networks, Cloud/Data center networks, SDN (OpenFlow, etc.)/NFV, IPv6, Machine learning, etc. |
| 委員長氏名（和） | 石田 賢治(広島市大) / 中尾 彰宏(東大) / 寺田 純(NTT) |
| 委員長氏名（英） | Kenji Ishida(Hiroshima City Univ.) / Akihiro Nakao(Univ. of Tokyo) / Jun Terada(NTT) |
| 副委員長氏名（和） | 波戸 邦夫(インターネットマルチフィード) / 大石 哲矢(NTT) / 梅原 大祐(京都工繊大) |
| 副委員長氏名（英） | Kunio Hato(Internet Multifeed) / Tetsuya Oishi(NTT) / Daisuke Umehara(Kyoto Inst. of Tech.) |
| 幹事氏名（和） | 谷口 展郎(NTT) / 星野 文学(長崎県立大) / 渡部 康平(長岡技科大) / 城 哲(KDDI総合研究所) / 池邉 隆(NTT) / 吉田 雅裕(中大) / 吉田 悠来(NICT) / 原 一貴(NTT) |
| 幹事氏名（英） | Noburo Taniguchi(NTT) / Fumitaka Hoshino(Univ. of Nagasaki) / Kouhei Watabei(Nagaoka Univ. of Tech.) / Tetsu Jyo(KDDI Research) / Takashi Ikebe(NTT) / Masahiro Yoshida(Chuo Univ.) / Yuki Yoshida(NICT) / Kazutaka Hara(NTT) |
| 幹事補佐氏名（和） | / 三原 孝太郎(NTT) / 山浦 隆博(東芝) / 井田 悠太(山口大) |
| 幹事補佐氏名（英） | / Kotaro Mihara(NTT) / Takahiro Yamaura(Toshiba) / Yuta Ida(Yamaguchi Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Information Networks / Technical Committee on Network Systems / Technical Committee on Communication Systems |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 容量制約付き最短経路ツアー問題に基づくサービスチェイニング |
| サブタイトル（和） | ラグランジュ緩和法と最短経路ツアーアルゴリズムに基づく解法 |
| タイトル（英） | Service Chaining Based on Capacitated Shortest Path Tour Problem |
| サブタイトル（和） | Solution Based on Lagrangian Relaxation and Shortest Path Tour Algorithm |
| キーワード(1)（和/英） | ネットワーク機能仮想化 / Network functions virtualization |
| キーワード(2)（和/英） | サービスチェイニング / service chaining |
| キーワード(3)（和/英） | 整数線形計画問題 / integer linear programming |
| キーワード(4)（和/英） | 容量制約付き最短経路ツアー問題 / capacitated shortest path tour problem |
| キーワード(5)（和/英） | ラグランジュ緩和 / Lagrangian relaxation |
| キーワード(6)（和/英） | 劣勾配法 / subgradient algorithm |
| 第 1 著者 氏名（和/英） | 原 崇徳 / Takanori Hara |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Institute of Science and Technology(略称：NAIST) |
| 第 2 著者 氏名（和/英） | 笹部 昌弘 / Masahiro Sasabe |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Institute of Science and Technology(略称：NAIST) |
| 発表年月日 | 2021-09-09 |
| 資料番号 | NS2021-60 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | NS-170 |
| ページ範囲 | pp.18-23(NS), |
| ページ数 | 6 |
| 発行日 | 2021-09-02 (NS) |