ECE534/634 Communication Networks
CSC424 Computer Networks
Link Layer
(Framing, Error coding)
1
Previously …
• A Simple Model of “Link”
– Rate, propagation delay
– Message latency, BD product
• Signals over wireless
• Fundamental limits
– Nyquist limit
– Shannon capacity
2
Transmission Parameters
• The bandwidth (B): width of the non-zeros
frequency range of the signal
– Limits the rate of transitions
• Signal strength (S), Noise strength (N) (at the
receiver)
– Limits how many signal levels we can distinguish
– Unit: dBm – power relative to 1 milliwatt
• Defined as 10 * log10 (P/1 mW)
3
Nyquist Limit
• The maximum symbol rate is 2B (Hz) in a
noiseless channel of bandwidth B (Hz)
– Example: Assume binary amplitude encoding, a
3000 Hz channel can transmit data at a rate of at
most 6000 symbols/second R = 6000 bits/second
0 0 1 1 1 1 0 1 0 1 0 0 0 0 1
+V
-V
4
Nyquist Limit
• How to improve upon this bit rate?
– Use more levels
6000 symbols/second
R = 12000 bits/second
0 2 3 3 1 0
00 10 11 11 01 00
– Thus if there are V signal levels, ignoring noise, the
maximum bit rate is
R = 2B log2 V bits/sec
5
Shannon’s Theorem
C = B log2 (1 + S/N)
• Upper bound on channel capacity, while
considering noise
– C : maximum capacity (bps)
– B : channel bandwidth (Hz)
– S/N: Signal to Noise Ratio (SN), often expressed in
decibels SNR := 10 log10 (S/N)
• Claude Shannon: Father of information theory
– “A Mathematical Theory of Communication”, 1948
6
Channel Capacity Example
• Bandwidth: 3200 Hz
– If use 4 signal levels over a noiseless channel,
what is the maximum bit rate?
R = 2B log2 V bits/sec
2 x 3200 x log2(4)=12.8 Kbps
• Typical S/N: 10
– What is the upper limit on capacity?
C = 3200 x log2(1 + 10) = 11 Kbps
– If use 4 signal levels, what is the maximum rate?
7
Lecture Progression
• Bottom-up through the layers
Application -HTTP, DNS, CDNs
Transport -TCP, UDP
Internet -IP, NAT, BGP
Link -Ethernet, 802.11
Physical -Wires, fiber, wireless
8
Overview of Link Layer
• Concerns how to transfer messages over one or
more connected links
– Messages are frames, of limited size
• Topics
– Framing
– Error coding (detection and correction)
– Retransmission
– Multiple Access
– Switching
9
In terms of layers
Network
Link
Virtual data path
Physical Actual data path
10
Typical Implementation of Layers
11
Framing
• A link layer function, defining which bits have
which function
• Minimal functionality: mark the beginning and
end of packets (or frames)
12
Byte Count
• Start each frame with a length field
– Simple, hopefully good enough…
– Difficult to re-synchronize after framing error
13
Byte Stuffing
• Idea: mark frames with special byte value that
means start/end of frame
– What happens when the user sends this FLAG
value?
• Replace the FLAG inside the frame with an escape code
• Have to escape the escape code too!
14
Byte Stuffing
• Rules
– Replace each FLAG in data with ESC FLAG
Original bytes Receiver
After stuffing
15
Byte Stuffing
• Rules
– Replace each ESC in data with ESC ESC
Original bytes Receiver
After stuffing
16
Byte Stuffing
• Rules
– Replace each FLAG in data with ESC FLAG
– Replace each ESC in data with ESC ESC
Original bytes Receiver
After stuffing
17
Byte Stuffing
• Rules
– Replace each FLAG in data with ESC FLAG
– Replace each ESC in data with ESC ESC
Original bytes Receiver
After stuffing
18
Bit Stuffing
• Stuff at the bit level: mark frames with special bit
sequence
– Must ensure data containing this sequence can be
transmitted
– Example: 111111 (six ‘1’s) is a flag
• Transmitter: after five 1s in the data, insert a 0
111111 -> 1111101
• Receiver: a 0 after five 1s is deleted (unstuffs)
1111101 -> 111111
• Less overhead, but more complicated than byte
stuffing
19
Example
Data bits: 111111
Transmitted bits 0 0 0
with stuffing 111111
20
Example
Data bits
Transmitted bits
with stuffing
21
Ethernet Framing
• Preamble is 7 bytes of 10101010 (5 MHz
square wave) followed by one byte of
10101011
• Allows receivers to recognize start of
transmission after idle channel
Preamble SFD Datagram Length More stuff
22
Noise may flip received bits
1 1 1
Signal
0 0 0 0 0
Slightly 1 1 1
Noisy 0 0 0 0 0
Very 1 1 1
noisy 0 0 0 0 0
23
Noise may flip received bits
1 1 1
Signal
0 0 0 0 0
Slightly 1 1 1
Noisy 0 0 0 0 0
Very 1 1 1
noisy 0 0 0 0 0
24
Error Coding
• Some bits will be received in error due to
noise (at the Physical Layer).
• What can we do?
– Detect errors with codes (Retransmit)
– Correct errors with codes
• Reliability is a concern that cuts across the
layers
25
Approach – Add Redundancy
• Error detection codes
– Add check bits to the message bits to let some errors be
detected
• Error correction codes
– Add more check bits to let some errors be corrected
• Key issue is how to structure the code to detect
many errors with few check bits and modest
computation
26
Motivating Example
• A simple code to handle errors:
– Send two copies ! Error if different 010 → 010 010
• How good is this code?
– How many errors can it detect/correct?
• Correct - 0 010 110 010? 110? 111?
• Detect - ? 101 101 010 101
– How many errors will make it fail?
• 2 011 011
• We want to handle more errors with less overhead
27
Systematic Block Code
• Codeword consists of D data bits plus R check
bits
D R = fn(D) D R’
R = fn(D)
Sender: Receiver:
- Compute R check bits based on the D - Receive D+R bits with unknown errors
data bits; - Recompute R check bits based on the
- Send the codeword of D+R bits D data bits; error if R does not match R’
28
Intuition for Error Codes
Correct codewords 2D
All possible combinations 2D+R
• Send a valid codeword A, what is not desirable at the
receiver?
– Receive a valid codeword A
– Receive an invalid codeword B
– Receive a valid codeword C
• Randomly chosen codeword is unlikely to be correct;
overhead is low 29
