Chapter 9: Media Access Control Protocols

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/127

encourage image

There's no tags or description

Looks like no tags are added yet.

128 Terms

1
New cards

What situation is Media Access Protocols trying to address?

It’s trying to address the situation where you have multiple devices connected to the same local network, and need to figure out how a single one of these devices can send data.

2
New cards

What is a medium?

A medium is a physical thing that signals must pass through.

3
New cards

What happens to the data your laptop transmits over Wi-Fi?

That data becomes radio waves, in which air is the medium.

4
New cards

What does it mean for a medium to be shared?

It means that if you have multiple devices all connected to the same physical medium, each individual device must share that physical medium.

For example: If Device A, Device B, and Device C are all connected to the same Wi-Fi network, each device doesn’t get its own air. They must all share the same air.

5
New cards

What is a broadcast link?

A broadcast link is a shared communication channel connected to multiple devices.

For example: The medium that Devices A, B, and C are conected to.

6
New cards

Why is a Broadcast link called a “Broadcast” link?

Because if one laptop, say Laptop A, transmits some data, that signal physically goes everywhere on the medium. So if Laptop A sends some data, that data is “broadcasted” to all other devices on that medium, meaning Laptop B, Laptop C, and Laptop D hears it.

7
New cards

Does everyone keep the frame, or the data that gets sent from one laptop?

No; Even though all other devices might physically receive the signal, they will discard the frame unless the frame was meant for them.

8
New cards

What happens when two laptops send signals at the exact same time through the exact same shared medium?

For example: Laptop A sends a signal at the same time as Laptop B.

The signals interfere, and this creates a collision.

9
New cards

What is a collision?

A collision is when two or more devices transmit at the same time on a shared medium.

When a collision happens, the receiver doesn’t get any clear data, it just receives a bunch of garbled up corrupted data because the signals overlap.

10
New cards

What is a collision domain?

A collision domain is the set of devices whose transmissions can collide with one another.

For example, if Devices A, B, C, and D, all share the same medium, and any 2 devices can transmit simultaneously, this means that all 4 devices belong to one collision domain.

11
New cards

What is the main problem with collisions occurring?

The problem is that when collisions occur, they waste resources. This is because it leads to delays, creates more congestion, and more retransmissions.

12
New cards

What is a broadcast domain?

A broadcast domain is the collection of devices that receive a broadcast frame.

13
New cards

What is a broadcast frame?

A broadcast frame is data that gets sent to every device operating on the same local network.

It uses a special destination MAC address known as: FF-FF-FF-FF-FF-FF to indicate that the frame is meant for everyone.

14
New cards

What happens when a broadcast frame is sent?

If one laptop sends a broadcast frame, it means that all other laptops or devices operating on that network get a copy.

15
New cards

What is a Hub?

A hub is an old networking device that repeats/retransmits everything it receives.

16
New cards

Let’s say my Laptop sends a frame, and the Hub receives it.

What will the Hub do?

The hub will send it everywhere, to all other connected devices, just by repeating the signal.

17
New cards

What happens to collisions when using a Hub?

For example, if Laptop A and Laptop B both send at the same time on a Hub, what will happen?

A collision will happen, because a Hub doesn’t separate the devices, it just retransmits the signal everywhere. For this reason, we say that a Hub is not a collision domain separator.

18
New cards

What happens to collisions when using a switch?

When a switch is connecting multiple devices together, the switch examines frame destinations and only forwards frames where they’re needed. For this reason, we say that a switch is a collision domain separator. It prevents collisions from ever happening.

19
New cards

How does a switch separate collision domains?

Because each port connected to a switch is a separate communication segment.

For example, Port A is connected to a switch independently of Port B. So now when Laptop A transmits, it doesn’t interfere directly with B or C, because they’re all isolated by the switch.

20
New cards

Why isn’t a switch a Broadcast Domain Separator?

Because if one device sends a Broadcast frame with the destination MAC address FF-FF-FF-FF-FF-FF, which indicates it should be transmitted to everyone, the switch recognizes it as a broadcast and still forwards it to everyone. So the Broadcast Domain still stays intact.

21
New cards

What is a router?

A router is a device that connects devices operating on different networks and forwards packets using IP addresses.

22
New cards

Why is a router a broadcast domain separator?

It is a broadcast domain separator because it stops a broadcast in one network from ever being sent to another adjacent network.

For example, if Network A sends a broadcast to all devices connected within that network, every network on earth should not receive that. So any broadcasts sent in Network A should stay in Network A, and this is done by preventing it from crossing the router.

23
New cards

Why is a router also a Collision Domain Separator?

It is also a Collision Domain Separator because every router interface belongs to a separate network segment.

24
New cards

Categorize Hubs, Switches, and Routers as being either Collision Domain Separators and/or Broadcast Domain Separators:

A Hub is neither a Collision Domain Separator nor a Broadcast Domain Separator.

A Switch is only a Collision Domain Separator.

A Router is both a Collision Domain Separator and a Broadcast Domain Separator.

25
New cards

Let’s say we have Laptop A, Laptop B, Laptop C, and Laptop D all connected to the same Wi-Fi network. Now let’s say Laptop A wants to send information. Who decides whether Laptop A is allowed to transmit right now?

The MAC Sublayer.

26
New cards

What is the MAC Sublayer?

The MAC Sublayer is the part of the Data Link Layer responsible for controlling access to a shared medium.

27
New cards

What does MAC stand for?

Media Access Control.

28
New cards

Why is it called the Media Access Sublayer?

Because Media refers to the shared medium (i.e. air, cable)

Access means permission to use it, and Control means we control/define the rules for who gets to use it.

29
New cards

So how would you really define what MAC means?

It means the set of rules that determines who gets to transmit when.

30
New cards

Why do we need MAC protocols?

We need MAC protocols because without them, anytime a device wants to send something at the same time as another device, all of those devices are allowed to transmit immediately, which results in multiple collisions.

So we need MAC protocols to control who gets access to a medium.

31
New cards

What are the 3 types of MAC protocols that exist?

  1. Random Access Protocols

  2. Channelization Protocols

  3. Controlled Access Protocols


32
New cards

What is a Random Access Protocol?

A protocol in which devices independently decide whether to attempt transmitting.

In a Random Access Protocol, there is no boss or schedule coordinating the devices.

33
New cards

In a Random Access Protocol, does every device have authority over the others?

No, none of the transmitting devices has authority. All devices are equal.

34
New cards

In Random Access Protocol, how does a device decide whether it should send?

For example, if Laptop A has data it wants to send, how does it know when to transmit?

It checks to see if the medium is currently busy or if it is idle. Its decision depends on the state of the medium.

35
New cards

What does it mean for a medium to be “busy” or “idle”?

A busy medium means another device is currently transmitting.

An idle medium means no device is currently transmitting.

36
New cards

Why is it called a Random Access Protocol?

Because the opportunity to transmit naturally arises when devices have data and the medium is available. There is no fixed schedule which says Device A must transmit at X time and Device B must transmit at Y time, etc.

37
New cards

What is Contention?

Contention is a fancy word that refers to competition among devices for access to a shared medium.

38
New cards

Why are Random Access Protocols also called Contention Protocols?

Because devices are competing with each other for access to the medium.

None of the devices are given a turn, none of the devices are guaranteed access, and all of them are trying to gain access to the same shared medium.

39
New cards

What is the biggest drawback of Random Access?

The problem is that two devices might decide that now is a good time to send, so they both transmit simultaneously, resulting in a collision.

For example, both Device A and Device B see that the medium is currently idle, so they both decide to send at the same time, creating a collision.

40
New cards

What happens during a collision?

During a collision, two frames, Frame A and Frame B, are transmitted at the same time, and their signals overlap, which means the receiver will get corrupted data instead of either one of the frames. This means that transmission fails.

41
New cards

What type of rules must a Random Access Protocol define in order to avoid collisions?

The protocol must define rules about:

When devices can send data

What devices should do if the medium is busy

What devices should do if a collision occurs

How a device knows that its transmission actually succeeded and that the frame arrived

42
New cards

What is Pure ALOHA?

Pure ALOHA is a Random Access Protocol in which a device transmits immediately whenever it has a frame to send. It does not check whether someone else is transmitting, and it doesn’t ask for permission or wait for a time slot.

43
New cards

Why is it called Pure “ALOHA”?

It’s called Pure ALOHA because Pure ALOHA was developed at the University of Hawaii to connect computers across the different islands.

44
New cards

Why would anyone design pure ALOHA if it’s so terrible?

Because it was developed in the early 1970s, when networking was still very new, and researchers wanted a simple method of transmitting immediately and dealing with collisions later.

45
New cards

In Pure ALOHA, what happens if two devices transmit simultaneously?

The signals overlap, and this creates a collision.

46
New cards

In Pure ALOHA, how does a device know whether its transmission worked?

Using something called Acknowledgements.

47
New cards

What is an Acknowledgement in Pure ALOHA?

An Acknowledgement (ACK) is a message sent by the receiver to indicate that it received the data correctly.

48
New cards

What happens if an Acknowledgement never arrives in Pure ALOHA?

In Pure ALOHA, the sending device just assumes that either the frame was destroyed or the acknowledgement was destroyed. Either way, it means the transmission failed.

49
New cards

In Pure ALOHA, how long does a device need to wait before deciding the transmission failed?

It waits for a fixed period of time known as the Time-Out Period.

If the Acknowledgement doesn’t arrive within that time period, it means the transmission failed and the device re-transmits. Otherwise, if the Acknowledgement does arrive within that time period, it means the transmission was successful.

50
New cards

Why don’t devices retransmit immediately after a failed transmission?

Because a failed transmission likely means that 2 device transmissions collided. So if both of these devices re-transmit immediately, it means that the devices will collide again, and again, and again.

51
New cards

What is Backoff Time?

Backoff Time is a randomly chosen waiting time a device must wait before retransmitting. We need it to prevent endless collisions.

52
New cards

Why does Backoff Time need to be random?

Backoff Time needs to be random because if both devices waited exactly 1 second after a collision, then they would both retransmit after exactly 1 second, and collide again.

53
New cards

What does the variable K represent?

K represents the number of failed attempts, or in other words, the number of collisions.

For example, one collision would mean K=1.

54
New cards

What does a larger K mean?

A larger K means more collisions took place, and therefore, the protocol needs to back off even more.

55
New cards

What is Kmax?

Kmax represents the maximum number of retransmission attempts allowed.

For example, if Kmax = 16, it means we’ve already failed 16 times, so the protocol just gives up.

56
New cards

What is Propagation Delay?

Propagation Delay is how long it takes a signal to physically travel.

Propagation Delay = Distance (m) / Propagation Speed (m/s)

57
New cards

Why does Propagation Delay even matter?

How long does it take for a full round trip?

Propagation Delay matters because acknowledgements need to travel back.

So if it takes Tp time for the acknowledgement to get from the sender to the receiver, then the time it takes for the acknowledgement to get from the receiver to the sender is also Tp.

Therefore, a full round trip would take 2Tp.

58
New cards

What is the maximum timeout period before the acknowledgement can arrive?

2Tp.

59
New cards

What is Frame Transmission Time?

The time required to place all bits of a frame onto a medium.

Tfr = Frame Size (bits) / Transmission Rate (bps)

60
New cards

What is R?

R is a random integer chosen after a collision.

It dictates what the random waiting time/backoff time of a device should be after a failed transmission.

61
New cards

What is the formula for R?

R is {0….2K-1}

62
New cards

The stations on a wireless ALOHA network are a maximum of 600 km apart. If we assume that signals propagate at c = 3 × 108 m/s, what is the value of TP? If K = 2, what is the value of TB?

Maximum of 600 km apart

Propagation Speed = 3 × 108

Tp = ?

Tb = ?

Convert km to m

600 km x 10³ m / 1km = 600,000 m

Calculate Tp

600,000 m / 3 × 108 m/s = 2 ms

Calculate R

R = 22 -1 = 3

Calculate Tb

Tb = R x Tp

= 3 × 2 = 6 ms

This means that Tb can be any value from {0,2,4,6} ms

Tp is 2 ms

63
New cards

What is Vulnerable Time?

Vulnerable Time is the period during which another transmission could cause a collision.

AKA, it is the time window in which a frame is in danger.

64
New cards

A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the requirement to make this frame collision-free?

Find Vulnerable Time

Vulnerable Time = 2 x Tfr = 2 × 1 ms = 2ms


Find Frame Transmission Time

Tfr = frame size / transmission rate = 200 / 200 × 10³ = 0.001 s or 1 ms


Convert kbps to bps

200 kbps x 10³ / 1 kbps = 200 × 10³ bps


This means that to avoid collisions, no station should start transmitting 1 ms before or 1 ms after the start of your transmission. Otherwise a collision can occur.

65
New cards

What does Throughput mean in Pure ALOHA?

It means the number of frames that successfully survive collisions.

For example, if you transmit 1000 frames, not all 1000 will reach their destination. Some will collide. Throughput only measures the surviving frames.

66
New cards

What is G?

G represents the average number of frames generated during one frame transmission time in Pure ALOHA.

For example, if Tfr = 1ms, that means a frame takes 1ms to transmit. If we count the number of frames the network generates during that 1ms, the count is G.

So G = 1.

67
New cards

If Tfr is equal to 1 ms, and the network generates 2 frames every ms, what is G?

G is 2.

68
New cards

What does a larger G imply?

It implies more traffic and more collisions.

69
New cards

What does S represent?

S represents Throughput in Pure ALOHA.

70
New cards

What is the Maximum Throughput for Pure ALOHA?

When G = 0.5, or S = 0.184. This means only 18.4% efficiency.

71
New cards

A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. Compute is the throughput if the system (all stations together) produces 1000 frames per second? Explain the result

Frame Size = 200 bits

Transmission Rate = 200 Kbps

1000 frames/s produced

Throughput (S) = ?

Recall: S = Ge-2G and G = # of frames generated in one Tfr

Find Frame Transmission Time

Tfr = frame size / transmission rate = 200 bits / 200 × 10³ bps = 1 × 10-3 s

Convert kbps to bps

200 kbps x 10³ / 1 kbps = 200 × 10³ bps

Find the number of Frames generated per Tfr

1000 frames / 1 second x 1×10-3s / 1 frame = 1 frame / 1 × 10-3 s

Solve for Throughput

S = 1 x e-2×1 = 0.13533 = 13.5% efficiency.

This means that only: 0.1353 × 1000 = 135 out of 1000 frames did not arrive damaged as a result of collisions.

72
New cards

Since Pure ALOHA’s maximum efficiency rate, even under ideal conditions, is only 18.4%, what method do we use instead of Pure ALOHA?

Slotted ALOHA.

73
New cards

Why did engineers create Slotted ALOHA?

Because Pure ALOHA was extremely inefficient, stations could transmit whenever they felt like it, which created a ton of collisions and wasted resources.

74
New cards

What is Slotted ALOHA?

Slotted ALOHA is a Random Access Protocol where we divide time into slots, and only allow devices to transmit at the beginning of a slot.

75
New cards

What is a Time Slot in Slotted ALOHA?

A time slot is a block of time whose length equals Tfr.

For example, if Tfr = 1 ms, then:

Slot 1: 0-1 ms

Slot 2: 1-2 ms

Slot 3: 2-3 ms

And a station can only begin transmitting at the beginning of a slot:

| Slot | Slot | Slot |

76
New cards

Can collisions still happen in Slotted ALOHA?

Yes, because 2 devices can choose the same slot and transmit simultaneously, creating a collision.

For example, Device A might choose Slot 1, and Device B might also choose Slot 1. If they both start transmitting simultaneously, this would result in a collision.

77
New cards

What happens to Vulnerable Time in Slotted ALOHA?

Vulnerable Time is cut in half.

Vulnerable Time = Tfr

78
New cards

Why is it important that the Vulnerable Time is smaller?

It’s important because it means fewer chances for collision, and therefore, a higher throughput.

79
New cards

What is the Throughput Formula for Slotted ALOHA?

S = Ge-G

It has double the throughput of Pure ALOHA.

80
New cards

What is the maximum throughput of Slotted ALOHA?

G = 1 and S = 0.368 (36.8% efficiency).

This is because the throughput has been doubled compared to Pure ALOHA.

81
New cards

A slotted ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the throughput if the system (all stations together) produces 1000 frames per second? Explain your result.

Frame Size = 200 bits

Transmission Rate = 200 kbps

Produces 1000 frames/second

Throughput (S) = ?

Solve for G

G = 1000 frames / 1 second x 1×10-3 s / 1 frame = 1 frame per Tfr

Solve for Frame Transmission Time

Tfr = frame size / transmission rate = 200 / 200 × 103 = 1 × 10-3 s

Convert to bps

200 kbps x 103 bps / 1 kbps = 200 × 103 bps

Find Throughput

S = Ge-G = 1e-1 = 0.3678 = 36.79%

This means that 0.3678 × 1000 = 368 out of 1000 frames survived the collisions.

82
New cards

What does CSMA stand for?

Carrier Sense Multiple Access.

83
New cards

What does Carrier Sense Multiple Access actually mean?

Multiple Access means multiple stations share a single medium.

Carrier Sense means a station senses if the medium is busy or not prior to transmission.

84
New cards

Why does listening first in CSMA actually help?

Because if a device listens before transmitting, it can determine if the medium is busy or not.

If the medium is busy, it will avoid transmitting, which prevents collisions.

85
New cards

Why can collisions still happen in CSMA?

Collisions can still happen because of propagation delay.

For example, if one device starts transmitting, other devices may not know that Device A has started transmitting, because signals take time to travel. As a result, if another device listens, it won’t hear anything, because the signal hasn’t reached the other device yet. So this creates a collision.

86
New cards

So how has CSMA improved the process compared to Pure ALOHA?

It has improved the process by creating fewer collisions.

87
New cards

What is the Vulnerable Time for CSMA?

Tp (The propagation delay).

88
New cards

Why is the Vulnerable Time for CSMA just Tp, the Propagation Delay?

Because now that stations are listening, there are no more collisions as a result of two devices transmitting when the medium is busy. Now the only thing causing collisions is the propagation delay, because the time required for the signal to reach the most distant station is Tp, and this is the only thing that determines whether or not the medium was heard as busy.

89
New cards

Are there multiple CSMA methods? Why? What do all of the methods have in common?

Yes there are multiple CSMA methods. But all CSMA methods agree on listening first to see if the medium is busy. The only difference between the CSMA methods is what happens after you’ve listened to the medium.

90
New cards

What is Persistence?

How aggressively a station tries to transmit.

91
New cards

What is 1-Persistence CSMA?

The most aggressive CSMA version. If the medium is busy, it keeps listening continuously, and the moment it becomes idle, it transmits immediately.

92
New cards

Why is it called 1-Persistent CSMA?

Because the probability of transmitting is 1, or 100% the moment the channel becomes free.

93
New cards

What is the downside of 1-Persistent CSMA?

If all 3 devices are waiting, listening, then suddenly, the channel becomes idle, all of the devices transmit immediately. This results in a collision.

94
New cards

What is non-persistent CSMA?

Non-Persistent CSMA is the less aggressive version of CSMA. Here, if the channel is busy, it waits a random amount of time, then listens again.

95
New cards

Why does non-persistent CSMA reduce Collisions?

It reduces collisions because now if two devices are waiting, they each wait a random amount of time before checking the medium again, and then transmit.

For example, Device A might wait 5 ms and Device B might wait 11 ms. Now there are fewer collisions.

96
New cards

What is the downside of non-persistent CSMA?

The fact that the channel can become free while the stations are waiting out their random delays.

As a result, nobody transmits, even though transmission could have occurred, which wastes bandwidth. So while there are fewer collisions, there is also less efficiency.

97
New cards

What is P-Persistent CSMA?

It is a type of CSMA that says when a channel becomes idle, a device should transmit with a probability P, and should not transmit with a probability 1-P, just wait for the next slot.

For example, a station might have only a 50% chance of transmitting when the medium becomes free.

98
New cards

Which is the best CSMA method?

P-Persistent CSMA, because it results in fewer collisions than 1-Persistent, and better efficiency than non-Persistent.

99
New cards

What does CSMA/CD stand for?

CSMA/CD stands for Carrier Sense Multiple Access with Collision Detection.

100
New cards

How is CSMA/CD different from regular CSMA?

It’s different because it continues listening to the medium and monitoring the medium after it transmits to check for collisions.

For example, once a station transmits a frame, it continues monitoring the medium to see if anyone else transmitted.