Subject: [ledbat] LEDBAT implementation report

From: Victor Grishchenko <[email-masked]>
Date: Tue, 23 Feb 2010 17:50:55 +0100

Hi!

As a part of the P2P-Next-project, we are developing a multiparty transport protocol (named swift). In particular, it employs LEDBAT congestion control. Currently we are debugging/testing transport in swarm-like scenarios (~40 servers, both real and emulated network conditions). 
The thing functions more or less as expected, e.g. see http://mfold.libswift.org/harvest-1266937401/node319-node312.big.png
In perfect conditions it indeed proceeds almost loss-free, consumes 9x% of available bandwidth, yields to TCP etc. In high-bandwidth, many-connections, nearly-congested conditions it is not that simple, e.g. http://mfold.libswift.org/harvest-1266937401/seeder-messy.big.png On the other hand, that is also expected.

The only problem we've found is the suggested framing method. Namely, according to both specs
  http://bittorrent.org/beps/bep_0029.html#timestamp-difference-microseconds
  http://tools.ietf.org/html/draft-shalunov-ledbat-congestion-00  (Page 9)
the receiver calculates one-way delay. That allows the receiver to easily supply misleading information, e.g. to divide the (delay-min_delay) difference by two. That leads to gross unfairness, suppression of all other LEDBAT streams of the same sender, etc. Actually, I wonder whether the sender might detect that situation in principle. Practically, the attack might be interesting as it allows to grab as much of seeder bandwidth as one wants to (that is BitTorrent-specific).
More secure alternative is to keep a queue of timestamps at the sender. The receiver sends acks with raw timestamps, the sender does the math on its own. Thus, the receiver can not lie consistently. E.g. see tbqueue data_out_ in
  http://github.com/gritzko/swift/blob/master/swift.h
  http://github.com/gritzko/swift/blob/master/sendrecv.cpp
It was sort of an issue for our protocol, as it adds another queue. Must not be an issue for TCP/uTP, as they keep data buffers anyway, so a timestamp doesn't add much. As a nice byproduct, this way we send half as much timestamps, so ~4 bytes per packet is saved.

As another note, we (me and the swift) always space packet send events in time, so cwnd actually defines the sending rate, not the amount of data sent "now" (see the interplay of green lines on the graphs). According to our best unmeasured belief, that is generally a nicer option for a low extra delay congestion control.

All the best,

		Victor Grishchenko
		post-doc
		TU Delft

---

From: Nicholas Weaver <[email-masked]>
Date: Tue, 23 Feb 2010 09:12:18 -0800

> the receiver calculates one-way delay. That allows the receiver to easily supply misleading information, e.g. to divide the (delay-min_delay) difference by two. That leads to gross unfairness, supp…

I wonder if this might also allow outcompeting of regular TCP flows, or is there still the TCP-parameter AIMD response to packet loss?  (which would still allow the Savage optimisitic-ACK attack)

> It was sort of an issue for our protocol, as it adds another queue. Must not be an issue for TCP/uTP, as they keep data buffers anyway, so a timestamp doesn't add much. As a nice byproduct, this wa…

In general, what may need to happen is that RTT delay may need to be taken into account.  One random thought would be to include an encrypted cookie to the timestamps, so its something like

S -> R:  Seq #, TS, E(TS)
R -> S:  E(TS), 1 way delay calculation

This prevents the receiver from faking ACKs (as the E(TS) is effectively acting as a tamper resistant sequence # to ack the timestamp-containing packet), and allows the sender to measure the actual RTT as well as the "advertised" one-way delay, and use RTT as well as 1-way delay as a signal if overall congestion looks like it may be occuring?

E(TS) should be a 32 bit blockcipher with a 128B key.  there are plenty of block cyphers with tuneable blocksize that could be used.