Transcript The Data Link Layer

The Data Link Layer
Husnain Sherazi
Department of Computer Science & IT
Lahore Leads University
TCP/IP Suite and OSI Reference Model
The TCP/IP protocol stack does not define
the lower layers of a complete protocol
stack
In this lecture, we will address how the
TCP/IP protocol stacks interfaces with the
data link layer and the MAC sublayer
Application
Layer
Application
Layer
Transport
Layer
Network
Layer
(Data) Link
Layer
Presentation
Layer
Session
Layer
Transport
Layer
Network
Layer
(Data) Link
Layer
Physical
Layer
TCP/IP Suite
OSI
Reference
Model
Data Link Layer
a)
Objective:
–
b)
Achieving reliable communication between two adjacent machines
Design Issues:
–
–
–
–
–
Framing: data are sent in blocks called frames, the beginning and end of each
frame must be recognized by the receiver.
Error control: bit errors introduced by the transmission system should be
detected and/or corrected.
Flow control: the sending station must not send frames at a rate faster than the
receiving station can absorb them.
Addressing: on a multipoint line, such as a LAN, the identity of the two
stations involved in a transmission must be specified.
Transmit control information and data on the same line
3
Framing
Relationship between packets and frames.
Framing
a)
Large block of data may be broken up into small frames at the
source because:
–
–
limited buffer size at the receiver
A larger block of data has higher probability of error
•
–
With smaller frames, errors are detected sooner, and only a
smaller amount of data needs to be retransmitted
On a shared medium, such as Ethernet and Wireless LAN, small frame size
can prevent one station from occupying medium for long periods
5
Framing
a)
b)
c)
Need to indicate the start and end of a block of data
Use preamble (e.g., flag byte) and postamble
If the receiver ever loses synchronization, it can just search for the flag
byte.
Frame: preamble + control info + data + postamble
Problem: it is possible that the flag byte’s bit pattern occur in the data
Two popular solutions:
d)
e)
f)
–
Byte stuffing
•
•
–
The sender inserts a special byte (e.g., ESC) just before each “accidental” flag byte
in the data (like in C language, “ is replaced with \”).
The receiver’s link layer removes this special byte before the data are given to the
network layer.
Bit stuffing: each frame starts with a flag byte “01111110”.
•
•
Whenever the sender encounters five consecutive 1s in the data, it automatically
stuffs a 0 bit into the outgoing bit stream.
When the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it
automatically deletes the 0 bit.
6
Services Provided to Network Layer
(a) Virtual communication.
(b) Actual communication.
Services Provided to Network Layer
Placement of the data link protocol.
Framing
A character stream. (a) Without errors. (b) With one error.
Framing (2)
(a) A frame delimited by flag bytes.
(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 memory after destuffing.
Error Detection: Types of Error
a)
An error occurs when a bit is altered between transmission and
reception
Single bit errors
b)
–
–
–
c)
One bit is altered
Adjacent bits are not affected
Can occur in the presence of white noise (thermal noise)
Burst errors
–
–
–
–
A cluster of bits with Length B
the first and the last and a number of intermediate bits in error (not necessarily
all the bits in the cluster suffer an error)
More common and more difficult to deal with
Can be caused by impulse noise
12
Error Detection Process
• Additional bits are added by
transmitter for error detection (called
error-detecting codes, or check bits,
or checksum)
13
• Can be used in different
network layers
Parity Check
a)
b)
Append a parity bit to the end of a block of data
Value of parity bit is such that the new data has even (even parity)
or odd (odd parity) number of ones
–
c)
E.g., original data 1110001 -> 11100011 (odd parity)
Even number of bit errors goes undetected
–
E.g., 11100011 -> 11010011 (undetected!)
14
Cyclic Redundancy Check
a)
For a block of k bits, transmitter generates an (n-k)-bit sequence
called Frame Check Sequence (FCS)
The resulting frame consisting of n bits is exactly divisible by some
predetermined number.
Receiver divides the incoming frame by the predetermined number:
b)
c)
–
If no remainder, assume no error
15
Error Correction
a)
Retransmission: correction of detected errors usually requires data
block to be retransmitted
–
Retransmission may not be appropriate for some wireless applications
•
•
–
Propagation delay can be long (satellite) compared with frame transmission
time
•
b)
c)
Bit error rate in wireless network is high
Result in lots of retransmissions
Result in retransmission of frame in error plus many subsequent frames (back to
this issue in next chapter)
It would be desirable to enable the receiver to correct errors in an
incoming transmission on the basis of the bits in that transmission.
FEC: Forward Error Correction
16
Error Correction Process Diagram
17
Line Configuration
a)
Link Topology
–
–
–
Physical arrangement of stations on the medium (link)
Link has two stations: a point-to-point link
More than two stations: a multipoint link
•
b)
local area network, satellite
Half duplex
–
–
c)
Of two stations, only one station may transmit at a time
Requires one data path
Full duplex
–
–
–
Simultaneous transmission and reception between two stations
Digital signaling: requires two data paths (e.g., two twisted pairs)
Analog signaling: can use different frequencies
18
Flow Control
a)
Ensuring the sending entity does not overwhelm the receiving entity
–
b)
Transmission time
–
–
c)
Time taken to emit all bits into medium at the sender’s side
Determined by the data rate
Propagation time
–
–
d)
Preventing buffer overflow
Time for a bit to traverse the link and reach the destination
Determined by the transmission distance
We first assume error-free transmission.
19
Model of Frame Transmission
20
Flow Control: Initial Assumptions
a)
b)
c)
d)
e)
Simplex Channel
Infinite buffer capacity with the receiver
Error free transmission
Network layer at the senders end is always ready with data
No need for flow control
Unrestricted Simplex Protocol
a) Data transmission in one direction
b) From Sender to Receiver
c) Communication channel is assumed to be
error free
d) Receiver is able to process infinitely
quickly
Simplex Stop-and-Wait Protocol
a) Unidirectional and Communication channel is
again assumed to be error free
b) But this time receiver has a limited size buffer
c) Sender can not rush with the data
d) One frame at a time and ACK for it
e) In this protocol, the contents of
acknowledgement frame are unimportant.
the
A Simplex Protocol for a Noisy Channel
a. What if the channel is noisy and we can lose
frames
b. A positive acknowledgement with
retransmission protocol.
c. Add a time out to the sender so it retransmits
after a certain period
Further assumptions dropped
a) The channel is noisy, frames may be damaged or lost
b) Good scene : data frame reaches intact, ack sent back and
received, next frame sent
c) Bad scene :
–
–
Data frame damaged or lost ..hence no ack – sender times out
and resends .. No problems
Data frame reaches intact but Ack lost .. Times out ..resends..
Receiver receives duplicate frames..Problem
Problem of Duplicate frames
a) Solution :
–
Keep a sequence number for each frame to
distinguish between the new frame and a duplicate
frame.
b) How large should be the sequence number? Or
c) What should be minimum number of bits
required for the sequence number?
–
The only ambiguity at the receiver is between two
successive frames.. Say m and m+1 and never
between m-1 and m +1 .. Its only after the ack for m1 reaches back intact mth frame is sent.. And once
mth frame reaches intact at the receiver’s end .. Story
of m-1th frame is over .. However depending upon
whether ack of mth frame reaches back intact or not
either mth or m+1 th frame is sent .. hence only 1 bit
is sufficient
Further assumption dropped
a)
b)
Channel is simplex ..
So, Now communication is two way .. I.e. Duplex channel
–
–
Interleave data and ack .. So ..a kind field is required to specify whether the
frame contains data or ack.
Piggyback ack on data frame
Sliding Window Protocol
1.
2.
Assumes two-way communication (full duplex). It uses two types of
frames:
Data
Ack (sequence number of last correctly received frame)
The basic idea of sliding window protocol is that both sender and
receiver keep a ``window'' of acknowledgment. The sender keeps
the value of expected acknowledgment; while the receiver keeps the
value of expected receiving frame. When it receives an
acknowledgment from the receiver, the sender advances the
window. When it receives the expected frame, the receiver advances
the window
Sliding Window Protocol(Duplex)
a) At any instant of time, the sender maintains a set of
sequence numbers corresponding to frames it is permitted
to send – this includes
–
–
Frames not yet sent
Frames sent but not yet acknowledged .. May have to be sent
again
This corresponds to the sender’s window. When a packet comes from
the NL ..it is appended in the window and when an ack arrives
for a frame..it is deleted from the buffer(and from the window)
Sliding Window Protocol(Duplex)
a) Similarly, the receiver also maintains a set of sequence
numbers corresponding to frames it is permitted to accept.
–
When a frame arrives, its seq number is checked..if it falls in the
window it is accepted else discarded .. Once an ack is sent for a
frame it is deleted from the window so that duplicate frames are
not accepted.
b) Sliding window gives the DLL the flexibility to accept the
frames in any order but they must be handed over to the
NL in order.
Sliding Window Protocols
• A One-Bit Sliding Window Protocol
• A Protocol Using Go Back N
• A Protocol Using Selective Repeat
Sliding Window Protocols (2)
A sliding window of size 1, with a 3-bit sequence number.
(a) Initially.
(b) After the first frame has been sent.
(c) After the first frame has been received.
(d) After the first acknowledgement has been received.
A One-Bit Sliding Window Protocol (2)
Two scenarios for protocol 4. (a) Normal case. (b) Abnormal
case. The notation is (seq, ack, packet number). An asterisk
indicates where a network layer accepts a packet.
A Protocol Using Go Back N
Pipelining and error recovery. Effect on an error when
(a) Receiver’s window size is 1.
(b) Receiver’s window size is large.
Go back N
A Sliding Window Protocol Using Selective Repeat
a)
b)
Now if 4 frames transmitted (seq nr 0-3), and sequence number 1
has an error. Frames 2-3 will not be ignored at receiver side, but
they can be buffered.
What happens when Frame 1 times out and is retransmitted? Upon
reception, the receiver can pass frames 1, 2 and 3 up to the network
layer and update its receiver window.
Selective Repeat
Selective Repeat