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

Matt Mathis <mathis@psc.edu> Thu, 24 January 2008 15:49 UTC

Return-path: <tcpm-bounces@ietf.org>
Received: from [127.0.0.1] (helo=stiedprmman1.va.neustar.com) by megatron.ietf.org with esmtp (Exim 4.43) id 1JI4Kl-0002xw-6s; Thu, 24 Jan 2008 10:49:43 -0500
Received: from tcpm by megatron.ietf.org with local (Exim 4.43) id 1JI4Kk-0002xp-5S for tcpm-confirm+ok@megatron.ietf.org; Thu, 24 Jan 2008 10:49:42 -0500
Received: from [10.90.34.44] (helo=chiedprmail1.ietf.org) by megatron.ietf.org with esmtp (Exim 4.43) id 1JI4Kj-0002xc-QX for tcpm@ietf.org; Thu, 24 Jan 2008 10:49:41 -0500
Received: from mailer1.psc.edu ([128.182.58.100]) by chiedprmail1.ietf.org with esmtp (Exim 4.43) id 1JI4Kj-0000DJ-FA for tcpm@ietf.org; Thu, 24 Jan 2008 10:49:41 -0500
Received: from tesla.psc.edu (tesla.psc.edu [128.182.58.233]) by mailer1.psc.edu (8.14.2/8.13.3) with ESMTP id m0OFne8C015306 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 24 Jan 2008 10:49:40 -0500 (EST)
Received: from localhost.psc.edu (localhost.psc.edu [127.0.0.1]) by tesla.psc.edu (8.13.1/8.13.1) with ESMTP id m0OFneu5006901; Thu, 24 Jan 2008 10:49:40 -0500
Date: Thu, 24 Jan 2008 10:49:40 -0500 (EST)
From: Matt Mathis <mathis@psc.edu>
To: Lars Eggert <lars.eggert@nokia.com>
Subject: Re: [tcpm] Ordering of SACK blocks, flushing of reassembly queue after inactivity
In-Reply-To: <1648983D-9F94-4C59-88AD-78496CBFA119@nokia.com>
Message-ID: <Pine.LNX.4.64.0801241023450.27196@tesla.psc.edu>
References: <47952032.3030809@freebsd.org> <Pine.LNX.4.64.0801221619190.27196@tesla.psc.edu> <4797D53C.10908@freebsd.org> <Pine.LNX.4.64.0801240911250.27196@tesla.psc.edu> <1648983D-9F94-4C59-88AD-78496CBFA119@nokia.com>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 2409bba43e9c8d580670fda8b695204a
Cc: TCP Maintenance and Minor Extensions WG <tcpm@ietf.org>
X-BeenThere: tcpm@ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: TCP Maintenance and Minor Extensions Working Group <tcpm.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/tcpm>, <mailto:tcpm-request@ietf.org?subject=unsubscribe>
List-Post: <mailto:tcpm@ietf.org>
List-Help: <mailto:tcpm-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/tcpm>, <mailto:tcpm-request@ietf.org?subject=subscribe>
Errors-To: tcpm-bounces@ietf.org

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