GATE CS & IT Engineering Computer Networks Syllabus

Why do bridged/switched Ethernet networks run the Spanning Tree Protocol (STP)?

To eliminate loops in a topology with redundant links. Loops would cause broadcast storms and multiple frame copies; STP disables redundant ports to create a single loop-free active topology (a spanning tree) while keeping backups for failover.

Contrast a collision domain and a broadcast domain in switched Ethernet.

Each switch/bridge port is its own collision domain (full-duplex switching eliminates collisions). All ports of a switch are in one broadcast domain; a router (or VLAN boundary) separates broadcast domains.

State Dijkstra's algorithm time complexity for shortest paths and its key restriction.

With a binary heap, $O((V+E)\log V)$; with an adjacency-matrix/array, $O(V^{2})$. It computes single-source shortest paths but requires non-negative edge weights.

What is the Bellman-Ford equation that underlies distance-vector routing?

$d_x(y)=\min_{v}\{c(x,v)+d_v(y)\}$, where $d_x(y)$ is the least cost from $x$ to $y$, the minimum is over neighbors $v$, and $c(x,v)$ is the link cost from $x$ to neighbor $v$.

How does flooding forward packets, and what techniques prevent infinite duplication?

Flooding sends each incoming packet out on every link except the one it arrived on. To bound it: a hop-count/TTL field, sequence numbers to drop already-seen packets, or selective/reverse-path flooding.

In distance-vector routing, what is the count-to-infinity problem?

When a link fails, routers may slowly increment their distance estimates via each other (believing a path still exists), counting up toward infinity. It results from slow propagation of bad news in DV routing.

Name three techniques used to mitigate the count-to-infinity problem in distance-vector routing.

Split horizon (don't advertise a route back on the interface it was learned from), split horizon with poison reverse (advertise it back with infinite cost), and hold-down timers / triggered updates / defining a small value as infinity.

Compare distance-vector and link-state routing on what is shared and with whom.

Distance vector: each router shares its entire distance table only with directly-connected neighbors, periodically (e.g., RIP). Link state: each router floods the cost of only its directly-connected links to all routers, then each independently runs Dijkstra on the full topology (e.g., OSPF).

Which routing protocol family does RIP belong to, and what is its metric and infinity value?

RIP is a distance-vector protocol. Its metric is hop count, and it defines $16$ as infinity (unreachable), limiting network diameter to $15$ hops.

What is the size of an IPv4 address, the header's min/max length, and the total address space?

IPv4 addresses are $32$ bits, giving $2^{32}\approx 4.3\times 10^{9}$ addresses. The header is $20$ bytes minimum and $60$ bytes maximum (with options).

State the classful IPv4 ranges for Class A, B, and C and their default network mask lengths.

Class A: first bit $0$, $0.0.0.0$-$127.255.255.255$, mask $/8$. Class B: first bits $10$, $128.0.0.0$-$191.255.255.255$, mask $/16$. Class C: first bits $110$, $192.0.0.0$-$223.255.255.255$, mask $/24$.

For a CIDR block with prefix length $n$, how many total addresses and usable hosts does it contain (IPv4)?

Total addresses $=2^{32-n}$. Usable hosts $=2^{32-n}-2$ (subtracting the network address and the broadcast address).

Given the block $172.16.0.0/20$, how many addresses does it span and what is the subnet mask in dotted decimal?

$2^{32-20}=2^{12}=4096$ addresses ($4094$ usable). Mask $/20 = 255.255.240.0$.

What is the role of the subnet mask, and how is the network address obtained from an IP address?

The subnet mask separates network and host portions. The network (subnet) address is obtained by a bitwise AND of the IP address with the subnet mask.

What does ARP do, and at which layers does it operate?

Address Resolution Protocol maps a known IPv4 (layer-3) address to a MAC (layer-2) address on the same LAN. It works between the network and data link layers; the request is broadcast and the reply is unicast.

Describe the ARP request/reply mechanism briefly.

A host broadcasts an ARP request ("Who has IP X? Tell IP Y") to all stations on the LAN; only the host owning IP X replies with a unicast ARP reply containing its MAC address, which the requester caches in its ARP table.

What are the four messages in the DHCP address-assignment handshake (DORA)?

Discover (client broadcast), Offer (server offers an address), Request (client requests the offered address), Acknowledge (server confirms the lease). Order: Discover -> Offer -> Request -> Ack.

Why must the initial DHCP Discover message be broadcast, and what addresses are used?

The client has no IP address yet and doesn't know the server, so it broadcasts to $255.255.255.255$ with source $0.0.0.0$ so any DHCP server on the LAN can respond.

What is ICMP used for, and name two common ICMP message types.

Internet Control Message Protocol reports errors and provides diagnostics for IP. Common messages: Echo Request/Reply (used by ping), Destination Unreachable, Time Exceeded (used by traceroute), and Redirect.

How do ping and traceroute use ICMP?

Ping sends ICMP Echo Request and measures the Echo Reply round-trip time. Traceroute sends packets with increasing TTL; each router that drops a packet (TTL$=0$) returns an ICMP Time Exceeded, revealing the path hop by hop.

What is NAT, and what problem does it solve?

Network Address Translation maps multiple private IP addresses to one (or few) public IP address(es), conserving the scarce IPv4 public address space and adding isolation for the private network.

In NAPT (PAT), what does the NAT table use to distinguish multiple internal connections sharing one public IP?

It uses the combination of (public IP, port number): the NAT box rewrites the source IP and source port and records the mapping {private IP:port <-> public IP:new port}, demultiplexing returning traffic by the translated port.

What is the difference between flow control and congestion control?

Flow control prevents a fast sender from overwhelming a slow receiver (an end-to-end, receiver-driven limit). Congestion control prevents senders from overwhelming the network's internal capacity (router buffers/links).

In a sliding-window protocol, what window sizes do Go-Back-N and Selective Repeat use given an $n$-bit sequence-number field?

Go-Back-N: sender window up to $2^{n}-1$, receiver window $=1$. Selective Repeat: sender and receiver windows each up to $2^{n-1}$.

Define link utilization (efficiency) for a sliding-window protocol with window size $W$.

Efficiency $=\dfrac{W\cdot T_t}{T_t+2T_p}$ (capped at $1$), where $T_t$ is transmission time and $T_p$ is propagation delay. For full utilization, $W\geq \dfrac{T_t+2T_p}{T_t}=1+2a$ with $a=\frac{T_p}{T_t}$.

In TCP congestion control, how does the congestion window evolve in slow start versus congestion avoidance?

Slow start: cwnd grows exponentially, doubling each RTT until it reaches the threshold $ssthresh$. Congestion avoidance: cwnd grows linearly, increasing by about $1$ MSS per RTT (additive increase).

What is TCP's AIMD strategy and how does cwnd respond to loss events?

Additive Increase, Multiplicative Decrease: increase cwnd by $1$ MSS per RTT with no loss. On a triple duplicate ACK (fast recovery), set $ssthresh=\frac{cwnd}{2}$ and halve cwnd. On timeout, set cwnd to $1$ MSS and restart slow start.

What congestion-control function does the leaky bucket algorithm provide?

The leaky bucket shapes/polices traffic by outputting packets at a constant rate regardless of bursty input; packets that overflow the fixed-capacity bucket are discarded, smoothing flow into the network.

How does the token bucket differ from the leaky bucket for traffic shaping?

Token bucket allows bursts: tokens accumulate at a fixed rate up to capacity $b$, and a packet may be sent only if a token is available, so a burst of up to $b$ can be sent at once. Maximum output over time $t$ is bounded by $b+r\cdot t$ (token rate $r$). Leaky bucket enforces a strictly constant output rate with no bursts.

Distinguish 1-persistent, non-persistent, and p-persistent CSMA.

1-persistent: sense the channel and transmit immediately when idle (probability 1). Non-persistent: if busy, wait a random time then re-sense (fewer collisions, lower utilization). p-persistent (slotted): when idle, transmit with probability $p$ and defer to the next slot with probability $1-p$.

What is the maximum throughput efficiency of a non-persistent vs 1-persistent CSMA compared to ALOHA, qualitatively?

CSMA outperforms ALOHA because carrier sensing reduces collisions; non-persistent CSMA achieves higher maximum throughput than 1-persistent CSMA (which can approach high utilization at low load but degrades under heavy load), and both exceed slotted ALOHA's $\frac{1}{e}\approx 36.8\%$.