Transcript Error Correction and Detection

Data Link Layer
Position of the data-link layer
Data link layer duties
Data Link Layer Design Issues
•
•
•
•
Network layer services
Framing
Error control
Flow control
Data Link Layer Design Issues
• Physical layer delivers bits of information to and from data link
layer. The functions of Data Link Layer are:
1. Providing a well-defined service interface to the network layer.
2. Dealing with transmission errors.
3. Regulating the flow of data so that slow receivers are not
swamped by fast senders.
• Data Link layer
– Takes the packets from Network layer, and
– Encapsulates them into frames
• Each frame has a
– frame header – a field for holding the packet, and
– frame trailer.
• Frame Management is what Data Link Layer does.
Packets and Frames
Relationship between packets and
frames.
Relationship between packets and frames.
Services Provided to the Network Layer
• Principal Service Function of the data link layer is to transfer
the data from the network layer on the source machine to the
network layer on the destination machine.
– Process in the network layer that hands some bits to the
data link layer for transmission.
– Job of data link layer is to transmit the bits to the
destination machine so they can be handed over to the
network layer there (see figure in the next slide).
Network Layer Services
(a) Virtual communication. (b) Actual
communication.
Possible Services Offered
1.Unacknowledged connectionless service.
2.Acknowledged connectionless service.
3.Acknowledged connection-oriented service.
Unacknowledged Connectionless Service
• It consists of having the source machine send independent
frames to the destination machine without having the
destination machine acknowledge them.
• Example: Ethernet, Voice over IP, etc. in all the
communication channel were real time operation is more
important that quality of transmission.
Acknowledged Connectionless Service
• Each frame send by the Data Link layer is acknowledged and
the sender knows if a specific frame has been received or lost.
• Typically the protocol uses a specific time period that if the
given time has passed without getting acknowledgment it will
re-send the frame.
• This service is useful when an unreliable channel is being
utilized (e.g., 802.11 WiFi).
Acknowledged Connection Oriented Service
• Source and Destination establish a connection first.
• Each frame sent is numbered
– Data link layer guarantees that each frame sent is indeed
received.
– It guarantees that each frame is received only once and
that all frames are received in the correct order.
• Examples:
– Satellite channel communication
– Long-distance telephone communication, etc.
Framing
• To provide service to the network layer the data link layer
must use the service provided to it by physical layer.
• Stream of data bits provided to data link layer is not
guaranteed to be without errors.
• It is up to data link layer to correct the errors if necessary.
Framing
• Transmission of the data link layer starts with breaking up the
bit stream
– into discrete frames
– Computation of a checksum for each frame, and
– Include the checksum into the frame before it is
transmitted.
• Receiver computes its checksum error for a receiving frame
and if it is different from the checksum that is being
transmitted will have to deal with the error.
• Framing is more difficult than one could think!
Framing Methods
1.Byte count.
2.Flag bytes with byte stuffing.
3.Flag bits with bit stuffing.
Byte Count Framing Method
• It uses a field in the header to specify the number of bytes in the
frame.
• Once the header information is being received it will be used to
determine end of the frame.
• Trouble with this algorithm is that when the count is incorrectly
received the destination will get out of synch with transmission.
– Destination may be able to detect that the frame is in error but it
does not have a means (in this algorithm) how to correct it.
Framing (1)
A byte stream. (a) Without errors. (b) With
one error.
Flag Bytes with Byte Stuffing Framing
Method
• This methods gets around the boundary detection of the
frame by having each appended by the frame start and frame
end special bytes.
• If they are the same (beginning and ending byte in the frame)
they are called flag byte.
• If the actual data contains a byte that is identical to the FLAG
byte (e.g., picture, data stream, etc.) the convention that can
be used is to have escape character inserted just before the
“FLAG” character.
Framing (2)
• A frame delimited by flag bytes.
• Four examples of byte sequences before and after byte stuffing.
Flag Bits with Bit Stuffing Framing
Method
• This methods achieves the same thing as Byte Stuffing
method by using Bits (1) instead of Bytes (8 Bits).
• Each frames begins and ends with a special bit pattern:
– Whenever the sender’s data link layer encounters five
consecutive 1s in the data it automatically stuffs a 0 bit into the
outgoing bit stream.
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 the receiver’s memory after
de stuffing.
Error Detection
and Correction
• Types of Errors
• Detection
• Correction
Basic concepts
Networks must be able to transfer data from one
device to another with complete accuracy.
Data can be corrupted during transmission.
For reliable communication, errors must be
detected and corrected.
Error detection and correction
are implemented either at the data link
layer or the transport layer of the OSI
model.
Types of Errors
Single-bit error
Single bit errors are the least likely type of errors in
serial data transmission because the noise must have a
very short duration which is very rare. However this
kind of errors can happen in parallel transmission.
Burst error
The term burst error means that two or more bits in the
data unit have changed from 1 to 0 or from 0 to 1.
Burst errors does not necessarily mean that the errors
occur in consecutive bits, the length of the burst is
measured from the first corrupted bit to the last corrupted
bit. Some bits in between may not have been corrupted.
Error detection
Error detection means to decide whether the
received data is correct or not without having a
copy of the original message.
Error detection uses the concept of redundancy,
which means adding extra bits for detecting
errors at the destination.
Redundancy
Detection methods
Parity Check
A parity bit is added to every data unit so that the total
number of 1s(including the parity bit) becomes even for
even-parity check or odd for odd-parity check
Detection -examples
Example 1
Suppose the sender wants to send the word world. In
ASCII the five characters are coded as
1110111 1101111 1110010 1101100 1100100
The following shows the actual bits sent
11101110 11011110 11100100 11011000
11001001
Example 2
Now suppose the word world in Example 1 is received
by the receiver without being corrupted in
transmission.
11101110 11011110 11100100 11011000
11001001
The receiver counts the 1s in each character and comes
up with even numbers (6, 6, 4, 4, 4). The data is
accepted.
Example 3
Now suppose the word world in Example 1 is
corrupted during transmission.
11111110 11011110 11101100 11011000
11001001
The receiver counts the 1s in each character and
comes up with even and odd numbers (7, 6, 5, 4, 4).
The receiver knows that the data are corrupted,
discards them, and asks for retransmission.
Vertical Redundancy Check
VRC
Longitudinal Redundancy Check
LRC
Two –Dimensional Parity Check
Cyclic Redundancy Check
CRC
Cyclic Redundancy Check
• Given a k-bit frame or message, the
transmitter generates an n-bit sequence,
known as a frame check sequence (FCS), so
that the resulting frame, consisting of (k+n)
bits, is exactly divisible by some
predetermined number.
• The receiver then divides the incoming
frame by the same number and, if there is
no remainder, assumes that there was no
error.
Binary Division
Polynomial
Polynomial and Divisor
Standard Polynomials
Checksum
At the sender
The unit is divided into k sections, each of n
bits.
All sections are added together using one’s
complement to get the sum.
The sum is complemented and becomes the
checksum.
The checksum is sent with the data
At the receiver
The unit is divided into k sections, each of n
bits.
All sections are added together using one’s
complement to get the sum.
The sum is complemented.
If the result is zero, the data are accepted:
otherwise, they are rejected.
Performance
The checksum detects all errors involving an
odd number of bits.
It detects most errors involving an even number
of bits.
If one or more bits of a segment are damaged
and the corresponding bit or bits of opposite
value in a second segment are also damaged, the
sums of those columns will not change and the
receiver will not detect a problem.
Error Correction
It can be handled in two ways:
1) receiver can have the sender retransmit the
entire data unit.
2) The receiver can use an error-correcting
code, which automatically corrects certain
errors.
Single-bit error correction
To correct an error, the receiver reverses the value
of the altered bit. To do so, it must know which bit
is in error.
Number of redundancy bits needed
• Let data bits = m
• Redundancy bits = r
Total message sent = m+r
The value of r must satisfy the following relation:
2r ≥ m+r+1
Error Correction
Hamming Code
Hamming Code
Hamming Code
Example of Hamming Code
Single-bit error
Error
Detection