[aodvv2-discuss] Re: Fwd: loop scenario

  • From: Lotte Steenbrink <lotte.steenbrink@xxxxxxxxxxxx>
  • To: aodvv2-discuss@xxxxxxxxxxxxx
  • Date: Wed, 17 Feb 2016 16:54:12 +0100

Hi Vicky,

Am 17.02.2016 um 10:50 schrieb Victoria Mercieca <vmercieca0@xxxxxxxxx>:

Hi Lotte,


On Tue, Feb 16, 2016 at 4:29 PM, Lotte Steenbrink 
<lotte.steenbrink@xxxxxxxxxxxx> wrote:
FYI, plus a comment about the new loop discovery inline...

Anfang der weitergeleiteten Nachricht:

Von: Behnaz yousefi <behyousefi@xxxxxxxxx>
Betreff: Aw: loop scenario
Datum: 16. Februar 2016 12:19:10 MEZ
An: Lotte Steenbrink <lotte.steenbrink@xxxxxxxxxxxx>
Antwort an: Behnaz yousefi <behyousefi@xxxxxxxxx>

 
Dear Mr. Steenbrink,
 
I’m really sorry for the delay. We intended to answer your email sooner but 
we found a new loop scenario and decided to get back to you after examining 
this new scenario, unfortunately it took longer than we expected :-(.  
 
Regarding your question about leaking information: Our paper is under review 
and we would really appreciate it if you could hold on till we receive the 
acceptance.
In addition as we mentioned before, we are trying to model aodvv2-version 
12. While modeling the new version, we have found a new loop scenario that 
we would like to check it with you. Consider the following scenario for a 
network of 5 nodes shown in figure1 where n0 wants to send a packet to n4:

<datauri-file.png>
 
Figure 1: The network of five nodes, nodes in the same communication range 
are connected through solid lines. 

 
1.       n0 initiates a route discovery procedure for destination n4 by 
multicasting a “rreq” message to n1 and n3. Suppose that the “rreq” message 
to n1 is not received duo to some congestion.
2.       n3 upon receiving the “rreq” message, after updating its routing 
table, multicasts the “rreq” to its neighbors, n2 and n0.
3.       n2 adds a route towards n0 with next-hop=n3 and hop-count=2. Then 
it multicasts the “rreq” to n1, n3 and n4.
4.       n0 retries to send the “rreq” to n1. Meanwhile n1 receives the 
“rreq” sent by n3 and adds a route towards n0 with next-hop=n2 and 
hop-count=3.
5.       Now n1 receives the “rreq” sent by n0. Because it’s a better route 
it would be added to the routing table, a route towards n0 with next-hop=n0 
and hop-count=1 .Then it multicasts the new route to its neighbors, n2 and 
n0.
6.       n2 processes the received “rreq” message from n1 and since the hop 
count of the new route is equal to the existing route in the routing table 
and the existing route is unconfirmed the new route would be added to the 
routing table with next-hop=n1 and hop-count=2. At this point a loop is 
formed between n1 and n2.
I don't really understand where the loop is created here, to be honest. 
Wouldn't a loop only be formed if the better routes were added to the table 
alongside the previously added ones (instead of the new info updating the old 
info, as mandated by the draft)? What am I missing? :/


Because the first route to n0 installed on n1 is still unconfirmed, the 
second RREQ would cause a second route to n0 be installed, also unconfirmed.
n2 ends up with 2 potential routes to n0, and n1 has 2 potential routes to 
n0, and if they end up choosing each other, there will be a loop. 

Exactly. I just didn't get why the route would be added instead of updated, but 
that's because I was only looking at section 6.7.1. instead of also looking at 
6.7.2.! My mistake, sorry :(


But a RREP coming back from n4 should be sent on the best unconfirmed route 
to n0.
n2 picks either n1 or n3, lets assume n1 because thats the worst case. We can 
assume n2 gets an ack, so the route to n0 becomes confirmed on n2. 
n1 would try to regenerate the RREP, picking the 1-hop route direct to n0. If 
that fails to be acknowledged, currently nothing happens for the route 
discovery process, it times out.

If another RREQ/RREP happened, n2 forwards the RREP, again to n1. n1 would 
now try to forward it to n2, the next hop on its best route to n0. n2 is 
probably stupid enough to acknowledge, and so the loop would form with routes 
being confirmed. n1 would think it had a route to n0 via n2 hopcount 3. n2 
would think it had a route via n1 hopcount 2.

Note: since the second received RREQ has a higher seqnum, any old info 
(unconfirmed or not) should probably get deleted/replaced?


You mean the RREQ you're describing in "if another RREQ happened, ..."? That 
sounds reasonable and I can't really come up with a scenatrio in which this 
would lead to links becoming less stable but that doesn't have to mean 
anything...

However, it looks like storing multiple unconfirmed routes is probably just a 
bad idea (we should probably only store the first/best one).

So we'd change 6.7.2. Applying Route Updates, point 2 to something like:

       *  If AdvRte has a different next hop to LocalRoute, and both
          AdvRte.NextHop's Neighbor.State is Unknown and
          LocalRoute.State is Active or Idle and Cost(AdvRte) < Cost(LocalRte),
          the advertised route offers improvement.  AdvRte SHOULD
          be used to update the existing LocalRoute. Continue to step 4.


? Again, sounds reasonable... But that means that if one link breaks during 
discovery, we'd have to start from the beginning, instead of having an array of 
alternatives to choose from, correct? (also, would that open up a new attack 
vector, since a malicious neighbor could "override" legitimate routes during 
discovery, triggering discovery retries across the whole network? or is that 
negligible since discovery retries are limited anyway?)

And 1 hop acks dont help.

Also I just had a thought...if we were to use end to end acks, how would 
blacklisting work?

oof, that's a good one...

Regards,
Lotte


Regards, 
Vicky.

 
Regards, Lotte

We are wondering if this scenario is feasible in the real world. As you see, 
the scenario is sound based on the following assumptions:
·n0 attempts to resend the “rreq” message when it doesn’t receive an “ack” 
from n1
·The resending procedure of the “rreq” message by n0 takes long enough that 
the “rreq” message passes through two nodes and be processed by them.
We would really like to get a feedback on the mentioned scenario and whether 
it conforms to the reality. Your feedback will affect on our base theory on 
verifying protocols.

Best Regards, 
Behnaz Yousefi
School of Electrical and Computer Engineering
University Of Tehran
Tehran ,Iran


On Monday, February 15, 2016 11:50 PM, Lotte Steenbrink 
<lotte.steenbrink@xxxxxxxxxxxx> wrote:


Dear Ms. Yousefi,
I was wondering if you'd had a chance to look at my e-mail below yet, or 
whether it may have gotten lost in a flurry of other e-mails? :) 

Kind Regards,
Lotte Steenbrink

Am 26.01.2016 um 17:08 schrieb Lotte Steenbrink 
<lotte.steenbrink@xxxxxxxxxxxx>:


Dear Ms. Yousefi,

Am 20.01.2016 um 19:36 schrieb Behnaz yousefi <behyousefi@xxxxxxxxx>:

Dear Mr. Steenbrink,
Thank you for responding to my email. It means a great deal to us to know 
that our findings were helpful and it motivates us to continue our work 
more eagerly. We really appreciate your answers to our questions they were 
very helpful, we would get back to you if we confronted any other ambiguity 
while modeling the new version.  
 

Great! :) For the sake of transparency, I'd like to share the fact that you 
found the loop (and we fixed it) with the MANET working group... Seeing as 
this does not appear to be part of your published work you cited, are you 
okay with this? (I don't want to accidentally leak any of your findings!)

As I mentioned in my previous email, we were modeling the version 12 and 
now we are going to switch to version
13 and check some properties such as loop freedom and monotonic increase of 
sequence numbers.We would like to know whether there is any specific 
property you want to be checked, if there is such property please let us 
know.  Please note that our current framework abstracts from time so it is 
not possible to check timed properties yet.

That sounds like a great offer, thank you. If we stumble upon anything we'll 
let you know.

 
We would be honored to be mentioned in the Acknowledgments section, thanks 
for your suggestion. My colleague’s names are as follows: Dr. Fatemeh 
Ghassemi and Dr. Ramtin Khosravi.     
 

Done!

With kind regards,
Lotte Steenbrink

 
Best regards,

Behnaz Yousefi
School of Electrical and Computer Engineering
University Of Tehran
Tehran ,Iran
 


On Tuesday, January 19, 2016 12:41 PM, Lotte Steenbrink 
<lsteen@xxxxxxxxxxxxxxxxxx> wrote:


Dear Ms. Yousefi,
thank you for prompting us towards your research and findings. I'm sorry
we didn't get back to you sooner, christmas etc. delayed our discussion a
bit...

In response to your findings, we've changed 6.7.1.  Evaluating Route
Information in version 13 of the draft, which was just published
(https://tools.ietf.org/html/draft-ietf-manet-aodvv2-13) so that
LoopFree() is *always* considered before adding a new route, even if all
known routes to date are Unconfirmed. Thank you so much for bringing this
to our attention!

Regarding your other questions:

-      What is going to happen to the other unconfirmed routes?
They would remain. We had thought they could be used in future, either
when the Ack fails to return from a sent RREP, or for other route
discovery attempts in future.

-      Would the second best route be used?
In general, yes: Section 6.7.2. Applying Route Updates says at the end:

  If this update to the Local Route Set results in multiple LocalRoutes
  to the same address, the best LocalRoute will be Unconfirmed.  In
  order to improve the route used for forwarding, the router SHOULD try
  to determine if the link to the next hop of that LocalRoute is
  bidirectional, by using that LocalRoute to forward future RREPs and
  request acknowledgements (see Section 7.2.1).

But with the new draft, the second best would be the first best, since the
faulty route shouldn't be added anymore.

-      Whether an “rerr” message is generated or an “rerr” message is
generated only when all unconfirmed routes become invalid?
The RERR is only generated if an Active route is lost. Idle routes may be
included in a RERR at this point, but Unconfirmed routes will never be
advertised as being lost.

Does this help? (In case you have any suggestions which/where
clarifications are needed in the Draft, they're greatly appreciated)

Additionally, we'd like to add you to the Acknowledgments section of the
next AODVv2 Draft. Are you okay with this, and are there any of your
colleagues who you think should be named also?

With kind regards,
Lotte Steenbrink (on behalf of the AODVv2 author team)







<datauri-file.png>



Other related posts: