BSc CSIT (TU) Science Computer Networks (BSc CSIT, CSC258) Question Paper 2075 Nepal

Distance Vector Routing

Distance Vector (DV) routing is a distributed, iterative, and asynchronous routing algorithm in which each router maintains a routing table (the distance vector) listing, for every destination, the best known distance (cost/metric) and the next hop to reach it. It is based on the Bellman-Ford equation:

where $D_x(y)$ is the least cost from node $x$ to $y$, $c(x,v)$ is the cost of the direct link from $x$ to its neighbour $v$, and $D_v(y)$ is $v$'s estimate of the cost to $y$.

Working

1. Each router initializes its table with the cost to its directly connected neighbours (and $\infty$ to all others).
2. Periodically (e.g. every 30 s in RIP) each router sends its entire distance vector to its immediate neighbours.
3. On receiving a neighbour's vector, a router updates its table using the Bellman-Ford equation; if a lower-cost path is found, it records the new cost and the next hop.
4. The process repeats until the tables converge (no further changes). RIP is the classic example, using hop count as the metric with a maximum of 15.

Characteristics: simple, low overhead, but slow convergence and "routing by rumour" (a router trusts neighbours without knowing the full topology).

Count-to-Infinity Problem

When a link or router fails, the bad news (an increased/infinite cost) propagates slowly while good (but now stale) routes bounce back and forth between routers, each incrementing the cost by one in every exchange. The metric creeps upward step by step toward infinity instead of converging quickly.

Example: A — B — C. If the C–B link breaks, B should mark C unreachable. But A still advertises "I can reach C in 2 hops" (its route actually goes through B). B believes A, sets cost = 3, advertises it; A then raises to 4, and so on — the count climbs to infinity. This delays convergence and can cause routing loops.

Methods to Solve It

1. Defining a maximum (infinity): Treat a cost (e.g. 16 hops in RIP) as infinity. This bounds the counting but does not eliminate the loop.
2. Split Horizon: A router never advertises a route back over the interface from which it learned that route. (A does not tell B about C, since A's route to C is via B.)
3. Split Horizon with Poison Reverse: Instead of suppressing the route, the router advertises it back with a cost of infinity, explicitly poisoning it so the neighbour immediately knows the path is invalid.
4. Route Poisoning / Triggered Updates: When a route fails, the router immediately sets its cost to infinity and sends a triggered update without waiting for the periodic timer, speeding up propagation of bad news.
5. Hold-down timers: A router ignores updates about a recently-failed route for a fixed period, preventing stale information from reinstating it.

Subnetting a Class B Network into 4 Subnets

Take the Class B network 172.16.0.0 with the default mask 255.255.0.0 (/16). The default network bits = 16, host bits = 16.

Step 1 — Bits to borrow

To create at least 4 subnets we need $2^n \geq 4 \Rightarrow n = 2$ bits borrowed from the host part.

• New prefix length = $16 + 2 = 18$ → mask /18
• Number of subnets = $2^2 = 4$
• Host bits remaining = $32 - 18 = 14$ → hosts per subnet = $2^{14} - 2 = 16382$

Step 2 — New Subnet Mask

The third octet borrows the two high-order bits: 11000000 = 192.

Block size in the third octet = $256 - 192 = 64$.

Step 3 — Subnet ID and Broadcast Address of Each Subnet

Result: New subnet mask = 255.255.192.0 (/18), giving 4 subnets each with 16,382 usable hosts, with the subnet IDs and broadcast addresses shown above.

TCP (Transmission Control Protocol)

TCP is a connection-oriented, reliable, byte-stream transport-layer protocol (RFC 793). It provides reliable in-order delivery using sequence/acknowledgement numbers, retransmission, flow control (sliding window) and congestion control. It is full-duplex and uses port numbers for process-to-process delivery.

TCP Segment Structure

The TCP header is 20 bytes (minimum), up to 60 bytes with options.

Three-Way Handshake (Connection Establishment)

1. SYN: Client sends a segment with SYN = 1 and an initial sequence number seq = x.
2. SYN + ACK: Server replies with SYN = 1, ACK = 1, its own seq = y, and ack = x + 1.
3. ACK: Client sends ACK = 1, seq = x + 1, ack = y + 1.

The connection is now ESTABLISHED and data transfer can begin. The handshake synchronizes sequence numbers on both ends.

Connection Termination (Four-Way Handshake)

Because TCP is full-duplex, each direction is closed independently:

1. FIN from the initiator (e.g. client), FIN = 1.
2. ACK from the server acknowledging the FIN.
3. FIN from the server when it has finished sending.
4. ACK from the client; it then enters the TIME-WAIT state (2×MSL) before fully closing, to ensure the final ACK is delivered and old segments expire.

Framing

Framing is the data-link-layer function of dividing the continuous bit stream received from the network layer into manageable, discrete units called frames, each with a clearly identifiable beginning and end so the receiver can distinguish one frame from the next. A frame typically carries a header, the payload, and a trailer (often with an error-check field).

To mark frame boundaries, a special flag byte/bit pattern (e.g. 01111110) is placed at the start and end. The problem is that the same pattern may appear inside the data; stuffing solves this.

Bit Stuffing

Used in bit-oriented protocols (e.g. HDLC) where the flag is 01111110 (six consecutive 1s).

• Sender: Whenever it transmits five consecutive 1s in the data, it automatically inserts (stuffs) a 0 after them, so the flag pattern can never appear in the payload.
• Receiver: On detecting five consecutive 1s followed by a 0, it removes (de-stuffs) the 0.

Example: Data 0111111 → transmitted as 01111011 (a 0 stuffed after the five 1s).

Byte (Character) Stuffing

Used in byte-oriented protocols (e.g. PPP). A special flag byte marks frame boundaries, and an escape (ESC) byte handles data that contains the flag.

• Sender: If a FLAG or ESC byte occurs inside the data, an ESC byte is inserted before it.
• Receiver: Removes the ESC byte and treats the following byte as data, not a delimiter.

Byte stuffing works on whole bytes, whereas bit stuffing works at the bit level and adds less overhead.

Stop-and-Wait vs Sliding Window Protocol

Summary: Stop-and-Wait sends one frame and waits, making it simple but inefficient. Sliding Window allows several frames to be outstanding, greatly improving link utilization and throughput, at the cost of more buffering and sequence-number management.

Connection-Oriented vs Connectionless Services

Summary: A connection-oriented service is like a telephone call — connect, talk, hang up — providing reliable ordered delivery. A connectionless service is like sending postcards — each is addressed and sent independently with no guarantee of order or arrival.

UDP (User Datagram Protocol)

UDP is a connectionless, unreliable, message-oriented transport-layer protocol (RFC 768). It provides minimal services on top of IP: process-to-process delivery via port numbers and an optional checksum. It has no handshake, sequencing, acknowledgement, flow control or congestion control, so it is fast and low-overhead — suitable for DNS, DHCP, TFTP, SNMP, VoIP, online gaming and streaming where speed matters more than guaranteed delivery.

UDP Header Format

The UDP header is fixed at 8 bytes, consisting of four 16-bit fields:

Layout (each row = 16 bits):

 0               15 16              31
+-----------------+-----------------+
|  Source Port    | Destination Port|
+-----------------+-----------------+
|     Length      |    Checksum     |
+-----------------+-----------------+
|            Data (payload)         |
+-----------------------------------+

The small fixed 8-byte header is why UDP is lightweight compared to TCP's 20-byte header.

CIDR (Classless Inter-Domain Routing)

CIDR is an IP addressing and route-aggregation scheme (RFC 1519) that removes the rigid Class A/B/C boundaries and allows the network/host split to occur at any bit position, specified by a prefix length written in slash notation a.b.c.d/n, where $n$ is the number of network (prefix) bits.

Key Ideas

• The mask can be any value $0 \le n \le 32$, not just /8, /16, /24.
• Number of addresses in a block = $2^{32-n}$.
• Route aggregation (supernetting): many contiguous networks are advertised as a single prefix, shrinking routing tables and conserving IPv4 addresses.

Example

Consider 192.168.16.0/20.

• Prefix length $n = 20$ → host bits = $32 - 20 = 12$.
• Mask = 11111111.11111111.11110000.00000000 = 255.255.240.0.
• Block size = $2^{12} = 4096$ addresses (4094 usable hosts).
• Address range = 192.168.16.0 to 192.168.31.255.

This single /20 block aggregates sixteen /24 networks (192.168.16.0/24 … 192.168.31.0/24) into one routing-table entry, demonstrating CIDR's efficient address use and supernetting benefit.

Hub vs Switch vs Router

Summary: A hub blindly repeats bits to every port; a switch intelligently forwards frames using MAC addresses within one network; a router routes packets between different networks using IP addresses and separates broadcast domains.

ARP (Address Resolution Protocol)

ARP is a network-layer protocol (RFC 826) used to map a known logical (IP) address to its corresponding physical (MAC/hardware) address on a local area network. Because data-link delivery on an Ethernet LAN requires the destination MAC address, ARP resolves the next-hop IP into the MAC needed to build the frame.

How ARP Resolves IP → MAC

1. Cache check: When a host wants to send a packet to a target IP on the same LAN, it first checks its ARP cache (a table of recent IP→MAC mappings). If found, it uses it directly.
2. ARP Request (broadcast): If not cached, the host broadcasts an ARP Request frame to MAC address FF:FF:FF:FF:FF:FF (all hosts on the LAN). It contains the sender's IP & MAC and the target IP, asking "Who has IP X? Tell me your MAC."
3. Processing: Every host on the LAN receives the broadcast, but only the host whose IP matches the target IP responds.
4. ARP Reply (unicast): The target host replies directly (unicast) to the requester with an ARP Reply containing its MAC address.
5. Caching: The requesting host stores the IP→MAC mapping in its ARP cache (with a timeout) so future packets need no new request, then encapsulates the IP packet in a frame addressed to that MAC.

If the destination is on a different network, ARP resolves the MAC of the default gateway (router) instead of the final host.

HTTP (HyperText Transfer Protocol)

HTTP is the application-layer, request–response protocol used by the World Wide Web to transfer hypermedia resources (HTML, images, etc.) between a client (browser) and a web server. It runs over TCP, typically on port 80 (HTTPS on 443), and is stateless — each request is independent (state is maintained externally via cookies/sessions).

Working of HTTP

1. Connection: The client opens a TCP connection to the server (three-way handshake) on port 80.
2. Request: The browser sends an HTTP request message consisting of:
   • A request line — method (GET, POST, PUT, DELETE, HEAD…), the URL/path, and the HTTP version.
   • Headers — e.g. Host, User-Agent, Accept.
   • An optional body (e.g. form data in a POST).
3. Processing: The server locates/processes the requested resource.
4. Response: The server returns an HTTP response message with:
   • A status line — HTTP version and a status code (e.g. 200 OK, 301 Moved, 404 Not Found, 500 Server Error).
   • Headers — e.g. Content-Type, Content-Length, Date.
   • A body — the requested content (HTML, image, JSON, etc.).
5. Connection handling:
   • Non-persistent (HTTP/1.0): a separate TCP connection per object.
   • Persistent (HTTP/1.1, keep-alive): one connection reused for multiple requests, improving efficiency.
6. The browser renders the received content; cookies may carry state across requests.

NAT (Network Address Translation)

NAT is a technique (RFC 1631/3022) that translates private IP addresses into public IP addresses (and vice-versa) at a router/firewall boundary. It lets many hosts on a private network (e.g. 192.168.x.x) share one or a few public IP addresses to access the Internet, conserving the limited IPv4 address space and adding a layer of security by hiding internal hosts.

Types of NAT

1. Static NAT: A one-to-one fixed mapping between a private IP and a public IP. Used when an internal server must be permanently reachable from outside.
2. Dynamic NAT: Private IPs are mapped to public IPs drawn from a pool, assigned on demand. The mapping is temporary and changes per session.
3. PAT (Port Address Translation) / NAT Overload: Many-to-one — many private IPs share a single public IP, distinguished by different port numbers. This is the most common form (home/office routers).

Uses of NAT

• Conserves public IPv4 addresses — many hosts share few public IPs.
• Security / privacy — internal IP structure is hidden from the outside.
• Easier renumbering / flexibility — internal addressing can change without affecting external addresses.
• Allows organizations to use private address ranges internally while still reaching the public Internet.