Multiple Access Links and Protocols
Two types of network links:
Point-to-point link (single wire, e.g. PPP, SLIP)
Broadcast link (shared wire or wireless medium; e.g, Ethernet, Wavelan, etc.)
Copyright By PowCoder代写 加微信 powcoder
humans at a shared wire (e.g., shared RF shared RF cocktail party
cabled Ethernet) (e.g., 802.11 WiFi) (satellite) (shared air, acoustical)
5: DataLink Layer
MAC Protocols
Multiple nodes are connected to a single shared broadcast channel:
two or more simultaneous transmissions by nodes: interference
collision if node receives two or more signals at the same time
Multiple Access Protocol
distributed algorithm that determines how nodes share channel, (i.e., determine when node can transmit)
communication about channel sharing must use channel itself!
no out-of-band channel for coordination
5: DataLink Layer
MAC Protocols: a taxonomy
Three broad classes:
1. Channel Partitioning Protocols
divide channel into smaller pieces (time slots, frequency
bands, multiple access codes)
allocate piece to node for exclusive use
2. Random Access Protocols
Channel not divided, allow collisions recover from collisions
3. Taking turns Protocols
tightly coordinate shared access to avoid collisions
5: DataLink Layer
MAC Protocols: a taxonomy
Three broad classes:
1. Channel Partitioning Protocols
divide channel into smaller pieces (time slots, frequency
bands, multiple access codes)
allocate piece to node for exclusive use
2. Random Access Protocols
Channel not divided, allow collisions recover from collisions
3. Taking turns Protocols
tightly coordinate shared access to avoid collisions
5: DataLink Layer
MAC Protocols: a taxonomy
Three broad classes:
1. Channel Partitioning Protocols
divide channel into smaller pieces (time slots, frequency
bands, multiple access codes)
allocate piece to node for exclusive use
2. Random Access Protocols
Channel not divided, allow collisions recover from collisions
3. Taking turns Protocols
tightly coordinate shared access to avoid collisions
5: DataLink Layer
MAC Protocols: a taxonomy
Three broad classes:
1. Channel Partitioning Protocols
divide channel into smaller pieces (time slots, frequency
bands, multiple access codes)
allocate piece to node for exclusive use
2. Random Access Protocols
Channel not divided, allow collisions recover from collisions
3. Taking turns Protocols
tightly coordinate shared access to avoid collisions
5: DataLink Layer
Random Access protocols
When node has packet to send
transmit at full rate (R) of channel
no a priori coordination among nodes
two or more transmitting nodes -> collision!!,
random access MAC protocol specifies:
how to detect collisions
how to recover from collisions (e.g., via delayed retransmissions)
Examples of random access MAC protocols: slotted ALOHA
CSMA and CSMA/CD
5: DataLink Layer
CSMA (Carrier Sense Multiple Access)
1. Adapter senses if there is no signal energy entering the adapter from the channel.
2. If channel sensed idle: start transmitting frame.
3. If channel sensed busy: defer transmission, wait until no signal energy is present anymore and then start transmitting frame.
4. During transmission, adapter monitors for the presence of signal energy coming from other adapters.
5. If collision is detected, abort transmission of frame. Wait for a random amount of time, then go to Step 2.
6. If no collision was detected during transmission of frame, then done.
human analogy: don’t interrupt others!
5: DataLink Layer
CSMA (Carrier Sense Multiple Access)
If channel sensed idle: transmit entire pkt If channel sensed busy: defer transmission
Persistent CSMA:
• Wait for channel to become idle
with probability p, send packet
Non-persistent CSMA: retry after random time interval
human analogy: don’t interrupt others!
5: DataLink Layer
Non-Persistent CSMA
If channel sensed idle: transmit entire pkt If channel sensed busy: defer transmission
Non-persistent CSMA: retry after random time interval
while N<= max :
listen(channel) if free(channel):
send(frame) wait(ack or timeout)
if received(ack) :
break # transmission was successful
N=N+1 else:
wait(random_time_interval)
# end of while loop
# Too many transmission attempts
5: DataLink Layer
CSMA/CD collision detection
Carrier Sense Multiple Access with Collision Detection
At time t0, node B senses that the channel is idle and begins to transmit.
spatial layout of nodes along ethernet
4 nodes attached to a linear broadcast bus
Note that there is signal propagation delay.
5: DataLink Layer
CSMA/CD collision detection
At time t1, node D is not able to detect that node B is already transmitting; therefore, it begins to transmit as well causing a collision of signals later on.
(The problem is due to propagation delay. B’s transmission signal has
not reached node D yet at time t1.)
5: DataLink Layer
spatial layout of nodes along ethernet
4 nodes attached to a linear broadcast bus
CSMA/CD collision detection
While transmitting, both nodes monitor for the presence of signal energy coming from other adapters using the broadcast channel.
4 nodes attached to a linear broadcast bus
5: DataLink Layer
CSMA/CD collision detection
As soon as node B and node D detects the collision of signals, they abort transmitting.
Here, the damaged frames were not transmitted in their entirety.
4 nodes attached to a linear broadcast bus
The Ethernet standard includes the CSMA/CD protocol, which is particularly effective for a wired broadcast LAN spanning a small geographical region.
5: DataLink Layer
CSMA/CD (Collision Detection)
CSMA/CD: carrier sensing, deferral as in CSMA
collisions detected within short time
colliding transmissions aborted, reducing channel wastage
persistent or non-persistent retransmission collision detection:
easy in wired LANs: measure signal strengths, compare transmitted, received signals
difficult in wireless LANs: receiver is shut off while transmitting
human analogy: the polite conversation
5: DataLink Layer
CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) used in 802.11
1. Adapter senses if there is no signal energy entering the adapter from the channel.
2. If channel sensed idle: wait for a short amount of time, then start transmitting frame. Else if channel sensed busy: defer transmission, then go to Step 3.
3. Wait until no signal energy is present anymore. Increment collision counter. Choose a random backoff time based on collision counter, then countdown to zero (while sensing).
4. When counter reaches zero, transmit frame then wait for ACK.
5. If ACK is received, then done. Otherwise, go to Step 3. 5: DataLink Layer
5: DataLink Layer
“Taking Turns” MAC protocol
Token passing Protocol:
Fair share of bandwidth
control token passed from one node to next in some fixed order.
(nothing to send)
Possession of token allows a node to transmit a max. number of frames
concerns:
token overhead
single point of failure (token holder)
Necessitates a recovery procedure when the token is not released by a node
e.g. FDDI protocol (Fiber Distributed Data Interface), IEEE 802.5 token ring
DataLinkLaye5r:DataLinkLayer 5-20 protocol
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com