Transcript CSMA

Data Link Layer
Useful References
 Wireless Communications and Networks by
William Stallings
 Computer Networks (third edition) by
Andrew Tanenbaum
 Computer Networking (second edition) by
J. Kurose and K. Ross
Network protocol stack
 application: supporting network
applications

FTP, SMTP, STTP
 transport: host-host data transfer
 TCP, UDP
 network: routing of datagrams from
source to destination

IP, routing protocols
 link: data transfer between
neighboring network elements

PPP, Ethernet
 physical: bits “on the wire”
application
transport
network
link
physical
Links
 A communication path consists of a series of
communication links, starting at the source host,
passing through a series of routers and ending at
the destination host.
 How are packets sent across individual links within
the end-to-end communication path?
Multiple Access Links and Protocols
Two types of “links”:
 point-to-point
 PPP for dial-up access
 point-to-point link between Ethernet switch and host
 broadcast (shared wire or medium)
 traditional Ethernet
 802.11 wireless LAN
Multiple Access protocols
 Single shared broadcast channel
 Two or more simultaneous transmissions by nodes:
interference

Only one node can send successfully at a time
A multiple access protocol is characterized as follows:
 Distributed algorithm that determines how nodes
share channel, i.e., determine when node can transmit
 Communication about channel sharing must use channel
itself!
Ideal Multiple Access Protocol
Broadcast channel of rate R bps
1. When one node wants to transmit, it can send at
rate R.
2. When M nodes want to transmit, each can send at
average rate R/M
3. Fully decentralized:


no special node to coordinate transmissions
no synchronization of clocks, slots
4. Simple
MAC Protocols: a taxonomy
Three broad classes:
 Channel Partitioning


Divide channel into smaller “pieces” (time slots,
frequency, code)
Allocate piece to node for exclusive use
 Random Access
 Channel not divided, allow collisions
 “recover” from collisions
 “Taking turns”
 Tightly coordinate shared access to avoid collisions
Channel Partitioning MAC protocols: TDMA
TDMA: Time Division Multiple Access
 Access to channel in "rounds"
 Each station gets fixed length slot (length = pkt
trans time) in each round
 Unused slots go idle
 Example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6
idle
Channel Partitioning MAC protocols: FDMA
FDMA: Frequency Division Multiple Access
 Channel spectrum divided into frequency bands
 Each station assigned fixed frequency band
 Unused transmission time in frequency bands go idle
 Example: 6-station LAN, 1,3,4 have pkt, frequency
frequency bands
bands 2,5,6 idle
Channel Partitioning
CDMA (Code Division Multiple Access)
 Unique “code” assigned to each user; i.e., code set




partitioning
Used mostly in wireless broadcast channels
(cellular, satellite, etc)
all users share same frequency, but each user has
own “chipping” sequence (i.e., code) to encode data
encoded signal = (original data) X (chipping
sequence)
decoding: inner-product of encoded signal and
chipping sequence
CDMA
 Let di be the value of the data bit for the
ith bit slot.
 For mathematical convenience, we
represent a data bit with a o value as –1.
 Each bit slot is further subdivided into M
minislots.
 In this example, M=8 (although usually it is
higher).
CDMA
 The CDMA code used by the sender
consists of a sequence of M values: c1 c2 c3
…cM each taking a +1 or –1 value. In the
example, the CDMA code being used is
(1,1,1,-1,1,-1,-1,-1).
CMDA Encode
 For the mth minislot of the slot
transmitting di, the output of the CDMA
encoder Zi,m, is the value of di multiplied by
the mth bit in the assigned CDMA code, cm:
 Zi,m
= di*cm
CDMA Encode/Decode
CDMA Decode
 The original data bit di is recovered by
computing:

di = (1/M)Zi,m . Cm (m=1…M)
CDMA Encode/Decode
CDMA: Two-Sender
Interference
 The world is far from ideal.
 CDMA must work in the presence of
interfering senders that are encoding and
transmitting their data using a different
assigned code.
 How then does a CDMA receiver recover a
sender’s original data bits when those data
bits are being tangled with bits from other
senders.
CDMA: Two-Sender Interference
CDMA
 Codes must be carefully chosen so that there is
minimal interference.
 Codes must be orthogonal which means that the
inner product of two distinct codes should be 0
 The inner product of a code with itself should be
one.
 The inner product of a code with its complement
should be –1.
CDMA Assumptions
 The codes satisfy the properties mentioned
earlier.
 The receiver knows who the sender is.
 Our discussion made the assumption that the
received signal strengths from various senders at
a receiver are the same; this is difficult to
achieve in practice.
Random Access Protocols
 When node has packet to send
 Transmit at full channel data rate R.
 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
 ALOHA
 CSMA, CSMA/CD, CSMA/CA
CSMA (Carrier Sense Multiple Access)
CSMA: listen before transmit:
 If channel sensed idle: transmit entire frame
 If channel sensed busy, defer transmission
 Human analogy: don’t interrupt others!
CSMA collisions
spatial layout of nodes
Collisions can still occur:
propagation delay means
two nodes may not hear
each other’s transmission
Collision:
entire packet transmission
time wasted
Note:
role of distance & propagation
delay in determining collision
probability
CSMA/CD (Collision Detection)
CSMA/CD: carrier sensing, deferral as in CSMA
Collisions detected within short time
 Colliding transmissions aborted, reducing channel
wastage

 Collision detection:
 Easy in wired LANs: measure signal strengths,
compare transmitted, received signals
 Difficult in wireless LANs; can be costly
 Human analogy: the polite conversationalist
CSMA/CD collision detection
CSMA/CA
 Collision if 2 or more nodes transmit at same time
 CSMA makes sense:
 get all the bandwidth if you’re the only one transmitting
 shouldn’t cause a collision if you sense another transmission
 Collision detection doesn’t work: hidden terminal
problem
Signal Strength
Location
CSMA/CA
CSMA sender
- if sense channel idle for
DIFS sec.
then transmit entire frame
(no collision detection)
-if sense channel busy
then binary backoff
CSMA receiver
- if received OK
return ACK after SIFS
(ACK is needed due to
hidden terminal problem)
Collision Avoidance: RTS-CTS
exchange
 Sender transmits short
RTS (request to send)
packet: indicates
duration of transmission
 Receiver replies with
short CTS (clear to send)
packet

Notifying (possibly hidden)
nodes
 Hidden nodes will not
transmit for specified
duration: NAV
Collision Avoidance: RTS-CTS
exchange
 RTS and CTS short:
Collisions less likely, of
shorter duration
 End result similar to
collision detection

“Taking Turns” MAC protocols
Channel partitioning MAC protocols:
 Share channel efficiently and fairly at high load
 Inefficient at low load: delay in channel access,
1/N bandwidth allocated even if only 1 active
node!
Random access MAC protocols
 Efficient at low load: single node can fully
utilize channel
 High load: collision overhead
“taking turns” protocols
Look for best of both worlds!
“Taking Turns” MAC protocols
Token passing:
Polling:
 Control token passed from
 Master node
one node to next
“invites” slave nodes
sequentially.
to transmit in turn
 Token message
 Concerns:
 Concerns:
 Polling overhead


Latency
Single point of
failure (master)



Token overhead
Latency
Single point of failure (token)
Summary of MAC protocols
 What do you do with a shared media?

Channel Partitioning, by time, frequency or code
• Time Division,Code Division, Frequency Division

Random partitioning (dynamic),
• ALOHA, S-ALOHA, CSMA, CSMA/CD
• carrier sensing: easy in some technologies (wire), hard
in others (wireless)
• CSMA/CD used in Ethernet
• CMSA/CA and CMSA can be used in 802.11 (discussed
later)

Taking Turns
• polling from a central site, token passing