Scribd Logo
Upload

Welcome to Scribd!

  • 86 views

    Data Link Layer: Unit - III

    Uploaded by

    Francis Densil Raj
    The document discusses framing and error detection techniques in data link layer. It describes: 1. Data link layer takes packets from network layer and encapsulates them into frames by adding header, trailer and error detection bits. Frames can be of fixed or variable size. 2. Variable sized frames use length field or end delimiter for framing. Bit-stuffing or byte-stuffing is used to avoid confusion with delimiter pattern in message. 3. Error detection techniques like parity check, checksum and cyclic redundancy check are used to detect errors in frames. Error correction uses techniques like backward error correction and forward error correction.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd

    Data Link Layer: Unit - III

    Uploaded by

    Francis Densil Raj
    86 views24 pages
    The document discusses framing and error detection techniques in data link layer. It describes: 1. Data link layer takes packets from network layer and encapsulates them into frames by adding header, trailer and error detection bits. Frames can be of fixed or variable size. 2. Variable sized frames use length field or end delimiter for framing. Bit-stuffing or byte-stuffing is used to avoid confusion with delimiter pattern in message. 3. Error detection techniques like parity check, checksum and cyclic redundancy check are used to detect errors in frames. Error correction uses techniques like backward error correction and forward error correction.

    Original Description:

    CN

    Original Title

    Unit 3

    Copyright

    © © All Rights Reserved

    Available Formats

    PPTX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses framing and error detection techniques in data link layer. It describes: 1. Data link layer takes packets from network layer and encapsulates them into frames by adding header, trailer and error detection bits. Frames can be of fixed or variable size. 2. Variable sized frames use length field or end delimiter for framing. Bit-stuffing or byte-stuffing is used to avoid confusion with delimiter pattern in message. 3. Error detection techniques like parity check, checksum and cyclic redundancy check are used to detect errors in frames. Error correction uses techniques like backward error correction and forward error correction.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    86 views24 pages

    Data Link Layer: Unit - III

    Uploaded by

    Francis Densil Raj
    The document discusses framing and error detection techniques in data link layer. It describes: 1. Data link layer takes packets from network layer and encapsulates them into frames by adding header, trailer and error detection bits. Frames can be of fixed or variable size. 2. Variable sized frames use length field or end delimiter for framing. Bit-stuffing or byte-stuffing is used to avoid confusion with delimiter pattern in message. 3. Error detection techniques like parity check, checksum and cyclic redundancy check are used to detect errors in frames. Error correction uses techniques like backward error correction and forward error correction.

    Copyright:

    © All Rights Reserved
    Download as PPTX, PDF, TXT or read online from Scribd
    Download as pptx, pdf, or txt
    of 24

    Data Link Layer

    Unit - III
    Framing in Data Link Layer
    • synchronized transmission of bits from the source to the destination.
    • packs bits into frames.
    • Data-link layer takes the packets from the Network Layer and
    encapsulates them into frames.
    • If the frame size becomes too large, then the packet may be divided
    into small sized frames.
    • Smaller sized frames makes flow control and error control more
    efficient.
    • Then, it sends each frame bit-by-bit on the hardware.
    • At receiver’s end, data link layer picks up signals from hardware and
    assembles them into frames.
    Parts of a Frame
    • A frame has the following parts −
    • Frame Header − It contains the source and the destination addresses
    of the frame.
    • Payload field − It contains the message to be delivered.
    • Trailer − It contains the error detection and error correction bits.
    • Flag − It marks the beginning and end of the frame.
    Types of Framing
    • Fixed-sized Framing
    • Here the size of the frame is fixed
    • the frame length acts as delimiter of the frame
    • does not require additional boundary bits to identify the start and
    end of the frame.
    • Example − ATM cells.
    • Variable – Sized Framing
    • the size of each frame to be transmitted may be different
    • additional mechanisms are kept to mark the end of one frame and
    the beginning of the next frame.
    Two ways to define frame delimiters in variable sized framing are −
    • Length Field − Here, a length field is used that determines the size of
    the frame.
    • End Delimiter − Here, a pattern is used as a delimiter to determine
    the size of frame.
    • If the pattern occurs in the message, then two approaches are used to
    avoid the situation −
    • Byte – Stuffing − A byte is stuffed in the message to differentiate from the
    delimiter. This is also called character-oriented framing.
    • Bit – Stuffing − A pattern of bits of arbitrary length is stuffed in the message
    to differentiate from the delimiter. This is also called bit – oriented framing.
    Error Detection and Correction in Data link Layer

    • bit streams of data, are transmitted from the source to the destination with a
    certain extent of accuracy.
    Errors
    • Data may get corrupted due to interference and network problems.
    • The corrupted bits leads to spurious data being received by the destination
    and are called errors.
    • Types of Errors
    • Single bit error 
    • Multiple bits error 
    • Burst error 
    Single bit error
    • In the received frame, only one bit has been corrupted, i.e. either
    changed from 0 to 1 or from 1 to 0.

    • Multiple bits error − In the received frame, more than one bits are
    corrupted.
    Burst error
    • In the received frame, more than one consecutive bits are corrupted.

    Error Control
    • Error control can be done in two ways
    • Error detection − Error detection involves checking whether any error has occurred or not.
    • Error correction − Error correction involves ascertaining the exact number of bits that has
    been corrupted and the location of the corrupted bits.
    • For both error detection and error correction, the sender needs to send some additional
    bits along with the data bits.
    • The receiver performs necessary checks based upon the additional redundant bits.
    • If it finds that the data is free from errors, it removes the redundant bits before passing the
    message to the upper layers.
    Error Detection Techniques

    • There are three main techniques for detecting errors in frames: Parity Check,
    Checksum and Cyclic Redundancy Check (CRC).
    • Parity Check
    • The parity check is done by adding an extra bit, called parity bit to the data
    While creating a frame, the sender counts the number of 1s in it and adds the
    parity bit in the following way
    • In case of even parity: If a number of 1s is even then parity bit value is 0. If the
    number of 1s is odd then parity bit value is 1.
    • In case of odd parity: If a number of 1s is odd then parity bit value is 0. If a
    number of 1s is even then parity bit value is 1.
    • On receiving a frame, the receiver counts the number of 1s in it.
    • In case of even parity check, if the count of 1s is even, the frame is accepted,
    otherwise, it is rejected. A similar rule is adopted for odd parity check.
    • The parity check is suitable for single bit error detection only.
    Checksum

    • Data is divided into fixed sized frames or segments.


    • The sender adds the segments using 1’s complement arithmetic to get
    the sum.
    • It then complements the sum to get the checksum and sends it along
    with the data frames.
    • The receiver adds the incoming segments along with the checksum
    using 1’s complement arithmetic to get the sum and then
    complements it.
    • If the result is zero, the received frames are accepted; otherwise, they
    are discarded.
    Cyclic Redundancy Check (CRC)
    • Cyclic Redundancy Check (CRC) involves binary division of the data bits
    • the sender performs binary division of the data segment by the divisor.
    • It then appends the remainder called CRC bits to the end of the data
    segment.
    • This makes the resulting data unit exactly divisible by the divisor.
    • The receiver divides the incoming data unit by the divisor.
    • If there is no remainder, the data unit is assumed to be correct and is
    accepted.
    • Otherwise, it is understood that the data is corrupted and is therefore
    rejected.
    Error Correction Techniques

    • Backward Error Correction (Retransmission) 


    • If the receiver detects an error in the incoming frame, it requests the sender to
    retransmit the frame.
    • Forward Error Correction
    • If the receiver detects some error in the incoming frame, it executes error-correcting
    code that generates the actual frame.
    The four main error correction codes are
    • Hamming Codes
    • Binary Convolution Code
    • Reed – Solomon Code
    • Low-Density Parity-Check Code
    Stop-and-Wait Protocol 

    • transmission of frames over noiseless channels.


    • It provides unidirectional data transmission.
    • the receiver has a finite processing speed.
    • If data frames arrive at the receiver’s end at a rate which is greater
    than its rate of processing, frames be dropped out. 
    • the receiver sends an acknowledgement for each frame upon its
    arrival.
    • he sender sends the next frame only when it has received a positive
    acknowledgement from the receiver
    • Sender Site: The data link layer in the sender site waits for the
    network layer for a data packet. It then checks whether it can send
    the frame. If it receives a positive notification from the physical layer,
    it makes frames out of the data and sends it. It then waits for an
    acknowledgement before sending the next frame.
    • Receiver Site: The data link layer in the receiver site waits for a frame
    to arrive. When it arrives, the receiver processes it and delivers it to
    the network layer. It then sends an acknowledgement back to the
    sender.
    Flow control
    • Flow control is a technique that allows two stations working at
    different speeds to communicate with each other. 
    Sliding Window Protocol

    • multiple frames are sent by sender at a time before needing an


    acknowledgment (can be single)
    • Sliding window refers to an imaginary boxes that hold the frames on both
    sender and receiver side.
    •  Frames may be acknowledged by receiver at any point even when
    window is not full on receiver side.
    • Frames may be transmitted by source even when window is not yet full
    on sender side.
    • 0 to n-1
    Sliding Window on Sender Side

    • At the beginning of a transmission, the sender's window contains n-l


    frames.
    • Let the window size is 7
    Sliding Window on Receiver Side

    • At the beginning of transmission, the receiver's window


    contains n-1 spaces for frame but not the frames.
    • As the new frames come in, the size of window shrinks.
    • Given a window of size w, if three frames are received without an ACK
    being returned, the number of spaces in a window is w-3.
    Multiple Access Protocols

    • The Data Link Layer is responsible for transmission of data between two nodes.
    Its main functions are-
    • Data Link Control
    • Multiple Access Control
    • Data Link control
    • reliable transmission of message over transmission channel by using techniques
    like framing, error control and flow control
    Multiple Access Control
    • If there is a dedicated link between the sender and the receiver then data link
    control layer is sufficient
    • if there is no dedicated link present then multiple stations can access the
    channel simultaneously.
    • Hence multiple access protocols are required to decrease collision and avoid
    crosstalk.
    1. Random Access Protocol
    •  all stations have same superiority
    It has two features
    • There is no fixed time for sending data
    • There is no fixed sequence of stations sending data
    (a) ALOHA – 
    • It was designed for wireless LAN but is also applicable for shared
    medium.
    • multiple stations can transmit data at the same time and can hence
    lead to collision and data being garbled.
    • Pure Aloha
    • Slotted Aloha
    • Checksum Example-
    •

    • Consider the data unit to be transmitted is-

    • 10011001111000100010010010000100

    • Consider 8 bit checksum is used.

    • Step-01:
    •

    • At sender side,

    • The given data unit is divided into segments of 8 bits as-

    • Now, all the segments are added and the result is obtained as-

    • 10011001 + 11100010 + 00100100 + 10000100 = 1000100011


    • Since the result consists of 10 bits, so extra 2 bits are wrapped around.
    • 00100011 + 10 = 00100101 (8 bits)
    • Now, 1’s complement is taken which is 11011010.
    • Thus, checksum value = 11011010
    •

    • Step-02:
    •

    • The data along with the checksum value is transmitted to the receiver.
    •

    • Step-03:
    •

    • At receiver side,

    • The received data unit is divided into segments of 8 bits.


    • All the segments along with the checksum value are added.
    • Sum of all segments + Checksum value = 00100101 + 11011010 = 11111111
    • Complemented value = 00000000
    • Since the result is 0, receiver assumes no error occurred in the data and therefore accepts it.

    You might also like