## 3 Delay Inversion and Jitter Optimizations
### The Delay Inversion Effect  
Consider the topology shown in Figure 1(a) and assume that router \(A\) floods an RREQ, in order to discover a route towards \(D\). A \"trivial\" hop count metric is used in this example, _i.e._, the path with less hops is preferred. Absent jitter, the RREQ would reach \(D\) through the path \(p_{2}=\{A,E,D\}\) faster than it would through the path \(p_{1}=\{A,B,C,D\}\); assuming that processing time at each intermediate router, before retransmission, is similar.  
Now, if a random delay on retransmission--jitter--is applied at each hop and if that jitter is selected from a uniform random distribution \([0,J_{m}]\), the message copy sent through the longer path (in terms of  
Figure 1: Timeline for packet flooding from \(A\): (**a**) Network topology; (**b**)With direct retransmission by \(B\) and \(C\); (**c**) With retransmission by \(B\) and \(C\) after a random delay. The network topology contains four routers \(\{A,B,C,D\}\) and four bidirectional links \(\{AB,AC,BD,CD\}\).  
the number of hops), \(p_{1}\), may reach the destination faster than the message copy over \(p_{2}\); and this, with a non-negligible probability. Figure 2b illustrates this case, and Section 4.1.1 analyzes the probability in further detail.  
With reference to Figure 2, consider the transmission of an RREQ packet from \(A\), received simultaneously at \(B\) and \(E\). Although the RREQ needs to traverse two hops (\(B\) and \(C\)) to reach \(D\) via \(p_{1}\) and only one hop (\(E\)) via \(p_{2}\), the RREQ sent across \(p_{1}\) may be received first at \(D\) if \(j_{E}>j_{B}+j_{C}\), as shown in Figure 2b.  
Router \(D\) replies to the route request from \(A\) with an RREP that advertises the (longer-than-shortest) path \(p_{1}\). When the RREQ, traversing \(p_{2}\), reaches \(D\), \(D\) replies by generating another RREP that advertises the (shorter) path \(p_{2}\). This implies that \(A\) gets, and possibly uses for a certain amount of time, a suboptimal path towards \(D\) (\(p_{1}\)), and it needs to receive two RREP from \(D\) in order to learn the optimal path from \(A\) to \(D\). If \(D\) is not the ultimate destination sought by \(A\), then \(D\) would retransmit two copies of the RREQ--one received via each of the paths \(p_{1}\) and, then, \(p_{2}\).  
This example illustrates that the use of a uniform random distribution for jitter values when forwarding RREQ packets during route discovery in a reactive routing protocol may lead to cases in which \"transmissions over longer paths get first\". This effect is hereafter denominated delay inversion caused by jitter.  
Delay inversion is harmful due to at least three undesirable effects:  
1. It increases the (probability of) sub-optimality of reported routes;
2. It increases the impact of data traffic forwarded through the network, as a consequence of the use of suboptimal routes; and
3. It increases the amount of control traffic: duplicate RREQs forwarded and multiple RREPs generated.  
Figure 2: Delay inversion example. Router \(A\) tries to broadcast an route request (RREQ) message through the network, through paths \(p_{1}\) and \(p_{2}\). The RREQ through the longer path \(\{A,B,C,D\}\) travels faster than the one through the shorter path \(\{A,E,D\}\), due to (unfortunate) jittering. (**a**) Topology; (**b**) Example of jitter value assignment for an RREQ from \(A\) towards \(D\).