Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!ames!ucbcad!ucbvax!geof@decwrl.DEC.COM@imagen.UUCP
From: geof@decwrl.DEC.COM@imagen.UUCP (Geof Cooper)
Newsgroups: mod.protocols.tcp-ip
Subject: Re:  Analyzing Acknowledgement Strategies, continued
Message-ID: <8701191933.AA00226@apolling.imagen.uucp>
Date: Mon, 19-Jan-87 14:33:55 EST
Article-I.D.: apolling.8701191933.AA00226
Posted: Mon Jan 19 14:33:55 1987
Date-Received: Tue, 20-Jan-87 04:59:36 EST
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: imagen!geof@decwrl.DEC.COM
Organization: The ARPA Internet
Lines: 96
Approved: tcp-ip@sri-nic.arpa

I did some research on timers in TFTP at MIT in 1983, with Karen
Sollins and John Romkey.  The problem at hand was to develop a 
strategy that made TFTP work on both 1200 baud lines and ethernets.
We had time for exactly one test, and it worked in that test.  After
that I left MIT and no one else was interested in tuning the algorithm
further.  I don't have a SCRIBE implementation that is willing to output
this thing without a fuss.  I hesitate to send the note to the entire
list, although it is short.  Perhaps someone would like to be mailed
a copy and act as an FTP gateway for the rest.

The algorithm is different from one previous to it in that it used
something similar to the "timeline" strategy that you outlined.  In
this case, I used the number of retransmissions of successive packets
as an indicator.  I concentrated on avoiding congestion and not on
recovering from lost packets.  The algorithm is interesting in that
it is two algorithms -- one is invoked if everything is going well,
and the other is invoked if recent history suggests that congestion
is going on.

The basic idea was to "get the hell out of there" when you detected
that you were sending multiple retransmissions of each packet.  In
this case, the algorithm increases as N^2 with each successive sample.
The algorithm comes down using a 2-element linear filter [(this+last)/2].
Measurements of the roundtrip time are made only when no retransmissions
occur.  This is the only way that the roundtrip timer can be tightened.
The N^2 backoff can happen any time.

The following is a rough outline of the algorithm.  Recall that in TFTP,
only one data packet can be outstanding.  This packet is retransmitted
until an ACK is received and then the next packet is sent.  Thus, it is
equivalent to a sliding window protocol with window size 1, where each
ACK opens the window.  The particular ACKing strategy is not important,
except that at least one ACK must be generated for each data packet
received.

NT means Number of Transmissions of the current data packet.
(NT = 1) => packet sent once.  When an ACK is received execute:

    MeasuredRoundTripTime := TimeReceivedFirstAck - TimeSentFirstData;
    
    if last_NT = 1 then
        K := K_Init;
    
    if NT = 1 then
        RountripTime := ( MeasuredRoundTripTime + RoundTripTime ) / 2
    else
        begin
            if last_NT > 1 then
                K := K + K_incr;
            RoundTripTime := RoundTripTime + K
        end;

    last_NT = NT;
    NT := 0;
    
When sending a packet, execute:

    RetransmitTime = (1.5 * RoundTripTime) * 2^NT;
    NT := NT + 1;

Initial values are chosen to overestimate the roundtrip time.

======================


Also, Raj Jain (who at least was then) of DEC did some work on retransmission
strategy.  He did some simulations while at MIT's lab for computer science,
and wrote a paper on the results.  I have a draft version of the paper.
It was to be published, but I don't remember where, and I never saw it come
by in print.  Maybe I missed it.  Here is the abstract:

    DIVERGENCE OF TIMEOUT ALGORITHMS FOR PACKET RETRANSMISSIONS
        Raj Jain
        DEC Hudson HLO2-3/N03

    The problem of adaptively setting the timeout interval for retransmitting
a packet has been discussed.  A layered view of the algorithms has been
presented.  It is shown that a timeout algorithm consists of essentially
five layers or procedures which can be independently chosen and modified.
A number of timeout algorithms proposed in the literature have been
decomposed into these five layers.

    One of the key layers not discussed in the literature is that of
determining the sample round trip delay for packets that have been transmitted
more than once.  It is shown that this layer has a significant impact on the
network performance.

    Under repeated packet loss, most timeout algorithms either diverge
or converge to a wrong value.  A number of alternative schemes have been
presented.  It is argued that divergence is preferable to false converence.
It is a feature that is helpful in reducing network traffic during congestion.

    DEC-TR-329
    Version: August 28, 1985

- Geof