# A Distance-Vector-Based Multi-Path Routing Scheme for Static-Node-Assisted Vehicular Networks
## 4 MP-RDV: The Proposed Scheme
### Selection of Multiple Paths  
The basic strategy for multi-paths selection in MP-RDV is to use the primary and the secondary next-relays simultaneously, i.e., each static node forwards the copies of a packets to both relay nodes. However, a naive deployment of this strategy causes several problems. Figure 3: Example Scenario of Packet Forwarding in RDV (Reliable Distance-Vector routing): A packet is to be forwarded from \(n_{2}\) to \(n_{7}\) with the routing tables of \(n_{2}\) and \(n_{5}\) shown in Tables 2 and 3, respectively. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Dest.** & **Next\(\_\)-Relay** & **Prev.** & **Dist.** & **Del. Ratio** & **Metric** \\ \hline \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) \\ \(n_{7}\) & \(n_{7}\) & \(n_{6}\) & 1 & 90\% & 0.028 \\ \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) & \(\vdots\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Routing Table of \(n_{5}\) in Figure 3.  
The first problem is the so-called routing loop problem, which is shown in Figure 4. In this example, nodes \(n_{3}\) and \(n_{8}\) have packets that destines to the right side, e.g., \(n_{11}\). Node \(n_{3}\) has the primary relay \(n_{5}\) and the secondary relay \(n_{8}\), while \(n_{8}\) has the primary relay \(n_{10}\) and the secondary \(n_{3}\). If \(n_{3}\) and \(n_{8}\) distribute the packet copies into both relays, packets easily loop between \(n_{3}\) and \(n_{8}\) that consume the bandwidth and degrades communication performance significantly. We name the second problem \"same-street problem,\" which is shown in Figure 5. In this case, suppose that node \(n_{3}\) has packets whose destination lies on the right side, e.g., \(n_{11}\). If the primary relay is \(n_{5}\) and the secondary is \(n_{4}\), all packets are going into the same street, defeating the purpose of load balancing. Unfortunately, both problems easily occur frequently, which makes the multi-path mechanism useless. We must design the method that takes advantage of the merit of multi-path strategy and simultaneously prevents the two harmful defects. To this end, we propose to apply the following two conditions to utilize multiple paths. That is, when a packet is at a static node, only if both of those conditions are met, both the primary and the secondary relays are activated for the packet, and only the primary relay is used otherwise. (A) The distance in _carry_ of the secondary path is the same as or less than the primary path. (B) The previous-hop node of the secondary relay is different from that of the primary relay. Condition (A) is applied to prevent routing loops in combination with the primary and the secondary relays. If packets are always forwarded to decrease the distance in _carry_, they will surely not create loops. Condition (B) is applied to prevent the same-street problem. Since RDV passes packets to the vehicles that comes from the previous-hop node that has the largest probability to visit  
Figure 4: The Routing Loop Problem: When the secondary relay for a destination at \(n_{3}\) is \(n_{8}\) and the one at \(n_{8}\) is \(n_{3}\), packets on secondary paths would make routing loops. Figure 5: The Same-street Problem: When the primary and secondary relay for a destination at \(n_{3}\) is \(n_{4}\) and \(n_{5}\), respectively, those paths are along the same street and no load balancing effect is expected. the next-relay nodes, the vehicles from different previous-hop node are expected to go for different directions and visit different next-relays in many cases. One of the exceptions is when two roads are joining into a road, in which vehicles from those two source roads will go to the same direction. Excluding the exceptional cases, this rule solves the same-street problem with high probability.