Re: [lwip-devel] more about SO_REUSE and UDP

[lukem . lwip]

On Fri, 26 Mar 2004, Leon Woestenberg wrote:

> Hello Luke,
>
> Luke wrote:
> > On Thu, 25 Mar 2004, Leon Woestenberg wrote:
> >
> >>For optimal lookup behaviour (on heavy traffic networks) the alternative
> >>is to have dummy PCB's in the UDP/TCP list, that have a new PCB_DROP
> >>flag set.
> >>
> >>This way, the PCB's *can* be sorted by most-targetted destination port
> >>to least-targetted port, dynamically with reference count and the
> >>overall lookup time is reduced to a minimum. Increased overhead due to
> >>sorting though.
> >
> >
> > We found that traversing the PCB list was extremely expensive when we had
> > a system with lots of simultaneous connections. I fixed it by first
>  >
> In the order of how many connections are we talking? tens, thousands?

The number of connections need not be very large before you start to
notice a performance impact - traversing a linked-list of 50 nodes would
probably add significantly to the cache impact of the incoming data path.
For a medium scale web servers you may need to handle 500 simultaneous
connections, at which point the overhead is clearly excessive.

> > abstracting pcb lists into a separate, well defined interface, and then
> > implemented a hashtable to do fast PCB lookups. This approach would work
> > well for UDP as well, and is in my opinion a more thorough solution to the
> > linear searches currently used for handling PCB lists.
> >
> How would your hash implementation handle the case where 95% of the
> inbound (broadcast) traffic is on unlistened ports?

lwIP keeps three separate lists for TCP connections, one for each
of TCP's active, time-wait and listen states. For every incoming packet,
each of these lists must me traversed before the packet may be discarded.

For UDP this would be simpler because there is only one list which needs
to be checked.

In either case, looking up the hash table should be much faster for all
but the smallest number of pcbs. And even in the case of a very small
number of connections the overhead should be negligible, assuming
reasonable constants are chosen.

> What would the overhead be if lwIP has say, typically five connections open?

The CPU overhead of the hashtable is very small - generating the hash key
can be done very quickly - we are hashing integers which is very easy.

The memory overhead should also be small - number of hashtable entries
should be around 4x the number of expected entries. In your 5 connection
case we have an overhead of 20xsizeof(mem_ptr_t) bytes.

In the case that multiple pcb's hash to the same bucket I use a
linked-list to resolve conflicts, which gives performance no worse than
the current implementation if the number of hash buckets is 1.

--
Luke