Re: [lwip-devel] Fast ARP for a "mini" system

[Jakob Stoklund Olesen]

Małowidzki wrote:
> Because of the specificity of our system, we have an idea of an
> alternative implementation that would trade some memory for processing
> speed. We assume we would handle C-class networks only (and its subnets,
> of course). The basic idea would be using one ARP entry per IP address
> (for a given IP Ethernet interface). Thus, the array would have 256 entries:
>  
> struct etharp_entry arp_table[256];                   // one ARP cache
> per IP Ethernet interface

Małowidzki,

It sounds like what you need is a bigger ARP table and a
faster-than-linear search algorithm.

I have implemented something similar to what you are suggesting using
double hashing. This is not an ARP table, but the forwarding table for
an Ethernet bridge. It is the same principle, though.

An Ethernet bridge maps MAC -> interface. I use a fixed size cache table
with the number of entries a power of 2. To look up a MAC address I
calculate two hash values: an initial entry number, and a stride. My
lookup function is as follows: (C++, sorry)

NetInterface*
NetBridge::lookup(const unsigned char mac[6])
{
    unsigned ent = mac[5] & (kEntries-1);
    const unsigned stride = mac[4] | 1;

    for (unsigned n=0; n<kProbes; n++) {
        if (m_cache[ent].nif && memcmp(m_cache[ent].mac, mac, 6)==0) {
            bridge_stats.hit++;
            return m_cache[ent].nif;
        }
        ent = (ent+stride) & (kEntries-1);
    }

    bridge_stats.miss++;
    return 0;
}

Note: You only do kProbes cache table probes before you give up. I am
using kProbes=5.

If two addresses have the same initial hash value, there is a good
chance that they have different stride values. They collide on the first
probe, but not on the second.

Stride is forced to be odd. Since kEntries is a power of two, they must
be coprime. This is good.

I haven't done all the theoretical calculations, but this data structure
gives good cache coverage and a fast, hard-limited lookup time. You must
be able to handle the table running full. There are only kProbes
possible slots for an address. If they are all full you must decide
which entry must go away. I use a least-recent-used algorithm for that.

In your case, you could use the low N bits of the IP address for the
initial entry, and the other 32-N bits for stride. kEntries=2**N,
kProbes>=1. Higher kProbes means better cache utilisation and lower
performance.

The advantage of this approach is that you can tune memory vs
performance as you please.

/stoklund