Data Link Layer: Frame Structure, MAC, LLC, Error Control, Flow Control, Switching

1. Overview of the Data Link Layer

The Data Link Layer (Layer 2 of the OSI model) sits between the Physical Layer and the Network Layer. Its primary responsibilities are:

The Data Link Layer is crucial for ensuring that packets sent by the Network Layer arrive intact and in order on the receiving end.

2. Frame Structure

A typical Ethernet frame (IEEE 802.3) consists of:

+----------------+----------------+----------------+----------------+----------------+
| Preamble (7B)  | SFD (1B)       | Destination MAC| Source MAC     | EtherType      |
+----------------+----------------+----------------+----------------+----------------+
| Payload (46–1500B) | CRC (4B) |                                 |
+----------------+----------------+----------------+----------------+----------------+

• Preamble & SFD: 7 bytes of alternating 1/0 bits followed by a Start Frame Delimiter (0xAB) to allow the receiver to synchronize.
• Destination & Source MAC: 48‑bit addresses; broadcast address is FF:FF:FF:FF:FF:FF.
• EtherType: Identifies the upper‑layer protocol (e.g., 0x0800 for IPv4).
• Payload: Encapsulated Network Layer packet. Minimum 46 bytes; padded if smaller.
• CRC: 32‑bit cyclic redundancy check for error detection.

Example: Ethernet Frame Construction

Suppose an IPv4 packet of 100 bytes is to be transmitted from host A (MAC = 00:11:22:33:44:55) to host B (MAC = 66:77:88:99:AA:BB).

1. Preamble: 7 bytes of 0xAA.
2. SFD: 0xAB.
3. Destination MAC: 66:77:88:99:AA:BB.
4. Source MAC: 00:11:22:33:44:55.
5. EtherType: 0x0800.
6. Payload: 100‑byte IPv4 packet.
7. CRC: Calculated over bytes 3–(n‑4).

The resulting frame length = 7 + 1 + 6 + 6 + 2 + 100 + 4 = 126 bytes.

3. Logical Link Control (LLC)

LLC is the upper sublayer of the Data Link Layer. It provides a common interface to the Network Layer and manages multiple network protocols over a single link.

LLC Types

LLC frames contain a DSAP (Destination Service Access Point) and SSAP (Source Service Access Point) to identify the upper‑layer protocol. For example, DSAP = 0x06 indicates IP.

4. Media Access Control (MAC)

MAC sublayer controls how devices on a shared medium gain access to the channel.

Common MAC Protocols

Collision Detection Example (CSMA/CD)

1. Device senses idle medium.
2. Begins transmission.
3. While transmitting, it monitors the line.
4. If a collision is detected (signal differs from transmitted bits), it stops, sends a jam signal, and waits a random back‑off time before retrying.

5. Error Detection & Correction

5.1 Cyclic Redundancy Check (CRC)

• Uses a generator polynomial (e.g., G(x) = x^32 + x^26 + x^23 + … + 1).
• Sender appends 32‑bit CRC to frame; receiver recomputes CRC and compares.
• Probability of undetected error ≈ 1/2^32.

5.2 Hamming Code (Error Correction)

Worked Example: Data 01100111

1. Data bits: d1 d2 d3 d4 d5 d6 d7 = 0 1 1 0 0 1 1
2. Parity positions: p1, p2, p4 (powers of 2).
3. Place data:

   Position: 1 2 3 4 5 6 7 8
   Bits:     p1 p2 d1 p4 d2 d3 d4 d5
   

   But for 7‑bit data we need 3 parity bits → 10‑bit codeword.
4. Compute parity:
   • p1 covers bits 1,3,5,7,9 → parity of 0,1,0,1,?
   • p2 covers bits 2,3,6,7,10 → parity of 0,1,1,1,?
   • p4 covers bits 4,5,6,7 → parity of 0,0,1,1.
     After calculation, we obtain parity bits p1=0, p2=1, p4=1.
5. Final codeword: 0 1 0 1 0 1 1 1 0 1 (10 bits).

If a single bit error occurs, the receiver recomputes parity and identifies the erroneous position via the syndrome.

5.3 Automatic Repeat reQuest (ARQ)

• Stop‑and‑Wait: Sender transmits one frame, waits for ACK/NACK.
• Sliding Window: Sender can transmit multiple frames up to a window size; receiver acknowledges cumulatively.

6. Flow Control

7. Switching Techniques

7.1 Store‑and‑Forward

• Switch receives entire frame, checks CRC, then forwards.
• Pros: error detection before forwarding.
• Cons: higher latency, requires buffer memory.

7.2 Cut‑Through

• Switch forwards frame as soon as destination MAC is read (typically after the header).
• Pros: lower latency.
• Cons: errors may propagate; no CRC check before forwarding.

7.3 Fragmentation & Reassembly

• In some protocols (e.g., Frame Relay), frames may be fragmented to fit into smaller cells (1520 B).
• The switch reassembles them before forwarding.

8. Link Layer Protocols

8.1 Ethernet (IEEE 802.3)

• Topology: Bus or star (via switches).
• Speed: 10 Mbps, 100 Mbps, 1 Gbps, 10 Gbps.
• Addressing: 48‑bit MAC.
• Switching: Store‑and‑forward, cut‑through.

8.2 Point‑to‑Point Protocol (PPP)

PPP is used over serial links (e.g., dial‑up, ISDN). It provides:

PPP Link Setup Process

1. LCP Configure-Request: Sender proposes options.
2. LCP Configure-Ack: Receiver accepts or rejects.
3. LCP Terminate-Request: Either side can terminate.
4. NCP: After LCP is established, NCP negotiates IP parameters.

8.3 High‑Level Data Link Control (HDLC)

HDLC is a bit‑stream protocol providing:

• Frame Types: Information, Supervisory, Unnumbered.
• Bit Stuffing: Prevents accidental flag sequences.
• Sequence Numbers: For reliable transmission.
• Error Detection: CRC.

HDLC is the basis for PPP and other protocols.

8.4 Frame Relay

• Cell‑Based: Fixed 1520‑byte cells.
• Virtual Circuits: Permanent (PVC) or switched (SVC).
• No error correction: Relies on higher layers.

9. Comparison of Key Protocols

10. Applications of the Data Link Layer

11. Exam Tip

• Know the layering: Distinguish between LLC and MAC, and understand where each protocol fits.
• Memorize key frame fields: Preamble, SFD, MAC addresses, EtherType, CRC.
• Be able to compute CRC and Hamming codes: Practice with small data sets.
• Understand ARQ mechanisms: Stop‑and‑Wait vs. Sliding Window; write the sequence of events for a retransmission scenario.
• Compare protocols: Use a table to contrast Ethernet, PPP, HDLC, and Frame Relay on parameters like addressing, error handling, and typical speeds.
• Link‑setup steps: For PPP, list the LCP and NCP negotiation sequence.
• Common exam questions: “Explain the difference between link‑state and distance‑vector routing” (though a routing topic, it often appears in the context of the Data Link Layer’s role in routing protocols).
• Practice tracing: Draw an ASCII diagram of an Ethernet frame and a PPP link‑setup sequence; annotate each step.

By focusing on these points and practicing calculations, you’ll be well‑prepared for the Data Link Layer section of the TU Computer Networks exam.