Optimizing Network Performance Using Weighted Multipath Routing

Equal-Cost Multipath (ECMP) routing has been widely adopted to perform load balancing. With ECMP, a router can maintain multiple next hops for a destination IP prefix. The most common method used by such routers is to split traffic with per-flow basis evenly among those next hops. This approach, although simple, cannot achieve optimal load balancing. In this paper we study the optimal configuration of weighted ECMP, where traffic splitting among the available paths is based on a set of pre-determined ratios. The contribution of this paper is two-fold. First, we develop a model to obtain the split ratios such that the overall network end-to-end delay is optimized. This is important because better delay performance is a result of better bandwidth allocation and has a direct impact on application, while most existing work tries to minimize the traffic load on the most utilized link. Second, we prove that the problem can be first solved by using a simple flow-based routing model and then converting the results to apply to IP networks, where destination-based forwarding is used. We present a heuristic algorithm to find the near-optimal weight configurations and demonstrate the effectiveness of the algorithm using computer simulations.