Transcript The Data Link Layer

Chapter 3
THE DATA LINK
LAYER
1
HYBRID MODEL
 The
2
hybrid reference model to be used in this book.
FUNCTIONS
LAYER
OF THE
DATA LINK
3
DATA LINK LAYER DESIGN ISSUES
Services Provided to the Network Layer
• Framing (Packetizing)
• Physical addressing
• Error Control
• Flow Control
• Access control.
•
4
SERVICES PROVIDED TO NETWORK
LAYER
• Unacknowledged connectionless service.
No acknowledgement, no logical connection, used
in very low error rate channel and real-time traffic.
•
Acknowledged connectionless service.
each frame acknowledged, used in unreliable
channel
•
Acknowledged connection-oriented service
a connection established, frames are
numbed.reliable transmission guaranteed.
5
For the data link layer, break the bit stream
up into discrete frames and computer the
checksum for each frame (error control).
Four methods are used to break the bit
stream.
1.Character count. (rarely used)
2.Flag bytes with byte stuffing
3.Starting and ending flags, with bit
stuffing.
4.Physical layer coding violations.
6
FRAMING (PACKETIZING)
7
FRAMING (2)
(a) A frame delimited by flag bytes.
8
(b) Four examples of byte sequences before and after stuffing.
FRAMING (3)
Bit stuffing
(a) The original data.
(b) The data as they appear on the line.
(c) The data as they are stored in receiver’s memory9
after destuffing.
Flow Control
Ensuring the sending entity does not overwhelm the
receiving entity
Feedback-based flow control
Rate-based flow control (network layer)
10
STOP AND WAIT
Only one frame at a time can
be in transit.
1.Source transmits frame
2.Destination receives frame
and replies with
acknowledgement (if it is
correct, otherwise send
NAK.)
3.Source waits for ACK
before sending next frame
4.Destination can stop flow
by not send ACK
5.Source can retransmit if
got a NAK.
6.Works well for a few large
frames
7.Inefficient line utilization11for
small frames
SLIDING WINDOW PROTOCOLS
Allow multiple frames to be
in transit
•Receiver has buffer W
long
•Transmitter can send up to
W frames without ACK
•Each frame is numbered
•ACK includes number of
next frame expected
•Sequence number
bounded by size of field (k)
• Frames are numbered
12
modulo 2k
EXAMPLE SLIDING WINDOW
13
SLIDING WINDOW PROTOCOLS (2)
Duplex communication: each station needs
to maintain two windows
Piggyback: num of frame and num of ack are
included in one frame.
Sliding-window flow control is more efficient
than stop-and-wait flow control.
14
ERROR CONTROL
Detection and correction of errors
• Lost frames: a frame failed to arrived to the
other side.
• Damaged frames: some bits are in error.
Automatic repeat request
 Error detection
 Positive acknowledgment
 Retransmission after timeout
 Negative acknowledgement
15
ERROR DETECTION AND
ERROR CORRECTION
 Additional
bits added by transmitter for
error detection and/or error correction
code
 Error detection is more often used in
protocol with ARQ.
High code rate, high reliability.
c) Error correction is used in specific
situation. (no reverse channel)
d) Hybrid ARQ: combination of error
detection and correction.
16
ERROR CONTROL SCHEME
17
STOP-AND –WAIT ARQ
1. Source transmits single
frame
2. Wait for ACK
3. If received frame
damaged, discard it
4. Transmitter has timeout
5. If no ACK within timeout,
retransmit
6. If ACK damaged,
transmitter will not
recognise it, Transmitter
will retransmit
7. Receive gets two copies
of frame
18
8. Use ACK0 and ACK1
9. Simple but Inefficient
GO BACK N
 Based
on sliding window
 If no error, ACK as usual with next frame expected
 Use window to control number of outstanding
frames
 If error, reply with rejection
 Discard that frame and all future frames until
error frame received correctly
 Transmitter must go back and retransmit that
frame and all subsequent frames
19
SELECTIVE REJECT
(RETRANSMISSION)
 Only
rejected frames are retransmitted
 Subsequent frames are accepted by the
receiver and buffered
 Minimizes retransmission
 Receiver must maintain large enough buffer
to reordering.
 More complex login in transmitter
20
EXAMPLE DATA LINK PROTOCOLS
• HDLC
– High-Level Data Link
Control
• The Data Link Layer in the Internet
21
HIGH-LEVEL DATA LINK CONTROL
22
Frame format for bit-oriented protocols.
HIGH-LEVEL DATA LINK CONTROL (2)
23
The contents of an HDLC frame are shown in the following table:
Flag
Address
Control Information
8
bits
8 or
8 or 16
more bits bits
Variable length, 0 or more
bits
FCS
Flag
16 or 32
bits
8 bits
24
THE DATA LINK LAYER IN THE
INTERNET
PPP (Point-to-point protocol) handles error
detection, supports multiple protocols, allows
IP addresses to be negotiated at connection
time.
25
PPP – POINT TO POINT PROTOCOL
The PPP full frame format for unnumbered
mode operation.
26
Performance of ARQ
Stop-and-Wait Flow Control
The total time to send the data as
T = n(2tprop + tframe)
The utilization, or efficiency, of the line is
u
n  t frame
n(2t prop  t frame)
It is useful to define the parameter a = tprop/tframe .
Then
1
u
1  2a
27
Error-free sliding-window flow control
1

u W
1  2a
W  1  2a
W  1  2a
where W is window size
28