Re: [tcpm] Ordering of SACK blocks, flushing of reassembly queue after inactivity

On Thu, 24 Jan 2008, Lars Eggert wrote:

> The highspeed TCP folks have reported cases where SACK processing can eat CPU 
> cycles up to a degree where it significantly affects performance. (I think 
> this was under Linux.) I'm not sure if this is an issue with the code or an 
> issue with the spec; if it's the latter, we may have some work to do. (But 
> you probably know more about this than I do anyway.)

Yes, the straight forward ways to implement the scoreboard all take O(N^2) 
time, especially in the pathological case where every 2nd or 3rd segment is 
lost, such as following a slowstart into a drop tail queue.

At GigE, it is pretty easy to construct cases where the CPU time to process 
all of the SACK blocks in all ACKS exceeds rto. (Or at least this was true 
for Linux kernels that are more than a few years old.  There has been a lot of 
attention to SACK efficiency lately).

Thanks,
--MM--
-------------------------------------------
Matt Mathis      http://www.psc.edu/~mathis
Work:412.268.3319    Home/Cell:412.654.7529
-------------------------------------------
Evil is defined by mortals who think they know
"The Truth" and use force to apply it to others.

_______________________________________________
tcpm mailing list
tcpm@ietf.org
https://www1.ietf.org/mailman/listinfo/tcpm