Routing – What happens when the ARP cache overflows

In at least one implementation there is a hard limit on the capacity of the ARP table. What happens when the ARP cache is full and a packet is offered with a destination (or next-hop) that isn't cached? What happens under the hood, and what is the effect on the service quality?

For example, Brocade NetIron XMR and Brocade MLX routers have a configurable ip-arp system maximum. The default value in that case is 8192; the size of a /19 subnet. It is not clear from the documentation whether this is per interface or for the whole router, but for the purpose of this question, we can assume it is per interface.

Few networkers would configure a /19 subnet on an interface on purpose, but that isn't what happened. We were migrating a core router from a Cisco model to a Brocade. One of the many differences between Cisco and Brocade is that Cisco accepts static routes that are defined with both an outbound interface and a next-hop address, but Brocade insists on one or the other. We dropped the next-hop address and kept the interface. Later, we learned the error of our ways, and changed from interface to next-hop address, but everything seemed to be working initially.

+----+ iface0    +----+
| R1 |-----------| R2 |---> (10.1.0.0/16 this way)
+----+.1       .2+----+
      10.0.0.0/30

Before the migration, R1 was a Cisco, and had the following route.

ip route 10.1.0.0 255.255.0.0 iface0 10.0.0.2

After the migration, R1 was a Brocade, and had the following route.

ip route 10.1.0.0 255.255.0.0 iface0

R2 is a Cisco router, and Cisco routers perform proxy ARP by default. This is the (mis-)configuration in production that set the stage for what turned out to be an ARP cache overflow.

1. R1 receives a packet destined for the 10.1.0.0/16 network.
2. On the basis of the static interface route, R1 ARPs for the destination on iface0
3. R2 recognizes that it can reach the destination, and responds to the ARP with its own MAC.
4. R1 caches the ARP result that combines an IP in a remote network with the MAC of R2.

This happens for every distinct destination in 10.1.0.0/16. Consequently, even though the /16 is properly sub-netted beyond R2, and there are only two nodes on the link adjoining R1 and R2, R1 suffers ARP cache overload because it induces R2 to behave as if all 65k addresses are directly connected.

The reason I'm asking this question is because I hope it will help me make sense of the network service trouble reports (days later) that led us, eventually, to the overflowing ARP cache. In the spirit of the StackExchange model, I tried to distill that to what I believe is a crisp, specific question that can be answered objectively.

EDIT 1 To be clear, I am asking about part of the glue layer between data link (layer 2) and network (layer 3), not the MAC forwarding table within the data link layer. A host or router builds the former to map IP addresses to MAC addresses, while a switch builds the latter to map MAC addresses to ports.

EDIT 2 While I appreciate the effort to which responders have gone to explain why some implementations are not subject to ARP cache overflow, I feel that it is important for this question to address those that are. The question is "what happens when", not "is vendor X susceptible to". I've done my part now by describing a concrete example.

EDIT 3 Another question this is not is "how do I prevent the ARP cache from overflowing?"