Unit-3 Data_Link_Layer

Data Link Layer: 

In the OSI (Open Systems Interconnection) model, the Data Link Layer is the 2nd layer from the bottom and the 4th layer from the top. This layer is responsible for the communication between directly connected devices, known as adjacent nodes, and facilitates the transfer of data across individual links between these nodes. A link refers to the communication channel that directly connects two adjacent nodes.

The primary role of the Data Link Layer is to ensure that data (datagrams) are moved across individual links between the source and destination, handling a variety of tasks such as error detection, retransmission, flow control, and random access.

---

Key Functions of the Data Link Layer

1. Framing and Link Access:
   Data Link Layer protocols encapsulate each network layer datagram inside a link layer frame before it is transmitted over the link. A frame contains a data field, which holds the network layer datagram, and additional control information. It also specifies the structure of the frame and determines how the frame is accessed by the channel for transmission.

2. Reliable Delivery:
   This layer can provide a reliable delivery service, ensuring that datagrams are transmitted without errors. This is achieved through retransmissions and acknowledgements between nodes. Reliable delivery is particularly useful for links with higher error rates, as it helps correct errors locally, without requiring the entire data packet to be retransmitted from the source.

3. Flow Control:
   To prevent buffer overflow at the receiving node, the Data Link Layer implements flow control. This mechanism prevents the sender from overwhelming the receiver with data by pacing the transmission according to the receiver’s capacity.

4. Error Detection:
   Errors can occur during data transmission due to signal degradation (attenuation) or noise. The Data Link Layer employs error detection mechanisms by adding error-detecting bits to the frame. The receiving node can then perform checks to detect any errors in the received frame.

5. Error Correction:
   Unlike error detection, error correction enables the receiving node to both identify errors and correct them without needing a retransmission. This helps improve the efficiency of data transmission in unreliable environments.

6. Half-Duplex and Full-Duplex Communication:

   • Full-Duplex: Both nodes can transmit data simultaneously over the link.
   • Half-Duplex: Only one node can transmit at a time, requiring nodes to take turns.

---

Data Link Layer Protocols

Common protocols used in the Data Link Layer include:

• Ethernet: Widely used in local area networks (LANs).
• Token Ring: Utilizes a token-passing method for communication.
• FDDI (Fiber Distributed Data Interface): Primarily used in larger networks like metropolitan area networks (MANs).
• PPP (Point-to-Point Protocol): Often used in dial-up connections and point-to-point links.

---

Example of Protocol Handling in a Data Path

Consider a situation where a datagram is transferred from a source node to a destination across multiple links. On the first link, the datagram might be handled by the Ethernet protocol, while on the next link, the datagram could be processed using the PPP protocol. The flexibility of the Data Link Layer allows different protocols to handle the datagram as it moves across various links in the transmission path.

---

Services Provided by the Data Link Layer:

• Error-Free Delivery: The layer ensures datagrams are transmitted without error.
• Error Detection and Correction: Adds error-checking bits to detect and potentially correct transmission errors.
• Flow Control: Prevents buffer overflow by regulating the speed at which data is sent.
• Framing: Encapsulates datagrams in link layer frames for transmission.
• Duplexing: Supports both full and half-duplex transmission modes depending on the link configuration.

Error Detection: 

When data is transmitted from one device to another, errors can occur due to various factors such as noise, interference, or signal degradation. These errors result in differences between the sent and received data. Error detection techniques are used to identify these errors, ensuring the integrity of the transmitted data.

---

Types of Errors

1. Single-Bit Error:
   A single-bit error occurs when only one bit in the data unit is altered—i.e., a 0 is changed to 1 or vice versa. This type of error is more likely to occur in parallel data transmission, where each wire transmits a separate bit. For example, if eight wires are used to send a byte of data, a noise on one wire may corrupt just one bit.

   • Example:
     Sent data: 01100110
     Received data: 01100100 (third bit from the left changed from 1 to 0)

2. Burst Error:
   A burst error occurs when two or more bits in the data unit are altered. The burst length is determined from the first to the last corrupted bit. Burst errors are more common in serial data transmission, where bits are transmitted sequentially.

   • Example:
     Sent data: 01100110
     Received data: 11101100 (multiple bits altered due to longer noise duration)

---

Error Detection Techniques

Several techniques are used to detect errors in transmitted data. These techniques add redundancy or extra bits to the data to enable error detection.

---

1. Single Parity Check

In this technique, a parity bit is added to the data unit. The parity bit ensures that the total number of 1s in the data (including the parity bit) is even or odd, depending on the parity used (even or odd parity). If the received data does not match the expected parity, an error is detected.

• Example (Even Parity):
  • Sent Data: 1011010 (original 7-bit data)
  • Parity Bit: 1 (to make the number of 1s even)
  • Sent Data (with parity): 10110101
  • Received Data: 10110111
  • Error Detected: The received data has an odd number of 1s, indicating a transmission error.

Drawbacks:

• Can only detect single-bit errors.
• Cannot detect two-bit errors or errors in which bits are flipped in such a way that parity remains unchanged.

---

2. Two-Dimensional Parity Check

This technique enhances single parity by organizing data into a matrix (rows and columns). Parity bits are calculated for both rows and columns, providing an additional layer of error detection. This method is better suited to detect and locate errors across multiple bits.

• Example:
  Consider the following 4x4 matrix with even parity:

  Data	Parity (Row)
  1101	0
  1010	1
  0110	1
  0001	1

  The column parity is:
  1, 1, 1, 0

  If an error occurs during transmission and a bit is altered (e.g., in the third row and second column), the receiver will detect an inconsistency in both the row and column parity.

Drawbacks:

• Unable to detect some burst errors where multiple bits in different positions are flipped.

---

3. Checksum

The checksum method is based on summing the data units and sending the sum along with the data. At the receiving end, the same summing process is repeated. If the calculated sum at the receiver matches the transmitted checksum, the data is considered error-free. If not, an error is detected.

• Example:

  • Sent Data: 11010101 00101010 11110000 (3 blocks of 8 bits)

  • Checksum Calculation:
    Add all the blocks using one's complement arithmetic:
    11010101 + 00101010 + 11110000 = 101001111
    Take one's complement: 01011000
    This is the checksum sent with the data.

  • Received Data: 11010101 00101010 11110000 and checksum: 01011000

  • The receiver performs the same addition and compares the result. If the result is zero, the data is accepted. Otherwise, an error is detected.

Drawbacks:

• May fail to detect burst errors that result in identical checksums despite corrupted data.

---

4. Cyclic Redundancy Check (CRC)

CRC is a more sophisticated error detection technique that uses binary division. The sender appends a predetermined number of 0s (equal to the number of bits in a divisor minus one) to the data and then divides the data by a predefined divisor. The remainder, called the CRC remainder, is sent with the data. The receiver performs the same division, and if the remainder matches, the data is considered valid.

• Example:

  • Original Data: 11100
  • Divisor: 1001
  • Step 1: Append three 0s to the data: 11100000
  • Step 2: Perform binary division using the divisor. The CRC remainder is 111.
  • Step 3: The final transmitted data is 11100111 (original data plus the remainder).

  At the Receiver:

  • The receiver divides 11100111 by 1001.
  • If the remainder is 0, the data is accepted.
  • If the remainder is not 0, an error is detected.

---

 Example of Error Detection Techniques

1. Single Parity Check

   • Sender: Adds a parity bit to make the number of 1s even/odd.
   • Receiver: Recalculates parity from received bits and checks for mismatch.
   • Drawback: Detects only single-bit errors.

2. Two-Dimensional Parity Check

   • Sender: Adds parity bits for both rows and columns of data.
   • Receiver: Recalculates row and column parity, detects errors if mismatched.
   • Drawback: Misses some complex errors involving multiple bits.

3. Checksum

   • Sender: Sums data blocks and sends the sum (checksum).
   • Receiver: Repeats summing process, compares calculated sum with transmitted checksum.
   • Drawback: Vulnerable to undetected burst errors.

4. Cyclic Redundancy Check (CRC)

   • Sender: Divides data with a divisor, appends the remainder (CRC).
   • Receiver: Repeats division, compares remainder.
   • Drawback: None for small transmission errors, widely used in real-world applications.

Error Correction:

Error correction codes (ECC) are essential in ensuring the accurate transmission of data by detecting and correcting errors that occur during data transfer from sender to receiver. These codes enable reliable communication, especially over noisy or unreliable channels.

There are two primary methods for handling error correction:

1. Backward Error Correction:

   • Once the receiver detects an error, it requests the sender to retransmit the entire data unit. This method works well for non-real-time applications where delays in retransmission can be tolerated.

2. Forward Error Correction (FEC):

   • The receiver uses an error-correcting code that automatically detects and corrects errors without requiring retransmission. FEC is commonly used in real-time systems where retransmissions are undesirable.

A single additional bit can detect the presence of an error but is insufficient for error correction. To correct errors, we must know the exact position of the erroneous bit. For example, in a scenario with a single-bit error, an error correction code can identify which one of the transmitted bits is incorrect.

---

Calculating Redundant Bits

To correct errors, we add redundant bits to the data. The number of redundant bits required depends on the total number of data bits, and we can calculate it using the following formula:

$$2^r \geq d + r + 1$$

Where:

• d = number of data bits
• r = number of redundant bits

For example, if the value of d is 4, the smallest value of r that satisfies the equation is 3.

---

Hamming Code: Error Correction Technique

Hamming code, developed by R.W. Hamming, is an error correction code that uses both data and redundant bits to detect and correct errors. This code can be applied to data units of any length and allows us to identify the exact position of an error.

Parity Bits

• Parity bit: A bit added to the data to ensure that the number of 1s is either even (even parity) or odd (odd parity).
  • Even parity: If the total number of 1s is even, the parity bit is set to 0; if odd, the parity bit is set to 1.
  • Odd parity: If the total number of 1s is even, the parity bit is set to 1; if odd, the parity bit is set to 0.

Hamming Code Algorithm

The Hamming code algorithm consists of the following steps:

1. Add r redundant bits to the d data bits, forming a total of d + r bits.
2. Assign decimal positions to each bit in the data unit.
3. Place redundant bits in positions that correspond to powers of 2 (i.e., positions 1, 2, 4, 8, ...).
4. Calculate parity values for the redundant bits by checking specific bit positions.
5. At the receiving end, recalculate the parity bits and identify any errors using the binary values of the redundant bits.

---

Hamming Code Example

Let's walk through an example to better understand Hamming code.

Original Data

Suppose the original data is 1010 (4 data bits).

• Total number of data bits (d) = 4
• Number of redundant bits (r) is calculated as:

$$2^r \geq d + r + 1 \quad \Rightarrow \quad 2^3 \geq 4 + 3 + 1 \quad \Rightarrow \quad r = 3$$

Thus, we need 3 redundant bits.

• Total number of bits = d + r = 4 + 3 = 7

Positioning the Redundant Bits

The redundant bits are represented as r1, r2, and r4. These bits are placed in positions corresponding to powers of 2:

• r1: Position 1
• r2: Position 2
• r4: Position 4

Thus, the 7-bit sequence will be: _ _ _ 1 _ 0 1 0, where the data bits are placed in positions 3, 5, 6, and 7.

Determining the Parity Bits

Next, we calculate the parity bits (r1, r2, and r4) based on the bit positions:

1. r1: Checks positions 1, 3, 5, and 7.
   • Bits at these positions: _ 1 0 0
   • Number of 1s = 1 (odd), so r1 = 1 (for even parity).
2. r2: Checks positions 2, 3, 6, and 7.
   • Bits at these positions: _ 1 0 0
   • Number of 1s = 1 (odd), so r2 = 1 (for even parity).
3. r4: Checks positions 4, 5, 6, and 7.
   • Bits at these positions: _ 1 0 0
   • Number of 1s = 1 (odd), so r4 = 1 (for even parity).

Thus, the transmitted 7-bit sequence is 1111010.

---

Error Detection and Correction Example

Suppose that during transmission, the 4th bit is changed from 0 to 1 at the receiving end, resulting in the received sequence: 1111110.

Recalculating the Parity Bits

At the receiver, we recalculate the parity bits to detect and correct any errors:

1. r1: Checks positions 1, 3, 5, and 7.

   • Bits at these positions: 1 1 1 0
   • Number of 1s = 3 (odd), so r1 = 1.

2. r2: Checks positions 2, 3, 6, and 7.

   • Bits at these positions: 1 1 1 0
   • Number of 1s = 3 (odd), so r2 = 1.

3. r4: Checks positions 4, 5, 6, and 7.

   • Bits at these positions: 1 1 1 0
   • Number of 1s = 3 (odd), so r4 = 1.

The recalculated parity bits form the binary number 111, which is 7 in decimal. This means the error occurred at position 7, and the bit value must be changed from 1 to 0 to correct the error.

---

1. Overview of Data Link Controls:

The Data Link Layer (DLL) provides the crucial service of enabling reliable data transfer over a physical medium. It helps avoid issues like data loss and collisions that may occur during simultaneous transmission, especially in half-duplex communication, where only one device can transmit data at a time. If both devices try to transmit data at the same time, a collision will occur, leading to information loss. The Data Link Layer helps to coordinate transmission and prevent such problems.

The Data Link Layer primarily serves three key functions:

1. Line Discipline: It determines which device can send data and when it can be sent.
2. Flow Control: It prevents the receiver from becoming overwhelmed by too much incoming data.
3. Error Control: It ensures that the received data is free of errors and requests retransmission if necessary.

---

2. Line Discipline:

Line discipline is responsible for managing the coordination between two devices during data transmission. It ensures that only one device transmits data at any given time, and the receiver is ready to accept it. It can be achieved through two primary methods: ENQ/ACK and Poll/Select.

---

2.1 ENQ/ACK (Enquiry/Acknowledgement):

The ENQ/ACK method works in environments where there is no risk of the wrong receiver being on the link (i.e., a dedicated point-to-point link). Here, the sender and receiver are the only devices involved, so they can manage transmission with minimal control overhead.

• Process:
  1. ENQ Frame: The sender starts by sending an Enquiry (ENQ) frame to check if the receiver is available.
  2. Receiver Response: The receiver can respond in three ways:
     • Positive Acknowledgement (ACK): The receiver is ready to accept the transmission.
     • Negative Acknowledgement (NACK): The receiver is not ready to receive data.
     • No Response: If no response is received, the sender assumes the ENQ was lost and retries up to three times.
  3. Transmission: If the response is ACK, the sender sends the data frames. After the transmission, the sender sends an End-of-Transmission (EOT) frame to signal the end of the session.
  4. Error Handling: If NACK is received, the sender retries after a delay, or if no response is received after multiple attempts, the session is aborted.

---

2.2 Poll/Select Method:

The Poll/Select method is suitable for multi-device topologies, such as star or bus networks, where one device is the primary device (master), and the others are secondary devices (slaves).

• Poll/Select Process:

  1. Primary Device: The primary device controls the communication channel.
  2. Polling: When the primary device wants to receive data, it sends a poll to each secondary device in turn, asking whether it has data to send.
  3. Select: When the primary device wants to send data, it issues a select command to the intended secondary device, asking it to get ready to receive the data.

• Polling in Detail:

  • The primary device asks each secondary device, one by one, whether it has any data to send.
  • If a secondary device has data, it responds with an ACK, and transmission begins.
  • If a secondary device has no data, it responds with a NACK, and the primary moves to the next device.

• Selecting in Detail:

  • The primary device selects a secondary device and sends a Select (SEL) frame, which contains the address of the intended receiver.
  • The selected device responds with an ACK if it’s ready to receive the transmission.
  • Once ready, the primary device sends the data frames.

---

3. Flow Control:

Flow control ensures that the sender does not overwhelm the receiver by sending data faster than the receiver can process and store. This prevents buffer overflow on the receiver’s side.

Two primary methods of flow control are:

---

3.1 Stop-and-Wait Flow Control:

In this method:

• The sender transmits one frame at a time and waits for an acknowledgement before sending the next one.
• Advantage: Simplicity, as it guarantees that the sender doesn’t overload the receiver.
• Disadvantage: Inefficiency due to idle time while waiting for an ACK.

Process:

1. The sender sends a frame.
2. It then waits for an ACK before sending the next frame.
3. If no ACK is received, the frame is retransmitted after a timeout.

---

3.2 Sliding Window Flow Control:

This method allows the sender to transmit multiple frames before receiving an ACK, making more efficient use of the network.

• Window Size: The size of the window (number of frames that can be sent without ACK) is defined as n-1 frames.
• ACK Efficiency: The receiver can acknowledge multiple frames in one ACK, increasing efficiency.

Sliding Window Process:

1. Sender Window: The sender can send frames until the window is full. The window slides forward as ACKs are received.
2. Receiver Window: The receiver has a buffer window that represents the number of frames it can accept. As frames are received, the window shrinks.
3. ACKs: When the receiver sends an ACK, it acknowledges the next expected frame number, signaling that all previous frames have been received.

---

4. Error Control:

Error control ensures that the data reaches the destination correctly. It involves both error detection and retransmission in case of lost or corrupted data.

4.1 Stop-and-Wait ARQ (Automatic Repeat Request):

• The sender waits for an ACK after each frame.
• If an error is detected, the receiver sends a NAK, and the sender retransmits the frame.
• The sender also sets a timer for each frame sent. If the timer expires without receiving an ACK, the sender assumes the frame was lost and retransmits.

---

4.2 Sliding Window ARQ:

In this case, multiple frames can be sent before receiving an ACK, and if an error is detected, only the specific frame with the error is retransmitted.

There are two primary sliding window ARQ protocols:

---

4.2.1 Go-Back-N ARQ:

• If an error occurs in a frame, the receiver sends a NAK for that frame, and the sender retransmits that frame and all subsequent frames.
• This approach can waste bandwidth by retransmitting already correct frames.

---

4.2.2 Selective Repeat ARQ:

• Only the specific erroneous frame is retransmitted.
• The receiver holds out-of-order frames in a buffer until the correct frame is received.
• This method is more efficient but requires more complex receiver logic.

---

Flow Diagram for Data Link Controls

Here’s an enhanced flow diagram that details the entire process for Line Discipline, Flow Control, and Error Control:

                                +-----------------------------------------+
                                |         Data Link Controls              |
                                +-----------------------------------------+
                                               |
                +------------------------------+------------------------------+
                |                                                             |
       +-------------------------+                                  +-------------------------+
       |    Line Discipline       |                                  |      Flow Control       |
       +-------------------------+                                  +-------------------------+
                |                                                             |
      +------------------+-----------------+                     +----------------+------------------+
      |          ENQ/ACK             |        Poll/Select        |  Stop-and-Wait  |  Sliding Window   |
      +------------------------------+---------------------------+----------------+------------------+
                |                               |                                |                         |
     +------------------+        +-------------------------+          +------------------+   +----------------------+
     | ENQ/ACK Process   |        | Poll/Select Process     |          | Frame-by-Frame   |   | Continuous Frames     |
     +-------------------+        +-------------------------+          | Transmission     |   | Transmission (ACK)    |
                                                |
                                  +-----------------------------+              
                                  | Error Control                |              
                                  +-----------------------------+              
                                                |              
                 +-----------------------------------------------+              
                 |                                               |              
+--------------------------+                         +--------------------------+ 
| Stop-and-Wait ARQ         |                         | Sliding Window ARQ       | 
+--------------------------+                         +--------------------------+ 
                 |                                               |              
+-------------------------+        +------------------------+    +----------------------+              
| Retransmit Damaged Frame |        | Go-Back-N ARQ Process  |    | Selective Repeat ARQ  |              
+-------------------------+        +------------------------+    +----------------------+