Re: [iccrg] Background on my talk in iccrg
Bob Briscoe <in@bobbriscoe.net> Wed, 03 April 2019 14:47 UTC
Return-Path: <in@bobbriscoe.net>
X-Original-To: iccrg@ietfa.amsl.com
Delivered-To: iccrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 688ED1200A2 for <iccrg@ietfa.amsl.com>; Wed, 3 Apr 2019 07:47:16 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.099
X-Spam-Level:
X-Spam-Status: No, score=-0.099 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=bobbriscoe.net
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VV_cqPpBwIby for <iccrg@ietfa.amsl.com>; Wed, 3 Apr 2019 07:47:13 -0700 (PDT)
Received: from server.dnsblock1.com (server.dnsblock1.com [85.13.236.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B71DF12008D for <iccrg@irtf.org>; Wed, 3 Apr 2019 07:47:12 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=bobbriscoe.net; s=default; h=Content-Type:In-Reply-To:MIME-Version:Date: Message-ID:From:References:To:Subject:Sender:Reply-To:Cc: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=WuCIDb/sUpQnz1j9ou45bUQNGCjvH1xiLPNymT0aN2U=; b=I5BcEkAZUwFpzo7sMDuPdPv0W OkGUn+qRtVTRQdAUhwiAiZqrXvJiacgj5bpolDQy02j+V+VF5Ez9ThTN/TE9PZp0Ijby3xDHPLQGG a/5UipfG7asoCIfqCcEjABuqTLx9QgIg3dUbQ+P1wlkIwRB8aqrBLjjDOOlu8JlfJFJH40Hd3SiDr nAALq9k98iWizelBWcME+RYM64ktNS1THRY5kgTzoRENk8gElLslP65lrPIEoCOIJMNw0YrWXR6XZ 69f9nrs3a+bp1nGfv/8FOxJ0XFzz8h4ksxUmGGsaFFAgLRq2WmOsXUGBwJplPNVPrP710zup3ohie LHUxkZeEQ==;
Received: from [31.185.128.56] (port=55748 helo=[192.168.0.7]) by server.dnsblock1.com with esmtpsa (TLSv1.2:ECDHE-RSA-AES128-GCM-SHA256:128) (Exim 4.91) (envelope-from <in@bobbriscoe.net>) id 1hBhAT-0001vj-N8 for iccrg@irtf.org; Wed, 03 Apr 2019 15:47:10 +0100
To: iccrg@irtf.org
References: <9D7CBDDC-EEDC-4510-96D6-EA893826F190@ifi.uio.no> <d05eb4b8-53ae-82be-5442-711c3316940b@bobbriscoe.net> <9be2b58a-4664-c2bd-378d-38feeea193e8@bobbriscoe.net> <fc81e540-3f81-d6c7-bbdc-2fd2d03774e6@bobbriscoe.net> <fb2f75f7-e46a-8ccd-9656-733db6dc6c87@ifi.uio.no> <c80adefc-f5eb-db72-cfa1-1fa8a15ed955@ifi.uio.no>
From: Bob Briscoe <in@bobbriscoe.net>
Message-ID: <361a787a-71e8-fc2b-2bec-c81f13c413cb@bobbriscoe.net>
Date: Wed, 03 Apr 2019 15:47:09 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101 Thunderbird/60.5.1
MIME-Version: 1.0
In-Reply-To: <c80adefc-f5eb-db72-cfa1-1fa8a15ed955@ifi.uio.no>
Content-Type: multipart/alternative; boundary="------------1B9376647CF7F9856D6B426D"
Content-Language: en-GB
X-AntiAbuse: This header was added to track abuse, please include it with any abuse report
X-AntiAbuse: Primary Hostname - server.dnsblock1.com
X-AntiAbuse: Original Domain - irtf.org
X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12]
X-AntiAbuse: Sender Address Domain - bobbriscoe.net
X-Get-Message-Sender-Via: server.dnsblock1.com: authenticated_id: in@bobbriscoe.net
X-Authenticated-Sender: server.dnsblock1.com: in@bobbriscoe.net
Archived-At: <https://mailarchive.ietf.org/arch/msg/iccrg/1kIkbg9rlp2oZgxKrXCe35tW37Q>
Subject: Re: [iccrg] Background on my talk in iccrg
X-BeenThere: iccrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "Discussions of Internet Congestion Control Research Group \(ICCRG\)" <iccrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/iccrg>, <mailto:iccrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/iccrg/>
List-Post: <mailto:iccrg@irtf.org>
List-Help: <mailto:iccrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/iccrg>, <mailto:iccrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 03 Apr 2019 14:47:17 -0000
Peyman, On 03/04/2019 12:51, Peyman Teymoori wrote: > > > On 4/3/2019 1:44 PM, Peyman Teymoori wrote: >> >> Hi Bob, >> >> Thanks a lot for the comments! >> >> On 4/3/2019 12:48 PM, Bob Briscoe wrote: >>> Peyman, >>> >>> 1/ I realize now that I incorrectly appeared to be dismissing your >>> work in my email and my comment at the mic. I apologize. >>> Your -log(1-p) formulation does indeed have the correct additive >>> property. Thank you for this. >> >> A true additive signal was what we were looking for. >> >>> >>> 2/ Implementation >>> You say "...we will consider deployment challenges more thoroughly >>> in our future work." Surely this is a sender-only algorithm, so >>> there is no deployment challenge? However, there is a (minor) >>> implementation challenge. Perhaps that's what you meant?... >>> >> Yes, and I agree that it's a sender-side change, which cannot be >> major! and it needs router configurations as well. >> >>> 2a/ With the current DCTCP approach of updating an EWMA of the >>> congestion level once per RTT, I don't think implementation will >>> present too much of a performance hit. >> That's right. >>> >>> (1-p) could be calculated by maintaining counters of the number of >>> unmarked bytes and total bytes, then every RTT using an efficient >>> integer division, such as do_div() in Linux, then using an efficient >>> log implementation. I'm not sure what to do when there's 100% >>> marking to avoid calculating -log(0) = +infinity. >> In simulations, I just checked if 1-p = 1 before calculating log, and >> since p is the result of EWMA, there were very rare cases of having p >> = 1. >>> Aside from that issue, I don't think this calculation would harm >>> performance too much, although I would prefer not to have a regular >>> spike of processing time... >> Right. >>> >>> 2b/ We liked p/(1-p) because it lends itself to a simple iterative >>> calculation on every ACK or NACK. That's because there are >>> (1-p)*cwnd ACKs per round trip and p*cwnd NACKs per round trip. So >>> an increase can be applied on each ACK and a decrease on each NACK. >>> >>> This insight was not our idea - I first saw it in Richard Gibbens's >>> and Peter Key's tutorial "Distributed Control and Resource Pricing" >>> at SIGCOMM 2000. They used it when modelling TCP's AIMD. >>> >>> I much prefer iterative algorithms, cos they are stateless. >>> Otherwise TCP gets more and more complicated with all the possible >>> combinations of modes you have to allow for. >>> >>> I can't think of a way to iteratively calculate -log(1-p). I've only >>> tried for a few minutes, but I can't really fathom where to even start. >> I haven't tried it either but, that's a good hint on how to make the >> calculation easier! >>> I also cannot think of a good way to reason about what base should >>> be used for the log. >>> >>> -log(1-p) and p/(1-p) have similar shapes, so maybe the latter would >>> be a suitable approximation for the former anyway. >> I plotted this for some different values of the log base. It seems >> like 1.5 as the base produces closer values to 1/(1-p) for p \in >> [0.4,0.8]. > Fixing 1/(1-p) to p/(1-p): if base=2, they are close for p \in [0, 0.55]. Also the slopes have a similar form, and they're equal at p=0: _d (-log_b(1-p) )_= ___1 _ dp ln(b)*(1-p) _d (p/(1-p))_ = _ 1 _ dp (1-p)^2 Bob >>> Normally I criticize others for developing solutions without any >>> theoretical backing just because they are easy to implement. Now I'm >>> guilty of it myself. I'm much happier now we can start from your >>> theoretical ideal, then approximate it for ease of implementation. >> >> ... and I am very happy that you liked the idea! >> >> Kind regards, >> Peyman >> >> >>> >>> Thanks again, >>> >>> >>> >>> Bob >>> >>> On 28/03/2019 16:56, Bob Briscoe wrote: >>>> Addendum... >>>> >>>> On 28/03/2019 17:03, Bob Briscoe wrote: >>>>> Peyman, >>>>> >>>>> The approx additive property of combinatorial probability at low >>>>> marking probability is only one way to get the additive network >>>>> utility maximization property of the network. >>>>> >>>>> Alternatively, you can transform the signal into the number space >>>>> between [0,1] by using p/(1-p) which you can do in the end-system >>>>> by measuring your congestion level as the distance between ECN >>>>> marks, rather than the the probability of marking. >>>>> >>>>> This is explained in the Unsaturated Marking section of this tech >>>>> report: >>>>> http://bobbriscoe.net/projects/latency/ccdi_tr.pdf#subsection.3.1 >>>>> >>>>> We presented some of the highlights of this paper in ICCRG in the >>>>> past, but I think we had to skip this section, due to lack of time >>>>> (at least I cannot find the slides we originally prepared in the >>>>> copy in the IETF proceedings, but I thought we had presented it at >>>>> some time). >>>> [BB] I just found it: >>>> http://bobbriscoe.net/presents/1703ietf/1703L4S_DualQ_TCP_Prague-iccrg.pdf >>>> >>>> >>>> >>>> Bob >>>>> >>>>> >>>>> Bob >>>>> >>>>> On 21/03/2019 13:18, Peyman Teymoori wrote: >>>>>> Dear all, >>>>>> >>>>>> I would like to share the report (preprint) we have been working on with you before the meeting in Prague since my presentation will be about it. This is actually a research work, and we will consider deployment challenges more thoroughly in our future work. >>>>>> >>>>>> Kind regards, >>>>>> Peyman >>>>>> >>>>>> >>>>>> _______________________________________________ >>>>>> iccrg mailing list >>>>>> iccrg@irtf.org >>>>>> https://www.irtf.org/mailman/listinfo/iccrg >>>>> >>>>> -- >>>>> ________________________________________________________________ >>>>> Bob Briscoehttp://bobbriscoe.net/ >>>> >>>> -- >>>> ________________________________________________________________ >>>> Bob Briscoehttp://bobbriscoe.net/ >>> >>> -- >>> ________________________________________________________________ >>> Bob Briscoehttp://bobbriscoe.net/ >> >> _______________________________________________ >> iccrg mailing list >> iccrg@irtf.org >> https://www.irtf.org/mailman/listinfo/iccrg > > _______________________________________________ > iccrg mailing list > iccrg@irtf.org > https://www.irtf.org/mailman/listinfo/iccrg -- ________________________________________________________________ Bob Briscoe http://bobbriscoe.net/
- [iccrg] Background on my talk in iccrg Peyman Teymoori
- Re: [iccrg] Background on my talk in iccrg Emmanuel Lochin
- Re: [iccrg] Background on my talk in iccrg Bob Briscoe
- Re: [iccrg] Background on my talk in iccrg Bob Briscoe
- Re: [iccrg] Background on my talk in iccrg Bob Briscoe
- Re: [iccrg] Background on my talk in iccrg Peyman Teymoori
- Re: [iccrg] Background on my talk in iccrg Peyman Teymoori
- Re: [iccrg] Background on my talk in iccrg Bob Briscoe
- Re: [iccrg] Background on my talk in iccrg De Vleeschauwer, Danny (Nokia - BE/Antwerp)
- [iccrg] Estimating an Additive Path Cost with ECN Michael Welzl
- Re: [iccrg] Estimating an Additive Path Cost with… Emmanuel Lochin