collision avoidance

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

I've been experimenting with some of the mechanisms I need to do the
modified collision avoidance algorithm I discussed a few days ago.

The other day I added a feature to my developmental version of the AX.25
code to monitor the destination addresses in overheard AX.25 frames; it is
an exact counterpart to the existing "heard" mechanism that monitors source
addresses. (Special provision is made for frames including digipeaters in
both routines, since in this case I'm interested in the actual physical
transmitter or receiver, not the original source or the ultimate
destination.)

I also modified both database lists so that whenever an entry is updated, it
is moved to the top of the list. This effectively sorts the list in
most-recently-used order, making the output listing nicer. To do this, I had
to get rid of the hash chain header array and go to a single linked list for
each database. I am hoping that the MRU autosorting will more than overcome
the performance loss caused by the removal of hashing.  (Assuming a good
locality of reference in addresses, which seems likely, the average linear
search length will be very short even if the list is long.)

My plan is to use both the source and destination databases to influence the
transmitter holdoff I mentioned earlier. When you monitor a frame, you look
up the frame's destination in the source (heard) database.  If the address
is not there, or if the entry is "old", then you treat the station as hidden
and inhibit your transmitter long enough to allow the addressed station to
send a complete transmission without colliding. If the address has a
"recent" entry in the source database, then the station is not hidden and
you need wait only long enough for the station to seize the channel if it
wants to - several keyup delays, say.

My thinking here is that if a station isn't hidden, then you only need wait
long enough for it to seize the channel if it's going to send something; if
it does transmit, you'll hear it and that will hold you off the channel.  If
it has no more data to send, then you can go ahead and seize the channel
yourself. You need hold off for the length of a complete transmission only
if the remote station is hidden, since you don't know if it's transmitting
or not.

I need to pick figures for "old" and "recent"; I'm inclined to use
a number on the order of a round trip time, but I'm open to suggestions.

I also need to make special provision for broadcast addresses; since no
station (is supposed to) transmit with a broadcast address in the source
field, my algorithm would treat them all as hidden stations unless they're
recognized and treated specially. I'd like to build in a complete list of
AX.25 broadcast addresses if I could. The ones I know about so far are QST,
CQ, NODES, MAIL, BEACON and ID. Are there others?

Phil