From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-vn0-x231.google.com (mail-vn0-x231.google.com [IPv6:2607:f8b0:400c:c0f::231]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id 2851321F4E9 for ; Fri, 10 Apr 2015 13:55:13 -0700 (PDT) Received: by vnbf1 with SMTP id f1so8478858vnb.5 for ; Fri, 10 Apr 2015 13:55:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=aP7CNu2YzORJ6OLVxJTwIqYfehgzCcq7ondq3XyMz+0=; b=z1/flXt6zyKbzARLcUxkfrBaFPX/FxyT46uix5SVsrRGBpG8qxA12L/aZyc8W+g1oE zd5WOXCzvDilPcBhV95gVLROY4HxWOi2iB7PGkAy20V9gjNq8+HtyYbGT8ad0bRdYrrG Iofvqxt2/UUrA4jcfMubzJkY0eh1wBTh0+khWHObCy2qXjL53ReO1GC5U5wTw9IelGzY u10N8NuG6FC+XYLn7NcvGeukO8LCwk34uHrrlWBZqZWK28FQKkAxYtxzNXBsj96VyyqQ Z0n0d/AgbVAgrPEqTr41IORi/73Tf/Aublw/HNBnZma++VGfd6iy8Bl2J2/c3tNMVp4g 3y7A== MIME-Version: 1.0 X-Received: by 10.52.33.180 with SMTP id s20mr3407541vdi.35.1428699312419; Fri, 10 Apr 2015 13:55:12 -0700 (PDT) Received: by 10.52.240.145 with HTTP; Fri, 10 Apr 2015 13:55:12 -0700 (PDT) Received: by 10.52.240.145 with HTTP; Fri, 10 Apr 2015 13:55:12 -0700 (PDT) In-Reply-To: References: Date: Fri, 10 Apr 2015 23:55:12 +0300 Message-ID: From: Jonathan Morton To: sahil grover Content-Type: multipart/alternative; boundary=20cf3079baae01f833051364fb95 Cc: David Lang , codel@lists.bufferbloat.net Subject: Re: [Codel] SfqCodel X-BeenThere: codel@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: CoDel AQM discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 10 Apr 2015 20:55:42 -0000 --20cf3079baae01f833051364fb95 Content-Type: text/plain; charset=UTF-8 SFQ is quite simple in essence. It performs flow isolation, allowing packets from different flows to bypass each other. A flow is defined as packets possessing a common 5-tuple of source address, destination address, protocol (TCP, UDP, ICMP etc), source port and destination port. Ideally, Fair Queuing would perfectly separate all flows into queues, then service each of them equally and fairly in turn, for some measure of equality and fairness. This would provide ideal flow isolation. SFQ is not quite this ideal model. The 5-tuple is converted into a hash value which is used directly to index into a fixed list of queues; thus hash collisions can occur which mix traffic from multiple flows in the same queue. It also services queues in a strict round-robin, delivering one packet per cycle, regardless of the relative sizes of these packets. These are compromises intended to minimise CPU overhead and implementation complexity. (They made sense at the time when SFQ was cutting edge, which was a long time ago.) Fq_codel as implemented in Linux is not the same as sfq_codel as implemented in ns2. Instead of using SFQ to provide flow isolation, it uses DRR++, which provides bytewise fairness and a priority boost to sparse flows. Recent work has also found a way to significantly reduce the hash collision problem without imposing much additional overhead, and this has been incorporated into cake. - Jonathan Morton --20cf3079baae01f833051364fb95 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable

SFQ is quite simple in essence. It performs flow isolation, = allowing packets from different flows to bypass each other.

A flow is defined as packets possessing a common 5-tuple of = source address, destination address, protocol (TCP, UDP, ICMP etc), source = port and destination port.

Ideally, Fair Queuing would perfectly separate all flows int= o queues, then service each of them equally and fairly in turn, for some me= asure of equality and fairness. This would provide ideal flow isolation.

SFQ is not quite this ideal model. The 5-tuple is converted = into a hash value which is used directly to index into a fixed list of queu= es; thus hash collisions can occur which mix traffic from multiple flows in= the same queue. It also services queues in a strict round-robin, deliverin= g one packet per cycle, regardless of the relative sizes of these packets. = These are compromises intended to minimise CPU overhead and implementation = complexity. (They made sense at the time when SFQ was cutting edge, which w= as a long time ago.)

Fq_codel as implemented in Linux is not the same as sfq_code= l as implemented in ns2. Instead of using SFQ to provide flow isolation, it= uses DRR++, which provides bytewise fairness and a priority boost to spars= e flows. Recent work has also found a way to significantly reduce the hash = collision problem without imposing much additional overhead, and this has b= een incorporated into cake.

- Jonathan Morton

--20cf3079baae01f833051364fb95--