# Hop-by-Hop Multipath Overlay Routing for Optimizing Network Resource Allocation in WANs
## 1 Introduction  
The rapid advancement of technologies such as AI and big data analytics is driving the expansion of data centers worldwide [1]. The increase in data centers has intensified the traffic across the wide area networks (WANs), which connect the vast storage and computing capacities in data centers to users and service providers. The features of this traffic are large volume, long distance, and delay requirements. Thus, the efficient utilization of network resources in WANs has become critical. One solution is the use of overlay networks [2]. It is built on top of a legacy network, and can re-route traffic with overlay routing decisions generally made by centralized controllers. Existing overlay solutions are mostly implemented with SD-WANs [3] and built on private clouds, leading to limitations in scalability and flexibility. To overcome this problem, we propose to leverage overlay networks as a public infrastructure that efficiently allocates network resources to all users. The primary challenge is ensuring scalability in overlay routing while optimizing all-to-all transmission performance. Existing overlay routing solutions predominantly rely on source-based routing, which utilizes pre-determined paths with multiprotocol label switching (MPLS) [4] or segment routing [5]. As the network scale increases, the number of paths grows exponentially, which expands the computational complexity and control cycles of the centralized resource allocation. While an intermediate overlay node can dynamically re-route packets, source-based routing limits routing decisions to the network edges. In contrast, hop-by-hop multipath routing offers multiple next-hop options for each destination, and avoids loops through Loop Free Invariant (LFI) [6] or directed acyclic graphs (DAGs) [7]. This method allows dynamic path switching at intermediate nodes and provides a design space for large-scale overlay routing. However, in the overlay network, tunnels can share overlapped underlay links, which diminishes the performance gain of switching next hops. We tackle this problem from the perspective of overlay node placement and path selection. The placement of overlay nodes is determined by the service requirements. For all-to-all multipath transmission, nodes are chosen either by minimizing single-hop path overlap [8], maximizing the throughput region [9]. For specific transmissions pairs [10; 11; 12], overlay nodes are selected based on network topology to ensure that the number of paths meets predefined criteria. These methods are aligned with source-based or single-hop overlay routing. In multi-hop overlay routing, all-to-all routing performance needs to be considered to enable optimal hop-by-hop routing. In order to generate paths with minimal overlap [10], it is necessary to increase the path diversity between any two overlay nodes by leveraging the max-flow min-cut theorem. This study improves the path diversity by increasing the number of utilized underlay links and reducing the overlap among overlay tunnels. Next-hop selection determines the end-to-end paths of multipath routing. Elastic data flows in the network are capable of dynamically adjusting the transmission rates in response to the available network resources [13]. Compared with the fixed selection of paths in source-based routing, the selection of end-to-end paths grows exponentially with the number of traversed intermediate nodes in hop-by-hop routing. Due to the overhead of tracking end-to-end paths at intermediate nodes, flow information is not recorded and flows are divided into smaller units (flowlets [14], etc). When congestion occurs, flows switch to paths with lower congestion levels and gradually saturate all the available paths. This enables elastic allocation of network resources. However, there are obstacles in this process. On the one hand, the overlap of underlay paths reduces the potential transmission gain from path switching.