一种新增链路数最少的网络负载均衡模型——基于线性规划理论

A Network Load Balancing Model with Minimal New Links Added—Based on Linear Programming Theory

摘要: 本文提出了一种基于线性规划的网络负载均衡算法，与传统算法相比，新算法具有使得节点间新增链路数最少的特点。新算法避免了传统基于策略的启发式算法可能无法有效求解的问题和传统基于模型的优化算法复杂度一般为指数级的问题。新算法是将网络负载均衡问题建模为优化问题并近似为线性规划模型求解得到的，在理论上可以充分利用SDN网络信息，同时具有可以在多项式时间内求解等较好性质。在经典网络拓扑和随机生成的网络拓扑上得到的数值实验结果表明，与同类算法相比，新算法可以有效解决网络拥塞问题，同时使得所需新增链路数更少，在运行时间上也具有一定优势，可以大大降低网络的运行成本，具有广泛应用前景。

Abstract: This paper presents a new network load balancing algorithm based on linear programming. Compared to traditional algorithms, this algorithm features minimal new links added. This algorithm avoids the weakness of traditional strategy-based heuristic algorithms, which cannot effectively solve the problem, and the weakness of traditional optimization-model-based algorithms, which require exponential time complexity. The new algorithm models network load balancing problem as an optimization problem and solves it through linear programming. Using this method, this algorithm can fully utilize SDN network information, and the problem can be solved in pol-ynomial time. Numerical experiments result in both classic and randomly generated network topology shows the new algorithm can effectively solve network load balancing problem and need less new links within less time, compared to traditional algorithms, which can reduce the operating cost of the network greatly. Thus, the new algorithm has broad application prospects.