B227 Lecture Overheads - Topic 4: Multiple Access Protocols

The Channel Allocation Problem

The central problem in transmission using broadcasting: how to make use of a single channel when multiple machines wants to use it?

Static allocation:

Using Frequency Division Multiplexing (FDM) or Time Division Multiplexing (TDM) - see topic on Physical Layer.

Allocated a different parts of the channel to different users forever - no possible clashes.

Very inefficient use of the channel, since most users are idle most times.

Dynamic Allocation:

Allocate the channel to different users as they need it.

Some considerations:

Everyone is using the one channel to communicate

If two frames are transmitted at the same time, the resulting signal is garbled

Continuous vs Slotted Time - is time divided into discrete slots, and stations can only transmit in slots?

Carrier Sensing - can the stations sense whether other stations are using the channel?

Multiple Access Protocols

Pure and Slotted Aloha

Carrier Sense Multiple Access (CSMA) Protocols

Collision Free Protocols

Limited Contention Protocols

Wavelength Division Multiple Access (WDMA) Protocols

Wireless LAN Protocols

Pure Aloha

Developed originally at The University of Hawaii (hence the name - "aloha" is "hello" in Hawaiian)

Assume all frames are fixed-length, and are transmitted without being synchronized (ie. not slotted)

The idea: let every station transmit whenever they want.

The sender will detect collisions by detecting their own frames.

Resend if necessary

Slotted Aloha

Time is divided into slots. Each slot is the time taken to transmit one frame.

Frames are transmitted only at the beginning of a slot.

The time when a frame is vulnerable to collisions is halved compared to pure ALOHA.

Figure 4-2 shows the time a frame (the shaded one) is vulnerable to collisions from other frames. That vulnerable time is from t₀ to t₀+2t. If the frames are only allowed to be transmitted in slots (that is, at time t₀, t₀+t and t₀+2t), the only vulnerable time is in the second slot (t₀+t to t₀+2t) which is only half of before (t₀ to t₀+2t).

Figure 4-3 compares the throughput between the two ALOHA schemes. The Y-axis is the average percentage of frames that gets through ungarbled over one slot time interval. The X-axis is the average number of times frame transmissions attempted in one slot over the whole network. The best if when we average one frame per slot. Any less, and we're not making full use of each slot. Any more, and we start getting many collisions.

Carrier Sense Multiple Access (CSMA) Protocols

In CSMA, stations detects the carrier (ie. the medium carrying the transmission, ie. the channel) to see if there it is in a middle of another transmission.

Adjust behaviour accordingly.

1-Persistent CSMA

For unslotted transmissions:

A station detects the channel.

If channel busy, wait until the current transmission is finished.

If channel idle, transmit.

Called 1-persistent because transmission happens with probability 1 if the channel is idle.

Still possible to have collisions if:

Two stations detects the channel idle at the same time and begin, transmitting

One station starts transmitting, but the signal hasn't reached another station yet before it starts to detect the channel.

Non-persistent CSMA

A station detects the channel.

If channel busy, wait for a random interval.

If channel idle, transmit.

The longer wait interval, the less number of collisions.

p-persistent CSMA

For slotted transmissions:

A station detects the channel.

If channel busy, wait for the next slot, and applies the next step.

If channel idle, transmit with probability p - which means wait for the next slot with probability 1-p. At the next slot, repeat this step again.

Figure 4-4 shows the performance of the various CSMA protocols

CSMA with Collision Detection (CSMA/CD)

Abort transmission if collision is detected - as oppose to continue to transmit the whole frame.

Waits for a random interval before retrying.

Applies to unslotted transmissions.

Figure 4-5

In CSMA/CD, there are times called contention periods where stations are transmitting and detecting if there are collisons. If a station transmits and doesn't detect a collision within this contention period, it knows it will be able to transmit the rest of the frame without collision. We consider that the station has seized the channel.

Collision Free Protocols

In CSMA/CD, there are still collisions during contention periods.

In some protocols, we resolve the contention WITHOUT any collisions:

Two example collision-free protocols:

Bit-Map Protocol

Binary Countdown

Bit-Map Protocols

Figure 4-6

In a network of N stations, we create a contention period of N slots.

Each station is allocated statically one of the N slots (note this is ONLY in the contention period). If the station wants to transmit a frame, it will transmit a 1 during it's contention period slot.

At the end of the contention period, all the stations which had transmitted a one during their slot will transmit their frames in order.

All stations knows who is going to transmit, because they all got the bits bits during the contention period, so they can all determine when the next contention period will come up again.

Advantage to be allocated a higher slot in the contention period - less waiting.

Binary Countdown

Like the game spin-the-bottle: at every stage, depending on where the spinning bottle points, some competitors are eliminated.

Every station has a binary address.

We read the addresses of all stations wishing to transmit, one bit at a time.

At every stage, we eliminate most of the contending stations using some rule based on their address bits.

The last remaining station gets to transmit. The others waits for the next contention period and tries again.

Read the textbook p255 for an example. The example uses the binary operation OR, which favours addresses having bits 1.

Limited Contention Protocols

Limited Contention Protocols are combines contention-based protocols with collision free protocols. Due to the lack of time, we won’t go into it in this unit. For those interested, read section 4.2.4 in the textbook.

Wavelength Division Multiple Access (WDMA) Protocols

Used by fiber optic LANs

Uses wave division multiplexing (WDM, discussed in the previous topic) to allocated different parts of the light spectrum (ie. to have different channels) to different stations.

Each station is allocated 2 channels – one for control, one for data

Each station has two transmitters and two receivers:

I receiver for listening on this station’s control channel - this receiver will not need to be tunable (ie. change the range of wavelengths it can receive), since the range of wavelengths for this station’s control channel is fixed.

1 transmitter for sending to another station’s control channel - this transmitter will need to be tunable, since it needs to send to the control channel of ANY of the other stations.

1 transmitter for sending for sending out this station’s data - this transmitter will not need to be tunable, since the range of wavelengths for this station’s data channel is fixed.

I receiver for listening to other station’s data channel - this receiver will need to be tunable, since it needs to send to the data channel of ANY of the other stations.

An example of how to use this, consider we want to send data to station X. So we have one control transmitter, one control receiver, one data transmitter, and one data receiver. Both we and station would already have specific parts of the spectrum’s wavelength allocated to our control channel and data channel.

To establish a connection with station X, we notify X by sending frames to the X’s control channel (ie. we send frames using the wavelength allocated to X’s control – X’s control receiver will ALWAYS be listening on this wavelength range). Station X will now tune its data receiver to our data transmitter’s wavelength. Now when we transmit, X will receive it. The reason we want just send directly without initially notifying X on its control channel is that X’s data receiver could be tuned to one of many stations on the network.

Wireless LAN Protocols

For truly mobile communication (as oppose to just portable, eg. plug laptops to wall sockets using modems), we need to use radio signals.

Some complications:

Not all stations are within range of each other – so, eg. a sending station may not detect interference coming from another station far away, but that interference occurs in receiving stations between them.

In indoor environments, walls can block signals.

Multiple Access with Collision Avoidance (MACA)

Figure 4-12 textbook p265

The idea is to have everyone monitoring the airwaves.

When a sender wishes to send, it will transmit a Request to Send (RTS) frame with the size of the intending data frame in the RTS frame.

The intended receiver will send a Clear to Send (CTS) frame back, again with the size of the intending data frame in the CTS frame

The sender can now begin to send the data frame.

All stations around the sender and receiver will have received the RTS or CTS frame, and therefore will know how long to wait.

Collisions still possible – eg. two stations sending RTS frames at the same time.

MACAW ("MACA for Wireless LANs") improves on MACA by adding acknowledgments, certain properties of CSMA, and the amount of time to wait if receiver is busy.

Digital Cellular Radio

In this unit, we won’t go into the details of these standards, since they are still mainly directed at voice telephony. But keep in mind that with the upcoming convergence of voice and data communications, some of these standards may become very relevant in data communications.

Some competing standards for digital cellular radio:

Global System for Mobile Communications (GSM)

Cellular Digital Packet Data (CDPD)

Time Division Multiple Access (TDMA)

Code Division Multiple Access (CDMA)

Currently ,CDMA is getting more and more popular. It is also used in Satellite transmissions. It is probably the most complicated of the few above to understand, since it is based on Boolean Algebra to construct the code. Qualcomm developed the standard and compares it to several couples in a room all speaking a different language. Only a specific couple can communicate, and each is "tuned in" to only their conversation. In more technical terms, CDMA uses specific codes that convert analog voice sounds into digitized code that is undigitized on the receiving end, whether handset or cell site. All possible signals are added together, and every receiver receives the same final signal. But depending on how they decode it, they will get their relevant original signal.
Also, please note that it is a very common mistake for students to confuse CDMA with CSMA, I guess because the acronym is similar, and they both are LAN technologies. But please don't make this mistake. One is for wire-based LANs like Ethernets and the other is for wireless WANs like satellites systems.

[Back to Lecture Notes page]