# Hop-by-Hop Multipath Overlay Routing for Optimizing Network Resource Allocation in WANs
## 2 Related Works
### Overlay Multipath Routing  
Multipath routing improves transmission throughput and reliability by obtaining multiple paths between transmission pairs. It can be categorized into two types: source-based and hop-by-hop. The source-based approach is widely used in SD-WAN scenarios. A centralized controller collects the network information and computes the transmission paths, with the endpoints routing the transmission paths in the packets via MPLS [4] or SRv6 [5]. Based on the concept of routing on disjoint paths, RB-trees [16] generate two independent trees for each destination. SPDP [17] improves the performance by reducing path stretch while generating disjoint paths. These methods only support source-selectable routing, in which the source chooses the routes from pre-calculated paths. To improve scalability, deflection routing [18] provides each router with a set of alternate next-hops and ensures loop-free paths. Path splicing [19] further lowers the cost of routing by introducing multiple routing trees. Each router can flexibly change the routing trees to form multipath, but lacks a mechanism to prevent routing loops. Ref. [20] computes multiple fully disjoint trees while maintaining efficiency and scalability. These methods give the selection of the best path a global perspective, making it suitable for large-scale data transmission. However, it has shortcomings such as long control cycles and limited scalability. Hop-by-hop multipath routing primarily obtains transmission paths by deploying distributed algorithms on network nodes. Since common network devices only support OSPF and IS-IS protocols, the application of such algorithms is not widespread in WANs. In the distributed routing protocol LISP [21; 22], nodes can change transmission paths based on the current congestion status and register the path information in a centralized mapping system. The endpoint nodes determine the transmission path by querying the mapping system. However, this approach still requires a registration query process and does not achieve full distribution. A common method is to assign priorities to different next hops [23]. Since overlay nodes are capable of measuring load, Ref. [13] introduces a semi-distributed method. The centralized controller generates transmission paths elastically based on network traffic, and intermediate nodes make routing decisions in response to congestion events. Since overlay nodes support more functionalities, this study intends to implement hop-by-hop multipath routing based on overlay nodes to enhance the scalability of multipath routing. The reference [24] estimates the underlay queue backlogs through a centralized approach to determine the optimal transmission strategy for overlay nodes and proves it to be throughput-optimal.  
Most existing overlay routing is source-based routing, which adopts topology planning in determining the efficiency and cost of the overlay networks. Resilient overlay networks (RON) [25] adopt a link-state routing protocol with short-interval probes, which causes a lack of scalability. Ref. [8] proposed a topology-aware overlay network that improves performance of end-to-end communications by leveraging path redundancy and maximizing path independence. Ref. [26] focused on designing overlay topologies by minimizing both overlay link creation costs and routing costs. Ref. [27] developed a minimal-cost communication network topology that adheres to predefined reliability constraints. Reference [28] proposed a method for dynamically configuring the topology based on service requirements. In [28], path overlap can be detected in both known and unknown underlay topologies. To introduce hop-by-hop multipath routing in an overlay network, an important issue is the overlap of underlay paths. While most existing methods rely on a global perspective, this study proposes a hop-by-hop multipath routing approach that avoids path overlap by incorporating both global and local perspectives.