| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2021-09-09 12:40 容量制約付き最短経路ツアー問題に基づくサービスチェイニング ～ ラグランジュ緩和法と最短経路ツアーアルゴリズムに基づく解法 ～ ○原 崇徳・笹部昌弘（奈良先端大）  NS2021-60 |
|
| 抄録 | （和） | ネットワーク機能仮想化 (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 / / | |
| 文献情報 | 信学技報, vol. 121, no. 170, NS2021-60, pp. 18-23, 2021年9月. | |
| 資料番号 | NS2021-60 | |
| 発行日 | 2021-09-02 (NS) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NS2021-60 |
|
| 研究会情報 | |
| 研究会 | IN NS CS NV |
| 開催期間 | 2021-09-09 - 2021-09-10 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | 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. |
| 講演論文情報の詳細 | |
| 申込み研究会 | NS |
| 会議コード | 2021-09-IN-NS-CS-NV |
| 本文の言語 | 日本語 |
| タイトル（和） | 容量制約付き最短経路ツアー問題に基づくサービスチェイニング |
| サブタイトル（和） | ラグランジュ緩和法と最短経路ツアーアルゴリズムに基づく解法 |
| タイトル（英） | 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 |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 原 崇徳 / Takanori Hara / ハラ タカノリ |
| 第1著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 第2著者 氏名（和/英/ヨミ） | 笹部 昌弘 / Masahiro Sasabe / ササベ マサヒロ |
| 第2著者 所属（和/英） | 奈良先端科学技術大学院大学 (略称： 奈良先端大) Nara Institute of Science and Technology (略称： NAIST) |
| 第3著者 氏名（和/英/ヨミ） | / / |
| 第3著者 所属（和/英） | (略称： ) (略称： ) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2021-09-09 12:40:00 |
| 発表時間 | 25分 |
| 申込先研究会 | NS |
| 資料番号 | NS2021-60 |
| 巻番号（vol） | vol.121 |
| 号番号（no） | no.170 |
| ページ範囲 | pp.18-23 |
| ページ数 | 6 |
| 発行日 | 2021-09-02 (NS) |
[研究会発表申込システムのトップページに戻る]