Subject: [rbridge] Time to summarize "forward or block" BPDU thread

From: petera at nortel.com (Peter Ashwood-Smith)
Date: Tue, 18 Oct 2005 01:40:17 -0400

> Here's the counterexample:
> 
> Have existing bridges BLOCK.

  Thats not really a counter example but let me try to explain 
where you are getting confused below. 
 
> Assume each bridge computes its own spanning tree internally 
> (i.e., between its own ports on its own device), and sends 
> coded 'hellos' that it it recognizes if they loop, i.e., all 
> the thinks a campus would do.

  Because it would not be a MINIMUM spanning tree. However, yes, if you
repeatedly connect a set of node disjoint trees together with a single 
link, reducing the number of trees by one each time, the result is a 
tree. This I think is what you are suggesting and yes, I believe 
an algorithm like this does actually make a tree. The catch is that it
is NOT a minimum spanning tree and you cannot easily select a root.
STP produces a minimum spanning tree rooted where you want it so
you get much more with the STP protocol than just the hello/detect/block
idea. STP requires its BPDUs to flood through the network to elect
the root and compute paths to it and rbridge requires link state to
flood link information so it can compute the minium spanning tree.
Both protocols need to know about ALL the possible paths in their 
domains to minimize the resulting tree.
The DR mechanism is only used to prevent a loop between these two
domains but it does not by itself guarantee that the combination of
the two trees is still minimum. Therefore, the DR mechanism if applied 
by itself as you suggest does produce a tree but it is not minimum and
you
have no control over the root that is selected.

  Rbridge of course only uses this DR mechanism at the interface between
itself and some other domain (STP or manually configured), and so 
you end up with a minimum spanning tree in STP and a minimum spanning
tree in the rbridge
domain but the combination of the two is not necessarily the best
possible
since neither minimization was done over the complete set of links/nodes
available. This makes sense because if you take two minimum solutions 
over disjoint sets you cannot simply add them together to produce a 
global minimum solution. For example, I cannot take a shortest path from
some node S to an intermediate E and a shortest path from E to D, add
them together and
get the shortest path from S to D because there may be a much better E!
 
> Now if that works, let's do it for bridges and then we 
> wouldn't have a spanning tree convergence problem at all, right?

  It produces a tree but not a minimum spanning tree with no control
over
the root. So its not quite the 'work' you had in mind and this in a nut
shell is I believe your mistake.
 
> If that does NOT work, then why does it work for rbridge 
> campuses and not bridges?

  It does work its just that we want minimum spanning trees and
to do that we need information about all the nodes we can reach.
STP gets this by flooding BPDUSs and Rbridges by link state updates. 
Take away the BPUDS and you can't get minimum. Rbridges can take
the BPDU away [BLOCk] because it does its own minimum and combines the
results with DR to produce a possibly non global minimum solution but
that is the price you pay for neither side seeing all the data.

> My general test is "an rbridge campus needs to look like a 
> bridge" or "look like a link". If it does, then I know I 
> understand it. When it doesn't, it would be useful to 
> understand whether this is really a 'new  animal' and exactly 
> why it's newness is unique to rbridges (i.e., why it can't be 
> applied as well to bridges).

  I think you need to think of this as a new animal as Radia suggested.

  Hope this helps.

  Peter

> Joe

---

From: Radia.Perlman at sun.com (Radia Perlman)
Date: Mon, 17 Oct 2005 23:18:48 -0700

One nit, on terminology...

Just making sure that someone who has recently studied "minimum spanning 
trees"
doesn't get confused by your explanation, Peter.
You're not wrong, but the terminology "minimum spanning tree" usually 
refers to something different
than what you're talking about...
something where the total cost of all the links in the tree is minimum.

STP (and Dijkstra) do not compute minimum spanning trees. For instance, 
if you
had a Root R, with 3 links coming off it, attached to R1, R2, and R3, 
respectively,
with the cost of all those links being 10, and a link between R1 and R2 
of cost 1,
then STP and Disjkstra would compute the tree consisting of R and its 
attached
links.

That tree would have a total weight (add the link costs) of 30.

The minimum spanning tree would instead connect R2 to R1, so the total
weight would be 21.

STP (and Disjkstra) instead compute a tree of shortest paths from the 
root. They wouldn't
attach R2 to R1 because then the path from root to R2 would be 11 rather 
than 10
if R2 was attached to the Root.

Anyway...just for future reference on the term "minimum spanning tree"...

******
And now for more explanation...there's really nothing optimal about the tree
computed by STP. Any single shared tree will be good for some S-D pairs,
and bad for others.

The tree created by hopping across bridged islands won't be any more or less
optimal than if there were a giant spanning tree across the entire campus,
where we went to some effort to ensure the combination of RBridges and
bridges computed the same tree as they would have if everyone were bridges.

Plus...RBridges aren't computing a single tree anyway...they are computing
per-ingress-RBridge trees.

As I've said before, we really want to terminate the bridged islands, and
then have RBridges just see each bridged island as a single link.

Radia

Peter Ashwood-Smith wrote:

>_______________________________________________
>rbridge mailing list
>rbridge at postel.org
>http://www.postel.org/mailman/listinfo/rbridge
>  
>

---

From: saikat at seas.upenn.edu (Saikat Ray)
Date: Tue, 18 Oct 2005 12:06:34 -0400

[Saikat] I think it is a good opportunity to clarify one thing since the
concept of optimality rose. What cost-function are you considering
optimizing? If you use additive per-link static cost, then for the broadcast
case, under the assumption of symmetrical link costs, any given minimum
weight spanning tree is optimum regardless of the source of the packet. Then
why should there be multiple (per ingress) trees for broadcast?

Radia

---

From: Radia.Perlman at sun.com (Radia Perlman)
Date: Tue, 18 Oct 2005 09:45:51 -0700

I don't think we should strive for "optimal", but rather "simple, 
robust, and pretty good".

But what is optimized by STP (and Dijkstra) is the cost from each node 
to the Root.
If the Root were the only sender (which of course it isn't), then one 
could consider the spanning tree "optimal"
in distribution time (though not in total cost of delivery, which would 
require a minimum
weight spanning tree).

With link state routing, we can get optimal pt-to-pt paths. It's only 
for multicast that which spanning
tree is chosen may matter.

If a broadcast goes to all links, then one spanning tree is as good as 
another.

In an earlier email I mentioned several reasons why per-ingress trees 
are worth the effort:

Imagine the actual topology being a big circle, 20 hops around. If it 
were a single spanning tree,
one of the links in the circle would be broken. If a packet originates 
from the left side of the
break, it has to go completely around the circle to get to someone on 
the right side of the break,
even though in the physical topology it's only a single hop.

So, for instance, if those two links were the only VLAN A links, then 
the broadcast domain of VLAN A
requires 20 hops to deliver each packet, rather than a single hop, if it 
were a per-ingress RBridge tree.

Basically, with a per-ingress tree, then each packet gets delivered to 
each link optimally.

In the case of VLAN broadcast domains (e.g., for ARPs within VLAN A), 
and for IP multicast (assuming
RBridges snoop on IGMP so they know which subset of links have 
receivers), per-ingress trees can
wind up much less expensive to deliver traffic.

Radia

---

From: saikat at seas.upenn.edu (Saikat Ray)
Date: Tue, 18 Oct 2005 13:38:30 -0400

[Saikat] So you are considering additive per-link static (i.e. independent
of the load on the link) cost, right? That is what I wanted to confirm.