Subject: [rbridge] How to do RPF checks for bidirectional RBridge trees

From: Radia.Perlman at sun.com ([email-masked])
Date: Thu, 08 Mar 2007 08:29:43 -0800

Sanjay,

We are agreeing on the technical details.

As for terminology, I don't care. Is there a better term than "RPF check"?

And as you observed, the reason for having R1 announce the set of trees
it will select is to avoid having (# of trees) * (# of RBridges) RPF state.

The default is "compute a tree based on me" and "I will always choose
tree rooted as me", which would result in (# of trees) state. The only
RPF state at R2, for tree R1,
is to put R1 onto the adjacency from which frames
from R1 should arrive, and the null set on the other adjacencies in
the R1 tree.

The only reasons R1 should choose a tree other than itself are:

a) R1 is configured to decline being a tree root, in order to cut down
on the number of trees RBridges need to compute, in which case R1 will,
in most cases,
be configured to just announce one tree, and always select that one

b) R1 is sourcing some high volume multicast sources, in which case
R1 is likely to be configured to choose perhaps 2, maybe 3, but not
"lots of" different trees.

So with this announcement of which trees R1 will choose when ingressing
packets, it greatly simplifies RPF state.

Radia

----- Original Message -----
From: "Sanjay Sane (sanjays)" <sanjays at cisco.com>
Date: Wednesday, March 7, 2007 11:19 pm
Subject: Re: [rbridge] How to do RPF checks for bidirectional RBridge trees

> 
> What every rbridge wants to do is -- 
> for every rbridge Rx that could use tree R1, 
> On this tree R1, find which is the interface that leads me towards Rx,
> or leads Rx towards me.
> Multicast packets ingressed from Rx, and using tree R1, should be
> allowed to come in only on this interface. 
> 
> The RPF state per interface could potentially be 
> #ofswitches * #oftrees
> 
> By announcing this field, are you just trying to reduce the RPF 
> state ? 
> 
> btw, should we use the term "RPF" to denote what's being checked here?
> What we're really checking is whether the ingress rbridge is really
> forwarding as per a given R1 tree. 
> 
> -Sanjay
> 
> 
> -----Original Message-----
> From: rbridge-bounces at postel.org [rbridge-bounces at postel.org] On
> Behalf Of Radia Perlman
> Sent: Wednesday, March 07, 2007 6:18 PM
> To: rbridge at postel.org
> Subject: [rbridge] How to do RPF checks for bidirectional RBridge 
> trees
> It isn't totally obvious how to do RPF (reverse path forwarding) 
> checksto make multicast forwarding safer, when we're doing 
> bidirectional trees
> (ingress is R1, but R1 chooses tree root R2).
> 
> So after thinking about it, I think this is how it would work, and it
> introduces a new field that would be nice to add to the core instance
> IS-IS LSP. The field is "I promise to only choose the following set of
> RBridges to be tree roots". The only reasons for R1 to choose a
> distribution tree rooted on an RBridge other than itself are:
> 
> a) R1 is configured not to ask to be a tree root (so that RBridges 
> don'thave to calculate as many trees)
> 
> b) R1 wants to multipath multicast originating on its attached links.
> 
> The reason for having R1 preannounce is to simplify creating an RPF
> database associated with each tree.
> 
> If tree R1 is used if and only if R1 is the ingress for the data, then
> the RPF tree for tree R1 would look like this, at some RBridge R in 
> thecore:
> 
> for each "adjacency" (neighbor/port): one of the following: not in 
> tree,in-port, or out-port. The RPF check would discard any incoming 
> data for
> tree R1 except on the in-port.
> 
> However, if R1 chooses R2 as the root of the multicast tree, then the
> RPF database associated with the tree R2, at some core RBridge R looks
> like this:
> 
> Let S be the set of RBridges that have announced, in their LSPs, that
> they might choose R2 as the tree for multicast traffic they are 
> sourcinginto the campus.
> 
> R keeps, for tree R2, and for each adjacency, {set of RBridges that 
> areplausible ingress RBridges for packets received on that adjacency}.
> 
> The set union of all of those will be S.
> 
> I hope that's correct, and that I've explained it clearly....
> 
> Radia
> 
> _______________________________________________
> rbridge mailing list
> rbridge at postel.org
> http://mailman.postel.org/mailman/listinfo/rbridge
> 
> _______________________________________________
> rbridge mailing list
> rbridge at postel.org
> http://mailman.postel.org/mailman/listinfo/rbridge
>

---

From: dino at cisco.com (Dino Farinacci)
Date: Thu, 8 Mar 2007 09:31:54 -0800

> As for terminology, I don't care. Is there a better term than "RPF  

It it not an RPF check, because as you and Sanjay described it, the  
best-path from an rBridge to a receiver is on the forward path.

So an appropriate and less misleading term is "the expected incoming  
interface check".

> it will select is to avoid having (# of trees) * (# of RBridges)  

The dominate state in the forwarding plane is number of group  
entries, regardless of he number of roots. The forwarding plane  
forwards on (*,G) entries, so that is the state volume we want to  
keep an eye on.

> from R1 should arrive, and the null set on the other adjacencies in

This doesn't make sense to me. You want to choose one root for a  
particular (*,G) entry and all rBridges use the same root for this  
entry.

Dino

---

From: Radia.Perlman at sun.com (Radia Perlman)
Date: Thu, 08 Mar 2007 09:57:31 -0800

We're not talking about G's here, as in specific multicast destination 
addresses. We're talking
about
a) Distinct distribution trees: computed by using the link state 
database to compute a shortest path
tree from the named Root
b) ingress RBridges, for filtering based on "expected incoming interface 
(adjacency) check"

(Note: when you say "interface" do you mean what I refer to as 
"adjacency" (which is a (port, neighbor) pair),
or do you mean "port"? -- I'll assume you mean "adjacency", and 
therefore I'll use "interface" because I
never really liked the word "adjacency" --- too many syllables, and it's 
a word I never tend to use in
ordinary conversation.

Anyway...where G's come in (as well as VLANs), is further filtering 
information on each interface in the
named tree.

So the rules are, if  R3 receives a multicast packet on interface i, 
with named tree=R2, and ingress RBridge=R1,
then:

if R1 is not on the expected source list for interface i, then the 
packet is dropped

passing that check, for each interface other than i, in tree R2, 
filtering is done based on whether the VLAN
specified in the inner frame can be reached downstream on that 
interface, and for IP multicast group G, whether
either IP multicast routers, or receivers for G are reachable downstream 
on that interface.

Radia

---

From: dino at cisco.com (Dino Farinacci)
Date: Thu, 8 Mar 2007 10:20:36 -0800

> We're not talking about G's here, as in specific multicast  
> destination addresses. We're talking
> about
> b) ingress RBridges, for filtering based on "expected incoming  
> interface (adjacency) check"

Yes, I understand that. But the state storage cost here is more in  
control-plane memory which is less of a concern than forwarding-plane  
memory. That is why I spoke up.

> "adjacency" (which is a (port, neighbor) pair),

I meant port, but if you want to do a last-hop neighbor incoming  
check then you have to do a 6-byte compare and are required to have  
the last-hop MAC address in the frame. I know the frame formats have  
been changing, so not sure that the last-hop MAC address is still in  
the frame (I'm behind on TRILL reading).

> never really liked the word "adjacency" --- too many syllables, and  
> it's a word I never tend to use in
> ordinary conversation.

Right, adjacency tends to be more unicast centric and means  
downstream. We are talking about upstream interfaces here (closer to  
the source and not closer towards the destination).

> information on each interface in the

Right.

> So the rules are, if  R3 receives a multicast packet on interface  
> i, with named tree=R2, and ingress RBridge=R1,
> then:
>

Right, said another way if R1 is not the last-hop device on the  
shortest path from R1 to R3, the packet is dropped.

> filtering is done based on whether the VLAN

Yes. But I mentioned this before. The oif-list for the G is populated  
based on the receivers downstream. So you actually filter by default  
and only the ports in the oif-list get packets sent out on.

I know why you say filtered, because you are describing a broadcast  
tree which contains all links in the topology and the membership tree  
is typically a subset of those links.

Doesn't matter, just terms. I think we agree on the concept.

> either IP multicast routers, or receivers for G are reachable  
> downstream on that interface.

Right.

But just to reiterate my point, when a packet comes into an rBridge,  
in fast switching mode, an entry like this exists to be forwarded on  
if the DA is G:

     (*,G), incoming-interface: port i, oif-list: port j, k, l

So as you say if the packet came in on port i, the packet gets  
replicated out
ports j,k,l. If the packet comes in on any other port, it is dropped.

What I describe above could be implemented in a fast hardware  
implementation.

Dino

---

From: Radia.Perlman at sun.com (Radia Perlman)
Date: Thu, 08 Mar 2007 10:53:55 -0800

Yup. The bottom line, for those only skimming, is that you and I are not 
disagreeing
about anything.

And the action item from this thread is that the extra announcement 
"these are the trees I will specify" should go
into IS-IS, in the core instance LSP.

Also, in the protocol spec, it we should update the forwarding/filtering 
rules to include
"allowed ingress RBridges on this adjacency/port", and make sure the 
filtering rules really
do specify what you and I said, in different words.

There is an open question, however, which is whether the "expected 
incoming interface" check should be
SHOULD, MAY or MUST for checking not just port, but neighbor. The 
downside is the extra 6-byte
check, as you point out. The upside is less likely to have bizarre 
temporary loops. I'd vote for
MUST actually.

Radia

---

From: dino at cisco.com (Dino Farinacci)
Date: Thu, 8 Mar 2007 11:49:04 -0800

> temporary loops. I'd vote for

I definitely agree with MUST.

Dino

---

From: sgai at nuovasystems.com (Silvano Gai)
Date: Thu, 8 Mar 2007 14:01:00 -0800

I am glad you agree ;-)

Will you also agree with me that this technique is useful for network in
a steady state, but does not prevent temporary loops when there is a
topology change?

-- Silvano 

> From: rbridge-bounces at postel.org [mailto:rbridge-bounces at postel.org]
On
> Behalf Of Dino Farinacci
> Sent: Thursday, March 08, 2007 11:49 AM
> To: Radia.Perlman at sun.com
> Cc: rbridge at postel.org

---

From: dino at cisco.com (Dino Farinacci)
Date: Thu, 8 Mar 2007 14:34:05 -0800

> a steady state, but does not prevent temporary loops when there is a

I agree there will be transient multicast packet looping when there  
are topology changes.

Dino

---

From: erik.nordmark at sun.com (Erik Nordmark)
Date: Fri, 09 Mar 2007 14:37:58 -0800

> I agree there will be transient multicast packet looping when there  

Dino,

I'm trying to draw an example topology where a change causes a transient 
multicast loop (with an "expected incoming adjacency" check) and I can't 
  find one. Unicast is sooo much easier ;-)

Have you observed temporary IP Multicast loops? (apart from the PIM SM 
ones before ASSERTS where added). What was the topology and change 
necessary to trigger those?

    Erik

---

From: dino at cisco.com (Dino Farinacci)
Date: Fri, 9 Mar 2007 15:36:03 -0800

> I'm trying to draw an example topology where a change causes a  
> transient multicast loop (with an "expected incoming adjacency"  
> check) and I can't  find one. Unicast is sooo much easier ;-)

The simplest example is when using multi-access links. The fact that  
some switches use the multi-access link as an oif and others use the  
link as an expected-incoming interface.

So if the ones that are using the multi-access link as an oif happen  
to join the root through one of the other switches (which can be many  
hops away), then the multicast forwarding (and replication) loop occurs.

This only happens when the link state database is not in sync among  
the switches involved because each one thinks the root is located on  
a different path while still consider the same location of the  
receivers.

> Have you observed temporary IP Multicast loops? (apart from the PIM  
> SM ones before ASSERTS where added). What was the topology and  
> change necessary to trigger those?

Oh definitely, when two routers think the RP for a (*,G) are  
different. And this can happen when the topology is in steady state.

And this happens due to misconfiguration or in the early days of PIM  
when you detect one RP down, you move to another one, but others in  
the topology stayed with the original one. Again, in a steady-state  
topology. The reason some thought the RP went down is because the  
network was congested and the RP keepalives were all lost. Those were  
interesting times.  ;-)

So this can happen in IS-IS as well if the not everyone is using the  
same roots.

Dino

---

From: erik.nordmark at sun.com (Erik Nordmark)
Date: Fri, 09 Mar 2007 15:58:42 -0800

Dino Farinacci wrote:

> So if the ones that are using the multi-access link as an oif happen to 
> join the root through one of the other switches (which can be many hops 
> away), then the multicast forwarding (and replication) loop occurs.

With TRILL be clearly have to be careful at the edge (the ingress and 
egress rbridges) when it comes to the relationship between 802.1D and 
designated RBridge in order to handle topology changes. In particular 
since the frames without the TRILL header header doesn't have a TTL.

But leaving that aside for a moment, the way Radia described the 
forwarding check (the "expected incoming adjacency" check), the transit 
paths between the RBridges would act as point-to-point due to checking 
both the incoming port and the previous hop RBridge.

It was in such a pt-pt topology that I tried to find a simple example of 
a temporary loop.

> Oh definitely, when two routers think the RP for a (*,G) are different. 
> And this can happen when the topology is in steady state.
> 
> when you detect one RP down, you move to another one, but others in the 
> topology stayed with the original one. Again, in a steady-state 

But AFAICT that type of loop can't happen in TRILL since we have an 
explicit designator for the tree to use in every multi-destination data 
frame.

    Erik

---

From: sgai at nuovasystems.com (Silvano Gai)
Date: Fri, 16 Mar 2007 02:16:15 -0700

EriK,

inline

> From: Erik Nordmark [mailto:erik.nordmark at sun.com]
> Sent: Friday, March 09, 2007 3:59 PM
> To: Dino Farinacci
> Cc: Silvano Gai; rbridge at postel.org; Radia.Perlman at sun.com
to
> both the incoming port and the previous hop RBridge.

IMHO you can build the most sophisticated RPF check, but it will always
be based on local information. Since it is well known that the local
information of two RBridges may be temporary out of sync, due to the way
IS-IS works, the possibility of a temporary loop is concrete.

Temporary loop == Broadcast Storm

-- Silvano

> >> Have you observed temporary IP Multicast loops? (apart from the PIM
SM
> > Oh definitely, when two routers think the RP for a (*,G) are
different.
> > when you detect one RP down, you move to another one, but others in
the