基于鲁棒性的链路权重规划算法

Link Weight Programming Algorithm Based on Robustness

在IP网络中,链路权重规划是流量工程中的重要问题。为了优化网络流量并实现负载均衡,针对业务量矩阵的不确定性,依据鲁棒性理论提出一个链路权重规划的MIP模型。该模型使用Γ模型描述业务量矩阵的不确定集,通过表示扰动程度的参数Γ实现了对鲁棒性的调节,在此基础上求得不确定集中最差情况下的最优解。实验结果表明,与传统的链路权重规划方法以及新出现的MRC规划模型相比较,该算法可降低最大链路利用率,分别达到了40%和20%。

For IP networks, the link weight planning is an important issue of traffic engineering. In order to optimize the network traffic and achieve load balancing and against the unknown traffic matrix, this article proposes a link weight prograrmning MIP model based on the robustness theory. This model applies the F_model to describe uncertainty set of traffic matrix, and regulates the robustness by the parameter F which indicates the extent of disturbance, on this base, obtains the optimal solution in the worst-ease of uncertain set. Through the experiment in American Abilene network, the proposed algorithm can reduce the maxi- mum link utilization 40 percent and 20 percent respectively when comparing with traditional link weight planning methods and the emerging MRC programming model.