collision avoidance

[karn@ka9q.bellcore.com (Phil Karn)]

Sorry I haven't been too talkative lately - I haven't even had a chance
to go through the tcp-group mail for the last week yet.

I have been active, though, experimenting with some simple ways to
reduce channel collisions. This was motivated by frustration in
trying to get something approaching the potential performance out of
my 56kb/s WA4DSY modems.

The modems themselves work fine. I could ping one from the other and lose
maybe 5 packets out of 1000. (One run lost no packets at all out of 1000).
TCP transfers with mss == window also work quite well.

The problem comes when you use TCPs with configurations more typical
of the Internet (mss=1460, window=8K). FTPs really bogged down with
these settings.

A little investigation and thought revealed the following. As slow-start
begins, TCP sends only a single packet and waits for an ack.  It and the ack
get through fine. The returning acknowledgement causes TCP to open its
congestion window to two packets, and they go out back-to-back. The receiver
returns two acknowledgements, but unfortunately (for various reasons,
including disk access delays) they come out with a slight carrier gap
between them. The first ack causes the sending tcp to open its window to
three packets and begin sending them, frequently colliding with the second
ack coming back from the receiver.

The sending TCP times out, backs off, and retransmits a single packet (the
one missing). It gets through and is acknowledged, but because it had been
retransmitted the retransmission timer is left at its backed-off value (this
is the "Karn algorithm" at work). TCP proceeds to ramp up the congestion
window again, sends two packets, and collisions start again. Unfortunately,
the retransmit timer was never given a chance to come back to its "normal"
value, so it just keeps on climbing as data collides with returning acks.

Last weekend I decided to finally implement the MACA scheme I talked about
in my last ARRL conference paper. I first implemented a driver primitive
called "mute" that allows me to inhibit the transmitter for some specified
interval. (This was easy to implement - it's combined with the p-persistence
test. It is exactly as though I set p=0 for some period of time, and then
return it to its normal value). The purpose of the mute primitive was of
course to implement the MACA requirement that receiving a CTS message
inhibits your transmitter for some specified interval unless it is directed
at you.

While testing this feature I had an idea. The whole purpose of MACA is to
keep you off the channel when you know somebody else is about to transmit.
In MACA this is done explicitly with the CTS message. But in reality, almost
ANY message (data OR ack) is essentially an invitation for the addressed
station to send something (data will elicit an ack, and an ack often, but
not always, elicits more data). So instead of using explicit RTS/CTS
messages, why not just do the following:

1. If you overhear a packet addressed to somebody else, inhibit your
transmitter for X milliseconds.

2. If you finish transmitting a series of packets, inhibit your transmitter
for X milliseconds. (This is really just a special case of #1, and it
wouldn't have to be explicitly stated if we all had full duplex interfaces
that could monitor our own packets.)

3. If you receive a packet addressed to you, cancel the previously set
transmitter inhibit, if any.

I used inhibit intervals of 500 ms with my wa4dsy modems, and the
improvement was dramatic. FTPs actually work pretty much as expected,
although there is some interaction with the p-persistence algorithm
(sometimes the other station defers so long that the first station's
inhibit interval expires first).

The effect of this algorithm is to get away from the current packet radio
paradigm of contending anew for the channel each and every time you key up.
As long as two stations keep a dialog going, everyone else will defer to
them until they are done (i.e., pause for a while).  Then the stations
waiting to send traffic contend with each other and a new pair of "winners"
are chosen.

There has always been a tradeoff between fairness and efficiency in packet
radio; it's a fact of life. This algorithm allows us to move from complete
fairness (i.e., nobody gets through because of all the collisions ;-))
toward overall efficiency. What I'd like to do now is to make it possible to
tweak a "knob" and select some sort of compromise between fairness and
efficiency, ie., to keep a pair of stations from hogging the channel
indefinitely during a very long file transfer.

One way of doing this is to combine the transmit mute/inhibit feature with
p-persistence. In effect, I want a time-varying value of p, influence by
what you hear on the channel. If I overhear a packet sent to somebody else,
I decrease my p value almost (but not all the way) to zero and let it slowly
rise again. If I get a packet addressed to me, I increase p to 1 and let it
decrease again.  In this way, a pair of stations sending packets back and
forth will most likely get it again, but there's a small probability (on
each packet) of another pair jumping in and taking the channel away. In
other words, you can almost "time slice" the channel, with "task switching"
done in a distributed, probabilistic fashion.

Ideas? Comments?

BTW, I have an idea to make TCP a little more tolerant of the problem
I discussed earlier, independent of fixes at the link layer. I haven't
tried it yet, but my plan is to delay the reopening of the congestion
window after a timeout to first allow the retransmit timer to return
to its regular value.

Phil