基于逐跳计算的分布式负载均衡算法

摘要 网络中流量的不断增长容易导致流量不均衡、网络拥塞，进而影响用户的体验。因特网服务提供商（ISP）通常采用优化开放最短路径优先（OSPF）权值（OPW）算法应对网络拥塞，然而该算法存在三个方面的问题：1）需要实际流量矩阵；2）容易导致网络震荡；3）OPW已经被证实为NP难题，并且需要采用集中式方法求解。针对OPW算法存在的问题，提出了一种基于逐跳计算的分布式负载均衡算法（DLBH）。首先，为所有节点设置虚拟流量；然后，根据虚拟流量计算所有链路的代价；最后，采用分布式算法计算最优路由。DLBH采用分布式方法解决网络拥塞问题，而OPW只能采用集中式方法解决网络拥塞问题，因此DLBH的扩展性优于OPW的扩展性。理论分析表明，DLBH的时间复杂度远远小于OPW的时间复杂度。实验结果表明，DLBH的最大链路利用率明显低于OPW算法的最大链路利用率，大幅降低了网络拥塞