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

From: Andre Oppermann <[email-masked]>
Date: Mon, 21 Jan 2008 23:44:02 +0100

I'm currently rewriting the tcp reassembly queue of FreeBSD (which
is still almost 4.4BSD verbatim) to deal with large socket buffers
and to be more economic with kernel memory in the form of mbufs. [1]
The new code is based on blocks of contiguous segment data instead
of a list of received out-of-order segment that has to be traversed
to find the right place for the new segment.  It also does all the
obvious optimizations based on the chance of things happening.

Now there are two issues I'd like to solicit the input from this wg.

The first is the ordering of SACK blocks.  The block based reassembly
queue lends itself to generate the SACK option from.  The blocks are
ordered ascending from the first segment closest to rcv_nxt.  Per RFC
2018 Section 4 the first SACK block MUST be the one with the most
recent addition to it.  This is easily done by adding a pointer to
the block last modified.  However a bit later it says the following
SACK blocks SHOULD be also in order of their 'recentness' while also
specifying they may be listed in arbitrary order.  Now tracking this
information in the block based and sequence number ordered reassembly
queue it a bit more involved and I wonder if it really necessary and
useful.  In general the SACK blocks tend to be ordered sequentially
after the first SACK block in single random loss cases.  Only in
packet reordering cases, possibly mixed with loss, this may not be
the case.  On the other hand the most valuable information for the
sender are the blocks closest to rcv_nxt so it can fill the hole and
complete the sequence space.  While the RFC leaves me free to do as
I please I wonder if there are observations or rationales that clearly
show the the ordering by recentness to be better than sequential
ordering after the first SACK block?

The second is how long to hold onto data in the reassembly queue.
The general theme here is resource exhaustion be it through malicious
activity or just end points that drop off the net.  I think we can
all agree that holding onto reassembly queue data until the session
times out (if ever) is not really useful considering the overall
resource constrains.  The question now is after what time to flush
the reassembly queue (and to send an appropriate ACK)?  A range of
options are available.  On the wide side we have a flush timeout
of something like 2 times MSL.  On the small side we can go down to
the current calculated retransmit timeout value as seen from our side.
Also of importance is from where the timeout is calculated.  From the
time the first segment arrived in the reassembly queue (resetting when
rcv_nxt is advanced), or from the arrival time of the most recent
segment.  For the moment and testing I've chosen the former at four
times retransmit timeout as something that probably marks the boundary
between spurious network losses or partitioning and longer-term
disconnect or malicious activity.  Is any empirical data available on
abandoned sessions with data in the reassembly queue?  What is your
opinion and rationale on this?

[1] 
http://perforce.freebsd.org/fileLogView.cgi?FSPC=//depot/projects/tcp_reass/netinet/tcp_reass.c

-- 
Andre

[email-masked]

_______________________________________________
tcpm mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/tcpm

---

From: Joshua Blanton <[email-masked]>
Date: Tue, 22 Jan 2008 10:42:07 -0500

I don't have a good answer to your first question (other than to
mention that, if you always send the most-recently-modified SACK
regions, you ensure that they're sent multiple times - which is the
only quasi-reliability you can create on the ACK path), but I would
like to address the second.

> opinion and rationale on this?

Well, I actually disagree that holding onto reassembly queue data is
a lost cause, even after long periods of inactivity - so perhaps we
don't all agree :-).  Certainly you could tell *after* the fact that
holding such data was a fool's errand, if the connection is
terminated; until that point, there's no reason to necessarily
assume that the lack of progress in the connection is permanent.  In
general, I would expect an operating system to hold on to reassembly
data for forever, assuming that there's no memory resource concern
that makes the buffers valuable...  To flush data simply because
wall-clock time has elapsed doesn't make sense to me, since I've
seen many traces where "long" time periods have elapsed and then
connections suddenly resume.  If there's no global "we're running
out of memory" trigger available for a given OS, a stack could set a
timer to fire at some arbitrary time (4*RTO, for instance) and check
for memory pressure - *if* it exists, go ahead and flush the data.

I don't have any data showing how much reassembly data is left
hanging around when a session is abandoned, but I have looked at
quite a few traces trying to find SACK renegs (which would be the
result of your data flushing).  In general, I believe that a scheme
such as you're proposing is not used; other than some traces that
I've found that p0f identifies as being FreeBSD receivers, there
doesn't appear to be a solid link between connection progress
timeouts and reneging.  I don't know the FreeBSD stack well enough
to say that, in its current implementations, it definitely flushes
reassembly queue data based on a timer - but I suspected that it
did, and your question reinforces my suspicion.  If I am correct,
and FreeBSD currently (5.x and 6.x) times out reassembly data as
you're proposing, I've seen traces where this actually impedes a
connection's recovery - so I vote against such a scheme.

Again, I have no problem with stacks flushing out-of-order data in
the face of a low-memory condition.  Beyond that, I'd have to see
some pretty convincing data that "long pauses == connection that
will terminate without finishing," which is what I feel you're
proposing.

Josh

---

From: Matt Mathis <[email-masked]>
Date: Tue, 22 Jan 2008 17:40:19 -0500 (EST)

> ordering after the first SACK block?

RFC 2018 is written the way it is written to maximize the robustness in the 
presence of lost ACKs.  If the network never looses ACKs, then just reporting 
the single SACK block with the newest data is guaranteed to be sufficient for 
the sender to have perfect knowledge about the state of the reassembly queue 
at the receiver.

If occasional ACKs and one of several non-contiguous retransmissions are lost, 
the sender might not learn that some of the retransmissions were successful if 
the 2nd and 3rd SACK block do not reflect the history of the first block.

Although in most cases you want to know about blocks closest to rcv_nxt, that 
is not always true.  In particular if the two oldest retransmissions are lost 
and then some ACKs are also lost, the sender will not know that some of the 
later holes have been successfully filled.  If you are going to take a timeout 
anyhow, this isn't so important, but we tried to avoid timeouts at all costs.

If the 2nd and 3rd block reflect most recent history of the 1st block, the 
sender will have perfect knowledge of the reassembly queue as long as the 
network never looses 3 consecutive ACKs (and usually tolerates many more 
losses).

The "may use other algorithms" is there because we suspect that you can do 
even better, for example by making the 2nd and 3rd blocks periodically or 
randomly re-report all old SACK blocks.  As far a I know this has never been 
pursued, and we certainly did not want to specify or even suggest it in 2018.

Everyone else implements it as written....

Oh, except nix "timeouts MUST clear the scoreboard"... If you preserve the 
scoreboard on a timeout, you might be able to do goodput=throughput (zero 
duplicate data at the receiver) under very high loss rates, which is a good 
thing.

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.

---

From: Andre Oppermann <[email-masked]>
Date: Thu, 24 Jan 2008 00:14:51 +0100

> for memory pressure - *if* it exists, go ahead and flush the data.

The memory pressure thing is critical part here.  Otherwise I fully
agree that we should hold onto the reassembly queue forever.
Unfortunately we can't afford to do that as memory is still limited.

The problematic part I'm trying to address here is the very difficult
definition of memory pressure.  In modern kernels this isn't as simple
as it seems on a first glance.  Of course we can and do detect when we
run out of physical memory in kernel.  However memory pressure starts
a lot earlier and may manifest itself by a couple of subsystems having
trouble to obtain enough memory out of their zones.  Memory also may
be used for more productive things than reassembly queues, for example
disk buffers.  In SMP and NUMA systems various pools of memory on the
CPUs may have associated memory regions which may be depleted to
different levels.  On top of it modern kernels run in memory
overcommit mode where not all potential memory requirements can
be fulfilled at the same time.  Otherwise we would have to lock down
the full socket buffer space for every connection we may have.  This
is very inefficient and uneconomical.

Whether limited kernel memory is more valuable in a reassembly queue
than other data structure really depends on the goals and purpose of a
particular system and its application setting.  All this and a lot more
makes it really hard to go for a purist solution.

We as developers of a general purpose operating system (in this case
FreeBSD) have to chose appropriate limits and defaults for a wide range
of operating conditions.  Special and niche applications may require
specific tunings and explicit settings.

We have to find a good balance among allocation of memory to the various
usages in the kernel.  Not to forget we also have to protect to a
certain extent against malicious attacks that try to chew us up.  For
this we use things like syncaches and other methods.  TCP reassembly
is no exception to this.

The hard part, and the reason I've come here to solicit input, is to
decide where to set the limits.  There are a number of (imaginary)
intersecting curves that represent the usefulness of memory tied up
in an inactive or non-responsive reassembly queue vs. other valuable
uses the kernel may have for that memory.  The question is where these
curves intersect and where to set the cutoff point in the reassembly
queue.  If for example 98% of all sessions get their reassembly act
together within 2xRTO it may be worth the negative impact on the other
2% to opportunistically use the memory for other purposes.  Even if
we flush the reassembly queue in those two percent it is a graceful
failure as the connections are not terminated and stay alive although
not at the theoretically optimal point from a network resource
conservation point of view.

I guess this really gets into a discussion about the economics theory
side of things...  ;-)

> connection's recovery - so I vote against such a scheme.

The reassembly queues in FreeBSD 5, 6 and 7 do not get flushed unless
under severe system wide memory pressure (a time things already fall
apart left and right).  All the work and changes I'm doing and
discussing here are on a separate development and testing branch and
won't be in official FreeBSD until everything is sorted out and tested.

> will terminate without finishing," which is what I feel you're

Whether the connection will terminate without finishing is only an
optimization aspect.  The tipping point is "long pause && holding
on to valuable memory <> other more valuable use for memory".  Now
define long pause, value of memory and plot the trajectory.

-- 
Andre

---

From: Andre Oppermann <[email-masked]>
Date: Thu, 24 Jan 2008 01:01:00 +0100

Matt Mathis wrote:
> RFC 2018 is written the way it is written to maximize the robustness in 
> the presence of lost ACKs.  If the network never looses ACKs, then just 
> reporting the single SACK block with the newest data is guaranteed to be 
> sufficient for the sender to have perfect knowledge about the state of 
> the reassembly queue at the receiver.
> 
> If occasional ACKs and one of several non-contiguous retransmissions are 
> lost, the sender might not learn that some of the retransmissions were 
> successful if the 2nd and 3rd SACK block do not reflect the history of 
> the first block.
> 
> Although in most cases you want to know about blocks closest to rcv_nxt, 
> that is not always true.  In particular if the two oldest 
> retransmissions are lost and then some ACKs are also lost, the sender 
> will not know that some of the later holes have been successfully 
> filled.  If you are going to take a timeout anyhow, this isn't so 
> important, but we tried to avoid timeouts at all costs.

This pretty much where my question originates from.  The approach of
reporting the most recent block first and then closest and second
closest to rcv_nxt works just fine as long as the number of holes is
not large or excessive.  However even then I may argue that filling
the hole after rcv_nxt is the most important goal, above reporting
second and third recent blocks (if different).  Once the first hole
is filled the closest and second closest blocks to rcv_nxt automatically
shift to the right by one and get reported immediately.  When a large
number of holes appear the sender is very likely to face a collapsed
congestion window and will have to throttle down its rate of sending.
This makes it probable that guaranteed knowledge further out is not
relevant at this point in time.  By the time this becomes relevant it
get reported because it gets closer to rcv_nxt.

I'm not forcefully arguing this view but want to bring it up for further
elaboration and comparison with the other recommended approaches.

> If the 2nd and 3rd block reflect most recent history of the 1st block, 
> the sender will have perfect knowledge of the reassembly queue as long 
> as the network never looses 3 consecutive ACKs (and usually tolerates 
> many more losses).
> 
> The "may use other algorithms" is there because we suspect that you can 
> do even better, for example by making the 2nd and 3rd blocks 
> periodically or randomly re-report all old SACK blocks.  As far a I know 
> this has never been pursued, and we certainly did not want to specify or 
> even suggest it in 2018.
> 

FreeBSD currently does so as well.  It's in my development branch I'm
working and experimenting with alternative approaches.  Using the block
building logic of the reassembly queue itself for SACK reporting is
quite tempting.  ;-)

> Oh, except nix "timeouts MUST clear the scoreboard"... If you preserve 
> the scoreboard on a timeout, you might be able to do goodput=throughput 
> (zero duplicate data at the receiver) under very high loss rates, which 
> is a good thing.

Thanks for your extensive explanations.

-- 
Andre

---

From: Matt Mathis <[email-masked]>
Date: Thu, 24 Jan 2008 09:29:41 -0500 (EST)

If you are thinking at the scale of a dozen packet windows with just a couple 
of losses, I don't disagree with you.  However, with 1000 packet windows, you 
almost never see "just a couple of losses", and your proposed simplification 
will be very exposed to lost ACKs.  Given that the ACK rate doubles, 
your chances are not good.

BTW 1000 packet windows are not all that big: 1500 Byte MTU, 70 ms RTT and 
only 90 Mb/s - well within reach for any university user in the US or Europe
and FIOS users in Korea or Japan.   The real challenge is getting the 
scoreboard to work well with 10k or 100k packet windows....

Thanks,
--MM--

On Thu, 24 Jan 2008, Andre Oppermann wrote:

>> presence of lost ACKs.  If the network never looses ACKs, then just 
>> sufficient for the sender to have perfect knowledge about the state of the 
>> reassembly queue at the receiver.
>> 
>> successful if the 2nd and 3rd SACK block do not reflect the history of the 
>> first block.
>> 
>> that is not always true.  In particular if the two oldest retransmissions 
>> are lost and then some ACKs are also lost, the sender will not know that 
>> some of the later holes have been successfully filled.  If you are going to 
>> take a timeout anyhow, this isn't so important, but we tried to avoid 
>> timeouts at all costs.
>
>> randomly re-report all old SACK blocks.  As far a I know this has never 
>> been pursued, and we certainly did not want to specify or even suggest it 
>> in 2018.
>>

---

From: Lars Eggert <[email-masked]>
Date: Thu, 24 Jan 2008 17:04:25 +0200

On 2008-1-24, at 16:29, ext Matt Mathis wrote:
> BTW 1000 packet windows are not all that big: 1500 Byte MTU, 70 ms  
> RTT and only 90 Mb/s - well within reach for any university user in  
> the US or Europe
> and FIOS users in Korea or Japan.   The real challenge is getting  
> the scoreboard to work well with 10k or 100k packet windows....

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.)

Lars

---

From: David Malone <[email-masked]>
Date: Thu, 24 Jan 2008 15:24:29 +0000

> we may have some work to do. (But you probably know more about this  

I think it was mainly implementation issues, see Chapter 3 of:

	http://www.hamilton.ie/publications/baruch_even_thesis.pdf

it describes how to fix some of the problems. With that, there were
no problems running up to about 1Gbps with sizeable RTTs.

	David.

---

From: Matt Mathis <[email-masked]>
Date: Thu, 24 Jan 2008 10:49:40 -0500 (EST)

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--