From victor.grishchenko@gmail.com Tue Feb 23 08:49:03 2010 Return-Path: X-Original-To: ledbat@core3.amsl.com Delivered-To: ledbat@core3.amsl.com Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id 185F428C314 for ; Tue, 23 Feb 2010 08:49:03 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.599 X-Spam-Level: X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599] Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id h73DRs7YW6d3 for ; Tue, 23 Feb 2010 08:49:01 -0800 (PST) Received: from ey-out-2122.google.com (ey-out-2122.google.com [74.125.78.27]) by core3.amsl.com (Postfix) with ESMTP id 7D39428C30F for ; Tue, 23 Feb 2010 08:49:01 -0800 (PST) Received: by ey-out-2122.google.com with SMTP id 9so958761eyd.51 for ; Tue, 23 Feb 2010 08:50:59 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:from:content-type :content-transfer-encoding:subject:date:message-id:to:mime-version :x-mailer; bh=dY/NevvQa3OBLtwFkYP5avpu5PIBWw4U5v4vWOWdoIU=; b=pDyzKjP1GjmPZy2T7MwIQx565hPF2qSPQdiIK+CETRn+S+vYQf1OR+K/ci1W8EwZYT JOg+WvZhUnxr09nza6rq+Dsj2Bkw0DA5Rmx4TpZ+I71Asxrf3vdmEG9YKmzx9bNFBCEL Dc4xhTLqDhpWMeujTDYO1A4ojFUfoBWp1Ab7o= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:content-type:content-transfer-encoding:subject:date:message-id :to:mime-version:x-mailer; b=fAQEhkDYzZOYJOjT7A0/g9XKzDUKca0dtc93nnF63x4VqgztxrhAEabLnOPXQQy4T+ bcs900SRdG8BFFV0vUL9c+FgBZgjYf9NNSJplR7uqPLdbQp0hfOZLkzo+zOcVEn4p6zY +AXqRIdld8euY1X1BDRQGFn5cfTPJFeNG0R5E= Received: by 10.213.97.67 with SMTP id k3mr781452ebn.18.1266943857918; Tue, 23 Feb 2010 08:50:57 -0800 (PST) Received: from ?10.0.0.4? (s55928ca0.adsl.wanadoo.nl [85.146.140.160]) by mx.google.com with ESMTPS id 14sm138019ewy.10.2010.02.23.08.50.56 (version=TLSv1/SSLv3 cipher=RC4-MD5); Tue, 23 Feb 2010 08:50:57 -0800 (PST) From: Victor Grishchenko Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Date: Tue, 23 Feb 2010 17:50:55 +0100 Message-Id: <39B07644-0249-4E82-AEFF-825557357137@gmail.com> To: ledbat@ietf.org Mime-Version: 1.0 (Apple Message framework v1077) X-Mailer: Apple Mail (2.1077) Subject: [ledbat] LEDBAT implementation report X-BeenThere: ledbat@ietf.org X-Mailman-Version: 2.1.9 Precedence: list List-Id: Mailing list of the LEDBAT WG List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 23 Feb 2010 16:49:03 -0000 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).=20 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 nweaver@ICSI.Berkeley.EDU Tue Feb 23 09:10:22 2010 Return-Path: X-Original-To: ledbat@core3.amsl.com Delivered-To: ledbat@core3.amsl.com Received: from localhost (localhost [127.0.0.1]) by core3.amsl.com (Postfix) with ESMTP id B633428C26C for ; Tue, 23 Feb 2010 09:10:21 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -6.243 X-Spam-Level: X-Spam-Status: No, score=-6.243 tagged_above=-999 required=5 tests=[AWL=0.356, BAYES_00=-2.599, RCVD_IN_DNSWL_MED=-4] Received: from mail.ietf.org ([64.170.98.32]) by localhost (core3.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id M9PaJOPRERnF for ; Tue, 23 Feb 2010 09:10:19 -0800 (PST) Received: from fruitcake.ICSI.Berkeley.EDU (fruitcake.ICSI.Berkeley.EDU [192.150.186.11]) by core3.amsl.com (Postfix) with ESMTP id 1E24B28C324 for ; Tue, 23 Feb 2010 09:10:19 -0800 (PST) Received: from [IPv6:::1] (jack.ICSI.Berkeley.EDU [192.150.186.73]) by fruitcake.ICSI.Berkeley.EDU (8.12.11.20060614/8.12.11) with ESMTP id o1NHCIhq002698; Tue, 23 Feb 2010 09:12:18 -0800 (PST) References: <39B07644-0249-4E82-AEFF-825557357137@gmail.com> In-Reply-To: <39B07644-0249-4E82-AEFF-825557357137@gmail.com> Mime-Version: 1.0 (Apple Message framework v1077) Content-Type: text/plain; charset=us-ascii Message-Id: Content-Transfer-Encoding: quoted-printable From: Nicholas Weaver Date: Tue, 23 Feb 2010 09:12:18 -0800 To: Victor Grishchenko X-Mailer: Apple Mail (2.1077) Cc: ledbat@ietf.org, Nicholas Weaver Subject: Re: [ledbat] LEDBAT implementation report X-BeenThere: ledbat@ietf.org X-Mailman-Version: 2.1.9 Precedence: list List-Id: Mailing list of the LEDBAT WG List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 23 Feb 2010 17:10:22 -0000 On Feb 23, 2010, at 8:50 AM, Victor Grishchenko wrote: > 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). 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) > 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. 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.