Subject: Re: [pim] some questions/comments to PIM-SM draft-10

From: Mark Doll <[email-masked]>
Date: Tue, 05 Oct 2004 19:10:36 +0200

Hi Yi!

Venu Hemige pointed out to me, that (parts of) the Update_SPTbit macro 
would be executed out of band, thus one loses some packets if the 
forwarding rule is changed the way you've proposed:

Venu Hemige wrote (personal email):
 > Besides, changing the definition of the pseudo-code for forwarding per
 > Yi Zhao's suggestion may be theoretically correct, but one should
 > realize that only a portion of the pseudo-code can be implemented in
 > the forwarding plane of most implementations that use hardware-based
 > forwarding. By changing the definition per Yi Zhao, the first few
 > packets coming down the source-specific tree will not be forwarded
 > since (in most implementations) Update_SPTbit happens out-of-band. I
 > think the current definition is fine to handle most of the common
 > cases.

So both, the draft's version and your version (augmented with the fix 
below) have (different) drawbacks.

For SSM (at least with the fix below) no data packets are ever lost in 
both versions.

For ASM, one has to decide what might be worse: interrupting traffic on 
the RPT for (*,G) receivers (if SPT and RPT intersect two times) or 
losing some packets at the very beginning for the new (S,G) receivers 
(when injecting RPT traffic into SPT). And/or what might be more 
probable: SPT and RPT intersecting two times or the existence of shared 
LANs as transit networks.

Or in other words:

How should the case "both SPT and RPT upstream neighbors are on the same 
shared LAN" (aka RPF_interface(S) == RPF_interface(RP(G)) AND RPF'(S,G) 
!= RPF'(*,G)) be handled correctly:

Draft's version: inject RPT traffic into SPT as it arrives and risk 
blackholing all receivers for some short time if SPT and RPT intersect 
two times.

Your version (with my fix): wait for the Assert(S,G) to occur on the 
upstream shared LAN an miss forwarding some packets at the very 
beginning to new (S,G) receivers, starting with the packet that triggers 
the assert until the assert has been processed and SPTbit(S,G) has been 
updated.

I dont't know what's more appropriate.

If Update_SPTbit can be executed on every data packet, your version 
(without my fix) is superior, of course, since it has no drawbacks while 
the draft version's drawback still remains.

- Mark.

------------------------------------------------------------------------
P.S.: Here is my fix to your proposed change to the forwarding rule.

If we asume Update_SPTbit(S,G,iif) is too costly to be executed on every 
data packet arrival (which I think it is), one should use a data traffic 
independend variant Update_SPTbit(S,G) instead. The new version is the 
same as the old version except that the two conditions iif == 
RPF_interface(S) and RPF_interface(S) != RPF_interface(RP(G)) are omitted.

There are two cases where we might lose some packets during switchover 
from RPT to SPT:

In the first case RPF_interface(S) != RPF_interface(RP(G)), the RPF 
check between SPTbit == TRUE and SPTbit == FALSE differs, so we do not 
accept traffic correctly arriving via the SPT. This can be handled by 
another if clause in the forwarding rule (see the end of my email), 
which resembles the condition from Update_SPTbit(S,G,iif) that 
Update_SPTbit(S,G) omits.

The second is the case where we have to wait for an upstream Assert(S,G) 
to occur (I_Am_Assert_Loser(S,G,RPF_interface(S) == TRUE). Here, we will 
still loose some packets (at least the packet, that triggers the 
Assert(S,G)). This can't be changed if we want to prevent RPF traffic to 
be sent onto the SPT.

The SPTbit would be updated whenever one of the preconditions changes 
(becomes TRUE), thus not on data packet arrival:

void
Update_SPTbit(S,G) {
         if ( JoinDesired(S,G) == TRUE
	     AND ( DirectlyConnected(S) == TRUE
	           OR inherited_olist(S,G,rpt) == NULL
	           OR ( RPF'(S,G) == RPF'(*,G) AND RPF'(S,G) != NULL )
	           OR I_Am_Assert_Loser(S,G,RPF_interface(S) == TRUE ) {
		set SPTbit(S,G) to TRUE
	}
}

To sum up:

o If the RTT between the router and the sender is (considerably) smaller 
  via SPT than via RPT, we will loose packets anyway since we 
Prune(S,G,rpt) directly after receiving the first SPT data packet. So we 
miss to forward a number of packets (equivalent of what the senders 
sends during the span of time RTT(RPT)-RTT(SPT)).

o In the draft's version, we risc blackholing RPT traffic when SPT and 
RPT intersect two times - for both (*,G) and (S,G) downstream neighbors.

o In the new version, we miss to forward the first data packets via SPT 
on downstream interfaces with (S,G) state in one case:
- we have (*,G) state on other downstream interfaces
- we have no (*,G) state on the respective (S,G) downstream interface
- RPF_interface(S) == RPF_interface(RP(G)) and RPF'(S,G) != RPF'(*,G) 
(both SPT and RPT upstream neighbors are on the same upstream LAN)

So for SSM, no data packets are ever lost since we never have (*,G) state.

For ASM, we have to decide what is worse: interrupting traffic on the 
RPT for (*,G) receivers or losing some packets at the beginning for 
(S,G) receivers.

The complete forwarding rule (changes to my last email are marked with "|"):

if ( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S))
         set KeepaliveTimer(S,G) to Keepalive_Period
}
| # Note: no UpdateSPTbit(S,G,iif) any more; replaced by UpdateSPTbit(S,G)
   oiflist = inherited_olist(S,G,rpt)
   if ( SPTbit(S,G) == TRUE ) {
|	Label "SPT"
         # Note: start KAT only on nodes that have downstream RPT state
         if ( inherited_olist(S,G,rpt) != NULL ) {
                 set KeepaliveTimer(S,G) to KeepalivePeriod
         }
         # Note: set oiflist to inherited_olist(S,G)
         oiflist = oiflist (+) immediate_olist(S,G)
         if ( iif == RPF_interface(S) ) {
                 forward packet to oiflist (-) iif
         } else if ( iif in oiflist ) {
                 send Assert(S,G) on iif
         }
   } else {
         if ( iif == RPF_interface(RP(G)) ) {
                 # Note: Checking KAT is optional
                 if ( KeepaliveTimer is not running ) {
                         CheckSwitchToSpt(S,G)
                 }
                 forward packet to oiflist (-) iif
| 	} else if ( iif == RPF_interface(S) AND JoinDesired(S,G) == TRUE ) {
|		# Note: RPF_interface(S) != RPF_interface(RP(G))
|		#       transition from RPT to SPT completed
|		set SPTbit(S,G) to TRUE
|		goto Label "SPT"
         } else if ( iif in oiflist ) {
                 send Assert(*,G) on iif
         }
   }

   void
   CheckSwitchToSpt(S,G) {
         if ( pim_include(*,G) (-) pim_exclude(S,G) != NULL
              AND SwitchToSptDesired(S,G) == TRUE ) {
                 set KeepaliveTimer(S,G) to KeepalivePeriod
   }

#
# SPTbit(S,G) should be updated (aka Update_SPTbit(S,G) is called)
# whenever any of the included prerequisites changes from FALSE to TRUE
# (and SPTbit is still FALSE): So Update_SPTbit(S,G) is not data driven
# any more as Update_SPTbit(S,G,iif) was.
#
   void
| Update_SPTbit(S,G) {
|	# Note: "iif == RPF_interface(S)" omitted
         if ( JoinDesired(S,G) == TRUE
	     AND ( DirectlyConnected(S) == TRUE
|	           # Note: "RPF_interface(S) != RPF_interface(RP(G)" omitted
	           OR inherited_olist(S,G,rpt) == NULL
	           OR ( RPF'(S,G) == RPF'(*,G) AND RPF'(S,G) != NULL )
	           OR I_Am_Assert_Loser(S,G,RPF_interface(S) == TRUE ) {
		set SPTbit(S,G) to TRUE
	}
   }

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

---

From: "edrt"<[email-masked]>
Date: Wed, 6 Oct 2004 20:50:36 +0800

Hi Mark,

First, I want to make sure I correctly understand the problem Venu pointed out.
Take FreeBSD+pimd as example, when kernel saw data comming from SPT

a. If it is the first time kernel saw this multicast flow :
   After kernel send NOCACHE notification to pimd, and before pimd 
   calculate & install the MFC into kernel, kernel will cache the
   multicast packets coming from SPT.

b. If kernel already forwarding this multicast flow using upstream RPT
   branch, and if RPF_interface(S) != RPF_interface(RP(G)) :
   After kernel send WRONGVIF notification to pimd, and before pimd
   update SPTbit & refresh MFC in the kernel, kernel will continue forwarding
   traffic only to inherited_olist(S,G,rpt). 

c. If kernel already forwarding this multicast flow using upstream RPT
   branch, and if (RPF_interface(S) == RPF_interface(RP(G))) AND (RPF'(S,G) != RPF'(*,G)) :
   After Assert happens, and before pimd update SPTbit & refresh MFC
   in the kernel, kernel will continue forwarding traffic only to 
   inherited_olist(S,G,rpt). 

To sum up, with the new pseudo-code, and with the current FreeBSD+pimd 
synchronization mechanismin, in case b & c, the first few packets
coming from SPT won't be delivered to SSM state only downstream branches,
until after the data & control plane is synchronized.

And I doubt that with the current FreeBSD+pimd syhchronization mechanism,
kernel will lost first few packets from SPT in case b, even if we implement
user space pimd with the current draft forwarding pseudo-code. 

And your proposed patch
	>|		set SPTbit(S,G) to TRUE
seems won't solve the problem in case b on FreeBSD. Because packets triggered
WRONGVIF notifications to pimd still get dropped in kernel, and it also take 
time to let user space pimd recalc and refresh MFC in the kernel using this 
piece of pseudo-code, so the synchronization problem still there. 

Different implemenation might use different data & control plane synchronization 
model, may be on some platform this won't be a issue. So my personal opinion is to
leave this synchroniaztion issue to the implementor of the protocol and platform 
rather than changing the protocol.

Point out if I'm missing something.

Thanks
Yi Zhao

---

From: Mark Doll <[email-masked]>
Date: Tue, 12 Oct 2004 18:42:27 +0200

Hi Yi,

> rather than changing the protocol.

I agree, leaving it to the implementation is better, of course. But when 
specifying something that's not efficiently implementable, the statement
"A PIM-SM implementation [...] will still be comformant with this 
specification so long as it results in the same externally visible 
protocol behavior [...]" will render all those efficient implementations 
non-conformant. So it should be made explicit in the draft that, 
regarding the data forwarding rule, this requirement can be relaxed and 
it's up to the implementation how to relax it. Then I'm fine with an 
unimplementable abstract forwarding rule.

- Mark.