Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site petrus.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!gamma!epsilon!zeta!sabre!petrus!karn
From: karn@petrus.UUCP (Phil R. Karn)
Newsgroups: net.ham-radio.packet
Subject: Link Layer thoughts
Message-ID: <777@petrus.UUCP>
Date: Mon, 23-Dec-85 06:56:14 EST
Article-I.D.: petrus.777
Posted: Mon Dec 23 06:56:14 1985
Date-Received: Wed, 25-Dec-85 01:01:25 EST
Organization: Bell Communications Research, Inc
Lines: 160

Recently I've been thinking about ways to improve the performance of
link level protocols on noisy links, and I came across a very interesting
idea.

In the paper "ALOHA Packet Broadcasting - A Retrospect", by Binder, et. al.,
published in the 1975 (10 years ago!) National Computer Conference, are the
following interesting sections:

[KA9Q Note: the "MENEHUNE was the ALOHANET's packet switch, analogous to
our TNC. Its name is an obscure wordplay. The ARPANET people were calling their
packet switches "IMPs" (Interface Message Processors), so the ALOHA people
simply chose the Hawaiian word for "imp", as in "mischevious dwarf".]

"Error control for broadcast channel data packets (MENEHUNE to user nodes)
involves some special considerations. For efficient operation, the usual
positive acknowledgment scheme in which the ACK's themselves are not
acknowledged depends on a high probability of the ACK's being successfully
received. However, an ACK sent from user nodes must compete with data
traffic in the random access channel. At full channel loading each
random access packet must be retransmitted an average of 1.7 times,
which means each data packet or ACK must be sent a total of 2.7 times on
the average before it is successfully received. But in order to force
retransmission of the ACK's, the data packet being acknowledged must
also be sent an average of 2.7 times by the MENEHUNE - even though it
was received correctly the first time!....

[ka9q note: these numbers come from the fact that running a pure ALOHA
channel at the optimum throughput level of 1/2e or 18.4% requires
an "offered load" of 1/2 or 50%. I.e., the channel will have at LEAST
one carrier on it 50% of the time, but only 18% of the time will there
be ONLY one carrier. This means that each packet has a probability of
(1/2e) / (1/2) = 1/e = 36.8% of making it across, and therefore packets
must be sent on the average 1/(1/e) = e = 2.718 times to make it across
once.]

"...to eliminate the unnecessary repetitions of data packets from the
MENEHUNE, it is also necessary to acknowledge the ACK. That is, the ACK
sent by a user node is timed out and retransmitted until an
acknowledgement for it is received, just as for data packets. If another
packet is waiting for transmission to the node at this time, its
transmission with the next sequence number constitutes the ACK to the
ACK; otherwise, a short ACK-ACK packet is sent by the MENEHUNE. This can
be easily shown to result in significantly less total channel overhead,
at the expense of more complication in the node implementation."

I was intrigued by this idea and decided to study it further. What follows
is my initial analysis of the ACK-ACK protocol and how it compares to
the current AX.25 protocol.

In AX.25, ACKs are not acknowledged. This means that if the probability of
getting a packet across a given channel is p, then on the average, A = 1/p
transmissions of the ACK by the receiver will be necessary for the sender to
get one back. To elicit 1/p ACKs from the receiver, the sender has to send
D = 1/p * A = 1/(p**2) data packets. For example, if p = .5 (50% probability
of getting a packet across the channel), then you can expect, on the average,
A = 2 transmissions of the ACK and D = 4 transmissions of the data packet
before sender can go on to the next data packet. If p = .25, then A = 4 and
D = 16.

Note I've assumed for sake of illustration that p is equal in both directions;
in the "real world" a data packet is a bigger target than an ACK and is
therefore even more likely to get clobbered.

To show the effect of ACK-ACKs, I'll define a number N, the ratio between
the sender's data-retransmission timer to the receiver's ACK-retransmission
timer. We assume that this number is always greater than 1. (If it wasn't,
the sender would always time out and resend the data before the receiver
ever gets a chance to retransmit its ACK). N therefore represents the number
of times the receiver will attempt to retransmit its ACK before the sender
unnecessarily resends its data packet (which is what we'd like to avoid).

The probability P of getting an ACK through at least once in N transmission
attempts when each attempt has probability p of succeeding is

P = 1 - (1 - p)**N

Make N large enough, and P approaches 1 (i.e., the ACK will almost certainly
get through.) Of course there will still be plenty of data packet
retransmissions, simply because (1-p) of them will never make it to the
receiver in the first place. So the total expected number of data packet
transmissions D changes from 1/(p**2) in the present case to (1/p) * (1/P)
with ACK-ACKs. Let's plug in some numbers and see what effect this has
on D, the expected number of data packet transmissions.

p = .5, N = 5, no ACK-ACK case:
     D = A * 1/p = 1/(p**2) = 1/(.5*2) = 4
same, with ACK-ACKs:
     P = .969
     D = (1/p) * (1/P) = 2.06, a 49% decrease

p = .25, N = 5, no ACK-ACKs:
     D = 16
same, with ACK-ACKs:
 P = .763
     D = 5.24, a 67% decrease

You may be asking "what about the extra overhead of the ACK-ACK"? Recall
that a new data packet can serve as an ACK-ACK. So long as there is
a steady stream of traffic, "standalone" ACK-ACKs are never transmitted;
the next data packet provides that function. Only at the end of a traffic
burst is an extra packet generated, and this seems a small price to pay to
save all those unnecessary retransmissions.

So clearly we have something here. The question is how to implement it.

I am not certain that this technique can be adapted easily to LAPB,
the connection-oriented upper sublayer of AX.25 Level 2.  It may be possible,
but it would take some work. LAPB was originally intended for highly reliable
point-to-point links, and radical surgery may be necessary. In any event,
LAPB is an unnecessarily complex link level protocol for a datagram network,
so I already have a motivation for doing a lobotomy instead.

Fortunately, there are "hooks" in AX.25 that allow us to dispense with LAPB
and implement the ACK-ACK protocol while still conforming to the AX.25
addressing format. We need three types of packets to implement the ACK-ACK
protocol: a data packet, a regular ACK packet (sent in response to the data
packet) and an ACK-ACK packet (sent in response to the regular acknowledgment
when no additional data is available). Here's one possible assignment:

data packet - UI frame with or without Poll bit set
regular ack packet - UA, with or without Final bit set
ACK-ACK - empty UI frame with Poll bit cleared

The poll/final bits allow either or both acknowledgments to be optional. For
example, stations in a datagram network operating on high quality links with
very low packet loss rates might elect to operate without the overhead of
link level acknowledgments; in this case, each data packet is sent in a UI
frame with the poll bit cleared.  Similarly, when regular acknowledgments are
requested (i.e., with the poll bit set in UI data frames), the receiver uses
the final bit in the UA to indicate whether an ACK-ACK is requested. Since a
new data packet can be sent in place of an ACK-ACK, making both out of UI
frames simplifies the receiver implementation. In each case, setting the
poll/final bit means that some sort of response is expected from the other
side, which also simplfies the implementation.

Notice that there are no sequence numbers, since a sliding window protocol such
as LAPB is unnecessary on a half duplex channel. The protocol operates in a
lock-step fashion; there is always a one-for-one relationship between a data
packet and its acknowledgement, and this simplifies things enormously.
Since packets cannot "cross in the mail" on a shared half-duplex channel,
there is never any ambiguity as to which data packet an ACK refers to
(note that this assumption is violated and the protocol breaks down in two
situations: a long digipeater string where the end stations cannot hear each
other directly, and on a long-delay satellite channel where the round trip
delay exceeds the packet transmission time. Digipeaters we're already getting
rid of, and I'll worry about high speed satellite channels when we get
one.)

The only "state" required in the protocol is a buffer for the most recently
sent or received packet. (The transmitter may need to resend it and the
receiver needs to detect and filter out duplicates transmissions). However,
once a packet has been sent and fully acknowledged, no state needs to be
maintained, a MAJOR advantage when servicing a large number of mostly idle
local "links" with limited memory.

Comments and suggestions on this idea are welcome.

73,

Phil Karn, KA9Q