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>I don't really understand where the loop is created here, to be honest.
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.
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.
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?
However, it looks like storing multiple unconfirmed routes is probably just a
bad idea (we should probably only store the first/best one).
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?
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>