a few random thoughts about channel access

[brian (Brian Kantor)]

Whilst having packet-radio nightmares again last night, a couple of
thought about channel access methods came to mind.  Here I go,
challenging assumptions again.

1. CSMA/CA is what we do to avoid collisions - we watch the channel and
wait until it's clear.  Most sophisticated people do it with
p-Persistance.  However, I think that a small variation in pP methods
would help throughput.

Simply, most of the pP implementations I've played with ALWAYS use
the roll-a-die-in-this-slot method - so when they go to transmit a
packet, they could conceivably wait one or more slottimes before they
transmit even though the channel is clear.  I think that if there is no
channel activity present the first time you have a packet ready to
transmit, you should simply go for it.  If the channel IS active, you
wait until it's clear, then you start doing the slot-delays.

This variation has the win that you'll never unnecessarily slot-delay
on a clear channel, but you will still gain the pP advantage of
avoiding the "lets all jump on the channel now that he's done" syndrome
which non-pP channel access methods exhibit.  Implicit in this is
that the generation of packets ready-to-transmit is somewhat random;
with maxframe set to one, even a high-volume data source like a BBS or
a sending FTP will exhibit this behaviour, since the next packet is, by
definition, not ready to transmit until the previous one has been
ack'd.

Problem with this one is implementing it; it probably means firmware
changes in everyone's TNC.  Arrgh.  Only the on-the-bus people can do
this in software.  Still, if you've got a DRSI card, you might give it
a shot and see if it helps.

2. Backoff.  Exponentially backing off when you don't get an ACK for a
packet has one tacit assumption that may be fatally flawed: that the
packet or its ack were lost due to congestion that can be cured by
reducing traffic density.  Yet on a packet radio network where packets
are lost randomly due to non-congestion-related causes (like static
crashes and passing Volkswagens), this assumption, if applied purely,
leads to backing off a lossy channel when in fact the right thing to do
is to be more aggressive!  (I recall one FTP session that had backed
off to an 8-hour retry time because I'd not limited backoff times and
it was a really lossy (50% or more dropped) channel.)

Some technique for noticing the degree of congestion and adjusting the
retry time is needed - perhaps something can be done along the lines of
noting other traffic on the channel and adjusting the exponent in the
backoff formula accordingly.  Algorithms which give greater weight to
the round trip time of successful (i.e., ack'd) packets are also a good
idea for combating the pathological-backoff problem that simpler
methods might generate.  Gotta think more on this one.

3. p-Persistance slottimes.  I'm wondering if we aren't really using
far too short a slottime.  On a network which has hidden stations (i.e,
90%+ of all ham packet radio networks), waiting a few milliseconds
because your coin didn't come heads-up in the current slot isn't going
to help - you're still going to stomp on the hidden station's packet
that he began transmitting those few milliseconds ago.  It seems to me
that you'd want the slottime to be more on the order of the
transmission time of the average packet, if indeed not of the
transmission time of the MAXIMUM packet.  That way, when you toss the
coin and lose in this slottime, the other guy gets a clear channel for
the whole packet, not just the beginning of it.  Implicit in the
use of short slottimes is the idea that you'll hear him and back off,
which simply isn't the case a really high proportion of the time.

Using slottimes on the order of one to five seconds (for a 1200 bps
channel) demands that you use technique #1 above; you'd really NOT want
to randomly wait some multiple of seconds on a clear channel.  It might
be smart to do this dynamically - if you're seeing packets but not
their acks, or acks but not the packets they're for, you've got hidden
stations and you should be using long slottimes.  Otherwise you're just
fine with slottimes on the order of the DCD response time of your
demodulator.  Again, this requires quite a bit of smarts, so the
on-the-bus people have an advantage, but the this one CAN be done with
KISS implementations, since the computer is getting all the packets and
can make the determination as to whether there are hidden stations
present or not, and adjust the TNC's slottime parameter accordingly.

Comments?
        - Brian