Bugzilla – Bug 1951
AODV does not update nexthop for 1-hop nodes
Last modified: 2014-07-20 04:14:42 UTC
Created attachment 1854 [details] patch to the bugreport The Functions *RecvRequest* and *ProcessHello* add a neighbor route entry to the routing table for the sender of the packet. A neighbor route entry is one where the nexthop is equal to the destination (thus neighbor). If a route entry to the sender exists already, the existing entry will be updated instead. This update does not, however, update the nexthop field, as it should. For instance, A has a route to B via nexthop C. Now A receives a Hello packet from B and therefore knows that it can reach B directly (via nexthop B). Instead of updating the existing route entry so that the nexthop points to B, it updates all fields but keeps the nexthop to C. Even if C is no longer reachable, as long as A receives Hello packets from B, it will keep the wrong route. The following assertions [1] confirm this behavior, they were triggered in a grid-style network with some moving nodes and a probabilistic propagation model. We encountered a more severe result of this bug where the IP address 102.102.102.102 was encountered as a nexthop. This address is used by AODV as a dummy nexthop when searching for a route. The route entry has the status IN_SEARCH during this time. A Hello message at the wrong time *and* losses of the reply packets cause this route entry to become VALID without updating the nexthop. So we got a VALID route entry with nexthop 102.102.102.102, which causes crashes in the IP stack. In our case, changes we did were blocking some reply packets. It may be possible, albeit rare, that this behavior is encountered with unmodified AODV. The attached bugfix solves both of the problems described above by updating the nexthop field plus the hop count field (1 for neighbors). [1]: diff -r c5bf751f8d4e src/aodv/model/aodv-routing-protocol.cc --- a/src/aodv/model/aodv-routing-protocol.cc Mon Dec 02 23:05:14 2013 +0100 +++ b/src/aodv/model/aodv-routing-protocol.cc Tue Jul 15 11:57:45 2014 +0000 @@ -1112,6 +1112,8 @@ } else { + if(toNeighbor.GetNextHop () != src ) + assert(false && "error: validated bad route in RecvRequest()"); // BUG!!! toNeighbor.SetLifeTime (ActiveRouteTimeout); toNeighbor.SetValidSeqNo (false); toNeighbor.SetSeqNo (rreqHeader.GetOriginSeqno ()); @@ -1440,6 +1442,8 @@ } else { + if(toNeighbor.GetNextHop () != rrepHeader.GetDst () ) + assert(false && "error: validated wrong route in ProcessHello()");// BUG!!! toNeighbor.SetLifeTime (std::max (Time (AllowedHelloLoss * HelloInterval), toNeighbor.GetLifeTime ())); toNeighbor.SetSeqNo (rrepHeader.GetDstSeqno ()); toNeighbor.SetValidSeqNo (true);
Looks like a bug: Do you have a comparison of the aodv performance (throughput or packet delivery ratio) determined with the example manet-routing-compare.cc with and without your patch. for 1. Seed == 1 2. Seed == 2 3. Seed == 3 -john (In reply to Roman Naumann from comment #0) > Created attachment 1854 [details] > patch to the bugreport > > The Functions *RecvRequest* and *ProcessHello* add a neighbor route entry to > the routing table for the sender of the packet. A neighbor route entry is > one where the nexthop is equal to the destination (thus neighbor). > > If a route entry to the sender exists already, the existing entry will be > updated instead. This update does not, however, update the nexthop field, as > it should. > > For instance, A has a route to B via nexthop C. Now A receives a Hello > packet from B and therefore knows that it can reach B directly (via nexthop > B). Instead of updating the existing route entry so that the nexthop points > to B, it updates all fields but keeps the nexthop to C. Even if C is no > longer reachable, as long as A receives Hello packets from B, it will keep > the wrong route. The following assertions [1] confirm this behavior, they > were triggered in a grid-style network with some moving nodes and a > probabilistic propagation model. > > We encountered a more severe result of this bug where the IP address > 102.102.102.102 was encountered as a nexthop. This address is used by AODV > as a dummy nexthop when searching for a route. The route entry has the > status IN_SEARCH during this time. A Hello message at the wrong time *and* > losses of the reply packets cause this route entry to become VALID without > updating the nexthop. So we got a VALID route entry with nexthop > 102.102.102.102, which causes crashes in the IP stack. In our case, changes > we did were blocking some reply packets. It may be possible, albeit rare, > that this behavior is encountered with unmodified AODV. > > The attached bugfix solves both of the problems described above by updating > the nexthop field plus the hop count field (1 for neighbors). > > [1]: > diff -r c5bf751f8d4e src/aodv/model/aodv-routing-protocol.cc > --- a/src/aodv/model/aodv-routing-protocol.cc Mon Dec 02 23:05:14 2013 > +0100 > +++ b/src/aodv/model/aodv-routing-protocol.cc Tue Jul 15 11:57:45 2014 > +0000 > @@ -1112,6 +1112,8 @@ > } > else > { > + if(toNeighbor.GetNextHop () != src ) > + assert(false && "error: validated bad route in RecvRequest()"); // > BUG!!! > toNeighbor.SetLifeTime (ActiveRouteTimeout); > toNeighbor.SetValidSeqNo (false); > toNeighbor.SetSeqNo (rreqHeader.GetOriginSeqno ()); > @@ -1440,6 +1442,8 @@ > } > else > { > + if(toNeighbor.GetNextHop () != rrepHeader.GetDst () ) > + assert(false && "error: validated wrong route in > ProcessHello()");// BUG!!! > toNeighbor.SetLifeTime (std::max (Time (AllowedHelloLoss * > HelloInterval), toNeighbor.GetLifeTime ())); > toNeighbor.SetSeqNo (rrepHeader.GetDstSeqno ()); > toNeighbor.SetValidSeqNo (true);
Created attachment 1857 [details] Perfs comparison +1 to apply the patch. The performance comparison say that sometimes it's not a good idea to switch to a 1-hop away node just because you got a HELLO. However, this is totally normal for protocols not relying on link stability metrics. Moreover, a bug is a bug. We can't keep it alive just because sometimes it has a positive effect :P
changeset: 10846:c45f06192b19