Subject: GenID in PIM-SM

From: Narayanan Vidya-CVN065 <[email-masked]>
Date: Thu, 12 Apr 2001 15:22:59 -0500

All,
The GenID spec (now incorporated into the revised PIM-SM draft) states that a router should send out a hello with a new GenID as soon as it boots up. Following this, it will receive hellos from its neighbors and the BSM from the DR and any multicast state as appropriate. 

My understanding has always been that a router only accepts an RP-Set/BSM if it has unicast routes to the BSR and all the C-RPs in that RP-Set. If that is true, would it not be necessary to wait for unicast convergence before sending the PIM Hello with the new GenID? In the event of sending out the PIM Hello immediately after boot up, since there is only one hop involved here, it would receive the BSM and multicast state from its neighbor fairly soon. Depending on the unicast protocol of choice, it could potentially take 10s of seconds before the rebooted router has the routes to the C-RPs and BSR in place. So, the router would drop the RP-Set and also the (*,G)/(S,G) Join/Prune messages. This is defeating the purpose of having the GenID feature. 

Have I made any wrong assumptions? Or, am I missing something here?

Thanks for any clarification.
Vidya

---

From: Bill Fenner <[email-masked]>
Date: Thu, 12 Apr 2001 17:25:33 -0700

>My understanding has always been that a router only accepts an RP-Set/BSM if
>it has unicast routes to the BSR and all the C-RPs in that RP-Set.

The "Bootstrap Message Processing Checks" section in
draft-ietf-pim-sm-bsr-00.txt says:

if (BSM.dst_ip_address == ALL-PIM-ROUTERS group) {
  if ( BSM.src_ip_address != RPF_neighbor(BSM.BSR_ip_address) ) {
     drop the BS message silently
  }
} else if (BSM.dst_ip_address is one of my addresses) {
  if ( (No previous BSM received)
       OR (DirectlyConnected(BSM.src_ip_address) == FALSE) ) {
     #the packet was unicast, but this wasn't
     #a quick refresh on startup
     drop the BS message silently
  }
} else {
  drop the BS message silently
}

If this is a BSM that is unicasted from one of my directly connected
neighbors, the second block applies (i.e. BSM.dst_ip_address is one of
my addresses).  The contents of that block is actually buggy -- the "No
previous BSM received" should be "any previous BSM has been accepted by
this router" -- the intent is to accept the first BSM unicasted from a
directly connected peer.

The following paragraph explains the intended meaning:

...or the router must have no BSR state (it just restarted) and
have received the BS message by unicast from a directly connected
neighbor.

We've fixed the pseudocode in the draft.

Is there anywhere else in the spec that makes it sound like a startup
BSM won't be accepted?

  Bill

---

From: Narayanan Vidya-CVN065 <[email-masked]>
Date: Fri, 13 Apr 2001 12:23:44 -0500

Bill,
Thanks for the clarification. I did not realize that this has been modified in the draft. 

-Vidya

-----Original Message-----
From: Bill Fenner [mailto:[email-masked]]
Sent: Thursday, April 12, 2001 7:26 PM
To: vidyan
Cc: [email-masked]
Subject: Re: GenID in PIM-SM

  Bill

---

From: Narayanan Vidya-CVN065 <[email-masked]>
Date: Tue, 17 Apr 2001 10:28:04 -0500

Bill,
There are a couple of things that are still not quite clear with this behavior. Please correct me if I'm wrong, but, from your response, it seems like a router should accept the unicasted BSM without performing any RPF checks. In this case, once the router accepts the RP-Set, it is also going to get state ((*,G) or (S,G) Joins/Prunes) from its downstream routers. In this case, it would have to do an RPF check to the RP or the source as needed in order to propogate the J/P message. If unicast routing has not converged, then it would drop that message - is that a valid assumption? Now, it has an RP for a group that it cannot get to - what happens here? 

If there are multiple ways of getting to an RP and if PIM had previously converged through the alternate path, then, when this router comes up, its downstream neighbor would send a join through this router and prune the tree through the alternate path. So, potentially, there can be loss of packets for upto 60 seconds, if the router drops the first join. 

Am I missing something here? 

Thanks,
Vidya

---

From: Bill Fenner <[email-masked]>
Date: Tue, 17 Apr 2001 12:10:21 -0700

>a router should accept the unicasted BSM without performing any RPF
>checks.

Right, so that it has some information immediately upon booting up.

>In this case, once the router accepts the RP-Set, it is also going
>to get state ((*,G) or (S,G) Joins/Prunes) from its downstream routers. In
>this case, it would have to do an RPF check to the RP or the source as
>needed in order to propogate the J/P message. If unicast routing has not
>converged, then it would drop that message - is that a valid assumption?
>Now, it has an RP for a group that it cannot get to - what happens here? 

It has several options.  A naieve implementaiton could just fail to send
the message upstream and wait for the next periodic interval to do anything.
A more advanced implementation might remember that it didn't have a route
for this source or RP and ask the routing process to inform it as soon as
it has a route, and trigger the upstream join as soon as the route appears.

>If there are multiple ways of getting to an RP and if PIM had previously
>converged through the alternate path, then, when this router comes up, its
>downstream neighbor would send a join through this router and prune the tree
>through the alternate path.

If it did this, it would do so based on routing information that the
downstream router has but this router doesn't.  Why would the downstream
router have a route through this router that this router doesn't know
about?

>So, potentially, there can be loss of packets
>for upto 60 seconds, if the router drops the first join. 

Or for up to the unicast routing convergence time, in a "smarter"
PIM implementation.

  Bill

---

From: Narayanan Vidya-CVN065 <[email-masked]>
Date: Tue, 17 Apr 2001 16:10:25 -0500

Thanks for the response. Please see below for comments.
 
> it has a route, and trigger the upstream join as soon as the 

Are these options stated anywhere in the revised PIM draft or the new BSR draft? Or, is it pretty much left to implementation choice? It seems to me that GenID would only partially serve the purpose if such joins were to be dropped. 

> router have a route through this router that this router doesn't know

This could happen if there are different unicast routing protocols running in the network. For example, consider this scenario: 

R1 ----- R2 ----- R3 ----- RP

Lets say that R2 just rebooted. Further assume that the interface between R1 and R2 is running static routing and the rest of the interfaces are running OSPF or some other IGP. As soon as the interface on R1 comes up (this should happen shortly after R2 comes up), it is going to now think that it has a route to the RP through R2. Even if it had an alternate path to the RP, it is going to attempt to join through this path and prune the other one, if this is the preferred one. However, R2 does not quite have a path to the RP yet, since OSPF has not yet converged. 

In a case like this, there could be a hole in the packet flow by using this approach. 

Also, from your comment here, it seems like a downstream router should only send the joins after having a unicast route to the RP/source through the rebooted router. A fundamental question - upon GenID change, does a downstream router also send the state (J/P messages) immediately with the unicast BSM or does it not do that until something in the unicast RPF changes. I would assume that it only happens after the RPF changes due to unicast convergence, since there is no way of knowing about the new preferred path towards the RP/source until then. In that case, there should be no reason for the rebooted router to buffer any J/P messages to wait for unicast routes to the RP/source. 

If states are transferred only after unicast convergence, then, this issue would only happen while running multiple unicast routing protocols. Am I missing something here? 

Thanks,
Vidya

---

From: Bill Fenner <[email-masked]>
Date: Tue, 17 Apr 2001 14:55:56 -0700

>Are these options stated anywhere in the revised PIM draft or the new BSR
>draft? Or, is it pretty much left to implementation choice? It seems to me
>that GenID would only partially serve the purpose if such joins were to be
>dropped. 

Such joins are never dropped (i.e. they will at least create state in the
router to which they were addressed).

>In a case like this, there could be a hole in the packet flow by using this

This hole would be present for unicast too, so is a flaw in your choice
of combination of routing protocols, not a flaw in PIM.

>Also, from your comment here, it seems like a downstream router should only
>send the joins after having a unicast route to the RP/source through the
>rebooted router.

How else is router B the RPF neighbor of router A than for A to have a
route to the RP/source through B?

>A fundamental question - upon GenID change, does a
>downstream router also send the state (J/P messages) immediately with the
>unicast BSM or does it not do that until something in the unicast RPF
>changes.

As shown in the upstream state machines, the J/P messages are
not triggered immediately but delayed in order to prevent implosion.
If the RPF changes in the meantime, that's a different transition
and the Join to the new RPF neighbor and the Prune to the old RPF
neighbor are transmitted immediately.

  Bill

---

From: Narayanan Vidya-CVN065 <[email-masked]>
Date: Tue, 17 Apr 2001 17:17:02 -0500

> router to which they were addressed).

I was referring to the comment in your previous email "A naieve implementaiton could just fail to send
the message upstream and wait for the next periodic interval to do anything" - From this I inferred that the first message would be dropped. If it is to wait for the periodic interval to send it upstream, then, what would be the purpose of creating state? 

In any case, for further discussion, lets assume that the implementation is not so naive.  

> neighbor are transmitted immediately.

To clarify, when I said "immediately", I didn't mean "all at the same time" - maybe I didn't word it correctly, but I meant to ask if they wait for the rebooted router to become the new RPF neighbor before they send out the J/P messages. If they don't, then how do the routers know what state information to send to this rebooted router? If the RPF for all the existing state hasn't changed yet, then, no state has actually changed - correct? 

The two comments above seem to be contradicting each other. The first one indicates that unicast has to converge before J/P messages can be sent, while your second comment indicates that J/P messages are triggered with random time intervals upon a change in GenID. The first one makes logical sense. I'm not sure I follow the second comment. 

Basically, I'm wondering why there would ever be a need to buffer any J/P messages (as you indicated in your first response) and wait for unicast routes to be available, if those messages are only sent after the unicast routes become available. 

Thanks,
Vidya

---

From: Narayanan Vidya-CVN065 <[email-masked]>
Date: Wed, 18 Apr 2001 10:26:40 -0500

> Routing does not have to converge; the downstream routers do 
> "immediately"
> retransmit their joins when the upstream's GenID changes.  A robust
> upstream implementation will create the appropriate state and will
> send the appropriate Joins further upstream as soon as unicast routing
> converges.  This is not in the spec because it feels kind of 
> complicated
> to specify other than in vague terms.
> 

I am a little confused. How does a router know that the rebooted router is infact its "upstream" neighbor towards the source/RP in order to send the J/P messages? In other words, before unicast converges, the downstream router would have no idea if the rebooted router is in the path towards the RP/source/both/neither. So, in such a case, what kind of state does it attempt to send? (*,G)? (S,G)? Both? 

I can see the J/P messages being sent if the rebooted router was only down for a short while and the downstream router had  not timed out the state yet. That too, I would think, is implementation specific. There is really no need to hang on to the PIM state for 210 seconds when an interface goes down. A smart implementation would probably clean it all up when unicast routing indicates that the interface is no longer up. 

So, bottomline - what state is really sent to a rebooted router prior to unicast convergence? 

Thanks,
Vidya

---

From: Bill Fenner <[email-masked]>
Date: Wed, 18 Apr 2001 11:23:03 -0700

>So, bottomline - what state is really sent to a rebooted router prior to

Any state where the RPF points to the rebooted router.  If your RPF
information that pointed to that router has also gone away due to the
reboot, then no state will be sent.

Note that one situation where GenID is very useful even for a naive
implementation is when the PIM component of a router restarts (or is
reconfigured), as opposed to on reboot.  In this case, all the necessary
information is already available to be used immediately.

  Bill

---

From: Narayanan Vidya-CVN065 <[email-masked]>
Date: Wed, 18 Apr 2001 13:36:54 -0500

> information is already available to be used immediately.

Yes, if it is just the PIM component that has reset, then this point is valid. But, in most cases (link or router failure), I would guess that unicast convergence should immediately clean things up and trigger the correct J/P messages. GenID still helps, since without it, the rebooted router would not have the RP-Set. 

I think it would be helpful to have a hint about this operation in the spec - atleast the fact that state information will be sent to the rebooted router if that router is the RPF neighbor towards the RP/source. 

-Vidya