Medium Access Control Protocols

IntroductionA medieval General is using messengers to communicate with his regiments, but he finds that using people to send messages is slow. After thinking, he realizes he could use drums for communication. Every regiment learns their distinct drum patterns to send reports and listen for commands. But in practice, the General finds that two regiments will often start drumming over each other and he is unable to decipher the message. This is because the regiments might start drumming at the same time, or one regiment won’t hear that the other is already drumming when they start. The potential for overlapping signals means the General won’t always understand the message, and the regiments can’t know if the General heard their message. How can the General prevent such costly communication failures?Solutions to this type of problem are known as Medium Access Control (MAC) protocols, and are critical to the function of all modern digital communications. Instead of drums, we use radio waves, but the idea is the same. Our WiFi, cellular, and Bluetooth devices must all solve this problem. Because they operate under different constraints, they each solve it in a slightly different way.Before we look at modern communications, let us travel back to 1969 to the islands of Hawai’i and discover how the first wireless computer network solved this issue.ALOHAOn the island of Oʻahu, the main campus of the University of Hawai’i hosted a powerful IBM computer. Nearby community colleges wanted to connect to this powerful computer, but unfortunately these colleges sat on separate islands. Laying down a cable to create a point-to-point network, like the experimental ARPAnet of the time, would have been expensive. So, they decided to use this as the perfect excuse to research implementing a wireless computer network.Thus was born the ALOHAnet.The goal was fairly simple: enable all the islands to communicate with the IBM machine at the same time. This meant a radio on every island, each trying to communicate with the base station.One big issue presented itself: If two islands tried to communicate with the base station at the same time, their radio signals would overlap and become indecipherable, exactly the issue our General struggled with when listening to multiple regiments at once.This is where we introduce the first MAC protocol, today known as Pure ALOHA.Take a moment to try and solve the problem yourself. How could the regiments minimize collisions, or at least make sure their message was heard by the General?

Later we will see how WiFi solves this issue using a single communication channel, but ALOHA had it easier since it used two frequencies for its protocol. In our army metaphor this can be represented as being able to use both drums and horns, where different instruments can each communicate without interfering with the other instruments.Below is the description for Pure ALOHA, the first-ever, random-access MAC protocol for a wireless computer network.Pure ALOHAWhen you have a message to send, immediately send it. This may collide with someone else, so you need to get back an acknowledgement from the base station (the General) confirming they got your message. We might worry that the acknowledgement message could collide with another message being sent at the same time, but ALOHA uses two frequencies: one for sending messages to the base station, and the other for sending messages from the base station, so the base station’s acknowledgment will not collide with incoming messages. This also means that when the base station sends you information, it doesn’t need an acknowledgement back.If you don’t get back the acknowledgment (called an ACK) in a short timeframe, try sending the message again. But we need to be careful here. Imagine everyone immediately tries to resend their messages after they fail; what would happen? Two users who just interfered with each other would immediately resend and interfere again! And this would repeat forever. To solve this, you need to wait a random amount of time before resending the message. Eventually, by chance, messages will stop colliding (as long as there aren’t too many stations). In the original paper the authors sample their random delay from an exponential distribution, but later we will see how this can be improved.Below is a simulation of Pure ALOHA with three stations talking to a base station. Stations will begin a backoff immediately after sending a message, with a minimum delay to allow for an ACK to be sent back, in which case they cancel their backoff.We denote a message being sent from a station as a colored bar with full height, and a message being heard as a bar at half height. A message is not actually received unless the entire message is heard without interference, so we mark messages as striped until the entire message is correctly received.

Messages are sometimes heard by all stations (such as the ACK from the base station), but they are intended for only one station (whose name is in the message), so we color the message darker for the intended station and semi-transparent for other stations.Code for the animation is here.We see when a station sends a message, the base station decodes it, then sends back an ACK. When two stations send messages that overlap, the base station is unable to read either (think the General hearing two drums at the same time) and the ACK is not sent back. When we see all the stations try to send a message at around the same time, notice it is harder for each message to be lucky enough to finish before another starts. We also see at one point an overlap between the ACK and the message from station C, but nothing interferes. This is because the stations are sending on a different frequency than the base station, so messages between the two do not interfere.The protocol worked! Although, it’s not very efficient. You can look at the original paper to see that they calculate the efficiency of this algorithm to be 18.4% of the theoretical optimal throughput (the paper has a typo of 18.6%). They also calculate that the network can only handle up to 324 users, after which, there is so much interference that not a single message can make it to the base station. But typical traffic for ALOHA was small enough that this protocol was sufficient.This was followed by many improvements, such as using slotted ALOHA, which increased the throughput to 36.8% efficiency by using time slots. And these improvements only continued. But more interesting was the development that ALOHA inspired in other mediums.EthernetImmediately after the success of ALOHAnet, it was recognized that a similar protocol could be created for wired networks. In fact, this similar protocol would be adaptable to any medium that can carry a signal. This new protocol was called Ethernet, inspired by the historical concept of the luminiferous ether. This protocol would allow any number of computers to talk to each other over any medium, such as through air, water, or a wire.Typically, Ethernet uses a single wire that every computer connects over, and every node is treated equal.

Lack of a leader makes coordinating devices much harder, but a single wire makes it easier for nodes to monitor what is happening on the network. This physical medium was novel compared to what previous networks had been built for. To compare: ARPAnet, the precursor to the internet, used a directional wired point-to-point connection between each device, so messages never interfered, but messages had to be routed through a complex network of devices. ALOHAnet used a wireless connection to a central base station, which meant nodes could be coordinated by a central coordinator, but they couldn’t tell what other nodes were hearing. Because of all these differences, Ethernet was able to utilize new methods compared to these previous networks.Here’s how you would set up an Ethernet network: Lay a cable around the room, then clamp each computer onto the cable. That’s it; you now have a functioning network. Unfortunately, we must again solve the issue of coordinating all the computers so they don’t talk over each other.Computers on the wire can listen to the wire at the same time as they transmit over it. This is quite powerful. Before, in the wired setting, the transmitter had to be as loud as possible to reach the far-away radio, meaning, if a radio tried to listen while it transmitted, all it would hear was its own transmission. Imagine in our drummer analogy, the drummers need to be as loud as possible to be heard, but that means they can’t hear other drums. But on a wire, this problem doesn’t exist. It takes almost no power to transmit a signal to everyone else, so a computer doesn’t drown out its own receiver. And since we know everyone is listening on the same wire, we know that everyone will hear the same thing (save for a very small propagation delay). These two useful facts allow us to build a much more powerful MAC protocol.Ethernet ProtocolBecause we know everyone is hearing the same thing, we can wait until the wire is quiet before we talk (this wouldn’t be as useful in ALOHAnet since we don’t know what the base station is hearing). This listening before transmitting is known as Carrier Sense Multiple Access (CSMA) and reduces the likelihood of collisions in Ethernet. It does not eliminate them though.Just like ALOHAnet, users need to wait a random amount of time after the wire becomes free in order to avoid all talking at once.

Sampling that delay from an exponential distribution, as ALOHAnet did, would be sub-optimal. Imagine we had a million computers on the network; the likelihood that at least two computers would pick roughly the same delay would be extremely high and the collisions may never end. Ideally, we scale our delay by the size of the network. We could develop a complicated protocol to track the number of computers on the network to do this, but there is a more elegant solution.Ethernet developed exponential random backoff where, instead of sampling from a static distribution, it samples from a uniform interval that doubles each time a collision occurs, and then resets after a successful send. This scales the backoff interval to the size of the network dynamically, adapting to computers being added or removed from the network. Be careful to watch out for the channel capture effect, where one node with a large backoff gets starved out of access to the wire by other nodes with small backoffs.Ethernet’s final improvement was to detect collisions immediately. If we listen to the wire while we are transmitting, we can compare what we are sending to what we are hearing. If they are different, then we immediately know a collision just occurred. This is necessary since there isn’t a base station anymore to tell us if a collision occurred. With the ability for immediate detection, the protocol is amended to be called Carrier-sense Multiple Access with Collision Detection (CSMA/CD).The Ethernet cable has a small delay, so it would be possible for a node to transmit a short message and not hear that a collision occurred until after it finished transmitting, which would not be caught by CSMA/CD. So, Ethernet requires that a message must be broadcast for at least as long as a message takes to make a round-trip along the wire. This message size is typically called the Minimum Ethernet Frame Size.Here we see a simulation of Ethernet with three computers. We exaggerate the delay of the signal traveling over the wire. When two computers try to send at around the same time, they will detect that the signal on the wire is not what they are expecting and start a random backoff. We increase the range of the random backoff each time a message fails to send.Code for the animation is here.Notice that there are no ACKs, just messages. We also see how nodes immediately handle collisions rather than waiting to see if their messages were received correctly.