Subject: [rbridge] New shim header proposal---without F-tag field

From: Eric.Gray at marconi.com (Gray, Eric)
Date: Wed, 1 Nov 2006 17:36:07 -0500

Silvano,

	Radia and I are currently having an off-line discussion 
about what your #3 below means.  I'll have to get back to you
on that.

	In the meantime, I have been assuming that we are using
a link state routing protocol - at least in part - because of
the built in shortest-path first algorithm.  This is implied 
in your #3.

	Assuming that one might be running IS-IS instances per
VLAN, IS-IS peers being used to support VLANs over RBridges 
do not need to compute Dijkstra (SPF) for all other RBridges.
Just those in the same VLANs, and part of the same LSDB.

 	Note that I am not saying everyone would do this, but -
if people did - then they would be trading RBridge IDs (as 
IS-IS instances) to achieve simplified per-VLAN LSDBs.

	By the way, "computing trees" is - IMO - not what is
being done.  It is only a way to view what is actually
being done.  Each IS-IS node has to know the shortest path
to all other IS-IS nodes in any case.  What it does in the
process of "constructing an IRT", is:

1)	compute this same information for all IS-IS instances 
	in the same LSDB,
2)	make a note of which RBridges it is on the shortest
	path between,
3)	create IRT entries for these RBridges

	This creates an analog of a point-to-multipoint tree 
because the RBridge can then retrieve all entries for any
frame based on the ingress RBridge ID in that frame (this
applies ONLY to multicast, broadcast and flooded frames).
The RBridge then forwards a copy of the received frame for
each of these entries.

	I think if you model it this way, you will find that 
the computational complexity is less than you think it is
- especially if the problem is broken up (by, for example,
using per-VLAN instancing).

--
Eric

--> -----Original Message-----
--> From: Silvano Gai [mailto:sgai at nuovasystems.com] 
--> Sent: Wednesday, November 01, 2006 5:02 PM
--> To: Gray, Eric; Russ White
--> Cc: Radia Perlman; rbridge at postel.org
--> Subject: RE: [rbridge] New shim header proposal---without 
--> F-tag field
--> 
--> 
--> Eric, 
--> 
--> This has nothing to do with the connectivity.
--> I simply read:
--> http://www.ietf.org/internet-drafts/draft-ietf-trill-rbridge
--> -protocol-00
--> .txt
--> 
--> tell me where I am wrong:
--> 1) there is one IRT per RBridge
--> 2) there is one ISIS LSA per RBridge, i.e. # of RBridge
--> 3) Each RBridge needs to compute Djikstra for all the IRTs, 
--> plus one for
--> the core instance, therefore the number of Djikstra 
--> computation is (# of
--> RBridge + 1)
--> 
--> The total CPU effort to compute Djikstra is therefore (# of 
--> Rbridge + 1)
--> on a LSA database # of Rbridges.
--> 
--> This has nothing to do with the connectivity/topology among the
--> RBridges.
--> 
--> You should like a lot the last proposal of Radia, because 
--> it elegantly
--> solves this problem for you.
--> 
--> -- Silvano
--> 
--> 
--> > -----Original Message-----
--> > From: Gray, Eric [mailto:Eric.Gray at marconi.com]
--> > Sent: Wednesday, November 01, 2006 1:11 PM
--> > To: Silvano Gai; Russ White
--> > Cc: Gray, Eric; Radia Perlman; rbridge at postel.org
--> > Subject: RE: [rbridge] New shim header proposal---without 
--> F-tag field
--> > 
--> > Silvano,
--> > 
--> > 	I did not actually say that we need to support half a
--> > million RBridges, I simply said that we may need to support
--> > more than 32K (or even 64K), consequently I do not support a
--> > reduction in the "name space" to 16 bits.
--> > 
--> > 	It would never work out to an order N^2 connectivity
--> > in any case, so this concern - IMO - comes under the heading
--> > of FUD.  If every port needed to be connected to every other
--> > port, then there would not be a need to have VLANs, and -
--> > hence - no need to have separate per-VLAN instances.  In a
--> > real world application where VLANs are used to connect large
--> > numbers of multi-port switches, only a few ports on a few
--> > switches typically end up connected to each individual VLAN.
--> > Some exceptions would occur, but they would be exceptions.
--> > Thus per-VLAN connectivity would be a sparse partial mesh, or
--> > VLANs would not be used.
--> > 
--> > 	This is in fact part of the justification for having
--> > per-VLAN IS-IS instances.  Trauma to part of the network is
--> > only going to impact on routing convergence for the IS-IS
--> > instances participating in affected VLANs.
--> > 
--> > --
--> > Eric
--> > 
--> > --> -----Original Message-----
--> > --> From: Silvano Gai [mailto:sgai at nuovasystems.com]
--> > --> Sent: Wednesday, November 01, 2006 11:55 AM
--> > --> To: Russ White
--> > --> Cc: Gray, Eric; Radia Perlman; rbridge at postel.org
--> > --> Subject: RE: [rbridge] New shim header proposal---without
--> > --> F-tag field
--> > -->
--> > -->
--> > --> What is a stretch is 32K trees of 32K nodes, which is what
--> > --> you need if
--> > --> you want to deploy the current TRILL proposal with 
--> 32K RBridges.
--> > -->
--> > --> Eric says that we need to accommodate half a million RBridges.
--> > --> Half a million tree of half a million nodes is unfeasible.
--> > -->
--> > --> If we want to support such a large number of Rbridges, we
--> > --> need to modify
--> > --> the current Trill proposal, reducing the number of trees
--> > --> that need to be
--> > --> computed.
--> > -->
--> > --> Agreed?
--> > -->
--> > --> -- Silvano
--> > -->
--> > -->
--> > --> > -----Original Message-----
--> > --> > From: Russ White [mailto:riw at cisco.com]
--> > --> > Sent: Wednesday, November 01, 2006 8:35 AM
--> > --> > To: Silvano Gai
--> > --> > Cc: Gray, Eric; Radia Perlman; rbridge at postel.org
--> > --> > Subject: Re: [rbridge] New shim header proposal---without
--> > --> F-tag field
--> > --> >
--> > --> > -----BEGIN PGP SIGNED MESSAGE-----
--> > --> > Hash: SHA1
--> > --> >
--> > --> >
--> > --> > >> 	I don't think there is consensus yet that we
--> > --> only need 16 bits
--> > --> > >> for RBridge IDs.
--> > --> > >
--> > --> > > With 16 bits, using 1 bit to indicate unicast, we 
--> can have 32K
--> > --> switches.
--> > --> > > According to the current definition of TRILL, there is
--> > --> the need to
--> > --> run
--> > --> > > Djikstra on a database with 32K records, one time 
--> for the core
--> > --> instance
--> > --> > > and 32K times for the IRTs. This is clearly out of
--> > --> reach even for
--> > --> the
--> > --> > > most powerful CPU.
--> > --> >
--> > --> > ?? Perhaps 32k trees is a stretch, but 32k nodes in a
--> > --> tree? I don't
--> > --> > think that's really a stretch on today's processors, from
--> > --> the scaling
--> > --> > work I've seen done in IS-IS.
--> > --> >
--> > --> > :-)
--> > --> >
--> > --> > Russ
--> > --> >
--> > --> > - --
--> > --> > riw at cisco.com CCIE <>< Grace Alone
--> > --> >
--> > --> > -----BEGIN PGP SIGNATURE-----
--> > --> > Version: GnuPG v1.4.2.2 (MingW32)
--> > --> > Comment: Using GnuPG with Mozilla - 
--> http://enigmail.mozdev.org
--> > --> >
--> > --> > 
--> iD8DBQFFSMypER27sUhU9OQRAqLwAJ9FLN2YNP2mrB6i0ZcV1fxLzAT0hgCfYHYj
--> > --> > 6mJCA68nQLjCD8US9nRZZag=
--> > --> > =kwzq
--> > --> > -----END PGP SIGNATURE-----
--> > -->
-->