# Hop-by-Hop Multipath Overlay Routing for Optimizing Network Resource Allocation in WANs
## 3 System Design
### Overlay Hop-by-Hop Routing  
To address the congestion issues caused by large-scale data transfers and increase the efficiency of the network layer, we propose a best-effort approach where both load and cost are taken into account. In the hop-by-hop multipath routing algorithm, the cost of the tunnels is determined by latency, which is assumed to be relatively stable. Intermediate nodes can flexibly adjust paths by switching to an alternative next hop. During path selection, tunnels with lower costs are prioritized to reduce transmission costs. When congestion or failures occur, intermediate overlay nodes switch to paths with higher costs but a lower degree of congestion. The existing hop-by-hop multipath routing schemes ensure transmission reachability through LFI or DAG. In overlay networks, tunnels with different endpoints may have overlapping underlay links, which fail to bypass transmission bottlenecks. In the previous section, the overlay node placement method partially reduces path overlap by maximizing the path diversity of overlay nodes. However, path overlap cannot be eliminated with a limited number of overlay nodes. Path overlap in dynamic multipath routing can easily lead to a decrease in transmission efficiency. Examples are illustrated in Figure 4. A flow from source node A to destination node F has two paths: (A, B, C, F) and (A, B, D, E, C, F). Node A has node F and node D as its next hops. In the next hop selection, tunnel (A, F) and tunnel (A, D) overlap at the underlay link (A, B). The tunnel with the lower cost is (A, F). If link (A, B) is congested, switching the path to (A, D) cannot alleviate congestion. However, if link (B, C) becomes the bottleneck, tunnel (A, D) can bypass congestion. Another scenario involves multi-hop path selection. In this case, the link (C, F) is congested. Although tunnel (A, D) is not congested, switching paths is unable to alleviate congestion while degrading the performance. We address the issue by measuring the load of the adjacent tunnels at every overlay node. The Discounting Rate Estimator (DRE) [31] is a low-overhead measurement method for high-speed traffic, which is widely applied in data center networks and wide-area networks. It maintains a register that increases with the arrival of each packet and periodically (every \(T\)) decreases according to a factor \(\alpha\). The value of the register is proportional to the  
Figure 4: An example of bypassing congestion using hop-by-hop routing. transmission rate, with a coefficient of \(T/\alpha\). In the following discussion, it is assumed that the tunnel load is obtained through DRE and represented in a normalized form. During the routing, if the load of path (A, F) is heavier than the load of path (A, D, E, F), it means that two paths do not share the bottlenecks and path (A, D, E, F) is an alternative path. If both tunnel (A, F) and tunnel (A,D) are overloaded, congestion occurs at the overlapping link (A, B) and switching paths to (A, D) is invalid. And when the tunnel (A, D) is not overloaded, it is unclear whether the link (B, C) or link (C, F) is congested. Algorithm 2 presents the single-hop path selection Algorithm. The algorithm makes decisions at each node based on local load information, selecting non-congested nodes with the lowest cost from the next-hop set. ```
Input: The load \(l(h)\) and cost \(c(h)\) associated with each next hop \(h\) in the next-hop set \(H(x)\) towards the destination. Output: The selected next hop \(x\). 1\(x\gets h\) with lowest cost;
2 if\(l(x)\) indicate no congestionthen
3 return x;
4 foreach\(h\in H\)do
5 if\(l(h)\) indicate no congestion and \(c(h)<c(x)\)then
6\(x\gets h\) ;
7 return x;
```  
**Algorithm 2**Single-hop path selection  
While single-hop congestion is easy to identify, multi-hop path selection needs global coordination. The goal of multi-hop path selection is to avoid transmitting data to congested areas and to filter the paths that cannot bypass congestion.