Abstract: The continuous increase of traffic in the network can easily lead to unbalanced traffic, network congestion, and thus affect the users' experience. The Optimizing Open Shortest Path First (OSPF) Weights (OPW) algorithm is generally employed by Internet Service Provider (ISP) to deal with network congestion. However, there are three problems in this algorithm:1) real traffic matrix is needed; 2) network oscillation is easily to be led; 3) OPW has been proven to be a Non deterministic Ploynomial (NP) problem and requires to be solved by centralized approach. Aiming at the above problems of OPW algorithm, a new Distributed Load Balancing algorithm based on Hop-by-hop computing (DLBH) was proposed. Firstly, virtual traffic was set for all nodes. Then, the cost of all links was calculated based on the virtual traffic. Finally, the optimal routing was calculated using distributed algorithm. DLBH uses a distributed approach to solve the network congestion problem, while OPW can only use a centralized approach to deal with the network congestion problem. Therefore, the scalability of DLBH is superior to the scalability of OPW. Theoretical analysis shows that, the time complexity of DLBH is much less than that of OPW. The experimental results show that, the maximum link utilization of DLBH is significantly lower than that of OPW algorithm, which greatly reduces network congestion.

Key words: hop-by-hop computing, load balancing, virtual traffic, maximum link utilization, distributed algorithm

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

关键词: 逐跳计算, 负载均衡, 虚拟流量, 最大链路利用率, 分布式算法