Medium Access Control (MAC) Protocols
Textbook: Ch.12
We are still in Data Link Layer . . .
SEHH2238 Computer Networking
Copyright By PowCoder代写 加微信 powcoder
SEHH2238 Lecture 5 1
12.1 Random Access
SEHH2238 Computer Networking
Main Topics
ALOHA Protocol
Pure ALOHA and Slotted ALOHA
CSMA – Carrier Sense Multiple Access
Non-persistent CSMA
1-persistent CSMA
Collision Detection Procedure
Collision Detection Timing
SEHH2238 Lecture 5 2
SEHH2238 Computer Networking
Local Area Network (LAN)
A network used to interconnect distributed computers located within a single building or localized group of buildings in a limited geographic area
Wired LAN & wireless LAN
Classified by
Topology
Transmission media
Multiple Access Control (MAC) protocols
SEHH2238 Lecture 5 3
SEHH2238 Computer Networking
Multiple Access Control Protocols
The protocols used to determine who can transmit next on a multiaccess channel (i.e. the network is in a bus topology, usually also a broadcast channels)
Also called media access control protocols
A protocol must be used to ensure that the transmission medium is accessed and used in a fair way
SEHH2238 Lecture 5 4
SEHH2238 Computer Networking
Multiple Access Protocols
SEHH2238 Lecture 5 5
SEHH2238 Computer Networking
RANDOM ACCESS
In random-access or contention no station is superior to another station and none is assigned control over another.
At each instance, a station that has data to send uses a procedure defined by the protocol to make a decision on whether or not to send.
This decision depends on the state of the medium (idle or busy).
SEHH2238 Computer Networking
Evolution of random access protocols
If two or more stations send at the same time, there is a collision in the common channel and all the data frames will be destroyed (since the network is a bus topology)
SEHH2238 Lecture 5 7
SEHH2238 Computer Networking
ALOHA Network
A wireless radio network in a bus topology, developed by University of Hawaii,
ALOHA is the earliest random access protocol (in early 1970)
SEHH2238 Lecture 5 8
SEHH2238 Computer Networking
Pure ALOHA
(Random Access Protocol)
It can be used on any shared medium
The network is in a bus topology
Each station makes its own decision
Transmit whenever the data is ready
If collided, retry (re-transmit) after a random delay (called back-off time)
The collision is known by ACK operation; if no ACK receives, then assume collision
SEHH2238 Lecture 5 9
SEHH2238 Computer Networking
What will happen? Collision
Frames in a pure ALOHA network
Pure ALOHA
Idea: Each station sends a frame whenever it has a frame to send.
SEHH2238 Lecture 5 10
SEHH2238 Computer Networking
Procedure for ALOHA protocol
SEHH2238 Lecture 5 11
SEHH2238 Computer Networking
Figure 12.3: Procedure for pure ALOHA protocol
SEHH2238 Computer Networking
Example 12. 1
The stations on a wireless ALOHA network are a maximum of 600 km apart.
If we assume that signals propagate at 3 × 108 m/s,
wefindTp =(600×103)/(3×108)=2ms.
For K=2,therangeofRis{0,1,2,3}.
ThismeansthatTB canbe0,2,4,or6ms,basedonthe
outcome of the random variable R. 600 km
SEHH2238 Lecture 5
SEHH2238 Computer Networking
Figure 12.4 Vulnerable time for pure ALOHA protocol The length of time in which collisions may occur
Tfr – frame size in seconds
SEHH2238 Lecture 5 14
SEHH2238 Computer Networking
Example 12.2
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?
Average frame transmission time Tfr is 200 bits/200 kbps or 1 ms. The vulnerable time is 2 × 1 ms = 2 ms. This means no station should send later than 1 ms before this station starts transmission and no station should start sending during the period (1 ms) that this station is sending.
SEHH2238 Lecture 5
SEHH2238 Computer Networking
Throughput
Throughput is the portion of data frames reaching the destination successfully
In pure Aloha, the maximum throughput is only 0.18 Proof (optional, could be skipped):
It is known that the average number of successful transmission for pure Aloha is
S = G x e-2G
where G is the average number of frames generated by the system in one frame transmission time (may be collided)
by differentiation, we can find that Smax occurs at G =1/2 and the corresponding Smax is 0.18
SEHH2238 Lecture 5 16
SEHH2238 Computer Networking
Example 12. 3
A pure ALOHA network transmits 200-bit frames on a shared channel of 200 kbps. What is the throughput if the system (all stations together) produces
a. 1000 frames per second? b. 500 frames per second? c. 250 frames per second?
The frame transmission time is 200/200 kbps or 1 ms.
a. If the system creates 1000 frames per second, or 1 frame
per millisecond, then G = 1. In this case S = G × e−2G = 0.135 (13.5 percent). This means that the throughput is 1000 × 0.135 = 135 frames. Only 135 frames out of 1000
will probably survive.SEHH2238 Lecture 5
SEHH2238 Computer Networking
Example 12. 3 (continued)
b. If the system creates 500 frames per second, or 1/2 frames per millisecond, then G = 1/2. In this case S = G × e−2G = 0.184 (18.4 percent). This means that the throughput is 500 × 0.184 = 92 and that only 92 frames out of 500 will
probably survive. Note that this is the maximum throughput case, percentage-wise.
c. If the system creates 250 frames per second, or 1/4 frames per millisecond, then G = 1/4. In this case S =
G × e−2G = 0.152 (15.2 percent). This means that the throughput is 250 × 0.152 = 38. Only 38 frames out of 250 will probably survive
SEHH2238 Lecture 5
SEHH2238 Computer Networking
Slotted ALOHA
Adopt the same fixed packet length (data frame length) for all stations
Divide time into discrete intervals (slots) of duration equals to the packet length (in terms of transmission time)
All stations follow the same synchronized time system
Transmit only at the beginning of the next time slot
If collided, retry after a random delay
Maximum throughput is doubled to 0.36
SEHH2238 Lecture 5 19
SEHH2238 Computer Networking
Figure 12.5 Frames in a slotted ALOHA network
SEHH2238 Lecture 5 20
SEHH2238 Computer Networking
Figure12.6 VulnerabletimeforslottedALOHAprotocol
SEHH2238 Lecture 5 21
SEHH2238 Computer Networking
12.1.2 Carrier Sense Multiple Access (CSMA) Allow variable packet length
Listen to the channel (sense the carrier) before transmission
If the channel is idle then transmit otherwise
non-persistent CSMA
– (if channel is busy) retry after a random delay
1-persistent CSMA
– (if channel is busy) wait until the channel becomes idle and then transmit
If collided, retry after a random delay
SEHH2238 Lecture 5 22
SEHH2238 Computer Networking
Collision in CSMA
(The collision is known by receiving and checking the ACK)
The network should be a bus topology
SEHH2238 Lecture 5 23
SEHH2238 Computer Networking
Figure 12.8 Vulnerable time in CSMA
The network should be a bus topology
SEHH2238 Lecture 5 24
between the farthest stations
SEHH2238 Computer Networking
Persistence Methods
Persistence method defines the procedure for a station that senses a busy medium
non-persistent CSMA 1-persistent CSMA p-persistent CSMA (skip)
SEHH2238 Lecture 5 25
SEHH2238 Computer Networking
Figure 12.9 Behavior of persistence methods
SEHH2238 Lecture 5 26
SEHH2238 Computer Networking
Figure 12.10: Flow diagram for persistence methods
SEHH2238 Computer Networking
Non-persistent CSMA
A station senses the channel when it has a frame ready to send
If the channel is idle, the station sends the frame immediately
If the channel is busy, it waits a random period of time and senses the channel again (and repeat the process)
If collided, retry after a random delay
SEHH2238 Lecture 5 28
SEHH2238 Computer Networking
1-Persistent CSMA
A station senses the channel when it has a frame ready to send
If the channel is busy, the station senses the channel again and again until the channel becomes idle
When the channel is idle, the station sends the frame immediately
If collided, retry after a random delay
SEHH2238 Lecture 5 29
SEHH2238 Computer Networking
CSMA/CD Protocol
Carrier Sense Multiple Access with
Collision Detection
Listen before & while transmission
Before transmission, the source station
first listen to the channel
If the channel is idle, transmit
If collided, retry after a random delay What is more …
SEHH2238 Lecture 5 30
SEHH2238 Computer Networking
Collision Detection in CSMA/CD
It is possible that 2 stations detect the channel idle at the same time and start transmission simultaneously and hence data collided
To check whether collision occurs, the station simultaneously monitors the data signal actually present on the channel when transmitting a frame
If transmitted & monitored signals are different then collision detected (CD). The station then stops transmitting the current frame immediately
SEHH2238 Lecture 5 31
SEHH2238 Computer Networking
Collision Detection
Figure 12.11 Collision of the first bit in CSMA/CD
The network should be a bus topology
SEHH2238 Lecture 5 32
SEHH2238 Computer Networking
Collision Detection
Figure 12.12 Collision and abortion in CSMA/CD
The network should be a
bus topology
SEHH2238 Lecture 5 33
SEHH2238 Computer Networking
CSMA/CD (Cont.)
To tell other stations that collision has occurred, the station continues to send a random bit pattern (known as jam sequence/signal) for a short period of time before stopping transmission
The stations involved then wait for a random delay (the back-off time) before trying to retransmit the affected frames (i.e. those collided)
For 1-persistent method the max throughput of using CSMA/CD is around 0.5
For non-persistent method, the max throughput of CSMA/CD can go up to 0.9
SEHH2238 Lecture 5 34
SEHH2238 Computer Networking
CSMA/CD procedure -Summary
SEHH2238 Lecture 5 35
SEHH2238 Computer Networking
Fig12.13 Flow diagram for the CSMA/CD
SEHH2238 Lecture 5 36
SEHH2238 Computer Networking
Figure 12.14 Energy level
during transmission, idleness, or collision
A station can also monitor the energy level to determine the channel is idle, busy, or in collision
SEHH2238 Lecture 5 37
SEHH2238 Computer Networking
Time for detecting collision
Tp is the time for a signal to propagate between the farthest stations
In the worst case a station cannot be sure that it has seized the channel until it has transmitted for 2Tp without hearing a collision
Therefore the longest time to detect collision is the maximum round trip delay = 2Tp
2Tp is also the minimum frame size (transmission time) required for proper operation of CSMA/CD
SEHH2238 Lecture 5 38
SEHH2238 Computer Networking
Example 12.5
A network using CSMA/CD has a bandwidth of 10 Mbps. If the maximum propagation time (including the delays in the devices and ignoring the time needed to send a jamming signal) is 25.6 μs, what is the minimum size of the frame?
•The frame transmission time is Tfr = 2 × Tp = 51.2 μs.
• This means, in the worst case, a station needs to transmit for a period of 51.2 μs to detect the collision.
• The minimum size of the frame is 10 Mbps × 51.2 μs = 512 bits or 64 bytes.
•This is actually the minimum size of the frame for Standard Ethernet.
SEHH2238 Lecture 5 39
SEHH2238 Computer Networking
Back-off Time (optional, skip)
How much is enough?
Simplest: just double the back-off time if collide again Exponential back-off
In Kth attempt,
the station waits a random amount of time between:
0to(2K -1)xTfr
where Tfr is the average frame transmission time Back-off Limit
If the number of retry exceeds the pre-set limit in back-off (usually 15), the station has tired enough and abort the procedure
SEHH2238 Lecture 5 40
MAC protocols to be use in a bus channel
SEHH2238 Computer Networking
Pure ALOHA – max throughput 0.18 Slotted ALOHA – max throughput 0.36 CSMA – Carrier Sense Multiple Access
Listen before transmission
1-persisten CSMA/CD – max throughput ≈ 0.5
All – If collided, retry after a random delay
Revision Quiz
http://highered.mheducation.com/sites/0073376221/stu dent_view0/chapter12/quizzes.html
SEHH2238 Lecture 5 41
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com