サービスチェイニングの数理最適化

ネットワークのソフトウェアとプログラム化によって，ネットワーク機能の柔軟な配置と管理が可能になりました． サービスチェイニング（Service Function Chaining, SFC）は，特定の順序でネットワーク機能（例：ファイアウォール，ロードバランサー，IDSなど）を通過するようにトラフィックを誘導する技術です． SFCの最適化は，ネットワークのパフォーマンス向上とリソース効率化に寄与します． 本研究では，数理最適化の観点から，資源制約の下でネットワーク機能の配置とルーチングを実現するSFC問題に取り組みます． 特にShortest Path Tour Problem (SPTP) と呼ばれる問題とSFC問題の類似性に着目し，SFC問題を効率的に解くために，SPTPに基づく整数線形計画法（Integer Linear Programming, ILP）に取り組んでいます1． さらに，本問題を効率的に解くために，ヒューリスティック解法2や強化学習を用いた手法3も検討しています． また，ネットワーク機能の多様性と冗長性を考慮したSFC問題にも取り組んでおり，資源効率と可用性の両立を目指しています4．

Mathematical Optimization for SFC

Network softwarization and programmability have enabled flexible deployment and management of network functions. Service Function Chaining (SFC) offers a key solution that steers traffic through a specific sequence of network functions (e.g., firewall, load balancer, IDS). In this research, we address the SFC problem that realizes the placement and routing of network functions under resource constraints from the viewpoint of mathematical optimization. In particular, we focus on the similarity between the SFC problem and the Shortest Path Tour Problem (SPTP), and we have formulated this problem as an Integer Linear Program (ILP) based on SPTP to efficiently solve the SFC problem1. Furthermore, we have also explored heuristic approaches2 and reinforcement learning-based methods3 to further efficiently solve the problem. We have also addressed the SFC problem considering the diversity and redundancy of network functions, aiming to achieve both resource efficiency and availability4.

  1. M. Sasabe and T. Hara, “Capacitated Shortest Path Tour Problem-Based Integer Linear Programming for Service Chaining and Function Placement in NFV Networks,” IEEE Trans. Netw. Serv. Manage., vol. 18, no. 1, pp. 104–117, Mar. 2021, doi: 10.1109/TNSM.2020.3044329. ↩︎ ↩︎

  2. T. Hara and M. Sasabe, “Speedy and Efficient Service Chaining and Function Placement Based on Lagrangian Heuristics for Capacitated Shortest Path Tour Problem,” J Netw Syst Manage, vol. 31, no. 1, p. 24, Dec. 2022, doi: 10.1007/s10922-022-09715-y. ↩︎ ↩︎

  3. T. Hara and M. Sasabe, “Capacitated Shortest Path Tour Based Service Chaining Adaptive to Changes of Service Demand and Network Topology,” IEEE Transactions on Network and Service Management, pp. 1–15, 2024, doi: 10.1109/TNSM.2024.3351737. ↩︎ ↩︎

  4. T. Hara, M. Sasabe, K. Sugihara, and S. Kasahara, “Resource-Efficient and Availability-Aware Service Chaining and VNF Placement with VNF Diversity and Redundancy,” IEICE Transactions on Communications, vol. E107.B, pp. 105–116, 2024, doi: 10.1587/transcom.2023WWP0003. ↩︎ ↩︎