Re: [PATCH] tcp: efficient port randomisation

On Tue, 2 Nov 2004 09:54:44 +0200
Michael Vittrup Larsen [off-list ref] wrote:

On Monday 01 November 2004 18:20, Stephen Hemminger wrote:

quoted

quoted

* It is probably a good strategy to set 'tcp_rover_next' such that
  the next search is resumed from the previous port found to be free.
  (similar to the old algorithm).  I don't see this in your patch,
  but of course I could have missed it.

It was intentional since it would require holding a lock around the search.
The tradeoff is better SMP performance in the sparsely filled port space
(more typical) vs. better UP performance in the case of a mostly full port
space.

I think a typical scenario is many short-lived (e.g. minutes) TCP connections, 
few long-lived (e.g. hours) connections and an ephemeral port wrap-around 
probably also in hours - at least a long time compared to the life-time of 
the short-lived connections.

But because of the hashing most ports will be scattered all over the port space,
because they come from different hosts.

This would result in a closely spaced 'group' of ports being occupied 
somewhere in the ephemeral port range, and 'tcp_rover_next' would point at 
the uppermost extreme of this group and thus always guarantee a free port on 
first try (collisions will only happen with long-lived connections).  If you 
don't update 'tcp_rover_next', and this somehow gets to lag behind this 
'group' of ports (say point at the lower extreme) you will need to search 
through this group first before you enter the unoccupied port space.

Also, Linux TCP will reuse ports if (saddr, daddr, sport) are different.
Look at __tcp_v4_check_established.  This means that the ports actually have
to be in use with real connections to the same host.

Your scheme works initially because you do not lag behind the free port space, 
but eventually you will, and I think this will result in less optimal 
performance compared to the old behaviour.

Free port space should be evenly distributed because of the hash function.

Since updating the 'tcp_rover_next' practically always result in a free port 
on first try, I think SMP performance will not suffer even though the lock 
was held all through the port search (except when the port space is very 
crowded).

But by not having a global lock on port allocation, different cpu's can be
searching different hash trees.  This would matter under Dos attack with
multiple interfaces.

And yes, I do use Linux exclusively, so I do care :-))

quoted

From a statistically point of view, if the connection life-times are uniformly 

distributed from zero to infinite (theoretical scenario), it does not matter 
what starting point you use. However, soon as life-times are not uniformly 
distributed, this kind of search algorithm will benefit from good starting 
point defining where the probability of used vs. unused port drop from high 
to low.

The BSD solution with a pure random rover suffers similarly, especially when 
the port space becomes crowded.

quoted

quoted

* connect_port_offset() does not (at least from an algorithm point
  of view) need to return an u32, an u16 is sufficient.

If it is truncated to u16, then compiler has to take extra effort to
truncate is unnecessary given later  modulo operation.

I agree (in fact thats what I argued in the draft) - it probably depends on 
your platform - you are assuming a 32-bit platform I guess.