Unit 5: DATA LINK LAYER

The Data Link Layer (DLL) is the second layer of the OSI model. It is responsible for node-to-node delivery of data, framing, error control, flow control, and access control. The DLL takes packets from the Network Layer, encapsulates them into frames, and sends them to the Physical Layer for transmission. It is divided into two sublayers: Logical Link Control (LLC) and Media Access Control (MAC).

1. Elementary Datalink Protocols

Elementary protocols manage flow control and error control for data transmission between a sender and a receiver.

1.1 Unrestricted Simplex Protocol (Utopian)

• Concept: Assumes an ideal channel with no errors and a receiver capable of processing data infinitely fast.
• Mechanism: The sender continuously pumps data out; the receiver continuously accepts it.
• Drawback: Unrealistic. Does not handle flow control or error control.

1.2 Simplex Stop-and-Wait Protocol

• Concept: Addresses the issue of the receiver being overwhelmed (flow control). Still assumes an error-free channel.
• Mechanism:
  1. Sender transmits a single frame and waits.
  2. Receiver receives the frame, processes it, and sends a dummy "ACK" (acknowledgment) frame back to the sender.
  3. Sender receives the ACK and transmits the next frame.
• Drawback: Inefficient use of bandwidth, especially over long distances (high propagation delay).

1.3 Protocol for Noisy Channels (Stop-and-Wait ARQ)

• Concept: Handles both flow control and error control (damaged or lost frames).
• Mechanism: Uses sequence numbers (0 and 1) and timers.
  • If a frame is lost or corrupted (checked via CRC), the receiver drops it and does not send an ACK.
  • The sender's timer expires (timeout), triggering a retransmission of the unacknowledged frame.
• Drawback: Waiting for an ACK after every frame drastically reduces channel utilization.

1.4 Sliding Window Protocols

To overcome the inefficiency of Stop-and-Wait, sliding window protocols allow the sender to transmit multiple frames before needing an acknowledgment.

• Go-Back-N ARQ: If a frame is lost, the receiver discards all subsequent frames. The sender must retransmit the lost frame and all frames sent after it.
• Selective Repeat ARQ: The receiver buffers out-of-order frames. If a frame is lost, the sender only retransmits the specifically lost frame.

2. Error Detection and Correction

During transmission, electrical noise or physical anomalies can alter data bits. Errors can be Single-bit errors (one bit changed) or Burst errors (multiple bits changed).

2.1 Parity Check (Error Detection)

The simplest form of error detection involves appending a redundant bit (parity bit) to the data unit.

• Even Parity: The parity bit is set so that the total number of 1s in the frame (including the parity bit) is an even number.
• Odd Parity: The total number of 1s is made odd.
• Limitations: Can only detect an odd number of bit errors. If two bits flip, the parity remains correct (undetected error).

2.2 Checksum (Error Detection)

Primarily used in the Internet (TCP/IP).

• Sender:
  1. Divides data into segments of bits (usually 16 bits).
  2. Adds all segments together using 1's complement arithmetic.
  3. Complements the final sum to get the Checksum.
  4. Appends the Checksum to the data.
• Receiver:
  1. Adds all received segments (including the Checksum) using 1's complement arithmetic.
  2. Complements the result.
  3. If the result is all 0s, the data is accepted; otherwise, it is rejected.

2.3 Cyclic Redundancy Check - CRC (Error Detection)

Highly robust technique based on polynomial arithmetic.

• Mechanism:
  1. The sender and receiver agree on a Generator Polynomial of degree (represented as a binary string of bits).
  2. The sender appends zero bits to the end of the data message .
  3. The sender performs Modulo-2 division (XOR operation) of the padded message by .
  4. The remainder of this division is the CRC.
  5. The sender replaces the padded zeros with the CRC and transmits the frame.
• Validation: The receiver divides the incoming frame by . If the remainder is zero, there are no errors.

2.4 Hamming Code (Error Detection and Correction)

Developed by R.W. Hamming, this technique uses multiple parity bits placed at specific positions to not only detect but correct single-bit errors.

• Calculating Redundant Bits (): Must satisfy the inequality , where is the number of data bits.
• Positioning: Redundant (parity) bits are placed at positions that are powers of 2 (1, 2, 4, 8, etc.). Data bits fill the remaining positions.
• Parity Calculation (Even Parity Example):
  • (position 1) checks bits 1, 3, 5, 7, 9, 11...
  • (position 2) checks bits 2, 3, 6, 7, 10, 11...
  • (position 4) checks bits 4, 5, 6, 7, 12, 13...
• Error Correction: The receiver recalculates the parity bits. If errors are found, the decimal equivalent of the failed parity bits pinpoints the exact bit position of the error, allowing it to be flipped (corrected).

3. MAC Sublayer (Medium Access Control)

The MAC sublayer is the lower sublayer of the DLL. When multiple stations share a single communication channel (e.g., a bus network, wireless airwaves), there must be a mechanism to determine who gets to use the channel at what time to prevent collisions. This is governed by Multiple Access Protocols.

4. Multiple Access Protocols

These protocols are broadly divided into three categories: Random Access, Controlled Access, and Channelization.

4.1 Random Access (Contention-Based) Protocols

No station is assigned superiority. Any station can transmit data at any time, which leads to collisions.

ALOHA

Developed at the University of Hawaii for wireless data transmission.

• Pure ALOHA:
  • Stations transmit frames whenever they have data.
  • If a collision occurs, frames are destroyed. The sender waits for a random backoff time and retransmits.
  • Vulnerable Time: (where is frame transmission time).
  • Maximum Efficiency: ~18.4% (at ).
• Slotted ALOHA:
  • Time is divided into discrete slots. Stations can only begin transmission at the beginning of a slot.
  • Reduces the chance of collisions.
  • Vulnerable Time: .
  • Maximum Efficiency: ~36.8% (at ).

CSMA (Carrier Sense Multiple Access)

"Listen before you talk." Before transmitting, a station listens to the channel to check if it is idle.

• 1-persistent CSMA: Station senses the channel. If idle, it transmits immediately (probability = 1). If busy, it continuously monitors until idle and then transmits. High chance of collision if multiple stations are waiting.
• Non-persistent CSMA: If the channel is idle, transmit. If busy, wait for a random amount of time before sensing again. Reduces collisions but increases delay.
• p-persistent CSMA: Used in slotted channels. If idle, transmit with probability . With probability , defer to the next slot.

CSMA/CD (CSMA with Collision Detection)

Used primarily in traditional wired Ethernet (IEEE 802.3).

• Mechanism:
  1. Station listens. If idle, begins transmission.
  2. While transmitting, it simultaneously monitors the channel for collisions (abnormal voltage spikes).
  3. If a collision is detected, transmission stops immediately.
  4. The station sends a Jam Signal to alert all other stations of the collision.
  5. The station applies a Binary Exponential Backoff algorithm to wait a random time before retrying.
• Constraint: To detect a collision before finishing transmission, the frame transmission time must be Propagation Delay.

4.2 Controlled Access Protocols

Stations consult one another to determine which station has the right to transmit. Collisions are eliminated.

• Reservation: Time is divided into intervals. A station must make a reservation in a "reservation frame" before sending data.
• Polling: Uses a Primary-Secondary topology. The primary device controls the link.
  • Poll: Primary asks a secondary if it has data to send.
  • Select: Primary tells a secondary it is about to send data to it.
• Token Passing: A special control frame called a "Token" circulates around the network (e.g., Token Ring). A station can only transmit data if it currently holds the token.

5. Ethernet Protocol (IEEE 802.3)

Ethernet is the most widely used local area network (LAN) technology. It operates at both the Physical and Data Link layers, utilizing the CSMA/CD MAC protocol.

5.1 Ethernet Frame Format

The standard IEEE 802.3 MAC frame consists of the following fields:

1. Preamble (7 bytes): Alternating 1s and 0s used for receiver clock synchronization.
2. Start Frame Delimiter (SFD) (1 byte): 10101011. Indicates the beginning of the frame.
3. Destination Address (6 bytes): The MAC address of the receiving station(s).
4. Source Address (6 bytes): The MAC address of the sending station.
5. Type/Length (2 bytes): Indicates either the length of the data field or the type of Network layer protocol (e.g., IPv4) encapsulated.
6. Data + Padding (46 to 1500 bytes): The actual payload. If data is less than 46 bytes, padding is added to meet the minimum frame size requirement (64 bytes total).
7. CRC / FCS (Frame Check Sequence) (4 bytes): Contains a 32-bit CRC generated over the Addresses, Type, and Data fields for error detection.

5.2 MAC Addressing

• Also known as physical addresses or hardware addresses.
• They are 48-bit (6-byte) addresses burned into the Network Interface Card (NIC).
• Represented in hexadecimal format (e.g., 00:1A:2B:3C:4D:5E).
• The first 24 bits are the Organizationally Unique Identifier (OUI) assigned by the IEEE to the manufacturer. The last 24 bits are assigned by the manufacturer.

5.3 Ethernet Evolution

• Standard Ethernet: 10 Mbps (e.g., 10Base-T, using CSMA/CD).
• Fast Ethernet (IEEE 802.3u): 100 Mbps. Can operate in half-duplex (with CSMA/CD) or full-duplex (no collisions, no CSMA/CD needed).
• Gigabit Ethernet (IEEE 802.3z / 802.3ab): 1 Gbps (1000 Mbps). Exclusively uses full-duplex switches in modern implementations, effectively rendering CSMA/CD obsolete in gigabit networks.