Data link layer, framing and error control notes — Unit 2

The Data Link Layer (DLL) is Layer 2 of the OSI model. Its primary function is to transform the raw transmission facility provided by the physical layer into a reliable link. It makes the physical layer appear error-free to the upper layers (Network layer).

⇒1.1 Key Responsibilities of DLL

• Framing: Divides the stream of bits received from the network layer into manageable data units called frames.
• Physical Addressing: Adds a header to the frame to define the sender and/or receiver of the frame (MAC addresses).
• Flow Control: Implements mechanisms to prevent a fast sender from overwhelming a slow receiver.
• Error Control: Adds mechanisms to detect and retransmit damaged or lost frames.
• Access Control: Determines which device has control over the link at any given time when two or more devices are connected to the same link (MAC sublayer).

The data link layer acts as an intermediary, and it faces several design issues to ensure smooth communication between adjacent nodes.

⇒2.1 Services Provided to the Network Layer

• Unacknowledged Connectionless Service: Independent frames are sent without any acknowledgment from the receiver. Suitable for highly reliable links or real-time traffic (e.g., Ethernet).
• Acknowledged Connectionless Service: No logical connection is established, but every frame sent is individually acknowledged. Used over unreliable channels (e.g., Wi-Fi).
• Acknowledged Connection-Oriented Service: A logical connection is set up before data transfer. Frames are numbered, ensuring they are received exactly once and in the correct order.

To provide service to the network layer, the data link layer must use the service provided by the physical layer. The physical layer accepts and transmits raw bits. DLL breaks these bit streams into discrete frames. There are four common framing methods:

⇒3.1 Character Count

Uses a field in the header to specify the number of characters in the frame. If the count is garbled by a transmission error, the receiver loses synchronization, making this method unreliable.

⇒3.2 Flag Bytes with Byte Stuffing

A special byte called a flag byte is used as both the starting and ending delimiter of a frame. If the flag byte pattern coincidentally occurs in the data, a special escape byte (`ESC`) is inserted just before it. This is known as Byte Stuffing.

⇒3.3 Starting and Ending Flags with Bit Stuffing

Used for bit-oriented protocols. Each frame begins and ends with a special bit pattern: `01111110`. To prevent this pattern from appearing in the payload, the sender inserts a `0` bit after every five consecutive `1`s in the data. The receiver removes it. This is Bit Stuffing.

⇒3.4 Physical Layer Coding Violations

Some encodings on the physical layer have invalid signals (e.g., Manchester encoding requires a transition in the middle of every bit). A signal without a transition can be used to mark the start and end of frames.

Signals traveling over transmission media are subject to attenuation, distortion, and noise, leading to bit errors (a `0` becomes a `1`, or vice versa).

⇒4.1 Types of Errors

• Single-bit Error: Only one bit in a given data unit is changed. Very rare in serial data transmission.
• Burst Error: Two or more bits in the data unit have changed. More common in serial transmission due to impulse noise.

⇒4.2 Detection vs Correction

To detect errors, redundant bits are added to the data payload at the sender's end, and verified at the receiver's end.

⇒5.1 Simple Parity Check

A single bit (parity bit) is appended to a block of data. In Even Parity, the bit is set so the total number of `1`s is even. In Odd Parity, the total number of `1`s is odd.

• Advantage: Very simple to implement.
• Disadvantage: Can only detect an odd number of errors. Fails if an even number of bits are inverted.

⇒5.2 Two-Dimensional Parity Check

Data is organized in a table. Parity bits are calculated for each row and each column. It significantly improves detection capability and can even locate a single-bit error.

⇒5.3 Checksum

Commonly used in the Transport layer (TCP/UDP). The data is divided into equal segments (e.g., 16 bits). These segments are added using 1's complement arithmetic, and the sum is complemented to form the checksum.

CRC is the most powerful and widely used error detection technique in the Data Link Layer. It is based on polynomial division using Modulo-2 arithmetic (XOR operations).

⇒6.1 How CRC Works

• The sender and receiver agree on a common generator polynomial `G(x)` of degree `r`.
• The sender appends `r` zero bits to the original data message `M(x)`.
• The appended message is divided by the generator polynomial using Modulo-2 division.
• The resulting remainder is the CRC checksum.
• The sender replaces the appended zeros with the CRC checksum and transmits the data.
• At the receiver, the incoming data is divided by the same generator `G(x)`. If the remainder is zero, the data is accepted; otherwise, it is rejected.

CRC is incredibly robust. It can detect all single-bit errors, all double-bit errors (if G(x) has a factor with at least 3 terms), and all burst errors of length less than or equal to the degree of the polynomial.

The Hamming Code, developed by Richard Hamming, is a Forward Error Correction (FEC) technique that detects and corrects single-bit errors.

⇒7.1 Redundant Bits Calculation

To determine how many redundant bits `r` are needed for a message of `m` bits, we use the formula:
`2^r >= m + r + 1`

⇒7.2 Bit Positioning

Redundant bits are placed at positions that are powers of 2 (1, 2, 4, 8...). The data bits are placed in the remaining positions (3, 5, 6, 7, 9...).

⇒7.3 Parity Calculation

Each parity bit calculates even parity over a specific set of bits. For example, `P1` checks bits 1, 3, 5, 7. `P2` checks bits 2, 3, 6, 7. `P4` checks bits 4, 5, 6, 7.

At the receiver end, the parity checks are performed again. The results (0s and 1s) form a binary number that directly points to the exact position of the erroneous bit, allowing it to be flipped and corrected.

Flow Control is a set of procedures that restricts the amount of data that a sender can transmit before waiting for an acknowledgment. Its goal is to prevent a fast sender from flooding a slow receiver with data.

⇒8.1 Why is Flow Control Needed?

Receivers have a limited amount of memory (buffer) to store incoming data. If data arrives faster than the receiver's CPU can process it, the buffer fills up. Any subsequent frames will be dropped and permanently lost.

⇒8.2 Categories of Flow Control

• Feedback-based Flow Control: The receiver sends back information (acknowledgments) to the sender giving it permission to send more data. (Used in Data Link and Transport layers).
• Rate-based Flow Control: The protocol has a built-in mechanism that limits the rate at which senders can transmit data, without requiring feedback from the receiver.

These are foundational protocols designed for theoretical understanding. They assume an idealized environment.

⇒9.1 Unrestricted Simplex Protocol

Assumes the channel is perfectly reliable (no errors, no lost frames) and the receiver has an infinite buffer and infinite processing speed. The sender continuously pumps out frames without waiting for any acknowledgment.

⇒9.2 Simplex Stop-and-Wait Protocol

Removes the assumption of an infinite buffer at the receiver. The sender transmits one frame and completely halts until it receives a 'dummy' acknowledgment frame from the receiver. Only then does it send the next frame.

While it solves flow control, it is extremely inefficient on links with long propagation delays (low channel utilization).

Also known as the Simplex Protocol for a Noisy Channel. It adds error control to the basic Stop-and-Wait protocol.

⇒10.1 Key Mechanisms

• Timers: The sender starts a countdown timer when it transmits a frame. If the timer expires before an ACK is received, it assumes the frame (or ACK) was lost and retransmits.
• Sequence Numbers: To solve the duplicate frame problem (caused by a lost ACK resulting in a retransmission), frames are tagged with alternating sequence numbers (0 and 1).
• ACK Numbers: The receiver sends an ACK containing the sequence number of the next frame it expects to receive.

Efficiency Issue: The sender still only sends one frame at a time, leaving the channel idle for a full Round Trip Time (RTT).

To overcome the inefficiency of Stop-and-Wait, sliding window protocols allow the sender to transmit multiple frames before waiting for an acknowledgment. This keeps the network 'pipe' full, improving bandwidth utilization.

⇒11.1 The Sender Window

The sender maintains a 'window' of sequence numbers representing frames it is permitted to send. When an ACK arrives, the window 'slides' forward, allowing new frames to be transmitted.

⇒11.2 The Receiver Window

The receiver maintains a window of sequence numbers representing the frames it is currently willing to accept. Frames falling outside this window are discarded.

There are two main implementations of sliding window protocols with error control: Go-Back-N and Selective Repeat.

In Go-Back-N, the sender window size can be greater than 1 (up to `2^m - 1`, where `m` is the sequence number bit size), but the receiver window size is always exactly 1.

⇒12.1 Operational Mechanism

• The receiver only accepts frames arriving strictly in the correct order.
• If a frame is lost or corrupted, the receiver discards it and all subsequent frames.
• When the sender's timer expires for the lost frame, the sender must 'go back N' frames and retransmit the lost frame along with all subsequent frames that were already transmitted.

⇒12.2 Pros and Cons

• Advantage: Very simple receiver logic, requires minimal buffering.
• Disadvantage: Wastes bandwidth on retransmitting successfully received frames that arrived after the lost one.

Selective Repeat is designed to overcome the bandwidth waste of Go-Back-N. In this protocol, both the sender and receiver maintain a window size strictly greater than 1 (specifically, `2^(m-1)`).

⇒13.1 Operational Mechanism

• The receiver accepts and buffers out-of-order frames that fall within its receiver window.
• If a frame is lost, the receiver sends a Negative Acknowledgment (NAK) specifically for that frame.
• The sender only retransmits the precise frame that was lost or corrupted, not the entire window.
• Once the missing frame arrives, the receiver sorts the buffered frames and delivers them to the network layer in order.

⇒13.2 Pros and Cons

• Advantage: Highly efficient use of bandwidth; no redundant retransmissions.
• Disadvantage: Complex implementation requiring sorting logic and significant buffering at both sender and receiver.

⇒14.1 High-Level Data Link Control (HDLC)

HDLC is a bit-oriented protocol developed by ISO. It supports both point-to-point and multipoint configurations.

• Frame Types: Information frames (I-frames) for data, Supervisory frames (S-frames) for flow/error control, and Unnumbered frames (U-frames) for link management.
• Framing: Uses the `01111110` flag with bit stuffing.

⇒14.2 Point-to-Point Protocol (PPP)

PPP is a highly popular byte-oriented protocol primarily used for point-to-point links (e.g., dial-up connections, DSL).

• It provides error detection but no error correction (no flow control).
• Includes the Link Control Protocol (LCP) to establish, configure, and test the data-link connection.
• Includes Network Control Protocols (NCPs) to negotiate network-layer protocol options.
• Supports authentication via protocols like PAP and CHAP.

To deliver a packet from a source to a destination across different networks, both MAC (Physical) and Logical (IP) addresses are strictly required.

⇒15.1 Physical (MAC) Address

• Operates at the Data Link Layer (Layer 2).
• Burned into the NIC; permanently identifies a specific hardware device.
• Used for node-to-node delivery within the same local network.
• Changes hop-by-hop as the frame moves from one router to the next.

⇒15.2 Logical (IP) Address

• Operates at the Network Layer (Layer 3).
• Assigned by the network administrator or DHCP; identifies a node's location on the internet.
• Used for end-to-end delivery across different networks.
• Remains constant from the original source to the final destination.

When a sender knows the destination's IP address (from DNS) but needs to build a Layer 2 frame, it must discover the destination's MAC address. ARP bridges this gap.

⇒16.1 The ARP Process

• ARP Request (Broadcast): The sender blasts a message to `FF:FF:FF:FF:FF:FF` asking, 'Who has IP 192.168.1.5? Tell 192.168.1.2.'
• ARP Reply (Unicast): Every device on the LAN receives the request, but only the device with IP `192.168.1.5` replies directly to the sender with its MAC address.
• ARP Cache: To avoid flooding the network with requests, devices temporarily store resolved IP-to-MAC mappings in an ARP cache table.

⇒16.2 ARP in Routing

If the destination IP is on a completely different network, the sender uses ARP to find the MAC address of its Default Gateway (the router), not the final destination.

The primary motivation behind sliding window protocols (like Go-Back-N and Selective Repeat) is to maximize channel utilization (efficiency).

⇒17.1 Mathematical Model

Let `Tt` be the Transmission Time (time to put the frame onto the wire) and `Tp` be the Propagation Delay (time for one bit to travel from sender to receiver).

• Round Trip Time (RTT): `2 * Tp`
• Total cycle time for one frame: `Tt + 2 * Tp`
• Let `a = Tp / Tt`.

⇒17.2 Efficiency Comparisons

Cyclic Redundancy Check relies heavily on Modulo-2 arithmetic, which is essentially binary addition and subtraction without carries or borrows (equivalent to the logical XOR operation).

⇒18.1 The Division Process

• Let the generator polynomial `G(x)` correspond to a bit pattern of length `n`.
• Append `n-1` zeros to the original data message.
• Perform Modulo-2 division (using XOR) of the padded message by the generator pattern.
• The final remainder of this division (which will be `n-1` bits long) is the CRC.
• Replace the appended zeros with the CRC to form the final transmitted frame.

⇒18.2 Standard Generator Polynomials

Polynomials are chosen based on their mathematical properties to detect specific types of errors. For example, `CRC-32` (used in Ethernet and ZIP files) is a 33-bit pattern that detects all burst errors of 32 bits or less, and 99.9999999% of burst errors greater than 32 bits.

High-Level Data Link Control (HDLC) is a foundational bit-oriented protocol. Its frame structure dictates exactly how data and control information are packaged.

⇒19.1 HDLC Frame Fields

⇒19.2 The Control Field (Frame Types)

• I-Frames (Information): Carry user data and piggybacked acknowledgments for flow control.
• S-Frames (Supervisory): Carry flow and error control commands (e.g., Receive Ready, Reject) when there is no user data to piggyback on.
• U-Frames (Unnumbered): Used for link management and connection setup/teardown. They do not carry sequence numbers.

The Point-to-Point Protocol (PPP) includes an Authentication phase to verify the identity of the user before allowing access to the network layer (crucial for ISP dial-up and DSL connections).

⇒20.1 PAP (Password Authentication Protocol)

A very basic two-way handshake. The client repeatedly sends its username and password in clear text until the server accepts it. Because it is unencrypted, it is highly vulnerable to eavesdropping and replay attacks.

⇒20.2 CHAP (Challenge Handshake Authentication Protocol)

A highly secure three-way handshake that never transmits the actual password.

• Challenge: The server sends a random string (the challenge) to the client.
• Response: The client concatenates the challenge with its secret password, runs it through a one-way hashing algorithm (like MD5), and sends the resulting hash back to the server.
• Verification: The server performs the exact same mathematical hash on its end. If the hashes match, access is granted. A hacker intercepting the hash cannot reverse it to find the password.