Nagle's algorithm and uTP

[thrnz]

I've noticed that the way libtorrent handles undersized uTP packets is different than that of libutp and the original RFC introducing Nagle's algorithm, and introduces a potential delay of up to an RTT.

If I'm reading the code correctly, currently libtorrent holds back sending an undersized uTP packet until its either no longer undersized, or until there are no more unack'd packets in flight. As a result, the packet can be held back for up to an entire RTT waiting for acks to arrive before being transmitted.

libtorrent/src/utp_stream.cpp

Lines 1514 to 1520 in 084219e

	// did we fill up the whole mtu?
	// if we didn't, we may still send it if there's
	// no bytes in flight
	if (m_bytes_in_flight > 0
	&& int(p->size) < std::min(int(p->allocated), effective_mtu)
	&& !force
	&& m_nagle)

libutp appears to only hold back an undersized packet until the next ack is received. The RFC also only mentions holding back the packet until something arrives from the other end (though it is from 1984, and I don't know if things have changed). As a result, there is much less likely to be any significant extra delay.

I'm not sure what the effects of this extra delay might be - if any - or whether it's been intentionally done that way or was an oversight. One thing that does come to mind though is when a peer is choked, where there will be a large stream of outgoing data that ends in a tiny choke message. The choke message could potentially be held back as undersized until everything previously in-flight is ack'd, causing the peer to continue requesting new pieces, and - if the extra RTT delay on top of the existing send buffers and underlying latency is high enough - potentially be disconnected due to sending requests while choked.

I'd be surprised if this alone has any meaningful effect on #3542.

[arvidn]

hopefully I'll find some time to look into this.
There are some simulations that might be useful in investigating the exact behavior, although, I don't think there are any tests for nagel's algorithm specifically.

[thrnz]

I've been using this for the last month or so to potentially work around it, though it's not been tested beyond the 'it still compiles and doesn't outright break uTP' stage.

[arvidn]

interesting. My understanding of nagle's algorithm is that only one under-sized packet is supposed to be sent per RTT. Perhaps I misread it. I think it makes sense, though, to try really hard to coalesce sent data into as large packets as possible.

[thrnz]

I was basing that on what was in the original RFC from 1984:

The solution is to inhibit the sending of new TCP  segments  when
new  outgoing  data  arrives  from  the  user  if  any previously
transmitted data on the connection remains unacknowledged.   This
inhibition  is  to be unconditional; no timers, tests for size of
data received, or other conditions are required.
....
Thus, when we omit sending data on arrival from the
user,  we  are  simply  deferring its transmission until the next
message arrives from the distant host. A  message  must  always
arrive soon unless the connection was previously idle or communi-
cations with the other end have been lost.  In  the  first  case,
the  idle  connection,  our  scheme will result in a packet being
sent whenever the user writes to the TCP connection.  Thus we  do
not  deadlock  in  the idle condition.  In the second case, where
the distant host has failed, sending more data is futile  anyway.

It looks like it was superseded by this though, which does indeed hold back the undersized packet until there's nothing left in flight:

The Nagle algorithm is generally as follows:
  If there is unacknowledged data (i.e., SND.NXT >
  SND.UNA), then the sending TCP buffers all user
  data (regardless of the PSH bit), until the
  outstanding data has been acknowledged or until
  the TCP can send a full-sized segment.

I guess one way favors latency, and the other favors efficiency.

The original RFC appears to have been marked as obsolete as of 2016.

[thrnz]

My understanding of nagle's algorithm is that only one under-sized packet is supposed to be sent per RTT.

That looks about right. Unless I'm misreading, then that appears to be the logic that the Linux kernel itself uses. There's some more background info here that's helped me get my head around it, and how that differs from the original from 1984.

How about something like this then? Noting the sequence number of the last undersized packet sent and not sending another until its been ack'd. That should mean that the last few bytes of a 'big' send (eg. data ending in a choke) can get sent immediately rather than being held back for an entire RTT which appears to currently be the case.

[thrnz]

It might be worth looking at the deferred ack logic as well.

If I'm reading things right, currently send_pkt(pkt_ack) can force the packet to be sent with an empty payload - ie. just the header with an updated ack_nr. If a 'nagled' packet is currently being held back, it might make sense to see if it could be picked up and sent at the same time. It's only being held back in order to reduce overhead from packet headers, and sending the extra header-only packet would negate any gain.

It might also be worth removing a previously queued deferred ack if send_pkt() is called again before the deferred ack is sent as the updated ack_nr can get sent out there and then, leaving the pending deferred ack redundant.

[thrnz]

I'll open some PRs with potential changes, though I'd imagine they'd need review/more testing to make sure they're fixing what they're intended to fix.

[arvidn]

thanks. great patches!

[ghost]

Do you guys have plans to backport these to RC_1_2?

[thrnz]

Do you guys have plans to backport these to RC_1_2?

I've opened #7096 that backports these to 1.2. You might want to keep an eye on that to see if/when it gets merged.