From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lb0-f171.google.com (mail-lb0-f171.google.com [209.85.217.171]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id B6C5F201B71 for ; Fri, 26 Oct 2012 12:56:56 -0700 (PDT) Received: by mail-lb0-f171.google.com with SMTP id m4so2467127lbo.16 for ; Fri, 26 Oct 2012 12:56:54 -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=LROQQfQMN+Yvf2go34irt96IxBRb0iLxcaPno7UHdK4=; b=iqQTdm54ZzINNBmS37A6dM1hZZDfsZTwUMyfa6YcLvjOIodierYH22zZ51TxwMze+6 sYUaYiUR6yNJDCH1gbWzuQCu8ZI0ISasWnfGQiapG12bvl77ULwJPzd2ZYDs3Bd+l2zz B+KoM3D26ntxZETm2Lb1+VZP6XUfJMpxTSzo7W8EHeFtULm/6sKzpuXyTh1jSGu5jigd fcdm1tuICKw3nwpSkDjTvnpKM6rZcCr5q6vNw5A4fk72gjSLM7FMuFHbyjOgk68WHAAE ZEQBvyGeQZBwYtu55rW7BBfLHnz77Bz3SQpQHP2Fsx7JqVT+lW+QJ1QWPVmVNNtxSDU+ PJYg== MIME-Version: 1.0 Received: by 10.112.39.138 with SMTP id p10mr9303271lbk.54.1351281414237; Fri, 26 Oct 2012 12:56:54 -0700 (PDT) Received: by 10.114.12.228 with HTTP; Fri, 26 Oct 2012 12:56:54 -0700 (PDT) Received: by 10.114.12.228 with HTTP; Fri, 26 Oct 2012 12:56:54 -0700 (PDT) In-Reply-To: <1210261854.AA17675@ivan.Harhan.ORG> References: <1210261854.AA17675@ivan.Harhan.ORG> Date: Fri, 26 Oct 2012 22:56:54 +0300 Message-ID: From: Jonathan Morton To: Michael Spacefalcon Content-Type: multipart/alternative; boundary=485b390f7ac4afecf404ccfbb86a Cc: opensdsl@ifctfvax.harhan.org, bloat@lists.bufferbloat.net Subject: Re: [Bloat] Designer of a new HW gadget wishes to avoid bufferbloat X-BeenThere: bloat@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: General list for discussing Bufferbloat List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 26 Oct 2012 19:56:57 -0000 --485b390f7ac4afecf404ccfbb86a Content-Type: text/plain; charset=ISO-8859-1 > > I think = > > there are many good arguments for head-drop, and while I'm not a = > > hardware engineer, I don't see why it would be terribly difficult to = > > implement. Suppose you have a list of starts of packets addresses within = > > your cell transmit ring buffer. Drop the first list element. Head drop! = > > Done! Once the current packet's cells are transmitted, you jump to the = > > next start of packet in the list, wherever it is. As long as you ensure = > > that packets you receive on the HDLC side don't overwrite the cells you = > > are currently transmitting, you are fine. (If the buffer was really = > > small, this probably meant lots of head drop.) > > Let me try to understand what you are suggesting. It seems to me that > you are suggesting having two separate elastic buffers between the > fill side and the drain side: one storing cells, the other storing > one-element-per-packet information (such as a buffer start address). > You implement head drop by dropping the head element from the buffer > that reckons in packets, rather than cells. But the cells are still > there, still taking up memory in the cell buffer, and that cell > storage memory can't be used to buffer up a new ingress packet because > that storage sits in the middle between cells of a packet in the > middle of transmission and the next packet which is still "officially" > in the queue. > > But I can see how perhaps the head drop mechanism you are suggesting > could be used as a secondary AQM-style packet dropper - but it can't > be the primary mechanism which ensures that the fill logic doesn't > overwrite the cell buffer RAM which the drain side is still reading > from. I was talking about the latter in my original post when I said > that I couldn't do anything other than tail drop. > > But I've come up with an enhancement to the tail drop which we could > call "modified tail drop" - is there a better, more widely accepted > term perhaps? Here's what I mean: when the fill logic sees the > beginning of a new packet on the HDLC side, it checks the buffer fill > level. If the limit has been reached, instead of simply proceeding to > skip/ignore the new HDLC ingress packet, drop the packet which has > been most recently added to the cell buffer (reset the write pointer > back to a saved position), and proceed to buffer up the new packet > normally. Okay, so you can fudge the write pointer to do a different kind of tail drop. That's great for dealing with a physically full buffer on packet arrival. What you need to do for head drop is the same kind of pointer manipulation at the read end. You only do it between IP packets, so you may want to make the decision of whether to do so in advance, so as to avoid having to insert an idle cell while that decision is made. > What draws me to the Cyclone III family is that even the lowest-end > parts feature 46 RAM blocks of 9 Kibits each (1 Kibyte + parity), > i.e., up to 46 KiB of RAM capacity. That's huge for a low-cost FPGA. > If I allocate 26 of those M9K blocks for the HDLC->SDSL cell buffer > (24 blocks for the cell payload buffer and 2 blocks for the parallel > buffer storing cell header data for the SDSL Tx logic), we can buffer > up to 511 ATM cells. (To be convenient, the buffer size in cells must > be a power of 2 minus 1.) That corresponds to ~575 ms at 384 kbps or > ~144 ms at 1536 kbps. Do you think that would be enough, or do you > think we need even more RAM for the "good queue" function? Half a second at bottleneck rate is plenty. At the higher link rate the buffer will fill more gradually, so you can still absorb a half second burst in practice, if your inbound link rate is 2Mbps. > Thus it seems to me that a sensible way to proceed would be to build > my hardware first, using the simplistic buffer limit mechanism I have > described in my original post, and then try to add CoDel later, once > the basic functionality has been brought up. Or do you think this > approach would be problematic? You should definitely think ahead to how you will implement head drop eventually. Changing that part of the system later might be more painful than you anticipate. Aside from that, starting with a simple tail drop queue will validate the rest of the system and give you a point of comparison. The next step might be to test the head drop mechanism using a trivial rule such as dropping alternate packets if the queue is more than half full. > 2. I work on a different bandwidth scale. They talk a lot about > packets crossing from 1 Gbps or 100 Mbps to 10 Mbps, etc, but the > highest possible SDSL kbps rate is 2320, and even that is only on > paper: the line cards which are actually deployed USA-wide by what > used to be Covad max out at 1536 kbps. We still have a bandwidth- > reduction bottleneck as the V.35 Tx link (router->DSU) has a higher > capacity than SDSL/ATM, but it isn't *that* much higher bandwidth. Lower bandwidth links are still very important in the consumer space. Sitting on a commuter train in Helsinki, I still regularly get GPRS links instead of 3G in certain specific places. Even 3G is more typically at your SDSL bandwidths than at the widely advertised HSPA rates. > 3. The CoDel (and bufferbloat/AQM) folks in general seem to view the > arrival and departure of packets as atomic instantaneous events. > While the latter may be true for a software router which receives > packets from or hands them over to a hardware Ethernet interface in > an instantaneous atomic manner, that model absolutely does not hold > for the underlying HW device itself as it reformats a stream of > packets from HDLC to SDSL/ATM in a flow-through fashion, without > waiting for each packet to be received in its entirety. It's a valid model for decision making, since you make decisions at discrete points in time corresponding to packet boundaries. If you come up with some specific objections, feel free to bring them up here. - Jonathan Morton --485b390f7ac4afecf404ccfbb86a Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable

> > I think =3D
> > there are many good arguments for head-drop, and while I'm no= t a =3D
> > hardware engineer, I don't see why it would be terribly diffi= cult to =3D
> > implement. Suppose you have a list of starts of packets addresses= within =3D
> > your cell transmit ring buffer. Drop the first list element. Head= drop! =3D
> > Done! Once the current packet's cells are transmitted, you ju= mp to the =3D
> > next start of packet =A0in the list, wherever it is. As long as y= ou ensure =3D
> > that packets you receive on the HDLC side don't overwrite the= cells you =3D
> > are currently transmitting, you are fine. (If the buffer was real= ly =3D
> > small, this probably meant lots of head drop.)
>
> Let me try to understand what you are suggesting. =A0It seems to me th= at
> you are suggesting having two separate elastic buffers between the
> fill side and the drain side: one storing cells, the other storing
> one-element-per-packet information (such as a buffer start address). > You implement head drop by dropping the head element from the buffer > that reckons in packets, rather than cells. =A0But the cells are still=
> there, still taking up memory in the cell buffer, and that cell
> storage memory can't be used to buffer up a new ingress packet bec= ause
> that storage sits in the middle between cells of a packet in the
> middle of transmission and the next packet which is still "offici= ally"
> in the queue.
>
> But I can see how perhaps the head drop mechanism you are suggesting > could be used as a secondary AQM-style packet dropper - but it can'= ;t
> be the primary mechanism which ensures that the fill logic doesn't=
> overwrite the cell buffer RAM which the drain side is still reading > from. =A0I was talking about the latter in my original post when I sai= d
> that I couldn't do anything other than tail drop.
>
> But I've come up with an enhancement to the tail drop which we cou= ld
> call "modified tail drop" - is there a better, more widely a= ccepted
> term perhaps? =A0Here's what I mean: when the fill logic sees the<= br> > beginning of a new packet on the HDLC side, it checks the buffer fill<= br> > level. =A0If the limit has been reached, instead of simply proceeding = to
> skip/ignore the new HDLC ingress packet, drop the packet which has
> been most recently added to the cell buffer (reset the write pointer > back to a saved position), and proceed to buffer up the new packet
> normally.

Okay, so you can fudge the write pointer to do a different kind of tail = drop. That's great for dealing with a physically full buffer on packet = arrival.

What you need to do for head drop is the same kind of pointer manipulati= on at the read end. You only do it between IP packets, so you may want to m= ake the decision of whether to do so in advance, so as to avoid having to i= nsert an idle cell while that decision is made.

> What draws me to the Cyclone III family is that even the lowest-end=
> parts feature 46 RAM blocks of 9 Kibits each (1 Kibyte + parity),
> i.e., up to 46 KiB of RAM capacity. =A0That's huge for a low-cost = FPGA.
> If I allocate 26 of those M9K blocks for the HDLC->SDSL cell buffer=
> (24 blocks for the cell payload buffer and 2 blocks for the parallel > buffer storing cell header data for the SDSL Tx logic), we can buffer<= br> > up to 511 ATM cells. =A0(To be convenient, the buffer size in cells mu= st
> be a power of 2 minus 1.) =A0That corresponds to ~575 ms at 384 kbps o= r
> ~144 ms at 1536 kbps. =A0Do you think that would be enough, or do you<= br> > think we need even more RAM for the "good queue" function?

Half a second at bottleneck rate is plenty. At the higher link rate the = buffer will fill more gradually, so you can still absorb a half second burs= t in practice, if your inbound link rate is 2Mbps.

> Thus it seems to me that a sensible way to proceed would be to buil= d
> my hardware first, using the simplistic buffer limit mechanism I have<= br> > described in my original post, and then try to add CoDel later, once > the basic functionality has been brought up. =A0Or do you think this > approach would be problematic?

You should definitely think ahead to how you will implement head drop ev= entually. Changing that part of the system later might be more painful than= you anticipate.

Aside from that, starting with a simple tail drop queue will validate th= e rest of the system and give you a point of comparison. The next step migh= t be to test the head drop mechanism using a trivial rule such as dropping = alternate packets if the queue is more than half full.

> 2. I work on a different bandwidth scale. =A0They talk a lot about<= br> > =A0 =A0packets crossing from 1 Gbps or 100 Mbps to 10 Mbps, etc, but t= he
> =A0 =A0highest possible SDSL kbps rate is 2320, and even that is only = on
> =A0 =A0paper: the line cards which are actually deployed USA-wide by w= hat
> =A0 =A0used to be Covad max out at 1536 kbps. =A0We still have a bandw= idth-
> =A0 =A0reduction bottleneck as the V.35 Tx link (router->DSU) has a= higher
> =A0 =A0capacity than SDSL/ATM, but it isn't *that* much higher ban= dwidth.

Lower bandwidth links are still very important in the consumer space. Si= tting on a commuter train in Helsinki, I still regularly get GPRS links ins= tead of 3G in certain specific places. Even 3G is more typically at your SD= SL bandwidths than at the widely advertised HSPA rates.

> 3. The CoDel (and bufferbloat/AQM) folks in general seem to view th= e
> =A0 =A0arrival and departure of packets as atomic instantaneous events= .
> =A0 =A0While the latter may be true for a software router which receiv= es
> =A0 =A0packets from or hands them over to a hardware Ethernet interfac= e in
> =A0 =A0an instantaneous atomic manner, that model absolutely does not = hold
> =A0 =A0for the underlying HW device itself as it reformats a stream of=
> =A0 =A0packets from HDLC to SDSL/ATM in a flow-through fashion, withou= t
> =A0 =A0waiting for each packet to be received in its entirety.

It's a valid model for decision making, since you make decisions at = discrete points in time corresponding to packet boundaries. If you come up = with some specific objections, feel free to bring them up here.

- Jonathan Morton

--485b390f7ac4afecf404ccfbb86a--