# A Distance-Vector-Based Multi-Path Routing Scheme for Static-Node-Assisted Vehicular Networks
## 3 RDV: The Base Scheme
### Packet Duplication  
In VANET, vehicles as carriers of packets move under their drivers' own will so that they might go away or park somewhere without forwarding packets to their next-relay nodes. To achieve reliable packet delivery under this kind of uncertainty, RDV creates several copies for each packet and forwards all of them to its next-relay nodes. Note that RDV creates the copies of a packet dedicated to reaching the next-relay node, i.e., the packet copies destine to its next-relay, and if they fail to reach the next-relay, they will be dropped silently. By forwarding multiple copies to a next-relay, we can raise the packet delivery ratio to a pre-configured level even under a relatively high drop probability for each packet.  
The mechanism of packet duplication in RDV to achieve the pre-configured expected packet delivery ratio is called APD. In APD, network administrators previously configure the end-to-end packet delivery ratio that they expect, and RDV generates packet copies at each intermediate node so that the expectation of packet delivery ratio exceeds the preconfigured value such as 99%.  
Now let \(P\) be the preconfigured expected delivery ratio to suffice, and let \(\delta\) be the distance in carry of the path to the destination. (See Table 1 for the definitions.) For each link \(l\) in the path, we denote the expected packet delivery ratio by \(E_{l}\). Since the delivery ratio of the path is expressed by the product of those of the included links, \(P\) is achieved if each included link \(l\) suffices \((E_{l})^{\delta}\geq P\), i.e., the least expected value of \(E_{l}\) is expressed as  
\[E_{l}=P^{\frac{1}{\delta}}. \tag{1}\]  
On the other hand, let \(R_{l}\) be the delivery ratio of link \(l\) measured by SVS, and \(D_{l}\) the number of duplicated packet copies on link \(l\), respectively. Then, to achieve the delivery ratio \(E_{l}\), two variables \(R_{l}\) and \(D_{l}\) must suffice the following formula:  
\[1-(1-R_{l})^{D_{l}}\geq E_{l}. \tag{2}\]  
From this, the smallest value of \(D_{l}\) to achieve \(E_{l}\) is computed as  
\[D_{l}=ceil(\frac{log(1-E_{l})}{log(1-R_{l})}), \tag{3}\]  
where \(ceil(\cdot)\) is the ceiling function. RDV achieves the preconfigured expectation of end-to-end delivery ratio if each of source and intermediate nodes generates \(D_{l}\) copies according to the above Formula (3).  
Figure 2 shows a concise example of APD. The expected delivery ratio that is previously configured by administrators is set as \(P=99\%\), and a packet is to be forwarded from \(n_{1}\) to \(n_{4}\). In this case, \(n_{1}\) computes the expected delivery ratio \(E_{l}\) for each link \(l=(n_{1},n_{2})\), \((n_{2},n_{3})\), and \((n_{3},n_{4})\) as 99.67% from the above equation. Since the measured delivery ratio of link \((n_{1},n_{2})\) derived from SVS is \(R_{(n_{1},n_{2})}=80\%\), the number of duplicated copies of the packet is computed as \(D_{(n_{1},n_{2})}=4\) from Formula (3). As a result, \(n_{1}\) forwards four packets to \(n_{2}\). Note that \(E_{l}\) is included in the packet and is notified to \(n_{2}\). With this information, \(n_{2}\) computes the number of duplicated copies to be forwarded to \(n_{3}\) in the same computational process as the case of \(n_{1}\).  
\begin{table}
\begin{tabular}{c c} \hline
**Variable** & **Value** \\ \hline \(p\) & Preconfigured expected delivery ratio. \\ \(\delta\) & Distance in carry for the destination. \\ \(E_{l}\) & Expected delivery ratio on link \(l\). \\ \(D_{l}\) & Number of duplicated copies on link \(l\). \\ \(R_{l}\) & delivery ratio of link \(l\) estimated by SVS. \\ \hline \end{tabular}
\end{table}
Table 1: Notations on Adaptive Packet Duplication (APD).