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

基于数学优化和时空 GNN 的可持续 NFV 网络

基本信息

批准号：
22H03586
负责人：
笹部昌弘
金额：
$ 11.15万
依托单位：
Kansai University (2023)Nara Institute of Science and Technology (2022)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2025-03-31
项目状态：
未结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22H03586/
关键词：
NFVネットワーク持続可能性数理最適化時空間GNN サービスチェイニングネットワーク機能仮想化(NFV)機能配置整数線形最適化(ILO)容量制約付き最短経路ツアー問題(CSPTP)ラグランジュ緩和グラフニューラルネットワーク CNF

项目摘要

本研究が目指す持続可能な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），以及在它们之间创建循环。今年我们的目标是成立元素科技1，由代表和同事分别担任主要负责人和副负责人。服务链为服务链请求在物理网络上设置适当的服务路径。业务路径从源节点开始，在各个中继节点上按照期望的顺序执行物理网络上的功能，然后成为到达目的节点的最短路由。然而，路线上的每个节点和链路在处理和流量方面都有容量限制。申请人之前发现该问题可以被表述为基于能力化最短路径巡回问题（CSPTP）的整数线性优化（ILO）。另一方面，由于容量限制和服务路径内可能存在环路，该问题成为NP难组合优化问题。因此，在本研究中，我们建立了一种新的解决方法，该方法考虑了最优性和计算复杂性之间的平衡。具体来说，我们将通过拉格朗日松弛将CSPTP转换为SPTP，使用次梯度方法控制拉格朗日乘子，并在考虑SPTP约束的总单模性的情况下将ILP线性化为LP，这是通过结合松弛等数学方法来实现的。我们还提出了一种构建冗余服务路径的方法，以在发生硬件或软件故障时将服务路径可用性维持在一定水平以上。