Subject: Re: FW: [pim] PIM-SM: Assert Issue resulting in assert-loser forwarding onto LAN

From: Mark Doll <[email-masked]>
Date: Tue, 07 Sep 2004 17:19:47 +0200

Hi Venu!

Sorry, your description is not clear to me. Please provide a drawing
with your topology!

> PruneDesired(S,G,rpt) = RPTJoinDesired(G) && 
> *!lost_assert(S,G,RPF_Interface(RP(G)) &&*
> (inherited_olist(S,G,rpt) == NULL || RPF’(S,G) != RPF’(*,G))

At least this correction is false. Assume a router that switches
from RPT to SPT and RPF_interface(S) == RPF_interface(*,G) and RPF'(S,G)
!= RPF'(*,G)) (both SPT and RPT upstream neighbors are connected to the
same upstream interface). In this case, Update_SBTbit(S,G,iif) depends
on an upstream Assert(S,G) to occur. When the router loses the
Assert(S,G) on its upstream interface, the router knows that the
transition to the SPT has been completed and it should send 
Pune(S,G,rpt) to the RPT upstream neighbor. If you insert
"!lost_assert(S,G,RPF_Interface(RP(G))" you prevent this from happening
since PrundeDesired(S,G,rpt) does not become true.

But there is another issue regarding this case which Yi Zhao
([email-masked]) brought up in his email from 3. September. See no. 4
there. In the case I've described above the Pune(S,G,rpt) should be sent
to RPF'(*,G) and not to RPF'(S,G,rpt) ==
Assert_Winner(S,G,RPF_interface(RP(G)) == RPF'(S,G) != RPF'(*,G) as it
is currently specified!

Having said this, one could also argue that in this case sending 
triggered or periodic Prune(S,G,rpt) messages is superfluous since there 
was an Assert(S,G) which already prevents duplicate forwarding of data 
packets. So it might be ok to insert 
"!lost_assert(S,G,RPF_Interface(RP(G))". But I don't think that this is 
what the PIM designers intended (cf. "# Note:" comments in section 4.5.8).

Regards, Mark.

P.S.: Regardless if your proposed solution is wrong or not, I strongly 
believe that the current specification should be clarified/corrected.

_______________________________________________
pim mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/pim

---

From: "Venu Hemige" <[email-masked]>
Date: Tue, 7 Sep 2004 12:43:49 -0700

Hi Mark,

Let me describe the problem again first with a diagram.

Consider the following topology:

			(Source S)
			     |			
	               +--+			 
           ----------|Rs|--------
	     |         +--+	  |
	     | ^			  |  ^
	     | |RPF'(S)		  |  |RPF'(S)	
	     | |			  |  |
	     |			  |
RPF'(RP) +--+                 +--+
<------- |Ra|                 |Rb|
         +--+                 +--+
    	     |			  |	
	     |	<-- RPF(RP)	  |
	     ---------------------		
		  | Network LANx  |
		  |			|
		+---+           +---+
	  	| Rx|           | Ry|
		+---+		    +---+

Ra and Rb are two routers connected to the network LANx. 
The interface to LANx on router Rb is RPF_Interface(RP(G)).
Rs is the router to which the source S is connected.

And consider the following sequence of steps:

1. Router Rb sends a Join(*,G) to router Ra.
2. Router Rx sends a Join(S,G) to router Ra which is forwarded to router
Rs.
3. Router Ry sends a Join(S,G) to router Rb which is forwarded to router
Rs.
4. When traffic starts flowing down the SPT, Ra and Rb perform
Assert(S,G) election on network LANx and Ra becomes
Assert_Winner(S,G,LANx). Rb becomes Assert_Loser(S,G,LANx).
5. As a result, Ra continues to forward traffic to the network LANx.
6. Rb also forwards traffic to LANx because the interface to LANx is in
inherited_olist(S,G,rpt). This is because lost_assert(S,G,rpt,LANx)
returns FALSE since LANx is RPF_Interface(RP(G)).

So that is how we end up with two routers forwarding onto a LAN.

Now regarding the solution I proposed, I agree with you that in the
scenario you mention, we end up not sending a *triggered* Prune(S,G,rpt)
to RPF'(*,G). It does not however affect the behavior defined in section
4.5.8. We will still be sending periodic Prune(S,G,rpt) as per the
behavior defined in section 4.5.8. So it is not completely incorrect to
change PruneDesired(S,G,rpt) the way I proposed. To address the issue
with triggered prunes, it seems necessary to add another event to the
Upstream (S,G,rpt) FSM in NotPruned state that causes a triggered
Prune(S,G,rpt) to be sent when RPF'(S,G,rpt) becomes different from
RPF'(*,G). 

I disagree with your statement in the last paragraph of your email. It
is not superfluous to send Prune(S,G,rpt) in the case where RPF'(*,G) !=
RPF'(S,G,rpt). There could be local (*,G) receivers on the RPT upstream
neighbor resulting in it forwarding traffic to the LAN in the absence of
Prune(S,G,rpt). So it is still essential that we send a Prune(S,G,rpt)
even though there is an (S,G) assert state on RPF_Interface(RP). Of
course, as you and Yi Zhao mention, they need to be sent to RPF'(*,G)
and not RPF'(S,G,rpt).

Regards,

-Venu

> -----Original Message-----
> From: Mark Doll [mailto:[email-masked]]
> Sent: Tuesday, September 07, 2004 8:20 AM
> To: Venu Hemige
> Cc: [email-masked]; [email-masked]
> Subject: Re: FW: [pim] PIM-SM: Assert Issue resulting in assert-loser
> forwarding onto LAN
> 
> Hi Venu!
> 
> > (inherited_olist(S,G,rpt) == NULL || RPF'(S,G) != RPF'(*,G))
>

---

From: Mark Doll <[email-masked]>
Date: Wed, 08 Sep 2004 19:56:15 +0200

Hi Venu,

now things are clearer, although I'm still confused about the right 
solution.

Since the semantics of the different macros in the PIM-SM spec are still 
not 100% clear to me, I'm not shure what other pathological cases might 
break if something is changed. I need some more time to think about all 
this and the semantically correct behavior...

At least I agree with you, that your example is not handled correctly by 
the current spec and must be solved.

See my comments inline.

- Mark.

> Consider the following topology:

0. Router Rx (or Ry) sends a Join(*,G) to router Rb.

This places interface LANx on Rb into inherited_olist(S,G,rpt). Hmm, 
never recognised before, that a Join(*,G) received on the _upstream_ 
interface towards RP can make that interface's DownstreamJPState(*,G) 
transition to Join...

> returns FALSE since LANx is RPF_Interface(RP(G)).

Yes, you are right. lost_assert macros incorporate an RPF check, 
downstream J/P state machines don't do an RPF check on received joins.
This discrepancy causes the problem.

Substituting lost_assert(S,G,rpt) with lost_assert(S,G) in 
inherited_olist(S,G,rpt) as proposed by you is IMHO semantically 
incorrect. We are talking about traffic from the RPT. SPT traffic is 
handled with inherited_olist(S,G).

All this won't happen, if we can avoid to place the LANx interface of Rb 
into inherited_olist(S,G,rpt). No data packet will ever be forwarded 
onto this interface anyway, since it's the incoming interface for the 
RPT traffic...

> So that is how we end up with two routers forwarding onto a LAN.

Yes.

> Prune(S,G,rpt) to be sent when RPF'(S,G,rpt) becomes different from

ACK. I just thought that sending periodic prunes where we won't send a 
triggered Prune is semantically incorrect. So I applied the notes which 
explain the rationale behind periodic prunes to the triggered ones, too.

> course, as you and Yi Zhao mention, they need to be sent to RPF'(*,G)

You are right. I've missed the case with the local receivers. So the 
sending of Prune(S,G,rpt) messages _must_ be fixed.

---

From: "Venu Hemige" <[email-masked]>
Date: Wed, 8 Sep 2004 22:25:11 -0700

Hi Mark,

Please see comments inline.

<Portions of the original text deleted>

> interface towards RP can make that interface's DownstreamJPState(*,G)

[Venu Hemige]  I missed this aspect in the example scenario I pointed
out. Receiving a Join(*,G) on an upstream interface does not add the
interface to inherited_olist(S,G,rpt). The scenario requires local (*,G)
receivers on LANx with router Rb becoming the DR. That is how LANx would
end up with both downstream and upstream JP state for the (*,G). The
rest of the scenario and arguments remain the same.

> handled with inherited_olist(S,G).
[Venu Hemige] I don't see why this is semantically incorrect. Would you
say having pim_exclude(S,G) in inherited_olist(S,G,rpt) is also
incorrect? inherited_olist(S,G,rpt) is the olist that would be used for
a packet from S to G forwarding on the RP tree. Replacing
lost_assert(S,G,rpt) with lost_assert(S,G) makes this olist more
accurately represent the OIFs to which (S,G) forwarding must happen on
the RP tree. 

> onto this interface anyway, since it's the incoming interface for the
[Venu Hemige] Yes, this is the goal. If there is a better solution, then
we should look into that.

Regards,
-Venu

---

From: Mark Doll <[email-masked]>
Date: Thu, 09 Sep 2004 14:40:09 +0200

Hi Venu!

Changing inherited_olist(S,G,rpt) as you've proposed breaks another 
case. So this must be solved differently. But see below.

Venu Hemige wrote:
> interface to inherited_olist(S,G,rpt).

[MD] Please point me to the places in the spec, where receiving joins on 
upstream interfaces are excluded from processing in the downstream 
join/prune state machines, since I can't find them.

> The scenario requires local (*,G)

[MD] Ok, this is also possible.

> accurately represent the OIFs to which (S,G) forwarding must happen on

[MD] No, this will break the another (more regular) case. Asume the 
following topology:

        RP    S
        |     |
        Rx    Ry
        |     |
  ---+--+-----+--+----   <---- that's the LAN we are observing here
     |           |
     Ra          Rb
     |           |
     A           B
    (*,G)       (S,G)

1. Ra sends Join(*,G) to Rx because of receiver A joining G
    => LAN interface of Rx in inherited_olist(S,G,rpt)
2. Rb sends Join(S,G) to Ry because of receiver B joining (S,G)
    => LAN interface of Ry in inherited_olist(S,G), SPTbit(S,G) == TRUE
3. Both Rx and Ry forward data from S to G to their LAN interface
4. Assert(S,G) happens, which Ry wins
    => I_Am_Assert_Loser(S,G,LAN) == FALSE on Ry
       I_Am_Assert_Loser(S,G,LAN) == TRUE on Rx, Ra, Rb

    => lost_assert(S,G,rpt,LAN) == FALSE on Ry, Ra, Rb
       lost_assert(S,G,rpt,LAN) == TRUE on Rx(!!!)
    On Ry, Ra, Rb, this is because RPF_interface(RP(G)) == LAN
    On Rx, this is because
           RPF_interface(RP(G)) != LAN AND
           SPTbit(S,G) == FALSE(!!!) AND
           AssertWinner(S,G,LAN) != me

    => lost_assert(S,G,LAN) == FALSE on Rx(!!!), Ry, Ra, Rb
    On Rx(!!!), Ra, Rb, this is because RPF_interface(S) == LAN
    On Ry, this is because
           RPF_interface(S) != LAN AND
           AssertWinner(S,G,LAN) = me

So on Rx, lost_assert(S,G,rpt,LAN) == TRUE but lost_assert(S,G,LAN) == 
FALSE. If you now substitute lost_assert(S,G,rpt) with lost_assert(S,G) 
in inherited_olist(S,G,rpt), as you proposed, the LAN won't be excluded 
from inherited_olist(S,G,rpt) on Rx any more. So we end up with both Rx 
and Ry forwarding trafic to the LAN.

>>All this won't happen, if we can avoid to place the LANx interface of
> 
> Rb
> 

[MD] Looking at the above example, I'm wondering, what might be the 
rationale behind setting lost_assert to false although we obviously have 
lost the assert and I_Am_Assert_Loser is true (i.e. on Ra and Rb).

What would happen, if we omit the RPF check in the lost_assert macros 
like we omit it in accepting joins or local receivers? Maybe we have to 
recheck the paranthesis in the *_olist macros etc., but shouldn't it be 
possible to avoid deleting valid interfaces also without the RPF check 
in the lost_assert macros?! Or am I missing something really important here?

- Mark.

---

From: "Venu Hemige" <[email-masked]>
Date: Thu, 9 Sep 2004 11:24:09 -0700

Hi Mark,

Please see comments inline:

> Sent: Thursday, September 09, 2004 5:40 AM
> To: [email-masked]
> case. 

[Venu Hemige] I disagree. Comments inline below where you describe this
case.

> So this must be solved differently. But see below.
> 
> Venu Hemige wrote:
> >
[Venu Hemige] There is nothing in the spec to prevent a router from
accepting a Join sent to it on it's upstream interface. But if that
happens, there is a routing inconsistency and a loop. That should only
happen during topology changes and should get corrected when the
topology stabilizes. What I meant in my previous email was, a Join on an
upstream interface is typically (in stable state) a "See Join" event in
the Upstream J/P FSM as opposed to a "Rx Join" event in the Downstream
J/P FSM.

> and Ry forwarding trafic to the LAN.
[Venu Hemige] Your above analysis is correct, but incomplete. Ra must
send a Prune(S,G,rpt) to Rx since RPF'(S,G,rpt) != RPF'(*,G). That
should cause inherited_olist(S,G,rpt) on Rx to remove LAN from it's
olist.

Regards,
-Venu

---

From: Mark Doll <[email-masked]>
Date: Fri, 17 Sep 2004 15:04:27 +0200

Hi Venu!

Sorry for my late answer. Until now, I was truly convinced that you were 
right. :-)

But reading your email today again, I'm wondering what should Ra cause 
to send the Prune(S,G,rpt) message, that is needed to resolve the 
conflict between Rx and Ry. See my comment at the end of this email.

> should cause inherited_olist(S,G,rpt) on Rx to remove LAN from it's

[MD] Why should Ra send a Prune(S,G,rpt)? PruneDesired(S,G,rpt) is only 
true if either inherited_olist(S,G,rpt) == NULL or SPTbit(S,G) == TRUE. 
But neither applies to Ra, since Ra has receivers, and no source 
specific state. Rb also does not send a prune, since it has not joined 
the RPT. So this conflict lasts.

- Mark.

---

From: "Venu Hemige" <[email-masked]>
Date: Fri, 17 Sep 2004 16:09:07 -0700

Hi Mark,

Ra creates source specific state because of the (S,G) assert on the RPF
interface. And this results in RPF'(S,G,rpt) to become different from
RPF'(*,G) in your example.

Sadly, sending of Prune(S,G,rpt) is not entirely determined by
PruneDesired(S,G,rpt). Per section 4.5.8, Prune(S,G,rpt) will be sent if
RPF'(S,G,rpt) != RPF'(*,G) even though PruneDesired(S,G,rpt) is FALSE. 

I wish this were consolidated under PruneDesired(S,G,rpt) since:

1. It is otherwise confusing (both to a network operator and to a reader
of the spec) to see that Prune(S,G,rpt) messages are sent in "not
pruned" (S,G,rpt) state.
2. Sending triggered Prune(S,G,rpt) is not currently handled when
RPF'(S,G,rpt) becomes different from RPF'(*,G). 
3. It makes it modular to say Prunes(S,G,rpt) will be sent if and only
if PruneDesired(S,G,rpt) becomes true and also helps simplify section
4.5.8 to 
    if (PruneDesired(S,G,rpt)) 
	  add Prune(S,G,rpt) to compound message.

-Venu

> Sent: Friday, September 17, 2004 6:04 AM
> Cc: [email-masked]

---

From: "girishkg" <[email-masked]>
Date: Sat, 18 Sep 2004 16:49:47 +0530

Hi All,

1. think we should add the oif in the Oif list if a router receives a Join
on its upstream interface. This is a valid   scenario and our current draft
does not prevent also in doing so. Final oif List is build using --

oiflist = oiflist (-) iif

2. Triggered (S,G,Rpt) prune should not be send as a result of assert
happening on the upstream interface as it will defeat the purpose of Assert
mechanism for choosing the single forwarder on the M-LAN. Periodic (S,G,Rpt)
prunes will be send along with (*,G) join as described in draft.

3. For solving the problems we are discussing, we should either,
a) Remove the RPF check in -  lost_assert(S,G,rpt,I) macro as suggested by
Mark. (We can avoid changing the other lost_assert macors). The RPF check =>
Assert cannot happen on Iif of any entry as MDPs are never forwarded on Iif.

OR

b) Change the macro -

bool lost_assert(S,G,rpt,I) {
>>>>>   if ( RPF_interface(RP) == I  OR
         ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) {
       return FALSE
    } else {
       return ( AssertWinner(S,G,I) != NULL AND
                AssertWinner(S,G,I) != me )
    }
  }

to

bool lost_assert(S,G,rpt,I) {
>>>>>>   if ((RPF_interface(RP) == I) AND SPTbit(S,G) != TRUE)  OR
         ( RPF_interface(S) == I AND SPTbit(S,G) == TRUE ) ) {
       return FALSE
    } else {
       return ( AssertWinner(S,G,I) != NULL AND
                AssertWinner(S,G,I) != me )
    }
  }

Regarding the second fix, i feel, that if the forwarding of MDPs is due to
(S,G) entry then assert could not have happened because of Iif of (S,G)
entry and appropriate result is chosen by "else" case. Similarily, if the
MDPs were forwarded due to (*,G) entry then assert could not have happened
due to Iif of (*,G) entry.

Please excuse me if i missed something or if i didnt understand the problem
correctly.

Regards,
Girish

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]On Behalf Of
Venu Hemige
Sent: Saturday, 18 September 2004 4:39 AM
To: 'Mark Doll'
Cc: [email-masked]
Subject: RE: FW: [pim] PIM-SM: Assert Issue resulting in
assert-loserforwarding onto LAN

Hi Mark,

-Venu

***************************************************************************
This message is proprietary to Future Software Limited (FSL)
and is intended solely for the use of the individual to whom it
is addressed. It may contain  privileged or confidential information
and should not be circulated or used for any purpose other than for
what it is intended.

If you have received this message in error, please notify the
originator immediately. If you are not the intended recipient,
you are notified that you are strictly prohibited from using,
copying, altering, or disclosing the contents of this message.
FSL accepts no responsibility for loss or damage arising from
the use of the information transmitted by this email including
damage from virus.
***************************************************************************

---

From: Mark Doll <[email-masked]>
Date: Sat, 18 Sep 2004 14:51:40 +0200

Venu Hemige wrote:
[...]
> RPF'(S,G,rpt) != RPF'(*,G) even though PruneDesired(S,G,rpt) is FALSE. 

[MD] You're right, Venu. Those discrepancies between periodic and 
triggered Prune(S,G,rpt) are really a source of confusion (like the 
discrepancies between I_am_Assert_Looser and lost_assert). :-(

But failing to sent a triggered Prune(S,G,rpt) means that both, the SPT 
and the RPT upstream router, keep forwarding traffic onto LAN until the 
next periodic Prune(S,G,rpt) ist sent by the RPT downstream neighbor Ra. 
That's not good either.

> 	  add Prune(S,G,rpt) to compound message.

[MD] This would be much better, because this also means, that there's no 
case in which periodic prunes are sent but triggered prunes are not (and 
vice versa). Together with the issue Yi brought up about the differing 
upstream neighbors for Prune(S,G,rpt)---RPF'(*,G) vs. RPF'(S,G,rpt), I 
suppose, that the sections about Prune(S,G,rpt) should be revised in the 
current draft.

So your proposed fix works, but I still believe, that there is a better 
solution. Maybe this can be resolved by omitting the RPF checks from 
lost_assert macros (see my question to the pim list yesterday). I have 
to try this in our testbed to understand things better.

- Mark.