Data Link Layer Practice Questions

To ensure full link utilization, the window size $W$ must satisfy the Bandwidth-Delay Product ($BDP$) relative to the packet size.
First, convert the bandwidth and packet size to consistent units: $BW = 128 \text{ kbps} = 128,000 \text{ bps}$ and $L = 32 \text{ bytes} = 32 \times 8 = 256 \text{ bits}$.
The Round Trip Time ($RTT$) is $80 \text{ ms} = 0.08 \text{ s}$.
Calculate the $BDP$ (total bits in flight): $BDP = BW \times RTT = 128,000 \times 0.08 = 10,240 \text{ bits}$.
The optimal window size is the number of packets required to fill this $BDP$:
$W = \frac{BDP}{L} = \frac{10,240}{256} = 40$.

The transmission of the $k$-th packet starts at time $t_s = k$. Given a round trip time (RTT) of $N$ units, the acknowledgement (ACK) for the packet transmitted at time $k$ is received at time $t_a = k + N$. To have received an ACK by time $i$, the transmission time must satisfy $k + N \le i$, which simplifies to $k \le i - N$. Thus, the total number of acknowledged packets by time $i$ is $i - N$. The goodput $G$, defined as the number of successfully acknowledged packets per unit time, is:

$G = \frac{\text{Total ACKs received}}{\text{Time } i} = \frac{i - N}{i} = 1 - \frac{N}{i}$

To solve for the total number of transmissions using the Go-Back-N (GBN) protocol with a window size of $N=3$ and a packet loss every 5th transmission ($T_5, T_{10}, T_{15}$), we trace the sequence of transmissions:

1. Initial Packets: $T_1, T_2, T_3$ transmit $P_1, P_2, P_3$ (all successful).
2. Next Window: $T_4, T_5, T_6$ transmit $P_4, P_5, P_6$. $P_5$ is the 5th transmission ($T_5$) and is lost.
3. Retransmission 1: Due to the timeout on $P_4$, $T_7, T_8, T_9$ retransmit $P_4, P_5, P_6$.
4. Next Window: $T_{10}, T_{11}, T_{12}$ transmit $P_7, P_8, P_9$. $P_7$ is the 10th transmission ($T_{10}$) and is lost.
5. Retransmission 2: Due to the timeout on $P_7$, $T_{13}, T_{14}, T_{15}$ retransmit $P_7, P_8, P_9$. $P_9$ is the 15th transmission ($T_{15}$) and is lost.
6. Final Transmission: $T_{16}$ retransmits $P_9$ successfully.

The total number of packets transmitted is 16.

For $S_1$ (no buffer), the aggregate traffic rate must not exceed the link capacity $C = 100$ Mbps at any time, so $S_1 \times R_{on} \leq C \implies S_1 \times 10 \leq 100$, yielding $S_1 = 10$.
With a large buffer and synchronized sources, the condition for no data loss is that the average aggregate traffic rate must not exceed the link capacity.
The probability of a source being ON is $P_{on} = \frac{T_{on}}{T_{on} + T_{off}} = \frac{1}{1 + 2} = \frac{1}{3}$.
The average rate per source is $R_{avg} = R_{on} \times P_{on} = 10 \times \frac{1}{3} = \frac{10}{3}$ Mbps.
The total average rate for $S_2$ sources is $S_2 \times \frac{10}{3} \leq 100$.
Solving for $S_2$, we get $S_2 \leq \frac{100 \times 3}{10} = 30$.

To find the cyclic redundancy check (CRC) for the message $M = 1010001101$ using the divisor polynomial $P(x) = x^{5+}x^{4+}x^{2+}1$, follow these steps:

1. Identify the divisor: The polynomial $P(x) = x^{5+}x^{4+}x^{2+}1$ corresponds to the binary sequence $110101$.
2. Prepare the dividend: Append $k=5$ zeros (the degree of the polynomial) to the message $M$.
   $M' = 101000110100000$
3. Perform modulo-2 division: Divide $M'$ by $P = 110101$ using XOR operations.
   Converting to decimal for verification: $M' = 20896_{10}$ and $P = 53_{10}$.
   The division $20896 \pmod{53}$ yields a remainder of $14$.
4. Convert remainder to binary: The decimal remainder $14$ in 5-bit binary is $01110$.

Thus, the CRC for the given message is $01110$.

In CSMA/CD, a node must detect a collision within a duration determined by the propagation delay, $T_p$. In satellite networks, $T_p$ is extremely high, meaning a station cannot detect a collision signal before it completes transmitting its packet, rendering collision detection ineffective. Option A is false because IEEE 802.11 uses CSMA/CA to avoid, not detect, collisions. Option B is false because Ethernet is historically based on the CSMA/CD protocol. Option D is false because CSMA/CD is inherently a contention-based protocol where multiple nodes compete for access. Thus, high propagation delay makes CSMA/CD unsuitable.

A bridge operates at the Data Link Layer ($Layer 2$) of the OSI model, making option A correct. By segmenting the network, it divides collision domains into smaller units, which confirms option B is true. Its fundamental purpose is to connect distinct LAN segments, validating option C. However, a bridge forwards broadcast frames to all connected ports (flooding) rather than isolating them. Therefore, a bridge does not reduce the broadcast domain; only a router ($Layer 3$ device) can segment broadcast traffic. Thus, statement D is false.

In the Selective Reject protocol using $n$-bit sequence numbers, the total number of unique sequence numbers is $2^n$. To avoid ambiguity between retransmitted frames and new frames, the sum of the sender window size ($W_s$) and receiver window size ($W_r$) must satisfy the condition $W_s + W_r \leq 2^n$. Assuming optimal performance where window sizes are symmetric ($W_s = W_r$), we substitute to get $2W_s \leq 2^n$. Dividing both sides by $2$, we arrive at $W_s \leq 2^{n-1}$. Therefore, the maximum window size is $2^{n-1}$.

Given bandwidth $BW = 1\text{ Gbps} = 10^9\text{ bps}$, length $L = 1000\text{ m}$, and speed $v = 2 \times 10^8\text{ m/s}$.
The propagation delay is $T_{prop} = \frac{L}{v} = \frac{1000}{2 \times 10^8} = 5 \times 10^{-6}\text{ sec}$.
For CSMA/CD, transmission time must be at least the round-trip time, so $T_{trans} \ge 2 \times T_{prop} = 10 \times 10^{-6}\text{ sec}$.
The minimum frame size $S_{min}$ is calculated as $S_{min} = BW \times (2 \times T_{prop})$.
Substituting the values: $S_{min} = 10^9\text{ bps} \times 10^{-5}\text{ sec} = 10000\text{ bits}$.

The minimum frame size in Ethernet ensures that a sender detects collisions within the round-trip propagation delay ($RTT$). First, calculate the number of bits transmitted during the $RTT$:
$\text{Bits}_{RTT} = \text{Bandwidth} \times RTT = (10 \times 10^6 \text{ bps}) \times (46.4 \times 10^{-6} \text{ s}) = 464 \text{ bits}.$
To account for the mandatory 48-bit jamming signal sent upon collision detection, add these bits to the $RTT$ duration bits:
$\text{Minimum Frame Size} = \text{Bits}_{RTT} + \text{Jamming Signal} = 464 + 48 = 512 \text{ bits}.$
Thus, the minimum frame size is 512 bits.

The transmission time is $T_t = \frac{100 \text{ bits}}{10 \times 10^6 \text{ bps}} = 10 \mu s$, and the propagation delay is $T_p = \frac{1000 \text{ m}}{2 \times 10^8 \text{ m/s}} = 5 \mu s$.
The total duration of one time slot is $T_{slot} = T_t + T_p = 10 \mu s + 5 \mu s = 15 \mu s$.
With $N$ stations, the cycle duration is $T_{cycle} = N \times T_{slot} = 15N \mu s$.
The throughput for each station is given by $\frac{100 \text{ bits}}{T_{cycle}} = \frac{100}{15N \times 10^{-6} \text{ sec}} = \frac{2}{3} \times 10^6 \text{ bps}$.
Solving $\frac{100}{15N} = \frac{2}{3}$ gives $\frac{20}{3N} = \frac{2}{3}$, which simplifies to $N = 10$.

The efficiency $\eta$ of the stop-and-wait protocol is given by $\eta = \frac{T_{fr}}{T_{fr} + 2T_p}$, where $T_{fr} = \frac{L}{R}$ is the frame transmission time and $T_p$ is the one-way propagation delay. Given $\eta \ge 0.5$ and negligible acknowledgment transmission time:
$\frac{T_{fr}}{T_{fr} + 2T_p} \ge 0.5 \implies T_{fr} \ge 2T_p$.
Substituting $T_{fr} = \frac{L}{R}$ with bit rate $R = 4000\text{ bps}$ and $T_p = 20\text{ ms} = 0.02\text{ s}$:
$\frac{L}{4000} \ge 2 \times 0.02 \implies \frac{L}{4000} \ge 0.04$.
$L \ge 4000 \times 0.04 = 160\text{ bits}$.
Therefore, the minimum frame size is $160\text{ bits}$.

Let $M=24$ bytes be the message size, $H=3$ bytes be the header, and the number of hops $n=3$ (source to destination via two intermediate nodes). The total transmission time $T$ is proportional to $(\lceil \frac{M}{S-H} \rceil + n - 1) \times S$, where $S$ is the packet size and $N = \lceil \frac{M}{S-H} \rceil$ is the number of packets.
Substituting the values, we minimize $T(S) = (\lceil \frac{24}{S-3} \rceil + 2) \times S$:

• For $S=4$: $(\lceil \frac{24}{1} \rceil + 2) \times 4 = 26 \times 4 = 104$.
• For $S=6$: $(\lceil \frac{24}{3} \rceil + 2) \times 6 = 10 \times 6 = 60$.
• For $S=7$: $(\lceil \frac{24}{4} \rceil + 2) \times 7 = 8 \times 7 = 56$.
• For $S=9$: $(\lceil \frac{24}{6} \rceil + 2) \times 9 = 6 \times 9 = 54$.
  Since 54 is the minimum value, the optimum packet size is 9 bytes.

To ensure correct ARQ operation, the sequence number space must prevent the receiver from confusing a retransmitted "old" frame with a "new" frame. The transmitter maintains a window of $N$ unacknowledged frames, while the receiver maintains a window of $M$ expected frames. To avoid overlap between these two windows in the sequence space $S$, the condition $S \ge N + M$ must hold true. This ensures that even if acknowledgments are lost, the receiver can uniquely identify frames. Thus, the minimum number of distinct sequence numbers required is $N + M$.

To calculate the maximum data rate (throughput) of the Go-Back-N ARQ scheme, we first determine the frame transmission time $T_f$ and the round-trip time $RTT$.

1. Frame transmission time: $T_f = \frac{L}{R} = \frac{100 \times 8 \text{ bits}}{20,000 \text{ bps}} = 0.04 \text{ s}$.
2. Round-trip time: $RTT = 2 \times T_p = 2 \times 0.4 \text{ s} = 0.8 \text{ s}$.
3. In Go-Back-N, the throughput is approximated by transmitting $N$ frames per round-trip cycle: $\text{Throughput} \approx \frac{N \times L}{RTT}$.
4. Substituting the given values: $\frac{10 \times 800 \text{ bits}}{0.8 \text{ s}} = \frac{8,000 \text{ bits}}{0.8 \text{ s}} = 10,000 \text{ bps} = 10 \text{ Kbps}$.
   This calculation assumes the transmission time $T_f$ is negligible compared to the $RTT$ ($0.04 \text{ s} \ll 0.8 \text{ s}$).

The original payload for Network B is $180 \text{ (application)} + 20 \text{ (TCP header)} = 200$ bytes. The Network B MTU is $100$ bytes, including the $20$ byte IP header, which leaves $80$ bytes for payload per fragment. The number of fragments required is $\lceil 200 / 80 \rceil = 3$. The total data transmitted across the link to Network C includes the original $200$ bytes of payload plus $3$ IP headers of $20$ bytes each, totaling $260$ bytes. The transfer rate for the $180$ bytes of application data is:
$\text{Rate} = \frac{180 \text{ bytes}}{260 \text{ bytes}} \times 512 \text{ Kbps} \approx 354.46 \text{ Kbps}$
Rounding to the given options, we get $354.5 \text{ Kbps}$.

In a time-slotted system with $N$ hosts each transmitting with probability $p=0.2$, the probability of a successful transmission for a specific host is $S = p(1-p)^{N-1}$.
We require $S \ge 0.16$.
For $N=1$: $S = 0.2(1-0.2)^{0} = 0.2 \ge 0.16$.
For $N=2$: $S = 0.2(1-0.2)^{1} = 0.2 \times 0.8 = 0.16 \ge 0.16$.
For $N=3$: $S = 0.2(1-0.2)^{2} = 0.2 \times 0.64 = 0.128 < 0.16$.
Since $N=3$ fails the throughput requirement, the maximum number of hosts supported is 2.

The frame delimiter flag $0111$ consists of three consecutive $1$s. To perform bit stuffing, a $0$ is inserted after every sequence of $11$ to prevent the flag pattern from occurring within the data.

Processing the sequence $01110110$ step-by-step:

1. The first $11$ at indices $2,3$ triggers stuffing: $011 \rightarrow 0110$.
2. The remaining data to process is $1_4 0_5 1_6 1_7 0_8$.
3. Appending the next bit $1_4$ and $0_5$ gives $011010$.
4. The next $11$ ($1_6 1_7$) triggers stuffing: $11 \rightarrow 110$.
5. Appending the final bit $0_8$ results in the sequence $0110101100$.

After the first collision, $B$ failed, incrementing its backoff stage to $k=2$ with $r_B \in \{0, 1, 2, 3\}$. For the second transmission, $A$ is at $k=1$ with $r_A \in \{0, 1\}$. The total sample space size for $(r_A, r_B)$ is $2 \times 4 = 8$. $A$ wins the backoff race if $r_A < r_B$, which includes the pairs: $(0,1), (0,2), (0,3), (1,2), (1,3)$. There are 5 favorable outcomes out of 8 possible outcomes. Thus, the probability that $A$ wins the second backoff race is $5/8 = 0.625$.