NDP problem(s)

Lotte_Steenbrink2 · 7 April 2014 12:17

Dear RIOTers, for the past 2 weeks or so, I have been unable to wrap my head around a bug in my AODVv2 code which prevented any unicast messages (i.e. Route Reply packets) from being sent. There’s a high probability that some of this is my fault, but at this point, I’m wondering whether the current status of the NDP implementation might have something to do with it as well.

The problem is as follows: Whenever a Route Request (RREQ) Packet arrives at its Target Node (TargNode), the Target Node answers with a Route Reply (RREP) packet, basically saying “here I am, you’ve found a route to me, start sending your data”- While RREQs are broadcasted, a RREP is unicast back to the Originating Node (OrigNode), hop by hop. When a RREQ arrives at TargNode, it stores a route towards OrigNode in its routing table, with the 1 hop neighbor that sent the RREQ as the next hop towards OrigNode. So, when a RREP has to be sent, the next hop towards OrigNode is looked up and destiny_socket_sendto(_sock_snd, buffer, length, 0, &next_hop, sizeof next_hop) [1]is called. In consequence, ipv6_send_packet() is called, which asks the Neighbor Cache whether it knows about next_hop. Usually, the Neighbor Cache does not know about next_hop, even though it should. This leads to AODVv2 being called through the invocation of ip_get_next_hop(*next_hop) again. And while AODVv2 knows next_hop as a, well, next hop, it does not have a dedicated routing table entry towards next_hop (and manually adding one as soon as I get a packet from next_hop is prone to sequence number inconsistencies and other fuckups), so it starts a (non-blocking) route discovery for next_hop and returns -1. Oops. The code where this happens can be found in [2].

I’ve tried to figure out if I did something wrong and how to make this work, but I’m a bit stuck. So, my questions are:

did I do something fundamentally wrong? if not:
did I miss any pull requests that might fix this? If no, are any planned in the near future? (i.e. what’s the status?)
if all else fails, can I manually add a NDP entry for next_hop as soon as I get a packet from next_hop or will this just lead to me shooting myself in the foot more creatively?

Note:

I’m using https://github.com/RIOT-OS/RIOT/pull/873
I’m fairly certain that my code used to work, but that was before the build system was changed fundamentally (no more external modules…), so it’s a bit of a pain to revert.

I’d be very very grateful for any help.

Cheers, Lotte

[1] actually, next_hop is stored in a struct sockaddr6_t, but I’ve simplified that for better readability [2] https://github.com/Lotterleben/RIOT/blob/aodvv2-clean/sys/net/routing/aodvv2/aodv.c

Lotte_Steenbrink2 · 7 April 2014 14:22

Hi again, Martin Landsmann suggested that I should describe how to actually test this, so I created a gist: https://gist.github.com/Lotterleben/10021199

Cheers, Lotte

Christian_Mehlis1 · 8 April 2014 23:20

does your implementation do the following:

on rebroadcasting an RREQ: 1. add L2 addr <-> IP (from neighbor) to neighbor cache 2. add originator IP in routing table via IP from neighbor on reaching the target: 1. do what to do in case of rebroadcasting 2. answer with RREP with IP dest=originator 3. let the routing table handle the work

so RREP forwarding is not the task of the routing, it will use a route, which was created beforehand by the routing (RREQ handler).

makes that sense?!

Best Christian

Lotte_Steenbrink2 · 9 April 2014 18:15

Hi Christian,

No, because as far as I know, that’s NDP’s task

Yup.

Before the bug, it did, yes.

I’m not quite sure I understand what you mean by this, sorry. Could you rephrase?

Cheers, Lotte

emmanuelsearch · 9 April 2014 22:03

Hi Christian,

Dear RIOTers, for the past 2 weeks or so, I have been unable to wrap my head around a bug in my AODVv2 code which prevented any unicast messages (i.e. Route Reply packets) from being sent. There’s a high probability that some of this is my fault, but at this point, I’m wondering whether the current status of the NDP implementation might have something to do with it as well.

The problem is as follows: Whenever a Route Request (RREQ) Packet arrives at its Target Node (TargNode), the Target Node answers with a Route Reply (RREP) packet, basically saying “here I am, you’ve found a route to me, start sending your data”- While RREQs are broadcasted, a RREP is unicast back to the Originating Node (OrigNode), hop by hop. When a RREQ arrives at TargNode, it stores a route towards OrigNode in its routing table, with the 1 hop neighbor that sent the RREQ as the next hop towards OrigNode. So, when a RREP has to be sent, the next hop towards OrigNode is looked up and destiny_socket_sendto(_sock_snd, buffer, length, 0, &next_hop, sizeof next_hop) [1]is called. In consequence, ipv6_send_packet() is called, which asks the Neighbor Cache whether it knows about next_hop. Usually, the Neighbor Cache does not know about next_hop, even though it should. This leads to AODVv2 being called through the invocation of ip_get_next_hop(*next_hop) again. And while AODVv2 knows next_hop as a, well, next hop, it does not have a dedicated routing table entry towards next_hop (and manually adding one as soon as I get a packet from next_hop is prone to sequence number inconsistencies and other fuckups), so it starts a (non-blocking) route discovery for next_hop and returns -1. Oops. The code where this happens can be found in [2].

I’ve tried to figure out if I did something wrong and how to make this work, but I’m a bit stuck. So, my questions are:

did I do something fundamentally wrong?

does your implementation do the following:

on rebroadcasting an RREQ:

add L2 addr ↔ IP (from neighbor) to neighbor cache

No, because as far as I know, that’s NDP’s task

NDP’s task is fuzzy in spontaneous wireless networks ( that’s why NHDP is not redundant ;). Is NDP’s task to check proactively the bidirectionality of all links, to all neighbors continuously? Not really, although that is what you really need to be ready to process a RREQ.

Your basic problem is that you do not have a mechanism that checks bidirectionality of links with neighbors BEFORE you are in a situation where you consider using a link for reverse path forwarding…

A solution would be to have a common neighbor cache/table that NDP and NHDP would populate and maintain. But if you don’t have NHDP running, then you’re faced with actively checking link bidirectionality with the node who sent you the RREQ after you receive this RREQ, before you consider forwarding the RREQ (or sending back the RREP if you are the target of the RREQ). With NDP, this is done with RS/RA exchange.

So the flow with this is:

Receive RREQ from node X Check NDP cache for entry matching X If match forward RREQ (or send reverse path RREP) If no match initiate RS/RA exchange with X If successful, forward RREQ (or send reverse path RREP) Else drop RREQ

While this does not look so great, anything else with NDP would be tentative at best. You could as Christian suggest manually add an NDP cache entry upon RREQ receival if none is there, but that does not mean that node X actually hears you, since you never checked that. Thus, by doing so, you are pushing the problem around, to AODV blacklisting mechanism for example (which will handle it somehow, but with a different trade off that yields more delay, especially if the path is long and the unidirectional link close to the source ).