Subject: Re: Possible looping situation in MAODV?

From: Elizabeth Royer <[email-masked]>
Date: Thu, 16 Nov 2000 09:06:09 -0800 (PST)

Hi Lusheng,

You're right - the way the draft is worded now this could happen.
If we changed it to read, in Section 9.12, 

"...If the 'M' flag is unset, *and the node from which the GRPH 
message was received is the receiving node's upstream neighbor 
on the multicast tree,* then this node can also use the Hop Count 
value to verify its current distance from the group leader."

I think that would fix the problem.  Do you agree?

Thanks for pointing this out.

Elizabeth

~> 
~> While I was reading the MAODV draft (maodv-00.txt), found that
~> there might be a situation under which MAODV could not prevent
~> routing loops from forming.  The details is as follows.
~> 
~> MAODV orders all the nodes by hop counts to group leader.  During
~> tree link repairing, only those who are on tree and whose hop counts are
~> not greater than the hop count in RREQ (which is the repairing node's own
~> hop count to group leader) can reply the RREQ.  Of course, the group
~> sequence number is also taken into consideration for hop count
~> freshness.
~> 
~> 
~> At time T1:
~> 
~>   (L) ------ n1 ------- n2 ------ n3 ------ n4 ------ n5
~>   
~> (L) being the group leader, others are tree nodes.  A tree branch
~> exists as (L) <--- n1 <--- n2 <--- n3 <--- n4 <--- n5.  so n5
~> has hop count to group leader of 5 at this time.
~> 
~> 
~> At time T2:  
~> 
~>   (L) ------ n1 ------- n2
~>    .                    |
~>    .                    |
~>    .                    |
~>    n5 ------ n4 ------- n3
~> 
~> Now n5 and (L) have a link between them (not used by multicast tree).
~> After (L) sends out a new GRPH, n5 will update its "hop count
~> to group leader" to 1 and result in an inconsistency: n5 has a
~> very low hop count to group leader but actually in the multicast tree
~> it is far away from the leader.
~> 
~> if some link, say n2 -- n1 link, is broken, and n2 (which still has
~> hop count to leader as 2) tries to repair the link, n5 is qualified to
~> accept such repair join since its hop count is less than 2.  Then a
~> loop n5 -- n4 -- n3 -- n2 -- n5 may be formed. 
~> 
~> If I was reading the draft wrong, could someone please point it out
~> for me?  Thanks. 
~> 
~> Lusheng
~> 
~> 
~>

---

From: Lusheng Ji <[email-masked]>
Date: Thu, 16 Nov 2000 16:02:42 -0500 (EST)

Hi, Elizabeth,

Thanks for your reply.  Yes, that would fix the problem.

Another question is, when processing
a tree repair RREQ, some on-tree node, say node N,  may not be qualified
to reply if it's hop count is not small enough.  So N keeps forwarding
RREQ.  What will happen if a node, say R, receives the node N forwarded
RREQ and replies?  The reply path effectively cuts through a tree branch
at N. Appearently from the draft, N should switch its upstream neighbor to
whoever it receives RREP from.  But this could deactivate the sub-tree 
underneath node N.  I am not very clear about how MAODV handles this
situation and could you please give more details on this.

Thanks.
Lusheng