Robust Virtual Network Function Allocation in Service Function Chains With Uncertain Availability Schedule
Robust Virtual Network Function Allocation in Service Function Chains With Uncertain Availability Schedule
复制标题
可用性计划不确定的服务功能链中的鲁棒虚拟网络功能分配
DOI：
10.1109/tnsm.2021.3076511
复制
发表时间：
2021
影响因子：
5.3
通讯作者：
Oki Eiji
中科院分区：
文献类型：
--
作者：
Kang Rui;He Fujun;Oki Eiji
可用性调度提供关于每个网络节点在每个时隙是否可用的信息。如果按照可用性计划分配功能，则可以抑制可用性计划中标记的节点不可用导致的服务中断。然而，给定的可用性调度可能与实际的可用性调度有差距，并影响VNF分配。提出了一种鲁棒优化模型，通过抑制可用性调度和功能重分配中节点不可用引起的网络中断，最大化可用性调度不确定网络中服务功能链（SFC）的连续可用时间。我们制定的问题作为一个混合整数线性规划（MILP）的问题，在给定的不确定性集的开始时隙和可用性计划中的每个节点上的不可用性。为了在较大规模的网络中在实际时间内求解该模型，我们提出了一种启发式算法。数值结果表明，在不同的鲁棒性水平下，该模型的性能优于基准模型，在最坏情况下，每个SFC中最长连续可用时隙的最小数目是最小的。与MILP方法相比，该启发式算法在有限的性能损失下减少了计算时间。在讨论中，我们引入了维护能力的约束条件，减少了不确定性集的大小，并扩展了每个节点的可用性调度中支持多个不可用期。
The availability schedule provides information on whether each network node is available at each time slot. The service interruptions caused by node unavailability marked in availability schedule can be suppressed if the functions are allocated according to the availability schedule. However, the given availability schedule may have gaps with the actual one and influence the VNF allocation. This paper proposes a robust optimization model to allocate virtual network functions (VNFs) in service function chains (SFCs) for time slots in sequence aiming to maximize the continuous available time of SFCs in a network with uncertain availability schedules by suppressing the interruptions caused by node unavailability marked in availability schedule and function reallocation. We formulate the problem as a mixed integer linear programming (MILP) problem over the given uncertainty set of the start time slot and period of unavailability on each node in the availability schedule. For solving the model in a practical time in a relative large size of network, we develop a heuristic algorithm. The numerical results show that the proposed model outperforms the baseline models under different levels of robustness in terms of the worst-case minimum number of the longest continuous available time slot in each SFC. The heuristic algorithm reduces the computation time with limited performance loss compared with the MILP approach. In the discussion, we introduce a constraint condition for the maintenance ability, which reduces the size of uncertainty set, and an extension for supporting more than one unavailability periods in the availability schedule on each node.