From rbriscoe@jungle.bt.co.uk Wed Apr 1 03:45:07 2009 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 B89CA3A6A98 for ; Wed, 1 Apr 2009 03:45:07 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.083 X-Spam-Level: X-Spam-Status: No, score=-1.083 tagged_above=-999 required=5 tests=[AWL=-0.455, BAYES_05=-1.11, DNS_FROM_RFC_BOGUSMX=1.482, RCVD_IN_DNSWL_LOW=-1] 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 GMLqQdYUAxog for ; Wed, 1 Apr 2009 03:45:00 -0700 (PDT) Received: from smtp4.smtp.bt.com (smtp4.smtp.bt.com [217.32.164.151]) by core3.amsl.com (Postfix) with ESMTP id 93A293A690B for ; Wed, 1 Apr 2009 03:45:00 -0700 (PDT) Received: from i2kc06-ukbr.domain1.systemhost.net ([193.113.197.70]) by smtp4.smtp.bt.com with Microsoft SMTPSVC(6.0.3790.3959); Wed, 1 Apr 2009 11:45:59 +0100 Received: from cbibipnt05.iuser.iroot.adidom.com ([147.149.196.177]) by i2kc06-ukbr.domain1.systemhost.net with Microsoft SMTPSVC(6.0.3790.1830); Wed, 1 Apr 2009 11:45:59 +0100 Received: From bagheera.jungle.bt.co.uk ([132.146.168.158]) by cbibipnt05.iuser.iroot.adidom.com (WebShield SMTP v4.5 MR1a P0803.399); id 1238582758255; Wed, 1 Apr 2009 11:45:58 +0100 Received: from mut.jungle.bt.co.uk ([10.215.130.87]) by bagheera.jungle.bt.co.uk (8.13.5/8.12.8) with ESMTP id n31AjtGg008364; Wed, 1 Apr 2009 11:45:56 +0100 Message-Id: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk> X-Mailer: QUALCOMM Windows Eudora Version 7.1.0.9 Date: Wed, 01 Apr 2009 11:46:03 +0100 To: Stanislav Shalunov From: Bob Briscoe Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1"; format=flowed Content-Transfer-Encoding: quoted-printable X-Scanned-By: MIMEDefang 2.56 on 132.146.168.158 X-OriginalArrivalTime: 01 Apr 2009 10:45:59.0550 (UTC) FILETIME=[0B52B9E0:01C9B2B7] Cc: ledbat@ietf.org Subject: [ledbat] Hard-coded delay target? draft-shalunov-ledbat-congestion-00 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: Wed, 01 Apr 2009 10:45:07 -0000 Stas, This posting repeats what I said in the ledbat=20 w-g meeting in SF, but to the whole list and with=20 added reasoning, given the benefit of more time for thought. On balance it seems wrong to aim for a hard-coded=20 delay target (25ms). I understand your reasoning=20 for it in the draft (dividing delay between=20 competing flows rather than adding), but there=20 are also stronger scaling reasons against it... For 1500B* packets, 25ms represents a standing queue of: 1 pkt @ 512kb/s 17 pkt @ 8Mb/s 50 pkt @ 24Mb/s (some backhaul links today) 208 pkt @ 100Mb/s (typical PON access rate today) 2080 pkt @ 1Gb/s (increasingly backhaul links are GigE) As bottleneck links get faster (magically this is=20 happening!), we will want to reduce the=20 hard-coded delay (to save on fast buffer memory and the power it requires). But if the the algo in draft-00 were changed in=20 the future to aim at 10ms (while the installed=20 base all still aimed at 25ms), the new code would=20 always be starved by the installed base.=20 Therefore we would be stuck forever with the=20 number we first thought of: 25ms hard-coded. Spelling this out longhand, imagine two flows competing: Flow N (New) (10ms target) Flow L (Legacy) (25ms target) L drives delay to 25ms while both flows have packets to send { N reduces rate because delay greater than 10ms L sees delay decrease so increases its rate to drive delay to 25ms } Result: newer algorithm always starves. IMHO, the algo needs to aim at minimising the=20 congestion delay, not aim at a fixed target (the=20 draft says the former but does the latter).=20 Section 3 onwards of [Key04] may help, even tho=20 it's in the context of adapting the receive=20 window it's still based on delay sensing. I'd be=20 interested to know whether Microsoft's BITS now=20 implements something like this algo. Bob [* =3D This might be fine if packet size scaled=20 with link speeds, but that isn't happening.] [Key04] Peter Key, Laurent Massouli=E9 and Bing=20 Wang, "Emulating low-priority transport at the=20 application layer: a background transfer service"=20 In: "ACM SIGMETRICS '04/Performance '04: Proceedings of the joint= international conference on Measurement and modeling of=20 computer systems", pp. 118--129=20 (2004) ________________________________________________________________ Bob Briscoe, Networks Research Centre, BT Research=20 From shalunov@bittorrent.com Thu Apr 2 23:10:20 2009 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 5A0653A6972 for ; Thu, 2 Apr 2009 23:10:20 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.89 X-Spam-Level: X-Spam-Status: No, score=-1.89 tagged_above=-999 required=5 tests=[AWL=0.087, BAYES_00=-2.599, FM_FORGED_GMAIL=0.622] 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 Ibz33BXyavde for ; Thu, 2 Apr 2009 23:10:19 -0700 (PDT) Received: from rv-out-0506.google.com (rv-out-0506.google.com [209.85.198.224]) by core3.amsl.com (Postfix) with ESMTP id 3BF6B3A6B1B for ; Thu, 2 Apr 2009 23:10:19 -0700 (PDT) Received: by rv-out-0506.google.com with SMTP id k40so884226rvb.49 for ; Thu, 02 Apr 2009 23:11:21 -0700 (PDT) MIME-Version: 1.0 Received: by 10.142.132.2 with SMTP id f2mr226193wfd.261.1238739081423; Thu, 02 Apr 2009 23:11:21 -0700 (PDT) In-Reply-To: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk> References: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk> Date: Thu, 2 Apr 2009 23:11:21 -0700 Message-ID: <6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com> From: Stanislav Shalunov To: Bob Briscoe Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Cc: ledbat@ietf.org Subject: Re: [ledbat] Hard-coded delay target? draft-shalunov-ledbat-congestion-00 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: Fri, 03 Apr 2009 06:10:20 -0000 Bob, The choice of parameters for congestion control has a degree to which it's arbitrary. Why does TCP ramp up at a hard-coded 1 MSS/RTT? Why not 3.5 or 0.6? Why does it multiply by 0.5 instead of 7/8 or 0.2 or 0? If a future version of TCP chooses 0.2 and 0.3 as its favorite lucky numbers while the installed base is at 1 and 0.5, the consequences are similar. While the choice of the particular parametrization for TCP might be argued to be suboptimal because it doesn't scale with link speed, I'm not aware of any congestion control mechanism without parameters. The mechanism we use scales the target queue linearly with link speed, as you point out. It's a feature. It enables the mechanism to work on a variety of bottleneck speeds. If you specify the target in bytes, you lose on fast links because your delay starts getting lower than scheduling noise and/or PCI bus jitter and you lose on slow links because the delay is too large for interactive apps. As choice of parameters goes, the choice of the gain is much more arbitrary than the choice of the target. The gain simply matches TCP in the worst case. Target is essentially the lowest value than can be reliably distinguished from 0 on a variety of machines under a variety of circumstances. As a practical matter, 25ms is a substantial reduction from the 1RTT rule of thumb and so it's reasonable to expect that the deployed gear will have this much delay. Usually it has far more. (Even at 10Gb/s and up.) If some gear at an atypical bottleneck doesn't have this much, the behavior degenerates into TCP. It is also a fairly unsubstantial increase relative to RTT and will remain such unless progress is made on the speed-of-light problem (or the planet is shrunk?). The work you cite never seems to mention minimizing delay as a goal. It discusses the queuing delay achieved in Theorem 3. And there's a parameter that controls it (alpha_b^*). -- Stas On Wed, Apr 1, 2009 at 3:46 AM, Bob Briscoe wrot= e: > Stas, > > This posting repeats what I said in the ledbat w-g meeting in SF, but to = the > whole list and with added reasoning, given the benefit of more time for > thought. > > On balance it seems wrong to aim for a hard-coded delay target (25ms). I > understand your reasoning for it in the draft (dividing delay between > competing flows rather than adding), but there are also stronger scaling > reasons against it... > > For 1500B* packets, 25ms represents a standing queue of: > =A0 1 pkt @ 512kb/s > =A017 pkt @ =A0 8Mb/s > =A050 pkt @ =A024Mb/s (some backhaul links today) > =A0208 pkt @ 100Mb/s (typical PON access rate today) > 2080 pkt @ =A0 1Gb/s (increasingly backhaul links are GigE) > > As bottleneck links get faster (magically this is happening!), we will wa= nt > to reduce the hard-coded delay (to save on fast buffer memory and the pow= er > it requires). > > But if the the algo in draft-00 were changed in the future to aim at 10ms > (while the installed base all still aimed at 25ms), the new code would > always be starved by the installed base. Therefore we would be stuck fore= ver > with the number we first thought of: 25ms hard-coded. > > Spelling this out longhand, imagine two flows competing: > =A0 =A0 =A0 =A0Flow N (New) =A0 =A0(10ms target) > =A0 =A0 =A0 =A0Flow L (Legacy) (25ms target) > > L drives delay to 25ms > while both flows have packets to send { > =A0 =A0N reduces rate because delay greater than 10ms > =A0 =A0L sees delay decrease so increases its rate to drive delay to 25ms > } > Result: newer algorithm always starves. > > IMHO, the algo needs to aim at minimising the congestion delay, not aim a= t a > fixed target (the draft says the former but does the latter). Section 3 > onwards of [Key04] may help, even tho it's in the context of adapting the > receive window it's still based on delay sensing. I'd be interested to kn= ow > whether Microsoft's BITS now implements something like this algo. > > > Bob > > [* =3D This might be fine if packet size scaled with link speeds, but tha= t > isn't happening.] > > [Key04] Peter Key, Laurent Massouli=E9 and Bing Wang, "Emulating low-prio= rity > transport at the application layer: a background transfer service" In: "A= CM > SIGMETRICS '04/Performance '04: Proceedings of the joint international > conference on Measurement and modeling of computer systems", pp. 118--129 > (2004) > > > > > ________________________________________________________________ > Bob Briscoe, =A0 =A0 =A0 =A0 =A0 =A0 =A0 Networks Research Centre, BT Res= earch > --=20 Stanislav Shalunov BitTorrent Inc shalunov@bittorrent.com personal: http://shlang.com From shalunov@bittorrent.com Thu Apr 2 23:28:51 2009 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 2F2AA3A68A6 for ; Thu, 2 Apr 2009 23:28:51 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.896 X-Spam-Level: X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[AWL=0.081, BAYES_00=-2.599, FM_FORGED_GMAIL=0.622] 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 VIlUcVWgY-ge for ; Thu, 2 Apr 2009 23:28:50 -0700 (PDT) Received: from wf-out-1314.google.com (wf-out-1314.google.com [209.85.200.170]) by core3.amsl.com (Postfix) with ESMTP id 2BE3E3A6881 for ; Thu, 2 Apr 2009 23:28:50 -0700 (PDT) Received: by wf-out-1314.google.com with SMTP id 24so1048293wfg.31 for ; Thu, 02 Apr 2009 23:29:52 -0700 (PDT) MIME-Version: 1.0 Received: by 10.142.13.14 with SMTP id 14mr237311wfm.108.1238740192346; Thu, 02 Apr 2009 23:29:52 -0700 (PDT) In-Reply-To: References: Date: Thu, 2 Apr 2009 23:29:52 -0700 Message-ID: <6c82d1360904022329o34efd701p8b7a0b08730ae65a@mail.gmail.com> From: Stanislav Shalunov To: Douglas Leith Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Cc: ledbat@ietf.org Subject: Re: [ledbat] fairness between competing delay flows in draft-shalunov-ledbat-congestion-00.txt 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: Fri, 03 Apr 2009 06:28:51 -0000 We have not observed the late-comer's advantage. As soon as the first flow has a hiccup (for example, because something needs to wait for a few disk head moves), there will be a gap in the first flow's traffic, enabling the second flow to measure accurately. During the session Murari mentioned that in their experience, flows were also always able to get a reasonable base delay measurement. Obviously, the more flows, the more uniform the traffic, the more likely it is that the late comers might be mistaken about the base. At tens of flows, this is clearly not a problem. At tens of thousands, which is what most backbones see for bulk connections, I'd expect it to start showing. The coordination problem at tens of thousands of connections is hard and almost certain to be emergent, but then extended congestion on backbone links is infrequent. In the worst case, it'll all fall back to TCP. For a small number of flows, the situation most typically encountered on congested links, base estimation seems to be reliable. On Tue, Mar 31, 2009 at 5:23 PM, Douglas Leith wrote: > Can I ask what the expected/desired behaviour will be when two or more > ledbat flows share a link ? > For example, say a first flow starts, ramps us cwnd until it hits the tar= get > queueing delay and then a second ledbat flow starts a while later. =A0Its= not > clear to me from the ID how the first flow would alter its cwnd to make > space for the second ledbat flow (especially if the second flow does not = use > slow start, or perhaps has an early exit from slow start). > Also, is there a danger that, similarly the vegas and related algorithms, > the later starting flow will have difficulty getting an accurate estimate= of > the base RTT since earlier starting flows maintain a standing queue ? > Doug > www.hamilton.ie --=20 Stanislav Shalunov BitTorrent Inc shalunov@bittorrent.com personal: http://shlang.com From saverio.mascolo@gmail.com Fri Apr 3 04:43:16 2009 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 92C143A6C65 for ; Fri, 3 Apr 2009 04:43:15 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.459 X-Spam-Level: X-Spam-Status: No, score=-2.459 tagged_above=-999 required=5 tests=[AWL=0.139, BAYES_00=-2.599, HTML_MESSAGE=0.001] 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 27JKH+xfPIq7 for ; Fri, 3 Apr 2009 04:43:13 -0700 (PDT) Received: from mail-bw0-f169.google.com (mail-bw0-f169.google.com [209.85.218.169]) by core3.amsl.com (Postfix) with ESMTP id A3D5F3A6AD7 for ; Fri, 3 Apr 2009 04:42:43 -0700 (PDT) Received: by bwz17 with SMTP id 17so927617bwz.37 for ; Fri, 03 Apr 2009 04:43:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:date :received:message-id:subject:from:to:cc:content-type; bh=b4xkWW9O7qFAOc/tgWEgSWh2KshNNz4E98n+bnR0iYI=; b=HUwlK1f39qw/Ut0fB59sxdNfwVxVpDibMOuhYgFaOzQ4eWv3QBD3/xeKFEUwfDknH3 FfBMbj9oZ4LTmXBVcoMBi7Lja9p53u2D0uwt1bFJYrFbcucdl59Ov5fwIE64Z/i8oMKx J60eWUR6eJeM3eJ0w8fKg4NZ3g9NHoDZ5LPms= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=rHyJ2zMUm2iQZ7QT7X+k56tUfKFxSdykR7eu9BICUQE//fN0TycNPMxrjFpCA4Eato Ifkb+woExV5KhSgmuyPeriFsQZ4zsqtWfT5lMMzU0UFMkNORn1WYjKRGh4WxZ69Y6UK2 BPE5dhIgfGZILS1sreFRWhu1PUmqquAi90Lps= MIME-Version: 1.0 In-Reply-To: <6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com> References: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk> <6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com> Date: Fri, 3 Apr 2009 13:43:29 +0200 Received: by 10.223.114.74 with SMTP id d10mr974433faq.87.1238759025088; Fri, 03 Apr 2009 04:43:45 -0700 (PDT) Message-ID: From: Saverio Mascolo To: Stanislav Shalunov Content-Type: multipart/alternative; boundary=0016368e2bc9a719b60466a50ff7 Cc: ledbat@ietf.org Subject: Re: [ledbat] Hard-coded delay target? draft-shalunov-ledbat-congestion-00 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: Fri, 03 Apr 2009 11:43:16 -0000 --0016368e2bc9a719b60466a50ff7 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On Fri, Apr 3, 2009 at 8:11 AM, Stanislav Shalunov wrote: > Bob, > > The choice of parameters for congestion control has a degree to which > it's arbitrary. Why does TCP ramp up at a hard-coded 1 MSS/RTT? here i have an answer that it is important to have in mind, especially because of many TCP variants that try a more aggressive probing (some of them replacing TCP NewReno). The increasing at 1 MSS/RTT is the *unique* increase with the property that *only one packet is lost* when the path capacity is hit. This becaus= e of a feedback lag equal to RTT, i.e. after 1 RTT TCP knows if the capacit= y has been hit. This 1 MSS/RTT increment has the very nice property that only one lost packet needs to be retransmitted. TCP variants trying a more aggressive probing experience several packet losses when the capacity is hit. So what happens is that the throughput increases but also retransmissions so that you end up with same goodput but with higher retransmissions, which is not good. These considerations imply that when setting: cwnd+=3Dgain*(T_target-T_forward) it is feasible to choose a low gain in order to have a TCP less than best effort but it is difficult to set a larger gain to have a quick probing in case of gigabit nets without ending in the problem before mentioned (we tried it sometime ago and we give up)! Why > not 3.5 or 0.6? Why does it multiply by 0.5 instead of 7/8 or 0.2 or > 0? again, here a less than best effort can be: cwnd=3Dmin(cwnd/2,BWE*base_rtt) saverio > If a future version of TCP chooses 0.2 and 0.3 as its favorite lucky > numbers while the installed base is at 1 and 0.5, the consequences are > similar. > > While the choice of the particular parametrization for TCP might be > argued to be suboptimal because it doesn't scale with link speed, I'm > not aware of any congestion control mechanism without parameters. > > The mechanism we use scales the target queue linearly with link speed, > as you point out. It's a feature. It enables the mechanism to work > on a variety of bottleneck speeds. If you specify the target in > bytes, you lose on fast links because your delay starts getting lower > than scheduling noise and/or PCI bus jitter and you lose on slow links > because the delay is too large for interactive apps. > > As choice of parameters goes, the choice of the gain is much more > arbitrary than the choice of the target. The gain simply matches TCP > in the worst case. Target is essentially the lowest value than can be > reliably distinguished from 0 on a variety of machines under a variety > of circumstances. > > As a practical matter, 25ms is a substantial reduction from the 1RTT > rule of thumb and so it's reasonable to expect that the deployed gear > will have this much delay. Usually it has far more. (Even at 10Gb/s > and up.) If some gear at an atypical bottleneck doesn't have this > much, the behavior degenerates into TCP. > > It is also a fairly unsubstantial increase relative to RTT and will > remain such unless progress is made on the speed-of-light problem (or > the planet is shrunk?). > > The work you cite never seems to mention minimizing delay as a goal. > It discusses the queuing delay achieved in Theorem 3. And there's a > parameter that controls it (alpha_b^*). > > -- Stas > > > On Wed, Apr 1, 2009 at 3:46 AM, Bob Briscoe > wrote: > > Stas, > > > > This posting repeats what I said in the ledbat w-g meeting in SF, but t= o > the > > whole list and with added reasoning, given the benefit of more time for > > thought. > > > > On balance it seems wrong to aim for a hard-coded delay target (25ms). = I > > understand your reasoning for it in the draft (dividing delay between > > competing flows rather than adding), but there are also stronger scalin= g > > reasons against it... > > > > For 1500B* packets, 25ms represents a standing queue of: > > 1 pkt @ 512kb/s > > 17 pkt @ 8Mb/s > > 50 pkt @ 24Mb/s (some backhaul links today) > > 208 pkt @ 100Mb/s (typical PON access rate today) > > 2080 pkt @ 1Gb/s (increasingly backhaul links are GigE) > > > > As bottleneck links get faster (magically this is happening!), we will > want > > to reduce the hard-coded delay (to save on fast buffer memory and the > power > > it requires). > > > > But if the the algo in draft-00 were changed in the future to aim at 10= ms > > (while the installed base all still aimed at 25ms), the new code would > > always be starved by the installed base. Therefore we would be stuck > forever > > with the number we first thought of: 25ms hard-coded. > > > > Spelling this out longhand, imagine two flows competing: > > Flow N (New) (10ms target) > > Flow L (Legacy) (25ms target) > > > > L drives delay to 25ms > > while both flows have packets to send { > > N reduces rate because delay greater than 10ms > > L sees delay decrease so increases its rate to drive delay to 25ms > > } > > Result: newer algorithm always starves. > > > > IMHO, the algo needs to aim at minimising the congestion delay, not aim > at a > > fixed target (the draft says the former but does the latter). Section 3 > > onwards of [Key04] may help, even tho it's in the context of adapting t= he > > receive window it's still based on delay sensing. I'd be interested to > know > > whether Microsoft's BITS now implements something like this algo. > > > > > > Bob > > > > [* =3D This might be fine if packet size scaled with link speeds, but t= hat > > isn't happening.] > > > > [Key04] Peter Key, Laurent Massouli=E9 and Bing Wang, "Emulating > low-priority > > transport at the application layer: a background transfer service" In: > "ACM > > SIGMETRICS '04/Performance '04: Proceedings of the joint international > > conference on Measurement and modeling of computer systems", pp. 118--1= 29 > > (2004= ) > > > > > > > > > > ________________________________________________________________ > > Bob Briscoe, Networks Research Centre, BT Research > > > > > > -- > Stanislav Shalunov > BitTorrent Inc > shalunov@bittorrent.com > > personal: http://shlang.com > _______________________________________________ > ledbat mailing list > ledbat@ietf.org > https://www.ietf.org/mailman/listinfo/ledbat > --=20 Prof. Saverio Mascolo Dipartimento di Elettrotecnica ed Elettronica Politecnico di Bari Via Orabona 4 70125 Bari Italy Tel. +39 080 5963621 Fax. +39 080 5963410 email:mascolo@poliba.it http://c3lab.poliba.it --0016368e2bc9a719b60466a50ff7 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
On Fri, Apr 3, 2009 at 8:11 AM, Stanislav Sh= alunov <shalunov@bittorrent.com> wrote:
Bob,

The choice of parameters for congestion control has a degree to which
it's arbitrary. =A0Why does TCP ramp up at a hard-coded 1 MSS/RTT? =A0<= /blockquote>

here i have an answer that it is important to have in = mind, especially because of many TCP variants that try a more aggressive pr= obing (some of them replacing TCP NewReno).

The=A0 increasing at 1 MSS/RTT is the unique increase with=A0 th= e property that=A0 only one packet is lost when=A0 the path capacity= is hit. This because of=A0 a feedback lag equal to RTT, i.e. after 1 RTT T= CP=A0 knows if the capacity has been hit. This 1 MSS/RTT increment has the= very nice property that only one lost packet needs to be retransmitted.
TCP variants trying a more aggressive probing experience several packet= losses when the capacity is hit. So what happens is that the throughput in= creases but also retransmissions so that you end up with same goodput but w= ith higher retransmissions, which is not good.


These considerations imply that when setting:

cwnd+=3Dgain*(= T_target-T_forward)

it is feasible to choose a low gain in order=A0 = to have a TCP less than best effort but it is difficult=A0 to set a larger = gain to have a quick probing in case of gigabit nets without ending in the = problem before mentioned (we tried it sometime ago and we give up)!

Why
not 3.5 or 0.6? =A0Why does it multiply by 0.5 instead of 7/8 or 0.2 or
0?

again, here=A0 a less than best effort can be:
<= br>cwnd=3Dmin(cwnd/2,BWE*base_rtt)

saverio



If a future version of TCP chooses 0.2 and 0.3 as its favorite lucky
numbers while the installed base is at 1 and 0.5, the consequences are
similar.

While the choice of the particular parametrization for TCP might be
argued to be suboptimal because it doesn't scale with link speed, I'= ;m
not aware of any congestion control mechanism without parameters.

The mechanism we use scales the target queue linearly with link speed,
as you point out. =A0It's a feature. =A0It enables the mechanism to wor= k
on a variety of bottleneck speeds. =A0If you specify the target in
bytes, you lose on fast links because your delay starts getting lower
than scheduling noise and/or PCI bus jitter and you lose on slow links
because the delay is too large for interactive apps.

As choice of parameters goes, the choice of the gain is much more
arbitrary than the choice of the target. =A0The gain simply matches TCP
in the worst case. =A0Target is essentially the lowest value than can be reliably distinguished from 0 on a variety of machines under a variety
of circumstances.

As a practical matter, 25ms is a substantial reduction from the 1RTT
rule of thumb and so it's reasonable to expect that the deployed gear will have this much delay. =A0Usually it has far more. =A0(Even at 10Gb/s and up.) =A0If some gear at an atypical bottleneck doesn't have this much, the behavior degenerates into TCP.

It is also a fairly unsubstantial increase relative to RTT and will
remain such unless progress is made on the speed-of-light problem (or
the planet is shrunk?).

The work you cite never seems to mention minimizing delay as a goal.
It discusses the queuing delay achieved in Theorem 3. =A0And there's a<= br> parameter that controls it (alpha_b^*).

-- Stas


On Wed, Apr 1, 2009 at 3:46 AM, Bob Briscoe <rbriscoe@jungle.bt.co.uk> wrote:<= br> > Stas,
>
> This posting repeats what I said in the ledbat w-g meeting in SF, but = to the
> whole list and with added reasoning, given the benefit of more time fo= r
> thought.
>
> On balance it seems wrong to aim for a hard-coded delay target (25ms).= I
> understand your reasoning for it in the draft (dividing delay between<= br> > competing flows rather than adding), but there are also stronger scali= ng
> reasons against it...
>
> For 1500B* packets, 25ms represents a standing queue of:
> =A0 1 pkt @ 512kb/s
> =A017 pkt @ =A0 8Mb/s
> =A050 pkt @ =A024Mb/s (some backhaul links today)
> =A0208 pkt @ 100Mb/s (typical PON access rate today)
> 2080 pkt @ =A0 1Gb/s (increasingly backhaul links are GigE)
>
> As bottleneck links get faster (magically this is happening!), we will= want
> to reduce the hard-coded delay (to save on fast buffer memory and the = power
> it requires).
>
> But if the the algo in draft-00 were changed in the future to aim at 1= 0ms
> (while the installed base all still aimed at 25ms), the new code would=
> always be starved by the installed base. Therefore we would be stuck f= orever
> with the number we first thought of: 25ms hard-coded.
>
> Spelling this out longhand, imagine two flows competing:
> =A0 =A0 =A0 =A0Flow N (New) =A0 =A0(10ms target)
> =A0 =A0 =A0 =A0Flow L (Legacy) (25ms target)
>
> L drives delay to 25ms
> while both flows have packets to send {
> =A0 =A0N reduces rate because delay greater than 10ms
> =A0 =A0L sees delay decrease so increases its rate to drive delay to 2= 5ms
> }
> Result: newer algorithm always starves.
>
> IMHO, the algo needs to aim at minimising the congestion delay, not ai= m at a
> fixed target (the draft says the former but does the latter). Section = 3
> onwards of [Key04] may help, even tho it's in the context of adapt= ing the
> receive window it's still based on delay sensing. I'd be inter= ested to know
> whether Microsoft's BITS now implements something like this algo.<= br> >
>
> Bob
>
> [* =3D This might be fine if packet size scaled with link speeds, but = that
> isn't happening.]
>
> [Key04] Peter Key, Laurent Massouli=E9 and Bing Wang, "Emulating = low-priority
> transport at the application layer: a background transfer service"= ; In: "ACM
> SIGMETRICS '04/Performance '04: Proceedings of the joint inter= national
> conference on Measurement and modeling of computer systems", pp. = 118--129
> <http://research.microsoft.com/apps/pubs/default= .aspx?id=3D67381> (2004)
>
>
>
>
> ________________________________________________________________
> Bob Briscoe, =A0 =A0 =A0 =A0 =A0 =A0 =A0 Networks Research Centre, BT = Research
>



--
Stanislav Shalunov
BitTorrent Inc
shalunov@bitto= rrent.com

personal: http://shlang.com=
_______________________________________________=
ledbat mailing list
ledbat@ietf.org = https://www.ietf.org/mailman/listinfo/ledbat



--
Prof. Saver= io Mascolo
Dipartimento di Elettrotecnica ed Elettronica
Politecnico = di Bari
Via Orabona 4
70125 Bari
Italy
Tel. +39 080 5963621 Fax. +39 080 5963410
email:mascolo@poliba.it

http://c3lab.poliba.it

=A0
--0016368e2bc9a719b60466a50ff7-- From lachlan.andrew@gmail.com Sat Apr 4 03:28:05 2009 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 35EDF3A68B8 for ; Sat, 4 Apr 2009 03:28:05 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.938 X-Spam-Level: X-Spam-Status: No, score=-1.938 tagged_above=-999 required=5 tests=[AWL=0.661, 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 7GQfxj52nYFv for ; Sat, 4 Apr 2009 03:28:04 -0700 (PDT) Received: from wa-out-1112.google.com (wa-out-1112.google.com [209.85.146.177]) by core3.amsl.com (Postfix) with ESMTP id 38DC73A6862 for ; Sat, 4 Apr 2009 03:27:48 -0700 (PDT) Received: by wa-out-1112.google.com with SMTP id l35so752485waf.5 for ; Sat, 04 Apr 2009 03:28:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=0oYfyHzIvNAtSSANGQKMnYwZLcAyurLpt3f5jw5jvJ4=; b=SfhthaWisnr+p7fOZdbtcyGJ0ibdF9AwmjcfcjZrFrv0KPX6jawzdMB1kYL8Ylj52E 0es/UQCFIgCxJ9IHF/lg5KYgAKGOnUPv8fYA6KDgivF5ai6ziEfU+gxZZyQsZh6WC6gs LBuzkBLy6HSUkRut3hOE0u+9b7OD4oG10biYg= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=P7rzKVILr9Fep/tlQysQgg+hMM9Jsd2YHOPFQlMaqiTkxW8h1gr2ZjhURd2jY/51t8 iKULldv0X8+Z7DaQB/RzRPqPSjqZVFH+q5bH50f+J4RuZxxUkMxTQO0SH/iK6nzy2J7w jQyWxBPSTn4dYUrDEzdfRRw9cTuUlOYdJKw8w= MIME-Version: 1.0 Received: by 10.114.148.2 with SMTP id v2mr1113655wad.26.1238840931783; Sat, 04 Apr 2009 03:28:51 -0700 (PDT) In-Reply-To: References: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk> <6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com> Date: Sat, 4 Apr 2009 20:28:51 +1000 Message-ID: From: Lachlan Andrew To: Saverio Mascolo Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Cc: ledbat@ietf.org Subject: Re: [ledbat] Hard-coded delay target? draft-shalunov-ledbat-congestion-00 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: Sat, 04 Apr 2009 10:28:05 -0000 Greetings Saverio, 2009/4/3 Saverio Mascolo : > On Fri, Apr 3, 2009 at 8:11 AM, Stanislav Shalunov > wrote: >> >> The choice of parameters for congestion control has a degree to which >> it's arbitrary. Why does TCP ramp up at a hard-coded 1 MSS/RTT? > > The increasing at 1 MSS/RTT is the _unique_ increase with the property that > _only_one_packet_is_lost_ when the path capacity is hit. It is the fastest, but increasing by 1 MSS every 2 RTT also has that property if there is a single flow. More importantly, if there are multiple flows, then 1 MSS/RTT doesn't guarantee a single loss per RTT for a given flow, and so any benefit from that is lost. $0.02, Lachlan -- Lachlan Andrew Centre for Advanced Internet Architectures (CAIA) Swinburne University of Technology, Melbourne, Australia Ph +61 3 9214 4837 From don@sandvine.com Sat Apr 4 07:15:45 2009 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 C63D63A693A for ; Sat, 4 Apr 2009 07:15:45 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -0.495 X-Spam-Level: X-Spam-Status: No, score=-0.495 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_COM=0.553, RDNS_NONE=0.1] 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 hWEI9oQfqAqk for ; Sat, 4 Apr 2009 07:15:45 -0700 (PDT) Received: from gw2.sandvine.com (unknown [64.235.97.59]) by core3.amsl.com (Postfix) with ESMTP id DD6CD3A6784 for ; Sat, 4 Apr 2009 07:15:44 -0700 (PDT) X-MIMEOLE: Produced By Microsoft Exchange V6.5 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Date: Sat, 4 Apr 2009 10:16:45 -0400 Message-ID: In-Reply-To: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: [ledbat] Hard-coded delay target?draft-shalunov-ledbat-congestion-00 Thread-Index: Acm1EEtUD8erfm6nR++14uhr9wiXWwAH4GYg References: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk><6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com> From: "Don Bowman" To: Subject: Re: [ledbat] Hard-coded delay target?draft-shalunov-ledbat-congestion-00 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: Sat, 04 Apr 2009 14:15:45 -0000 2009/4/3 Saverio Mascolo : > On Fri, Apr 3, 2009 at 8:11 AM, Stanislav Shalunov > wrote: >> >> The choice of parameters for congestion control has a degree to which >> it's arbitrary. Why does TCP ramp up at a hard-coded 1 MSS/RTT? > > The increasing at 1 MSS/RTT is the _unique_ increase with the property that > _only_one_packet_is_lost_ when the path capacity is hit. Has anyone taken a stab @ a model in NS? [http://www.isi.edu/nsnam/ns/]. It would help answer the what-ifs of timing and interactions with other protocols I think. From arnaud.legout@inria.fr Sun Apr 5 12:47:56 2009 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 C7FEE3A6AD3 for ; Sun, 5 Apr 2009 12:47:56 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -4.87 X-Spam-Level: X-Spam-Status: No, score=-4.87 tagged_above=-999 required=5 tests=[AWL=-1.221, BAYES_50=0.001, HELO_EQ_FR=0.35, 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 cFKMfMe7e7y1 for ; Sun, 5 Apr 2009 12:47:51 -0700 (PDT) Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by core3.amsl.com (Postfix) with ESMTP id D499B3A6ACA for ; Sun, 5 Apr 2009 12:47:50 -0700 (PDT) X-IronPort-AV: E=Sophos;i="4.39,326,1235948400"; d="scan'208";a="25681573" Received: from vau06-2-82-238-188-18.fbx.proxad.net (HELO [192.168.0.11]) ([82.238.188.18]) by mail3-relais-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 05 Apr 2009 21:48:53 +0200 Message-ID: <49D90B25.40409@inria.fr> Date: Sun, 05 Apr 2009 21:48:53 +0200 From: Arnaud Legout User-Agent: Thunderbird 2.0.0.21 (Windows/20090302) MIME-Version: 1.0 To: Don Bowman References: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk><6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: ledbat@ietf.org Subject: Re: [ledbat] Hard-coded delay target?draft-shalunov-ledbat-congestion-00 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: Sun, 05 Apr 2009 19:47:56 -0000 Hi Don Bowman wrote: > Has anyone taken a stab @ a model in NS? [http://www.isi.edu/nsnam/ns/]. > It would > help answer the what-ifs of timing and interactions with other protocols > I think. > doing simulations involving TCP in ns-2 is simply a bad idea, as ns-3 has been released. Why? Because in ns-3 you have the real TCP BSD stack in it. Ns-3 is not a simple evolution of ns-2, it is a complete rewrite with a new design based on the experience gathered on ns-2. Here is the URL for ns-3 http://www.nsnam.org/ Regards, Arnaud. From lachlan.andrew@gmail.com Mon Mar 30 16:49:42 2009 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 F0BCE3A69B3 for ; Mon, 30 Mar 2009 16:49:42 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.278 X-Spam-Level: X-Spam-Status: No, score=-1.278 tagged_above=-999 required=5 tests=[AWL=-0.441, BAYES_00=-2.599, MISSING_SUBJECT=1.762] 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 S03B3MECWZ13 for ; Mon, 30 Mar 2009 16:49:42 -0700 (PDT) Received: from wa-out-1112.google.com (wa-out-1112.google.com [209.85.146.178]) by core3.amsl.com (Postfix) with ESMTP id 72CB63A67DB for ; Mon, 30 Mar 2009 16:49:42 -0700 (PDT) Received: by wa-out-1112.google.com with SMTP id l35so1274057waf.5 for ; Mon, 30 Mar 2009 16:50:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:date:message-id:subject :from:to:content-type:content-transfer-encoding; bh=bIkL3j1SUti+mxRknWXsGzjEHfZ++LfAOrCAj6OvBfk=; b=vKimQtmxoNxsCY93lY0HUT5RBvQ8pcKthFKzrWMymal/+oltaSZpjGCZPBb46Cl5/B Rm/Fo2azbSVZnW6eIZIziJ0s3hbbFyTNbg+dQBxApk/QtVEr0deejnJLIsowYhhF9BqK HjDg0aXisnN52RweO4gSazuBNKvuOhnjzi7to= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:date:message-id:subject:from:to:content-type :content-transfer-encoding; b=vCyD/Z4oNal9kE0I9VcVt7gPkyWXLLeefypZD6lCC2qEXpm2n+7DKxHtTzWAkCslJB XkbV6/9wP/ToCASj86qOFVLwH14vpfZ14hLguKE9QS8WvTVCKHl9o8nDrBmZ9fPSVlJx xxsgz4Cfbm8N85yRqDI73ox+42i2d7Mg8mEnI= MIME-Version: 1.0 Received: by 10.115.16.1 with SMTP id t1mr3924138wai.58.1238457040827; Mon, 30 Mar 2009 16:50:40 -0700 (PDT) Date: Tue, 31 Mar 2009 10:50:40 +1100 Message-ID: From: Lachlan Andrew To: ledbat@ietf.org Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Mon, 06 Apr 2009 13:28:41 -0700 Subject: [ledbat] (no subject) 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: Mon, 30 Mar 2009 23:49:43 -0000 subscribe From saverio.mascolo@gmail.com Tue Apr 7 09:13:47 2009 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 A12C33A67A6 for ; Tue, 7 Apr 2009 09:13:47 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.506 X-Spam-Level: X-Spam-Status: No, score=-2.506 tagged_above=-999 required=5 tests=[AWL=0.092, BAYES_00=-2.599, HTML_MESSAGE=0.001] 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 5qowpF9noL6y for ; Tue, 7 Apr 2009 09:13:46 -0700 (PDT) Received: from fk-out-0910.google.com (fk-out-0910.google.com [209.85.128.184]) by core3.amsl.com (Postfix) with ESMTP id EB4293A6DC1 for ; Tue, 7 Apr 2009 09:09:49 -0700 (PDT) Received: by fk-out-0910.google.com with SMTP id 18so1090389fkq.5 for ; Tue, 07 Apr 2009 09:10:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :from:date:message-id:subject:to:cc:content-type; bh=5muHfgeeLaBTXuY0qsgqV5bYethDThz/8nzFTWS3CAw=; b=AtciKwlpNUngY8lPqpheVWt5PujZuFVkJED3YAyUbjBCbFlZ0+J5JPCRf9KxTxr/lB 8kbW3lVAvzaPQvzCg3aby/7/flHVxV5LCpepdzj2+v0ADyh7PuOs8/SuIJRt2XZ+I0OJ LYE+EMyI2K3Xxf/EyNH1KBy12rAy1jGV+/NGo= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; b=d4RCQ3olSe5F3KxBOEMYUVyOhbWo+t7Mt3vALOl6rL2zIPvblQ5bPcf4IDjB002edI bJjYDGymFdvmpl8gcNbc7kuNPYjf0vb3drtBcTYYmuJj9rrxAy4ZKlB9Y2zjGIUGdOxF 2sA5httcaGews/AGj3pPFX1tNwXXfb2QEJrk8= MIME-Version: 1.0 Received: by 10.223.104.74 with SMTP id n10mr170326fao.5.1239120655229; Tue, 07 Apr 2009 09:10:55 -0700 (PDT) In-Reply-To: References: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk> <6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com> From: Saverio Mascolo Date: Tue, 7 Apr 2009 18:10:40 +0200 Message-ID: To: Lachlan Andrew Content-Type: multipart/alternative; boundary=001636c5b1c77d27680466f94284 Cc: ledbat@ietf.org Subject: Re: [ledbat] Hard-coded delay target? draft-shalunov-ledbat-congestion-00 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, 07 Apr 2009 16:13:47 -0000 --001636c5b1c77d27680466f94284 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit hi, what about keeping track of the number of uploading connections N and using the setting: on ack reception: cwnd+=(1/cwnd)*1/N in any of the tcp connections open by the p2p client? this would make the p2p application equivalent to one TCP uploading connection. saverio On Sat, Apr 4, 2009 at 12:28 PM, Lachlan Andrew wrote: > Greetings Saverio, > > 2009/4/3 Saverio Mascolo : > > On Fri, Apr 3, 2009 at 8:11 AM, Stanislav Shalunov < > shalunov@bittorrent.com> > > wrote: > >> > >> The choice of parameters for congestion control has a degree to which > >> it's arbitrary. Why does TCP ramp up at a hard-coded 1 MSS/RTT? > > > > The increasing at 1 MSS/RTT is the _unique_ increase with the property > that > > _only_one_packet_is_lost_ when the path capacity is hit. > > It is the fastest, but increasing by 1 MSS every 2 RTT also has that > property if there is a single flow. More importantly, if there are > multiple flows, then 1 MSS/RTT doesn't guarantee a single loss per RTT > for a given flow, and so any benefit from that is lost. > > $0.02, > Lachlan > > -- > Lachlan Andrew Centre for Advanced Internet Architectures (CAIA) > Swinburne University of Technology, Melbourne, Australia > > Ph +61 3 9214 4837 > -- Prof. Saverio Mascolo Dipartimento di Elettrotecnica ed Elettronica Politecnico di Bari Via Orabona 4 70125 Bari Italy Tel. +39 080 5963621 Fax. +39 080 5963410 email:mascolo@poliba.it http://c3lab.poliba.it ================================= This message may contain confidential and/or legally privileged information. If you are not the intended recipient of the message, please destroy it. Any unauthorized dissemination, distribution, or copying of the material in this message, and any attachments to the message, is strictly forbidden. --001636c5b1c77d27680466f94284 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable hi,

what about keeping track of the number of uploading connections = N and using the setting:

on ack reception:
cwnd+=3D(1/cwnd)*1/N
in any of the tcp connections open by the p2p client? this would make= the p2p application equivalent to one TCP uploading connection.

saverio

On Sat, Apr 4, 2009 at 12:28 = PM, Lachlan Andrew <lachlan.andrew@gmail.com> wrote:
Greetings Saverio,

2009/4/3 Saverio Mascolo <s= averio.mascolo@gmail.com>:
> On Fri, Apr 3, 2009 at 8:11 AM, Stanislav Shalunov &= lt;shalunov@bittorrent.com&g= t;
> wrote:
>>
>> The choice of parameters for congestion co= ntrol has a degree to which
>> it's arbitrary. =A0Why does TCP ramp up at a hard-coded 1 MSS/= RTT?
>
> The =A0increasing at 1 MSS/RTT is the _unique_= increase with =A0the property that
> _only_one_packet_is_lost_ when =A0the path capacity is hit.

It is the fastest, but increasing by 1 MSS =A0every 2 RTT also has th= at
property if there is a single flow. =A0More importantly, if there are
multiple flows, then 1 MSS/RTT doesn't guarantee a single loss per RTT<= br> for a given flow, and so any benefit from that is lost.

$0.02,
Lachlan

--
Lachlan Andrew =A0Centre for Advanced Internet Architectures (CAIA)
Swinburne University of Technology, Melbourne, Australia
<http:/= /caia.swin.edu.au/cv/landrew> <http://netlab.caltech.edu/lachlan>
Ph +61 3 9214 4837



--
Prof. Saverio Ma= scolo
Dipartimento di Elettrotecnica ed Elettronica
Politecnico di Ba= ri
Via Orabona 4
70125 Bari
Italy
Tel. +39 080 5963621
Fax.= +39 080 5963410
email:mascolo@poliba.it
http://c3lab.poliba.it

=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
This message may contain confidential an= d/or legally privileged information.
=A0If you are not the intended recipient of the message, please destroy it= .
Any unauthorized dissemination, distribution, or copying of the mater= ial in
this message, and any attachments to the message, is strictly fo= rbidden.
--001636c5b1c77d27680466f94284-- From rbriscoe@jungle.bt.co.uk Wed Apr 8 11:04:04 2009 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 8B7CF3A6E8F for ; Wed, 8 Apr 2009 11:04:04 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -0.471 X-Spam-Level: X-Spam-Status: No, score=-0.471 tagged_above=-999 required=5 tests=[AWL=-0.954, BAYES_50=0.001, DNS_FROM_RFC_BOGUSMX=1.482, RCVD_IN_DNSWL_LOW=-1] 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 k-ecapmxdebd for ; Wed, 8 Apr 2009 11:03:57 -0700 (PDT) Received: from smtp4.smtp.bt.com (smtp4.smtp.bt.com [217.32.164.151]) by core3.amsl.com (Postfix) with ESMTP id 8136628C2CE for ; Wed, 8 Apr 2009 11:02:21 -0700 (PDT) Received: from i2kc06-ukbr.domain1.systemhost.net ([193.113.197.70]) by smtp4.smtp.bt.com with Microsoft SMTPSVC(6.0.3790.3959); Wed, 8 Apr 2009 19:03:27 +0100 Received: from cbibipnt05.iuser.iroot.adidom.com ([147.149.196.177]) by i2kc06-ukbr.domain1.systemhost.net with Microsoft SMTPSVC(6.0.3790.1830); Wed, 8 Apr 2009 19:03:27 +0100 Received: From bagheera.jungle.bt.co.uk ([132.146.168.158]) by cbibipnt05.iuser.iroot.adidom.com (WebShield SMTP v4.5 MR1a P0803.399); id 1239213806217; Wed, 8 Apr 2009 19:03:26 +0100 Received: from mut.jungle.bt.co.uk ([10.215.130.87]) by bagheera.jungle.bt.co.uk (8.13.5/8.12.8) with ESMTP id n38I3N0X029206; Wed, 8 Apr 2009 19:03:23 +0100 Message-Id: <200904081803.n38I3N0X029206@bagheera.jungle.bt.co.uk> X-Mailer: QUALCOMM Windows Eudora Version 7.1.0.9 Date: Wed, 08 Apr 2009 19:03:21 +0100 To: Stanislav Shalunov From: Bob Briscoe In-Reply-To: <6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.co m> References: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk> <6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1"; format=flowed Content-Transfer-Encoding: quoted-printable X-Scanned-By: MIMEDefang 2.56 on 132.146.168.158 X-OriginalArrivalTime: 08 Apr 2009 18:03:27.0898 (UTC) FILETIME=[517307A0:01C9B874] Cc: ledbat@ietf.org Subject: Re: [ledbat] Hard-coded delay target? draft-shalunov-ledbat-congestion-00 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: Wed, 08 Apr 2009 18:04:04 -0000 Stas, Pointing to other protocols that don't scale=20 isn't a good reason for deliberately designing a=20 new one that we know from the start won't scale=20 into the future. But I guess it's up to me /=20 others to come up with a more adaptive approach if we can. more inline... At 07:11 03/04/2009, Stanislav Shalunov wrote: >Bob, > >The choice of parameters for congestion control has a degree to which >it's arbitrary. Why does TCP ramp up at a hard-coded 1 MSS/RTT? Why >not 3.5 or 0.6? Why does it multiply by 0.5 instead of 7/8 or 0.2 or >0? > >If a future version of TCP chooses 0.2 and 0.3 as its favorite lucky >numbers while the installed base is at 1 and 0.5, the consequences are >similar. > >While the choice of the particular parametrization for TCP might be >argued to be suboptimal because it doesn't scale with link speed, I'm >not aware of any congestion control mechanism without parameters. I believe it's particularly important to avoid=20 non-dimensionless parameters (ie. to avoid=20 parameters with units). Wherever there is one,=20 I'd rather it was either adaptive, or a parameter=20 under application control. But enough of these generalities... >The mechanism we use scales the target queue linearly with link speed, >as you point out. It's a feature. It enables the mechanism to work >on a variety of bottleneck speeds. If you specify the target in >bytes, you lose on fast links because your delay starts getting lower >than scheduling noise and/or PCI bus jitter and you lose on slow links >because the delay is too large for interactive apps. All understood. I certainly wasn't proposing we set a buffer target in= bytes. But to me it's short-sighted and defeatist to say=20 "operating systems will never reliably be able to=20 measure delays to finer granularity than Xms".=20 Just because they usually can't today. The part I don't like is increasing rate to hit a=20 target delay. I'd prefer that the algo=20 continually increases rate (w per window say)=20 whether or not there's delay, and decreases rate=20 whenever it measures delay. Then the two will=20 balance at the *lowest measureable* delay delta.=20 I'd like to eventually see w under app-control=20 through the API (that argument requires another=20 thread). But, if I don't win that argument, w could initially be hard-coded. This has the property that the more flows compete=20 for the same queue, the more the delay will be. I=20 know you don't like that, but I actually think=20 it's a desirable property. It automatically=20 solves sharing of bottlnecks and problems like=20 the late-comers disadvantage (separate thread=20 with Doug Leith). It's a proven approach in=20 nearly every congestion control we have. Imagine large numbers of flows share a hard-coded=20 delay target, all with fixed gain. Imagine the=20 measured delay is slightly above target. Each one=20 makes a small rate reduction and gets surprised=20 that the delay has reduced a lot more than they=20 expected (because everyone else made a similar=20 reduction). So they all increase more than they=20 reduced. And the delay shoots up. Result, unstable oscillation? I know, this depends on the relative RTTs etc... I'm not saying there *is* a problem. It just=20 seems a rate *increase* towards a hard-coded=20 delay target is unnecessary. We only have to=20 *reduce* in the presence of *any* measurable=20 delay. Doing otherwise moves into unnecessarily=20 uncharted territory that should have warning signs "Here be monsters". >As choice of parameters goes, the choice of the gain is much more >arbitrary than the choice of the target. The gain simply matches TCP >in the worst case. Target is essentially the lowest value than can be >reliably distinguished from 0 on a variety of machines under a variety >of circumstances. Understood >As a practical matter, 25ms is a substantial reduction from the 1RTT >rule of thumb and so it's reasonable to expect that the deployed gear >will have this much delay. Usually it has far more. (Even at 10Gb/s >and up.) I doubt the 1RTT rule of thumb is used much these=20 days. It would require ridiculously large amounts=20 of buffer memory on hi-speed interfaces. Back in=20 2005, when I last asked, I discovered BT folks=20 were generally configuring buffer sizes in a way=20 that grew with about the sq-root of link speed=20 (not deliberately following Nick McKeown's advice=20 that came out around then, this was just=20 happenchance even tho they knew about McKeown's papers). You might configure about 25ms of buffer on a=20 155Mb/s interface these days. But on a GigE I'm=20 sure a good config would be less. For 10Gb/s=20 interfaces, what's the evidence for them being=20 config'd with far more than 25ms? Assuming 1500B=20 pkt size, this is about 21,000 packets of buffer. However, the point is that the trend for the=20 future is to reduce buffer memory on faster=20 interfaces, to reduce power requirements, given=20 so much buffer is now believed not to actually be=20 necessary. But I should also re-run my 2005 survey. >If some gear at an atypical bottleneck doesn't have this >much, the behavior degenerates into TCP. That sounds good if you say it quickly. But it's=20 actually a failure. It means all the flows one=20 expected to scavenge quietly in the background,=20 actually compete on equal terms in the foreground. Do you think of LEDBAT as a solution with=20 long-term relevance for sharing any bottleneck?=20 Or do you think of it as a stop-gap for sharing=20 low speed bottlenecks? I don't use the term=20 stop-gap disparagingly. I just mean something=20 that loses relevance in 5-10years, rather than=20 something that one expects will last as long as TCP has. >It is also a fairly unsubstantial increase relative to RTT and will >remain such unless progress is made on the speed-of-light problem (or >the planet is shrunk?). I keep on constant alert for breakthroughs in=20 these areas. But I'm currently more worried that=20 a 25ms target is an unnecessarily large choice,=20 given I don't believe we have to make a choice=20 anyway (see alternative approach above). >The work you cite never seems to mention minimizing delay as a goal. >It discusses the queuing delay achieved in Theorem 3. And there's a >parameter that controls it (alpha_b^*). Queuing delay is inside the alpha variable. On=20 second thoughts, it's prob not worth using that=20 paper to shed light on anything tho - too much=20 generality is included, which makes it too=20 complex as a basis for discussion here. Bob >-- Stas > > >On Wed, Apr 1, 2009 at 3:46 AM, Bob Briscoe = wrote: > > Stas, > > > > This posting repeats what I said in the=20 > ledbat w-g meeting in SF, but to the > > whole list and with added reasoning, given the benefit of more time for > > thought. > > > > On balance it seems wrong to aim for a hard-coded delay target (25ms). I > > understand your reasoning for it in the draft (dividing delay between > > competing flows rather than adding), but there are also stronger scaling > > reasons against it... > > > > For 1500B* packets, 25ms represents a standing queue of: > > 1 pkt @ 512kb/s > > 17 pkt @ 8Mb/s > > 50 pkt @ 24Mb/s (some backhaul links today) > > 208 pkt @ 100Mb/s (typical PON access rate today) > > 2080 pkt @ 1Gb/s (increasingly backhaul links are GigE) > > > > As bottleneck links get faster (magically this is happening!), we will= want > > to reduce the hard-coded delay (to save on fast buffer memory and the= power > > it requires). > > > > But if the the algo in draft-00 were changed in the future to aim at= 10ms > > (while the installed base all still aimed at 25ms), the new code would > > always be starved by the installed base.=20 > Therefore we would be stuck forever > > with the number we first thought of: 25ms hard-coded. > > > > Spelling this out longhand, imagine two flows competing: > > Flow N (New) (10ms target) > > Flow L (Legacy) (25ms target) > > > > L drives delay to 25ms > > while both flows have packets to send { > > N reduces rate because delay greater than 10ms > > L sees delay decrease so increases its rate to drive delay to 25ms > > } > > Result: newer algorithm always starves. > > > > IMHO, the algo needs to aim at minimising the=20 > congestion delay, not aim at a > > fixed target (the draft says the former but does the latter). Section 3 > > onwards of [Key04] may help, even tho it's in the context of adapting= the > > receive window it's still based on delay sensing. I'd be interested to= know > > whether Microsoft's BITS now implements something like this algo. > > > > > > Bob > > > > [* =3D This might be fine if packet size scaled with link speeds, but= that > > isn't happening.] > > > > [Key04] Peter Key, Laurent Massouli=E9 and Bing Wang, "Emulating= low-priority > > transport at the application layer: a background transfer service" In:= "ACM > > SIGMETRICS '04/Performance '04: Proceedings of the joint international > > conference on Measurement and modeling of computer systems", pp.= 118--129 > > (2004) > > > > > > > > > > ________________________________________________________________ > > Bob Briscoe, Networks Research Centre, BT Research > > > > > >-- >Stanislav Shalunov >BitTorrent Inc >shalunov@bittorrent.com > >personal: http://shlang.com ________________________________________________________________ Bob Briscoe, Networks Research Centre, BT Research=20 From lachlan.andrew@gmail.com Wed Apr 8 15:19:15 2009 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 94E1B3A6E75 for ; Wed, 8 Apr 2009 15:19:15 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.07 X-Spam-Level: X-Spam-Status: No, score=-2.07 tagged_above=-999 required=5 tests=[AWL=0.529, 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 Lt7FzGFiefbY for ; Wed, 8 Apr 2009 15:19:14 -0700 (PDT) Received: from wa-out-1112.google.com (wa-out-1112.google.com [209.85.146.181]) by core3.amsl.com (Postfix) with ESMTP id 3F3EE3A6BA1 for ; Wed, 8 Apr 2009 15:19:14 -0700 (PDT) Received: by wa-out-1112.google.com with SMTP id l35so161029waf.5 for ; Wed, 08 Apr 2009 15:20:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=V3GibQR/cN72MDe3UL8v/oMc8HCxYwrC2IpqUhnjJ6E=; b=U/f4K+Y41mxYr5/TwY9bH8W/X0ZNqmdej2GcAaylVRlUVVy/gQaIYfYA86nyqv6GIu 0xXrd85TN6aWioUqxNef7cDL/AU6jldAATSs3Uht3n7IaIdbEqUJmax/7DtqF+DM+/V1 p3n9h3gsdvUS9Ti6kE+n7qx2Q4EM6OIOoTrzw= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; b=lgyUZxKq13cz5tsPraKMuAAao+LPFnSJW5LCTZazKQM/O9CDAUp1b1IJh2kYwxYiDb 4rlC5uvf2xZAzwjFfD0knzhZzDVw+WC5qEeQuva5xx6R5+IVJVEjxCFWN+9qR817x5GF xUbqdYUvihYCzY8HmV1ZfHmTwTEaqWxuYaST4= MIME-Version: 1.0 Received: by 10.114.25.19 with SMTP id 19mr1008785way.89.1239229221698; Wed, 08 Apr 2009 15:20:21 -0700 (PDT) In-Reply-To: <200904081803.n38I3N0X029206@bagheera.jungle.bt.co.uk> References: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk> <6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com> <200904081803.n38I3N0X029206@bagheera.jungle.bt.co.uk> Date: Thu, 9 Apr 2009 08:20:21 +1000 Message-ID: From: Lachlan Andrew To: Bob Briscoe Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Cc: ledbat@ietf.org Subject: Re: [ledbat] Hard-coded delay target? draft-shalunov-ledbat-congestion-00 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: Wed, 08 Apr 2009 22:19:15 -0000 Greetings Bob, 2009/4/9 Bob Briscoe : > > At 07:11 03/04/2009, Stanislav Shalunov wrote: >> If you specify the target in >> bytes, you lose on fast links because your delay starts getting lower >> than scheduling noise and/or PCI bus jitter and you lose on slow links >> because the delay is too large for interactive apps. > > All understood. I certainly wasn't proposing we set a buffer target in > bytes. > > But to me it's short-sighted and defeatist to say "operating systems will > never reliably be able to measure delays to finer granularity than Xms". > Just because they usually can't today. It is easy to *measure* delay, the questions is "what is the source of the delay?" If delay is a sign of congestion, then it is justifiable to back off. If it is just jitter (something falling out of a cache along the route, perhaps) then the OS has no way to know. If jitter is consistently going down, then you're right about being short sighted. If jitter isn't going down, then we shouldn't design a protocol which assumes it will. Does anyone on the list have data about trends in jitter? > The part I don't like is increasing rate to hit a target delay. I'd prefer > that the algo continually increases rate (w per window say) whether or not > there's delay, and decreases rate whenever it measures delay. Then the two > will balance at the *lowest measureable* delay delta. That sounds like Doug's "delay AIMD". He and I have been discussing that, and it seems quite sensitive to asymmetric jitter. If one flow (with jitter) backs off noticeably when it senses a particular threshold of delay then the flow without jitter never gets to see the threshold met, and so never backs off until the jittered flow is starved, and then the cycle repeats. That might be avoided if the backoff is very small when delay is experienced (like Vegas). Also, the Linux stack has occasional very long delays of many ms; should it set a "lowest measureable" target which is longer than these very long delays, because otherwise the might be spurious? > I'm currently > more worried that a 25ms target is an unnecessarily large choice, given I > don't believe we have to make a choice anyway I agree that 25ms is an unnecessarily large delay, since jitter is typically in the 1ms range. $0.02, Lachlan -- Lachlan Andrew Centre for Advanced Internet Architectures (CAIA) Swinburne University of Technology, Melbourne, Australia Ph +61 3 9214 4837 From don@sandvine.com Wed Apr 8 19:42:56 2009 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 224433A6B99 for ; Wed, 8 Apr 2009 19:42:56 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.547 X-Spam-Level: X-Spam-Status: No, score=-1.547 tagged_above=-999 required=5 tests=[AWL=1.052, 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 USpCesayBa4A for ; Wed, 8 Apr 2009 19:42:55 -0700 (PDT) Received: from gw2.sandvine.com (ip59.sandvine.com [64.235.97.59]) by core3.amsl.com (Postfix) with ESMTP id 476013A6AB8 for ; Wed, 8 Apr 2009 19:42:54 -0700 (PDT) X-MIMEOLE: Produced By Microsoft Exchange V6.5 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Date: Wed, 8 Apr 2009 22:43:58 -0400 Message-ID: In-Reply-To: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: [ledbat] Hard-coded delay target?draft-shalunov-ledbat-congestion-00 Thread-Index: Acm4mEuQ7q7E04dER0CH1MwYAPPfWwAIzFPg References: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk><6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com><200904081803.n38I3N0X029206@bagheera.jungle.bt.co.uk> From: "Don Bowman" To: "Lachlan Andrew" , "Bob Briscoe" Cc: ledbat@ietf.org Subject: Re: [ledbat] Hard-coded delay target?draft-shalunov-ledbat-congestion-00 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: Thu, 09 Apr 2009 02:42:56 -0000 Andrew Lachlan wrote: >2009/4/9 Bob Briscoe : >> >> At 07:11 03/04/2009, Stanislav Shalunov wrote: >>> If you specify the target in >>> bytes, you lose on fast links because your delay starts getting lower >>> than scheduling noise and/or PCI bus jitter and you lose on slow links >>> because the delay is too large for interactive apps. >> >> All understood. I certainly wasn't proposing we set a buffer target in >> bytes. >> >> But to me it's short-sighted and defeatist to say "operating systems will >> never reliably be able to measure delays to finer granularity than Xms". >> Just because they usually can't today. > >It is easy to *measure* delay, the questions is "what is the source of >the delay?" If delay is a sign of congestion, then it is justifiable >to back off. If it is just jitter (something falling out of a cache >along the route, perhaps) then the OS has no way to know. Watch out for mobile networks where handoffs cause change in delay, Changes in error correction (that tunnel you are driving through) cause delay changes, etc. The network may also be able to dynamically shift bandwidth from upstream to downstream (e.g. wimax, lte). The latency is also much higher on 3G networks than on fixed. Also dynamic bandwidth networks don't always have buffering associated. An example, the 'powerboost' used in cable is a token-credit model which allows higher than nominal rates to be achieved until the sender/receiver is out of credits, and then it reverts to nominal rate. No buffer depth changes occur, the scheduler just changes rate suddenly. This has sometimes caused oscillations with media applications that try to 'measure' the rate of the line, and then pick a codec. ... >> I'm currently >> more worried that a 25ms target is an unnecessarily large choice, given I >> don't believe we have to make a choice anyway > >I agree that 25ms is an unnecessarily large delay, since jitter is >typically in the 1ms range. I think this (1ms) is pretty low for mobile. I also think it's pretty low for fixed. Measurements I have done on RTP jitter (e.g. voip) show more like 10ms of jitter for non-facilities-based voip, and I believe should be consistent for TCP. The proposed initial use of ledbat is e.g. p2p file sharing. In this application, the other endpoint is as likely to be on the far side of the world as the far side of your street, so I think we will see a pretty wide dynamic range in both jitter (from the high hop count) and latency. From rbriscoe@jungle.bt.co.uk Thu Apr 9 05:49:26 2009 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 EC89A3A6B94 for ; Thu, 9 Apr 2009 05:49:26 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.665 X-Spam-Level: X-Spam-Status: No, score=-1.665 tagged_above=-999 required=5 tests=[AWL=0.452, BAYES_00=-2.599, DNS_FROM_RFC_BOGUSMX=1.482, RCVD_IN_DNSWL_LOW=-1] 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 7twyd7MwMeZ2 for ; Thu, 9 Apr 2009 05:49:20 -0700 (PDT) Received: from smtp4.smtp.bt.com (smtp4.smtp.bt.com [217.32.164.151]) by core3.amsl.com (Postfix) with ESMTP id C86523A67C0 for ; Thu, 9 Apr 2009 05:49:19 -0700 (PDT) Received: from i2kc08-ukbr.domain1.systemhost.net ([193.113.197.71]) by smtp4.smtp.bt.com with Microsoft SMTPSVC(6.0.3790.3959); Thu, 9 Apr 2009 13:50:27 +0100 Received: from cbibipnt08.iuser.iroot.adidom.com ([147.149.100.81]) by i2kc08-ukbr.domain1.systemhost.net with Microsoft SMTPSVC(6.0.3790.1830); Thu, 9 Apr 2009 13:50:26 +0100 Received: From bagheera.jungle.bt.co.uk ([132.146.168.158]) by cbibipnt08.iuser.iroot.adidom.com (WebShield SMTP v4.5 MR1a P0803.399); id 1239281425467; Thu, 9 Apr 2009 13:50:25 +0100 Received: from mut.jungle.bt.co.uk ([10.73.81.25]) by bagheera.jungle.bt.co.uk (8.13.5/8.12.8) with ESMTP id n39CoNlg018456; Thu, 9 Apr 2009 13:50:24 +0100 Message-Id: <200904091250.n39CoNlg018456@bagheera.jungle.bt.co.uk> X-Mailer: QUALCOMM Windows Eudora Version 7.1.0.9 Date: Thu, 09 Apr 2009 12:53:01 +0100 To: Stanislav Shalunov From: Bob Briscoe In-Reply-To: References: <200904011045.n31AjtGg008364@bagheera.jungle.bt.co.uk> <6c82d1360904022311k28c5dfa2g160ec6abb92d5190@mail.gmail.com> <200904081803.n38I3N0X029206@bagheera.jungle.bt.co.uk> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Scanned-By: MIMEDefang 2.56 on 132.146.168.158 X-OriginalArrivalTime: 09 Apr 2009 12:50:26.0560 (UTC) FILETIME=[C1500800:01C9B911] Cc: ledbat@ietf.org Subject: Re: [ledbat] Hard-coded delay target?draft-shalunov-ledbat-congestion-00 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: Thu, 09 Apr 2009 12:49:27 -0000 Stas, OK, taking what Lachlan has said, I now accept we need *a* hard-coded threshold below which we assume delay variation isn't necessarily congestion. 1/ The value is TBA. Perhaps 25ms, perhaps 5ms. Whatever we choose will always hurt in some cases (e.g. Don's); the choice is about which ones are corner cases we can live with. E.g. During mobile handover, there will be a period during which the controller gets confused. It will sort itself out in time. Is that important? Dunno... It's for debate. I'd say it's something we can live with traded against the benefit of exploiting congestion info from delay 'most' of the time. 2/ But this still leaves questions about the core part of the control algo. However, these are more appropriate to Doug Lieth's thread on competing flows, so I'll shift to there. Bob At 03:43 09/04/2009, Don Bowman wrote: >Andrew Lachlan wrote: > >2009/4/9 Bob Briscoe : > >> > >> At 07:11 03/04/2009, Stanislav Shalunov wrote: > >>> If you specify the target in > >>> bytes, you lose on fast links because your delay starts getting >lower > >>> than scheduling noise and/or PCI bus jitter and you lose on slow >links > >>> because the delay is too large for interactive apps. > >> > >> All understood. I certainly wasn't proposing we set a buffer target >in > >> bytes. > >> > >> But to me it's short-sighted and defeatist to say "operating systems >will > >> never reliably be able to measure delays to finer granularity than >Xms". > >> Just because they usually can't today. > > > >It is easy to *measure* delay, the questions is "what is the source of > >the delay?" If delay is a sign of congestion, then it is justifiable > >to back off. If it is just jitter (something falling out of a cache > >along the route, perhaps) then the OS has no way to know. > >Watch out for mobile networks where handoffs cause change in delay, >Changes in error correction (that tunnel you are driving through) cause >delay changes, etc. The network may also be able to dynamically shift >bandwidth from upstream to downstream (e.g. wimax, lte). >The latency is also much higher on 3G networks than on fixed. > >Also dynamic bandwidth networks don't always have buffering >associated. An example, the 'powerboost' used in cable is a token-credit >model which allows higher than nominal rates to be achieved until >the sender/receiver is out of credits, and then it reverts to nominal >rate. No buffer depth changes occur, the scheduler just changes rate >suddenly. This has sometimes caused oscillations with media applications >that try to 'measure' the rate of the line, and then pick a codec. > > ... > > >> I'm currently > >> more worried that a 25ms target is an unnecessarily large choice, >given I > >> don't believe we have to make a choice anyway > > > >I agree that 25ms is an unnecessarily large delay, since jitter is > >typically in the 1ms range. > >I think this (1ms) is pretty low for mobile. I also think it's pretty >low for fixed. >Measurements I have done on RTP jitter (e.g. voip) show more like 10ms >of jitter for non-facilities-based voip, and I believe should be >consistent >for TCP. > >The proposed initial use of ledbat is e.g. p2p file sharing. In this >application, >the other endpoint is as likely to be on the far side of the world as >the >far side of your street, so I think we will see a pretty wide dynamic >range >in both jitter (from the high hop count) and latency. ________________________________________________________________ Bob Briscoe, Networks Research Centre, BT Research From rbriscoe@jungle.bt.co.uk Thu Apr 9 05:49:34 2009 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 B7D123A6C46 for ; Thu, 9 Apr 2009 05:49:34 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.71 X-Spam-Level: X-Spam-Status: No, score=-1.71 tagged_above=-999 required=5 tests=[AWL=0.407, BAYES_00=-2.599, DNS_FROM_RFC_BOGUSMX=1.482, RCVD_IN_DNSWL_LOW=-1] 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 eOEa7x9JYhek for ; Thu, 9 Apr 2009 05:49:28 -0700 (PDT) Received: from smtp3.smtp.bt.com (smtp3.smtp.bt.com [217.32.164.138]) by core3.amsl.com (Postfix) with ESMTP id 1100F3A696E for ; Thu, 9 Apr 2009 05:49:27 -0700 (PDT) Received: from i2kc06-ukbr.domain1.systemhost.net ([193.113.197.70]) by smtp3.smtp.bt.com with Microsoft SMTPSVC(6.0.3790.1830); Thu, 9 Apr 2009 13:50:34 +0100 Received: from cbibipnt05.iuser.iroot.adidom.com ([147.149.196.177]) by i2kc06-ukbr.domain1.systemhost.net with Microsoft SMTPSVC(6.0.3790.1830); Thu, 9 Apr 2009 13:50:34 +0100 Received: From bagheera.jungle.bt.co.uk ([132.146.168.158]) by cbibipnt05.iuser.iroot.adidom.com (WebShield SMTP v4.5 MR1a P0803.399); id 1239281433494; Thu, 9 Apr 2009 13:50:33 +0100 Received: from mut.jungle.bt.co.uk ([10.73.81.25]) by bagheera.jungle.bt.co.uk (8.13.5/8.12.8) with ESMTP id n39CoVKH018460; Thu, 9 Apr 2009 13:50:32 +0100 Message-Id: <200904091250.n39CoVKH018460@bagheera.jungle.bt.co.uk> X-Mailer: QUALCOMM Windows Eudora Version 7.1.0.9 Date: Thu, 09 Apr 2009 13:50:29 +0100 To: Stanislav Shalunov From: Bob Briscoe In-Reply-To: <6c82d1360904022329o34efd701p8b7a0b08730ae65a@mail.gmail.co m> References: <6c82d1360904022329o34efd701p8b7a0b08730ae65a@mail.gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Scanned-By: MIMEDefang 2.56 on 132.146.168.158 X-OriginalArrivalTime: 09 Apr 2009 12:50:34.0938 (UTC) FILETIME=[C64E69A0:01C9B911] Cc: Douglas Leith , ledbat@ietf.org Subject: Re: [ledbat] fairness between competing delay flows in draft-shalunov-ledbat-congestion-00.txt 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: Thu, 09 Apr 2009 12:49:34 -0000 Stas, Point taken about base measurements, but this questions is about the motivation for the core part of the control algo: cwnd += GAIN * off_target / cwnd. (using the draft's terminology: off_target = TARGET - queuing_delay) Q. Why should the controller's increase and decrease both depend on the same formula? I think this means the shares that competing flows get depend purely on the minutiae of the dynamics of each competing flow. That means shares depend on arbitrary stuff that sharing shouldn't depend on (e.g. whether disk heads move, how many other interrupts are served, who arrived first), and there's nothing explicit to control what the shares do depend on. However, I assume I must have missed something, as I'm sure you've thought of this. As far as I can work out (haven't had time to work through the non-linear case where the small standing queue might disappear completely), shares don't explicitly depend on RTT or packet size or delayed ack factor (which IMHO they shouldn't). While both the acceleration and deceleration of each flow do depend on these factors in equal measures (which IMHO they should too). So far so good, but... ...taking RTT as one example, altho the steady state shares won't depend directly on RTT, they might depend on second order effects of how differences in RTT interact with other random events. If correct, that's not good. It's random. Put another way, repeating the question in my earlier posting: Q. Why should the controller aim to *increase* delay up to the target? Instead the window *increase* could operate as a separate continuous process (as in AIMD algos). And the threshold only indicates a *decrease* is needed if exceeded. Then bottleneck sharing is explicitly under control. It is the equilibrium when the two decoupled increase & decrease processes balance. 'TARGET' then becomes merely a lower threshold for the decrease process, not a target for both processes. Bob At 07:29 03/04/2009, Stanislav Shalunov wrote: >We have not observed the late-comer's advantage. > >As soon as the first flow has a hiccup (for example, because something >needs to wait for a few disk head moves), there will be a gap in the >first flow's traffic, enabling the second flow to measure accurately. > >During the session Murari mentioned that in their experience, flows >were also always able to get a reasonable base delay measurement. > >Obviously, the more flows, the more uniform the traffic, the more >likely it is that the late comers might be mistaken about the base. >At tens of flows, this is clearly not a problem. At tens of >thousands, which is what most backbones see for bulk connections, I'd >expect it to start showing. The coordination problem at tens of >thousands of connections is hard and almost certain to be emergent, >but then extended congestion on backbone links is infrequent. In the >worst case, it'll all fall back to TCP. > >For a small number of flows, the situation most typically encountered >on congested links, base estimation seems to be reliable. > > >On Tue, Mar 31, 2009 at 5:23 PM, Douglas Leith wrote: > > Can I ask what the expected/desired behaviour will be when two or more > > ledbat flows share a link ? > > For example, say a first flow starts, ramps us cwnd until it hits > the target > > queueing delay and then a second ledbat flow starts a while later. Its not > > clear to me from the ID how the first flow would alter its cwnd to make > > space for the second ledbat flow (especially if the second flow > does not use > > slow start, or perhaps has an early exit from slow start). > > Also, is there a danger that, similarly the vegas and related algorithms, > > the later starting flow will have difficulty getting an accurate > estimate of > > the base RTT since earlier starting flows maintain a standing queue ? > > Doug > > www.hamilton.ie > > > >-- >Stanislav Shalunov >BitTorrent Inc >shalunov@bittorrent.com > >personal: http://shlang.com >_______________________________________________ >ledbat mailing list >ledbat@ietf.org >https://www.ietf.org/mailman/listinfo/ledbat ________________________________________________________________ Bob Briscoe, Networks Research Centre, BT Research