# Hop-by-Hop Multipath Overlay Routing for Optimizing Network Resource Allocation in WANs
## 3 System Design  
The goal of this study is to establish an overlay network that supports all-to-all hop-by-hop multipath transmission. In this network, the underlay network performs shortest-path routing, while the overlay network performs hop-by-hop multipath routing. To ensure the performance of overlay multipath transmission, two key principles are employed in the design. * **Maximized path diversity and underlying links utilization. ** During the routing process, it is essential to fully utilize multiple paths to bypass potential transmission bottlenecks. This requires minimizing the overlap of end-to-end paths and maximizing the use of underlying links. The metric is commonly found in classic algorithms related to overlay node placement [8; 10; 12] and multipath routing [16]. Maximized path diversity and underlying link utilization imply that end-to-end transmission experiences smaller transmission bottlenecks and higher resilience. * **Cost-effective intermediate node path switching** Intermediate nodes can flexibly switch paths when congestion occurs. In path switching, the next-hop node with the lowest cost and congestion relief is prioritized, avoiding unnecessary and excessive detours. This metric frequently appears in multipath routing algorithms, such as k-shortest paths and centralized path selection [13]. Achieving transmission with lower costs means the efficient utilization of network resources. The construction of the overlay network in this study involves the following steps. First, overlay nodes are selected from the underlay network, which serve as user access points and perform hop-by-hop multipath transmission. The placement of overlay nodes ensures path diversity for all-to-all transmissions. Second, an existing hop-by-hop multipath routing algorithm (LFI, MARA) is performed on the overlay topology based on the cost of tunnels. The cost is determined by the propagation delay and capacity of tunnels. It generates the next hop set for each intermediate node and ensures loop-free transmission. Third, overlay nodes periodically assess the load of tunnels to their adjacent nodes, and selectively choose the next-hops to mitigate the occurrence of unnecessary or excessive detours. Figure 1 illustrates the structure of the network. In the underlay layer, solid nodes represent standard network routing devices that support only shortest-path routing, while hollow nodes represent overlay nodes that support overlay-based multipath routing proposed in this paper. Overlay nodes are fully connected and capable of perceiving the status information of the overlay layer. The status and routing rules of the overlay layer nodes can be managed and maintained through the controller. In the overlay hop-by-hop multipath routing process, each intermediate node keeps a routing table with multiple next hops for each destination. Periodically, the selection of the next-hop node is narrowed based on the load of each tunnel. For example, Table 1 presents a routing table of the overlay network in Figure 1. The routing table includes the next-hop sets of every overlay node destined to node E, along with the cost and current load of each next-hop. For Node A, the shortest path to Node E is (A,C,E). When the load of tunnel (A,C) indicates that congestion occurs in its underlay links, the next hop of node A is adjusted to Node B and Node D. Node B has a lower cost than Node D, making it prioritized in the path selection. When the load of tunnel (C,E) indicates that congestion occurs in its underlay links, the next hop of node B is limited to Node D. The details of the overlay multipath transmission process are as follows:  
1. The controller generates the next-hop set for each overlay node based on existing hop-by-hop multipath algorithms. 2. At regular time intervals, the controller adjusts the original next-hop set of each overlay node based on the load conditions of all tunnels. During transmission, when a data packet arrives, the overlay node selects the next hop based on the destination of the packet.