Accuracy and Dynamics of Multi-Stage Load Balancing for Multipath Internet Routing

Flow-based load balancing algorithms for multipath Internet routing are often used for traffic engineering. However, the target load distribution and the load balanced result agree only on average, and there is a significant inaccuracy over time due to stochastic effects. Dynamic load balancing reduces this inaccuracy by relocating flows to other paths in regular time intervals. This causes packet reordering. Therefore, the flow reassignment rate should be kept low. In this paper we consider load balancing in networks. It differs from load balancing at a single node by the fact that several load balancing steps may be performed at consecutive nodes in series. This affects the flow reassignment rate and the load balancing accuracy due to interdependencies and polarization effects. We quantify the impact by simulation results, explain the observed phenomena, and give recommendations for load balancing in practice.