Sustainable NFV Networking based on Mathematical Optimization and Spatio-Temporal GNN

本研究が目指す持続可能なNFVネットワークは，数理最適化によるサービスチェイニング・機能配置（要素技術1），時空間GNNによるサービス需要の時空間変化に追従可能な制御方式（要素技術2），軽量な仮想化技術に基づく適応力を備えたサービスパスの実現（要素技術3）という3つの要素技術の確立，および，それらの間の循環作用により実現可能と考えている．本年度は，代表者と分担者がそれぞれ主・副担当として，要素技術1の確立を目指した．サービスチェイニングでは，サービスチェイン要求に対し，物理ネットワーク上に適切なサービスパスを設定する．サービスパスは，始点ノードから始まり，物理ネットワーク上に配置された機能を所望の順にそれぞれ中継ノード上で実行した後，終点ノードへと至る最短経路となる．ただし，経路上の各ノードと各リンクでは，処理やトラヒックの観点で容量制約が存在する．応募者らはこれまでに，この問題が容量制約付き最短経路ツアー問題(CSPTP: Capacitated Shortest Path Tour Problem)に基づく整数線形最適化(ILO: Integer Linear Optimization)として定式化できることを発見していた．一方でこの問題は，容量制約やサービスパス内でのループの可能性により，NP困難な組み合わせ最適化問題となる．そこで本研究では，最適性と計算量のバランスを考慮した新たな解法を確立した．具体的には，ラグランジュ緩和によるCSPTPのSPTPへの変換と劣勾配法を用いたラグランジュ乗数の制御，SPTP制約に関する全ユニモジュラ性を考慮した最適性を維持した形でのILPのLPへの線形緩和，といった数理的手法を組み合わせて実現している．また，ハードウェア・ソフトウェアの故障・障害発生に対して，サービスパスの可用性を一定レベル以上に維持するための冗長性を備えたサービスパスの構築手法を提案した．

本研究が目指す持続可能なNFVネットワークは，数理最適化によるサービスチェイニング・機能配置（要素技術1），時空間GNNによるサービス需要の時空間変化に追従可能な制御方式（要素技術2），軽量な仮想化技術に基づく適応力を備えたサービスパスの実現（要素技術3）という3つの要素技術の確立，および，それらの間の循環作用により実現可能と考えている．本年度は，代表者と分担者がそれぞれ主・副担当として，要素技術1の確立を目指した．サービスチェイニングでは，サービスチェイン要求に対し，物理ネットワーク上に適切なサービスパスを設定する．サービスパスは，始点ノードから始まり，物理ネットワーク上に配置された機能を所望の順にそれぞれ中継ノード上で実行した後，終点ノードへと至る最短経路となる．ただし，経路上の各ノードと各リンクでは，処理やトラヒックの観点で容量制約が存在する．応募者らはこれまでに，この問題が容量制約付き最短経路ツアー問題(CSPTP: Capacitated Shortest Path Tour Problem)に基づく整数線形最適化(ILO: Integer Linear Optimization)として定式化できることを発見していた．一方でこの問題は，容量制約やサービスパス内でのループの可能性により，NP困難な組み合わせ最適化問題となる．そこで本研究では，最適性と計算量のバランスを考慮した新たな解法を確立した．具体的には，ラグランジュ緩和によるCSPTPのSPTPへの変換と劣勾配法を用いたラグランジュ乗数の制御，SPTP制約に関する全ユニモジュラ性を考慮した最適性を維持した形でのILPのLPへの線形緩和，といった数理的手法を組み合わせて実現している．また，ハードウェア・ソフトウェアの故障・障害発生に対して，サービスパスの可用性を一定レベル以上に維持するための冗長性を備えたサービスパスの構築手法を提案した．