Data Link Layer Practice Questions

The transmission delay (p) is the time required to place the entire message on the link. It is calculated as Message Size / Bandwidth.
Message size = 50,000 bytes = $50,000 \times 8$ bits = 400,000 bits.
Bandwidth = $10^6$ bits/sec.
$p = \frac{400,000 \text{ bits}}{10^6 \text{ bits/sec}} = 0.4 \text{ sec} = 400 \text{ ms}$

The propagation delay (q) is the time it takes for a bit to travel from the source to the destination. It is calculated as Distance / Propagation Speed.
Distance = 10,000 km = $10^7$ m.
$q = \frac{10^7 \text{ m}}{2 \times 10^8 \text{ m/sec}} = 0.05 \text{ sec} = 50 \text{ ms}$

The generator polynomial $x^{3+}x+1$ corresponds to the divisor bit string 1011. The degree of the polynomial is 3.

To find the check bits, we append 3 zeros to the message 01011011, resulting in 01011011000. We then perform binary division (using XOR for subtraction) of this appended message by the divisor 1011.

The long division process shown in the PDF yields a remainder of 101. These three bits are the check bits.

The final transmitted message is the original message with the check bits appended: 01011011101.

The IEEE 802.3 standard mandates a minimum Ethernet frame size of 64 bytes to ensure reliable collision detection within CSMA/CD networks. Any frame transmitted with a length of less than $64$ bytes is considered invalid because it fails to satisfy these physical layer constraints. In networking terminology, a frame that is undersized due to collisions or hardware malfunctions is specifically defined as a runt frame. Therefore, an Ethernet frame falling below the required $64$-octet threshold is classified as a runt frame.

Let's analyze the statements regarding the IEEE 802.11 protocol:
I. In the commonly used 2.4 GHz band, channels 1, 6, and 11 are designed to be non-overlapping. Therefore, at least three non-overlapping channels are available. This statement is TRUE.
II. The RTS-CTS (Request to Send/Clear to Send) mechanism is part of the collision avoidance (CSMA/CA) strategy, not collision detection. Wireless devices typically cannot detect collisions while transmitting. This statement is FALSE.
III. To ensure reliable delivery, all unicast frames sent to a specific destination require an acknowledgment (ACK) from the receiver. This statement is TRUE.
Therefore, only statements I and III are true.

In binary exponential backoff after the $k$-th collision (up to k=10), the waiting time is chosen uniformly from $\{0, 1, 2, ..., 2^k - 1\}$ slot times. After 16 collisions, the transmission is aborted.

For CSMA/CD to function correctly, the minimum frame transmission time ($T_t$) must be at least twice the maximum signal propagation time ($T_p$). This ensures a station can detect a collision before it finishes transmitting the frame. The condition is $T_t \ge 2T_p$.
The minimum frame size (L) is calculated as $L = 2 \times T_p \times \text{Bandwidth}$.
Given:

• Bandwidth = $20 \times 10^6$ bits/second
• $T_p = 40 \mu s = 40 \times 10^{-6}$ seconds
  $L = 2 \times (40 \times 10^{-6}) \times (20 \times 10^6) = 1600$ bits.
  To convert this to bytes, we divide by 8: $1600 / 8 = 200$ bytes.

In Ethernet networks utilizing CSMA/CD, when multiple stations attempt to transmit data simultaneously, a collision occurs on the physical medium. Upon detecting this interference, the transmitting stations immediately cease sending their data frames and broadcast a specific, fixed-length bit sequence known as the Jam signal. This signal serves to reinforce the collision, ensuring that all other stations on the network segment detect the interference and halt their respective transmissions. Once the Jam signal is completed, the stations invoke an exponential backoff algorithm to wait for a random interval before attempting to retransmit.

Sender throughput is the amount of useful data transmitted per unit of time. For one successful frame transmission in Stop-and-Wait, the total time cycle includes the frame's transmission time ($T_t$), propagation delay ($T_p$), ACK's transmission time ($T_{ack}$), and the ACK's propagation delay ($T_p$).

$T_t = \frac{\text{Frame size}}{\text{Sender rate}} = \frac{1000 \times 8 \text{ bits}}{80 \times 1000 \text{ bps}} = 0.1$ s.
$T_p = 100$ ms $= 0.1$ s.
$T_{ack} = \frac{\text{ACK size}}{\text{Receiver rate}} = \frac{100 \times 8 \text{ bits}}{8 \times 1000 \text{ bps}} = 0.1$ s.

Total cycle time = $T_t + T_p + T_{ack} + T_p = 0.1 + 0.1 + 0.1 + 0.1 = 0.4$ s.
Throughput = $\frac{\text{Frame size}}{\text{Total time}} = \frac{1000 \text{ bytes}}{0.4 \text{ s}} = 2500$ bytes/second.

The polynomial $P(x) = x^3 + 1$ corresponds to the binary divisor $1001$.
The message $11001001$ is represented by the polynomial $M(x) = x^7 + x^6 + x^3 + 1$.
To find the transmitted message, compute the remainder of $M(x) \cdot x^3$ divided by $P(x)$.
Using the property $x^3 \equiv 1 \pmod{x^{3+}1}$, we get $M(x) \cdot x^3 = x^{10} + x^9 + x^6 + x^3 \equiv x + 1 + 1 + 1 = x + 1$.
The remainder $x+1$ corresponds to the binary sequence $011$ (for a 3-bit CRC).
Appending $011$ to the message $11001001$ results in $11001001011$.

In an Ethernet network that uses CSMA/CD, collisions can occur when multiple stations transmit simultaneously. After a collision is detected, the involved stations use the exponential backoff algorithm. This mechanism requires each station to wait for a random amount of time before retransmitting. The range of possible wait times increases exponentially with each subsequent collision, which reduces the probability of another collision during retransmission.

The time required to transmit 1 bit is $T_{bit} = \frac{1}{\text{Transmission speed}} = \frac{1}{10^7 \text{ bps}} = 10^{-7} \text{ seconds}$.
Converting this time to microseconds, we get $T_{bit} = 0.1 \, \mu\text{s}$.
Given the propagation speed $v = 200 \text{ meters}/\mu\text{s}$, the distance $d$ equivalent to this 1-bit delay is the distance a signal travels in $T_{bit}$ time:
$d = v \times T_{bit} = 200 \, \text{m}/\mu\text{s} \times 0.1 \, \mu\text{s} = 20 \, \text{meters}$
Thus, the 1-bit delay is equivalent to 20 meters of cable.

The transmission time $T_t$ for a frame is calculated as:
$T_t = \frac{\text{Frame Size}}{\text{Bandwidth}} = \frac{1000 \text{ bits}}{10^6 \text{ bps}} = 10^{-3} \text{ s} = 1 \text{ ms}$
The number of frames $N$ that can fit in transit within the link (propagation delay $T_p = 25 \text{ ms}$) is:
$N = \frac{T_p}{T_t} = \frac{25 \text{ ms}}{1 \text{ ms}} = 25$
To uniquely identify these frames, we require a sequence number space of size $2^I \ge N$:
$2^I \ge 25$
Since $2^4 = 16 < 25$ and $2^5 = 32 \ge 25$, the minimum number of bits required is $I = 5$.

To achieve 100% utilization, the sender's window size (W) must be large enough to transmit continuously for one full round-trip time. The number of frames needed is $W \ge 1 + 2a$, where $a = T_p / T_t$.
First, calculate the transmission time ($T_t$):
$T_t = \frac{\text{Frame Size}}{\text{Bandwidth}} = \frac{1 \text{ KB} \times 8 \text{ bits/byte}}{128 \times 10^3 \text{ bps}} = \frac{8192 \text{ bits}}{128000 \text{ bps}} \approx 64$ ms.
Now, calculate $a$:
$a = \frac{T_p}{T_t} = \frac{150 \text{ ms}}{64 \text{ ms}} \approx 2.34$.
The required window size is $W = 1 + 2(2.34) = 5.68$. Since we must send whole frames, we need a window of at least $\lceil 5.68 \rceil = 6$.
For Selective Repeat, the window size (W) and the number of sequence bits (n) are related by $2W \le 2^n$.
$2 \times 6 \le 2^n \Rightarrow 12 \le 2^n$.
The smallest integer $n$ that satisfies this is 4, as $2^4 = 16$.

First, calculate the transmission time ($T_t$) for one packet.
Packet size = 1000 bytes = 8000 bits.
Transmission speed = $10^6$ bits/sec.
$T_t = \frac{8000 \text{ bits}}{10^6 \text{ bits/sec}} = 8 \text{ ms}$.

The efficiency ($\eta$) of the stop-and-wait protocol is given by $\eta = \frac{T_t}{T_t + 2T_p}$, where $T_p$ is the one-way propagation delay.
Given $\eta = 25\% = 0.25$.
$0.25 = \frac{8}{8 + 2T_p}$
$0.25 \times (8 + 2T_p) = 8$
$2 + 0.5T_p = 8$
$0.5T_p = 6$
$T_p = 12$ ms.

To determine the codeword (transmitted data unit) at the receiver, follow these CRC steps:

1. The divisor is $1011$, which has a length of $4$, so append $k = 4 - 1 = 3$ zeros to the data unit $100111001$, resulting in $100111001000$.
2. Perform modulo-2 division of $100111001000$ by $1011$ using XOR operations.
3. The division yields a remainder of $011$.
4. Append this remainder to the original data unit ($100111001$) to form the transmitted codeword: $100111001011$.

In a CSMA/CD network, the minimum frame transmission time ($T_t$) must be at least twice the maximum one-way propagation delay ($T_p$) to ensure collision detection. For the minimum frame size, we use the equality $T_t = 2T_p$.
$T_t = \frac{\text{Frame Size}}{\text{Bandwidth}} = \frac{1250 \text{ bytes} \times 8 \text{ bits/byte}}{100 \times 10^6 \text{ bps}} = \frac{10000}{10^8}$ s.
$T_p = \frac{\text{Distance}}{\text{Signal Speed}} = \frac{1 \text{ km}}{\text{Signal Speed}}$.
Setting $T_t = 2T_p$:
$\frac{10000}{10^8} = \frac{2 \times 1 \text{ km}}{\text{Signal Speed}}$
Signal Speed = $\frac{2 \times 10^8}{10000}$ km/s = $20000$ km/s.

In ALOHA systems, the channel load $G$ is defined as the average number of transmission requests generated per time slot. Given the request rate $R = 70 \text{ requests/sec}$ and the slot duration $T = 50 \text{ msec} = 0.05 \text{ seconds}$, the load is calculated by multiplying the request rate by the duration of a single slot:
$G = R \times T$
$G = 70 \text{ requests/sec} \times 0.05 \text{ sec/slot} = 3.5 \text{ requests/slot}$
Therefore, the channel load is $3.5$.

First, calculate the one-way propagation delay ($T_p$) and the transmission delay ($T_t$).
$T_p = \frac{\text{Distance}}{\text{Speed}} = \frac{8000 \times 10^3 \text{ m}}{4 \times 10^6 \text{ m/s}} = 2$ seconds.
$T_t = \frac{\text{Packet Size}}{\text{Bandwidth}} = \frac{10^7 \text{ bits}}{500 \times 10^6 \text{ bps}} = 0.02$ seconds.

To achieve full capacity, the sender must be able to transmit continuously for one full Round Trip Time (RTT), which is $2 \times T_p = 4$ seconds. The number of packets that can be sent in this time is the required window size (W):
$W = \frac{\text{RTT}}{T_t} = \frac{4}{0.02} = 200$ packets.

For the Go-Back-N protocol, the number of sequence numbers ($2^m$) must be greater than the window size. We need at least $W+1 = 201$ sequence numbers. To represent 201 sequence numbers, we need $m$ bits such that $2^m \ge 201$.
$2^7 = 128$ (insufficient)
$2^8 = 256$ (sufficient)
Thus, a minimum of 8 bits are required for the sequence number field.

Let $T_t$ be the transmission time and $T_p$ be the propagation delay. The link utilization ($\eta$) for the stop-and-wait protocol is given by $\eta = \frac{T_t}{T_t + 2T_p}$.
To achieve a utilization of at least 50% ($\eta \ge 0.5$), we must have $\frac{T_t}{T_t + 2T_p} \ge 0.5$, which simplifies to $T_t \ge 2T_p$.
Given $T_p = 20$ ms, the round-trip time is $2T_p = 40$ ms.
The bit rate is 64 kbps. Let the frame size be $x$ bits.
$T_t = \frac{x}{64 \times 10^3}$ seconds.
So, $\frac{x}{64000} \ge 40 \times 10^{-3} \implies x \ge 2560$ bits.
In bytes, the minimum size is $\frac{2560}{8} = 320$ bytes.