Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!decvax!ucbvax!LBL-CSAM.ARPA!van
From: van@LBL-CSAM.ARPA.UUCP
Newsgroups: mod.protocols.tcp-ip
Subject: Re: Analyzing Acknowledgement Strategies
Message-ID: <8701131008.AA20447@lbl-csam.arpa>
Date: Tue, 13-Jan-87 05:08:43 EST
Article-I.D.: lbl-csam.8701131008.AA20447
Posted: Tue Jan 13 05:08:43 1987
Date-Received: Tue, 13-Jan-87 18:59:05 EST
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 99
Approved: tcp-ip@sri-nic.arpa

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.

 - Van