Subject: [rbridge] Setting initial "hop count" value

From: Radia.Perlman at sun.com ([email-masked])
Date: Thu, 03 May 2007 18:57:22 -0700

Sorry Eric. There ought to be a better name for it than "the RPF thing".
What's being talked about is what I presented at the WG, which is
the precomputation, for each tree, for each port, the set of ingress RBridges
from which it would be logical to receive packets from, on that port.

To summarize "the RPF thing" (and I'd love a better name for it, but maybe we
don't need to name it-- we can just put the algorithm in the spec)

a) Each RBridge R1 announces, in the core instance of IS-IS, the set of
trees R1 will ever choose as distribution trees for packets that R1 injects. So
say that R1 chooses {R1, R4, and R5}

b) Each RBridge also announces whether it wants to be the root
of a tree

c) Each RBridge R2 calculates a tree for each of the RBridges that have say "yes"
for b).

d) An RBridge, say R3, calculates the tree rooted at, say, R5. Let's say that
R3 determines that ports a, b, c, and f are in the R5-tree.
Then let's say that of all the RBridges, {R6 and R7} say (in a) that they
are going to choose the R5-tree. R3 figures out which port it should
receive things from R6, on the R5-tree, and marks that port as
"ingress RBridge R6 allowed". Likewise it does that for the port
for which it should receive things from R7 on that tree.

e) R3 does filtering as follows: If R3 receives a multicast packet marked
as R5-tree (egress RBridge field =R5), with ingress RBridge Rx, on port p,
then if the ingress RBridge is not listed among the allowed
ingress RBridges for that port for that tree, R3 discards the packet.

Note the overhead for this is that if the average number of trees each ingress
RBridge says they will select is 2 (I'd think most RBridges would select only one
tree -- it would be only for RBridges that want to multipath multicast that they'd
select more than one tree), then there are only 2*number of RBridges TOTAL
that will get listed as legal ingress RBridges.

Radia

----- Original Message -----
From: "Eric Gray (LO/EUS)" <eric.gray at ericsson.com>

> 
> 	First, what exactly is the "Radia RPF" proposal that you
> mention in another thread of discussion,

---

From: petera at nortel.com (Peter Ashwood-Smith)
Date: Thu, 3 May 2007 23:33:33 -0400

I suggest "the RPF thing" be called RPFC "Reverse Path Forwarding
Check".

Peter

> -----Original Message-----
> From: rbridge-bounces at postel.org 
> [mailto:rbridge-bounces at postel.org] On Behalf Of Radia.Perlman at sun.com
> Sent: Thursday, May 03, 2007 9:57 PM
> To: Eric Gray (LO/EUS)
> Cc: rbridge at postel.org; Joe Touch
> Subject: Re: [rbridge] Setting initial "hop count" value
> 
> What's being talked about is what I presented at the WG, 
> which is the precomputation, for each tree, for each port, 
> the set of ingress RBridges from which it would be logical to 
> receive packets from, on that port.
> 
> To summarize "the RPF thing" (and I'd love a better name for 
> it, but maybe we don't need to name it-- we can just put the 
> algorithm in the spec)
> 
> a) Each RBridge R1 announces, in the core instance of IS-IS, 
> the set of trees R1 will ever choose as distribution trees 
> for packets that R1 injects. So say that R1 chooses {R1, R4, and R5}
> 
> b) Each RBridge also announces whether it wants to be the 
> root of a tree
> 
> Then let's say that of all the RBridges, {R6 and R7} say (in 
> a) that they are going to choose the R5-tree. R3 figures out 
> which port it should receive things from R6, on the R5-tree, 
> and marks that port as "ingress RBridge R6 allowed". Likewise 
> it does that for the port for which it should receive things 
> from R7 on that tree.
> 
> e) R3 does filtering as follows: If R3 receives a multicast 
> packet marked as R5-tree (egress RBridge field =R5), with 
> ingress RBridge Rx, on port p, then if the ingress RBridge is 
> not listed among the allowed ingress RBridges for that port 
> for that tree, R3 discards the packet.
> 
> Note the overhead for this is that if the average number of 
> trees each ingress RBridge says they will select is 2 (I'd 
> think most RBridges would select only one tree -- it would be 
> only for RBridges that want to multipath multicast that 
> they'd select more than one tree), then there are only 
> 2*number of RBridges TOTAL that will get listed as legal 
> ingress RBridges.
> 
> Radia
> 
> > 	First, what exactly is the "Radia RPF" proposal that 
> you mention in 
> > another thread of discussion,
> 
> _______________________________________________
> rbridge mailing list
> rbridge at postel.org
> http://mailman.postel.org/mailman/listinfo/rbridge
>

---

From: sachja at gmail.com (sachin jain)
Date: Sun, 6 May 2007 07:13:54 -0700

Hi,
  I think the RPF check can have transient loops for packets in flight
during topology change. It does seem to have no loop for new packets.
Let me explain that with an example with only one distribution tree.

The topologys is as follows
  ------------------------------------
  |                                  |
R1 -------                         |
  |          |                        |
  |          R2      ------------  R3
  |            |                        |
  |            |                        |
  | ------   R4   ------------------

[Description : R1 is connected to every switch and R2, R3, R4 are connected
in a loop]

There is only one distribition tree agreed upon which is rooted at R1.

Suppose during a transient change the ISIS link state database at different
switches is such that the tree that each switch computes is as follows

R2: Tree is R1->R4->R2->R3
R3: Tree is R1->R2->R3->R4
R4: Tree is R1->R3->R4->R2

Suppose there is a packet which was originated from R1 and is in flight
between R2 and R3 just when the topology change happened. Now this packet
will loop between R2, R3, R4 because for each of them it is receiving on the
link which passes the RPF check for source R1.

Are above scenarios unlikely or acceptable?

sachin

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.postel.org/pipermail/rbridge/attachments/20070506/65edec71/attachment.html

---

From: pfr at info.ucl.ac.be (Pierre Francois)
Date: Mon, 07 May 2007 14:50:33 +0200

Sachin,

With the rpf check, you will have transient loops and duplications,
but no deadly storms where duplicated packets re-enter the loop and 
"feed" the loop,
This is similar to what you have with pim-ssm's rpf check.

Pierre.

sachin jain wrote:
> [Description : R1 is connected to every switch and R2, R3, R4 are 
> connected in a loop]
>
> Suppose during a transient change the ISIS link state database at 
> different switches is such that the tree that each switch computes is 
> as follows
>
> Suppose there is a packet which was originated from R1 and is in 
> flight between R2 and R3 just when the topology change happened. Now 
> this packet will loop between R2, R3, R4 because for each of them it 
> is receiving on the link which passes the RPF check for source R1.
>
> On 5/3/07, *Radia.Perlman at sun.com <mailto:Radia.Perlman at sun.com>* < 
> Radia.Perlman at sun.com <mailto:Radia.Perlman at sun.com>> wrote:
>
>     From: "Eric Gray (LO/EUS)" <eric.gray at ericsson.com
>     <mailto:eric.gray at ericsson.com>>
>
>     >
>     rbridge at postel.org <mailto:rbridge at postel.org>
> ------------------------------------------------------------------------
>