[aodvv2-discuss] Re: Fwd: loop scenario

  • From: Victoria Mercieca <vmercieca0@xxxxxxxxx>
  • To: "aodvv2-discuss@xxxxxxxxxxxxx" <aodvv2-discuss@xxxxxxxxxxxxx>
  • Date: Thu, 18 Feb 2016 10:08:11 +0000

Hi Charlie, hi everyone,

I think this goes back to the discussion we had ages ago, where:
a) a router receives a RREQ and installs a route to OrigAddr (unconfirmed)
with next hop address equal to the source IP address of the RREQ
b) a RREP arrives for OrigAddr
c) next hop for the RREP to be regenerated to is known from
LocalRoute[OrigAddr]
d) router regenerates the RREP, hands it to IP to send to the next hop
e) the forwarding table hasnt got a confirmed route to the next hop it
needs to send the RREP to (I seem to remember this having something to do
with the fact we cant assume they are on the same subnet?). Anyway the RREP
cant be sent to the next hop, and the router might in fact try to initiate
a RREQ to discover a route for the next hop address before it can then send
the RREP from step b.

So if I remember correctly, Justin suggested we multicast the RREP in this
case. i.e. just the first time we send a RREP to that neighbor. After that,
the link is confirmed bidirectional and we have a valid confirmed route to
the next hop.

However, I don't think we mention saving a route to a next hop neighbor
anywhere in the draft? Should we?

Kind regards,
Vicky.

On Wed, Feb 17, 2016 at 8:25 PM, Charlie Perkins <
charles.perkins@xxxxxxxxxxxxx> wrote:

Hello folks,

I still think it is a terrible idea to require multicast for transmission
of RREP across temporarily unconfirmed routes to the originator of the
RREQ.  In case you missed the [intarea] presentation, the difference in
performance can be a factor over 500, and this will only get worse as
wireless speeds continue to increase.  See
https://www.ietf.org/proceedings/94/slides/slides-94-intarea-1.pdf.  By
the way, with 802.15.t even IoT will be in the Mb/sec -- see
http://www.ieee802.org/15/pub/default_page.html

Also, a routing loop should only be counted for confirmed routes.  Data
cannot traverse an unconfirmed link -- even if RREP can.  This makes sense
because then RREP is a *method* for confirming links.  We have other
methods for confirming links as well.  In fact, for certain physical media,
layer-2 automatically confirms links and we should explicitly allow such
media to enable "automatic" confirmation.

Regards,
Charlie P.


On 2/17/2016 1:50 AM, Victoria Mercieca wrote:

Hi Lotte,


On Tue, Feb 16, 2016 at 4:29 PM, Lotte Steenbrink <
<lotte.steenbrink@xxxxxxxxxxxx>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:

[image: Inline image]

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.

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>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>lotte.steenbrink@xxxxxxxxxxxx>:

Dear Ms. Yousefi,

Am 20.01.2016 um 19:36 schrieb Behnaz yousefi < <behyousefi@xxxxxxxxx>
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>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>
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)











PNG image

Other related posts:

  1. Home
  2. aodvv2-discuss
  3. Archive
  4. 02-2016