On Thu, 3 Jun 2004, Adam Nellemann wrote:
> Chad R. Larson wrote:
> > Adam Nellemann wrote:
> >>
> >>Here's the theory behind why inbound shaping doesn't work (or at least
> >>doesn't work well) If anyone has knowledge to the contrary, please post:

It works, but it's less efficient to do it downstream of the choke point,
at least by the usual "packet drop" approach.

> >>Since there is no built-in "traffic control messages" (or similar) in
> >>TCP/IP, there is no way for m0n0wall to "tell" the device(s) on the
> >>"other side" of your WAN link (such as the router at your ISP's end of
> >>your ADSL line) to stop sending packets (or do so at a slower rate).
> > 
> > To the contrary.  The TCP "advertised window" is exactly that control.

Nope.  The TCP window was designed for *application* flow control, not
network flow control.

> > When a TCP packet is sent, one of the values in the header is the 
> > number of bytes the sender is willing to receive in return.  An ACK 
> > for all bytes and a window of 0 would be very similar to a CTL-S on a 
> > serial link, but varying the size of the window allows a smoother 
> > control of the flow than a simple start/stop.

It's not the right thing for that purpose, for a few reasons:

1) TCP doesn't provide reliable delivery of control information, such as
window updates.  In the original RFC793 version, the *only* means of
restarting transmission previously blocked by a closed window was
timeout-based retransmission of the window probe.  Most modern TCP
implementations send one "free ACK" when the window opens, but if that ACK
gets lost for any reason it falls back to timeouts.  Thus, the performance
of receiver-limited TCP tends to be very fragile on lossy networks.

2) The window specifies an *amount* of data, not a rate.  In order to
translate between the two, it's necessary for the receiver to know the
round-trip time of the path (in effect, the window size limits the
delay-bandwidth product, not the bandwidth per se).  But the receiver is
in no position to determine that in the absence of "ACKs of ACKs".

3) The receiver is never allowed to "reduce" the window, in the sense of
moving the window limit backward in the stream (the *size* of the window
can decrease as the ACK point moves forward, but the *sum* can never
decrease).  This puts a greater constraint on the throttling possibilities
than one would like.

TCP's congestion control (that regulates its send rate) also suffers from
the "too little information" problem like #2, but the other way - i.e. it
knows the RTT (sort of) but not the bandwidth.  It "probes" the bandwitdh
by continuing to increase the congestion window until it sees packet loss,
whereupon it reduces it.  At best this causes the rate to oscillate with
the *peaks* being the theoretical maximum, and hence the average is always
lower.

Note the stability problem:  TCP's only measure of RTT comes from time
from send to ACK, and its only throttle is by limiting the amount of
outstanding data.  If it doesn't increase the window when it's not
utilizing all the bandwidth, it will *never* utilize all the
bandwidth.  But if it increases the window after the bandwidth is
saturated, it just increases the queue length which increases the measured
RTT, which increases the delay-bandwidth product, which increases the
window needed to get the *same* bandwidth, etc., etc.  There is research
going on into rate-limited sending rather than window-limited sending, but
nothing in "production" AFAIK.

> This is very intersting info Chad! Sounds like it should be quite 
> possible to shape inbound traffic in a decent manner then (well, TCP 
> packets anyway).
> 
> Then the question becomes: Does the shaper in m0n0wall take advantage 
> of this possibility when shaping? And if so, how/when does it modify 
> the window?
> 
> Unfortunatly, I don't seem to remember reading anything about this in 
> the dummynet documentation I've seen :(

Probably because it has better sense than to do it that way. :-)

There are a few ways a router can tell a sending TCP to throttle back:

1) Drop packets.  This is the most common method, and not *too* bad if
done sparingly and *before* the choke point.  Doing it after the choke
point works, but wastes bandwidth where it's scarce.

2) ICMP Source Quench.  For some reason this never really caught on,
though it could provide feedback before getting to the point of dropping
packets.  I think this was partly due to the lack of standards for exactly
when to send them and what to do when receiving them.

3) Early Congestion Notification (ECN).  This is probably the best
approach in principle, but it's quite new and not widely supported.  The
idea is that a router can tweak flags in a packet to say that congestion
is becoming an issue, and this is reflected back to the sender along with
the ACK.  Properly supported, transmission could be throttled *before* it
becomes necessary to drop packets, and there's no problem doing this
downstream of the choke point.

On Thu, 3 Jun 2004, Dinesh Nair wrote:
> On Thu, 3 Jun 2004, Adam Nellemann wrote:
> 
> > This is very intersting info Chad! Sounds like it should be quite
> > possible to shape inbound traffic in a decent manner then (well, TCP
> > packets anyway).
> 
> it _can_ if it wants to. :0
> 
> seriously, justin ellison's magic shaper rulesets do take advantage of
> this window, at a cost of sacrificing about 10-15% of your download
> bandwidth. let's assume that your isp gives you 1Mbps download, and you
> set the incoming pipe bw to be 900Kbps. thus, as your downloads reach
> 900Kbps, the receiver will start throttling the sender using the tcp
> window mechanism described above.
> 
> justin should be releasing his magic shaper soon, me thinks.

I'd give that one a pass.

					Fred Wright