Andre Oppermann has posted a patch which completely revises FreeBSD's TCP reassembly code, increasing efficiency and scalability of fragmented packet reassembly with impressive initial test results. Oppermann writes:

"I've totally rewritten the TCP reassembly function to be a lot more
efficient. In tests with normal bw*delay products and packet loss
plus severe reordering I've measured an improvment of at least 30% in
performance. For high and very high bw*delay product links the
performance improvement is most likely much higher."

Those with spare cycles may want to give it a try. Read on for the entirety of Oppermann's educational post and a link to the patch.

From: Andre Oppermann [email blocked]
To: freebsd-net
Cc: freebsd-current
Subject: Rewritten TCP reassembly
Date: 2004-12-10 20:01:12

I've totally rewritten the TCP reassembly function to be a lot more
efficient.  In tests with normal bw*delay products and packet loss
plus severe reordering I've measured an improvment of at least 30% in
performance.  For high and very high bw*delay product links the
performance improvement is most likely much higher.

The main property of the new code is O(1) insert for 95% of all normal
reassembly cases.  If there is more than one hole the insert time is
O(holes).  If a packet arrives that closes a hole the chains to the left
and right are merged.  Artificially constructed worst case is O(n).  No
malloc's are done for new segments.  The old code was O(n) in all cases
plus n*malloc for a describing structure.

There are some problems with the new code I will fix before committing
it to the tree.  One is it can't handle non-writeable mbuf's and the
other is too little leading space in the mbuf (found only on loopback
interface, but there we don't have packet loss).  Once these two are
dealed with it is ready to go in.

Nothing is perfect and this code is only a first significant step over
what we have currently in the tree, especially for transfers over lossy
(wireless) and high speed links with and without packet reordering.
I have the next steps already in the works which will further optimize
(worst case O(windowsize/mclusters) instead of O(n)) and simplify a bit
more again.

The patch can be found here:

  http://www.nrg4u.com/freebsd/tcp_reass-20041210.patch

Please test and report good and bad news back.

-- 
Andre

• Archive of the Above Thread