[Xorp-hackers] about the implementation of PIM-SM

[Pavlin Radoslavov]

> I'm reading the XORP source code,and I have two questions about
> the implementation of PIM-SM:
> 
> 1:In the PIM-SM specification,Data Packet Forwarding Rules:
> On receipt of data from S to G ,we should deceide whether the KAT
> should be set,at the same time, we should update the
> SPTbit(S,G,iif).But in the implementation(XORP),we'll do it only
> when we received the IGMPMSG_NOCACHE and IGMPMSG_WRONGVIF messages
> from the Kernel.This is the special cases,not every time we
> received the multicast data.
> 
> It seems that the implementation is unconformity with the
> specification,How to interpret it?

The Data Packet Forwarding Rules as described in the spec are for
correctness. An implementation might use a more practical approach,
as long as the result is equivalent.

The spec description assumes per-packet updating of the KAT and the
SPT bit. In XORP, both the KAT and the SPT bit are kept per routing
entry (in user space), hence it will be very inefficient to update
them per forwarded data packet.

The work-around solution for the KAT is following:
When the first multicast data packet arrives, the userland program
will receive the IGMPMSG_NOCACHE upcall. Eventually, the processing
of that upcall will set the KAT for the corresponding (S,G) routing
entry. Also, the userland program starts measuring the forwarding
bandwidth for the (S,G) dataflow. The measurement is done by the
MFEA (by reading the forwarded packets/bytes from the kernel), or by
the kernel itself (e.g., on *BSD systems).
If the (S,G) forwarded bandwidth is 0 during the KAT period, then
the KAT is timed-out.

The work-around solution for the SPTbit is based on the following
observation. The Update_SPTbit(S,G,iif) function that should be
called per each forwarded data packet is defined as:

     void
     Update_SPTbit(S,G,iif) {
       if ( iif == RPF_interface(S)
             AND JoinDesired(S,G) == TRUE
             AND ( DirectlyConnected(S) == TRUE
                   OR RPF_interface(S) != RPF_interface(RP(G))
                   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,iif) ) {
          Set SPTbit(S,G) to TRUE
       }

However, for all practical purpose there is no reason to reevaluate
all conditions it per packet; instead, we should reevaluate them
only when any of the term is changed.
E.g., we should call Update_SPTbit() if one of the following
changes:
 - RPF_interface(S)
 - JoinDesired(S,G)
 - DirectlyConnected(S)
 - RPF_interface(S)
 - RPF_interface(RP(G))
 - inherited_olist(S,G,rpt)
 ...


All of this is implemented by event-tracking mechanism in XORP,
hence again we don't need to call Update_SPTbit() per each forwarded
data packet.


> 2:Because Linux Kernel only support (S,G) multicast forwarding
> entries,so XORP also only add the (S,G) entries to the Kernel
> MFC.
> If the Kernel received a multicast packet and can't find a MRT in
> the MFC,it send the IGMPMSG_NOCACHE message to the PIM-SM
> module.Now we use the user-level task(PIM-SM module) to forward
> that packet?? is that right??

Not exactly.
When the kernel sends the IGMPMSG_NOCACHE upcall to userland,
it queues the data message for a short period of time (few
seconds).
When the userland receives the IGMPMSG_NOCACHE upcall, it only
installs the corresponding MFC entry in the kernel. During the
installation process, the kernel itself checks if there are any data
packets queued for this MFC entry. If "yes", those packets are
forwarded by using the new MFC entry.

Regards,
Pavlin