Subject: [rbridge] a stronger RPF check for TRILL

From: Santosh Rajagopalan <[email-masked]>
Date: Thu, 8 Mar 2012 09:43:00 -0800

It appears the the multidestination frame checks present in TRILL may not
be strong enough to cover some cases of packet duplicates during network
transition scenarios. In this email, I'm going to suggest a modification of
the TRILL RPF check to cover these cases.

The root problem is that there's a notion of directionality built into the
RPF concept ("accept packets from X along this vector"). In a p2p link,
specifying the port alone uniquely qualifies that vector. However, in a
multiaccess link, there are many "links/adjacencies" overlaid on the
physical link. To identify one of them, you need to specify both the
outer_smac *and* the port. So the RPF check should actually be "accept
packets from X along (outer_smac, port)".

Consider this network:

F--A--B--C--o--D
All the links except the link between C and D are p2p links. C and D are
connected over a classical ethernet network (represented by the pseudonode
"o"). Let's say D gets picked as the root for a multidestination tree (the
choice of root is unimportant here).
The resulting tree looks like:

F--A--B--C--o--D

Now lets say that a link comes up from A to the same classical ethernet
network. So the network looks like this:
     ________
     |                 |
F--A--B--C--o--D

Let's say the resulting tree in steady state includes all links except the
B-C link. After the network has converged, a packet that starts out from F
will go F->A, where A will send one copy to the A-B link and another copy
into the CE network, from where it will be received by C and D.

However, lets consider a transition stage where A and D have acted on their
LSPs and programmed their forwarding plane, while B and C have not yet done
so.
This means that B and C both consider the link between them to still be
part of the tree.

So a packet that starts out from F and reaches A will be copied by A into
the A-B link and the A-o link. D's RPF check says to accept packets on this
tree coming from F over its link to the CE network, so it gets accepted. D
is also adjacent to A on the tree, so the tree adjacency check also passes.

However, the packet that gets to B gets sent out by B to C. C's RPF check
still has the old state, and it thinks the packet is ok. C sends the packet
along the old tree, which is towards the CE network. D receives one more
packet, but the tree adjacency check passes because C is adjacent to D in
the new tree as well. The RPF check also passes because D's link to the CE
network is ok for receiving packets from A.

So now D gets duplicates of every packet until B and C act on their LSPs
and program their hardware tables. The AF state is (I believe) irrelevant
here because we're talking about TRILL encapsulated packets, not native CE
frames.

In the example above, the adjacency check alone doesn't help, because the
rbridge D has adjacencies to both A & C on the tree. A check on (port,
smac) will pass for packets from both A and C.

The only check which can stop this from happening, I believe, is if you
replace the current RPF check which looks like this:
{tree_id, source_rbridge}->{allowed_port}

with a modified check which looks like this:

{tree_id, rbridge}->{allowed_port, allowed_outer_smac}

This will make sure that packets will be accepted by D only if they were
sent by A. This combined check can be a replacement for the currently
separate adjacency and RPF checks.

Thoughts?
--
Sunny Rajagopalan

_______________________________________________
rbridge mailing list
[email-masked]
http://mailman.postel.org/mailman/listinfo/rbridge

---

From: Anoop Ghanwani <[email-masked]>
Date: Fri, 9 Mar 2012 04:51:55 -0800

The tree adjacency check already accounts for this.
http://tools.ietf.org/html/rfc6325#section-4.6.2.5

   The Outer.MacSA is checked and the frame discarded if it is not a
   tree adjacency for the tree indicated by the egress RBridge nickname
   on the port where the frame was received.

This is done in addition to the port-based RPF check.

Anoop

On Thu, Mar 8, 2012 at 9:43 AM, Santosh Rajagopalan
<[email-masked]> wrote:
> It appears the the multidestination frame checks present in TRILL may not be
> strong enough to cover some cases of packet duplicates during network
> This means that B and C both consider the link between them to still be part
> of the tree.
>
> So now D gets duplicates of every packet until B and C act on their LSPs and
> program their hardware tables. The AF state is (I believe) irrelevant here
> because we're talking about TRILL encapsulated packets, not native CE
> frames.
>
> rbridge D has adjacencies to both A & C on the tree. A check on (port, smac)
> will pass for packets from both A and C.
>

---

From: Donald Eastlake <[email-masked]>
Date: Fri, 9 Mar 2012 09:44:26 -0500

Hi Anoop,

> This is done in addition to the port-based RPF check.

Ahhh, but this is not quite a strong as what Santosh is suggesting.
The subtle weakness is that "adjacency" has no directionality.

RFC 6325 currently specifies this part of the RPFC as two separate checks:
 1. Is ( tree, Outer.MacSA, arrival port) an allowed triplet according
to the current topology and tree?
 2. Is ( tree, ingress, arrival port ) an allowed triplet according to
the current topology and tree?

What Santosh is suggesting, which would be just a little stronger and
arguably simpler, is equivalent to replacing this with one test:
 -- Is ( tree, Outer.MacSA, ingress, arrival port ) an allowed quadruplet?

This is stronger because, on a multi-access link, one Outer.MacSA may
only be allowed on frames from the ingress and other Outer.MacSA may
only only be allowed on frames ingressed elsewhere.

I think some existing silicon may already use this combined RPFC test...

Thanks,
Donald
=============================
 Donald E. Eastlake 3rd   +1-508-333-2270 (cell)
 155 Beaver Street, Milford, MA 01757 USA
 [email-masked]

---

From: Radia Perlman <[email-masked]>
Date: Fri, 9 Mar 2012 07:57:29 -0800

Ah.  Yes, thank you for that explanation, Donald.  Santosh is indeed
correct, and it also makes the spec easier to read, which is an
additional plus.

Radia

---

From: Jon Hudson <[email-masked]>
Date: Fri, 9 Mar 2012 13:55:11 -0800

I agree! Both stronger & easier to read/understand. 

Very nice Santosh!

---

From: letracy <[email-masked]>
Date: Wed, 14 Mar 2012 21:19:38 -0700

I think one drawback to the stronger RPF check is that Rbridges will be
required to maintain more state.  In the best cases, Rbridges will be
required to maintain a 6 byte source MAC address per RPF.  In some other
cases, the stronger check will require additional RPF checks as well.

Consider a case such as:

             A - B - C
             |
 U - V - W = o - X - Y - Z

Where o is a LAN link and W has two parallel links into the LAN o with
unique MAC addresses on each link.
 
In this case, W is allowed to loadsplit among the two links and Rbridges
A and X are required by RFC6325 to accept traffic coming from either of
W's ports.  This will mean bridges X and A are required to maintain two
RPF entries each for Rbridges U, V and W (One RPF check accepting (W, SMAC1)
and one accepting (W, SMAC2), etc...).  Thus, the number of RPF checks
required in the network becomes proportional to the number of Rbridge ports
connected to LAN links as well as to the number of Rbridges in the network.
In larger networks this could explode in terms of scale and complexity.

Considering that the problem case is transient, rare, and only results in
duplicate packets (as opposed to loops) - I'd like to suggest that the
stronger check be made optional.
 
Thanks,
Leonard Tracy

On 3/9/12 1:55 PM, "Jon Hudson" <[email-masked]> wrote:

>>>>> be
>>>>> part
>>>>> and

---

From: Santosh Rajagopalan <[email-masked]>
Date: Thu, 15 Mar 2012 14:28:42 -0700

I think that a similar argument can be made for the current RPF check as 
well - it costs us table space and helps us in rare, transient cases. If 
you decide that the RPF check is worthwhile having in its current form, I 
think you can make the case that it's worthwhile having in the expanded 
form as well. 

Because really, the new form of the RPF check says the same thing as the 
current form - it's just that in multi-access links you need to qualify 
the "allowed link" a little more strongly. Also, I'm not sure if its 
absence could lead to loops - duplicates were just the first case I 
thought of. 

Note that in the case you illustrated below (where rbridges have multiple 
links to the CE network) you would need to have multiple RPF entries 
anyway, even without the new expanded check. For example, the rbridge W 
would need "allow (A, link_1)" in addition to "allow (A, link_2)". Of 
course, there's no denying that adding the mac address there will bring in 
additional memory costs.

--
Sunny Rajagopalan

From:   letracy <[email-masked]>
To:     Jon Hudson <[email-masked]>, Radia Perlman 
<[email-masked]>, Santosh Rajagopalan/Santa Clara/IBM@IBMUS
Cc:     Donald Eastlake <[email-masked]>, "[email-masked]" 
<[email-masked]>, Anoop Ghanwani <[email-masked]>
Date:   03/14/2012 09:37 PM
Subject:        Re: [rbridge] a stronger RPF check for TRILL
Sent by:        [email-masked]

Consider a case such as:

             A - B - C
             |

In this case, W is allowed to loadsplit among the two links and Rbridges
A and X are required by RFC6325 to accept traffic coming from either of
W's ports.  This will mean bridges X and A are required to maintain two
RPF entries each for Rbridges U, V and W (One RPF check accepting (W, 
SMAC1)
and one accepting (W, SMAC2), etc...).  Thus, the number of RPF checks
required in the network becomes proportional to the number of Rbridge 
ports
connected to LAN links as well as to the number of Rbridges in the 
network.
In larger networks this could explode in terms of scale and complexity.

Thanks,
Leonard Tracy

On 3/9/12 1:55 PM, "Jon Hudson" <[email-masked]> wrote:

>>>>> transition scenarios. In this email, I'm going to suggest a 
modification
>>>>> of
>>>>> However, lets consider a transition stage where A and D have acted 
on
>>>>> their
>>>>> LSPs and programmed their forwarding plane, while B and C have not 
yet
>>>>> done
>>>>> the A-B link and the A-o link. D's RPF check says to accept packets 
on
>>>>> this

---

From: Sam Aldrin <[email-masked]>
Date: Thu, 15 Mar 2012 14:54:04 -0700

Having read both sides of the story, two points I hear are
1. There is a scenario or corner case, where existing rpf check doesn't satisfy the needs.
2. Because the new proposal requires SMAC to be maintained, the size of tables exponentially increases.

IMO, weight given to 1and 2 could vary depending on vendor and whom you talk to. If stronger rpf check is needed, a solution without increasing the complexity in table size etc should be proposed. If that is something not going to be achieved, it should be left optional, till something is identified.

My 2 cents
Sam

Sent from my iPhone

On Mar 15, 2012, at 2:28 PM, Santosh Rajagopalan <[email-masked]> wrote:

> I think that a similar argument can be made for the current RPF check as well - it costs us table space and helps us in rare, transient cases. If you decide that the RPF check is worthwhile having in its current form, I think you can make the case that it's worthwhile having in the expanded form as well. 
> 
> Because really, the new form of the RPF check says the same thing as the current form - it's just that in multi-access links you need to qualify the "allowed link" a little more strongly. Also, I'm not sure if its absence could lead to loops - duplicates were just the first case I thought of. 
> 
> Note that in the case you illustrated below (where rbridges have multiple links to the CE network) you would need to have multiple RPF entries anyway, even without the new expanded check. For example, the rbridge W would need "allow (A, link_1)" in addition to "allow (A, link_2)". Of course, there's no denying that adding the mac address there will bring in additional memory costs. 
> 
> -- 
> Sunny Rajagopalan 
> 
> 
> 
> 
> To:        Jon Hudson <[email-masked]>, Radia Perlman <[email-masked]>, Santosh Rajagopalan/Santa Clara/IBM@IBMUS 
> Cc:        Donald Eastlake <[email-masked]>, "[email-masked]" <[email-masked]>, Anoop Ghanwani <[email-masked]>

---

From: letracy <[email-masked]>
Date: Thu, 15 Mar 2012 16:19:52 -0700

Hi Sunny,

I wanted to try and clarify my point a little better:

>From W¹s perspective nothing has changed except the addition of the SMAC.
RFC6325 does not mandate that it accept traffic from both links, so it can
have a single RPF check if it wishes.

In the example below, A and X do not know which port on the LAN link W will
send a particular frame on.  The RFC explicitly states that W is free to
loadsplit flows among its ports on the link and requires that A and X be
able to accept traffic from either of W¹s links (See RFC6325 Section 4.4.4).
This means that A and X (all Rbridges which share the LAN link with W) will
be required to have 1 RPF check per port W has on the link for W and for
each Rbridge behind W in the tree.

In the below example that means A must have the following RPF checks for its
interface connected to the LAN link:
(U,interface, SMAC_W1)
(U,interface, SMAC_W2)
(V,interface, SMAC_W1)
(V,interface, SMAC_W2)
(W,interface, SMAC_W1)
(W,interface, SMAC_W2)
(X,interface, SMAC_X)
(Y,interface, SMAC_X)
(Z,interface, SMAC_X)

Thanks,
Leonard

On 3/15/12 2:54 PM, "Sam Aldrin" <[email-masked]> wrote:

> IMO, weight given to 1and 2 could vary depending on vendor and whom you talk
> to. If stronger rpf check is needed, a solution without increasing the
> complexity in table size etc should be proposed. If that is something not
> going to be achieved, it should be left optional, till something is
> identified.
> 
> My 2 cents
> Sam
> 
> Sent from my iPhone
> 
>> I think that a similar argument can be made for the current RPF check as well
>> - it costs us table space and helps us in rare, transient cases. If you
>> decide that the RPF check is worthwhile having in its current form, I think
>> you can make the case that it's worthwhile having in the expanded form as
>> well. 
>> 
>> current form - it's just that in multi-access links you need to qualify the
>> "allowed link" a little more strongly. Also, I'm not sure if its absence
>> could lead to loops - duplicates were just the first case I thought of.
>> 
>> links to the CE network) you would need to have multiple RPF entries anyway,
>> even without the new expanded check. For example, the rbridge W would need
>> "allow (A, link_1)" in addition to "allow (A, link_2)". Of course, there's no
>> denying that adding the mac address there will bring in additional memory
>> costs.

---

From: Donald Eastlake <[email-masked]>
Date: Fri, 16 Mar 2012 15:03:35 -0400

Hi,

I agree that use of the stronger, simpler RPFC should be optional.
Among other things, we certainly don't want to declare faithful
implementations of RFC 6325 non-conformant. Also, I think there are,
for reasonable implementation strategies, cases where there would be
more state information with the current standard RPFC requirement and
other cases where there would be more state information with the
simpler, stronger RPFC requirement. (The most important factor for
distinguishing between these cases is, as implied by the message
below, how many ports each RBridge has on the multi-access link.)

Thanks,
Donald

On Thu, Mar 15, 2012 at 7:19 PM, letracy <[email-masked]> wrote:
> From W’s perspective nothing has changed except the addition of the SMAC.
> able to accept traffic from either of W’s links (See RFC6325 Section 4.4.4).
> well - it costs us table space and helps us in rare, transient cases. If you
> "allow (A, link_1)" in addition to "allow (A, link_2)". Of course, there's
> no denying that adding the mac address there will bring in additional memory
> costs.

---

From: Santosh Rajagopalan <[email-masked]>
Date: Fri, 16 Mar 2012 13:12:06 -0700

I agree; this sounds reasonable.

From:   Donald Eastlake <[email-masked]>
To:     "[email-masked]" <[email-masked]>
Date:   03/16/2012 12:27 PM
Subject:        Re: [rbridge] a stronger RPF check for TRILL
Sent by:        [email-masked]

Hi,

Thanks,
Donald

> well - it costs us table space and helps us in rare, transient cases. If 
you
> current form - it's just that in multi-access links you need to qualify 
the
> links to the CE network) you would need to have multiple RPF entries 
anyway,