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

Congestion Control in the Transport Layer

Congestion occurs when the number of packets sent into the network exceeds its carrying capacity, causing queues at routers to overflow, packet loss, increased delay and reduced throughput. Congestion control is the set of mechanisms used to keep the offered load within the limits the network can handle.

Approaches

• Open-loop (prevention): Design decisions made in advance so congestion does not occur — admission control, traffic shaping, good retransmission and discard policies.
• Closed-loop (feedback-based): Detect congestion (via packet loss, delay, or explicit signals), feed that information back to the source, and reduce the sending rate.

TCP implements closed-loop congestion control using a congestion window (cwnd) with phases: Slow Start (cwnd grows exponentially), Congestion Avoidance (additive increase), and fast retransmit / fast recovery (multiplicative decrease on loss) — i.e. the AIMD principle.

Traffic Shaping

Traffic shaping regulates the average rate and burstiness of data injected into the network so that flows become smoother and more predictable.

1. Leaky Bucket Algorithm

Think of a bucket with a small hole at the bottom. Water (packets) may be poured in at any (bursty) rate, but it leaks out at a constant rate. If the bucket is full, incoming packets are discarded.

• The host writes packets into a finite queue (the bucket).
• The interface transmits at a fixed rate $\rho$ (one packet per tick, or a fixed number of bytes per tick), regardless of input burstiness.
• Output is perfectly smooth (constant rate).

Bursty input  -->  [ buffer / bucket ]  -->  constant-rate output
                 (overflow -> packets dropped)

Limitation: It enforces a rigid constant output rate and cannot allow short bursts even when the network is idle.

2. Token Bucket Algorithm

A bucket holds tokens that are generated at a constant rate of $r$ tokens/second, up to a maximum capacity of $b$ tokens. To send a packet (or one byte), the host must remove a token. If tokens are available, packets go out immediately; if the bucket is empty, the packet waits.

• Allows bursts up to the number of accumulated tokens (max $b$), so saved-up tokens permit a temporary high rate.
• Long-term average rate is limited to $r$.
• Maximum burst length $S$ (seconds) at line rate $M$ satisfies $b + r\,S = M\,S$, giving $S = \dfrac{b}{M - r}$.

Tokens added at rate r --> [ token bucket (cap b) ]
Packet sent only if a token is removed; idle time accumulates tokens -> bursts allowed

Comparison

Token bucket is more flexible and is preferred where bursty but bounded traffic is acceptable.

Domain Name System (DNS)

DNS is an application-layer protocol that provides a distributed, hierarchical database to translate human-readable domain names (e.g. www.example.com) into IP addresses (e.g. 93.184.216.34) and vice versa. It mainly uses UDP port 53 (TCP 53 for zone transfers / large responses).

Hierarchical Name Space

            . (root)
         /   |   \
      com   org   np ...        <- Top Level Domains (TLD)
      /
  example.com                  <- second-level domain
      |
  www.example.com              <- host

Types of DNS Servers

• Root servers – know the addresses of TLD servers.
• TLD servers – handle .com, .org, .np, etc.
• Authoritative servers – hold the actual records for a domain.
• Local / recursive resolver – the server a client queries first; it does the legwork.

Name Resolution (Recursive + Iterative)

1. The host asks its local DNS resolver for www.example.com.
2. If not cached, the resolver queries a root server, which replies with the .com TLD server.
3. The resolver queries the TLD server, which returns the authoritative server for example.com.
4. The resolver queries the authoritative server, which returns the IP address.
5. The resolver caches the result (per TTL) and returns it to the host.

Common resource records: A (IPv4), AAAA (IPv6), CNAME (alias), MX (mail), NS (name server), PTR (reverse lookup).

Dynamic Host Configuration Protocol (DHCP)

DHCP automatically assigns IP configuration (IP address, subnet mask, default gateway, DNS server) to hosts, removing the need for manual setup. It runs over UDP, with the server on port 67 and the client on port 68.

DORA Process (four-step handshake)

1. DISCOVER – The client, having no IP, broadcasts a DHCPDISCOVER to find any DHCP server.
2. OFFER – One or more servers reply with a DHCPOFFER proposing an available IP address and lease parameters.
3. REQUEST – The client broadcasts a DHCPREQUEST accepting one offer (and implicitly declining others).
4. ACK – The chosen server sends DHCPACK, confirming the lease; the client now uses the address.

Client                         Server
  | --- DHCPDISCOVER (bcast) ---> |
  | <---- DHCPOFFER ------------- |
  | --- DHCPREQUEST (bcast) ----> |
  | <---- DHCPACK --------------- |

Lease & Renewal

Addresses are leased for a finite time; the client tries to renew at ~50% of the lease (T1) and rebind at ~87.5% (T2). DHCP also supports RELEASE (give up the address) and uses a relay agent to forward broadcasts across subnets.

Benefits: centralized, error-free, automatic IP management and address reuse.

Switching Techniques

Switching determines how data is moved from a source to a destination across intermediate nodes in a network.

1. Circuit Switching

A dedicated end-to-end physical path is established between sender and receiver before any data is transferred, and it is reserved for the entire session (e.g. the traditional telephone network).

• Phases: circuit setup → data transfer → teardown.
• Advantages:
  • Fixed, guaranteed bandwidth and constant low delay (good for real-time voice).
  • No congestion once the circuit is set up; data arrives in order.
• Disadvantages:
  • Setup time before transmission begins.
  • Poor utilization — the channel is reserved even when idle.
  • Expensive; inefficient for bursty data traffic.

2. Message Switching

Uses a store-and-forward approach: the entire message is sent to the first node, stored completely, then forwarded to the next node, and so on, until it reaches the destination. No dedicated path is reserved.

• Advantages:
  • Better line utilization than circuit switching (links shared).
  • No connection setup needed; supports message priorities; can store messages if a link is busy.
• Disadvantages:
  • Each node needs large storage to hold whole messages.
  • High and variable delay (whole message stored at every hop) — unsuitable for real-time traffic.

3. Packet Switching

The message is divided into small packets, each with a header (addressing/sequence info), and packets are individually routed and store-and-forwarded.

• Datagram approach (connectionless): each packet routed independently; may arrive out of order (e.g. IP).
• Virtual circuit approach (connection-oriented): a logical path is set up; all packets follow the same route (e.g. Frame Relay, MPLS).
• Advantages:
  • Efficient link utilization via statistical multiplexing.
  • Robust — packets can take alternate routes around failures.
  • Lower delay than message switching (pipelining of small packets); no full dedicated reservation.
• Disadvantages:
  • Overhead per packet (headers); reordering/buffering needed for datagrams.
  • Variable delay (jitter) and possible congestion/loss.

Summary

Bandwidth

Bandwidth is the range of frequencies a channel can carry (measured in Hz), or equivalently the maximum data-carrying capacity of a link (measured in bits per second). Higher bandwidth means a higher achievable data rate.

Nyquist Theorem (noiseless channel)

For a noiseless channel of bandwidth $B$ Hz carrying signals with $L$ discrete levels, the maximum data rate is:

Example: a 3 kHz channel with 4 signal levels gives $C = 2 \times 3000 \times \log_2 4 = 12{,}000$ bps. It shows that increasing the number of levels increases capacity (but makes the receiver more error-prone).

Shannon's Theorem (noisy channel)

For a noisy channel, the maximum (theoretical) capacity depends on the signal-to-noise ratio $\dfrac{S}{N}$:

where $S/N$ is usually given in dB as $10\log_{10}(S/N)$.

Example: $B = 3000$ Hz with SNR = 30 dB ($S/N = 1000$): $C = 3000 \times \log_2(1001) \approx 30{,}000$ bps. Shannon gives the upper bound that no scheme can exceed; Nyquist tells how many levels to use to approach it.

Network Topologies

Topology is the physical or logical arrangement of nodes and links in a network.

1. Bus Topology

All devices connect to a single common backbone cable.

• Advantages: cheap, easy to install, uses less cable.
• Disadvantages: a backbone fault brings down the whole network; hard to troubleshoot; collisions limit performance.

2. Star Topology

All devices connect to a central hub/switch.

• Advantages: easy to add/remove nodes; a single node failure doesn't affect others; easy fault isolation.
• Disadvantages: central device failure disables the whole network; more cable; cost of the central device.

3. Ring Topology

Devices form a closed loop; data travels in one (or two) direction(s), often using a token.

• Advantages: orderly access (no collisions with token passing); performs well under heavy load.
• Disadvantages: a single break can disrupt the ring; adding/removing nodes disrupts the network.

4. Mesh Topology

Every node connects directly to many/all others.

• Advantages: highly robust/fault-tolerant; dedicated links give high throughput and security.
• Disadvantages: very expensive; lots of cabling and I/O ports; complex to install. (Full mesh needs $\frac{n(n-1)}{2}$ links.)

5. Tree (Hierarchical) Topology

Star networks connected in a hierarchy via a backbone.

• Advantages: scalable, easy to manage in segments.
• Disadvantages: failure of the root/backbone affects large parts; heavy cabling.

6. Hybrid Topology

Combination of two or more topologies (e.g. star-bus).

• Advantages: flexible, scalable, reliable.
• Disadvantages: complex design and higher cost.

Framing

Framing is a data-link-layer function that breaks the continuous bit stream from the physical layer into manageable frames, each with clear start and end boundaries, so the receiver can tell where one frame stops and the next begins. Delimiting is commonly done with a special flag pattern at the frame boundaries. The problem: the flag pattern may also appear inside the data, so stuffing is used to keep data transparent.

Bit Stuffing (bit-oriented framing, e.g. HDLC)

The flag is the bit pattern 01111110. To stop this pattern from accidentally appearing in the payload, the sender, after every five consecutive 1s in the data, inserts a 0. The receiver, on seeing five 1s followed by a 0, removes the stuffed 0.

Data:    0 1 1 1 1 1 1 0   (six 1s)
Sent:    0 1 1 1 1 1 0 1 0  (0 stuffed after five 1s)
Received bit stream is de-stuffed back to the original.

Byte (Character) Stuffing (byte-oriented framing, e.g. PPP)

Frames are made of bytes. A special FLAG byte marks the start/end. If the FLAG byte (or the ESC byte) appears in the data, the sender inserts a special escape (ESC) byte before it; the receiver removes the ESC byte to recover the original data.

FLAG | ... DATA (with ESC before any FLAG/ESC inside) ... | FLAG

Summary: Bit stuffing works at bit level (insert 0 after five 1s); byte stuffing works at byte level (insert ESC before special bytes). Both ensure the delimiter cannot be confused with payload data (data transparency).

Stop-and-Wait vs Sliding Window Protocols

Both are data-link/transport flow-control protocols, but they differ in how many frames may be outstanding (unacknowledged) at a time.

Efficiency

• Stop-and-Wait efficiency: $\eta = \dfrac{1}{1 + 2a}$, where $a = \dfrac{T_{prop}}{T_{trans}}$. For large $a$ (long links), efficiency is very low.
• Sliding Window efficiency: $\eta = \dfrac{W}{1 + 2a}$ (capped at 1), so a suitably large window $W \ge 1 + 2a$ keeps the link fully utilized.

Conclusion: Stop-and-Wait is simple but wastes bandwidth on links with significant propagation delay, whereas the sliding window protocol pipelines multiple frames to achieve much higher throughput.

Connection-Oriented vs Connectionless Services

Connection-Oriented Service

A logical connection is established between sender and receiver before data transfer, used during transfer, and released afterwards (setup → data transfer → teardown). It is modeled on the telephone system. Example: TCP.

Connectionless Service

No connection is set up; each packet (datagram) is sent independently with full addressing and routed on its own. Modeled on the postal system. Example: UDP / IP.

Comparison

In short: connection-oriented service trades higher overhead for reliability and ordering, while connectionless service trades reliability for speed and simplicity.

User Datagram Protocol (UDP)

UDP is a connectionless, unreliable transport-layer protocol. It sends data as independent datagrams with no connection setup, no acknowledgement, no retransmission, no flow control and no ordering. It only adds a small header providing port-based multiplexing and an optional checksum. Because of its low overhead, it is used where speed matters more than reliability — e.g. DNS, DHCP, VoIP, video/audio streaming, online games, SNMP.

UDP Header Format (8 bytes)

The header is only 8 bytes long and has four 16-bit fields:

 0                   16                  31
+------------------+------------------+
| Source Port (16) | Dest. Port (16)  |
+------------------+------------------+
| Length (16)      | Checksum (16)    |
+------------------+------------------+
|              Data ...               |
+-------------------------------------+

• Source Port (16 bits): port of the sending process (optional; may be 0).
• Destination Port (16 bits): port of the receiving process.
• Length (16 bits): total length of the UDP datagram (header + data) in bytes, minimum 8.
• Checksum (16 bits): error check over the header, data and a pseudo-header; optional in IPv4, mandatory in IPv6.

The simple 8-byte header (versus TCP's 20-byte header) is what gives UDP its low overhead and speed.

CIDR (Classless Inter-Domain Routing)

CIDR is an IP addressing scheme that replaces the rigid classful system (A, B, C) with flexible, variable-length prefixes. Instead of fixed 8/16/24-bit network parts, CIDR lets the network/host boundary fall at any bit position, written in slash notation as IP/n, where $n$ is the number of network (prefix) bits.

Notation

In 192.168.10.0/24, the /24 means the first 24 bits are the network prefix and the remaining 8 bits are for hosts. The subnet mask is 255.255.255.0.

• Number of host bits = $32 - n$.
• Number of addresses in the block = $2^{32-n}$ (usable hosts = $2^{32-n} - 2$).

Benefits

• Efficient address allocation — blocks can be sized to need, reducing IPv4 wastage.
• Route aggregation (supernetting) — many contiguous networks are summarized into one routing entry, shrinking routing tables.

Example

Given block 200.10.0.0/22:

• Prefix bits $n = 22 \Rightarrow$ host bits $= 32 - 22 = 10$.
• Total addresses $= 2^{10} = 1024$; usable hosts $= 1024 - 2 = 1022$.
• Subnet mask $= 255.255.252.0$ (first 22 bits set).
• Address range: 200.10.0.0 to 200.10.3.255 (the .0–.3 covers the 2 borrowed bits in the third octet).

Thus four old class-C networks (200.10.0.0/24 … 200.10.3.0/24) are aggregated into a single /22 route — illustrating CIDR's address-saving and route-summarization power.

Hub vs Switch vs Router

Summary

• A hub is a simple Layer-1 device that just repeats incoming signals to every port, causing collisions and wasted bandwidth.
• A switch is a smarter Layer-2 device that learns MAC addresses and sends each frame only to its intended port, eliminating unnecessary traffic and collisions.
• A router is a Layer-3 device that connects different networks, forwards packets based on IP addresses using a routing table, and separates broadcast domains (e.g. linking a LAN to the Internet).

Address Resolution Protocol (ARP)

ARP is a network-layer (between L2 and L3) protocol that maps a known logical IP address to its corresponding physical (MAC) address on a local network. It is needed because, even though devices are addressed logically by IP, actual frame delivery on a LAN (e.g. Ethernet) requires the destination's MAC address.

How ARP Resolves an IP to a MAC Address

1. A host wants to send a packet to a destination IP on the same local network but does not know its MAC address.
2. It first checks its ARP cache (a table of recently learned IP→MAC mappings). If found, it uses that MAC directly.
3. If not cached, the host broadcasts an ARP Request frame to all devices on the LAN (destination MAC = FF:FF:FF:FF:FF:FF), asking "Who has IP X? Tell me your MAC."
4. Every host receives it, but only the host that owns IP X replies.
5. That host sends a unicast ARP Reply back to the requester containing its MAC address.
6. The requester stores the mapping in its ARP cache (with a timeout) and uses the MAC to build and send the Ethernet frame.

Host A (broadcast):  "Who has 192.168.1.5? Tell 192.168.1.2"
Host B (unicast):    "192.168.1.5 is at AA:BB:CC:DD:EE:FF"

Related

• Proxy ARP: a router answers ARP on behalf of another host.
• RARP / DHCP do the reverse (MAC → IP).

If the destination is on a different network, the host instead resolves the default gateway's MAC via ARP and sends the packet there for routing.