Data Link Layer Notes (SLIDES)

CONCISE VERSION

Data Link Layer Design Issues

• Frames

  • The link layer accepts packets from the network layer.

  • Encapsulates them into frames for transmission via the physical layer.

  • Reception involves the reverse process.

• Possible Services

  • Unacknowledged connectionless service

    • Frames are sent without connection establishment or error recovery.

    • Ethernet is an example.

  • Acknowledged connectionless service

    • Frames are sent with retransmissions if needed.

    • IEEE 802.11 is an example.

  • Acknowledged connection-oriented service

    • A connection is set up; this is relatively rare.

• Framing Methods

  • Byte count

  • Flag bytes with byte stuffing

  • Flag bits with bit stuffing

  • Physical layer coding violations using non-data symbols to indicate frame boundaries.

Framing

• Byte Count

  • A frame begins with a count of the number of bytes in it.

  • Simple but can be difficult to resynchronize after an error.

• Byte Stuffing

  • Special flag bytes delimit frames.

  • Occurrences of flags in the data must be stuffed (escaped).

  • Requires escaping extra ESCAPE bytes.

  • Example:

    • Key: AF

    • Esc: FA

    • Data: 1A F2 FA 3A 67 FA

  • Frame:

    • key

    • Esc

    • AF 1A F2 FA FA 3A 67 FA FA AF

• Bit Stuffing

  • Stuffing is done at the bit level.

  • A frame flag has six consecutive 1s.

  • On transmit, after five 1s in the data, a 0 is added.

  • On receive, a 0 after five 1s is deleted.

Error Control

• Error control repairs frames that are received in error.

• Requires errors to be detected at the receiver.

• Typically involves retransmitting unacknowledged frames.

• A timer protects against lost acknowledgements.

Flow Control

• Prevents a fast sender from out-pacing a slow receiver.

• The receiver provides feedback on the data it can accept.

• Less common in the Link layer because NICs run at wire speed.

Error Detection and Correction

• Error codes add structured redundancy to data so errors can be either detected or 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

  • Checksums

  • Cyclic redundancy codes

Error Bounds – Hamming Distance

• Code turns data of $n$ bits into codewords of $n+k$ bits.

• Hamming distance is the minimum number of bit flips to turn one valid codeword into any other valid one.

  • Example with 4 codewords of 10 bits ($n=2$, $k=8$):

    • 0000000000, 0000011111, 1111100000, and 1111111111

    • Hamming distance is 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)

Error Correction – Hamming Code

• Hamming code provides a 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.

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

Error Correction – Convolutional Codes

• Operates on a stream of bits, keeping internal state.

• Output stream is a function of all preceding input bits.

• Bits are decoded with the Viterbi Algorithm.

  • Popular NASA binary convolutional code (rate = 1/2) used in 802.11.

Error Detection – Parity

• The parity bit is added as the modulo 2 sum of data bits.

  • Equivalent to XOR; this is even parity.

  • Ex: 1110000 à 11100001

• Detection checks if the sum is wrong (an error).

• A 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 1/2.

Error Detection – Interleaved Parity

• Interleaving of $N$ parity bits detects burst errors up 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.

Error Detection – Checksums

• Checksum treats data as $N$-bit words and adds $N$ check bits that are the modulo $2^N$ sum of the words.

  • Ex: Internet 16-bit 1s complement checksum.

• Properties:

  • Improved error detection over parity bits.

  • Detects bursts up to $N$ errors.

  • Detects random errors with probability $1 - 2^{-N}$.

  • Vulnerable to systematic errors, e.g., added zeros.

Error Detection – CRCs

• Cyclic Redundancy Checks (CRCs) add bits so that the transmitted frame, viewed as a polynomial, is evenly divisible by a generator polynomial.

• Start by adding 0s to the frame and then dividing.

• Offset by any remainder to make it evenly divisible.

• Based on standard polynomials:

  • Ex: Ethernet 32-bit CRC is defined by a specific polynomial.

  • Computed with simple shift/XOR circuits.

• Stronger detection than checksums:

  • E.g., can detect all double bit errors.

  • Not vulnerable to systematic errors.

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

Link Layer Environment

• Commonly implemented as NICs and OS drivers; network layer (IP) is often OS software.

• Link layer protocol implementations use library functions.

Utopian Simplex Protocol

• An optimistic protocol (p1) to get us started.

  • Assumes no errors, and the receiver is as fast as the sender.

  • Considers one-way data transfer.

  • No error or flow control.

  • Sender loops blasting frames, and the receiver loops eating frames.

Stop-and-Wait – Error-Free Channel

• Protocol (p2) ensures sender can’t outpace receiver:

  • Receiver returns a dummy frame (ack) when ready.

  • Only one frame out at a time – called stop-and-wait.

  • Flow control is added.

Stop-and-Wait – Noisy Channel

• ARQ (Automatic Repeat reQuest) adds error control.

  • The receiver ACKs frames that are correctly delivered.

  • The sender sets a timer and resends the frame if no ACK is received.

• For correctness, frames and ACKs must be numbered.

  • Else receiver can’t tell retransmission (due to lost ACK or early timer) from a new frame.

  • For stop-and-wait, 2 numbers (1 bit) are sufficient.

Sliding Window Protocols

• Sliding Window concept

• One-bit Sliding Window

• Go-Back-N

• Selective Repeat

Sliding Window Concept

• The sender maintains a window of frames it can send.

  • Needs to buffer them for possible retransmission.

  • The window advances with acknowledgements.

• The receiver maintains a window of frames it can receive.

  • Needs to keep buffer space for arrivals.

  • The window advances with in-order arrivals.

• Larger windows enable pipelining for efficient link use.

  • Stop-and-wait (w=1) is inefficient for long links.

  • The best window (w) depends on bandwidth-delay (BD).

  • Want $w \ge 2BD+1$ to ensure high link utilization.

• Pipelining leads to different choices for errors/buffering.

One-Bit Sliding Window

• Transfers data in both directions with stop-and-wait.

• Piggybacks ACKs on reverse data frames for efficiency.

• Handles transmission errors, flow control, and early timers.

Go-Back-N

• The receiver only accepts/ACKs frames that arrive in order:

  • Discards frames that follow a missing/errored frame.

  • The sender times out and resends all outstanding frames.

• Tradeoff made for Go-Back-N:

  • Simple strategy for the receiver; needs only 1 frame buffer.

  • Wastes link bandwidth for errors with large windows; the entire window is retransmitted.

Selective Repeat

• The receiver accepts frames anywhere in the receive window.

• A cumulative ACK indicates the highest in-order frame.

• NAK (negative ack) causes the sender retransmission of a missing frame before a timeout resends the window.

• Tradeoff made for Selective Repeat:

  • More complex than Go-Back-N due to buffering at the receiver and multiple timers at the sender.

  • More efficient use of link bandwidth, as only lost frames are resent (with low error rates).

• For correctness, require:

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

  • $s \ge 2w$. This avoids ambiguity between new frames and retransmissions after the window slides.

Example Data Link Protocols

• Packet over SONET

• PPP (Point-to-Point Protocol)

• ADSL (Asymmetric Digital Subscriber Loop)

Packet Over SONET

• Packet over SONET is the method used to carry IP packets over
  SONET optical fiber links.

• Uses PPP (Point-to-Point Protocol) for framing.

• PPP frames may be split over SONET payloads.

PPP

• PPP (Point-to-Point Protocol) is a general method for delivering packets across links.

• Framing uses a flag (0x7E) and byte stuffing.

• “Unnumbered mode” (connectionless unacknowledged service) is used to carry IP packets.

• Errors are detected with a checksum.

• A link control protocol brings the PPP link up/down. Uses a state machine for link control.

ADSL

• Asymmetric Digital Subscriber Line (ADSL) is widely used for broadband Internet over local loops.

• ADSL runs from modem (customer) to DSLAM (ISP).

• IP packets are sent over PPP and AAL5/ATM.

• 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.

  • A PPP frame is converted to an AAL5 frame (PPPoA).

  • The AAL5 frame is divided into 48-byte pieces, each of which goes into one ATM cell with 5 header bytes.

DETAILED VERSION

Data Link Layer Design Issues

• Frames

  • The data link layer bridges the gap between the physical layer and the network layer by accepting packets from the network layer and transforming them into frames suitable for transmission.

  • Encapsulation: Packets are encapsulated into frames, adding headers and trailers to provide structure and control information.

  • Transmission: Frames are then passed to the physical layer for transmission over the communication channel.

  • Reception: The reverse process occurs at the receiving end, where the data link layer decapsulates frames to extract packets for the network layer.

• Possible Services

  • The data link layer offers a range of services to support reliable data transfer, each with distinct characteristics and trade-offs.

  • Unacknowledged Connectionless Service

    • Frames are sent without establishing a connection or guaranteeing delivery.

    • Characteristics: Simple and efficient, suitable for low-loss environments.

    • Error Recovery: No error recovery mechanisms are provided.

    • Example: Ethernet is a prime example of this service.

  • Acknowledged Connectionless Service

    • Frames are sent with retransmission mechanisms to ensure delivery.

    • Characteristics: Provides reliability without the overhead of connection establishment.

    • Retransmissions: Frames are retransmitted if acknowledgments are not received within a specified time.

    • Example: IEEE 802.11 (Wi-Fi) incorporates this service.

  • Acknowledged Connection-Oriented Service

    • A connection is established before data transfer begins, ensuring reliable, ordered delivery.

    • Characteristics: Offers the highest level of reliability but at the cost of increased overhead.

    • Connection Setup: Involves negotiating parameters and establishing a logical link between sender and receiver.

    • Relatively rare due to the overhead involved.

• Framing Methods

  • Framing methods define how frames are delimited and structured for transmission.

  • Byte Count

    • A frame begins with a count of the number of bytes in the frame.

    • Advantages: Simple to implement.

    • Disadvantages: Fragile; a single error can corrupt the frame count, leading to synchronization issues.

  • Flag Bytes with Byte Stuffing

    • Special flag bytes mark the beginning and end of frames.

    • Byte Stuffing: Occurrences of flag bytes within the data are escaped (stuffed) to avoid misinterpretation.

    • Overhead: Requires additional escaping of escape bytes themselves.

  • Flag Bits with Bit Stuffing

    • A specific bit pattern (e.g., six consecutive 1s) serves as the frame flag.

    • Bit Stuffing: After five consecutive 1s in the data, a 0 is inserted to prevent accidental flag patterns.

    • Advantages: More robust than byte stuffing.

  • Physical Layer Coding Violations

    • Non-data symbols or coding violations are used to indicate frame boundaries.

    • Examples: Utilizing signal levels or transitions that are not valid data symbols.

• Error Control

  • Error control ensures reliable data delivery by detecting and correcting errors introduced during transmission.

  • Mechanisms include error detection codes, retransmission protocols, and acknowledgment schemes.

• Flow Control

  • Flow control prevents a fast sender from overwhelming a slow receiver, ensuring efficient and reliable communication.

  • Techniques include feedback mechanisms, buffering, and rate control.

Framing

• Byte Count

  • In byte counting, each frame starts with a field indicating the number of bytes in the frame.

  • Simplicity: Easy to implement but highly susceptible to errors.

  • Resynchronization: Difficult to resynchronize if the count is corrupted.

• Byte Stuffing

  • Flag bytes are used to mark the start and end of a frame.

  • Escaping: If a flag byte appears in the data, it is escaped (stuffed) with an escape byte.

  • Key and Escape Bytes: Key (AF) and Esc (FA) are used.

  • Example:-

    • Key: AF

    • Esc: FA

    • Data: 1A F2 FA 3A 67 FA

    • Frame:

      • key

      • Esc

      • AF 1A F2 FA FA 3A 67 FA FA AF

  • Bit Stuffing

  • Data streams are examined at the bit level.

  • Frame Flag: Defined by six consecutive 1s.

  • Insertion: On transmission, a 0 is added after every five consecutive 1s in the data to prevent false flags.

  • Deletion: On reception, a 0 is deleted after every five consecutive 1s.

Error Control

• Error control is crucial for reliable communication, ensuring that frames are received correctly.

• Error Detection: Detecting errors at the receiver requires the use of error detection codes and mechanisms.

• Retransmission: Typically involves retransmitting frames that have not been acknowledged or are detected as erroneous.

• Timer Protection: A timer is set for each transmitted frame to protect against lost acknowledgments, triggering retransmission if an ACK is not received in time.

Flow Control

• Purpose: Prevents a fast sender from overwhelming a slow receiver by managing the rate of data transmission.

• Feedback: The receiver provides feedback to the sender about its capacity to accept data.

• Buffering: Receivers may buffer incoming data to handle temporary bursts but have limited capacity.

• Link Layer Relevance: Less common in modern link layers due to the high speed of Network Interface Cards (NICs) that operate close to wire speeds.

Error Detection and Correction

• Error Codes: Structured redundancy is added to data, enabling errors to be either detected or corrected, enhancing data integrity.

• Error Correction Codes

  • Hamming Codes: Correct single-bit errors by adding check bits and computing parity over subsets of the codeword.

  • Binary Convolutional Codes: Operate on a stream of bits, maintaining an internal state and generating an output stream based on preceding input bits; decoded with the Viterbi algorithm.

  • Reed-Solomon and Low-Density Parity Check (LDPC) Codes

    • Mathematically complex codes widely used in real systems, offering robust error correction capabilities.

• Error Detection Codes

  • Parity: Adds a parity bit to data to detect odd numbers of errors.

  • Checksums: Treat data as N-bit words and add N check bits that are the modulo $2^N$ sum of the words.

  • Cyclic Redundancy Checks (CRCs): Add bits so that the transmitted frame is evenly divisible by a generator polynomial, providing strong error detection.

Error Bounds – Hamming Distance

• Error bounds and Hamming distance are fundamental concepts in coding theory, providing a way to quantify the error detection and correction capabilities of a code; a code turns data of $n$ bits into codewords of $n+k$ bits.

• Hamming Distance: The minimum number of bit flips required to transform one valid codeword into another.

  • Example

    • Four codewords of 10 bits ($n=2$,$k=8$):

      • 0000000000

      • 0000011111

      • 1111100000

      • 1111111111

    • Hamming distance is 5.

• Bounds for a Code with Distance

  • $2d+1$: Can correct $d$ errors (e.g., 2 errors with distance 5).

  • $d+1$: Can detect $d$ errors (e.g., 4 errors with distance 5).

Error Correction – Hamming Code

• The Hamming code provides a method to add check bits to data, allowing for the correction of single-bit errors.

• Check Bits: These are parity bits calculated over subsets of the codeword.

• Syndrome: By recomputing the parity sums (syndrome), the position of the error can be identified and flipped.

• (11, 7) Hamming Code: An example is the (11, 7) Hamming code, which adds 4 check bits to 7 data bits and can correct one error.

Error Correction – Convolutional Codes

• Convolutional codes operate on a stream of bits and maintain an internal state, producing an output stream that is a function of all preceding input bits.

• Viterbi Algorithm: Bits are decoded using the Viterbi Algorithm, which finds the most likely sequence of states through the code trellis.

• NASA Binary Convolutional Code: A popular rate 1/2 code used in IEEE 802.11.

Error Detection – Parity

• Parity is a simple method for error detection, where a parity bit is added to the data.

• Modulo 2 Sum: The parity bit is calculated as the modulo 2 sum of the data bits, equivalent to an XOR operation; even parity is commonly used.

  • Example: 1110000 à 11100001

• Detection: Checks if the sum is wrong, indicating an error. It can detect an odd number of errors.

  • Examples

    • 1 error: 11100101; detected, sum is wrong.

    • 3 errors: 11011001; detected, sum is wrong.

    • 2 errors: 11101101; not detected, sum is right!

• Parity Bit Error: The error can also occur in the parity bit itself.

• Random Error Detection: Random errors are detected with a probability of 1/2.

Error Detection – Interleaved Parity

• Interleaving of $N$ parity bits is used to detect burst errors up to length $N$.

• Non-Adjacent Bits: Each parity sum is calculated over non-adjacent bits.

• Burst Error Detection: An even burst of up to $N$ errors will not cause it to fail.

Error Detection – Checksums

• Checksums involve treating data as $N$-bit words and adding $N$ check bits, which are the modulo $2^N$ sum of the words.

• Internet Checksum: The Internet uses a 16-bit 1s complement checksum as an example.

• Properties

  • Improved Error Detection: Compared to parity bits.

  • Burst Error Detection: Detects bursts of up to $N$ errors.

  • Random Error Detection: Detects random errors with a probability of $1 - 2^{-N}$.

  • Vulnerability: Systematic errors, such as added zeros, can bypass detection.

Error Detection – CRCs

• Cyclic Redundancy Checks (CRCs) add bits to a frame so that the entire transmitted frame, when viewed as a polynomial, is evenly divisible by a generator polynomial.

• Polynomial Division: Start by appending 0s to the frame and then performing polynomial division.

• Remainder Offset: Offset the frame by any remainder to ensure it is evenly divisible.

• Standard Polynomials: Based on standard polynomials like the Ethernet 32-bit CRC.

  • Computation: Computed with simple shift/XOR circuits.

• Advantages

  • Stronger Detection: More robust than checksums; can detect all double-bit errors.

  • Systematic Error Resistance: Not vulnerable to systematic errors.

Elementary Data Link Protocols

• Elementary data link protocols are fundamental techniques used for reliable data transfer over a link.

• Link Layer Environment

• Utopian Simplex Protocol

• Stop-and-Wait Protocol for Error-free Channel

• Stop-and-Wait Protocol for Noisy Channel

Link Layer Environment

• Link layers are commonly implemented as Network Interface Cards (NICs) and Operating System (OS) drivers, while the network layer (IP) is often implemented as OS software.

• Library Functions: Link layer protocol implementations use library functions available in the OS.

Utopian Simplex Protocol

• An optimistic protocol designed as a starting point, assuming no errors and a receiver as fast as the sender.

• One-Way Data Transfer: Considers only one-way data transfer.

• No Control: No error or flow control mechanisms are implemented.

• Operation: The sender continuously blasts frames, and the receiver continuously ingests them.

Stop-and-Wait – Error-Free Channel

• Protocol (p2) ensures sender can’t outpace receiver:-

  • Acknowledgement: Receiver returns a dummy frame (ACK) when ready to receive the next frame.

  • Single Frame: Only one frame is sent at a time, a technique known as stop-and-wait.

  • Flow Control: This adds flow control to guarantee that the sender does not overwhelm the receiver.

Stop-and-Wait – Noisy Channel

• ARQ (Automatic Repeat reQuest) adds error control to ensure reliable data transmission over a noisy channel.

• Acknowledgement: The receiver acknowledges frames that are correctly delivered, ensuring the sender knows the frame was received.

• Timer: The sender sets a timer for each frame and resends the frame if an ACK is not received within the timer interval.

• Numbering: Frames and ACKs must be numbered for correctness.

  • Prevents the receiver from mistaking a retransmission (due to a lost ACK or early timer) for a new frame.

  • Numbering: For stop-and-wait, 2 numbers (1 bit) are sufficient.

Sliding Window Protocols

• Sliding window protocols are techniques used to manage the flow of data between sender and receiver, enhancing efficiency and reliability.

• Sliding Window Concept

• One-bit Sliding Window

• Go-Back-N

• Selective Repeat

Sliding Window Concept

• The sliding window concept involves maintaining windows at both the sender and receiver to manage data transmission and reception.

• Sender Window: The sender maintains a window of frames that it is allowed to send.

  • Buffering: Requires buffering these frames for possible retransmission.

  • Advancement: The window advances as acknowledgements are received.

• Receiver Window: The receiver maintains a window of frames that it is prepared to receive.

  • Buffering: Needs to keep buffer space for incoming frames.

  • Advancement: The window advances as frames arrive in order.

• Pipelining: Larger windows enable pipelining, allowing for efficient link utilization where multiple frames are in transit simultaneously.

  • Stop-and-Wait Inefficiency: Stop-and-wait (w=1) is inefficient for long links.

  • Window Size: The best window size (w) depends on the bandwidth-delay (BD) product.

  • High Link Utilization: Want $$w "