Data Link Layer Comprehensive Exercises

Approach: list the five functions of the data link layer and the mechanism behind each one.

Steps:

The main functions of the data link layer are:

1. Framing: dividing the bit stream into frames so that they can be managed and checked for errors
2. Error control: error detection (parity check, CRC) and error correction (Hamming code)
3. Flow control: preventing the sender from transmitting too fast, usually through a sliding window
4. Reliable transmission: acknowledgment and retransmission mechanisms
5. Medium access control: the rules for accessing a channel shared by multiple stations

Answer: framing, error control, flow control, reliable transmission, and medium access control.

Approach: follow the four stages of a CRC exchange, from sender computation to receiver check.

Steps:

The basic idea of CRC error detection:

1. Sender: divide the data polynomial by the generator polynomial modulo 2 and append the remainder to the data as the check code
2. Transmission: send the data plus the check code
3. Receiver: perform the same modulo-2 division on the received data plus the check code using the same generator polynomial
4. Decision: a remainder of 0 means no error; a non-zero remainder means an error occurred

CRC detects both burst errors and random errors, so its detection capability is strong.

Answer: the sender computes the remainder of the data modulo the generator polynomial and appends it; the receiver repeats the division and treats a non-zero remainder as an error.

Approach: compare the two protocols on sending strategy, window size, efficiency, and implementation complexity.

Steps:

The main differences are:

1. Sending strategy:

   • Stop-and-wait: sends one frame at a time and waits for the acknowledgment
   • Sliding window: may send several frames without waiting for an acknowledgment

2. Window size:

   • Stop-and-wait: send window = 1, receive window = 1
   • Sliding window: send window > 1, receive window ≥ 1

3. Efficiency:

   • Stop-and-wait: low efficiency and low channel utilization
   • Sliding window: high efficiency and high channel utilization

4. Complexity:

   • Stop-and-wait: simple to implement
   • Sliding window: relatively more complex to implement

Answer: stop-and-wait sends one frame and waits, while the sliding window protocol sends several frames within a window and needs only one acknowledgment for the whole batch, which gives it much higher channel utilization.

Approach: compare the two protocols on the receive window, the retransmission policy, efficiency, and complexity.

Steps:

The main differences are:

1. Receive window:

   • GBN: receive window = 1, frames are accepted only in order
   • SR: receive window > 1, out-of-order frames can be buffered

2. Retransmission policy:

   • GBN: retransmits the erroneous frame and every frame after it
   • SR: retransmits only the erroneous frame

3. Efficiency:

   • GBN: may retransmit frames that were already received correctly, so it is less efficient
   • SR: retransmits only the erroneous frame, so it is more efficient

4. Complexity:

   • GBN: the receiver is simple
   • SR: the receiver must buffer frames, which makes the implementation complex

Answer: GBN has a receive window of 1 and retransmits the erroneous frame plus everything after it; SR has a larger receive window and retransmits only the erroneous frame, at the cost of receiver buffering.

Approach: name the protocol, then break it into its five steps and the operating sequence they produce.

Steps:

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

The basic principle:

1. Carrier sense: listen to the channel before transmitting to check whether it is idle
2. Multiple access: several stations share the same channel
3. Collision detection: keep listening while transmitting to detect collisions
4. Collision handling: stop transmitting immediately on detecting a collision and send a jamming signal
5. Retransmission: retransmit after a random delay

The operating sequence:

• When a station has data to send, it first listens to the channel
• If the channel is idle, it transmits immediately
• It keeps listening while transmitting
• If a collision is detected, it stops transmitting immediately and sends a jamming signal
• It waits for a random time and then tries again

Answer: Ethernet uses CSMA/CD, which senses the channel before transmitting, detects collisions during transmission, stops and signals on collision, and retransmits after a random backoff.

Approach: compare the two protocols on collision handling, target environment, operating principle, the hidden terminal problem, and efficiency.

Steps:

The main differences are:

1. How collisions are handled:

   • CSMA/CD: handles collisions after detecting them
   • CSMA/CA: avoids collisions before they happen

2. Target environment:

   • CSMA/CD: wired networks (Ethernet)
   • CSMA/CA: wireless networks (Wi-Fi)

3. Operating principle:

   • CSMA/CD: detects collisions while transmitting
   • CSMA/CA: avoids collisions before transmitting through RTS/CTS

4. The hidden terminal problem:

   • CSMA/CD: does not have this problem
   • CSMA/CA: solves it with RTS/CTS

5. Efficiency:

   • CSMA/CD: efficient in a wired environment
   • CSMA/CA: more reliable in a wireless environment

Answer: CSMA/CD detects and handles collisions after transmission begins and suits wired links; CSMA/CA avoids collisions before transmission through RTS/CTS and suits wireless links, where collisions cannot be reliably detected.

Approach: group the properties into similarities and differences, with the differences ordered by importance.

Steps:

Similarities:

1. Both are data link layer protocols
2. Both support point-to-point connections
3. Both provide error control functions

Differences:

1. Orientation:

   • PPP: byte-oriented
   • HDLC: bit-oriented

2. Complexity:

   • PPP: simple and easy to implement
   • HDLC: complex and powerful

3. Supported connections:

   • PPP: mainly point-to-point
   • HDLC: point-to-point and multipoint

4. Authentication:

   • PPP: supports PAP/CHAP authentication
   • HDLC: does not support authentication

5. Network layer protocols:

   • PPP: supports multiple network layer protocols
   • HDLC: is independent of the network layer protocol

Answer: both are data link layer protocols with point-to-point support and error control; PPP is byte-oriented, simpler, and adds authentication and network layer negotiation, while HDLC is bit-oriented, more complex, and supports multipoint links.

Approach: list the shared properties, then the five properties on which they differ.

Steps:

Similarities:

1. Both are data link layer devices
2. Both forward based on MAC addresses
3. Both can connect multiple network segments

Differences:

1. Number of ports:

   • Bridge: usually only 2 ports
   • Switch: usually many ports (4, 8, 16, 24, and so on)

2. Forwarding method:

   • Bridge: store and forward
   • Switch: store and forward or cut-through

3. Performance:

   • Bridge: forwards more slowly
   • Switch: forwards quickly and supports parallel forwarding

4. Features:

   • Bridge: basic functions
   • Switch: rich features, including VLANs and QoS

5. Application scenarios:

   • Bridge: connecting two network segments
   • Switch: building the core of a LAN

Answer: a switch is a multi-port bridge that gives each port its own collision domain, forwards in parallel, and adds features such as VLANs and QoS; a bridge is a simple two-port device for joining two segments.

Approach: walk through the collision handling sequence, then spell out the binary exponential backoff.

Steps:

The steps CSMA/CD follows when a collision occurs:

1. Collision detection: keep listening to the channel while transmitting
2. Immediate stop: stop transmitting as soon as the collision is detected
3. Send a jamming signal: send a jamming signal to notify the other stations that a collision occurred
4. Wait a random time: compute the waiting time with the binary exponential backoff algorithm
5. Try again: retransmit when the waiting time has elapsed

The binary exponential backoff algorithm:

• 1st collision: wait 0 or 1 slot times
• 2nd collision: wait 0, 1, 2, or 3 slot times
• 3rd collision: wait 0 to 7 slot times
• At most 16 retries, after which the frame is abandoned

Answer: the sender detects the collision, stops immediately, sends a jamming signal, waits a random backoff time drawn from a range that doubles with each collision, and then retransmits.

Approach: give the three technical reasons collision detection fails on a wireless link, then explain the RTS/CTS mechanism that replaces it.

Steps:

Why wireless networks use CSMA/CA:

1. Collision detection is difficult:

   • wireless signal propagation characteristics are complex
   • a collision is hard to detect while transmitting
   • the hidden terminal problem

2. Signal characteristics:

   • wireless signals attenuate quickly
   • the transmit power is limited
   • collision detection is hard to implement

3. The hidden terminal problem:

   • two stations may not be able to communicate directly
   • but both can reach the AP
   • CSMA/CA solves this with RTS/CTS

4. The RTS/CTS mechanism:

   • the sender first sends an RTS (Request To Send)
   • the receiver replies with a CTS (Clear To Send)
   • other stations that hear the CTS defer their transmissions

5. Greater reliability:

   • avoiding a collision is more effective than detecting it
   • the number of retransmissions is reduced
   • network efficiency improves

Answer: a wireless transmitter cannot reliably hear a collision because of attenuation, limited transmit power, and hidden terminals, so CSMA/CA avoids collisions in advance with IFS waiting, random backoff, and RTS/CTS instead of detecting them afterwards.