MAC MEDIA ACCESS CONTROL
Problem
Many planes have messages to send, but if two send simultaneously, neither succeeds.
Background
Media Access Control resolves contention for the shared communication channel. There are many approaches to the problem:
Random Access
ALOHA was developed when MAC issues were first investigated (at the University of Hawaii). The environment was similar to ours: single frequency, multi-station packet radio transmission. The protocol is crude: You send your signal. If it collides with a competitor, you both try again. There are many problems unsolved by such a simple approach. Even in theory, utilization is never more than 18% of the bandwidth
Slotted ALOHA offers a better performance by establishing a fixed packet size and synchronizing packet transmission. This reduces collisions by eliminating all those in which the second message steps on the tail of the first. The theoretic limit of utilization is 36%. Absolute synchronization is problematic, of course, in any system with latency effects. Our network, although it operates at the speed of light, may be spread across a few hundred km, which would introduce network latencies in the millisecond range across the entire network.
Carrier Sense Multiple Access (CSMA) improves this by listening to see if the channel is free before trying to transmit. This is a great improvement over Aloha systems. Carrier Sense is used to improve the efficiency of many MAC systems. Some wireless hardware provides Carrier Sense. Others only provide Packet Sense (the receipt of a whole verified packet).
CSMA/CD improves the system even more by adding Collision Detection. While the CSMA system can have an entire packet wasted before the contention is discovered, Collision Detection is an immediate reaction. CSMA/CD is the most successful MAC protocol, since it is the basis of Ethernet. Unfortunately, wireless systems usually cannot transmit and receive simultaneously, because the transmitter would blow up the receiver. So CSMA/CD will not be available to us.
Multiplex
There are several MAC strategies that depend upon dividing the single channel into a finite number of smaller channels,
Time Division Multiplex simple chops time into interleaved frames. In a simple implementation, each node will get its own slot (eg: every seventh frame) It is easy to see that this is very wasteful in a system like ours: We have many nodes with different (and changing) bandwidth demands and large propagation latencies.
Frequency Division Multiplex requires greater radio bandwidth to encode more digital bandwidth, and shares it among several nodes.
Code Division Multiple Access uses digital techniques to overlay multiple signals on one another. It is more subtle and flexible than simple Time Multiplexing but it requires complex techniques and very broad radio bandwidth, and probable licensing from the patent holders.
Negotiated Access
Multiple Access Collision Avoidance (MACA) is typical of a family of protocols that use a Request To Send signal initiated by the transmitter, and a Clear To Send from the intended receiver before transmitting the data. Both the RTS and CTS signals contain the length of the upcoming data packet. This tells all competing nodes who hear the CTS to fall silent for the time reserved for the data transmission. MACA was specifically designed for multiple access on a single radio channel, and resolves several of its unique problems. However it is not very efficient when a large number of small messages must be propagated. That may describe our SWARM network pretty well.
MACAW adds even tighter oversight to the control dialog. by requiring a DS signal before and an ACK after the data transmission.
Token Ring Networks pass a token from node to node. Only the node holding the token can transmit a frame. Token rings are efficient, flexible and fair. Standard token strategies are not as efficient in a widespread broadcast environment, and not well suited to a homogeneous network. Token systems tend to be very complex.
Floor Acquisition Multiple Access (FAMA) is a proposed standard that combines the idea of a unique token (the 'floor') with simpler RTS/CTS negotiation. It is was designed in particular to adapt the token concept to the issues inherent in wireless systems.
The Hidden Terminal Problem
In a network of A B C, there may be excellent communication between A and B, and also between B and C,. Yet C and A might be out of range of one another. Carrier Sense will fail to prevent inference at B (and so will A and C's collision detection). Systems with RTS/CTS handshaking will also fail to resolve this hidden terminal problem.
In a system involving planes spread over distances far greater than the range of their radios, robust solution to the hidden terminal problem is essential.
The Exposed Terminal Problem
In a network of A B C D, assume that each station can hear adjacent stations only. (eg A hears B but not C or D )
If C is transmitting a message to D then B will hear it. Most MAC systems will compel B to wait until C is off the air before sending its own message. This is true even if B wishes to send a message to A.
This wastes bandwidth, since A does not hear C's transmission and will receive B's messages uncorrupted. Likewise D's reception of messages from C will not be interfered with by B, who is out of D's radio range.
Solution
The nature of our network topology will suggest a MAC strategy.
Right now we favor a multi-hop, decentralized network whose packets contain routing directions. This seems to mitigate in favor of some specially designed token passing (or floor-ceding) solution. We have a great deal of knowledge about which transmitter is likely to need access to the media soon and can exploit this.
Implementation Potential
Plane A in the hop sequence A-B-C transmits to B, and knows that B needs Media Access in order to propagate the message to C. If A 'has the floor' and can cede it to 'B' we can exploit our knowledge.
Our cascading repeaters have a more complex sequencing and offer even greater wins in a system that propagates channel mastery as well as messages.
It is also possible that a Code division system can be created that affords good efficiency in our highly dispersed network by cleverly matching code division and geographic separation.
Hidden Terminal Opportunity
Our solution must overcome the Hidden Terminal Problem and its potential for collisions. But a big bandwidth win exists if we can exploit the hidden terminal feature, by recognizing that our bandwidth has these spatial components.
Further Work
There are dozens of other MAC protocols (many existing only in PhD dissertations). Consideration of these will undoubtedly be fruitful.
Good MAC choices depend on topology choices, which in turn will depend on the Command and Control structure that we design in the next months.
The MAC question is a very dependent (and minor) detail. We hope to postpone then until Phase II. However the Communications circuitry is being designed right now. Locking in to an inappropriate MAC choice will have devastating bandwidth costs.
We hope to synchronize our efforts with the Communications team in order to avoid bad choices - and to postpone as long as possible any MAC choice.
Related Topics
MAC strategy is highly integrated (or can be) with other networking issues, like routing and topology and with general group control structure,