Subject: Modifications to MACAW

From: "Dave Springall" <[email-masked]>
Date: Tue, 15 Sep 1998 18:25:01 +0100

>
>I, for one, would be very interested in a brielf description of what
>modifications you
>performed on MACAW to allow guaranteed broadcast packets in hidden terminal
>environments..
>Can you provide me with one?
>
>--thanks,
>  --chane
>

If my memory serves me correct, the modification that was made to MACAW
was as follows:

When sending a broadcast, the originating station sends a standard unicast
message to all neighbouring hosts.  If a station receives the "broadcast"
that it has already seen then, it will send an ACK back to the originator,
instead of a CTS.   The originator will not retry sending a "broadcast"
message to a station that doesn't respond to its initial RTS, but instead,
iterate to the next station in its list of neighbouring hosts.   The
originator will iterate through the stations until all stations have
received or the loop has closed or iterated n times (or after a certain
period).  This
was a parameter I was working on through several simulation scenarios.

The list of neighbouring hosts is obtained by logging the originator id of
all neighbouring traffic.   This list was aged and "stale" entries were
purged from the list periodically.   A station idle for a certain period
would send a beacon packet.   This is obviously controversial because of the
obvious power considerations, however batteries are much better than they
used to be, and the beacon packet doesn't have to be sent very often.

A few notes:  this whole scheme becomes more efficient when tightly coupled
with the routing protocol.   Routing information can be piggybacked on RTS,
CTS, ACK, BCN (beacon) packets and the "neighbouring host" table also can be
used by the routing protocol (such as SSA) to actively avoid the need to
send broadcasts.

My changes to the MACAW protocol may seem a little brute force, but I have
observed that the performance hit of a broadcast packet ignoring the hidden
terminal problem is very considerable: I can't remember the precise figures
but the event of a network flood practically stops normal transmission of
data.  The lack of reliability is also a consideration, for example, on a
busy network, a single broadcast is often missed.   This could possibly
prevent a route request flood from propagating across the "link" between two
busy clusters of nodes.

The RTS-ACK optimisation means that the data only gets transmitted once
within a locality (although several RTS-ACK exchanges may take place).
However, a queue of nodes that have received the broadcast could be put into
the RTS to further optimise this.  Another "however" would be also to say
that in the case of DSR, some of this information is available in the DATA
anyway.

I also added 10-15% efficiency to MACAW in certain hidden terminal
situations (with a modest improvement in others, and as far as I know, no
situations where the efficiency was less) by modifying the MILD algorithm.
I used the number of hosts in the "neighbour list" table to adjust the
backoff(max) value (not the back off value itself, but its upper limit).  I
found that in certain situations the backoff value was getting too high, and
the linear decrease was not reducing the counter fast enough.

Dave Springall