[aodvv2-discuss] Re: Fwd: loop scenario

  • From: Victoria Mercieca <vmercieca0@xxxxxxxxx>
  • To: "aodvv2-discuss@xxxxxxxxxxxxx" <aodvv2-discuss@xxxxxxxxxxxxx>
  • Date: Tue, 12 Jan 2016 09:17:15 +0000

Hi all,

True, as happens in step 4, we have said "if the current routes are
unconfirmed, save this one also as unconfirmed" without looking at
LoopFree. If we looked at LoopFree, we wouldnt have stored it. So n1 and n4
do store Unconfirmed routes to n2 via each other.

The RREP created in step 6 would be sent in response to the first RREQ
received, say for example this is from n1. If the second one (via n4)
offered a better metric, a second RREP might be generated. Either way, the
next hop neighbour is not confirmed so the AckReq is included, and though
the RREP is multicast, it is processed only by the intended next hop (the
address in the AckReq data element).

Assuming we dont know n2 has disappeared:
First n1 processes the RREP, sends the Ack to n3, forwards the RREP to its
best next hop (n2). If no ack returns...it deletes that unconfirmed route.
I dont think Draft 11 doesnt say anything about testing the next
unconfirmed route if the first one fails to send an Ack.
If a second RREP got sent when the RREQ from n4 arrived, the same happens.
If in future the link was confirmed somehow between n4-n1, then they would
both make the route via each other valid. Forming a loop.
Also, n1 could, if the implementation allowed it, then send the RREP to the
next hop on the other unconfirmed route, ie to n4. n4 might send an ack,
try to forward the RREP and get no Ack back and delete the unconfirmed
route, then try the next unconfirmed route which is via n1, If it
regenerated the RREP to n1, n1 would send an ack, and yes both n1 and n4
would try to route via each other for n2. Forming a loop.

If we do know n2 has disappeared:
The direct route to n2 is deleted at n1 and n4. No RERR is sent because the
route was unconfirmed. The unconfirmed routes via n1/n4 remain. If the RREP
then arrives for n1, it gets forwarded to n4, n4 sends an ack, and would
then try to forward the RREP to n1, I guess? Forming the loop.



The problems are:
a) that we dont do an end-to-end ack, and
b) that we saved the route from n4-n1 and from n1-n4 as unconfirmed at the
beginning.
Perhaps LoopFree should also apply in draft 11 section 6.5.1 step 1, where
it said:
" * If all matching routes have State set to Unconfirmed, AdvRte
SHOULD be used to update the routing table, so that it
contains multiple Unconfirmed routes. "
However, doing this before LoopFree means we could be allowing loops.
It was meant as a way to store a bunch of potential routes, intending that
the best one would be used to forward messages and ideally be verified,
otherwise offer some others to try... But it looks like it would be safer
to only store multiple Unconfirmed routes if they pass the other tests in
6.5.1 (6.7.1 in the newer version of the draft).




To respond to the 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?
I had thought this could happen, and the current draft says:
" 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)."
However, since that route has not been guaranteed LoopFree, it shouldn't
have been installed in the first place.

- 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.



Final recommendations:
In Draft 13 6.7.1 in step 1, a snippet of which is below, remove the
statement regarding Unconfirmed, but include Unconfirmed in the list on the
other statement (basically, if theres an existing route in any state,
continue to step 2 to check for improvement/loopfree).
* If all matching LocalRoutes have LocalRoute.State set to
Unconfirmed, AdvRte SHOULD be added to the Local Route Set.

* If a matching LocalRoute exists with LocalRoute.State set to
Active, Idle, or Invalid, continue to Step 2.
Also in step 4, update this statement to say if Invalid/Unconfirmed:
* If AdvRte is not better (i.e., it is worse or equal) but
LocalRoute is Invalid, AdvRte SHOULD be used to update the
Local Route Set because it can safely repair the existing
Invalid LocalRoute.


Anyone else had time to take a look?

Kind regards,
Vicky.

On Mon, Jan 11, 2016 at 11:27 PM, Lotte Steenbrink <
lotte.steenbrink@xxxxxxxxxxxx> wrote:

Next try :)

Anfang der weitergeleiteten Nachricht:

*Von: *Behnaz yousefi <behyousefi@xxxxxxxxx>
*Betreff: **loop scenario*
*Datum: *15. Dezember 2015 01:43:02 MEZ
*An: *"draft-ietf-manet-aodvv2@xxxxxxxx" <draft-ietf-manet-aodvv2@xxxxxxxx

*Antwort an: *Behnaz yousefi <behyousefi@xxxxxxxxx>

Dear AODV-v2 authors,

We have implemented a formal framework to model wireless protocols with
the aim to verify their properties. To this aim, we provide wRebeca, an
extension of bRebeca [1], to specify protocols and CACTL, the logic to
specify properties dependent to the underlying topology [2]. We have
provided tools [3] to support modeling ad-hoc protocols and subsequently
verifying the desired properties against those protocols automatically.

We have modeled AODVv2-11 as our case study. We tried to resolve
ambiguities to the best of our knowledge. The biggest ambiguity that we
encountered was the way an “rrep” message is sent while there are multiple
unconfirmed routes available. We assumed that all unconfirmed routes are
considered while sending the “rrep” message and found the following
scenario in which the loop-freedom property is violated, consider the
network topology shown in Figure 1:

[image: Inline image]

Figure 1: The network of four nodes, dotted lines represent nodes
communication ranges

1. n2 initiates a route discovery procedure for destination n3 by
broadcasting a “rreq” message.
2. n1 and n4 upon receiving the “rreq” message, add a route to their
routing tables towards n2 and store n2 as their next hop. Since it is the
first time that these nodes have received a message from n2, the neighbor
state of n2 is set to unconfirmed. Therefore, the route state is
unconfirmed.
3. As n1 and n4 are not the intended destination of the route request,
they rebroadcast the “rreq” message.
4. n1 receives the “rreq” message sent by n4 and since the route to n2 is
unconfirmed it adds n4 as new next hop to n2.
5. n4 also adds n1 as the new next hop towards n2 after processing the
“rreq” sent by node1. At this point a loop is formed between n1 and n4 but
not used yet.
6. n3 receives the “rreq” message sent by n1 and since it is the
destination, it sends a “rrep” message towards n1.
7. n2 moves out of n1 and n4 communication range.
8. n1 receives the “rrep” message sent by n3 and as the route state
towards n2 is unconfirmed it multicasts the “rrep” message to the existing
next hops, n2 and n4. Since n4 is adjacent to n1, it receives the message
and then sends an ack to n1. Therefore, n1 sets the neighbor state of n4 to
confirm and subsequently the route state towards n2 to valid. Then expunge
the next hop n2 which has not received an ack from.
9. n4 by receiving the “rrep” message from n1 multicasts it to its next
hops towards n1 and n2,
and similar to n1 it updates its routing table by validating n1 as its
next hop to n2. At this point, a loop between n1 and n4 becomes valid.
We would like to know if you are aware of this scenario. And you have any
approach to remove it?

We have known that there is a new draft AODVv2-12, and we would like to
model and verify it. We noticed that in the new draf, AODVv2-12, you tried
to clarify the mentioned ambiguity in AODVv2-11 by specifying that:
“*If all matching routing table entries have State set to Unconfirmed,
AdvRte SHOULD be added to the routing table. This may result in multiple
Unconfirmed routes to the same address. In this case, the best route from
the set of Unconfirmed routes SHOULD be used to forward future RREPs*”.
I assume that by “best route” you mean the route that has the best cost,
am I right?
Consider the situation when after sending the “rrep” message through the
best route no ack is received therefore according to the protocol the next
hop must be marked as blacklisted and the route should become invalid. I
was wondering
- What is going to happen to the other unconfirmed routes?
- Would the second best route be used?
- Whether an “rerr” message is generated or an “rerr”
message is generated only when all unconfirmed routes become invalid?

We would really appreciate it if you answer our questions and help us to
resolve the ambiguities in our specification.

*References *
[1] Yousefi, B., Ghassemi, F., Khosravi, R.: Modeling and efficient
verification of broadcasting actors. In: In preproceeding of 6th IPM
International Conference on Fundamentals of Software Engineering. pp.
114–128 (2015)
[2] Ghassemi, F., Ahmadi, S., Fokkink, W., Movaghar, A.: Model checking
MANETs with arbitrary mobility. In: Fundamentals of Software Engineering,
pp. 217–232. Springer (2013)
[3] wRebeca modeling language.
http://rebeca.cs.ru.is/files/Tools/Broadcasting-Actors-Setup.exe

Best Regards
Behnaz Yousefi
M.Sc. Student, Formal Lab
School of Electrical and Computer Engineering
University Of Tehran
Tehran ,Iran



PNG image

JPEG image

Other related posts:

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