Data Link Layer Practice Questions

The propagation delay for the round trip is $T_p = \frac{2 \times 36,504,000 \text{ m}}{3 \times 10^8 \text{ m/s}} = 0.24336 \text{ s}$.
The transmission time per frame is $T_f = \frac{L}{R} = \frac{L}{10^6} \text{ s}$, where $L$ is the packet size in bits.
For the Go-Back-N protocol, the utilization $\eta$ is given by $\eta = \frac{N}{1 + 2a}$, where $a = \frac{T_p}{T_f}$ and $N = 127$.
Substituting the given values: $0.25 = \frac{127}{1 + 2 \times \frac{0.24336}{L/10^6}} = \frac{127}{1 + \frac{486,720}{L}}$.
Rearranging for $L$: $1 + \frac{486,720}{L} = \frac{127}{0.25} = 508$, so $\frac{486,720}{L} = 507$.
Solving for $L$: $L = \frac{486,720}{507} \approx 960 \text{ bits}$.
Converting to bytes: $L = \frac{960}{8} = 120 \text{ bytes}$.

Given the transmission rate $R = 10 \text{ Mbps}$, token refill rate $r = 2 \text{ Mbps}$, and initial capacity $B = 16 \text{ Megabits}$.
The bucket discharges at a net rate of $R - r = 10 \text{ Mbps} - 2 \text{ Mbps} = 8 \text{ Mbps}$.
To find the maximum duration $t$ for transmitting at the full rate, we use the formula $B = (R - r) \cdot t$.
Solving for $t$, we obtain $t = \frac{B}{R - r} = \frac{16 \text{ Megabits}}{8 \text{ Mbps}} = 2 \text{ seconds}$.

Given $R = 1 \text{ Gbps} = 10^9 \text{ bps}$, $d = 200 \text{ m}$, and $v = 2 \times 10^8 \text{ m/sec}$.
The propagation delay is $T_{prop} = \frac{d}{v} = \frac{200}{2 \times 10^8} = 1 \times 10^{-6} \text{ sec}$.
For CSMA/CD, the transmission time must be at least the round-trip time (RTT), so $T_{trans} \ge 2 \times T_{prop} = 2 \times 10^{-6} \text{ sec}$.
The minimum frame size $L$ is calculated as $L = R \times 2 \times T_{prop}$.
$L = 10^9 \text{ bps} \times 2 \times 10^{-6} \text{ sec} = 2000 \text{ bits}$.
Converting to bytes: $L = \frac{2000}{8} = 250 \text{ bytes}$.

The IEEE 802 project defines various networking standards. IEEE 802.3, known as Ethernet, utilizes Carrier Sense Multiple Access with Collision Detection ($CSMA/CD$), where collisions are possible. IEEE 802.5 specifies the Token Ring protocol. In a Token Ring network, a token is passed sequentially among nodes, and only the node currently in possession of the token is authorized to transmit data. This deterministic method ensures that no two stations transmit simultaneously, thereby maintaining a collision-free environment.

To determine the minimum number of corrupted bits $n$, we first identify the rows and columns that violate the Even parity scheme (i.e., those with an odd sum).

Calculating the row parities (including $d_0$):

• $r_0: 0+1+0+1+0+0+1+1 = 4$ (Even)
• $r_1: 1+1+0+0+1+1+1+0 = 5$ (Odd)
• $r_2: 0+0+0+1+0+1+0+0 = 2$ (Even)
• $r_3: 0+1+1+0+1+0+1+0 = 4$ (Even)
• $r_4: 1+1+0+0+0+1+1+0 = 4$ (Even)
  Only $r_1$ is odd.

Calculating the column parities (including $r_4$):

• $d_7: 0+1+0+0+1 = 2$ (Even)
• $d_6: 1+1+0+1+1 = 4$ (Even)
• $d_5: 0+0+0+1+0 = 1$ (Odd)
• $d_4: 1+0+1+0+0 = 2$ (Even)
• $d_3: 0+1+0+1+0 = 2$ (Even)
• $d_2: 0+1+1+0+1 = 3$ (Odd)
• $d_1: 1+1+0+1+1 = 4$ (Even)
• $d_0: 1+0+0+0+0 = 1$ (Odd)

There is $1$ row with odd parity and $3$ columns with odd parity. Each bit flip at position $(r_i, c_j)$ toggles the parity of exactly one row and one column. To correct $3$ odd-parity columns, we must perform at least $3$ flips, as each flip can correct at most one column. Therefore, the minimum number of corrupted bits $n$ is $3$.

Ethernet operates at the Data Link Layer, where communication occurs hop-by-hop between adjacent physical nodes. Each time a frame traverses a network segment (e.g., through a router), it is re-encapsulated for the next hop. Consequently, the $Source Address$ field in the MAC header is populated with the physical address of the device that transmitted the frame onto the current medium. Because this field identifies the specific node that immediately preceded the current receiver in the transmission chain, it represents the previous station's physical address.

For maximum utilization in a sliding window protocol, the sender window size ($W_s$) must be large enough to keep the channel pipeline full. This means the sender must be able to transmit frames continuously without waiting for acknowledgements.

1. Transmission Delay ($T_t$): The time it takes to transmit one frame is given by its length divided by the channel capacity.
   $T_t = \frac{\text{Frame Length}}{\text{Channel Capacity}} = \frac{K}{R} \text{ seconds}$

2. Propagation Delay: The one-way propagation delay is $L \times t$. The Round Trip Time (RTT) for propagation is:
   $\text{RTT} = 2 \times L \times t = 2Lt \text{ seconds}$

3. Dimensionless Ratio 'a': This ratio represents the number of frame transmission times that fit into one RTT.
   $a = \frac{\text{RTT}}{T_t} = \frac{2Lt}{K/R} = \frac{2LtR}{K}$

4. Minimum Sender Window Size ($W_s$) for Maximum Utilization: To achieve maximum utilization, the sender must transmit frames for a duration equal to or greater than the RTT before an acknowledgement for the first frame is received. The minimum window size required to keep the pipe full is $1 + 2a$. The '1' accounts for the frame currently being transmitted, and '$2a$' accounts for the frames that can be sent during the RTT.
   $W_s = 1 + a = 1 + \frac{2LtR}{K}$
   This can be rewritten by finding a common denominator:
   $W_s = \frac{K}{K} + \frac{2LtR}{K} = \frac{K + 2LtR}{K}$

5. Minimum Bits for Sequence Number Field ('m'): If $m$ bits are used for the sequence number, then $2^m$ unique sequence numbers are available. For the sliding window protocol to function correctly and avoid ambiguity, the sender window size $W_s$ must be less than or equal to the total sequence number space, i.e., $2^m \ge W_s$. To find the minimum number of bits, we use the ceiling function:
   $m = \left\lceil \log_2(W_s) \right\rceil = \left\lceil \log_2\left(\frac{2LtR + K}{K}\right) \right\rceil$
   The square brackets $[x]$ in the options typically denote the ceiling function $\lceil x \rceil$.

The derived expression matches option C.

The final answer is $\boxed{C}$

Let $P(\text{transmit})$ be the probability a station transmits, which is $p$.
Let $P(\text{not transmit})$ be the probability a station does not transmit, which is $1-p$.
For a specific station $i$ to transmit, its probability is $p$.
For the remaining $n-1$ stations to not transmit, the probability for each is $(1-p)$.
Since transmissions are independent, the probability that station $i$ transmits AND all other $n-1$ stations do not transmit is:
$p \times (1-p)^{n-1}$
There are $n$ possible stations that could be the "only one" transmitting. Since these are mutually exclusive events, we sum their probabilities.
The total probability that only one station transmits is $n$ times the probability for any specific station:
$n \times p(1-p)^{n-1}$

In a token ring network with $N$ stations, each transmitting one frame per cycle, the total time for one cycle consists of the time to transmit all frames plus the total ring latency. The utilization $U$ is given by the ratio of the total transmission time to the total cycle time:
$U = \frac{N \cdot t_t}{N \cdot t_t + t_p}$
Substituting the given values $N = 15$, $t_t = 5$ ms, and $t_p = 3$ ms:
$U = \frac{15 \cdot 5}{15 \cdot 5 + 3} = \frac{75}{75 + 3} = \frac{75}{78} \approx 0.9615$
Rounding to three decimal places, we get $0.961$.

An Ethernet hub operates at the Physical Layer (Layer 1) of the OSI model. Its primary function is to receive an electrical signal from one port, regenerate (boost) the signal, and broadcast it to all other connected ports. Because it repeats incoming signals without interpreting the data link information or making logical forwarding decisions, it is technically classified as a multi-port repeater. Therefore, it does not function as a gateway, nor is it designed for token-ring or PBX systems.

To determine the maximum number of correctable bit errors $t$, we must find the minimum Hamming distance $d_{min}$ between any pair of the given codewords $\{00000000, 00001111, 01010101, 10101010, 11110000\}$.
By calculating the Hamming distance between each pair (e.g., $d(00000000, 00001111) = 4$ and $d(01010101, 10101010) = 8$), we find that the minimum distance is $d_{min} = 4$.
The capability to correct bit errors is defined by the formula $t = \lfloor \frac{d_{min} - 1}{2} \rfloor$.
Substituting the value of $d_{min}$, we get $t = \lfloor \frac{4 - 1}{2} \rfloor = \lfloor \frac{3}{2} \rfloor = 1$.
Thus, the maximum number of bit errors that can be corrected is 1.

To protect the message $M = 11001001$ using the CRC polynomial $P(x) = x^3 + 1$:

1. Identify the generator polynomial $P(x) = x^3 + 1$. Its binary representation is $P = 1001$.

2. The degree of the polynomial is $k=3$. This means the CRC checksum will be 3 bits long.

3. Append $k=3$ zeros to the original message: $M' = 11001001000$.

4. Perform binary division (XOR division) of $M'$ by $P$. We simulate a shift register:
   Initialize a $k$-bit register (remainder $R$) to $000$. The "reduced" divisor for XOR operations is $P$ without its MSB, i.e., $001$.

   Iterate through each bit of $M'$ ($11001001000$):

   • Current bit 1: R (MSB is 0) $\to$ 001
   • Current bit 1: R (MSB is 0) $\to$ 011
   • Current bit 0: R (MSB is 0) $\to$ 110
   • Current bit 0: R (MSB is 1) $\to$ 100 $\to$ 100 \oplus 001 = 101
   • Current bit 1: R (MSB is 1) $\to$ 011 $\to$ 011 \oplus 001 = 010
   • Current bit 0: R (MSB is 0) $\to$ 100
   • Current bit 0: R (MSB is 1) $\to$ 000 $\to$ 000 \oplus 001 = 001
   • Current bit 1: R (MSB is 0) $\to$ 011
   • Current bit 0: R (MSB is 0) $\to$ 110
   • Current bit 0: R (MSB is 1) $\to$ 100 $\to$ 100 \oplus 001 = 101
   • Current bit 0: R (MSB is 1) $\to$ 010 $\to$ 010 \oplus 001 = 011

   The final remainder (CRC checksum) is $011$.

5. Append the CRC checksum to the original message:
   Transmitted message = $11001001$ + $011 = 11001001011$.

The message that should be transmitted is $11001001011$.

In a token ring network with $N$ stations, the maximum utilization $U$ is defined as the ratio of the total time spent transmitting data to the total time for one complete cycle. The total transmission time for $N$ stations is $N \cdot t_t$, and the cycle includes the propagation latency $t_p$.

The formula is:
$U = \frac{N \cdot t_t}{N \cdot t_t + t_p}$
Substituting the given values $N = 10$, $t_t = 3$ ms, and $t_p = 5$ ms:
$U = \frac{10 \cdot 3}{10 \cdot 3 + 5} = \frac{30}{35} = \frac{6}{7} \approx 0.857$
This calculated value corresponds to option C.

The time duration for one bit ($T_{bit}$) is given by the inverse of the transmission speed:
$T_{bit} = \frac{1 \text{ bit}}{10^7 \text{ bps}} = 10^{-7} \text{ s}$
The propagation speed ($v$) is 200 metres/$\mu s$. Converting this to metres/s:
$v = 200 \text{ metres/}\mu s = 200 \times 10^6 \text{ metres/s} = 2 \times 10^8 \text{ metres/s}$
The equivalent length of cable is the product of propagation speed and the time for one bit:
$\text{Length} = v \times T_{bit} = (2 \times 10^8 \text{ m/s}) \times (10^{-7} \text{ s}) = 2 \times 10^{8-7} \text{ m} = 2 \times 10^1 \text{ m} = 20 \text{ metres}$

The transmission time $T_{\text{trans}}$ for 1000 bytes is $T_{\text{trans}} = \frac{1000 \times 8 \text{ bits}}{10 \times 10^6 \text{ bps}} = 800 \mu s$.
The total time per cycle for 10 nodes, including polling delay, is $T_{\text{total}} = 10 \times (T_{\text{trans}} + T_{\text{poll}}) = 10 \times (800 \mu s + 80 \mu s) = 8800 \mu s = 8.8 \times 10^{-3} s$.
The total data transmitted per cycle is $D_{\text{total}} = 10 \times 8000 \text{ bits} = 80,000 \text{ bits}$.
The throughput is $\text{Throughput} = \frac{D_{\text{total}}}{T_{\text{total}}} = \frac{80,000 \text{ bits}}{8.8 \times 10^{-3} s} = \frac{80,000,000}{8.8} \text{ bps}$.
Converting to Mbps, we get $\text{Throughput} = \frac{80,000,000}{8.8 \times 10^6} \text{ Mbps} = \frac{80}{8.8} \text{ Mbps} = \frac{800}{88} \text{ Mbps} = \frac{100}{11} \text{ Mbps}$.

To determine the forwarding table for $B3$, we must identify the root bridge and the spanning tree configuration:

1. The bridge with the lowest serial number is $B1$, so $B1$ is the root bridge.
2. For $B3$, the shortest path to the root $B1$ is through its port 3, which connects directly to the LAN segment containing $H3$ and $H4$. Thus, port 3 is the root port.
3. All traffic destined for hosts $H1, H2, H3,$ and $H4$ must be forwarded through the root port (port 3).
4. Traffic destined for hosts $H5, H6, H9,$ and $H10$ is forwarded through port 1, which connects $B3$ to the corresponding LAN segment.
5. Traffic destined for hosts $H7, H8, H11,$ and $H12$ is forwarded through port 2, which connects $B3$ to the corresponding LAN segment.
6. This configuration matches the mapping in option C.

The Ethernet frame standard mandates a $32$-bit Frame Check Sequence (FCS) at the trailer, which is implemented using a Cyclic Redundancy Check (CRC) to ensure data link layer integrity. Conversely, the IPv4 packet header contains a $16$-bit checksum field, which is calculated using a one's complement sum of the header data, rather than a CRC algorithm. While both fields serve to detect corruption, they utilize fundamentally different mathematical approaches, confirming that the Ethernet frame employs a CRC field while the IP packet employs a checksum field.

The spanning tree is constructed with $B1$ as the root bridge. Following the shortest path protocol, $B1$ connects directly to $B5$. $B5$ (port 3) has a path to $B3$ (port 4), making $B3$ a descendant of $B5$. $B3$ connects to the middle LAN, to which $B4$ is attached, establishing $B4$ as a descendant of $B3$. Finally, $B4$ connects to $B2$ through the lower LAN topology. The resulting tree hierarchy is $B1 \to B5 \to B3 \to B4 \to B2$. A depth-first traversal of this specific spanning tree path follows the order $B1, B5, B3, B4, B2$.

The probability of a successful transmission per attempt is $P_s = 1 - p = 1 - 0.2 = 0.8$.
In a stop-and-wait protocol, the number of transmission attempts for a single packet follows a geometric distribution with an expected value of $E = \frac{1}{P_s}$.
Therefore, the expected number of attempts required for one packet is $E = \frac{1}{0.8} = 1.25$.
For $M = 100$ packets, the total average number of transmission attempts is given by $M \times E = 100 \times 1.25 = 125$.