lOMoARcPSD|16716744

Chapter 3-Data Link Layer

computer networks (Northeastern University China)

StuDocu is not sponsored or endorsed by any college or university

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)
 lOMoARcPSD|16716744

Th D
The Data
t Li
Link
kLLayer
Chapter 3

• Data Link Layer Design Issues

• Error Detection and Correction
• Elementary Data Link Protocols
• Sliding Window Protocols
• E
Examplel D
Data
t Li
Link
kPProtocols
t l

Revised: August 2011

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

The Data Link Layer

Application
Responsible for delivering frames of
Transport
information o
over
er a single link
Network
• Handles transmission errors and
Link
regulates
g the flow of data
Ph i l
Physical

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Data Link Layer Design Issues

• Frames »
• Possible services »
• Framing methods »
• Error control »
• Fl
Flow control
t l»

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Frames

Link layer accepts packets from the network layer, and

encapsulates them into frames that it sends using the
physical layer; reception is the opposite process

Network

Link
Virtual data p
path

Physical Actual data path

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Possible Services

Unacknowledged
g connectionless service
• Frame is sent with no connection / error recovery
• Ethernet is example
Acknowledged connectionless service
• Frame is sent with retransmissions if needed
• Example is 802.11
Acknowledged connection-oriented
connection oriented service
• Connection is set up; rare

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Framing Methods

• Byte count »
• Flag bytes with byte stuffing »
• Flag bits with bit stuffing »
• Physical layer coding violations
− Use non
non-data
data symbol to indicate frame

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Framing – Byte count

Frame begins
g with a count of the number of bytes
y in it
• Simple, but difficult to resynchronize after an error

Expected
case

Error
case

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Framing – Byte stuffing

Special
p flag
g bytes
y delimit frames;; occurrences of flags
g in
the data must be stuffed (escaped)
• Longer, but easy to resynchronize after error

Frame
format

Need to escape
extra ESCAPE
bytes too!
Stuffing
examples

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Framing – Bit stuffing

Stuffing
g done at the bit level:
• Frame flag has six consecutive 1s (not shown)
• On transmit, after five 1s in the data, a 0 is added
• On receive, a 0 after five 1s is deleted

Data bits

Transmitted bits
with stuffing

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Error Control

Error control repairs

p frames that are received in error
• Requires errors to be detected at the receiver
• Typically retransmit the unacknowledged frames
• Timer protects against lost acknowledgements

Detecting errors and retransmissions are next topics.

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Flow Control

Prevents a fast sender from out-pacing

p g a slow receiver
• Receiver gives feedback on the data it can accept
• Rare in the Link layer as NICs run at “wire speed”
− Receiver can take data as fast as it can be sent

Flow control is a topic in the Link and Transport layers.

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Error Detection and Correction

Error codes add structured redundancy to data so

errors can be either detected
detected, or corrected
corrected.
Error correction codes:
• Hamming codes »
• Binary convolutional codes »
• Reed-Solomon and Low-Density Parity Check codes
− Mathematically complex, widely used in real systems

Error detection codes:

• Parity
P it »
• Checksums »
• Cyclic redundancy codes »

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Error Bounds – Hamming distance

Code turns data of n bits into codewords of n+k bits

Hamming distance is the minimum bit flips to turn one
valid codeword into anyy other valid one.
• Example with 4 codewords of 10 bits (n=2, k=8):
− 0000000000, 0000011111, 1111100000, and 1111111111
− Hamming
H i di
distance iis 5

Bounds for a code with distance:

• 2d+1 – can correct d errors (e.g., 2 errors above)
• d+1 – can detect d errors (e.g., 4 errors above)

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Error Correction – Hamming code

Hamming code gives a simple way to add check bits

and correct up to a single bit error:
• Check bits are parity over subsets of the codeword
• Recomputing the parity sums (syndrome) gives the
position of the error to flip, or 0 if there is no error

(11, 7) Hamming code adds 4 check bits and can correct 1 error

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Error Correction – Convolutional codes

Operates
p on a stream of bits,, keeping
p g internal state
• Output stream is a function of all preceding input bits
• Bits are decoded with the Viterbi algorithm

…111 … 0 1 1
1 0 1

P
Popular
l NASA binary
bi convolutional
l ti l code
d ((rate
t = ½) used
d iin 802
802.11
11

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Error Detection – Parity (1)

Parityy bit is added as the modulo 2 sum of data bits

• Equivalent to XOR; this is even parity
• Ex: 1110000  11100001
• Detection
D t ti checks h k if ththe sum iis wrong ((an error))

Simple way to detect an odd number of errors

• Ex: 1 error, 11100101; detected, sum is wrong
• Ex: 3 errors, 11011001; detected sum is wrong
• Ex: 2 errors, 11101101; not detected, sum is right!
• Error can also be in the parity bit itself
• Random errors are detected with probability ½

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Error Detection – Parity (2)

Interleaving
g of N p
parity
y bits detects burst errors up
p to N
• Each parity sum is made over non-adjacent bits
• An even burst of up to N errors will not cause it to fail

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Error Detection – Checksums

Checksum treats data as N-bit words and adds N check

bits that are the modulo 2N sum of the words
• Ex: Internet 16-bit 1s complement checksum

Properties:
• Improved
I d error d
detection
t ti over parity
it bit
bits
• Detects bursts up to N errors
• Detects random errors with probability 1-2N
• Vulnerable to systematic errors, e.g., added zeros

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Error Detection – CRCs (1)

Adds bits so that transmitted frame viewed as a polynomial
is evenly divisible by a generator polynomial

Start by adding
0s to frame
and try dividing

Offset by any reminder

to make it evenly
divisible

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Error Detection – CRCs (2)

Based on standard polynomials:

p y
• Ex: Ethernet 32-bit CRC is defined by:

• Computed with simple shift/XOR circuits

Stronger detection than checksums:

• E.g., can detect all double bit errors
• Not vulnerable to systematic errors

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Elementary Data Link Protocols

• Link layer environment »

• Utopian Simplex Protocol »
• Stop-and-Wait Protocol for Error-free channel »
• Stop-and-Wait Protocol for Noisy channel »

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Link layer environment (1)

Commonlyy implemented
p as NICs and OS drivers;;
network layer (IP) is often OS software

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Link layer environment (2)

Link layer protocol implementations use library functions
• See code (pprotocol.h) for more details

Group Library Function Description

ffrom_network_layer(&packet)
t k l (& k t) Take
T k a packetk t from
f network
t k layer
l to
t send
d
Network to_network_layer(&packet) Deliver a received packet to network layer
layer enable_network_layer() Let network cause “ready” events
disable_network_layer() Prevent network “ready” events
Physical from_physical_layer(&frame) Get an incoming frame from physical layer
layer to_physical_layer(&frame) Pass an outgoing frame to physical layer
wait_for_event(&event) Wait for a packet / frame / timer event
start_timer(seq_nr)
t t ti ( ) St t a countdown
Start td ti
timer running
i
Events &
stop_timer(seq_nr) Stop a countdown timer from running
timers
start_ack_timer() Start the ACK countdown timer
stop_ack_timer() Stop the ACK countdown timer

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Utopian Simplex Protocol

An optimistic protocol (p1) to get us started

• Assumes
A no errors, and
d receiver
i as ffast as sender
d
• Considers one-way data transfer

Sender loops blasting frames Receiver loops eating frames

• Th t’ it,
That’s it no error or flflow control
t l…

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Stop-and-Wait – Error-free channel

Protocol (p2) ensures sender can’t outpace receiver:
• Receiver returns a dummyy frame (ack)
( ) when readyy
• Only one frame out at a time – called stop-and-wait
• We added flow control!

Sender waits to for ack after Receiver sends ack after passing
passing frame to physical layer frame to network layer

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Stop-and-Wait – Noisy channel (1)

ARQ (Automatic Repeat reQuest) adds error control

• Receiver acks frames that are correctly delivered
• Sender sets timer and resends frame if no ack)

For correctness, frames and acks must be numbered

• Else receiver can’t
can t tell retransmission (due to lost
ack or early timer) from new frame
• For stop-and-wait, 2 numbers (1 bit) are sufficient

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Stop-and-Wait – Noisy channel (2)

{

Sender loop (p3):

Send frame (or retransmission)

S t timer
Set ti for
f retransmission
t i i
Wait for ack or timeout

If a good ack then set up for the

next frame to send (else the old
frame will be retransmitted)

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Stop-and-Wait – Noisy channel (3)

Receiver loop (p3):

Wait for a frame

If it’s new then take

it and advance
expected frame

Ack current frame

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Sliding Window Protocols

• Sliding Window concept »

• One-bit Sliding Window »
• Go-Back-N »
• Selective Repeat »

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Sliding Window concept (1)

Sender maintains window of frames it can send

• Needs to buffer them for possible retransmission
• Window advances with next acknowledgements
Receiver maintains window of frames it can receive
• Needs to keep p buffer space
p for arrivals
• Window advances with in-order arrivals

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Sliding Window concept (2)

A sliding
g window advancing
g at the sender and receiver
• Ex: window size is 1, with a 3-bit sequence number.

Sender

Receiver

At the start Firstt frame

Fi f Firstt frame
Fi f Sender
S d gets t
is sent is received first ack

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Sliding Window concept (3)

Larger
g windows enable ppipelining
p g for efficient link use
• Stop-and-wait (w=1) is inefficient for long links
• Best window (w) depends on bandwidth-delay (BD)
• Want w ≥ 2BD+1 to ensure high link utilization

Pipelining leads to different choices for errors/buffering

• We will consider Go-Back-N and Selective Repeat

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

One-Bit Sliding Window (1)

Transfers data in both directions with stop-and-wait
• Piggybacks
ggy acks on reverse data frames for efficiencyy
• Handles transmission errors, flow control, early timers
{

Each node is sender

and receiver (p4):

Prepare first frame

Launch it, and set timer

...
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

One-Bit Sliding Window (2)

...
Wait for frame or timeout

If a frame with new data

th deliver
then d li it

If an ack for last send then

prepare for next data frame

(Otherwise it was a timeout)

Send next data frame or

retransmit old one; ack
the last data we received

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

One-Bit Sliding Window (3)

Two scenarios show subtle interactions exist in p4:
− Simultaneous start [right] causes correct but slow operation
compared to normal [left] due to duplicate transmissions.

Time

Notation is ((seq,
q ack, frame number).
) Asterisk indicates frame accepted
p by
y network layer
y .

Normal case Correct, but poor performance

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Go-Back-N (1)

Receiver onlyy accepts/acks

p frames that arrive in order:
• Discards frames that follow a missing/errored frame
• Sender times out and resends all outstanding frames

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Go-Back-N (2)

Tradeoff made for Go-Back-N:

• Simple strategy for receiver; needs only 1 frame
• Wastes link bandwidth for errors with large
windows; entire window is retransmitted

Implemented as p5 (see code in book)

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Selective Repeat (1)

Receiver accepts
p frames anywhere
y in receive window
• Cumulative ack indicates highest in-order frame
• NAK (negative ack) causes sender retransmission of
a missing frame before a timeout resends window

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Selective Repeat (2)

Tradeoff made for Selective Repeat:

• More complex than Go-Back-N due to buffering
att receiver
i and
d multiple
lti l titimers att sender
d
• More efficient use of link bandwidth as only lost
frames are resent (with low error rates)

Implemented as p6 (see code in book)

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Selective Repeat (3)

For correctness,, we require:

q
• Sequence numbers (s) at least twice the window (w)

Error case (s=8, w=7) – too Correct (s=8, w=4) – enough

few sequence numbers sequence numbers

Originals Retransmits Originals Retransmits

New receive window overlaps New and old receive window

old
ld – retransmits
t it ambiguous
bi d ’t overlap
don’t l – no ambiguity
bi it

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Example Data Link Protocols

• Packet over SONET »

• PPP (Point-to-Point Protocol) »
• ADSL (Asymmetric Digital Subscriber Loop) »

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

Packet over SONET

Packet over SONET is the method used to carryy IP

packets over SONET optical fiber links
• Uses PPP (Point-to-Point Protocol) for framing

Protocol stacks PPP frames may be split

over SONET payloads

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

PPP (1)

PPP ((Point-to-Point Protocol)) is a g

general method for
delivering packets across links
• Framing uses a flag (0x7E) and byte stuffing
• “Unnumbered mode” (connectionless unacknow-
ledged service) is used to carry IP packets
• Errors are detected with a checksum

0x21 for IPv4 IP packet

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

PPP (2)

A link control p
protocol brings
g the PPP link up/down
p

State machine for link control

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

ADSL (1)

Widelyy used for broadband Internet over local loops

p
• ADSL runs from modem (customer) to DSLAM (ISP)
• IP packets are sent over PPP and AAL5/ATM (over)

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

ADSL (2)

PPP data is sent in AAL5 frames over ATM cells:

• ATM is a link layer that uses short, fixed-size cells
(53 bytes); each cell has a virtual circuit identifier
• AAL5 is a format to send packets over ATM
• PPP frame is converted to a AAL5 frame (PPPoA)

AAL5 frame is divided into 48 byte pieces, each of

which
hi h goes iinto
t one ATM cellll with
ith 5 h
header
d b bytes
t

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)

 lOMoARcPSD|16716744

End

Chapter 3

CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice Hall and D. Wetherall, 2011

Downloaded by sivaramakrishna B (sivaram6115@gmail.com)