craig@LOKI.BBN.COM.UUCP (12/24/86)
Has anyone done any work analyzing acknowledgement strategies on
a theoretical level?
It seems to me there is an inherent conflict in choosing acknowledgement
strategies. To reduce unnecessary retransmissions of data packets, one
wants to make sure data packets get acknowledged. But the best (only?)
way to make sure acknowledgements get through is to send more of them.
It is easy to identify bad strategies. A system which sends twenty
acknowledgements for every packet is a bad strategy because the number
of unneeded acknowledgements sent will clog a network more than the
reduction in unnecessary retransmissions (because an ack was lost)
could ever reduce network traffic. Similarly, a system which acknowledges
too little abuses the network because too many data packets get
unnecessarily retransmitted -- up to a point acknowledging more often
will reduce the *total* number of packets sent. (At least that's what
testing with RDP shows).
The problem is identifying where these tradeoffs balance out --
where the range of optimal solutions lies (if anywhere) in this space.
Has anyone ever looked at this issue?
Craigleiner@ICARUS.RIACS.EDU.UUCP (12/25/86)
Craig, Of course. This is basically the same as ARQ on a noisy channel, and there has been considerable analysis of such things. Also, comparisons with forward error correction. The thing that makes it difficult in the case of packet networks is the uncertainty on both the error characteristics (which can be handled via adaptive error detection/correction techniques) and delay. The latter is what makes the packet network ARQ problem different than the link error problem. On a link, the delay is pretty much constant, and so you know how long to wait for a time-out. In a packet network of the sort we typically deal with, that delay is statistical and must be dealt with as such (estimated, tracked, use maximum, etc.) Barry ----------
van@LBL-CSAM.ARPA.UUCP (01/13/87)
Craig -
I tried to do some work on analytic models of transport
protocols a couple of years ago. I have kept watching but
haven't found much in the ARQ literature that reflects realistic
protocol implementations. There were 6 or so papers whose
*method* looked like it could be adapted to the analysis of TCP
or RDP. Two that I kept in my "potentially useful" file were
Easton's "Batch Throughput Efficiency of ADCCP/HDLC/SDLC
Selective Reject Protocols", IEEE COM-28, No.2, Feb, 80, and Wai
Sum Lai's "Analysis of Piggybacking in Packet Networks", (this
was in the proceedings of one of the Berkeley Workshops on
Distributed Data Management and Computer Networks but I don't
know which one. Probably the fourth, 1979). A more recent paper
that looked interesting was "Performance Analysis of the
Selective Repeat ARQ Protocol" in COM-34, No.2, Feb, 86.
I wasn't sure from your msg what objective function you wanted
to optimize and what you viewed as constraints. I was trying to
model a net where
- each connection wished to maximize its throughput (as opposed
to maximizing total network throughput)
- aggregate network bandwidth is a limitting resource (i.e., data,
acks and other connections all compete for the same bandwidth)
- the population of users is large (i.e., the potential offered
load is many times the available bandwidth)
- all connections use the same send/ack policy and sends from
different connections are initially i.i.d.
- all packets go through gateways and the host-gateway path has
much higher bandwidth than the gateway-gateway path.
- gateways have finite buffer capacity
- packets are subject to loss by both damage and congestion.
Using some of the ALOHA analysis, you can show that any protocol
that deals the first six constraints must be fair and must be very
conservative with retransmissions (because congestive collapse is
exponential). The congestive-loss constraint made the problem
novel and I got some simulation results that might explain some of
the behavior you observe.
If we make the usual assumption of a constant bit error rate,
damage loss is a linear function of the traffic. Congestive loss
is a function of the packet interarrival times (i.e., the derivative
of traffic w.r.t. time). I made a loss model that looked like
L(N) = (a + b dN/dt) N
where L is the number of packets lost and N is the number of
packets sent (including retransmissions). I then did a cluster
analysis and a regression on a bunch of trace data to get
empirical values for a and b. Since I had first become interested
in gateway behavior when I noticed the large amount of congestive
loss, I wasn't surprised to find that b was three to four orders
of magnitude larger than a.
This note is already too long so I'll state, without background,
some preliminary, *simulation* results (I hope to one day have
analytic results but am presently hampered by massive mathematical
ignorance).
- The network is wildly unstable under most send/receive policies
if the rtt estimates are bad.
- If the window is W packets and the round trip time is R, the
sender policy that maximized throughput was to keep
W/R <= dN/dt <= 2W/R (i.e., spread the packets uniformly over
the rtt interval but still fill the pipe). Under heavy
congestion it also helped to inject some random variation into
the packet send times.
- If the sender doesn't try to spread out packets, it is unwise
for the receiver to delay an ack for more than half the average
packet interarrival time. An ack for multiple packets will
make the sender generate a burst of packets to fill the
window. Any time a burst is sent, the probability of loss goes
up quickly. (If you were testing on a lossy path, this may have
been what was happening when you observed that increasing the
number of acks increased the throughput.)
- If the sender doesn't try to spread packets, retransmissions
(usually) result in a burst of packets, that results in loss, that
results in retransmissions, that .... Most tcp's are guilty of
this burst, including 4.[23]bsd. It's this mis-behavior of
tcp which I believe accounts for you and others observing better
throughput with RDP than TCP. This is simply because the EACK
makes it less likely that a naive protocol implementation will
generate a burst of packets. ("Naive" means "naive of interarrival
time effects".)
While I never got any of the preceeding into a publishable form, I
have gone over some of the trace data and simulation results with
Mike Karels. I think we've agreed on a change to the 4bsd tcp
retransmission policy and hope to implement and test it soon. In
(limited) simulation, the new policy reduced the number of
retransmissions by a factor of four and increased the throughput
under heavy congestion by a factor of two.
Hope some of this was useful. If you have time to summarize, I'd
be interested in anything you learned from the replies to your query.
- VanMills@LOUIE.UDEL.EDU.UUCP (01/13/87)
Van, You are doing some fantastically wonderful stuff that should have been done long ago. Your conclusions coincide closely to my observations and probably many others, especially with respect to bunching (aka spasms), especially with Unix systems using humungus windows over lossy paths. One thing was not clear from your note. Did your simulations include the use of the Nagle Algorithm? Some years ago when I was experimenting along with others on TCP models I built a flow estimator into the code which produced in effect your dN/dt. It was designed to produce exactly the result you describe - spreading the packets uniformly over time. I also intended to build an estimator for dL/dt as the loss rate (did I get your nomenclature backwards?), but something else distracted me. However, I did wire up a couple of D/A converters to panel meters on my desk so I could see the estimators in action. One was the SRTT and the other the dN/dt. Boy, did I get an eyeful watching these gizmos in action as tings clogged and unclogged. If there weren't so many other beasties squealing for attention, I'd like to dive back in those issues again. The results might well have a profound effect on second-generation ISO transport protocol implementations. Idea: Use median-filter estimators instead of linear, recursive-filter ones. I found the former extraordinarily effective for comparing clocks across the swamps, which means they should work well for SRTT as well. My variant, which doesn't have a proper name, is as follows: save the last n RTT samples and sort them. Identify the median (dither if you have to if the number of samples is even), then toss out the extremum furthest from the median. Repeat until only a single sample is left. Season for the endgames. Serve with appropriate timeout, so that really old info is discarded. I have been using sample windows of eight. Keep up the good work. Dave
van@LBL-CSAM.ARPA.UUCP (01/15/87)
Dave -
Thanks for the kind words. I wish the DOE felt the same way.
My network research funds were cut off a year ago because "DARPA
funds transport protocol research, not DOE". While trying to
find new money, I got the impression that no one funds transport
protocol research since transport protocols are a "solved
problem" (this while the mean Arpanet transit delay was 15
seconds -- I tried to laugh but it hurt too much).
I'm not sure which Nagle algorithm you mean. I was assuming
instantaneous sources and sinks on each end of a connection so
all segments sent were the max segment size. So the
accumulate-until-the-ack Nagle algorithm didn't apply. I didn't
know about the send-one-packet-when-retransmitting algorithm at
the time and didn't simulate it.
I did do an empirical test of the Nagle retransmit algorithm
shortly after we brought up 4.3bsd. I ran an A-B-A-B test with
and without the algorithm (4.3 uses the algorithm) and took
statistics on sends, acks, rexmits, etc.. Each of the four test
phases ran a week. Local network traffic made it hard to assess
the results but it was clear that using the algorithm reduced the
number of retransmitted packets by about 30%.
I expected the effect to be larger. A quick look at some trace
data suggested that there was a problem when you resumed normal
behavior after a retransmit. Since you'll always be sending into
an empty window at this point, 4.3 will blast out 8 back-to-back
packets. A couple of packets near the end of this blast are
almost certain to be dropped so you'll end up in retransmit state
2 RTT after the previous recovery. The new algorithm we want to
try is designed to filter this turn-on transient.
I didn't look at median filters while looking at RTT estimators
but I did investigate several other FIR filters. I think that in
the clock sync problem you want a filter with good low pass
characteristics. For RTT, I wanted a filter with good transient
response: Because congestion builds up exponentially, if it's
detected late senders have to take drastic action to clear it and
throughput really takes a hit. If it's detected early senders
can make small adjustments to damp it out and throughput is
hardly affected. The simulations suggested that "early" was
really early -- within 3 to 4 packet times of the onset.
The problem with FIR filters was that there's usually a
discontinuity in the RTT samples at integer multiples of W, the
window size in mss packets. If the filter was short or tapered
enough to have good transient reponse, this discontinuity wiped
it out. If the filter was long enough to smooth the
discontinuity, it had no transient response.
Measuring RTT and output packet rate is essentially estimating
a parameter and its time derivative. This is the well known
"radar tracking problem" (estimating distance and velocity from
radar return echos) and my original estimator was a copy of the
IIR alpha-beta tracker equation from a GE radar handbook. This
had trouble because it's fixed gain. When the network is not
congested there's a lot of stochastic noise and the filter gain
has to be low to ignore this noise. When the network starts to
get congested, the stochastic noise gets squeezed out and you
could use much higher gain. Investigation of variable gain
filters led me to the Kalman's work on optimal stochastic
estimators.
A Kalman filter seems ideal for this problem. It's simple,
computationally efficient (6 parameters instead of the current 1
but all integer arithmetic) and always has the maximum gain that
the data supports. Also, if the underlying model is at all close
to reality, it's self tuning so network administrators don't have
to be mathematicians. I was just going to start on a
Box-Jenkins' style gateway model identification when the money
ran out. I keep intending to work on this in my copious free
time but ....
- Van
ps- perhaps we should take this discussion off line? I've been
filling up peoples' mailboxes lately and I get the impression
that there are only two or three of us interested in this topic.mike@BRL.ARPA.UUCP (01/16/87)
I vote for keeping it on the list. I'm keenly interested, but working on that level of the protocol always seems to stick about 3/4 of the way down on my queue; I think it's hopeless. I'll never get time to tinker down there again. But I do enjoy reading about somebody else doing an excellent job. Keep up the good work, and don't go underground! Best, -Mike
Mills@LOUIE.UDEL.EDU.UUCP (01/16/87)
Van, You are probably right that some mailboxes out there are creaking, so let's take this offline. If anybody else is interested, please honk. I gave up on linear filters some time ago for clock-synch. That's when I discovered median filters, which work like a razor through toothpaste in my experiments. I suspect they would work well for RTT as well. I thought of Kallman and Shannon and etc., but those dudes are all linear. I got to many bent edges. Dave
KLH@SRI-NIC.ARPA.UUCP (01/16/87)
No, no, please keep the discussion going here. It's so rare for anything really interesting to come along... thanks! -------
mckee@MITRE.ARPA.UUCP (01/16/87)
>ps- perhaps we should take this discussion off line? I've been > filling up peoples' mailboxes lately and I get the impression > that there are only two or three of us interested in this topic. I expect/hope many people are interested. The current MIL-STD 1777 and 1778 are incomplete; they need a section called Implementation Guidelines. The work that you, Mills, Nagle, Partridge, et al are doing will be the basis of that section. At any rate, while I can contribute little more than intense interest, please include me in your discussions. I would particularly like to hear from John Nagle on: >A quick look at some trace data suggested that there was a problem >when you resumed normal behavior after a retransmit. Since you'll >always be sending into an empty window at this point, 4.3 will blast >out 8 back-to-back packets. A couple of packets near the end of this >blast are almost certain to be dropped so you'll end up in retransmit >state 2 RTT after the previous recovery. I would offer the following comment: Packets are lost by Gateways, not PSNs. The PSNs can protect themselves against an input overload from subscribers; Gateways can only whimper Source Quench. Accordingly, we should thump on the egp-people people to "do something." Regards - Craig
LYNCH@A.ISI.EDU.UUCP (01/16/87)
I vote with Mike. Van and Dave are exploring critical issues and exposing the sad fact that support for this kind of research is not too big, but the problems are not going away. We wil never be able to build useful (and complex) internets until we have solid methods for controlling packetorhea. Dan -------
Mills@LOUIE.UDEL.EDU (01/19/87)
Henry, Thanks for the vote. So far as I know, I have not restricted distribution of any of my bleats, just answered what was sent. In the twinkle of keys I may have blown that model. You raise a good point, also raised by Gonzoles Arse here: why recurse on the median filter? The sample data I have collected here are almost always strongly skewed. They tend to be clustered more-or-less generally about a median, but with a significant population of gross outliers. The particular technique I evolved had a rather high seat of pants, but worked fantastically well with Internet delays. Dave
mckee@MITRE.ARPA (H. Craig McKee) (01/20/87)
>ps- perhaps we should take this discussion off line? I've been > filling up peoples' mailboxes lately and I get the impression > that there are only two or three of us interested in this topic. I expect/hope many people are interested. The current MIL-STD 1777 and 1778 are incomplete; they need a section called Implementation Guidelines. The work that you, Mills, Nagle, Partridge, et al are doing will be the basis of that section. At any rate, while I can contribute little more than intense interest, please include me in your discussions. I would particularly like to hear from John Nagle on: >A quick look at some trace data suggested that there was a problem >when you resumed normal behavior after a retransmit. Since you'll >always be sending into an empty window at this point, 4.3 will blast >out 8 back-to-back packets. A couple of packets near the end of this >blast are almost certain to be dropped so you'll end up in retransmit >state 2 RTT after the previous recovery. I would offer the following comment: Packets are lost by Gateways, not PSNs. The PSNs can protect themselves against an input overload from subscribers; Gateways can only whimper Source Quench. Accordingly, we should thump on the egp-people people to "do something." Regards - Craig --------
stever@videovax.tek.com ("Steven E. Rice") (01/22/87)
The "automatic" mailing software dropped the ball, so we'll try again: From: stever@videovax Newsgroups: mod.protocols.tcp-ip Subject: Re: Analyzing Acknowledgement Strategies Message-ID: <4160@videovax.Tek.COM> Date: Fri, 16-Jan-87 19:41:18 EET References: <8701151850.AA18157@lbl-csam.arpa> Reply-To: stever@videovax.Tek.COM (Steven E. Rice, P.E.) Organization: Tektronix Television Systems, Beaverton, Oregon Lines: 22 Summary: Please continue to let us in on the discussion! In article <8701151850.AA18157@lbl-csam.arpa>, Van Jacobson (van@LBL-CSAM.ARPA) writes: > Dave - [ body of the article deleted ] > - Van > > ps- perhaps we should take this discussion off line? I've been > filling up peoples' mailboxes lately and I get the impression > that there are only two or three of us interested in this topic. I cannot speak for anyone but myself, but I appreciate seeing the discussion of these issues. I am not at present directly involved with such networks, but the problems discussed are food for thought and the solutions proposed have bearing in other areas. Steve Rice ---------------------------------------------------------------------------- {decvax | hplabs | ihnp4 | uw-beaver}!tektronix!videovax!stever