Data Link Layer Practice Questions

To calculate the effective data rate, we first determine the time required for a single transmission cycle.

1. The transmission time ($t_{trans}$) for a frame of $L = 1000 \text{ bytes} = 8000 \text{ bits}$ at a bandwidth $R = 10 \text{ Mbps}$ is:
   $t_{trans} = \frac{L}{R} = \frac{8000 \text{ bits}}{10 \times 10^6 \text{ bps}} = 800 \mu s$
2. In a token ring, the cycle time includes the transmission time and the overhead to circulate the frame and release the token, typically modeled as $2 \times t_{prop}$ (where $t_{prop} = 400 \mu s$):
   $T_{total} = t_{trans} + 2 \times t_{prop} = 800 \mu s + 2 \times 400 \mu s = 1600 \mu s$
3. The effective data rate is the data transmitted per total cycle time:
   $\text{Effective Data Rate} = \frac{L}{T_{total}} = \frac{8000 \text{ bits}}{1600 \times 10^{-6} \text{ s}} = 5 \times 10^6 \text{ bps} = 5 \text{ Mbps}$

Let's analyze each statement regarding cache and TLB:
(A) "The TLB performs an associative search in parallel on all its valid entries using page number of incoming virtual address." This statement is TRUE. TLBs (Translation Lookaside Buffers) are typically implemented as associative caches, allowing simultaneous comparison of the incoming virtual page number with all entries in the TLB to find a match quickly.
(B) "If the virtual address of a word given by CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory." This statement is TRUE. A TLB hit means that the translation from virtual address to physical address was found, and the corresponding page is present in a physical frame in main memory. Even if the data itself is not in the CPU cache (cache miss), it must reside in main memory because its page address translation was successful.
(C) "The memory access time using a given inverted page table is always same for all incoming virtual addresses." This statement is FALSE. In an inverted page table, page numbers are searched by hashing the virtual page number. If a hash collision occurs, a linked list (or similar data structure) needs to be traversed, which takes variable time depending on the length of the collision chain. Therefore, access time is not always the same for all virtual addresses.
(D) "In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same." This statement is FALSE. If two distinct virtual addresses V1 and V2 map to the same hash value (a collision), then the page table lookup will involve traversing a chain of entries at that hash location. While the overall lookup time for different addresses might vary if one has a longer chain than the other, it's not guaranteed that these specific two addresses will have different memory access times. If they both end up at the same slot and are found at the beginning of their respective chains after the initial hash, their access times could be similar. However, the more crucial point of a hashed page table is that access time is not constant for all addresses due to potential collisions and varying chain lengths. The statement says "will not be the same," which implies they must be different. It's possible for them to take the same amount of time if they are both the first entries in a collision chain, for example. The variability comes from different chain lengths, not necessarily from these two colliding addresses always taking different times.

The question asks for the statement that is FALSE. Statement (C) is definitively false because of hash collisions. Statement (D) is also false as access times for colliding entries might be the same. The solution points to C.

For $CSMA/CD$, the packet transmission time must be at least the round-trip propagation time, calculated as $2 \times T_p = 2 \times \frac{L}{v}$.
Substituting the given values $L = 2 \times 10^3 \text{ m}$ and $v = 2 \times 10^8 \text{ m/s}$, the propagation delay is $T_p = \frac{2 \times 10^3 \text{ m}}{2 \times 10^8 \text{ m/s}} = 10^{-5} \text{ s}$.
The total round-trip time is $2 \times T_p = 2 \times 10^{-5} \text{ s}$.
The minimum packet size in bits is $\text{Bandwidth} \times (2 \times T_p) = 10^7 \text{ bps} \times 2 \times 10^{-5} \text{ s} = 200 \text{ bits}$.
Converting this to bytes, we get $\frac{200 \text{ bits}}{8 \text{ bits/byte}} = 25 \text{ bytes}$.
Since $25 \text{ bytes}$ is not listed among the given options, the correct answer is D.

Given $N=5$, packet size $L=1000$ bytes, transmission time $T_t=50 \mu s$, and propagation delay $T_p=200 \mu s$.
The time required to transmit a full window of $N$ packets and receive the corresponding acknowledgments is the round-trip cycle time:
$T_{cycle} = T_t + 2 \times T_p = 50 \mu s + 2(200 \mu s) = 450 \mu s$
Since $N=5$ packets are sent per cycle, the total data transmitted is $N \times L = 5 \times 1000 = 5000$ bytes.
The maximum achievable throughput is calculated as:
$\text{Throughput} = \frac{N \times L}{T_{cycle}} = \frac{5000 \text{ bytes}}{450 \times 10^{-6} \text{ s}} \approx 11.11 \times 10^6 \text{ Bps}$

The distance of a block code is defined as the minimum Hamming distance $d_{min}$ between any two distinct codewords. Given the code $\{C_1=000000, C_2=010101, C_3=000111, C_4=011001, C_5=111111\}$, we calculate the Hamming distance $d(C_i, C_j)$ (the number of positions where bits differ) for various pairs:
$d(C_1, C_2) = 3$
$d(C_2, C_3) = d(010101, 000111) = 2$
$d(C_2, C_4) = d(010101, 011001) = 2$
Since the smallest calculated distance between any two distinct codewords is 2, the minimum distance of the code is $d_{min} = 2$.

In asynchronous serial communication, the transmitter and receiver do not share a common clock signal. To interpret the incoming stream of $bits$ correctly, the receiver must identify the exact boundaries of each data frame. The "Start" bit serves as a trigger for the receiver to begin sampling, while the "Stop" bit signals the completion of that data frame. This framing process aligns the receiver's timing with the incoming $bit$ sequence, ensuring data is processed without clock drift. Therefore, these bits are strictly for synchronization between the two devices.

In asynchronous serial communication, the transmitter and receiver do not share a common clock signal. The 'start bit' notifies the receiver of the beginning of a data $frame$, while the 'stop bit' indicates the end, allowing the receiver to re-align its sampling clock with the incoming $bit$ stream. This fundamental process of timing alignment between devices is known as synchronization. Since start and stop bits do not perform error handling (A, B) or serve to slow down transmission (D), their primary and sole purpose in this context is ensuring timing alignment.

Ethernet II frame structure: Preamble (7 bytes of 10101010): synchronizes receiver clock. SFD - Start Frame Delimiter (1 byte: 10101011): signals start of frame. Destination MAC (6 bytes): target hardware address. Source MAC (6 bytes): sender hardware address. EtherType (2 bytes): identifies the Network Layer protocol (0x0800=IPv4, 0x0806=ARP, 0x86DD=IPv6). Data (46-1500 bytes): if data < 46 bytes, padding is added to meet minimum frame size. FCS - Frame Check Sequence (4 bytes): CRC-32 for error detection. Total minimum frame: 64 bytes (header + min data + FCS). Maximum: 1518 bytes.

CRC is standard error detection method.

The hidden terminal problem: Station A and C are both in range of B but not of each other. A transmits to B while C (unaware of A's transmission) also transmits to B - causing a collision at B. RTS/CTS solves this: A sends RTS to B; B broadcasts CTS (heard by all stations in B's range, including C); C hears CTS and defers transmission for the duration of A's data + ACK. This effectively reserves the channel. RTS/CTS adds overhead and is only beneficial for large frames where the overhead is amortized. The RTS threshold in 802.11 sets the minimum frame size that triggers RTS/CTS.

A: TRUE - bridges/switches operate at Layer 2 (MAC addresses); routers operate at Layer 3 (IP addresses). This is the fundamental distinction. C: TRUE - a bridge extends the broadcast domain (broadcasts propagate through bridges to all connected segments); a router separates broadcast domains (broadcasts do not cross router interfaces, since routers do not forward broadcast frames). B: FALSE - it is bridges (transparent to network layer protocols) that can connect heterogeneous LANs; routers must understand network-layer protocols on each interface. D: Partially true for intra-network forwarding, but bridges forward within the same network; routers are used for inter-network forwarding.

CRC degree = 4 (degree of G(x) = x⁴+x+1). Number of CRC bits appended = degree of G(x) = 4 bits. Data bits = 8 bits (10110011). Transmitted frame = data bits + CRC bits = 8 + 4 = 12 bits. The process: append 4 zeros to data (10110011 0000 = 12 bits), divide by G(x) = 10011 using XOR division, the 4-bit remainder is the CRC. The transmitted frame is the original 8 data bits followed by the 4 CRC bits = 12 bits total.

In IEEE 802.11 CSMA/CA DCF (Distributed Coordination Function): DIFS (DCF InterFrame Space) is the mandatory idle period a station must observe before attempting a new transmission. After a station determines the channel is idle, it waits DIFS time. If still idle after DIFS, it starts its random backoff counter. SIFS (Short IFS) < DIFS is used for high-priority responses (ACKs, CTS) to ensure the ACK sender can transmit before other stations' DIFS timers expire. The IFS hierarchy: SIFS < PIFS < DIFS, creating a priority scheme for channel access.

Without STP, redundant links in a switched network create loops. A broadcast frame entering a loop circulates forever, causing a broadcast storm that saturates all links and crashes the network. STP (IEEE 802.1D) prevents this: (1) Elect a root bridge (lowest Bridge ID = priority + MAC address). (2) Each non-root switch selects one root port (toward root bridge). (3) Each LAN segment selects one designated port. (4) All other ports are blocked (not forwarding). This creates a spanning tree - loop-free logical topology while maintaining path redundancy. RSTP (802.1w) is a faster convergence version.

A: TRUE - a switch reads the destination MAC address of each frame and forwards it only to the appropriate port using a MAC address table (CAM table); a hub is a physical layer device that simply repeats all incoming bits to all ports (electrical signal amplification). C: TRUE - each switch port is its own collision domain (full-duplex links have no collisions); a hub creates a single shared collision domain across all ports. D: TRUE - a switch filters frames (only forwarding to the correct port) and can selectively drop unknown or unwanted frames; a hub has no such intelligence. B: FALSE - a switch operates at the Data Link Layer (Layer 2), not the network layer.

Pure ALOHA maximum throughput = 1/(2e) ≈ 0.184 ≈ 18.4%. The throughput formula is S = G × e^(-2G) where G is the offered load. Maximum throughput occurs at G = 0.5: S = 0.5 × e^(-1) = 1/(2e) ≈ 18.4%. Slotted ALOHA achieves twice the throughput: S = G × e^(-G), maximum at G=1: S = 1/e ≈ 36.8% ≈ 37%. Pure ALOHA is less efficient because a frame can be collided not only by frames started simultaneously, but also by frames started up to one frame-time earlier or later (vulnerable period = 2T vs T for slotted).

ARP (Address Resolution Protocol) translates a known IP address to its corresponding MAC (hardware) address within the same local network (broadcast domain). Process: (1) Host A wants to send to IP 192.168.1.5 but doesn't know its MAC. (2) A broadcasts ARP Request: 'Who has 192.168.1.5? Tell 192.168.1.1'. (3) Host with IP 192.168.1.5 responds with ARP Reply: 'I have 192.168.1.5, my MAC is XX:XX:XX:XX:XX:XX'. (4) A caches this mapping in its ARP table. Reverse ARP (RARP) and InARP do the reverse. ARP only works within a single broadcast domain (subnet).

CRC is used for error detection at data link layer.

Frequency division is a channel multiplexing technique (physical layer), not a framing technique. The four main framing techniques are: byte count, flag bytes with bit stuffing, byte stuffing, and physical layer coding violations.