[iccrg] AIMD versus AIAD

Jonathan Morton <chromatix99@gmail.com> Fri, 20 November 2020 07:44 UTC

Return-Path: <chromatix99@gmail.com>
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 3BA623A10D2 for <iccrg@ietfa.amsl.com>; Thu, 19 Nov 2020 23:44:58 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.849
X-Spam-Level:
X-Spam-Status: No, score=-1.849 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 xgHWVUHswtHc for <iccrg@ietfa.amsl.com>; Thu, 19 Nov 2020 23:44:57 -0800 (PST)
Received: from mail-lf1-x131.google.com (mail-lf1-x131.google.com [IPv6:2a00:1450:4864:20::131]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BE74D3A0AF9 for <iccrg@irtf.org>; Thu, 19 Nov 2020 23:44:56 -0800 (PST)
Received: by mail-lf1-x131.google.com with SMTP id r9so12095696lfn.11 for <iccrg@irtf.org>; Thu, 19 Nov 2020 23:44:56 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:content-transfer-encoding:mime-version:subject:message-id:date :to; bh=YKRw/FL0m0DlKTpiUZrSS5jFCU6pGkhmqsITYxr1s1g=; b=RrhqpSAihKM9ClGeOAn3WU4G6Dj6VEPYquLR/A5gKa/+OVjSQ1Q3BbugsN2VC2+7/C 0w7tnTNUa4wqzg2VO3N0GsEukhxm5FOUHBb2F++JNi2jkv/YITk394/hGox8pJXFEWzV Z8WHI99n7eMOR3vZbt9Fk586uVQnDU/n+2YKGgmLevbtdzO/PzthIipMIvPWJ+UvbC96 YWtiS/joWHF0Dp20mnb3HHjykQmtjzgOMXNiDe1Gb9v89Bz/fbjbrmqUpwDBSQ6xnZf5 g0W75WVyAv+s+POnpT1lrDZhTbW6wg0NY8lN2M7goovnbs5lRNK+fO401+7ARPg9bGwf sIEw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:content-transfer-encoding:mime-version :subject:message-id:date:to; bh=YKRw/FL0m0DlKTpiUZrSS5jFCU6pGkhmqsITYxr1s1g=; b=OMGT7jvEGvcutr4Y1qw4DfrtUKeXBm4f3gwg5+cWDJJ+qFXv6PRoO1NUgdro/1cQQe ne6nGd+LFqr+syqGTGcRh84kWaaYz7tjOqbLtGa4+tHhRTa/XAqivUuMk4BHsuvAJgUp H9s0JFibS8qgyIEfnBGFuMsf3jP/hjmPvvl+G5jlN69XLQtoJhVWUDVpSDTS7gdt3gNg 5+khr+CyilgrZRdO2hL2Vd1ANkdWevxdoiF735gMDf7w8sNmXVE/HjwtnJBy1n829glU 2zdJQ/Hm0NfbGTuWUBY7QlWoRJvcrhPwBpaGGjfg5J5lfhlFSFaHxWwZq6vBQ/57CoF3 Bgmg==
X-Gm-Message-State: AOAM530xXccdq9vR8vY6LJtpNXXoU/ErKhH7+1B+6yNu2C0VVwi8KUpe XkIvf8EMRPB2NXyNvUgUNrGfha2jigI=
X-Google-Smtp-Source: ABdhPJwbzfhKTq7pDfk9TNN+rf6mx98YlgjFM0wirI5TR0VSfcCQ1ERkiitjtonTdUgf2YmPOWvzMg==
X-Received: by 2002:a19:4c56:: with SMTP id z83mr7180392lfa.456.1605858294489; Thu, 19 Nov 2020 23:44:54 -0800 (PST)
Received: from jonathartonsmbp.lan (178-55-159-67.bb.dnainternet.fi. [178.55.159.67]) by smtp.gmail.com with ESMTPSA id m29sm253808lfp.48.2020.11.19.23.44.53 for <iccrg@irtf.org> (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128); Thu, 19 Nov 2020 23:44:53 -0800 (PST)
From: Jonathan Morton <chromatix99@gmail.com>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.7\))
Message-Id: <5026FF59-8D58-4E7A-9026-42CE387E934D@gmail.com>
Date: Fri, 20 Nov 2020 09:44:52 +0200
To: iccrg IRTF list <iccrg@irtf.org>
X-Mailer: Apple Mail (2.3445.9.7)
Archived-At: <https://mailarchive.ietf.org/arch/msg/iccrg/-duVUQ9cNREWgbUm7OdQmA_JGnw>
Subject: [iccrg] AIMD versus AIAD
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: Fri, 20 Nov 2020 07:44:58 -0000

At the end of today's session, I had the opportunity to highlight the central feature of TCP Prague, inherited from DCTCP, which is the change in response to a CE mark (additive instead of multiplicative).  The response from the presenters (Bob & Koen) indicated that we need to clarify some terminology before the discussion can begin in earnest.

Specifically:  what is Multiplicative Decrease, and what is Additive Decrease, and which one does TCP Prague use?

It is well established that NewReno and CUBIC are AIMD algorithms, indeed Reno was the original AIMD CC.  A single packet loss or CE mark causes the cwnd to reduce to some fixed fraction of its previous value within one RTT of the congestion signal being recognised.  Or, mathematically:

MD:  O(1) signals causes O(N) reduction in cwnd.

Conversely, looking at DCTCP and ignoring the low-pass filters which disappear in the long run, each CE mark causes half a segment to be subtracted from the cwnd.  This is classic Additive Decrease.  There is still (barring implementation bugs) a Multiplicative Decrease response to packet loss.  So, distilling:

AD:  O(1) signals causes O(1) reduction in cwnd; to get O(N) reduction requires O(N) distinct signals.

The above is true regardless of how closely spaced the congestion signals are.  With precise feedback of CE marks, you can successfully register a mark on every data packet during a whole RTT and obtain, effectively, a multiplicative decrease - but that does not make the response MD, because the response to a *single* CE mark is O(1) segments.

 - Jonathan Morton