# Hop-by-Hop Multipath Overlay Routing for Optimizing Network Resource Allocation in WANs
## 3 System Design
### Overlay Node Placement  
The underlay network is represented as \(G(V,E)\), where \(V\) is the set of underlay routers and \(E\) is the set of underlay edges. Assume that the cost of each link \(e\in E\) is assigned with its latency and capacity, and the graph is connected. The overlay network is layered on top of the existing underlay network. Compared with traditional IP nodes, overlay nodes are capable of dynamically switching the next-hop overlay node, detecting local congestion, and functioning as access points for users and service providers. The goal of overlay node placement is to select a subset from the underlay node set \(V\), and replace it with overlay nodes. Overlay nodes communicate through tunnels. Based on the adjacency relationships between nodes, an overlay topology can be constructed. The cost of constructing the overlay network is influenced by the number of deployed overlay nodes. Consequently, previous studies search for the minimum number of overlay nodes to meet the transmission requirements. In this study, the overlay network performs flexible hop-by-hop routing to meet all-to-all (rather than specific) transmission demands. Therefore, we assume that \(m\) overlay nodes are implemented to maximize the performance of multipath transmission on the overlay network. Theoretically, as the number of nodes increases, the benefit of multipath routing improves until it reaches an optimal point. The placement of the overlay nodes influences the performance and efficiency of the overlay network. According to the max-flow min-cut theorem, the end-to-end maximum bandwidth is equal to the transmission bottlenecks, which are determined by the number of disjoint paths. Overlay routing can utilize multiple disjoint underlying paths, thus improving the transmission bandwidth and reliability. In order to reduce path overlap in overlay multipath routing and increase the utilization of underlying paths, we analyze the characteristics of the hop-by-hop multipath. As the underlay network employs the shortest path routing algorithm, the underlying links used by an overlay network are the shortest path tree between the overlay nodes. Overlay nodes can alter the next-hop in hop-by-hop multipath routing, utilizing underlay links that are not in the shortest path tree rooted at the destination. By bypassing congested or failed paths, multipath routing enhances the overall transmission efficiency. As shown in Figure 2, on the shortest path tree with the destination node as \(dst\), each node can follow the shortest path to reach the destination. Node A, as an overlay node, can dynamically switch to the next hop overlay nodes B, C, D, or E, with Node B as shortest path and C, D, E as backup. However, if tunnel (A, C), (A, D), or (A, E) overlap with tunnel (A, B) (as shown in Figure 2b), the congestion in tunnel (A, B) cannot be completely bypassed, resulting in a transmission bottleneck. When overlay node A is replaced by node F, the overlap between tunnel (F, C), (F, D), (F, E) and (F, B) is reduced (as shown in Figure 2c), making it a better choice for node placement. In order to improve the overall ability to bypass congested or failed paths, the overlap of the next-hop of each overlay node is considered. \begin{table}
\begin{tabular}{c l} \hline
**Symbols** & **Definition** \\ \hline \(S\) & The neighbor nodes of node \(n\) \\ \hline \(U_{n}\) & The total underlay links occupied by node n with \(S_{n}\) \\ \hline \(F\) & The objective function of overlay node placement \\ \hline \(\alpha\) & The coefficient of \(\|U_{n}\|\) \\ \hline \(\beta\) & The finite difference of \(F\) \\ \hline \(\gamma\) & The level of node congestion \\ \hline \end{tabular}
\end{table} 
Table 2: _Cont._Another factor is the occupation of the underlay links. Based on the research in literature [9], we observe that the underlying links occupied by the overlay network are formed by a concatenation of shortest path trees with the overlay nodes as roots and their neighboring nodes as leaves.