# Hop-by-Hop Multipath Overlay Routing for Optimizing Network Resource Allocation in WANs
## 1 Introduction
On the other hand, the limited decision-making information at intermediate overlay nodes makes it difficult to identify globally optimal paths. This study investigates a hop-by-hop multipath transmission scheme for an overlay network. Building on the existing hop-by-hop multipath routing algorithm, this study mainly focuses on the unique challenges in the overlay network. To alleviate the impact of path overlap on overlay transmission, we propose a multipath overlay node placement (MOP) algorithm and an overlay next-hop selection (ONHS) algorithm. The novelty and strengths of the proposed MOP and ONHS algorithms are as follows:  
* MOP is designed to improve the path diversity in overlay node placement. Existing methods are based solely on single-hop and multi-hop overlay routing, serving only specific transmission node pairs. Instead, MOP focuses on the path diversity of each overlay and provides richer path selection for all-to-all transmission. * ONHS introduces a next-hop selection mechanism at the intermediate node. Unlike existing state-of-the-art methods that adopt source-based path selection, dynamic path selection at intermediate nodes not only provides a higher transmission bottleneck, but also responds in real time to the emerging congestion/failure. In the construction of the overlay network, MOP is developed to increase all-to-all path diversity for hop-by-hop multipath transmission. After performing the static multipath routing algorithm, ONHS efficiently selects the next hop in case of congestion. In short, the contributions of this study are as follows. * We propose a hop-by-hop overlay multipath routing method designed for WANS. Building on existing hop-by-hop multipath routing, this method improves transmission efficiency by enhancing path diversity, reducing path overlap, and efficiently utilizing link resources. * We introduce MOP, an overlay node placement algorithm that supports hop-by-hop overlay multipath routing. MOP employs a heuristic strategy to enhance both hop-by-hop path diversity and underlay link utilization, thereby improving the performance of all-to-all multipath transmissions. The experiment results demonstrate that MOP consistently improves both end-to-end path diversity and link utilization across different topologies and varying numbers of overlay nodes. * We introduce ONHS, a next-hop selection algorithm for overlay multipath routing. ONHS incorporates a local next-hop selection mechanism at intermediate overlay nodes and a global selection strategy for multi-hop routing. The method enhances multipath routing by avoiding the delivery of traffic to congested tunnels. The experimental results show that ONHS reduces the escalation of congestion by at least 20% across various network topologies. The rest of the paper is structured as follows. Section 2 reviews the related work of this research from the perspective of overlay node placement and overlay multipath routing. Section 3 elaborates on the design of MOP and ONHS, and the implementation of the hop-by-hop multipath routing in the overlay network. Section 4 evaluates the performance of the proposed algorithm. Finally, Section 5 concludes this study.