From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from grace.univie.ac.at (grace.univie.ac.at [IPv6:2001:62a:4:25::25:115]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by huchra.bufferbloat.net (Postfix) with ESMTPS id 0A36F201B71 for ; Fri, 26 Oct 2012 14:45:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=univie.ac.at; s=rev2; h=To:References:Message-Id:Content-Transfer-Encoding:Cc:Date:In-Reply-To:From:Content-Type:Mime-Version:Subject; bh=fQr/aqVSPoSeL4azMEZhVgv3eGbs5CyddEFs8tphpnY=; b=Oxw1+ohAkPRQZwKN/CEzExRh4s7xUbQLslQZ2TT5kWYktf3Muk/qlLeD2jwISilDmHQ6DQSd83gjWmu62bIFBtW6OhhP/lyOVAFIMtFjmWtiH/1i5GsIGvIJ09N55zGYJVRLmuD+dkOe1z/baP8Q5Rd2R6FGO+m1Lp1OcW/R1r4=; Received: from joan.univie.ac.at ([131.130.3.110] helo=joan.univie.ac.at) by grace.univie.ac.at with esmtp (Exim 4.80) (envelope-from ) id 1TRrii-0001nK-Nl; Fri, 26 Oct 2012 23:45:36 +0200 Received: from h081217009087.dyn.cm.kabsi.at ([81.217.9.87] helo=[192.168.37.128]) by joan.univie.ac.at with esmtpsa (TLSv1:AES128-SHA:128) (Exim 4.80) (envelope-from ) id 1TRrii-00052Q-IQ; Fri, 26 Oct 2012 23:45:36 +0200 Mime-Version: 1.0 (Apple Message framework v1085) Content-Type: text/plain; charset=us-ascii From: Albert Rafetseder In-Reply-To: <1210261854.AA17675@ivan.Harhan.ORG> Date: Fri, 26 Oct 2012 23:45:35 +0200 Content-Transfer-Encoding: quoted-printable Message-Id: <6C8D51F5-687E-4094-8743-1BD38D7656BD@univie.ac.at> References: <1210261854.AA17675@ivan.Harhan.ORG> To: bloat X-Mailer: Apple Mail (2.1085) X-Univie-Virus-Scan: scanned by ClamAV on joan.univie.ac.at Cc: opensdsl@ifctfvax.Harhan.ORG 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 21:45:43 -0000 Am 26.10.2012 um 20:54 schrieb Michael Spacefalcon: > Albert Rafetseder wrote: >=20 >> You must also rule out ATM cell loss and reordering. Otherwise, there = is =3D >> too little data in your receive buffer to reassemble the transmitted = =3D >> frame (temporarily with reordering, terminally with loss). This calls = =3D >> for a timeout of sorts. >=20 > (...) > The issue of reordering is relevant only when there are 2 or more VCs > on the same physical circuit, and I have yet to encounter an xDSL > circuit of any flavor that is set up that way. > (...) > Cell loss: it can't be detected directly, and it manifests itself in > the reassembled AAL5 packets appearing to be corrupt (bad CRC-32 at > the end). If the first cell or some middle cell of a packet gets > lost, only that one packet is lost as a result. If the last cell of a > packet gets lost, the overall IP-over-ATM link loses two packets: the > one whose last cell got lost, and the next one, which appears to be a > continuation of the previous one. So that's another way in which ATM > on an xDSL circuit is worse than Ethernet or HDLC. I.e., you rule out ATM cell loss and reordering! :-) >> 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 jump to = the =3D >> next start of packet in the list, wherever it is. As long as you = 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 really =3D= >> small, this probably meant lots of head drop.) >=20 > 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. I'm suggesting a *ring* buffer. Let me try to sketch what I mean (view = in your favorite fixed-space font). ^r is the read pointer (output to = SDSL, head of the queue), ^w is the write pointer (input from HDLC, = tail). Pointers can only go right, but all addressing is done modulo the = buffer size, so you start over on the left side if you were ever to = point past the buffer. Currently, the read pointer processes "2", whereas the write pointer = will overwrite "A" next.=20 0123456789ABCDEF ^r ^w Now the read pointer has progressed a bit, but the write pointer was = much faster: xyz3456789rstuvw ^w ^r Obviously, ^w must not overtake ^r. The trick is now to push the read = pointer forward a bit instead of holding back the write pointer. Push it = how far? Far enough to buy us some headroom, e.g. given how likely you = estimate worst-case packets will accumulate. Finally, we will have lost = buffer slots (marked with asterisks) from the head of the queue, but = were able to save all of the new incoming data, which means no tail = drop: xyz!#$6*****tuvw ^w ^r > 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. The sketch above applies to both the list of addresses of cell starts = and the actual cell buffer. (You could also implement both ring buffers = as a single one, as a linked list: Store the address of the start cell = of the next packet in front of the cells of the current packet. To = head-drop packets, dereference the pointer multiple times. ASCII = diagrams on request :-) > 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. That's an interesting notion indeed. Still, even for sending cells from = packets that haven't fully gone into the ring buffer from the HDLC side, = I think that the approach described would work. The closer the write and = read pointers get, the more headaches, though.