Subject: [rbridge] Max Network size

From: greg.daley at eng.monash.edu.au (Greg Daley)
Date: Tue, 03 May 2005 12:35:35 +1000

Hi Joe,

Joe Touch wrote:
> 
> Guillermo Ib??ez wrote:
> 
>>I have a question:
>>   What is the maximum network size (number of hosts) required/expected 
>>in TRILL? May be it was already stated somewhere, I am not aware of it.
>>Regards
>>Guillermo Ib??ez
> 
> 
> There is no limit of design; it is based on the capability of edge
> RBridges to handle encapsulation tables, as well as of interior RBridges
> to have scalable routing.
> 
> We expect to scale to numbers of hosts much higher than current bridges,
>  but it's hard to predict what the knee of the design curve will be (IMO).

If I recall, the only explicit mentions about size (apart from Alex's
routing cost overview) are that we don't want to scale to metropolis
(Sydney?) size.

Greg

---

From: touch at ISI.EDU (Joe Touch)
Date: Tue, 03 May 2005 07:36:18 -0700

> routing cost overview) are that we don't want to scale to metropolis

I believe there may be limits to the geographic scale, since some
protocols (e.g., MAC, ARP) have timing expectations. There are systems
that have tried to overcome this (L2VPN), but I'm not as familiar with
how well their results work in that regard.

But the question focused on number of hosts, and I believe that
limitation is based on engineering, not architecture.

Joe

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 254 bytes
Desc: OpenPGP digital signature
Url : http://www.postel.org/pipermail/rbridge/attachments/20050503/97b63180/signature.bin

---

From: gibanez at it.uc3m.es (Guillermo Ibáñez)
Date: Wed, 4 May 2005 13:45:33 +0200

Hello Joe,

More on maximum network size.
-So we can expect, for a network with one hundred thousand hosts, rbridges
with tables of that size. OK?
(No problem so far).
-Scalable routing between Rbridges: my understanding is that MAC addresses
are used for routing between them. Although the number of bridges will no be
too high (i.e thousands), I do not understand well the meaning of
"scalability of routing" as the flat addresses used do not permit route
aggregation. I did not follow the routing discussiong so may be I missed
something.

Rbridge types
- You mention "interior" Rbridges and "edge" Rbridges. Do you see any
functional differentiation between these two types ? In this case handled it
could be handled by self configuration (upon detection of hosts an interior
bridge becomes edge bridge). My understanding is that  there are no
functional differentiation of Rbridges, but engineering differences to
optimize between "core" Rbridges and "access" Rbridges. Right?  
 
Regards
Guillermo Iba?ez

-----Mensaje original-----
De: rbridge-bounces at postel.org [mailto:rbridge-bounces at postel.org] En nombre
de Joe Touch
Enviado el: domingo, 01 de mayo de 2005 5:27
Para: Developing a hybrid router/bridge.
Asunto: Re: [rbridge] Max Network size

> in TRILL? May be it was already stated somewhere, I am not aware of it.

There is no limit of design; it is based on the capability of edge RBridges
to handle encapsulation tables, as well as of interior RBridges to have
scalable routing.

Joe

---

From: touch at ISI.EDU (Joe Touch)
Date: Wed, 04 May 2005 08:54:46 -0700

> More on maximum network size.

As a prelude, YES - lots of engineering issues...

> with tables of that size. OK?

Ingresses need to have enough information to encapsulate based on
destination host MAC address; that can be accomplished two ways:
	- full tables carried at each ingress
		which would be hard to compress, but might
		be hashable
	- internal bootstrap
		1) internal 'ARP' when a previously unknown
		MAC arrives at the ingress, resolving to a cached
		entry

		2) implied 'ARP' by broadcasting the packet
		with the successful egress back-propagating
		the entry later

I suspect a combination may be required, since there will be packets
whose MAC may not be knowable at the egress (silently attached), so we
may have to flood the network to even find the right egress to use. This
is no different from what bridges do, though...

> aggregation. I did not follow the routing discussiong so may be I missed

Yes, we need a routing protocol that can scale. Note, however, that
we're forwarding internally ONLY on the destination rbridge address, NOT
the original packet's MAC address. So the number of entries is the
number of egresses, NOT the number of end hosts.

The tradeoff is in the encapsulation table size (first item above);
_that_ table is O(# attached hosts), whereas the routing is O(# egresses).

> functional differentiation between these two types ?

Egress nodes need encapsulation tables and forwarding tables; interior
nodes just need forwarding tables and could be cheaper.

> In this case handled it

A edge bridge can easily function as interior; an interior might not
function as an edge. This may favor a single integrated design. The
behavior is configured on a per-MAC basis (traffic coming from another
rbridge in your campus is internal; all other traffic is external). This
should be very easy to automate, IMO (do an echo algorithm to find all
connected rbridges, declare that one campus unless manually configured
not to, and use those MACs as internal traffic).

The distinction based on device is better for describing the system, but
in practice I would expect it would be per-MAC, not per-box.

I hope this all helps - I can add it to the doc.

Joe

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 254 bytes
Desc: OpenPGP digital signature
Url : http://www.postel.org/pipermail/rbridge/attachments/20050504/36e07882/signature.bin

---

From: gibanez at it.uc3m.es (Guillermo Ibáñez)
Date: Fri, 06 May 2005 10:33:01 +0200

Joe Touch wrote:

>------------------------------------------------------------------------
>
I agree with your view, except about ARP. 
Is there any estimation on the ARP load expected on Rbridges as ARP 
proxies and hosts in general (ARPs unsolved by proxies)?
I wonder whether the Rbridges are the most suited devices to handle many 
ARP requests. For big networks like this it might be worth to consider 
the use of separate ARP servers distributed over the subnetwork instead 
of ARP proxies at Rbridges.
Regards
Guillermo

---

From: touch at ISI.EDU (Joe Touch)
Date: Fri, 06 May 2005 07:39:27 -0700

Guillermo Ib??ez wrote:
...
> of ARP proxies at Rbridges.

I am anticipating that RBridges should handle ARPs via broadcast as a
default; we're looking into proxy-ARP based on knowledge of ingress
locations, to reduce ARP load. That solution would need to be fault
tolerant to loss of the proxy mechanism, whether distributed or at a server.

Joe

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 254 bytes
Desc: OpenPGP digital signature
Url : http://www.postel.org/pipermail/rbridge/attachments/20050506/a70e8cf7/signature.bin

---

From: gibanez at it.uc3m.es (Guillermo Ibáñez)
Date: Fri, 06 May 2005 17:27:06 +0200

Guillermo Ib??ez wrote:

>tolerant to loss of the proxy mechanism, whether distributed or at a server.
Right. Default must always be ARP broadcast.  I understand that in this 
case the frame is not encapsulated,  just forwarded by Rbridge.
 ARP load is somewhat reduced in the core  by diffusing ARP to Rbridges 
via a specific multicast address iso broadcast address . But still the 
cost of local ARPs issued by each Rbridge at the ends may be significative.
I wonder if an ARP server/registrar approach can be foreseen as an 
alternative or complementary strategy.  The Designated Rbridge registers 
each host, when an ARP is received, at a (distributed) ARP server. This 
can help to enforce security (like preventing MAC spoofing) and  also 
ensure ARP resolution in one step without broadcast. The point is to 
distribute the load of ARP registry and queries between multiple ARP 
servers. This may be based on IP hashing.
Regards
Guillermo

---

From: touch at ISI.EDU (Joe Touch)
Date: Fri, 06 May 2005 08:43:29 -0700

> case the frame is not encapsulated,  just forwarded by Rbridge.

All packets arriving at an egress are always encapsulated, including
ARPs. The only non-encapsulated packets inside an RBridge campus would
be RBridge control traffic, e.g., routing protocols and encapsulation
table setup.

> cost of local ARPs issued by each Rbridge at the ends may be significative.

Sure - ARPs not only flood the RBridge campus, but also the stubs that
attach. But that's a property of all L2 networks; broadcasts broadcast.

> each host, when an ARP is received, at a (distributed) ARP server.

When an ARP reply is received, that can be done. But the first ARP to an
otherwise unknown host, which has silently attached to a stub at an
RBridge ingress, is unknown. The only way to find it is to flood.

> This 
> ensure ARP resolution in one step without broadcast. 

Correct the above if not correct, but assuming that there is no way to
secure ARP that doesn't modify ARP too.

> The point is to 

Sure, hashing will direct you to the right cache. But how does that
cache know what to reply? It can't unless IT floods; that's the catch-22.

Joe

---

From: gibanez at it.uc3m.es (Guillermo Ibáñez)
Date: Fri, 06 May 2005 18:12:23 +0200

Guillermo Ib??ez wrote:

Joe Touch wrote:

>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>
>
>Guillermo Ib??ez wrote:
>  
>
>>Guillermo Ib??ez wrote:
>>
>>Joe Touch wrote:
>>
>>
>>    
>>
>>>Guillermo Ib??ez wrote:
>>>...
>>>
>>>
>>>
>>>      
>>>
True. But this is the only case.

>secure ARP that doesn't modify ARP too.
ARP query would be performed by the Designated Router (encapsulated 
query directed to the ARP server). I am not expert, but I guess the 
server can autenticate the DRs. I agree that a host may spoof  its MAC 
but security measures are possible both at the ARP server (the spoofed 
host is registered in same server) and at the DR (attacks and  behaviour 
will likely concentrate on a certain port of  DR)   

>cache know what to reply? It can't unless IT floods; that's the catch-22.
The cach? knows the content because it is the unique both server and 
registrar for the IP addresses set. Prior to that query, upon first ARP 
issued  the host was registered by the DR at that cach?, based on its 
hash(IP) . An ARP cache query from host would produce from DR two 
packets : a registration of originating host at ARP registrar and an ARP 
query of destination host at ARP server. 
Regards
Guillermo

>-----BEGIN PGP SIGNATURE-----
>Version: GnuPG v1.2.4 (MingW32)
>Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org
>
>iD8DBQFCe5ChE5f5cImnZrsRAhYCAKCTK+bm/VtZ/7yGtU4Qi12pEC8B0QCfSJv0
>Iv1gD4eJ7OyDsvTkRCB/ZXg=
>=DzCO
>-----END PGP SIGNATURE-----

---

From: touch at ISI.EDU (Joe Touch)
Date: Fri, 06 May 2005 09:43:53 -0700

> True. But this is the only case.

The problem is that it's the defining case. All others can, as you
observe, be optimized with a variety of engineering solutions. IMO, none
are all that interesting - ARP already caches at the endhost anyway.

> query directed to the ARP server).

The ARPs are originated outside the campus; the two options are to
encapsulate the ARP and broadcast it or to encapsulate it and send it to
an internal cache (the ARP server). Neither is secure, since they are
triggered by external, unauthenticated ARPs.

> I am not expert, but I guess the 
> server can autenticate the DRs.

Sure - but that only authenticates the internal cache; there's no way to
authenticate the initial broadcast whose reply is used to populate the
cache.

> I agree that a host may spoof its MAC 

Why bother? As above, we already need to support broadcast ARP to
bootstrap. Besides, securing the internal protocol complicates the
deployment. There's little utility to securing the ARP cache
communication this way, IMO, unless you've already secured internal
control communication (e.g., routing) for other reasons.

> hash(IP). 

ARP may announce the location of the ARP sender, but doesn't announce
the location of the ARP reply. Both need to be snooped to load the
cache. The trouble is the first ARP _to_ any new IP address must always
be broadcast; by definition, it won't be in the cache.

> An ARP cache query from host would produce from DR two 

What does the ARP server do with a request of the destination if it
hasn't seen any communication from that host before?

Joe

---

From: gibanez at it.uc3m.es (Guillermo Ibáñez)
Date: Sat, 07 May 2005 11:20:08 +0200

Guiillermo Iba?ez wrote:

>are all that interesting - ARP already caches at the endhost anyway.
Yes.  But till then you avoid in many cases to do flood.

>triggered by external, unauthenticated ARPs.
I do not understand this "outside" origination of ARPs.  My 
understanding is that ARPs are sent by local hosts or routers.

>authenticate the initial broadcast whose reply is used to populate the
But the cach?, as a centralized point, can detect duplicated addresses 
and other abnormal behaviour....

>hasn't seen any communication from that host before?
Flooding, of course. Flooding is unavoidable at the end, but must be 
kept to a minimum for big networks to not use up hosts processing power.
We can think of new mechanisms for cach?s (ARP servers), as they 
implement a centralized function for a set of IP addresses, to track 
hosts mobility.
What I would like to see is a comparison between  the cach?s 
(distributed server/register) approach  with the current ARP proxy 
approach considering all aspects: engineering, security, broadcast 
volume, etc
Guillermo

>Joe.
>iD8DBQFCe57JE5f5cImnZrsRApfnAKCiYVfTjaHuLK4wnf+ckpsU8E0b5QCg+jLm
>BFwBjuirgR1GlaSbFy0044Q=
>=dWU9

---

From: touch at ISI.EDU (Joe Touch)
Date: Mon, 09 May 2005 15:30:22 -0700

> Yes.  But till then you avoid in many cases to do flood.

I'm not convinced about the "many" part; as I mentioned, the endsystems
cache. There are also snooping issues - ARP replies, if broadcast, can
preload these caches. By looking for ways to avoid flooding, we avoid
some of the optimizations already designed into ARP.

That said, this is where a good study would help; it's premature to do
anything except provide basic functionality (broadcast ARP) and mention
that optimizations MAY be useful, IMO.

> understanding is that ARPs are sent by local hosts or routers.

I've been speaking of ARPs as originating outside the RBridge, from
hosts connected to egress RBridges. Those ARPs are not performed by the
Designated Router; they just arrive at the egress.

The discussion of Designated Routers in the I-D is an optimization; I've
been speaking of the base case. Base case ARPs cannot be authenticated.

> and other abnormal behaviour....

Sure - but at what cost? Central point of failure? That's not an
acceptable trade-off, especially to enforce ARP properties that are
generally not enforced on conventional Ethernet LANs.

...
> kept to a minimum for big networks to not use up hosts processing power.

Agreed. But L2 semantics include flooding; ARP isn't the only use of
broadcast.

> implement a centralized function for a set of IP addresses, to track 

What you're proposing is to turn an RBridge into an NBMA (non-broadcast,
multiaccess network), and to push ARP into a server, ala ATM LAN
Emulation (LANE). I see that as a step backwards, esp. because, as noted
above, ARP isn't the only use of broadcast.

> approach considering all aspects: engineering, security, broadcast 

See LANE and other NBMA literature. There are benefits, but there are
also substantial robustness issues. Note that we can do NOTHING to avoid
flooding when speaking to systems that haven't spoken yet - we won't
find them at all unless the ARP emerges at the right egress link (L2
network), and there's no way to know a-priori which one that will be.

If we include a cache, we run the risk of having the cache semantics of
the endsystem collide with that of the network cache. Overall, I'd say
let's build an RBridge with broadcast and let's show that the load is a
big enough problem to deal with it first.

Joe

---

From: gibanez at it.uc3m.es (Guillermo Ibáñez)
Date: Tue, 10 May 2005 10:49:27 +0200

Guillermo Ib??ez wrote:

>that optimizations MAY be useful, IMO.
We must be aware of the high cost of ARP processing cost in hosts of a 
big network under the basic broadcast ARP approach.

>generally not enforced on conventional Ethernet LANs.
ARP servers can support replication. The point is whether it is an 
objective to improve ARP security or the current situation is acceptable 
in the foreseable big networks.

>Agreed. But L2 semantics include flooding; ARP isn't the only use of
Rigth. But I do not think much flooding will be received by hosts due to 
unknown host destination. The host response triggers the MAC learning.

>above, ARP isn't the only use of broadcast.
May be I am misunderstood. I do not exclude broadcast, only broadcast 
for ARP.

>network), and there's no way to know a-priori which one that will be.
I will look at it, but I do not think it is the same thing.

>big enough problem to deal with it first.
Some measurements on ARP load are available at:   
http://100x100network.org/papers/myers-hotnets2004.pdf
Guillermo

>iD8DBQFCf+R+E5f5cImnZrsRAspuAKDsoKdE7mjnWVafIlgtfda2JXdLfwCgoHcn
>oYZ1MjPaGdRLSmKtUQnlm/U=
>=d26+

---

From: touch at ISI.EDU (Joe Touch)
Date: Tue, 10 May 2005 11:49:56 -0700

Guillermo Ib??ez wrote:
...
> big network under the basic broadcast ARP approach.

It's a question of what BIG means. First, broadcast is the backup
anyway. Second, caching at endhosts and snooping of broadcast responses
reduces request load.

Finally, I may be in the minority here, but this has nothing to do with
RBridge. I don't see the primary benefit of RBridge to support scaling
to millions of nodes on an L2 net, nor do I see it as an opportunity to
rewrite how ARP is implemented.

Knwon optimizations can always be applied, but the core of its operation
in this regard is to support conventional broadcast services. ARP is no
different than any other broadcast service in that regard.

...
> in the foreseable big networks.

RBridges are designed to replace bridges to improve routing, not to
improve ARP security - the latter of which needs its own solution. Given
that solution, it can certainly be supported in an RBridge, but I don't
see why we would consider RBridges to uniqely enable or require it.

...
...
> I will look at it, but I do not think it is the same thing.

Both use the same solution to avoiding broadcast - a centralized ARP server.

>> http://100x100network.org/papers/myers-hotnets2004.pdf

That paper has some interesting positions, but that would be open
research. When a solution has been developed and tested, it might be
considered for standardization. Since this is not an IRTF effort,
though, that would be future work, IMO.

Joe

---

From: alper.yegin at samsung.com (Alper Yegin)
Date: Tue, 10 May 2005 17:17:11 -0700

> see why we would consider RBridges to uniqely enable or require it.

I agree. Use of an ARP server may be an additional optimization which
can be built on top of Rbridged network, much like other types of
networks. But I think we can and shall keep this separate unless there
is some specific Rbridge feature that requires presence of ARP servers
(which I can't see....)

Alper

---

From: gibanez at it.uc3m.es (Guillermo Ibáñez)
Date: Wed, 11 May 2005 15:37:08 +0200

Guillermo Iba?ez wrote:

>anyway. Second, caching at endhosts and snooping of broadcast responses
I would consider big  a network (single broadcast domain) with  25.000 
-100.000 hosts. But this could fall short.
As stated in the paper,  the ARP cache policy in hosts (Windows) is as 
follows:  unused entries in last two minutes expire, the refreshed ones 
are allowed a maximum of 10 minutes, then a new  ARP request will be 
sent. Measurements, (see below at the end of mail) are based on the 
current caching at endhosts, so the caching effect  is already included. 
Regarding snooping, I agree that snooping of broadcast responses at 
proxy-ARPs will reduce the load.

>different than any other broadcast service in that regard.
Conventional broadcast services must be supported. The difference of ARP 
vs other broadcast services I see is the load imposed to hosts in big 
networks.

>see why we would consider RBridges to uniqely enable or require it.
I agree ARP is a side  issue for Rbridges, but as Rbridges usage may 
increase sharply the broadcast domain size, they are indirectly the 
cause of the load to hosts, so it can not be ignored.

>Both use the same solution to avoiding broadcast - a centralized ARP server.
Not exactly one centralized server. There would be  multiple servers 
with distributed load (by IP hashing), each of partial servers may  have 
replication. An specific protocol  would be required for it. We can 
think also on Distributed Hash Tables but performance does not seem 
adequate.

>though, that would be future work, IMO.
I did not refer to this paper to support the solution proposed, but only 
as reference for the ARP measurements provided. Results were:  89 ARPs 
per second on average in a 2.456 hosts network, with peak load of 1150 
ARPs/second. For a network with 25.000 hosts (ten times size), this 
means  900 ARPs /second on average and 11.500 ARPs packets (peak) to 
process on every  host.

Guillermo

>iD8DBQFCgQJUE5f5cImnZrsRAnCTAKD5v0cnZuarZZrNnn673nsNYQzZzACcCMz1
>nDUUaT/jinVhlwJxYltXwq4=
>=G783

---

From: touch at ISI.EDU (Joe Touch)
Date: Wed, 11 May 2005 15:44:17 -0700

Guillermo Ib??ez wrote:
...
>  would consider big  a network (single broadcast domain) with  25.000

We agree that this is a problem for a sufficiently large network. As
I've already noted, there are two things RBridges are not uniquely
trying to solve:
	a) increased size of L2 subnets
	b) insecurity of ARP

Solutions to either should work fine in an RBridge scenario, but are not
part of the prerequisites of the RBridge architecture.

Although an RBridge may encourage large subnets - larger than are
currently typical - so do large L2 switches. There are solutions in that
space to reduce broadcasts (IGMP snooping, proxy ARP, etc.) that might
apply just fine here, but aren't worth (IMO) mentioning explicitly.

As you noted, there are plenty of challenges with proxy ARP - hashing,
load balancing, fault tolerance, etc. But all those solutions will
benefit all L2 subnet systems, and are not specific to RBridges.

...
...
> means  900 ARPs /second on average and 11.500 ARPs packets (peak) to 

Just because there are 10x as many hosts doesn't mean there will be 10x
as many ARPs, notably because there won't typically be 10x as many
routers to the rest of the Internet.

There are also other economies of scale possible in an RBridge -
broadcasts can be more efficient than in a spanning tree because there
can be multiple broadcast trees inside the RBridge campus.

Overall, as said before, I don't think this is an issue specific to
RBridges. Does anyone else??

Joe

---

From: gibanez at it.uc3m.es (Guillermo Ibáñez)
Date: Thu, 12 May 2005 10:02:38 +0200

Guillermo Ib??ez wrote:

>apply just fine here, but aren't worth (IMO) mentioning explicitly.
Agreed, no explicit recommendation of any procedure to reduce broadcasts.

>>>>http://100x100network.org/papers/myers-hotnets2004.pdf
Myers extrapolations in the paper are higher ( I do not know his 
rationale) than mine.

>can be multiple broadcast trees inside the RBridge campus.
Sorry, I do not catch this argument. Multiple spanning trees are not 
exclusive of Rbridges, any bridge can use them (with MSTP or future 
simplifications or evolutions of it).

>iD8DBQFCgorBE5f5cImnZrsRAkaUAKDZQjpYaUGIpK/MvUJ3JSTTKkRwZACffAy3
>+PD5qUt+CspyFRTAjks1XVg=
>=ciB6

---

From: touch at ISI.EDU (Joe Touch)
Date: Thu, 12 May 2005 13:00:44 -0700

Guillermo Ib??ez wrote:
...
> simplifications or evolutions of it).

We already note the need to use multiple spanning trees in RBridge to
match the way routing supports multiple paths, as well as for different
VLANs.

I.e., the need for multiple spanning trees is already assumed in
RBridges for other reasons. Agreed, it's not unique to RBridges, but
it's already there at least.

Joe