Subject: [rbridge] Traffic storms

From: Eric.Gray at marconi.com (Gray, Eric)
Date: Mon, 6 Nov 2006 17:45:04 -0500

Pierre,

	The "?loop problem" is apparently an issue with some devices where
reasonable forwarding behavior limitations have been "optimized out."  A
better way to handle the ?loop problem with RBridges is not to optimize
out the behavior that prevents it - i.e. - a prohibition against emitting
a frame on the same interface on which it was received.

	To be clear, at either the last IETF meeting, or the one just before
that one, it was made fairly clear that the ?loop problem occurs when a
device sends a PDU out of the same interface on which it was received. In 
comparison with simply dropping such a PDU, this behavior is pathological
- particularly in the case of L2 forwarding generally.

	I am not saying that we do not need ordered FIB for loop prevention
generally, but we should not need it for the ?loop problem.

--
Eric

--> -----Original Message-----
--> From: rbridge-bounces at postel.org 
--> [mailto:rbridge-bounces at postel.org] On Behalf Of Pierre Francois
--> Sent: Monday, November 06, 2006 5:20 PM
--> To: Sanjay Sane (sanjays)
--> Cc: rbridge at postel.org; Gideon Kaempfer; Radia Perlman
--> Subject: Re: [rbridge] Traffic storms
--> 
--> 
--> Sanjay,
--> 
--> Sanjay Sane (sanjays) wrote:
--> > Pierre,
--> >
--> > After reading through this paper, it seems the oFIB 
--> mechanism is suited
--> > towards unicast traffic, or a single-destination traffic. 
--> >
--> > In TRILL, if the plan is to protect the traffic storms, we *must*
--> > protect the transient loops in the "trees" that are built to carry
--> > unknowns/floods, multicast as well as unicast. Such 
--> traffic is targetted
--> > towards multiple destination, in fact, a tree extends to all the
--> > rbridges. 
--> >
--> > After thinking a bit, if we think of extending the 
--> mechanisms in the
--> > paper to cover "trees", we may have to delay the FIB 
--> ordering on all the
--> > links that are part of the tree on any given rbridge. 
--> This could be very
--> > inefficient. Do you think the oFIB mechanism would be 
--> suitable for such
--> > trees?
--> >   
--> 
--> Applying an "oFIB-like" solution for multicast traffic is 
--> something we 
--> are working on.
--> So, you can make ofib suitable for multicast trees, but we 
--> intend to 
--> modify it for efficiency purposes.
--> btw, you already face the ?loop problem for unicast 
--> traffic, and there 
--> oFIB can be applied as-is by rbridges..
--> 
--> Pierre.
--> > -Sanjay 
--> >
--> >  
--> >
--> > -----Original Message-----
--> > From: rbridge-bounces at postel.org 
--> [mailto:rbridge-bounces at postel.org] On
--> > Behalf Of Pierre Francois
--> > Sent: Friday, November 03, 2006 5:10 PM
--> > To: Silvano Gai
--> > Cc: rbridge at postel.org; Gideon Kaempfer; Radia Perlman
--> > Subject: Re: [rbridge] Traffic storms
--> >
--> >
--> > Silvano,
--> >
--> > See
--> > 
--> http://www.ietf.org/internet-drafts/draft-francois-ordered-f
--> ib-02.txt,
--> > for a loop avoidance mechanism for IS-IS/OSPF.
--> >
--> > See you in SD,
--> >
--> > Pierre.
--> >
--> >
--> >
--> > On Fri, 3 Nov 2006, Silvano Gai wrote:
--> >
--> >   
--> >> Eric,
--> >>
--> >> Also I suggest that people that have solved the problem 
--> of having a 
--> >> loop free topology using ISIS, submit proposasl so that 
--> we can compare
--> >>     
--> > them.
--> >   
--> >> Unfortunately I don't have one.
--> >>
--> >>
--> >>
--> >> -- Silvano
--> >>
--> >>
--> >>
--> >> ________________________________
--> >>
--> >> From: rbridge-bounces at postel.org 
--> [mailto:rbridge-bounces at postel.org] 
--> >> On Behalf Of Gray, Eric
--> >> Sent: Friday, November 03, 2006 11:54 AM
--> >> To: Gideon Kaempfer; Radia Perlman
--> >> Cc: rbridge at postel.org
--> >> Subject: Re: [rbridge] Traffic storms
--> >>
--> >>
--> >>
--> >> Gideon,
--> >>
--> >>
--> >>
--> >>     "Drop BPDUs" is not (exactly) the same as ignore 
--> them.  We use the
--> >>     
--> >
--> >   
--> >> term
--> >>
--> >> as short-hand for the one of three options we considered 
--> for handling
--> >> BPDUs:
--> >>
--> >>
--> >>
--> >>     Drop (do not participate actively in STP, and do not 
--> pass BPDUs 
--> >> through),
--> >>
--> >>     Transparent (pass BPDUs through - potentially 
--> altering them in 
--> >> some way),
--> >>
--> >>     Participate (have each RBridge participate in STP as 
--> if it were a 
--> >> bridge).
--> >>
--> >>
--> >>
--> >> Hence, when we say "Drop BPDUs" we are not saying that 
--> we cannot look
--> >>
--> >> at them, we are just saying that we're not doing one of 
--> the other two 
--> >> choices.
--> >>
--> >>
--> >>
--> >> --
--> >>
--> >> Eric
--> >>
--> >>
--> >>
--> >>
--> >> ________________________________
--> >>
--> >>
--> >> 	From: rbridge-bounces at postel.org
--> >> [mailto:rbridge-bounces at postel.org] On Behalf Of Gideon Kaempfer
--> >> 	Sent: Friday, November 03, 2006 1:40 AM
--> >> 	To: Radia Perlman
--> >> 	Cc: rbridge at postel.org
--> >> 	Subject: Re: [rbridge] Traffic storms
--> >>
--> >> 	Radia,
--> >>
--> >> 	Wouldn't this create a link between TRILL and STP we are trying
--> >>     
--> > to 
--> >   
--> >> avoid?
--> >>
--> >> 	Relying on the fact that a LAN segment has some kind of unique 
--> >> identifier (such as the root bridge ID) seems like a 
--> very practical 
--> >> solution to me, but strongly reliant on the fact that 
--> the Rbridges 
--> >> actually process BPDUs. I thought they were just meant to discard
--> >>     
--> > them.
--> >   
--> >> Is this acceptable?
--> >>
--> >> 	Regrads,
--> >>
--> >> 	 Gidi
--> >>
--> >>
--> >>
--> >> 	On 11/3/06, Radia Perlman <Radia.Perlman at sun.com> wrote:
--> >>
--> >> 	The simplest way to put it, I think, is that in certain
--> >>     
--> > transitory
--> >   
--> >> 	situations there might be two
--> >> 	RBridges that both think they are Designated RBridge, and that
--> >>     
--> > is 
--> >   
--> >> bad,
--> >> 	but should stop
--> >> 	as soon as a single Hello is received by the RBridge who should
--> >>     
--> > not 
--> >   
--> >> be
--> >> 	Designated.
--> >>
--> >> 	I think PIM has similar transitory situations that can occur,
--> >>     
--> > and
--> >   
--> >> 	bridges can also have (hopefully
--> >> 	temporary) problems if a repeater came up and merged two LANs. I
--> >>     
--> >
--> >   
--> >> think
--> >> 	such things are
--> >> 	annoying but not fatal. But I think it's possible we can with
--> >>     
--> > little
--> >   
--> >> 	effort avoid this problem.
--> >>
--> >> 	However, with RBridges, because the bridge spanning tree
--> >>     
--> > algorithm
--> >   
--> >> 	elects a Root, there's
--> >> 	really a way of uniquely identifying a LAN (where "LAN" is a
--> >>     
--> > bunch of
--> >   
--> >> 	links connected with
--> >> 	bridges). The unique identifier is the root bridge.
--> >>
--> >> 	When the B1-B2 link is down, RB1 and RB2 will see the topology
--> >>     
--> > as two
--> >   
--> >> 	separate links, and each
--> >> 	one will have a distinct spanning tree Root bridge (RB1 will see
--> >>     
--> > B1, 
--> >   
--> >> and
--> >> 	RB2 will see B2 as the root).
--> >>
--> >> 	When the B1-B2 link comes up, the bridges will first merge the
--> >>     
--> > two
--> >   
--> >> 	links, and either RB1 or RB2 will
--> >> 	see that the bridge spanning tree root has changed. This will be
--> >> 	discovered before B1 and B2 forward
--> >> 	traffic across the link because of the bridge forwarding delay.
--> >> 	If B1 has better priority as bridge spanning tree root than B2,
--> >>     
--> > then 
--> >   
--> >> RB1
--> >> 	will not notice anything
--> >> 	different when the B1-B2 link comes up. But RB2 will notice
--> >> 	something different; the spanning tree root has changed
--> >>     
--> > identities 
--> >   
--> >> from
--> >> 	"B2" to "B1".
--> >>
--> >> 	Given this, RB2 could temporarily stop forwarding to or from the
--> >>     
--> > link
--> >   
--> >> 	when the Root bridge
--> >> 	changes identities, though it should definitely immediately send
--> >>     
--> >
--> >   
--> >> IS-IS
--> >> 	Hellos (either RB1 or RB2 will
--> >> 	be elected Designated Router in the IS-IS election for that
--> >>     
--> > link). If
--> >   
--> >> 	RB2 has better prioirty for
--> >> 	root, the RB1 will immediately stop forwarding to or from the
--> >>     
--> > link 
--> >   
--> >> when
--> >> 	it sees the Hello from RB2.
--> >> 	If RB2 has better priority in the IS-IS election, then RB1
--> >>     
--> > should
--> >   
--> >> 	immediately send an IS-IS Hello
--> >> 	when it sees a Hello from a new RBridge on the link.
--> >>
--> >> 	So I think this is not a big deal, and that if we are worried,
--> >>     
--> > we can
--> >   
--> >> 	specify that an RBridge should
--> >> 	stop acting like the Designated RBridge for a few seconds after
--> >>     
--> > the
--> >   
--> >> 	identity of the Root in the spanning
--> >> 	tree algorithm changes.
--> >>
--> >> 	Or we could be even fancier and have each RBridge announce in
--> >>     
--> > its 
--> >   
--> >> IS-IS
--> >> 	Hellos which LAN IDs it
--> >> 	is Designated for, where a LAN ID is the MAC address of the Root
--> >>     
--> >
--> >   
--> >> bridge.
--> >> 	So RB1 continue
--> >> 	forwarding if the identity changes from B1 to B2 provided no
--> >>     
--> > other
--> >   
--> >> 	RBridge has claimed to be connected
--> >> 	to B2. But if RB2's LSP claims it is attached to B2, then RB1
--> >>     
--> > must 
--> >   
--> >> stop
--> >> 	forwarding for enough time
--> >> 	for the IS-IS election to sort itself out and choose a
--> >>     
--> > Designated 
--> >   
--> >> RBridge.
--> >>
--> >> 	Radia
--> >>
--> >>
--> >>
--> >>
--> >>
--> >>
--> >> 	Gideon Kaempfer wrote:
--> >>
--> >> 	>Following mention by Silvano of broadcast and multicast storms
--> >>     
--> > (and 
--> >   
--> >> the need
--> >> 	>to protect against them), I played around with different
--> >>     
--> > scenarios 
--> >   
--> >> and came
--> >> 	>upon one I would appreciate your comments on (in the hope I am 
--> >> pointing out
--> >> 	>a non-existent issue with TRILL). I believe a broadcast and
--> >>     
--> > even a 
--> >   
--> >> unicast
--> >> 	>storm could be created as the result of a loop that isn't
--> >>     
--> > protected 
--> >   
--> >> by TTL
--> >> 	>nor by STP in the case of a link connecting two separate LAN 
--> >> segments coming
--> >> 	>to life.
--> >> 	>
--> >> 	>- RB1 ---- RB2 -
--> >> 	>   |        |
--> >> 	>-  B1 --x-- B2 -
--> >> 	>   |        |
--> >> 	>   H1       H2
--> >> 	>
--> >> 	>1. The network (segment) involved consists of two Rbridges
--> >>     
--> > (RB1, 
--> >   
--> >> RB2), two
--> >> 	>bridges (B1, B2) and two hosts (H1, H2). They are physically 
--> >> connected as
--> >> 	>depicted.
--> >> 	>2. State A: the direct link between B1 and B2 is down. B1 and
--> >> B2 find
--> >> 	>themselves on different LAN segments and hence different
--> >>     
--> > spanning 
--> >   
--> >> trees. RB1
--> >> 	>and RB2 are both designated Rbridges (each for the segment of
--> >>     
--> > the
--> >   
--> >> 	>corresponding bridge).
--> >> 	>3. State B: the direct link between B1 and B2 goes up (someone 
--> >> connects a
--> >> 	>cable). B1 and B2 discover each other and establish a common 
--> >> spanning tree.
--> >> 	>RB1 and RB2 both find themselves attached to the same LAN
--> >>     
--> > segment 
--> >   
--> >> and hence
--> >> 	>RB1 (without loss of generality) will eventually become the 
--> >> designated
--> >> 	>Rbridge for it.
--> >> 	>4. Just before RB1 and RB2 identify that they are both on the
--> >>     
--> > same 
--> >   
--> >> segment
--> >> 	>and RB2 stops functioning as a designated Rbridge the following
--> >>     
--> >
--> >   
--> >> scenario
--> >> 	>seems possible:
--> >> 	>  a. H1 sends a broadcast frame.
--> >> 	>  b. B1 receives it and forwards to RB1 and B2.
--> >> 	>  c. RB1 (encapsulates and) forwards to RB2.
--> >> 	>  d. B2 forwards to RB2 and H2.
--> >> 	>  e. RB2 forwards the copy from RB1 to B2 (and the copy from B2
--> >>     
--> > to 
--> >   
--> >> RB1).
--> >> 	>  f. (RB1 forwards to B1.)
--> >> 	>  g. B2 forwards (again) to H2 and to B1.
--> >> 	>  h. B1 forwards to H1 (see remark below regarding filtering
--> >>     
--> > table
--> >   
--> >> 	>contamination) and to RB1.
--> >> 	>  i. Etcetera etcetera.
--> >> 	>5. A broadcast storm is born, created by a loop that is not 
--> >> protected by TTL
--> >> 	>(due to the fact that forwarding between the Rbridges is only
--> >>     
--> > across 
--> >   
--> >> a
--> >> 	>single hop) nor by STP (due to the fact that Rbridges do not 
--> >> participate in
--> >> 	>STP).
--> >> 	>6. If forwarding commences at the hardware level and no
--> >>     
--> > broadcast 
--> >   
--> >> rate
--> >> 	>limiting is in place, the storm may cause severe damage in a
--> >>     
--> > very 
--> >   
--> >> short time
--> >> 	>(note that replicated frames are sent to H1 and H2 (or any
--> >>     
--> > network 
--> >   
--> >> they
--> >> 	>could represent).
--> >> 	>7. Another unfortunate effect of this storm is that B1 and B2
--> >>     
--> > no 
--> >   
--> >> longer know
--> >> 	>where H1 is located (due to the contamination of their
--> >>     
--> > filtering 
--> >   
--> >> tables by a
--> >> 	>frame from H1 that arrives from the wrong direction (and in
--> >>     
--> > fact 
--> >   
--> >> from
--> >> 	>multiple directions). As a result, a possible unicast frame
--> >>     
--> > from H2 
--> >   
--> >> to H1
--> >> 	>will just join the storm over the loop at least in one
--> >>     
--> > direction 
--> >   
--> >> (RB2 will
--> >> 	>forward it to RB1) but will not arrive at H1...
--> >> 	>
--> >> 	>One possible solution could be for RB2 to identify the fact
--> >>     
--> > that it 
--> >   
--> >> is
--> >> 	>receiving a frame from a host with a MAC address that is
--> >>     
--> > associated 
--> >   
--> >> with a
--> >> 	>segment it thought it isn't connected to. Hence, it may trigger
--> >>     
--> > an 
--> >   
--> >> immediate
--> >> 	>neighbor discovery / designated Rbridge election. However,
--> >>     
--> > because 
--> >   
--> >> Rbridges
--> >> 	>should allow host mobility, this frame may need to be forwarded
--> >>     
--> > (and 
--> >   
--> >> hence
--> >> 	>the storm commences).
--> >> 	>
--> >> 	>As mentioned above, any comments are welcome.
--> >> 	>  Gideon Kaempfer
--> >> 	>
--> >> 	>_______________________________________________
--> >> 	>rbridge mailing list
--> >> 	>rbridge at postel.org
--> >> 	> http://mailman.postel.org/mailman/listinfo/rbridge
--> >> <http://mailman.postel.org/mailman/listinfo/rbridge>
--> >> 	>
--> >> 	>
--> >>
--> >> 	_______________________________________________
--> >> 	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
--> >
--> >   
--> 
--> _______________________________________________
--> rbridge mailing list
--> rbridge at postel.org
--> http://mailman.postel.org/mailman/listinfo/rbridge
-->

---

From: pfr at info.ucl.ac.be (Pierre Francois)
Date: Mon, 06 Nov 2006 15:01:00 -0800

> - particularly in the case of L2 forwarding generally.

That would mean that under a **planned** removal of an rbridge-rbridge 
link, where the rbridge network could suffer of forwarding
loops, you could drop traffic. Indeed,  "IS-IS like FIBs" are updated in 
an asynchronous fashion upon topological changes, so that transient 
inconsistency in the forwarding of
unicast traffic, leading to ?loops,  is something that regularly occur.

Moreover, if you use TE tools to set up the metrics of your links, you 
might end up with metric(X-->Y) != metric(Y-->X).
In such cases, "longer ?loops", i.e. loops involving 3 or 4 rBridges can 
occur upon convergence,
in which case the simple "incoming interface <>outgoing interface" loop 
mitigation check won't work.

Pierre.

---

From: akatlas at gmail.com (Alia Atlas)
Date: Mon, 6 Nov 2006 15:31:49 -0800

The multi-hop micro-forwarding loops only come up with asymmetric link
costs.  In TRILL, I believe the assumption is that there aren't
asymmetric link costs so that traffic flows are bidirectional.

For this case, dropping frames that would transmit through the same
interface that received it would handle the micro-forwarding loops, I
believe.

Alia

On 11/6/06, Pierre Francois <pfr at info.ucl.ac.be> wrote:
> _______________________________________________
> rbridge mailing list
> rbridge at postel.org
> http://mailman.postel.org/mailman/listinfo/rbridge
>

---

From: mshand at cisco.com (mike shand)
Date: Wed, 08 Nov 2006 17:31:40 +0000

At 23:31 06/11/2006, Alia Atlas wrote:
>costs.

We used to think that was true, but it is also 
possible to introduce multihop forwarding loops via ECMP.

e.g
                D
              /  \
         A------B----C
         |           |
      E-----------F

All costs 1, except BC = 2 and EF = 10 (both symmetric)
When AB fails C was previously forwarding to A via both B and D
After, B forwards via both D and C
So if a packet gets sent (say) C->B AND B->D we end up with a cyclic loop.

>  In TRILL, I believe the assumption is that there aren't

Handle, in the sense of avoiding looping, but of 
course the traffic would be dropped!

         Mike

> > > --> >>        Given this, RB2 could 
> temporarily stop forwarding to or from the
> > > --> >>
> > > --> > link
> > > --> >
> > > --> >>        root, the RB1 will 
> immediately stop forwarding to or from the
> > > --> >>
> > > --> > link
> > > --> >
> > > --> >> when
> > > --> >>        stop acting like the 
> Designated RBridge for a few seconds after
> > > --> >>
> > > --> > the
> > > --> >

---

From: mshand at cisco.com (mike shand)
Date: Wed, 08 Nov 2006 18:01:56 +0000

>course the traffic would be dropped!

Sorry, forgot to say...

So this means that where you have ECMP you would have to check for a 
packet received from ANY of the interfaces on which you could 
possibly transmit it, not just the one which you would actually 
choose for this packet.

         Mike

---

From: akatlas at gmail.com (Alia Atlas)
Date: Wed, 8 Nov 2006 13:42:30 -0800

> So if a packet gets sent (say) C->B AND B->D we end up with a cyclic loop.

Interesting case.  When we'd discussed it before, I think we'd missed
this ECMP case.
What are the implications for PLSN  with this?  Does your simulator
catch these cases?

> course the traffic would be dropped!

Sure - but in the absence of a fast-reroute technology, that's what
you need to do on failures.

Alia

---

From: pfr at info.ucl.ac.be (Pierre Francois)
Date: Wed, 08 Nov 2006 13:48:43 -0800

Alia,

This problem has been raised a while ago, but as far as I remember, we 
found out that it didn't make PLSN rule for "symmetrical
links only" networks incorrect. i.e. you really need asym. link metrics 
to have plsn loop free rules go wrong, ECMP
could not make plsn do bad things.

Pierre.