From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x130.google.com (mail-lf1-x130.google.com [IPv6:2a00:1450:4864:20::130]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id 85A973BA8E for ; Wed, 24 Oct 2018 14:43:48 -0400 (EDT) Received: by mail-lf1-x130.google.com with SMTP id o2-v6so4786652lfl.13 for ; Wed, 24 Oct 2018 11:43:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=DG2jlgejGh9YHfk7MbkhAZN/OmSJBmv70E5U9T+ewN4=; b=f2FL2rPidR3z0HXH6cgfzx+hSJKZjzYiRgvE01LIhGFMwXfwv9htRj7OnBztneCp6Z kafHQ1UM/7Kx7nE0i3FG+XdlR6+280hYs1knR7NDUXbrGVy0jDD2+42di8xxNXIk61op A5Ab/ISLgo2pl9aJtjYBqPoo6dieak7XaCXzoDfLuJmpxV+H4Ct7YsSZY+PoB4G6OAtP BNhM61SOBwx84IRPQfT4f5MpRhUqKHKmVLQm1mot4blLczsO9XaRwaLVCmQDDCWoqgfe sNgXatq8FqUNqqWDhWoVkd5FNGiafT9VrgoMhVYoiPtVwdo6N11bzD4v4ddKTl5pmsXu qHBw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=DG2jlgejGh9YHfk7MbkhAZN/OmSJBmv70E5U9T+ewN4=; b=bJeZgrUvyETFS286Wy34wXWeJbyrj6DDahqRPUtIqMTDfbUM5Nd0nxqOjn9vrJi4z3 JkB0DNjpK3e/ECBx0deSodc5KzuRhUYL2xmp5PFVHuk0MS+6Ob9WOv9xt8vcq1tJwkqt WeZSGGFb6se/nE/fPybUALGZqM080I3S87PRAq5qD5b7bBCqdvnly7g2VvSIDWas+dDu Rb17CYsj0pKE5hfDi0pYDxcMcFdMv60O25rttLDRceKeT784gTW9LZ1mDocN5VDGTCBa yIexqrfshHhU8TLDKV3CxFpaPh6jgXZBlMZq1OfUXDe6/H1x3TpRPXuVD7XUP0gGkuZZ m9mA== X-Gm-Message-State: ABuFfojHEanLcxooPtKU95vEg7C8lcMIW57LZYsLGdRpqUAjrEw484tj 2aDWULU4HX4RVbaG4iocc2g= X-Google-Smtp-Source: ACcGV60kOITvZi+R4afProWz4nYpHK2gL5t69tpKTMUVeC+rN2qiBrFB/ObDjTpCaAsYU1qxBXNCMg== X-Received: by 2002:a19:dd1d:: with SMTP id u29mr15726955lfg.97.1540406627255; Wed, 24 Oct 2018 11:43:47 -0700 (PDT) Received: from jonathartonsmbp.lan (83-245-235-40-nat-p.elisa-mobile.fi. [83.245.235.40]) by smtp.gmail.com with ESMTPSA id c62-v6sm845421lfg.6.2018.10.24.11.43.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 24 Oct 2018 11:43:46 -0700 (PDT) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 11.5 \(3445.9.1\)) From: Jonathan Morton In-Reply-To: Date: Wed, 24 Oct 2018 21:43:44 +0300 Cc: cake@lists.bufferbloat.net Content-Transfer-Encoding: quoted-printable Message-Id: References: To: Shefali Gupta X-Mailer: Apple Mail (2.3445.9.1) Subject: Re: [Cake] Query Regarding CAKE X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 24 Oct 2018 18:43:48 -0000 > On 24 Oct, 2018, at 3:06 pm, Shefali Gupta = wrote: >=20 > We're working on the implementation of CAKE in ns-3, but have been = facing an issue about finding resources on COBALT (algorithm / pseudo = code). In the LANMAN paper on CAKE, we did not find much detail about = COBALT. Can anyone provide us resources on COBALT. Essentially, COBALT is a variant of Codel, incorporating its key = features: - Acts on dequeue, ie. signals at the head of the queue rather than at = the tail. - Time based rather than packet percentage based, thereby interacting = efficiently with TCP's RTT cycle. - Linear signalling frequency ramp over time, implemented through an = inverse-square-root law per drop event, while packet sojourn time = remains above target. As Dave T=C3=A4ht noted, the implementation is different, being a nearly = complete rewrite, but the behaviour is the same in simple cases. The = API is also different, being based entirely on calls from the qdisc into = COBALT, rather than relying on a callback from Codel into the qdisc to = obtain a dequeued packet. COBALT returns a flag indicating whether the packet should be dropped, = rather than doing so itself; this permits Cake to avoid dropping the = last packet in a sub-queue, which could lead to "tail loss" and an RTO = delay at the application level. On ECN capable traffic, the Codel = portion of COBALT signals using CE marks and does not flag any packets = for dropping. The functional differences between Codel and COBALT arise from = limitations we observed in Codel's capabilities. The behaviour when sojourn time fell below target, then rose again = shortly afterwards, was poorly specified in Codel and didn't seem to = have any theoretical basis. I introduced a reversal of the = linear-over-time frequency ramp, which proved to be reasonably easy to = implement as well as being theoretically reasonable behaviour. It = should allow COBALT to adapt cleanly to lower-than-expected path RTTs, = which require faster signalling and shorter reaction times when the = target sojourn time is exceeded; I would be interested to see results = which could establish whether that's actually true. Codel also has trouble with unresponsive and anti-reponsive traffic due = to its relatively gentle method of signalling, and with ECN blackholes = in conjunction with ECN capable traffic. Cake has a backstop here in = the form of head-dropping from the longest queue in case of hitting a = global backlog limit, but this typically leads to burst loss in much the = same way as tail-drop FIFOs do. Hence the introduction of the BLUE = portion of COBALT. BLUE, as implemented in COBALT, is exceedingly simple. When packets are = hard-dropped due to a global limit violation, the affected sub-queue's = COBALT is notified of the event. Subject to a timeout, this causes the = drop percentage to be incremented by a fixed step. BLUE never uses ECN, = and acts only through packet drops. When the sub-queue empties, COBALT = is notified of this as well, and subject to the same timeout, decrements = the drop percentage by a smaller step. By acting only at these = extremes, the action of BLUE avoids interfering with the normal action = of Codel (which permits temporary excursions in queue length). These modifications require the COBALT state to be regularly updated = even when the associated sub-queue is empty and idle, as long as the = COBALT state has not reached quiescence (zero drop percentage for BLUE, = and a complete ramp-down of signalling frequency for Codel). There are = measures within Cake which ensure that occurs. As always, the source code is authoritative as to actual behaviour - but = please do continue to ask for clarification on rationale if required. - Jonathan Morton