Efficiency of SACK processing

Setup

See the general guideline of settings at Testing Setup of kernel 2.6.18-rc4
We show the efficiency of SACK processing in this experiment. As we have seen a lot of cases that TCP didn't work well with large window drop especially with large buffer. For this reason, we use large bottleneck buffer sizes in this setup(0.8BDP and 1.0BDP for 250ms RTT and 380ms RTT respectively). Also, recent kernels try to alleviate these problems by efficiently using cache hits and by introducing a new structure like RBtree, we include three kernel versions from 2.6.13 to the latest recent kernel at this time. We use two high-speed flows for two machines (one for each machine). We only tested the cases with RTTs of 250ms and 380ms. For each experiment, the RTTs of two high-speed flows are set to the same value.

We can see very long black-outs in throughput when a lot of packet losses happened in slowstart (especially it was severe with 2.6.18-rc4).
By looking at CPU utilizations, we observed that these black-outs are because of processing overheads of SACKs (this is trivial for small number of packets, but the number of SACKed packets are large enough (for example, larger than 10000 packets), then the system doesn't respond during these blackout periods (sometimes, it takes more than 10-20 secconds).