Analyzing Acknowledgement Strategies
v...@lbl-csam.arpa.uucp
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.
- Van
Mi...@louie.udel.edu.uucp
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