Re: [manet] Default Forwarding Algorithm in OLSR

[Cedric Adjih <cedric.adjih at inria.fr>]

Hello Laurent,


> I'm really puzzled about section 3.4.1 of RFC3626 and ask for light from
> OLSR gurus.
> 
> Could someone give me the reason why the node have to record and check
> the "consideration for forwarding a message" by checking that the
> message come form a symetric neighbor before checking, again, that the
> node sending the message is a MPR selector or not ? Why not checking in
> the first place if it's a MPR selector or not ? Why the two tests ?

Yes, it's because somewhere in the OLSR drafts, the MPR flooding
changed: basically, now MPR selection is "per interface": each node tries,
on each of its interfaces, to have enough MPR to cover nodes there.
And MPR flooding is modified accordingly, so it's no longer about
"symmetric neighbor" but about "the sender interface address is in
the symmetric 1-hop neighborhood of the node" [sic] ; in other
terms whether the message comes on a symmetric link or not.

Because for instance, a symmetric neighbor of a node A can have one 
symmetric link with one interface A0 of A, and one asymmetric link
with another interface A1 of A.

Thus the node first checks the message comes on a symmetric link
and later the node checks the message comes from a MPR selector.

I understand the MPR flooding procedure may not be written in the 
clearest way, the cause being that the changes to the OLSR drafts had
to be minor so that no big awful bug would be introduced.

> Here what I understand from the RFC :
> 
> If the message is received from a neighbor that is not symetric the
> message is dropped and the "trace" of the message is not recorded
> 
> If the message is received the first time from a symetric neighbor that
> is not a MPR selector the "trace" of the message is registered in the
> Duplicate Set, the field D_retransmitted is leaved false and the message
> is not relayed
> 
> If the message is received the first time from a MPR selector the
> "trace" of the message is registered in the Duplicate Set, the field
> D_retransmitted is set to true, and the message is relayed
> 
> If the message if received a second time on the same interface it is
> discarded (already relayed or not).
> If the message if received a second time on another interface :
> check that the neighbor is symetric then :
>   if message is already relayed (D_retransmitted == true) then messsage
> is discarded and the interface address is *not* registered in the
> duplicated set
>    elseif the sender is a MPR selector the message is relayed and
> interface is added to duplicate set.

   ...else if the sender is not a MPR selector, the message is not
     relayed but the interface is added to the duplicate set.

Otherwise this is what happens (technically, if you replace also
"symmetric neighbor" with "on a symmetrical link")

> 
> Here what i  naively think could be done :
> 
> Change section ?4.1 of section 3.4 from RFC3626 :
> check that the message has not already been received on the same
> interface for so test :
> if message not already registered in Duplicate Set, or already
> registered but on another interface then goto section 3.4.1
> if message already registered on that interface then drop the message
> 
> Section 3.4.1 :
> register the message in the Duplicated Set (or only add that particular
> interface if enough)
> check if the sender is a MPR Selector
> if not then do not relay the message
> else relay the message
> 
> I've missed something, that is sure, because there is no more need of
> the D_retransmitted field, but i dont see what and where.

Hmm... OLSR is no longer a draft, but a RFC, so I guess it will
no longer (easily) be changed, but anyway:
The D_retransmitted field is used for retransmitting the message
at most once, so it is used because you can receive the message
on several interfaces. Example:
- you can receive the message on 10 interfaces from non-MPR selectors,
  and only retransmit it when receiving it on a 11th interface from a MPR
  selector.
- you can receive the message on 1 interface, from a MPR selector,
  you retransmit it ; then you receive it on 10 other interfaces from
  MPR selectors, but you no longer retransmit it.
The node receiving a 11th transmission should be able to differentiate
between the two previous cases.

As you have noted, the invariants of the algorithm are:
- A message is processed at most once
- A message is retransmitted at most once
- Only messages coming on symmetrical links are processed/forwarded
  (true for RFC3626 messages: HELLO, TC, MID, HNA).
- A message has been processed if and only if there is a duplicate tuple
  for it in the duplicate set
- D_retransmitted is set, if and only if the message has been retransmitted
- When D_retransmitted is false, D_iface_list gives the list of
  interfaces on which the message has been received

Hence I think it's difficult to remove D_retransmitted, because this
information doesn't look redundant.

Best Regards,
-- Cedric Adjih

Currently: cedric at net.ie.niigata-u.ac.jp,
Laboratory of Pr. Mase, Information Network Research Group,
Dpt of Information Engineering, Niigata University, Japan

_______________________________________________
manet mailing list
manet at ietf.org
https://www1.ietf.org/mailman/listinfo/manet