Cyclic Redundancy Check (CRC)
view data bits, d1d2.....dn, as a polynomial:
choose r+1 bit pattern (generator), G (leftmost and
rightmost bits are both 1), viewed again as polynomial
choose r CRC bits, R, such that
for some polynomial H(x). Here, addition of the polynomial
coefficients is modulo 2 arithmetic.
In other words, the polynomial represented by the
concatenation of the data bits and the CRC bits is divisible
DataLink Layer 1
by G(x).
CRC (continued)
Note that, since in modulo 2 arithmetic,
R(x) = -R(x), one can also interpret R(x) as
the remainder when A(x)xr is divided by
G(x).
Error detection: divide the received string
by G(x), and if the remainder is non-zero,
announce an error.
Claim: this CRC can detect burst of errors
as long as the burst is of length r or
shorter.
DataLink Layer 2
1
CRC Example
Addition of 2
polynomials is the
same as mod 2
addition of the
components of
the two vectors
of 0,1’s (i.e. No carryover!
without
carryover)
D.2r
R = remainder[ ]
G
DataLink Layer 3
Link Layer
Introduction and
services
Error detection and
correction
Multiple access
protocols
Link-Layer Addressing
Ethernet
DataLink Layer 4
2
Multiple Access Links and Protocols
Two types of “links”:
point-to-point
point-to-point link between Ethernet switch and
host
shared wire or medium
traditional Ethernet
802.11 wireless LAN
DataLink Layer 5
Multiple Access protocols
single shared 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
DataLink Layer 6
3
Ideal Multiple Access Protocol
Shared 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
DataLink Layer 7
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” (Centralized polling or token-based)
Nodes take turns, but nodes with more to send can take
longer turns
DataLink Layer 8
4
Channel Partitioning MAC protocols: TDMA
TDMA: time division multiple access
access to channel in "rounds"
each node gets fixed length slot (length = pkt
trans time) in each round
unused slots go idle
example: 6-node LAN, 1,3,4 have pkt, slots 2,5,6
idle
DataLink Layer 9
Channel Partitioning MAC protocols: FDMA
FDMA: frequency division multiple access
channel spectrum divided into frequency bands
each node assigned fixed frequency band
unused transmission time in frequency bands go idle
example: 6-node LAN, 1,3,4 have pkt, frequency
bands 2,5,6 idle
time
frequency bands
DataLink Layer 10
5
Example: GSM
Global System for Mobile (GSM): digital
cellular standard developed in Europe.
25MHz band divided in 200 kHz sub-
channels, further divided into time-slots.
125 sub-channels
25 MHz
200 kHz
TS0 TS1 TS2 TS3 TS4 TS5 TS6 TS7
8 users per sub-channel
DataLink Layer 11
Channel Partitioning:Pros and Cons
Pro: no conflict between different nodes.
Con: serious waste of resource when a node
has nothing to transmit.
Good for continuous traffic like voice
Not very efficient for bursty traffic.
DataLink Layer 12
6
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
DataLink Layer 13
Slotted ALOHA
Assumptions Operation
all frames same size when node obtains fresh
time is divided into frame, it transmits in next
equal size slots, time to slot
transmit 1 frame no collision, node can send
nodes start to transmit new frame in next slot
frames only at if collision, node
beginning of slots retransmits frame in each
nodes are synchronized subsequent slot with prob.
if 2 or more nodes
p until success
transmit in slot, all
nodes detect collision
DataLink Layer 14
7
Slotted ALOHA
Pros Cons
single active node can collisions, wasting slots
continuously transmit idle slots
at full rate of channel nodes may be able to
highly decentralized: detect collision in less
only slots in nodes than time to transmit
need to be in sync packet
simple
DataLink Layer 15
Slotted Aloha efficiency
Efficiency is the long-run For max efficiency
fraction of successful slots with N nodes, find p*
when there are many nodes, that maximizes
each with many frames to send Np(1-p)N-1
For many nodes, take
N nodes with many limit of Np*(1-p*)N-1
frames to send, each as N goes to infinity,
transmits in slot with gives 1/e = .37
probability p (new
arrival or re-Tx) At best: channel
prob that node 1 has used for useful
success in a slot transmissions 37%
= p(1-p)N-1 of time!
prob that any node has
a success = Np(1-p)N-1 DataLink Layer 16
