基于拉格朗日松弛的服务功能链路由算法

Service Function Chain Routing Algorithm Based on Lagrange Relaxation

针对网络功能虚拟化/软件定义网络中资源利用率较低的问题,提出了一种自适应服务功能链路由算法(SFC-DGA)。首先将服务功能链路由问题转化为整数线性规划模型;然后根据服务功能链请求的结构,构造一个分层图网络模型;最后使用拉格朗日松弛方法,提出一种时延保证的服务功能链路由算法。实验结果表明,与随机路由算法和流量感知路由算法相比,SFC-DGA的服务功能链请求接受率分别提高了40.98%和8.86%,物理网络中节点资源利用率分别提高了50.34%和9.72%,链路资源利用率分别提高了54.57%和8.39%,负载均衡性能明显优于对比算法。

Aiming at the problem of low resource utilization in network function virtualization-enabled software defined networks,an adaptive service function chain routing algorithm(SFC-DGA)is proposed.Firstly,the problem of service function chain routing is transformed into an integer linear programming model.Then,according to the structure of service function chain request,a hierarchical graph network model is constructed.Finally,using Lagrange relaxation method,a service function chain routing algorithm with delay guarantee is proposed.The experimental results show that compared with the random routing algorithm and the traffic-aware routing algorithm,the SFC request acceptance rate of SFC-DGA has increased by 40.98%and 8.86%respectively,the node resource utilization rate has improved by 50.34%and 9.72%respectively,and the link resource utilization rate has increased by 54.57%and 8.39%respectively,and has achieved better performance in load balancing performance in the physical network.