Subject: [rbridge] Control plane scalability

From: zinin at psg.com (Alex Zinin)
Date: Thu, 3 Mar 2005 16:49:06 -0800

Radia, folks-

Below are some thoughts on scalability of the routing part in a multi-VLAN
environment below. Note that I'm explicitly scoping this to control plane only.
Comments are welcome.

  VLANs are used in Ethernet networks of a considerable size to control the size
  of the broadcast domains. While the size of each VLAN is naturally limited by
  broadcast, the total number of VLANs in the network can be pretty high
  (O(100s) for a mid-size network), and so the physical size of the network may
  be quite large. Connectivity between VLANs is provided via routing at the
  network layer. Within the VLAN, switches do STP and bridging.

  Control plane functionality in switches is limited to STP operations. STP is
  data- and computationally inexpensive. One of its nice properties is that it
  has no knowledge of end stations. Its purpose is to prune the topology to
  remove possible loops, rather than to find shortest paths to destinations. STP
  is not used to populate the MAC table, and its operation is completely
  independent from the MAC learning and forwarding processes. Therefore, STP
  message and computational complexity doesn't depend on the number of end
  stations. The protocol also doesn't maintain a complete topology map, but
  rather functions in distance-vector-like behavior.

Looking at the control plane part of rbridges now:

  Though technical details haven't been worked out yet, the essence of the
  routing part in the RBRIDGE proposal is to run a link-state protocol like
  IS-IS in the bridges and let them announce learned MAC-addresses as we do
  the IP prefixes now--as leaves hanging off the transit nodes.

  Control-plane complexity in link-state routing roughly includes two
  components: database/flooding, and route calculation (I skip neighbor
  discovery and maintenance for simplicity). Several parameters drive the
  overhead in these two components:

     1) size of the topology graph and its denseness
     2) frequency of topological changes in the graph
     3) amount of routing information announced
     4) frequency of routing information changes

  Compared to STP, the amount of information that needs to be maintained by
  rbridges in the control plane is clearly greater. Same is true for the
  computational overhead.

  The first two scaling parameters (graph size and change frequency) do not
  worry me much, since topologies of L2 networks tend to me much less complex
  than those of IP networks (that may be a result of experience with STP
  convergence, and could be expected to change in future).

  The key consideration is the amount of MAC reachability info and its change
  frequency. Clearly, since we're talking about announcing each individual MAC
  address, and they are not summarizeable, we will have much more information to
  be distributed than we do in IP routing. E.g., in a multisegment network, if
  IP routing was used with /27 subnets, a 100 IP prefixes would represent about
  3,000 hosts that would have to be announced individually in TRILL. One could
  certainly make a valid argument that the size of an Ethernet segment is
  limited by broadcast, and that a reasonable segment would include a few
  hundred stations maximum, which is nothing for link-state IP routing protocol
  implementations today. However, I believe we need to look at the multi-VLAN
  scenario in large scale networks to understand the scaling properties.

  In a multi-VLAN environment, a single physical network of L2 switches
  accommodates multiple virtual VLAN topologies. The number of VLANs in a single
  network may range from a few to a few hundred. The total number of stations
  within VLANs may vary from hundreds to tens of thousands. Challenges of
  scaling link-state routing in such environments are similar to those of
  scaling routing in the VPN case.

  As proposed now, a single copy of IS-IS would be running on all switches in
  the network. This means that all switches would need to flood and store MAC
  addresses in all VLANs, regardless of whether they need them or not. This
  scheme clearly has scaling problems--e.g., a 100 VLANs with 500 stations will
  require flooding and storing 50,000 entries on each switch in the network,
  regardless of its position in the network, throughput, computational
  abilities, available memory, or what traffic it actually sees.

  An alternate approach is to run a separate instance of IS-IS for each VLAN.
  While this may give acceptable results in moderate-size network with a few
  sparsely populated VLANs, it will have scaling issues of a different type in
  mid- to large-size deployments, where core switches participate in the
  majority of VLANs. More specifically, the number of individual processes
  that would run on the control CPU would stretch the CPU resources.

  The most promising approach would be to use what link-state protocols don't do
  today yet--multi-topology flooding, where information related to each VLAN
  would be flooded only to the nodes that need it. Note that this would only
  reduce the amount of information maintained by the edge switches, and only if
  they participate in a considerably smaller subset of VLANs. The core switches,
  exposed to most of VLANs would still have to maintain entries for all of them
  in their control-plane databases.

  Update dynamics of topological information within a RBRIDGE network should be
  similar to that of an IP network. Frequency of reachability info (MAC address)
  updates will generally have different patterns. E.g. spikes of updates related
  to "start-of-day" activities, some level of noise related to stations that
  hibernate and wake up. In scenarios with massive real-time relocations, as in
  the wireless case, the rate of updates may grow considerably high.

-- 
Alex
http://www.psg.com/~zinin

---

From: margaret at thingmagic.com (Margaret Wasserman)
Date: Fri, 4 Mar 2005 07:48:21 -0500

Hi Alex,

A few clarifying questions and some random thoughts...

>   network layer. Within the VLAN, switches do STP and bridging.

Roughly how many nodes are on a "mid-size network"?  How many L2 links?

You later talk about a 50,000 node, 100 link network.  Would you consider that
to be a mid-sized network?  Personally, I have never been involved in network
administration at an organization that owned >5,000 nodes, so I consider
50,000 nodes to be a *large* enterprise network.  I think of 
mid-sized enterprise
networks as consisting of a few hundred to a few thousand nodes.  (Small ones
are less than a few hundred.)

What do you mean by "routing at the network layer"?  It is my 
understanding that
each VLAN represents an IP subnet, and that IP routing between VLANs is
performed using normal IP routing protocols (OSPF, etc.).  This requires each
VLAN to be configured with IP addresses on a separate IP subnet, and nodes
cannot move between different VLANs without changing IP addresses or running
a mobility/tunneling protocol.

>   Control plane functionality in switches is limited to STP operations.

I am not sure what definition of "switches" you are using here.  I 
think that some
switches also contain routing functionality (as described above) for IP routing
between VLANs.

>  STP is

Some of these same advantages could be ascribed to RIP (as opposed to
OSPF or IS-IS), right?

>      4) frequency of routing information changes

These are excellent factors to focus on, I think.  Do we know which of these
factors is pushing the limits of existing switching hardware?  Or is the
computational portion of a typical switch under-used, with the cost largely
contained in the switching fabric itself?

>   convergence, and could be expected to change in future).

Right.  One of the advantages of rbridges would be the ability to 
take advantage
of redundant paths, so we should probably assume that people will install more
redundant paths in an rbridge cloud than in an STP network.

>   scenario in large scale networks to understand the scaling properties.

Without a way to limit broadcast/multicast traffic to a specific set 
of nodes, a
single rbridge cloud could not grow beyond the practical size for a broadcast
domain.  I think that you may be an order of magnitude low in this estimation
and that broadcast domains of a few thousand nodes may be reasonable
(based  on my dated knowledge of pre-VLAN bridged ethernet deployments).
This still wouldn't tax the memory and processing capability of a 
mid-sized router,
though.

It would be interesting to get some real-world data on this.  Are there any
enterprise network operators in the room who would like to inject some numbers
about the practical size of a single broadcast domain?

>   scaling routing in the VPN case.

We should probably do some investigation to determine if the scaling factors
of flat routing will hit before or after the scaling factors of a 
single broadcast
domain.  I agree that (as currently defined) an rbridge cloud will be a single
broadcast domain, and I expect that limits the size of an rbridge cloud to
something that can be flat routed using a fairly modest amount of processing.

And, unless folks have some idea of how to create multiple broadcast domains
without creating separate IP subnets (I am not seeing how that would work), it
will be necessary (in rbridge networks, just like STP networks) to configure
  different IP subnet prefixes for different broadcast domains and to route
between those domains at the IP layer.

But, you seem to be making some other assumptions...

>   abilities, available memory, or what traffic it actually sees.

I don't understand where the VLANs come in as a multiplier.  If you have 100
separate rbridge clouds with 500 nodes each, the internal rbridges for
each cloud will each have 500 entries.  Outside of the rbridge clouds,
you will effectively have 100 IP subnets (with separate IP subnet addresses
that will be routed at the IP layer).  So, you will have 100 entries in your IP
routing tables and a maximum of 500 entries in the "routing" table for any
given rbridge.

Are you planning to build one massive device that would run all of the
bridging and routing for this 50,000 node network?  If so, I agree that it
would need to run 100 rbridge instances (each with 500 "routes"), plus
at least one IP routing instance (with 100 routes).  I don't really see a
problem with that, though...

The alternative device would be running 500 instances of STP and at
least one IP routing instance (with 100 routes).

>   that would run on the control CPU would stretch the CPU resources.

It isn't necessary to run separate IS-IS processes to have separate instances
of the routing table...  At least, I have worked on IP and OSPF implementations
that ran multiple routing instances in a single process (with a single copy of
the running code in RAM) by accesses different  routing tables based on
per-instance state blocks.  But, this all falls into the category of 
implementation
details, I think...

Besides, it really isn't possible to talk about whether CPU resources will be
adequate without understanding the time constraints for when the calculation
would need to complete.  Do you have a good feel for those constraints?

>   the wireless case, the rate of updates may grow considerably high.

A lot of this would depend on how the rbridge learning function handles the
caching and timeout of information.  Would an entry go away when a node
hibernates?  Or only when that node stops responding to <what?> for <how
long>?  What happens when the same node shows up elsewhere in the
topology?

It is hard, at this point, to distinguish between questions/issues in four
categories:

(1) Inherent properties of the TRILL concept (such as the scaling properties
     of flat routing MAC addresses inside rbridge clouds).
(2) Specific properties of the current rbridge proposal (that could change).
(3) Ideas that people have about how we could expand rbridge to solve
     additional problems (like adding a broadcast domain concept).
(3) Constraints that need to be considered for standards work in this
     space (such as the practical limits for the size of broadcast domains).

I think that your post touches on all of these areas, and we need to
figure out how to break them apart and how/when to address each of
them.

Margaret

---

From: sommerfeld at sun.com (Bill Sommerfeld)
Date: Fri, 04 Mar 2005 11:07:37 -0500

On Thu, 2005-03-03 at 19:49, Alex Zinin wrote:
>   More specifically, the number of individual processes

On the other hand, multiple instances of a protocol are probably the easiest
way to exploit thread-level parallelism.  

And scheduling algorithms which can cope efficiently with many
threads/processes aren't exactly exotic.

Maybe I'm making a big leap here but somehow I think 
multicore/multithreaded/etc. processors will eventually find their way into
the embedded space.

(And I agree with everything Margaret said about the 1:1 linkage you presume
between protocol instance and "process" being an implementation artifact.
Admittedly one that's painful to change...)

					- Bill

---

From: ruwhite at cisco.com (Russ White)
Date: Fri, 4 Mar 2005 12:51:49 -0500 (Eastern Standard Time)

> Control plane functionality in switches is limited to STP operations. STP 
> is data- and computationally inexpensive. One of its nice properties is 
> that it has no knowledge of end stations. Its purpose is to prune the 
> topology to remove possible loops, rather than to find shortest paths to 
> destinations. STP is not used to populate the MAC table, and its 
> operation is completely independent from the MAC learning and forwarding 
> processes. Therefore, STP message and computational complexity doesn't 
> depend on the number of end stations. The protocol also doesn't maintain 
> a complete topology map, but rather functions in distance-vector-like 
> behavior.

I'm actually not entirely certain this is true... While STP is, itself, 
rather simple, and concerned with finding loops, isn't layer 2 address 
learning also required, along with the requisite timers, etc? If so, then I 
would class these as part of the control plane, as well, I think (?).

> The key consideration is the amount of MAC reachability info and its 
> change frequency. Clearly, since we're talking about announcing each 
> individual MAC address, and they are not summarizeable, we will have much 
> more information to be distributed than we do in IP routing. E.g., in a 
> multisegment network, if IP routing was used with /27 subnets, a 100 IP 
> prefixes would represent about 3,000 hosts that would have to be 
> announced individually in TRILL. One could certainly make a valid 
> argument that the size of an Ethernet segment is limited by broadcast, 
> and that a reasonable segment would include a few hundred stations 
> maximum, which is nothing for link-state IP routing protocol 
> implementations today. However, I believe we need to look at the 
> multi-VLAN scenario in large scale networks to understand the scaling 
> properties.

And this is where my question comes in, above. No, STP doesn't carry these, 
but the actual learning of where layer 2 addresses are attached to the 
network is required to make an STP based bridged network actually work, 
correct? The only real difference is, then, between learning these 
addresses as they are attached, vs when they transmit. I don't know that 
there's a lot of difference, computationally, between the two.

In other words, I don't think a link state vs stp comparison actually 
captures all the elements of complexity involved in the actual operation of 
the network (?).

>  in their control-plane databases.

This sound like it might actually scale better than multiple processes, one 
per vlan. Note that if you're using MPLS as your "core," you might not even 
need this. You might be able to aggregate the address spaces using labels 
and sites, so the edges see the full table, or at least the part of the 
table they care about, while the core sees just site to site connections 
(?)....

Think that might be feasible??

:-)

Russ

__________________________________
riw at cisco.com CCIE <>< Grace Alone

---

From: zinin at psg.com (Alex Zinin)
Date: Fri, 4 Mar 2005 13:29:42 -0800

Bill, Jarno-

 Combined answers to two messages.

 Scaling a routing implementation in general is certainly mostly an
 implementation issue, though, of course, implementations inherit efficiency of
 the algorithms used inside the protocol.

 Scaling routing in virtual topologies takes more than that, however. There are
 very clear implementation-independent scaling differences between
 multi-instance and aggregated (multi-topology) approaches, such as:

  - amount of CPU, BW, and memory spent on neighbor discovery and maintenance;
    the multi-instance approach takes times more, since it operates on virtual
    topologies and sees N times more adjacencies, while the aggregated one operates
    on the physical one.

  - amount of CPU and BW required to reconverge after a topology change;
    in the multi-instance case, each physical topology change maps into N
    virtual topology changes, that result in modification of N neighbor
    adjacencies, reorigination, and reflooding of N LSPs, recalculation of
    N SPFs and routing tables; the aggregated approach sees the physical
    topology, and thus spends less of those.

 When N is small (e.g. O(10)), the multi-instance approach gives acceptable
 results. When N grows larger, however (e.g. current campus network deployments
 already can use 100s to a 1000 VLANs), it becomes a problem. In other words,
 its scaling properties are limited.
    
 This is extremely similar to the question of scaling routing in the L3 VPN
 case. Ross Callon et al did a great job describing different trade-offs of
 routing in VPN in the framework document: draft-ietf-l3vpn-framework-00.txt.
 I would recommend reading it.

Alex

Thursday, March 3, 2005, 11:10:34 PM, jarno.rajahalme at nokia.com wrote:
> Isn't this an implementation/platform issue? E.g. running the different
> instances as threads on the same process would not cause any extra CPU
> overhead?

> So, running separate protocol instances should not be ruled out yet.

---

From: zinin at psg.com (Alex Zinin)
Date: Fri, 4 Mar 2005 14:38:35 -0800

Margaret,

>From what I know, switched campus networks today have in the order of 1K VLANs
and a few tens of thousands of stations.

> 50,000 nodes to be a *large* enterprise network. I think of mid-sized
> enterprise networks as consisting of a few hundred to a few thousand nodes.
> (Small ones are less than a few hundred.)

We're on the same page here. Note that the new Ethernet service providers, that
are emerging now, will have thousands of customers, and are already pushing the
common limit of 4K VLANs and current CAM table limits with 100s of MACs that
will need to be supported.

The point being here: looking at a single broadcast domain (VLAN) in this case
is not sufficient. We have to push it to the numbers we're about to see to
understand how this scales.

> What do you mean by "routing at the network layer"?

That was a generalization for IP, IPX, AT routing. Think IP routing.

> It is my understanding that each VLAN represents an IP subnet, and that IP
> routing between VLANs is performed using normal IP routing protocols (OSPF,
> etc.). This requires each VLAN to be configured with IP addresses on a
> separate IP subnet, and nodes cannot move between different VLANs without
> changing IP addresses or running a mobility/tunneling protocol.

That's how we scale beyond the limits of the broadcast domain today. I didn't
catch if you were trying to say this was a bad thing.

> I am not sure what definition of "switches" you are using here.

I mean Ethernet switches.

> I think that some switches also contain routing functionality (as described
> above) for IP routing between VLANs.

Of course. Those look logically as routers.

> Some of these same advantages could be ascribed to RIP (as opposed to

Close, but not exactly. STP is a single-destination (root) protocol.

> factors is pushing the limits of existing switching hardware?

Those were scaling aspects of the link-state protocols, that don't run on the
Ethernet switches today, and the point was to see what in rbridges would be
different from IP routing.

>   Or is the

for pure Ethernet switches (i.e. routing functionality aside), the control plane
part is simple.

> Without a way to limit broadcast/multicast traffic to a specific set of nodes,
> a single rbridge cloud could not grow beyond the practical size for a
> broadcast domain.

I would even take it one step further and say that rbridges need a viable way
of scaling in an environment with a large number of VLANs.

> I think that you may be an order of magnitude low in this estimation and that
> broadcast domains of a few thousand nodes may be reasonable (based on my dated
> knowledge of pre-VLAN bridged ethernet deployments). This still wouldn't tax
> the memory and processing capability of a mid-sized router, though.

The above wasn't an attempt to come at the maximum practical size of a broadcast
domain. It was to show how a number of IP prefixes in a network would translate
to the number of MACs.

> about the practical size of a single broadcast domain?

I found a publicly-available description of a university campus network. Here's
the URL: http://sydnet.usyd.edu.au/doc/sydnet.html
Dated 1998 (7 years ago), they had 100 VLANs and 12,000 Ethernet ports.

> of flat routing will hit before or after the scaling factors of a single
> broadcast domain.

Within a single VLAN, broadcast limits will kick in first. I'm not concerned
about this. Multi-VLAN environment is a different story.

> I agree that (as currently defined) an rbridge cloud will be a single

> between those domains at the IP layer.

I'm not sure what you are arguing here. The points above are obvious...

> bridging and routing for this 50,000 node network?

Margaret, when building switched Ethernet networks today, folks don't build
different broadcast domains using separate sets of single-VLAN devices. Neither
they use a single massive device to connect all stations 50,000 as you suggest
above. They build VLANs using multi-VLAN switches connected by VLAN trunks.
Those VLANs are distributed location-wise, and switches in the core of the
network have visibility to most (if not all) VLANs through those trunks.

> If so, I agree that it

See my reply to Bill and Jarno.

> least one IP routing instance (with 100 routes).

See my note on scaling STP in the original message.

> implementation details, I think...

I shouldn't have used the word "process", which is simply a useful abstraction
for resource separation that I used in a wider sense to represent a set of data
structures and computations associated with a specific instance. There _are
implementation-independent scaling issues which I pointed out in my previous
message.

> would need to complete.  Do you have a good feel for those constraints?

I do have typical numbers, but this is about scalability analysis, which means
we're concerned with asymptotical efficiencies of each approach. In other words,
which algorithm will allow to support larger N using the same CPU, memory, and
BW... or to put it on the other side: which approach will require sooner memory
and CPU upgrades. Clearly maintaining N times more adjacencies and calculating N
times more SPFs becomes a problem with large Ns.

> hibernates?  Or only when that node stops responding to <what?> for <how
long>>?  What happens when the same node shows up elsewhere in the
> topology?

See the thread with subject "End station discovery/liveness detection"

>      of flat routing MAC addresses inside rbridge clouds).

Modulo very dynamic environments with frequent station relocations, TRILL
should be able to handle a single broadcast domain.

>      additional problems (like adding a broadcast domain concept).

I don't consider this an additional problem. If the rbridge approach wants to
see the light of deployment, the multi-VLAN case needs to be solved.

Alex

---

From: zinin at psg.com (Alex Zinin)
Date: Fri, 4 Mar 2005 14:57:07 -0800

Russ,

> would class these as part of the control plane, as well, I think (?).

This is an interesting point. MAC table can be classified as forwarding state,
similar to the forwarding table in IP routers. MAC table management indeed
involves control plane operations (timers, link state changes, STP topology
change notification), and should be counted.

> correct?

sure

> The only real difference is, then, between learning these 

The difference is what is in computations, data, and BW required to
learn/compute the MAC table entries. In the routing-based scheme, the MAC
entries are the direct result of operations of a distributed algorithm, while in
the bridging case, they are more results of listening to the transit traffic.

> per vlan.

I certainly think so. Experience with 2547 vs per-VR routing also suggests this.

> Note that if you're using MPLS as your "core," you might not even 

> Think that might be feasible??

This is approximately what I had in mind when I asked the question in the
"Forwarding inside rbridge cloud" threat. It may work even without MPLS.

Alex

---

From: margaret at thingmagic.com (Margaret Wasserman)
Date: Fri, 4 Mar 2005 18:13:33 -0500

Hi Alex,

>network have visibility to most (if not all) VLANs through those trunks.

Yes, I am somewhat aware of these deployments, but I don't understand why
this implies that the core switches would be rbridges and/or why they would be
part of most of the rbridge clouds.

Maybe we can talk about this when we have a whiteboard handy?  I'm not
trying to score debating points here .  I think we're just thinking 
about this differently,
and I'd like to understand how you believe the topology will work as opposed
to how I think it will work.

Margaret

---

From: zinin at psg.com (Alex Zinin)
Date: Fri, 4 Mar 2005 15:39:17 -0800

Margaret,

  Sounds like an interesting topic :)