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

[Kieran Mansley]

On Wed, 2009-01-14 at 12:45 +0100, Małowidzki, Marek wrote:
> 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];

If you know you're only going to be used in an environment with just
that many IP addresses, and you're happy to use the RAM it needs, then
you're going to struggle to do better than indexing the array by the
last 8 bits of the IP address as I think you are suggesting.  This will
have a very quick O(1) look up time.  It's not suitable as a generic
solution, but might be fine for your application.  To make it more
generic and more robust to larger networks you'd need a hash table or
some other multi-level data structure as Jakob describes which would
retain a relatively fast lookup (but not as fast as your simple array
index) while allowing for more IP addresses on the network than you have
static storage.

Kieran