Data Link Layer: Computer Networks

Data Link Layer: A Comprehensive Guide

The data link layer is the second layer of the OSI model, positioned between the physical layer and the network layer. It provides node-to-node (hop-to-hop) communication, ensuring reliable data transfer across a physical network link. The layer handles framing, addressing, flow control, error detection and correction, and media access control.

Responsibilities of the Data Link Layer

1. Framing:

   • The data link layer organizes the bit stream received from the network layer into manageable units called frames.
   • A frame contains control information, such as source and destination addresses, as well as the data payload.

2. Addressing:

   • Adds a header to each frame, containing the MAC (Media Access Control) address of both the sender and the receiver.
   • This addressing ensures the frame reaches the correct device in a local network.

3. Flow Control:

   • Prevents the sender from overwhelming the receiver if the sender's data production rate exceeds the receiver’s ability to process it.
   • Implements mechanisms like feedback-based and rate-based flow control.

4. Error Control:

   • Ensures reliable communication by detecting and retransmitting lost, corrupted, or duplicate frames.
   • Incorporates error detection and correction techniques.

5. Media Access Control (MAC):

   • Coordinates access to the shared communication medium, especially when multiple devices compete for the link.
   • Uses protocols like CSMA/CD (Carrier Sense Multiple Access with Collision Detection) or CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance).

Error Detection and Correction

Errors can occur during data transmission due to noise, interference, or signal degradation. The data link layer incorporates mechanisms to detect and correct these errors.

Types of Errors

1. Single-Bit Error:

   • Occurs when a single bit in the data unit is altered.
   • Example: 00000001 transmitted as 00000011.

2. Burst Error:

   • Occurs when two or more consecutive bits in the data unit are altered.
   • Example: 00011100 transmitted as 11010100.

Redundancy

• Redundancy involves adding extra bits to the original data to detect or correct errors.
• The sender encodes data with redundant bits, and the receiver verifies the received data for errors.

Detection vs. Correction

1. Error Detection:

   • Identifies the presence of an error but does not correct it.
   • Commonly used when retransmission is feasible.

2. Error Correction:

   • Corrects errors at the receiver without retransmission.
   • Useful in scenarios where retransmission is impractical, such as live broadcasts.

Forward Error Correction (FEC) vs. Retransmission

1. Forward Error Correction:

   • The receiver uses redundant bits to guess and correct the message.
   • Effective when errors are few.

2. Retransmission:

   • If errors are detected, the receiver requests the sender to retransmit the data.

Coding Techniques

Block Coding

Block coding involves dividing the message into blocks of fixed size, then adding redundant bits to each block for error detection or correction.

1. Error Detection:

   • The receiver verifies the integrity of the received block using redundant bits.
   • If errors are detected, the block is discarded or retransmitted.

2. Error Correction:

   • The receiver uses redundant bits to identify and correct errors in the block.

3. Hamming Distance:

   • Measures the minimum number of bit changes needed to convert one valid codeword to another.
   • A higher Hamming distance provides better error detection and correction.

Linear Block Codes

Linear block codes are a subset of block codes where the redundant bits are generated using linear equations.

1. Simple Parity-Check Code:

   • Adds one parity bit to the block.
   • Formula for parity:
     • Parity bit = (Sum of data bits) % 2
   • Example:
     • Data: 1011
     • Parity bit: 1
     • Transmitted block: 10111

2. Hamming Code:

   • Capable of correcting single-bit errors and detecting two-bit errors.
   • Formula for parity bits:
     • 2^p ≥ m + p + 1
     • p = number of parity bits
     • m = number of data bits

Cyclic Codes

Cyclic codes are block codes with a cyclic property, widely used in error detection.

1. Cyclic Redundancy Check (CRC):
   • Adds a checksum to the data based on polynomial division.
   • Steps:
     1. Data is represented as a binary polynomial.
     2. Divide by a generator polynomial (G).
     3. Append the remainder to the data.

Example: CRC Calculation

• Data: 11010011101100
• Generator: 1011
• Perform binary division:
  • Quotient: 1101001
  • Remainder: 100
• Transmitted frame: 11010011101100100

Checksum

The checksum is calculated by dividing the data into equal-sized segments, adding them, and appending the complement of the sum.

1. Checksum Calculation:
   • Divide data into segments.
   • Add all segments.
   • Take the one's complement of the sum.

Example: Checksum Calculation

• Data: 11100001 11001001
• Sum: 110100010
• Checksum: 00101101

Data Link Layer: Data Link Control and Media Access Control

The data link layer in the OSI model serves two primary functions: data link control and media access control (MAC). These functions ensure reliable communication between two adjacent nodes (node-to-node communication) and coordinate access to the shared medium when multiple devices are connected to the same physical link.

Data Link Control

Data link control deals with framing, flow control, error control, and the protocols needed for reliable communication between adjacent nodes. These mechanisms ensure smooth and reliable transmission of frames.

Framing

Framing organizes the stream of bits received from the physical layer into meaningful units called frames. It is essential for enabling synchronization and error detection.

Types of Framing

1. Fixed-Size Framing:

   • Frames have a predetermined, fixed size.
   • Example: ATM cells (53 bytes).
   • Advantage: Simplicity since no need for explicit frame boundaries.
   • Disadvantage: Wastage of bandwidth if the data does not fully utilize the frame size.

2. Variable-Size Framing:

   • Frames can have variable lengths, and special patterns or characters mark the start and end of the frames.

Character-Oriented Protocols (Byte Stuffing):

• Each frame starts and ends with specific characters.
• If the marker character appears in the data, it is escaped with an additional special character.
• Example:
  • Frame: [DLE STX Data DLE ETX]
  • If DLE appears in the data, byte stuffing adds an extra DLE:
    • [DLE STX Data DLE DLE ETX].

Bit-Oriented Protocols (Bit Stuffing):

• Frames are defined using a specific bit pattern, such as 01111110 in HDLC.
• If the bit pattern appears in the data, an additional 0 is stuffed after any sequence of five 1s.
• Example:
  • Data: 01111110
  • After bit stuffing: 011111010.

Flow and Error Control

Flow Control

Flow control ensures that the sender does not overwhelm the receiver with data faster than it can process. Two common flow control mechanisms are:

1. Stop-and-Wait Protocol:

   • The sender transmits one frame and waits for an acknowledgment (ACK) before sending the next.
   • Simple but inefficient for long transmission delays.

2. Sliding Window Protocol:

   • The sender can transmit multiple frames before needing an acknowledgment.
   • A window size determines the maximum number of outstanding frames.
   • Improves efficiency over stop-and-wait.

Error Control

Error control detects and corrects errors in frames. It includes techniques for error detection (e.g., parity checks, CRC) and error correction (e.g., retransmission).

Protocols for Noiseless and Noisy Channels

Protocols for Noiseless Channels

1. Simplest Protocol:

   • Assumes no errors or loss of frames.
   • The sender transmits data, and the receiver immediately accepts it.
   • Example:

    Sender: Sends Frame 1 → Receiver: Acknowledges Frame 1
   

2. Stop-and-Wait Protocol:

   • Sender waits for an acknowledgment (ACK) after each frame before sending the next.
   • This ensures orderly transmission but is inefficient for high-latency links.

Protocols for Noisy Channels

1. Stop-and-Wait ARQ (Automatic Repeat Request):

   • Combines flow control and error control.
   • Operation:
     • Sender transmits a frame and waits for an ACK.
     • If no ACK is received within a timeout period, the sender retransmits the frame.
   • Uses sequence numbers to distinguish retransmissions.

2. Go-Back-N ARQ:

   • The sender can transmit multiple frames within the window size before requiring an ACK.
   • If an error occurs in a frame, all subsequent frames in the window are retransmitted.
   • Advantages:
     • Efficient for reliable channels.
   • Disadvantages:
     • Wasteful when errors occur frequently.

3. Selective Repeat ARQ:

   • Only the frames that are received in error are retransmitted.
   • The receiver must have enough buffer space to store out-of-order frames.
   • Advantages:
     • Reduces retransmission overhead compared to Go-Back-N.
   • Disadvantages:
     • More complex implementation.

Sliding Window Protocols

Sliding window protocols are used for flow and error control in both Go-Back-N and Selective Repeat ARQ. The sender and receiver maintain a window that defines which frames are eligible for transmission or acknowledgment.

1. Sender Window:

   • Specifies the range of sequence numbers that can be sent before waiting for an acknowledgment.

2. Receiver Window:

   • Specifies the range of sequence numbers that the receiver is ready to accept.

3. Window Size:

   • Determines the maximum number of frames that can be sent or received without acknowledgment.

Example: Sliding Window Operation

• Window size = 3, Sequence numbers = 0, 1, 2, 3 (modulo-4):
  

   Frame 0 → Sent and Acknowledged
   Frame 1 → Sent
   Frame 2 → Sent
  

• If Frame 1 is lost:
  

   Frame 1 → Resent
   Frame 2 → Retained at Receiver
  

High-Level Data Link Control (HDLC)

HDLC is a bit-oriented protocol widely used in point-to-point and multipoint communication. It provides mechanisms for framing, error detection, and retransmission.

1. Frame Types:

   • Information Frames (I-frames): Carry user data.
   • Supervisory Frames (S-frames): Provide acknowledgment and flow control.
   • Unnumbered Frames (U-frames): Provide control information.

2. Frame Format:
   

   Flag | Address | Control | Data | FCS | Flag

• Flag: Delimits the start and end of the frame (01111110).
• Address: Identifies the destination node.
• Control: Indicates frame type and sequence numbers.
• FCS: Ensures frame integrity using CRC.

Point-to-Point Protocol (PPP)

PPP is a byte-oriented protocol used for point-to-point communication, such as between a computer and an ISP. It supports multiple network layer protocols (e.g., IP, IPv6) and provides authentication and error detection.

1. Frame Format:

   Flag | Address | Control | Protocol | Data | FCS | Flag

• Protocol: Specifies the type of payload (e.g., IPv4, IPv6).
• Data: Contains the encapsulated packet.

1. Features:
   • Supports authentication (e.g., PAP, CHAP).
   • Detects errors using a checksum.

By using the mechanisms and protocols described above, the data link layer ensures efficient and reliable communication between directly connected nodes in a network.

Multiple Access Control

Multiple access control methods enable efficient sharing of a communication medium among multiple devices. They prevent collisions, resolve conflicts, and ensure that data is transmitted successfully. These methods are broadly classified into random access, controlled access, and channelization techniques.

1. Random Access

In random access methods, devices transmit data without coordination, which can lead to collisions. These methods rely on techniques to detect or recover from collisions.

1.1 ALOHA

ALOHA is one of the simplest random access protocols.

Pure ALOHA

• Each device sends data whenever it has data to send, without waiting for any specific time.
• Collisions occur when two or more devices transmit at the same time.
• Vulnerable Time:
  • A frame can collide if another frame is transmitted within one frame time before or after its transmission starts.
  • Vulnerable time = 2 * Frame Time (T)
• Throughput:
  • The maximum throughput of Pure ALOHA is S = G * e^(-2G), where G is the average number of frames generated per frame time.
  • Maximum throughput is 18.4% when G = 0.5.

Slotted ALOHA

• Time is divided into slots equal to the frame transmission time.
• A device can only transmit at the beginning of a time slot, reducing the chance of collision.
• Vulnerable Time:
  • Vulnerable time = Frame Time (T)
• Throughput:
  • The maximum throughput of Slotted ALOHA is S = G * e^(-G).
  • Maximum throughput is 36.8% when G = 1.

1.2 Carrier Sense Multiple Access (CSMA)

CSMA improves ALOHA by sensing the channel before transmission. If the channel is busy, the device waits before trying to transmit.

Types of CSMA:

1. 1-persistent CSMA:

   • The device senses the channel and transmits immediately if the channel is idle.
   • If the channel is busy, the device waits until it becomes idle and then transmits.
   • High collision probability when multiple devices are waiting.

2. Non-persistent CSMA:

   • The device senses the channel, and if it is busy, it waits for a random time before checking again.
   • Reduces collision probability but increases delay.

3. p-persistent CSMA:

   • Used in slotted channels.
   • If the channel is idle, the device transmits with probability p or defers to the next slot with probability 1-p.

Vulnerable Time:

• Vulnerable time = Propagation Time (τ).

1.3 CSMA/CD (Collision Detection)

CSMA/CD enhances CSMA by detecting collisions during transmission and aborting the transmission to save time and bandwidth.

Steps:

1. Sense the channel before transmitting.
2. If the channel is idle, start transmitting.
3. If a collision is detected during transmission, stop immediately and send a jamming signal to notify others.
4. Wait for a random backoff time before retransmitting.

Applications:

• Widely used in Ethernet.

1.4 CSMA/CA (Collision Avoidance)

CSMA/CA avoids collisions by using acknowledgments and handshaking before data transmission. It is widely used in wireless networks, such as Wi-Fi.

Steps:

1. Sense the channel before transmission.
2. If the channel is idle, wait for a random backoff period.
3. Send a small control frame (RTS - Request to Send).
4. If the receiver responds with CTS (Clear to Send), transmit the data.
5. If no CTS is received, assume the channel is busy and retry later.

Vulnerable Time:

• Vulnerable time = 2 * Propagation Time (τ).

2. Controlled Access

In controlled access methods, devices coordinate their transmission to avoid collisions. These methods are more efficient but require additional overhead.

2.1 Reservation

• Time slots are reserved for devices that need to transmit data.
• Devices must send a request to reserve a time slot, which is granted by a central controller.

Applications:

• Satellite communication.

2.2 Polling

• A central controller (polling device) queries each device in turn to see if it has data to send.
• The device responds if it has data; otherwise, the controller moves to the next device.

Advantages:

• No collisions.
• Fair allocation of the channel.

Disadvantages:

• Delay due to waiting for the poll.
• Single point of failure (the controller).

2.3 Token Passing

• A special control frame, called a token, circulates among the devices.
• A device can only transmit data if it has the token.
• After transmission, the token is passed to the next device.

Advantages:

• No collisions.
• Efficient use of the channel.

Disadvantages:

• Token loss requires reinitialization.
• Delay increases with the number of devices.

3. Channelization

Channelization is a technique where the available bandwidth is divided into separate channels, and each device is assigned a channel.

3.1 Frequency Division Multiple Access (FDMA)

• The bandwidth is divided into non-overlapping frequency bands, and each device is assigned a unique band.
• Devices transmit simultaneously but use different frequencies.
• Applications: Traditional radio and TV broadcasting.

Advantages:

• Simple and effective for analog communication.
• No collisions.

Disadvantages:

• Inefficient if a channel is idle.
• Requires guard bands to avoid interference.

3.2 Time Division Multiple Access (TDMA)

• Time is divided into slots, and each device is assigned a time slot.
• Devices take turns transmitting data during their assigned slots.
• Applications: Cellular networks (2G, 3G).

Advantages:

• Efficient for digital communication.
• Avoids collisions.

Disadvantages:

• Synchronization is required.
• Idle slots waste bandwidth.

3.3 Code Division Multiple Access (CDMA)

• All devices share the same frequency and time, but each device is assigned a unique code.
• Data is encoded using the assigned code, allowing multiple devices to transmit simultaneously without interference.
• Applications: Cellular networks (3G).

Advantages:

• High bandwidth efficiency.
• Resistant to interference and eavesdropping.

Disadvantages:

• Complex implementation.
• Requires precise power control to avoid near-far problem.

By combining random access, controlled access, and channelization techniques, modern networks ensure efficient, reliable, and scalable communication among multiple devices. Each technique is suited to specific network requirements and traffic patterns.

Wired LANs: Ethernet

Ethernet is one of the most widely used wired LAN technologies, standardized under the IEEE 802.3 standard. It operates in the data link and physical layers of the OSI model and facilitates efficient communication over a shared medium.

IEEE Standards

The IEEE has standardized Ethernet as part of its 802 project, subdividing the data link layer into two sublayers:

1. Logical Link Control (LLC):

   • Defined under IEEE 802.2.
   • Responsible for flow and error control.
   • Provides an interface to the network layer, ensuring reliable communication.

2. Media Access Control (MAC):

   • Defined under IEEE 802.3.
   • Manages access to the physical medium and handles frame transmission and reception.
   • Implements protocols to handle collisions (e.g., CSMA/CD in traditional Ethernet).

Ethernet MAC Sublayer

The MAC sublayer is central to Ethernet's operation and performs the following functions:

1. Framing:

   • Encapsulates network layer data into Ethernet frames.
   • Adds a header and trailer for addressing and error detection.

2. Media Access Control:

   • Regulates access to the physical medium.
   • Uses mechanisms like CSMA/CD for collision detection in half-duplex systems.

3. Error Detection:

   • Includes a Frame Check Sequence (FCS) in the trailer for error detection.

Ethernet Frame Format

Ethernet uses a well-defined frame format to ensure reliable communication. The structure of an Ethernet frame is as follows:

Frame Length:

• Minimum Length: 64 bytes (46-byte payload + headers and FCS).
• Maximum Length: 1518 bytes (1500-byte payload + headers and FCS).
• Frames smaller than 64 bytes or larger than 1518 bytes are considered invalid.

Addressing and NIC

Ethernet relies on MAC addressing and Network Interface Cards (NICs) for communication.

MAC Address:

• A unique 48-bit (6-byte) hardware address assigned to each NIC.
• Represented in hexadecimal format, e.g., 00:1A:2B:3C:4D:5E.
• The first 24 bits represent the Organizationally Unique Identifier (OUI), identifying the manufacturer, while the last 24 bits are unique to the device.

Types of MAC Addresses:

1. Unicast: Identifies a single device.
2. Multicast: Targets a group of devices.
3. Broadcast: Targets all devices on the network (FF:FF:FF:FF:FF:FF).

NIC (Network Interface Card):

• A hardware device that connects a computer to a network.
• Responsible for managing Ethernet frames, MAC addressing, and interfacing with the physical medium.
• Often integrated into motherboards or provided as an expansion card.

Physical Layer

Ethernet's physical layer is defined by the IEEE 802.3 standard and includes various technologies to support different speeds and media types.

Standards and Speeds:

• 10 Mbps Ethernet: Uses coaxial cable (10BASE2, 10BASE5).
• 100 Mbps Fast Ethernet: Typically uses twisted-pair cabling (100BASE-TX).
• 1 Gbps Gigabit Ethernet: Uses fiber optic or twisted-pair cabling (1000BASE-T, 1000BASE-X).
• 10 Gbps Ethernet and beyond: Primarily uses fiber optics (10GBASE-SR, 10GBASE-LR).

Ethernet's combination of simplicity, scalability, and efficiency has made it the de facto standard for wired LANs worldwide. Its evolution continues to adapt to the increasing demands of modern networks.