Subject: [rbridge] Back to ND/ARP optimization

From: Radia.Perlman at sun.com ([email-masked])
Date: Thu, 03 May 2007 07:38:16 -0700

Looking back on old emails, there are some people who'd like to get rid of ND/ARP optimization,
and some people pointing out that optimizing ND might not be so simple (for instance, SEND).

I'd be OK with removing it from the spec, or certainly making it something other than a MUST, like
perhaps MAY.

But there were fields in the per-VLAN instance of IS-IS to facilitate this, namely the (L3 address, L2 address).
An RBridge *could* learn this information locally, but wouldn't learn it as much. In other words, if S behind R1 sends
an ARP request for target T behind R2, the response will be unicast to S, so none of the other RBridges will
learn where T is. Only R1. So R1 could in the future do a proxy ARP. But if R2 announced (T, t) in its per-VLAN
instance of IS-IS, then all the RBridges could learn (T,t). Furthermore, if T has registered with R2 via some
L2 enrollment protoocol, then R2 can immediately know if T is no longer there and alert everyone.

Does anyone have a handle on how much traffic is caused by ARP/ND?

We could certainly do a compromise, like that each RBridge R1 SHOULD throttle ARP/ND queries, and
not reflood a query for T if there has been more than k (some parameter) queries for T in the last n seconds.

But that doesn't even have to be in the spec.

It would be nice to know in operational networks how much traffic is caused by ARP/ND queries, and how
worried people are about a malicious endnode DOS'ing by sending lots of queries. (but it could just as easily
send other types of broadcast/multicast traffic so maybe it's not worth worrying about optimization ARP/ND because
of malicious nodes).

Radia

---

From: sgai at nuovasystems.com (Silvano Gai)
Date: Thu, 3 May 2007 13:55:52 -0700

Radia,

> -----Original Message-----
> From: rbridge-bounces at postel.org [mailto:rbridge-bounces at postel.org]
On
> Behalf Of Radia.Perlman at sun.com
> Sent: Thursday, May 03, 2007 7:38 AM
> To: rbridge at postel.org
> Subject: [rbridge] Back to ND/ARP optimization
> 
> Looking back on old emails, there are some people who'd like to get
rid of
> ND/ARP optimization,
> I'd be OK with removing it from the spec, or certainly making it
something
> other than a MUST, like
> perhaps MAY.
> 
> But there were fields in the per-VLAN instance of IS-IS to facilitate
> this, namely the (L3 address, L2 address).
> An RBridge *could* learn this information locally, but wouldn't learn
it
> as much. In other words, if S behind R1 sends
> an ARP request for target T behind R2, the response will be unicast to
S,
> so none of the other RBridges will
> learn where T is. Only R1. So R1 could in the future do a proxy ARP.
But
> if R2 announced (T, t) in its per-VLAN
> instance of IS-IS, then all the RBridges could learn (T,t).
Furthermore,
> if T has registered with R2 via some
> L2 enrollment protoocol, then R2 can immediately know if T is no
longer
> there and alert everyone.
> 

With an ARP cache of 30 minutes, typical in hosts today, even with a 100
K hosts in a VLAN we get at most 55 ARP seconds. Since not all the hosts
talk with each other, it is more typically like 5 ARP/sec.

BASICALLY NOTHING.

> not reflood a query for T if there has been more than k (some
parameter)
> queries for T in the last n seconds.
> 

Let's get read completely of ARP/ND proxy: these are product not
standard features.

Typically products will be multilayer and will have sophisticated ARP/ND
management scheme. Standardizing it in TRILL does not make sense.

-- Silvano

> worried people are about a malicious endnode DOS'ing by sending lots
of
> queries. (but it could just as easily
> send other types of broadcast/multicast traffic so maybe it's not
worth
> worrying about optimization ARP/ND because
> of malicious nodes).
> 
> Radia
> 
> 
> _______________________________________________
> rbridge mailing list
> rbridge at postel.org
> http://mailman.postel.org/mailman/listinfo/rbridge

---

From: arien.vijn at ams-ix.net (Arien Vijn)
Date: Fri, 4 May 2007 19:04:18 +0200

Hi,

On May 3, 2007, at 10:55 PM, Silvano Gai wrote:

[...]

> talk with each other, it is more typically like 5 ARP/sec.

Well... that might be the case if all your hosts are actually  
answering. But query rates are pretty much determined by queries for  
unused addresses. In other words by the query rates hosts (routers)  
can achieve for addresses that are not in their caches.

For what its worth. I am involved in a real network with 400+ BGP  
routers in one broadcast domain (/23 IPv4 subnet). The average rate  
is little over 13 queries/second. That is with ARP mitigation and  
peak rates are much higher.

-- Arien

---

From: sgai at nuovasystems.com (Silvano Gai)
Date: Fri, 4 May 2007 12:00:39 -0700

Arien

Thanks for the real world data, which proves that ARP/ND proxy must not
be implemented on RBridges.

In fact, since the queries toward unused addresses are dominant, the
ARP/ND cache will almost always miss and the RBridge CPU will be busy
trying to remotely resolve queries that will never complete.

-- Silvano

> From: Arien Vijn [mailto:arien.vijn at ams-ix.net]
> Sent: Friday, May 04, 2007 10:04 AM
> To: Silvano Gai
> Cc: Arien Vijn; Radia.Perlman at sun.com; rbridge at postel.org
> Subject: Re: [rbridge] Back to ND/ARP optimization
> 
> Hi,
>

---

From: Radia.Perlman at sun.com (Radia Perlman)
Date: Sat, 05 May 2007 15:10:35 -0700

Actually, I'm not sure that's the conclusion that Arien was making (that 
ARP/ND
optimization is not worth it), especially with the comment "peak rates 
much higher".

So Arien...was that actually your conclusion?

I think that ARP/ND optimization could be added in the future as an 
option, or
even that an implementation can do something about it without having the 
spec
saying anything about it. Which would argue for not needing it in the 
spec now.

But just want to verify what Arien's conclusion is from the data 
presented...

Radia

---

From: sgai at nuovasystems.com (Silvano Gai)
Date: Sun, 6 May 2007 09:30:34 -0700

Radia,

I agree that Arien didn't make a conclusion, and I am interested in
Arien opinion.

I read about the bursts.

I suppose that even during "the high peak rate" most of the ARPs are for
unknown destinations and this does not change my conclusions.

-- Silvano

> From: Radia Perlman [mailto:Radia.Perlman at sun.com]
> Sent: Saturday, May 05, 2007 3:11 PM
> To: Silvano Gai
> Cc: Arien Vijn; rbridge at postel.org

---

From: Donald.Eastlake at motorola.com (Eastlake III Donald-LDE008)
Date: Sun, 6 May 2007 17:30:21 -0400

Silvano,

I don't understand what these Rbridge CPUs will be doing. If an Rbridge
receives a native ARP broadcast frame for an unknown IP address it would
just learn the source IP->MAC mapping and then flood the ARP broadcast.

Donald

-----Original Message-----
From: rbridge-bounces at postel.org [mailto:rbridge-bounces at postel.org] On
Behalf Of Silvano Gai
Sent: Friday, May 04, 2007 3:01 PM
To: Arien Vijn
Cc: rbridge at postel.org; Radia.Perlman at sun.com
Subject: Re: [rbridge] Back to ND/ARP optimization

Arien

-- Silvano

---

From: sgai at nuovasystems.com (Silvano Gai)
Date: Sun, 6 May 2007 17:35:37 -0700

Donald,

To provide a precise answer we need to consider which of the three
schemes described in section 3.12 of 
http://www.ietf.org/internet-drafts/draft-ietf-trill-rbridge-protocol-03
.txt
the RBridge will implement.

The draft refers generically to "Some mix of these strategies".

Lacking this information, let's assume the strategy you mention.
The flood cannot be done in HW. In fact it is mandatory to not resend
the ARP on the port it was received to avoid frame duplication.

The flood must be implemented in SW has n-1 port transmissions; where n
is the number of ports.

Therefore, the CPU of a 256 port RBridge:
- in absence of ARP/ND proxy receives 1 ARP (and the HW does the correct
replication)
- with ARP/ND proxy it receives 1 ARP (and the HW does nothing)and sends
out 255 ARP messages. Huge overhead

-- Silvano

> From: Eastlake III Donald-LDE008 [mailto:Donald.Eastlake at motorola.com]
> Sent: Sunday, May 06, 2007 2:30 PM
> To: Silvano Gai
> Cc: rbridge at postel.org
> Subject: RE: [rbridge] Back to ND/ARP optimization
> 
> Silvano,
> 
On

---

From: Donald.Eastlake at motorola.com (Eastlake III Donald-LDE008)
Date: Sun, 6 May 2007 23:40:16 -0400

Silvano,

Sorry, I still don't understand this.

What does an Rbridge do if it receives a native broadcast frame with an
unknown Ethertype (unknown in the sense that it is not in any special
table or comparison implemented in the Rbridge)? If the Rbridge isn't
the DR for the port it received it on, it drops it. If it is the DR, it
forwards it in native form out every other port for which it is the DR
and which is in the same VLAN. It also encapsulates it and sends it off
on a distribution tree pruned by VLAN.

What does an Rbridge do if it receives a native broadcast ARP frame? If
it isn't the DR for the port it receive it on, it drops it. Otherwise,
it learns the IP to MAC mapping for the sender fields in the ARP frame
and it tries to find the target IP address in its database of IP to MAP
mappings. If it can't find an entry for the target IP address, it then
proceeds as in the paragraph above to flood it.

In other words, for an unknown target IP address, processing of a
broadcast ARP frame is exactly the same as for an unknown Ethertype
except for the learning step and the table look up attempt step. Why
can't this be done in hardware? Even if I assume the learning and table
look up happen in software, if the IP address isn't found, why couldn't
the software just re-inject the frame into the hardware as if it had
come in on its original receipt port with a flag saying "treat like an
unknown Ethertype"?

Thanks,
Donald

-----Original Message-----
From: Silvano Gai [mailto:sgai at nuovasystems.com] 
Sent: Sunday, May 06, 2007 8:36 PM
To: Eastlake III Donald-LDE008
Cc: rbridge at postel.org
Subject: RE: [rbridge] Back to ND/ARP optimization

Donald,

-- Silvano

On

---

From: arien.vijn at ams-ix.net (Arien Vijn)
Date: Mon, 7 May 2007 16:14:05 +0200

Hello Radia,

On May 3, 2007, at 4:38 PM, Radia.Perlman at sun.com wrote:

> rid of ND/ARP optimization,
> something other than a MUST, like
> perhaps MAY.
>
> But there were fields in the per-VLAN instance of IS-IS to  
> facilitate this, namely the (L3 address, L2 address).
> An RBridge *could* learn this information locally, but wouldn't  
> learn it as much. In other words, if S behind R1 sends
> learn where T is. Only R1. So R1 could in the future do a proxy  
> ARP. But if R2 announced (T, t) in its per-VLAN
> Furthermore, if T has registered with R2 via some
> longer there and alert everyone.

This mechanism optimises successful quires, but I think that those  
are not the bulk of the ARP/ND broadcasts/multicasts.

> parameter) queries for T in the last n seconds.

This is similar to the way we do ARP mitigation. We made a friendly  
ARP spoofer that starts spoofing replies when the queries for T reach  
a threshold and after it verified that T is indeed unreachable. It  
stops spoofing for T as soon as it detects any sign of life from T.  
It works like charm as long as ARP caches and associated hard and  
software resources can deal with all these resolved addresses.

So I think that this approach would work. It may be implemented as  
feature in (R)bridges. But I think that it is better address it at  
the source and add a (optional) back-off mechanism in ARP/ND  
implementations.

> But that doesn't even have to be in the spec.

True.

> worried people are about a malicious endnode DOS'ing by sending  
> lots of queries. (but it could just as easily
> worth worrying about optimization ARP/ND because
> of malicious nodes).

Run a hacker conference network and you'll know that unfriendly ARP  
spoofing is reality. Would you choose to include ARP/ND optimizations  
then you should take that into account too.

Considering the possible consequences of ARP/ND optimizations versus  
what it would gain, I would suggest not to put that in the specs from  
the start. RBridges are probably difficult enough to engineer.  
Besides, I see no reason why this could not be added later on.

Cheers, Arien

--
Arien Vijn
Amsterdam Internet Exchange
http://www.ams-ix.net

---

From: arien.vijn at ams-ix.net (Arien Vijn)
Date: Mon, 7 May 2007 16:22:40 +0200

Hello Radia,

On May 6, 2007, at 12:10 AM, Radia Perlman wrote:

> Actually, I'm not sure that's the conclusion that Arien was making  
> (that ARP/ND
> optimization is not worth it), especially with the comment "peak  
> rates much higher".
>

Eh... I just posted an observation that differed from the theory :)

> even that an implementation can do something about it without  
> having the spec
> saying anything about it. Which would argue for not needing it in  
> the spec now.

I agree. Please see my reply on one of your other postings on this list.

> But just want to verify what Arien's conclusion is from the data  

My conclusion would be that you should consider that most queries are  
futile. Because in my observations, successful queries are not the  
bulk of the traffic. Hence I think that there is not much gain in  
optimising those. To me it seems hard to optimise unsuccessful  
queries. Throttling seems the only feasible way.

To give a bit more insight:

	1/ Futile ARP/ND queries are mostly due to scanners. Scanners try  
all addresses in one subnet, causing routers to query over and over  
again.

	2/ Another cause is more specific for the peering LAN I presented.  
Many operators just do not remove BGP sessions for peers that have  
left. Routers will continue to query for the lost peer.

	3/ Some systems do perform far more queries than others. As  
illustration you may want to have a quick look at this presentation  
and note some remarkable differences between vendors:

http://www.ams-ix.net/~arien/TM24-AV-ARP-V01.pdf

	4/ The peak rates I mentioned are due to the fact that the ARP  
mitigation kicks in after a while. Without mitigation, we would see a  
constant high query rate. The first version of this system was  
actually created when we saw that routers could not handle the  
increased query rate during a renumbering action.

Considering the above, I also come to the conclusion that all of this  
is a matter for end hosts (routers mostly).

Kind regards, Arien

---

From: sgai at nuovasystems.com (Silvano Gai)
Date: Mon, 7 May 2007 07:31:14 -0700

Donald,

Let's consider the following RBridge

+---------------------------------------------+
| RBRIDGE                                     |
|                +--------+                   |
|                |  CPU   |                   |
|                +--------+                   |
|                    |                        |
|                +--------+                   |
|                | Fabric |                   |
|                +--------+                   |
|                 |   |   |                   |
+-----------------+---+---+-------------------+
                  |   |   |
                  A   B   C

It has three ports A, B, C, one internal fabric and one CPU.

In the following I will assume that it has won DR election on all the
ports.

WITH NO ARP/ND OPTIMIZATION
===========================
An ARP for Z is received on port A.
The fabric forwards it as a regular Broadcast (i.e. it sends it on all
the ports except the one where it came in). It goes out on B and C (but
not on A) and the CPU gets a copy. The CPU is not Z, so the ARP process
in the CPU discards it.

WITH ARP/ND OPTIMIZATION
========================
An ARP for Z is received on port A.
The fabric MUST be programmed to not forward ARP has a regular
broadcast, but to pass it to the CPU. Therefore a single copy of the ARP
frame is sent to the CPU. The CPU cannot do a simple test, as in the
previous case, but it needs to search Z in a cache (a bit more
expensive). It misses. What happens next is interesting.

You say that you want to "forwards it in native form out every other
port".

We cannot send out of port A, since we received the ARP from port A and
we MUST send it ONLY on B and C. 
Therefore the CPU must:
- not use the classical broadcast mode (otherwise A will get a copy of
the frame);
- remember in SW from which port it received the frame;
- use some fabric specific mechanism to send out the frame only on B and
C.

The mechanism I have seen used in these cases is called "port direct" or
"index direct" in which basically the CPU has a way to send out any kind
of frame on a particular port. 

If this mechanism is used, the CPU needs to replicate in SW the ARP
query.

Other mechanism can be invented and implemented in HW, but I don't think
they are worthwhile. See also the reply of Arien.

I hope it clarifies.

-- Silvano

> Sent: Sunday, May 06, 2007 8:40 PM
> To: Silvano Gai
> > > > With an ARP cache of 30 minutes, typical in hosts today, even
with
> > > > a 100
> > > > K hosts in a VLAN we get at most 55 ARP seconds. Since not all
the
> > > > hosts