Networks Part 4 (Datalink Layer in Broadcast Networks)

Question 1

What are the assumptions of “Multiple Access Protocols”?

Answer 1

1. All hosts can transmit frames on the channel and all can receive from it.
2. Each frame sent is received by all hosts.
3. Hosts have to contend for use of the channel.
4. If two hosts send data simultaneously, the data will be damaged.

And, depending on the system:
5. Hosts may or may not be able to detect when collisions occur.
6. Timing of frame transmissions may be assumed continuous or slotted.
7. A network may have carrier sensing, or not have it.

Question 2

What are examples of contention protocols?

Answer 2

1. ALOHA
2. Carrier Sense Multiple Access

Question 3

What is an example of a collision free protocol?

Answer 3

The bit-map protocol.

Question 4

What are examples of limited-contention protocols?

Answer 4

1. Adaptive Tree Walk protocol.
2. Binary exponential back-off protocol.

Question 5

What is an example of a wireless LAN protocol?

Answer 5

The MACA protocol.

Question 6

What is the Pure ALOHA protocol? How does slotted ALOHA differ?

Answer 6

In pure ALOHA:
1. Hosts transmit whenever they want. Colliding frames are destroyed.
2. If a frame is destroyed, the sender waits a random amount of time and sends its again.
Utilisation of pure ALOHA is bad under high load (around 18%)

Slotted ALOHA splits up the time that transmitters can send data into sections, and each transmitter is assigned to a section. It can only transmit within this section. This doubles the efficiency of ALOHA (up to 37%)

Question 7

What are CSMA protocols?

Answer 7

“Carrier Sense Multiple Access” protocols, where hosts are typically capable of listening for other hosts currently transmitting, and change their behaviour accordingly.

Question 8

What is 1-Persistent CSMA?

Answer 8

When about to send data, host listens to channel.
If channel is busy, keep listening until it is free.
Immediately transmit complete frame.
If frame gets damaged, wait random amount of time, then retransmit whole frame.

Better than ALOHA, but still bad as it causes greedy waiting, which can cause collisions if more than 1 transmitter is waiting.

Question 9

What is Non-Persistent CSMA?

Answer 9

When about to send data, host listens to channel.
If channel is busy, wait for a random amount of time, then listen again.
If not busy, transmit a full frame.

Better than 1-Persistent as there is less data collision under high load, but it comes at the cost of longer delays before sending.

Question 10

What is P-Persistent CSMA?

Answer 10

When about to send data, host listens to channel.
If channel is idle, transmit with probability P.
If did not transmit, after waiting, transmit again with P, repeat ect..
If slot is busy wait a random amount of time then try again.

Similar to Non-Persistent CSMA, but with better performance under high load but more delay.

Question 11

What is CSMA/CD?

Answer 11

A variation on typical CSMAs but with collision detection.

Does not transmit a full frame, but aborts sending a frame if it detects that it has been damaged. It then waits a random amount of time and tries again.

Question 12

What is the Bit-map protocol?

Answer 12

A protocol that is arranged in a way where collisions simply can not occur.

The communication channel is divided up timewise between hosts. This is done by presenting a “contention period” where hosts submit a “1” if they want to host.

After the contention period is finished, the hosts will then submit data in numerical order. This prevents collisions as all hosts transmit at different times.

Under light loads, some transmission capacity is wasted, however is very efficient at high loads.

Question 13

Why might contention be preferable/avoided?

Answer 13

Networks that have low load prefer contention heavy systems as it provides low delay times.

As load increases, contention becomes less attractive, and collision free protocols become better for utilisation.

Limited contention protocols switch between these methods depending on load.

Question 14

What are examples of “limited contention” protocols?

Answer 14

1. Adaptive Tree Walk Protocol
2. Binary Exponential Back-off Protocol (used in classic ethernet)

Question 15

How does the “Adaptive Tree Protocol” work?

Answer 15

1. Hosts are divided up into a binary tree.
2. Hosts attempt to communicate on the top node.
3. If node is conflicted, move back down binary tree.
4. Only nodes stemming off the closest non-conflicting binary node can transmit.

Question 16

How does the “Binary Exponential Back-Off” protocol work?

Answer 16

1. After a collision, time is divided up into discrete slots. Length of slot is equal to longest round trip case possible on the LAN.
2. After the first collision, each host indepedntly waits 2^1 - 1 slots before retry.
3. After second collision, each host randomly picks 2^2 - 1 slots before retry.
4. Continue 2^n -1 trend until 2^10, on which this is the final exponential used.
5. If 16 retries is reached, report failure to the computer and have higher levels handle the failure.

Question 17

What complications do wireless connections introduce?

Answer 17

1. Cannot use the ethernet protocol.
2. Wireless systems cannot detect collisions whilst they are occurring. ACKs need to be used to discover errors.
3. Carrier sensing is useless because of hidden and exposed terminal problems.

Different protocols are needed for wireless networks.