Unit 3: DATA LINK LAYER & MAC SUBLAYER

1. Data Link Layer (DLL) Design Issues

The Data Link Layer is responsible for the reliable transfer of data frames from one node to the next connected node over the physical layer.

A. Services Provided to the Network Layer

The DLL acts as a service interface to the Network Layer.

1. Unacknowledged Connectionless Service:
   • No logical connection established.
   • No error recovery or acknowledgment.
   • Use case: Reliable media (fiber), voice traffic (where delay is worse than data loss), or Ethernet.
2. Acknowledged Connectionless Service:
   • No logical connection, but every frame is acknowledged.
   • If a frame doesn't arrive, the sender resends it.
   • Use case: Unreliable channels (WiFi).
3. Acknowledged Connection-Oriented Service:
   • Connection established before data transfer.
   • Frames are numbered, guaranteed delivery, and received in order.

B. Framing

The Physical layer transmits a raw bit stream. The DLL must break this stream into discrete units called frames.

• Character Count: Header specifies the number of characters in the frame. (Risk: If the count bit is corrupted, synchronization is lost).
• Byte Stuffing (Character Stuffing): Uses special "FLAG" bytes to mark start/end. If data contains the FLAG byte, an "ESCAPE" byte is inserted (stuffed) before it.
• Bit Stuffing: Uses a specific bit pattern (e.g., 01111110) as a flag. If the sender sees five consecutive 1s in the data, it inserts a 0 to prevent confusion with the flag.
• Physical Layer Coding Violations: Uses invalid signal encoding (e.g., high-high or low-low in Manchester encoding) to delimit frames.

C. Error Control

Ensures the receiver informs the sender of frames that arrive damaged or are lost.

• Acknowledgments (ACK): Receiver confirms safe arrival.
• Negative Acknowledgments (NAK): Receiver reports a damaged frame.
• Timers: Sender retransmits if no ACK is received within a specific time.

D. Flow Control

Prevents a fast sender from drowning a slow receiver in data.

• Feedback-based: Receiver sends permission to send more data.
• Rate-based: Protocol has a built-in limit on data transmission rate.

2. Error Detection and Correction

Noise on the physical link can flip bits (0 to 1 or 1 to 0).

A. Parity Check

The simplest error detection method. A "parity bit" is appended to the data.

• Even Parity: Total number of 1s (including parity bit) must be even.
• Odd Parity: Total number of 1s must be odd.
• Limitation: Can only detect an odd number of bit errors (1, 3, 5...). If two bits flip, the parity remains correct, and the error goes undetected.

B. Checksum

Used widely in TCP/IP.

1. Data is divided into fixed-size segments (e.g., 16-bit words).
2. The sender sums these segments using 1s complement arithmetic.
3. The result is complemented (bits flipped) and appended as the Checksum.
4. Receiver: Sums all segments + Checksum. If result is all 1s (in 1s complement implies 0), data is accepted; otherwise, rejected.

C. Cyclic Redundancy Check (CRC)

The most robust error detection used in Ethernet and WiFi. It relies on polynomial division.

• Mechanism:
  1. Data is viewed as a polynomial .
  2. A Generator Polynomial is agreed upon (must detect specific errors).
  3. zero bits are appended to the data frame (where is the degree of ).
  4. Binary division is performed using Modulo-2 Arithmetic (XOR, no carries/borrows).
  5. The Remainder is the CRC; it replaces the zeros.
• Receiver: Divides incoming frame by . If remainder is 0, frame is valid.

D. Hamming Code (Error Correction)

Detects and corrects single-bit errors by adding redundant bits at specific positions.

• Redundancy Formula: (where = data bits, = redundant bits).
• Bit Placement: Redundant bits are placed at positions that are powers of 2 (1, 2, 4, 8...).
• Calculation: Each parity bit covers specific bit positions based on binary representation (e.g., Parity bit 1 checks positions 1, 3, 5, 7...).
• Hamming Distance: The number of bit positions in which two codewords differ. To correct errors, a distance of is required.

3. Elementary Data Link Protocols

These protocols handle flow and error control.

A. Utopian Simplex Protocol

• Assumptions: Data moves only one way. Channel is error-free. Receiver has infinite buffer space.
• Logic: Sender blasts data as fast as possible. No ACKs needed. (Theoretical only).

B. Simplex Stop-and-Wait Protocol

• Scenario: Noisy channel, finite buffer.
• Logic:
  1. Sender transmits one frame.
  2. Sender stops and waits for an ACK from receiver.
  3. Once ACK is received, sender transmits next frame.
• Handling Errors:
  • Timers: If frame (or ACK) is lost, sender times out and retransmits.
  • Sequence Numbers: To distinguish between a new frame and a retransmission (in case ACK was delayed, not lost), frames are numbered (0, 1).

4. The MAC Sublayer (Medium Access Control)

In broadcast networks (bus, wireless), multiple nodes share a single channel. The MAC sublayer determines who gets to transmit next to avoid collisions.

A. Random Access Protocols

No station is superior; no scheduled time. Contention-based.

1. ALOHA

• Pure ALOHA:
  • Users transmit whenever they have data.
  • If collision occurs (no ACK received), wait a random time and retransmit.
  • Efficiency: Very low (~18.4%).
• Slotted ALOHA:
  • Time is divided into discrete slots.
  • Users can only start transmitting at the beginning of a slot.
  • Reduces collision probability.
  • Efficiency: Double that of pure ALOHA (~36.8%).

2. CSMA (Carrier Sense Multiple Access)

"Listen before you talk."

• Mechanism: Station listens to the channel (Carrier Sense).
• Persistence Strategies:
  • 1-persistent: If idle, transmit immediately (greedy). High collision chance if two nodes wait for the same idle moment.
  • Non-persistent: If busy, wait a random amount of time, then sense again. Reduces collisions but increases delay.
  • P-persistent: If idle, transmit with probability , or defer with probability .

3. CSMA/CD (Carrier Sense Multiple Access with Collision Detection)

Used in wired Ethernet (half-duplex). "Listen while talking."

• Mechanism:
  1. Sense channel; if idle, transmit.
  2. Monitor channel while transmitting.
  3. If signal power spikes (collision):
     • Abort transmission immediately.
     • Send a Jam Signal (so all stations know a collision occurred).
     • Wait a random time using Binary Exponential Backoff algorithm.
     • Retry.

B. Controlled Access Protocols

Collision-free protocols.

1. Reservation: Stations reserve a slot before transmitting data.
2. Polling: A primary station (master) asks secondary stations (slaves) one by one if they have data.
3. Token Passing: A special bit pattern (Token) circulates. Only the holder of the Token can transmit. (Used in Token Ring).

5. Ethernet Protocol (IEEE 802.3)

Ethernet is the dominant wired LAN technology.

A. Frame Format

An Ethernet frame varies between 64 and 1518 bytes.

B. MAC Address

• Size: 48 bits (6 bytes), represented in Hexadecimal (e.g., 00:1A:2B:3C:4D:5E).
• Unicast: Destined for one specific card.
• Multicast: Destined for a group.
• Broadcast: Destined for everyone (FF:FF:FF:FF:FF:FF).

6. Switch Working

A Switch is a Data Link Layer (Layer 2) device. Unlike a Hub (which broadcasts everything), a Switch filters and forwards packets intelligently.

A. Mechanism

Switches operate using a MAC Address Table (or Content Addressable Memory - CAM table).

B. The Learning Bridge Algorithm (Self-Learning)

The switch starts empty and learns the network topology dynamically:

1. Learning (Source Inspection):

   • When a frame enters a port (e.g., Port 1), the switch looks at the Source MAC.
   • It updates the table: "MAC Address A is located at Port 1".
   • It sets a "Time to Live" (TTL) for this entry.

2. Forwarding Decision (Destination Inspection):

   • The switch looks at the Destination MAC of the frame.
   • Case 1: Destination Unknown (Flooding): If the MAC is not in the table, the switch sends the frame out all ports except the incoming one.
   • Case 2: Destination Known: If the MAC maps to a specific port in the table, the switch sends the frame only to that port.
   • Case 3: Filtering: If the destination is on the same port/segment as the source, the frame is discarded (it doesn't need to cross the switch).

3. Aging:

   • Entries are deleted if the switch does not hear from that MAC address for a certain period (aging time). This handles devices moving or unplugging.