Multipath routing has been widely recognized to be more efficient than single path routing. In such schemes, multiple paths are configured between a pair of node, and then traffic is split among these paths. In richly interconnected networks, multipath routing can provide load balancing, improve bandwidth utilization and mitigate congestion. There are two critical issues for the design of multipath routing: 1) How to find multiple paths. 2) How to distribute traffic among them.

In networks using Open Shortest-Path First (OSPF), the nodes compute the path using the cost of each link, based on Dijkstra's shortest path algorithm. If there are multiple shortest paths between a pair of source and destination nodes, Equal-Cost Multipath (ECMP) routing would equally split traffic among the multiple paths. However, evenly splitting traffic among the paths does not achieve optimal load balancing. As shown in Fig.1, under ECMP routing scheme, the link between node 2 and node 5 becomes the bottleneck link, because the link is shared by the flows of two pairs (A, C) and (B, D). Things could be even worse in large-scale networks, where even traffic splitting may overload certain links while leaving some other links underutilized. 

In this project, we focus on the traffic split issue within the framework of ECMP. Instead of distributing traffic evenly among multiple paths, we present weighted ECMP (ECMP-d), which distributes traffic among available paths based on a set of pre-determined ratios. The objective is to optimize network performance under given traffic demand. While most existing works try to minimize the traffic load on the most utilized link, we aim at optimizing the end to end delay of each pair in the network, which has direct impact on the quality of service in most cases. We formulate and convert the problem to be a linear programming problem. Because of the difficulty in solving the problem for large-scale networks, we present a heuristic algorithm to obtain the near-optimal weight configuration. Simulations in various networks, including practical and randomly generated topologies, show that the proposed algorithm can effectively improve the overall network performance and outperforms existing schemes. In particular, the implementation of our scheme is very straightforward. It only requires the modification of router's hash parameters without any hardware or protocol changes.

Fig.1 Link capacity = 1. Value over link is link load. Source A sends 1 unit traffic via nodes (1, 4) and (2, 5) to destination C; Source B sends 1 unit traffic via nodes (2, 5) and (3, 6) to destination D.

Fig. 2 shows average path delay of each pair for weighted ECMP and traditional ECMP. The results indicate Weighted ECMP reduces the end-to-end delay of most pairs in the network, comparing with traditional ECMP. This means Weighted ECMP allocates traffic more efficiently than traditional ECMP and achieves better load balancing.

Publication

[1] Junjie Zhang, Kang Xi, Liren Zhang and H. Jonathon Chao, "Optimizing Network Performance using Weighted Multipath Routing", Submitted and under review.