1/127
Looks like no tags are added yet.
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.
What is a medium?
A medium is a physical thing that signals must pass through.
What happens to the data your laptop transmits over Wi-Fi?
That data becomes radio waves, in which air is the medium.
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.
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.
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.
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.
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.
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.
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.
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.
What is a broadcast domain?
A broadcast domain is the collection of devices that receive a broadcast frame.
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.
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.
What is a Hub?
A hub is an old networking device that repeats/retransmits everything it receives.
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.
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.
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.
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.
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.
What is a router?
A router is a device that connects devices operating on different networks and forwards packets using IP addresses.
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.
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.
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.
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.
What is the MAC Sublayer?
The MAC Sublayer is the part of the Data Link Layer responsible for controlling access to a shared medium.
What does MAC stand for?
Media Access Control.
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.
So how would you really define what MAC means?
It means the set of rules that determines who gets to transmit when.
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.
What are the 3 types of MAC protocols that exist?
Random Access Protocols
Channelization Protocols
Controlled Access Protocols
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.
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.
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.
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.
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.
What is Contention?
Contention is a fancy word that refers to competition among devices for access to a shared medium.
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.
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.
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.
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
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.
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.
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.
In Pure ALOHA, what happens if two devices transmit simultaneously?
The signals overlap, and this creates a collision.
In Pure ALOHA, how does a device know whether its transmission worked?
Using something called Acknowledgements.
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.
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.
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.
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.
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.
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.
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.
What does a larger K mean?
A larger K means more collisions took place, and therefore, the protocol needs to back off even more.
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.
What is Propagation Delay?
Propagation Delay is how long it takes a signal to physically travel.
Propagation Delay = Distance (m) / Propagation Speed (m/s)
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.
What is the maximum timeout period before the acknowledgement can arrive?
2Tp.
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)
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.
What is the formula for R?
R is {0….2K-1}
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
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.
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.
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.
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.
If Tfr is equal to 1 ms, and the network generates 2 frames every ms, what is G?
G is 2.
What does a larger G imply?
It implies more traffic and more collisions.
What does S represent?
S represents Throughput in Pure ALOHA.
What is the Maximum Throughput for Pure ALOHA?
When G = 0.5, or S = 0.184. This means only 18.4% efficiency.
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.
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.
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.
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.
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 |
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.
What happens to Vulnerable Time in Slotted ALOHA?
Vulnerable Time is cut in half.
Vulnerable Time = Tfr
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.
What is the Throughput Formula for Slotted ALOHA?
S = Ge-G
It has double the throughput of Pure ALOHA.
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.
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.
What does CSMA stand for?
Carrier Sense Multiple Access.
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.
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.
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.
So how has CSMA improved the process compared to Pure ALOHA?
It has improved the process by creating fewer collisions.
What is the Vulnerable Time for CSMA?
Tp (The propagation delay).
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.
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.
What is Persistence?
How aggressively a station tries to transmit.
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.
Why is it called 1-Persistent CSMA?
Because the probability of transmitting is 1, or 100% the moment the channel becomes free.
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.
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.
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.
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.
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.
Which is the best CSMA method?
P-Persistent CSMA, because it results in fewer collisions than 1-Persistent, and better efficiency than non-Persistent.
What does CSMA/CD stand for?
CSMA/CD stands for Carrier Sense Multiple Access with Collision Detection.
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.