Multipath routing is a trivial way to exploit the path diversity to leverage the network throughput. Technologies such as OSPF ECMP use all the available paths in the network to forward traffic, however, we argue that is not necessary to do so to load balance the network. In this paper, we consider multipath routing with only a limited number of end-to-end paths for each source and destination, and found that this can still load balance the traffic. We devised an algorithm to select a few paths for each source-destination pair so that when all traffic are forwarded over these paths, we can achieve a balanced load in the sense that the maximum link utilization is comparable to that of ECMP forwarding. When the constraint of only shortest paths (i.e. equal paths) are relaxed, we can even outperform ECMP in certain cases. As a result, we can use a few end-to-end tunnels between each source and destination nodes to achieve the load balancing of traffic.
@cite_14: 
@cite_10: 
@cite_3: This paper presents and discusses path selection algorithms to support QoS routes in IP networks. The work is carried out in the context of extensions to the OSPF protocol, and the initial focus is on unicast flows, although some of the proposed extensions are also applicable to multicast flows. We first review the metrics required to support QoS, and then present and compare several path selection algorithms, which represent different trade-offs between accuracy and computational complexity. We also describe and discuss the associated link advertisement mechanisms, and investigate some options in balancing the requirements for accurate and timely information with the associated control overhead. The overall goal of this study is to identify a framework and possible approaches to allow deployment of QoS routing capabilities with the minimum possible impact to the existing routing infrastructure.
@cite_24: Routing protocols using the distributed Bellman-Ford (DBF) algorithm converge very slowly to the correct routes when link costs increase, and in the case when a set of link failures results in a network partition, DBF simply fails to converge, a problem which is commonly referred to as the count-to-infinity problem. We present the first distance-vector routing algorithm, MDVA, that uses a set of loop-free invariants to prevent the count-to-infinity problem. MDVA, in addition, computes multipaths that are loop-free at every instant. In our earlier work we shows how such loop-free multipaths can be used in traffic load-balancing and minimizing delays, which otherwise are impossible to perform in current single-path routing algorithms.
@cite_19: Abstract We present a distributed routing algorithm for computing multiple paths between each source–destination pair in a computer network, such that the paths are loop-free at all times and are not necessarily of equal length. In this algorithm, routers exchange second-to-last hop on the shortest path to destinations in addition to shortest distances, which are used to prevent the well-know count-to-infinity problem. The safety and liveness properties of the algorithm are proved and its performance is analyzed.
@cite_0: Internet service providers have to provision network resources to optimize bandwidth utilization. Dynamic routing protocols take traffic variations into account to control the load distribution. Multipath routing protocols attempt to take advantage of the path diversity to bring network robustness and reliability. Indeed, with a specific traffic engineering policy, they enable load balancing across several paths. Our aim is to compute a set of loopfree paths in order to allow routers to share the load on several next hops depending on current load measurement. In this paper, we first describe our original Incoming Interface Multipath Routing technique, DT(p), then we present a scheme for load balancing, DT(p)-TE, based on link monitoring. We evaluate and compare our technique with several existing approaches by a set of simulations, using different scenarios and topologies. The simulations results suggest that the path diversity achieved with our proposition can significantly improve the network response time.
@cite_12: The upcoming gigabit-per-second high-speed networks are expected to support a wide range of communication-intensive real-time multimedia applications. The requirement for timely delivery of digitized audio-visual information raises new challenges for next-generation integrated services broadband networks. One of the key issues is QoS routing. It selects network routes with sufficient resources for the requested QoS parameters. The goal of routing solutions is twofold: (1) satisfying the QoS requirements for every admitted connection, and (2) achieving global efficiency in resource utilization. Many unicast multicast QoS routing algorithms have been published, and they work with a variety of QoS requirements and resource constraints. Overall, they can be partitioned into three broad classes: (1) source routing, (2) distributed routing, and (3) hierarchical routing algorithms. We give an overview of the QoS routing problem as well as the existing solutions. We present the strengths and weaknesses of different routing strategies, and outline the challenges. We also discuss the basic algorithms in each class, classify and compare them, and point out possible future directions in the QoS routing area.
@cite_15: 
@cite_13: 
@cite_25: Unlike traditional routing schemes that route all traffic along a single path, multipath routing strategies split the traffic among several paths in order to ease congestion. It has been widely recognized that multipath routing can be fundamentally more efficient than the traditional approach of routing along single paths. Yet, in contrast to the single-path routing approach, most studies in the context of multipath routing focused on heuristic methods. We demonstrate the significant advantage of optimal (or near optimal) solutions. Hence, we investigate multipath routing adopting a rigorous (theoretical) approach. We formalize problems that incorporate two major requirements of multipath routing. Then, we establish the intractability of these problems in terms of computational complexity. Finally, we establish efficient solutions with proven performance guarantees.
@cite_20: 
Multipath routing have been discussed since the early years of networking. A large body of literature is available addressing different issues of multipath routing. For example, @cite_15 @cite_19 @cite_24 @cite_0 describe the way to deduce loop-free multipath routes in a hop-by-hop basis. Some other, such as @cite_13 @cite_25 , transform the multipath routing problem into constrained optimization to find the optimal way to forward traffic for highest throughput and lowest congestion. QoS routing is addressed in @cite_10 @cite_20 @cite_3 @cite_12 @cite_14 , which is to perform multipath routing to satisfy QoS guarantees.