From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ondar.cablelabs.com (ondar.cablelabs.com [192.160.73.61]) by huchra.bufferbloat.net (Postfix) with ESMTP id EE2C721F19B for ; Tue, 3 Mar 2015 22:51:47 -0800 (PST) Received: from kyzyl.cablelabs.com (kyzyl [10.253.0.7]) by ondar.cablelabs.com (8.14.7/8.14.7) with ESMTP id t246piV5027469; Tue, 3 Mar 2015 23:51:44 -0700 Received: from exchange.cablelabs.com (10.5.0.19) by kyzyl.cablelabs.com (F-Secure/fsigk_smtp/407/kyzyl.cablelabs.com); Tue, 03 Mar 2015 23:51:44 -0700 (MST) X-Virus-Status: clean(F-Secure/fsigk_smtp/407/kyzyl.cablelabs.com) Received: from EXCHANGE.cablelabs.com ([::1]) by EXCHANGE.cablelabs.com ([::1]) with mapi id 14.03.0224.002; Tue, 3 Mar 2015 23:51:45 -0700 From: Greg White To: Jonathan Morton , sahil grover Thread-Topic: [Codel] why RED is not considered as a solution to bufferbloat. Thread-Index: AQHQUcPcgn9fhvL3rUGkYczAhhXWlp0DacgAgAijjYA= Date: Wed, 4 Mar 2015 06:51:44 +0000 Message-ID: References: In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: user-agent: Microsoft-MacOutlook/14.4.7.141117 x-originating-ip: [10.5.0.27] Content-Type: multipart/alternative; boundary="_000_D11B960B44E5Fgwhitecablelabscom_" MIME-Version: 1.0 Cc: "codel@lists.bufferbloat.net" Subject: Re: [Codel] why RED is not considered as a solution to bufferbloat. 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: Wed, 04 Mar 2015 06:52:16 -0000 --_000_D11B960B44E5Fgwhitecablelabscom_ Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable This is a common misconception. The "NotCodel" approach, operating entirely at enqueue time, will have to p= redict buffering latency for a packet when it is enqueued (likely based on = queue depth and expected dequeue rate), as opposed to CoDel which measures = the buffering latency for the packet after it has been experienced. If deq= ueue rate is predictable (true for some links, less so for others) then the= NotCodel approach can be designed such that it will drop (or mark) *the sa= me packets* that the CoDel approach would. In some hardware, it is much more feasible to perform these operations at e= nqueue time rather than at dequeue time. Implementers of such systems shou= ldn't be dissuaded from implementing CoDel (especially if their dequeue rat= e is reasonably predictable). We experimented with an implementation of "NotCodel" (we called it CoDel-D= T, for drop tail) and that code is in the ns-2.36 release candidate. One c= aveat, the control law in that implementation does not precisely match CoDe= l, and so there will be some slight differences in results between the two. -Greg From: Jonathan Morton > Date: Thursday, February 26, 2015 at 6:56 AM To: sahil grover = > Cc: "codel@lists.bufferbloat.net" > Subject: Re: [Codel] why RED is not considered as a solution to bufferbloat= . Okay, let me walk you through this. Let's say you are managing a fairly slow link, on the order of 1 megabit. T= he receiver on the far side of it is running a modern OS and has opened its= receive window to a whole megabyte. It would take about 10 seconds to pass= a whole receive window through the link. This is a common situation in the real world, by the way. Now, let's suppose that the sender was constrained to a slower send rate, s= ay half a megabit, for reasons unrelated to the network. Maybe it's a strea= ming video service on a mostly static image, so it only needs to send small= delta frames and compressed audio. It has therefore opened the congestion = window as wide as it will go, to the limit of the receive window. But then = the action starts, there's a complete scene change, and a big burst of data= is sent all at once, because the congestion window permits it. So the queue you're managing suddenly has a megabyte of data in it. Unless = you do something about it, your induced latency just leapt up to ten second= s, and the VoIP call your user was on at the time will drop out. Now, let's compare the behaviour of two AQMs: Codel and something almost, b= ut not entirely, unlike Codel. Specifically, it does everything that Codel = does, but at enqueue instead of dequeue time. Both of them will let the entire burst into the queue. Codel only takes act= ion if the queue remains more full than its threshold for more than 100ms. = Since this burst arrives all at once, and the queue stayed nice and empty u= p until now, neither AQM will decide to mark or drop packets at that moment= . Now, packets are slowly delivered across the link. Each one takes about 15m= s to deliver. They are answered by acks, and the sender obligingly sends fr= esh packets to replace them. After about six or seven packets have been del= ivered, both AQMs will decide to start marking packets (this is an ECN enab= led flow). Let's assume that the next packet after this point will be marke= d. This will be the receiver's first clue that congestion is occurring. For Codel, the next packet available to mark will be the eighth packet. So = the receiver learns about the congestion event 120 ms after it began. It wi= ll echo the congestion mark back to the sender in the corresponding ack, wh= ich will immediately halve the congestion window. It will still take at lea= st ten seconds to drain the queue. For NotCodel, the next available packet for marking is the one a megabyte l= ater than the eighth packet. The receiver won't see that packet until 10120= ms after the congestion event began. So the sender will happily keep the q= ueue ten seconds long for the next ten seconds, instead of backing off stra= ight away. It will take at least TWENTY seconds to drain the queue. Note that even if the link bandwidth was 10 megabits rather than one, with = the same receive window size, it would still take one second to drain the q= ueue with Codel and two seconds with NotCodel. This relatively simple traffic situation demonstrates that marking on deque= ue rather than enqueue is twice as effective at managing queue length. - Jonathan Morton --_000_D11B960B44E5Fgwhitecablelabscom_ Content-Type: text/html; charset="us-ascii" Content-ID: <5EEB2E54BA358E4F944C54FAD9C3EF99@cablelabs.com> Content-Transfer-Encoding: quoted-printable
This is a common misconception.  

The "NotCodel" approach, operating entirely at enqueue time,= will have to predict buffering latency for a packet when it is enqueued (l= ikely based on queue depth and expected dequeue rate), as opposed to CoDel = which measures the buffering latency for the packet after it has been experienced.  If dequeue rate is predictable= (true for some links, less so for others) then the NotCodel approach can b= e designed such that it will drop (or mark) *the same packets* that the CoD= el approach would. 

In some hardware, it is much more feasible to perform these operations= at enqueue time rather than at dequeue time.  Implementers of such sy= stems shouldn't be dissuaded from implementing CoDel (especially if their d= equeue rate is reasonably predictable).

We experimented with an implementation of "NotCodel"  (= we called it CoDel-DT, for drop tail) and that code is in the ns-2.36 relea= se candidate.  One caveat, the control law in that implementation does= not precisely match CoDel, and so there will be some slight differences in results between the two.

-Greg

From: Jonathan Morton <chromatix99@gmail.com>
Date: Thursday, February 26, 2015 a= t 6:56 AM
To: sahil grover <sahilgrover013@gmail.com>
Cc: "codel@lists.bufferbloat.net" <codel@lists.bufferbloat.net>
Subject: Re: [Codel] why RED is not= considered as a solution to bufferbloat.

Okay, let me walk you through this.

Let's say you are managing a fairly slow link, on the order = of 1 megabit. The receiver on the far side of it is running a modern OS and= has opened its receive window to a whole megabyte. It would take about 10 = seconds to pass a whole receive window through the link.

This is a common situation in the real world, by the way.

Now, let's suppose that the sender was constrained to a slow= er send rate, say half a megabit, for reasons unrelated to the network. May= be it's a streaming video service on a mostly static image, so it only need= s to send small delta frames and compressed audio. It has therefore opened the congestion window as wide as it will go= , to the limit of the receive window. But then the action starts, there's a= complete scene change, and a big burst of data is sent all at once, becaus= e the congestion window permits it.

So the queue you're managing suddenly has a megabyte of data= in it. Unless you do something about it, your induced latency just leapt u= p to ten seconds, and the VoIP call your user was on at the time will drop = out.

Now, let's compare the behaviour of two AQMs: Codel and some= thing almost, but not entirely, unlike Codel. Specifically, it does everyth= ing that Codel does, but at enqueue instead of dequeue time.

Both of them will let the entire burst into the queue. Codel= only takes action if the queue remains more full than its threshold for mo= re than 100ms. Since this burst arrives all at once, and the queue stayed n= ice and empty up until now, neither AQM will decide to mark or drop packets at that moment.

Now, packets are slowly delivered across the link. Each one = takes about 15ms to deliver. They are answered by acks, and the sender obli= gingly sends fresh packets to replace them. After about six or seven packet= s have been delivered, both AQMs will decide to start marking packets (this is an ECN enabled flow). Let's assum= e that the next packet after this point will be marked. This will be the re= ceiver's first clue that congestion is occurring.

For Codel, the next packet available to mark will be the eig= hth packet. So the receiver learns about the congestion event 120 ms after = it began. It will echo the congestion mark back to the sender in the corres= ponding ack, which will immediately halve the congestion window. It will still take at least ten seconds to dr= ain the queue.

For NotCodel, the next available packet for marking is the o= ne a megabyte later than the eighth packet. The receiver won't see that pac= ket until 10120 ms after the congestion event began. So the sender will hap= pily keep the queue ten seconds long for the next ten seconds, instead of backing off straight away. It will ta= ke at least TWENTY seconds to drain the queue.

Note that even if the link bandwidth was 10 megabits rather = than one, with the same receive window size, it would still take one second= to drain the queue with Codel and two seconds with NotCodel.

This relatively simple traffic situation demonstrates that m= arking on dequeue rather than enqueue is twice as effective at managing que= ue length.

- Jonathan Morton

 --_000_D11B960B44E5Fgwhitecablelabscom_--