Enlarged Diagram
Interactive Study Environment β€’ APJ Abdul Kalam Technological University
KTU 2024 SCHEME 18 CONTACT HOURS THEORY MASTERCLASS

Module 2: Transport Layer and Network Layer

The largest, highest-weightage module in Computer Networks. Covers Transport Protocols (UDP, TCP, Congestion Control), Network Layer (IPv4, CIDR, Subnetting, NAT), Unicast Routing (RIP, OSPF, BGP), Multicast Routing (DVMRP, PIM), IPv6, and Quality of Service (QoS).

119 Pages
Official PDF Notes Synthesized
167 Figures
High-Res Diagrams Embedded
12 Parts
Step-by-Step Learning Progression
100% Theory
Hands-on Code Excluded (KTU Rule)
OFFICIAL UNIVERSITY NOTES ORIGINAL EMBEDDED PDF

CN Module 2.pdf (119 Pages)

β†— Open in New Window ⬇ Download PDF

Scroll and read through your original 119-page lecture notes directly below, or reference them alongside each interactive concept in the study guide.

PART 01 CORE FOUNDATION β€’ 3M / 6M

Transport Layer Services & Principles

PDF Pages: 1 – 6
πŸ’‘ What is the Transport Layer?

While the Network Layer provides host-to-host communication (delivering datagrams between computers), the Transport Layer provides process-to-process logical communication (delivering messages between specific running programs on those computers).

1. Addressing: Port Numbers & Sockets

Operating systems run dozens of application processes simultaneously. To route data to the correct application, the transport layer uses Port Numbers (16-bit integers ranging from 0 to 65535):

Port RangeCategory NameUsage & Authority
0 – 1023Well-Known / Standard PortsAssigned and controlled by IANA for standard universal server services (HTTP = 80, HTTPS = 443, FTP = 20/21, SMTP = 25, DNS = 53).
1024 – 49151Registered PortsNot assigned automatically; organizations can register them with IANA to avoid conflicts.
49152 – 65535Dynamic / Private / EphemeralAssigned dynamically by the local OS to client processes for the duration of a session.
Port Addressing
Figure 1.1: Process-to-Process Communication via Port Addressing (Page 1)
πŸ”‘ Core Concept: Socket Address

A Socket Address is the unique combination of an IP Address (identifying the host machine on the network) and a Port Number (identifying the specific application process within that host):

\(\text{Socket Address} = (\text{IP Address}, \text{Port Number})\)

A full-duplex communication channel is uniquely identified globally by a Socket Pair (5-tuple: Source IP, Source Port, Destination IP, Destination Port, Transport Protocol).

2. Multiplexing and Demultiplexing

Multiplexing and Demultiplexing
Figure 1.2: Multiplexing at Sender and Demultiplexing at Receiver (Page 2)

3. Core Transport Services: Flow, Error & Congestion Control

ServiceProblem AddressedMechanism Used
Flow Control Prevents a fast sender from overwhelming a slow receiver's buffer. Feedback from receiver indicating available buffer capacity (Sliding Window, Window Size advertisements).
Error Control Detects corrupted, lost, duplicate, or out-of-order packets. Error-detection Checksums, Acknowledgments (ACK / NAK), Sequence Numbers, and Retransmission Timers.
Congestion Control Prevents senders from injecting too much traffic into the intermediate network routers. Congestion Window (\(\text{cwnd}\)), Slow Start, AIMD (Additive Increase Multiplicative Decrease).
Flow Control Buffer
Figure 1.3: Flow Control Buffer at Receiver (Page 3)
Error Control Mechanisms
Figure 1.4: Error Control: Sequence Numbers & ACKs (Page 4)
PART 02 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Transport Layer Protocols: Stop-and-Wait, Go-Back-N & Selective Repeat

PDF Pages: 7 – 18
πŸ’‘ Evolution of Transport Protocols

To achieve reliable transmission over an unreliable underlying network, protocols evolved from simple Stop-and-Wait to sophisticated sliding-window pipelined protocols: Go-Back-N (GBN) and Selective Repeat (SR).

1. Stop-and-Wait Protocol

Sender transmits one packet and stops. It waits until an acknowledgment (ACK) is received before sending the next packet. Uses 1-bit sequence numbers (0 and 1).

Stop and Wait Working
Figure 2.1: Stop-and-Wait Protocol Packet Exchange & Timeout (Page 7)

2. Go-Back-N (GBN) vs. Selective Repeat (SR / Selective-Repeat Protocol)

Selective-Repeat (SR) allows the receiver to accept out-of-order packets and send a Negative ACK (NAK) to request only missing frames.

Comparison Parameter Go-Back-N (GBN) Selective Repeat (SR)
Sender Window Size (\(W_s\)) \(W_s < 2^m\) (Max \(2^m - 1\) for \(m\)-bit sequence numbers). \(W_s \le 2^{m-1}\) (Half of the sequence number space).
Receiver Window Size (\(W_r\)) Always 1 (Accepts only the strictly expected packet). Equal to Sender Window: \(W_r = 2^{m-1}\).
Out-of-Order Packets Discarded immediately. Buffered in receiver buffer until missing packet arrives.
Acknowledgment Type Cumulative ACK: ACK \(n\) confirms all packets up to \(n-1\). Individual ACK: ACKs each successfully received packet.
Retransmission Behavior Retransmits all \(N\) unacknowledged packets in the window upon timeout ("Go-Back-N"). Retransmits only the specific timed-out packet.
Complexity & Memory Simple receiver; zero buffering needed at receiver. Complex receiver; requires buffering and individual packet timers.
Go-Back-N Sliding Window
Figure 2.2: Go-Back-N Sliding Window at Sender (Page 11)
GBN Packet Loss Retransmission
Figure 2.3: GBN Packet Loss: Discarding Out-of-Order Packets (Page 11)
πŸ“ High-Frequency KTU Question: Why Must \(W_s < 2^m\) in Go-Back-N?

If window size \(W_s = 2^m\), suppose the sender sends packets \(0\) to \(2^m - 1\). All packets arrive safely, but all ACKs are lost. The sender times out and re-sends packet \(0\). However, the receiver's window has already advanced to the next cycle and is expecting packet \(0\) of the *next* round! The receiver cannot distinguish between a retransmitted duplicate and a brand-new packet. Hence, \(W_s \le 2^m - 1\).

PART 03 CORE PROTOCOL β€’ 3M / 5M

User Datagram Protocol (UDP)

PDF Pages: 19 – 22
πŸ’‘ What is UDP?

UDP is an extremely lightweight, connectionless, unreliable transport protocol. It provides minimal transport service beyond IP: port addressing and optional error detection via checksum.

1. UDP Header Format (8 Bytes Fixed)

The UDP header is strictly 8 bytes (64 bits) long, divided into four 16-bit fields:

UDP Header Format
Figure 3.1: 8-Byte Fixed UDP Header Format (Page 20)
Header FieldLengthDescription & Purpose
Source Port16 bitsPort number of the sending process (optional; set to 0 if no reply is expected).
Destination Port16 bitsPort number of the receiving process (mandatory for delivery).
Total Length16 bitsTotal length of UDP user datagram in bytes (\(\text{Header} + \text{Data}\)). Minimum value = 8.
Checksum16 bitsOptional in IPv4 (all 0s if unused), mandatory in IPv6. Covers UDP pseudo-header, header, and data.
πŸ“ High-Frequency KTU Numerical: Maximum UDP Payload Size

Since the IP Total Length field is 16 bits, the maximum size of an IP datagram is \(2^{16} - 1 = 65535\) bytes. Subtracting the minimum 20-byte IP header and the 8-byte UDP header:

\[M_{\text{max}} = 65535 - 20 - 8 = \mathbf{65507 \text{ bytes}}\]

2. Checksum Calculation & The Pseudo-Header

To detect errors, UDP computes a 16-bit One's complement (1's complement) sum using Protocol 17. It includes a 12-byte Pseudo-Header borrowed from the IP layer (Source IP, Destination IP, All 0s, Protocol = 17, UDP Length) to verify that the datagram reached the correct destination host!

3. Why Choose UDP Over TCP? & UDP Datagram vs. TCP Segment

The transport PDU in UDP is formally known as a UDP Datagram (or User Datagram). Unlike TCP, UDP provides no connection setup, no flow control, and no retransmissions, leading to extremely low overhead:

FeatureUDP DatagramTCP Segment
ConnectionConnectionless (no handshake)Connection-oriented (three-way handshake)
Header Overhead8 bytes fixed20 – 60 bytes
ReliabilityUnreliable (best-effort, no ACKs)Reliable (sequence numbers, ACKs, retransmissions)
Flow / CongestionNone (transmits as fast as app feeds)Sliding window flow & AIMD congestion control
Data StreamPreserves message boundaries (datagrams)Byte-stream oriented (no message boundaries)
Use CasesDNS, DHCP, SNMP, VoIP, live streamingHTTP/HTTPS, FTP, SMTP, SSH
PART 04 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Transmission Control Protocol (TCP): Architecture & Connection

PDF Pages: 22 – 31
πŸ’‘ What is TCP?

TCP is a connection-oriented, reliable, byte-stream transport protocol. It provides full-duplex communication and creates the illusion of an unbroken logical "tube" carrying data between two processes.

🌊 Core TCP Features: Stream-Oriented & Full-Duplex

TCP provides a Stream-oriented (byte-stream) service. Applications write a continuous sequence of bytes into the TCP socket, and TCP packages these bytes into segments. Each byte is numbered using an Initial Sequence Number (ISN).

1. TCP Segment Format (20 to 60 Bytes)

The TCP header has a minimum length of 20 bytes and a maximum of 60 bytes (depending on optional fields):

TCP Segment Header Format
Figure 4.1: TCP Segment Header Format (Page 25)
Field NameBit WidthTechnical Description
Source Port / Dest Port16 bits eachIdentifies sending and receiving application process.
Sequence Number32 bitsByte sequence number of the first data byte in this segment.
Acknowledgment Number32 bitsCumulative ACK: contains the next expected byte number from sender. Valid if ACK flag = 1.
HLEN (Header Length / Data offset)4 bitsSpecifies number of 4-byte words in header. Range 5 to 15 (i.e., \(5 \times 4 = 20\) to \(15 \times 4 = 60\) bytes).
Reserved6 bitsReserved for future use.
Control Flags (URG, ACK, PSH, RST, SYN, FIN)6 bits (1 bit each) URG: Urgent pointer valid.
ACK: Acknowledgment number valid.
PSH: Push data immediately to application.
RST: Reset/abort connection.
SYN: Synchronize sequence numbers during connection establishment.
FIN: Terminate connection; no more data from sender.
Window Size (rwnd)16 bitsReceiver's advertised buffer space in bytes for flow control (max 65,535 bytes without scaling).
Checksum16 bitsMandatory error detection over pseudo-header, TCP header, and data.
Urgent Pointer16 bitsOffset added to sequence number pointing to end of urgent data (if URG = 1).
Options & Padding0 – 40 bytesOptional parameters (e.g., Maximum Segment Size / MSS, Window Scaling, Timestamps).

2. TCP Connection Establishment: Three-Way Handshake

  1. Step 1 (SYN segment from Client to Server): Client chooses an Initial Sequence Number (\(ISN_c = x\)), sets flag SYN = 1. Consumes 1 sequence number. Carries no data.
  2. Step 2 (SYN + ACK segment from Server to Client): Server allocates buffers, chooses its own sequence number (\(ISN_s = y\)), sets SYN = 1 and ACK = 1, and confirms client sequence by setting \(\text{ACK Number} = x + 1\). Consumes 1 sequence number.
  3. Step 3 (ACK segment from Client to Server): Client acknowledges server: sets ACK = 1, \(\text{Seq} = x + 1\), and \(\text{ACK Number} = y + 1\). May carry first application data bytes!
TCP 3-Way Handshake
Figure 4.2: TCP Three-Way Handshake Connection Establishment (Page 27)
πŸ”„ TCP Finite State Machine: The 11 Connection States

During its lifetime, a TCP endpoint transitions across 11 discrete protocol states:

State NameRoleDescription & Trigger Event
CLOSEDBothFictitious state; no active connection exists.
LISTENServerWaiting for an incoming connection request (SYN) from a client.
SYN-SENTClientClient sent SYN segment; waiting for matching SYN + ACK from server.
SYN-RCVDServerServer received SYN, sent SYN + ACK; waiting for confirming ACK.
ESTABLISHEDBothOpen connection! Data transfer phase in progress.
FIN-WAIT-1Active CloserSent FIN; waiting for ACK or FIN from remote endpoint.
FIN-WAIT-2Active CloserReceived ACK for own FIN; waiting for remote endpoint's FIN (Half-close active).
CLOSE-WAITPassive CloserReceived remote FIN, sent ACK; waiting for local app to close and send FIN.
CLOSINGBothSimultaneous close; both sent FIN and are waiting for respective ACKs.
LAST-ACKPassive CloserSent final FIN; waiting for confirming ACK from active closer.
TIME-WAITActive CloserWaits \(2 \times \text{MSL}\) to ensure remote endpoint received final ACK.

3. TCP Connection Termination: Four-Way Handshake & Half-Close

Either party can close the connection. Since TCP is full-duplex, each direction closes independently:

PART 05 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

TCP Flow Control, Error Control & Congestion Control

PDF Pages: 32 – 54
πŸ’‘ The Triad of TCP Reliability

TCP coordinates three distinct control loops: Flow Control (protects receiver buffer), Error Control (recovers lost data), and Congestion Control (protects intermediate network routers).

1. TCP Flow Control & Sliding Window

TCP uses a byte-oriented sliding window with dynamic Credit Allocation: the receiver grants the sender credit (\(rwnd\)) to transmit up to that many bytes before stopping. sliding window. The receiver advertises its available buffer space in the Window Size (rwnd) field of every ACK. The sender's usable window cannot exceed \(rwnd\).

TCP Sliding Window Buffers
Figure 5.1: Allocated Buffer & Sliding Window at Sender and Receiver (Page 33)

Silly Window Syndrome & Solutions

Occurs when data is generated in tiny chunks (e.g., 1 byte from a terminal), resulting in a massive 41-byte packet (20B IP + 20B TCP + 1B data) with 97.5% overhead!

2. TCP Congestion Control: AIMD, Slow Start & Fast Recovery

The effective transmission window is the minimum of receiver window and congestion window: \(\text{Send Window} = \min(rwnd, cwnd)\).

Slow Start and Congestion Avoidance
Figure 5.2: Congestion Window Dynamics: Slow Start & Congestion Avoidance (Page 41)
Congestion PhaseGrowth BehaviorTransition Condition
1. Slow Start Starts at \(cwnd = 1 \text{ MSS}\). Doubles exponentially every RTT (\(1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \dots\)) for each ACK received. Continues until \(cwnd\) reaches the Slow Start Threshold (\(ssthresh\)).
2. Congestion Avoidance Increases linearly by \(1 \text{ MSS}\) per RTT (Additive Increase). Continues until packet loss/timeout occurs.
3. Congestion Detection β€’ Timeout: Severe congestion. Set \(ssthresh = cwnd / 2\), reset \(cwnd = 1\), restart Slow Start.
β€’ 3 Duplicate ACKs: Mild congestion (TCP Reno). Fast Retransmit missing packet; set \(ssthresh = cwnd / 2\), set \(cwnd = ssthresh + 3\), enter Fast Recovery!
Avoids resetting to 1 MSS during isolated packet losses.

3. TCP Timers (PDF Pages 48 – 52)

4. Silly Window Syndrome, Nagle Algorithm & Clark's Solution

Silly Window Syndrome occurs when data is exchanged in tiny increments (e.g. 1 byte of application payload wrapped in 40 bytes of TCP/IP headers), causing extreme bandwidth waste:

5. Round-Trip Time (RTT) Estimation & Karn's Algorithm (Karn algorithm)

TCP calculates its Retransmission Timeout (RTO) using measured Round-Trip Times (RTT). However, when a packet is retransmitted and an ACK arrives, an ambiguity arises: Does the ACK correspond to the original packet or the retransmitted packet?

πŸ“ Karn's Algorithm Rules

Karn's algorithm resolves this measurement ambiguity with two strict principles:

  1. Rule 1: Do not measure or update the RTT estimate using ACKs for segments that have been retransmitted.
  2. Rule 2 (Timer Backoff): Whenever a retransmission occurs, double the current RTO value using exponential backoff: \[\text{RTO}_{\text{new}} = 2 \times \text{RTO}_{\text{old}}\] Continue doubling on successive retransmissions until a segment is transmitted and acknowledged without any retransmission.
PART 06 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Network Layer Introduction & IPv4 Protocol

PDF Pages: 55 – 66
πŸ’‘ What is the Network Layer?

The Network Layer provides host-to-host delivery of packets across multiple intermediate network hops. It handles packetizing, routing, forwarding, and logical addressing.

1. IPv4 Datagram Header Format (20 to 60 Bytes)

IPv4 Datagram Header Format
Figure 6.1: IPv4 Datagram Header Format (Page 57)
Header FieldBitsTechnical Function & Examination Role
VER (Version)4 bitsDefines IP version (always 4 for IPv4, binary 0100).
HLEN (Header Length / Data offset)4 bitsLength of header in 4-byte multiples. Minimum value is 5 (\(5 \times 4 = 20\) bytes).
Type of Service (DS / ECN)8 bitsSpecifies packet priority / Quality of Service (Differentiated Services).
Total Length16 bitsTotal length of datagram (\(\text{Header} + \text{Data}\)). Max = 65,535 bytes.
Identification16 bitsUnique ID assigned by sender to identify all fragments of the same original datagram.
Flags (DF & MF)3 bits Bit 0: Reserved (0).
Bit 1 (DF - Don't Fragment): If 1, router cannot fragment; if packet exceeds MTU, router drops it and sends ICMP error.
Bit 2 (MF - More Fragments): 1 means more fragments follow; 0 means this is the last fragment.
Fragment Offset13 bitsRelative position of data fragment in original datagram, measured in 8-byte units (\(\text{Offset} = \text{Byte Position} / 8\)).
Time to Live (TTL)8 bitsHop limit counter. Decremented by 1 at each router. When \(\text{TTL} = 0\), datagram is discarded to prevent infinite routing loops.
Protocol8 bitsIdentifies higher-layer protocol (1 = ICMP, 2 = IGMP, 6 = TCP, 17 = UDP).
Header Checksum16 bits1's complement checksum covering only the header (recalculated at every router due to TTL decrement!).
Source / Destination IP32 bits eachGlobally unique logical addresses of sender and recipient.

2. IPv4 Fragmentation & MTU Calculation

Each physical link technology has a Maximum Transmission Unit (MTU) (e.g., Ethernet MTU = 1500 bytes). When a datagram is larger than the outgoing link's MTU, routers fragment it.

πŸ“ High-Frequency KTU Numerical: IP Datagram Fragmentation

Problem: An IP datagram with total length 4000 bytes (including a 20-byte header) must pass through a link with an MTU of 1500 bytes. Find the number of fragments, total length, fragment offset, and MF flag for each fragment.

Solution:

Total data = \(4000 - 20 = 3980\) bytes.
Maximum data per fragment = \(1500 - 20 = 1480\) bytes (must be a multiple of 8; \(1480 / 8 = 185\), perfectly divisible!).

  • Fragment 1: Data bytes 0 to 1479 (1480 bytes).
    Total length = \(1480 + 20 = \mathbf{1500 \text{ bytes}}\).
    Fragment offset = \(0 / 8 = \mathbf{0}\).
    MF flag = \(\mathbf{1}\) (more fragments follow).
  • Fragment 2: Data bytes 1480 to 2959 (1480 bytes).
    Total length = \(1480 + 20 = \mathbf{1500 \text{ bytes}}\).
    Fragment offset = \(1480 / 8 = \mathbf{185}\).
    MF flag = \(\mathbf{1}\).
  • Fragment 3: Remaining data = \(3980 - (1480 \times 2) = 1020\) bytes.
    Total length = \(1020 + 20 = \mathbf{1040 \text{ bytes}}\).
    Fragment offset = \(2960 / 8 = \mathbf{370}\).
    MF flag = \(\mathbf{0}\) (last fragment!).
🌐 Special IPv4 Address Ranges
PART 07 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

IPv4 Addressing: Classful, CIDR Subnetting & NAT

PDF Pages: 67 – 75
πŸ’‘ What is an IP Address?

An IPv4 address is a 32-bit identifier that uniquely and universally defines the connection of a host or router to the Internet. Written in dotted-decimal notation (e.g., 192.168.1.1).

1. Classful Addressing (Historic)

ClassFirst Octet RangeDefault Subnet MaskNetID / HostID BitsUse Case
Class A0 – 127 (starts with 0)255.0.0.0 (/8)8 bits NetID, 24 bits HostIDHuge organizations (\(2^{24}-2 \approx 16.7\text{M}\) hosts).
Class B128 – 191 (starts with 10)255.255.0.0 (/16)16 bits NetID, 16 bits HostIDMid-sized organizations (\(2^{16}-2 = 65,534\) hosts).
Class C192 – 223 (starts with 110)255.255.255.0 (/24)24 bits NetID, 8 bits HostIDSmall networks (\(2^8-2 = 254\) hosts).
Class D224 – 239 (starts with 1110)NoneNoneMulticast groups.
Class E240 – 255 (starts with 1111)NoneNoneReserved for scientific research/future.

2. Classless Addressing (CIDR) & Subnetting

Classful addressing caused massive address waste. Today, the Internet uses Classless Inter-Domain Routing (CIDR). An address is written with a slash notation: address /n, where \(n\) is the prefix length (number of 1s in the mask).

πŸ“ High-Frequency KTU Subnetting Numerical

Problem: A host has IP address 172.16.45.200/26. Find:

  1. The subnet mask.
  2. The network address and broadcast address.
  3. The usable host address range and number of usable hosts.

Solution:

  • 1. Subnet Mask: Prefix \(n = 26\).
    Mask has 26 ones: 11111111.11111111.11111111.11000000 = \(\mathbf{255.255.255.192}\).
  • 2. Total Addresses in Block (\(N\)):
    \(N = 2^{32 - n} = 2^{32 - 26} = 2^6 = \mathbf{64 \text{ addresses}}\).
  • 3. Network Address (First Address):
    Looking at last octet 200: \(200 = 11001000_2\). ANDing with \(11000000_2\) gives \(11000000_2 = 192\).
    \(\implies \text{Network Address} = \mathbf{172.16.45.192}\).
  • 4. Broadcast Address (Last Address):
    \(\text{Network Address} + (N - 1) = 192 + 63 = 255\).
    \(\implies \text{Broadcast Address} = \mathbf{172.16.45.255}\).
  • 5. Usable Host Range:
    From first host (\(\text{Network} + 1\)) to last host (\(\text{Broadcast} - 1\)):
    \(\mathbf{172.16.45.193 \text{ to } 172.16.45.254}\).
    Number of usable hosts = \(2^6 - 2 = 64 - 2 = \mathbf{62 \text{ hosts}}\).
Hierarchical Addressing and Aggregation
Figure 7.1: Address Aggregation and Subnetting at Router (Page 68)
πŸ” Forwarding Table Lookup & Longest Prefix Match (LPM)

In classless addressing, routes in a router's Forwarding Table are organized by prefix lengths. When a packet arrives, the router may find multiple matching routing entries for the destination IP address.

Longest Prefix Match Rule: The router selects the routing table entry with the longest mask length (the most specific route with the highest number of 1s in the subnet mask). For example, a destination matching both 128.96.34.0/24 and 128.96.0.0/16 is routed via the /24 interface because it is more specific.

3. Network Address Translation (NAT) & NAPT

Allows thousands of devices on a private network to share a single public IP address when communicating on the Internet.

PART 08 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Unicast Routing Protocols: Distance Vector, Link State & Path Vector

PDF Pages: 76 – 88
πŸ’‘ Unicast Routing Overview

Routing is the process of selecting the optimal path across a network of interconnected routers. Routing protocols are broadly classified into Intra-Domain (Interior Gateway Protocols / IGP) and Inter-Domain (Exterior Gateway Protocols / EGP).

1. Distance Vector Routing (Bellman-Ford Algorithm & RIP)

In RIP, the distance metric is defined by Hop count (each router traversed adds 1 hop). The maximum valid path is 15 hops; 16 hops indicates infinity (unreachable destination).

Each router maintains a vector (table) of minimum distances to all known destinations. Routers periodically share their entire routing vector with their direct immediate neighbors only.

Bellman-Ford Equation: \(D_x(y) = \min_v \{ c(x,v) + D_v(y) \}\)

Distance Vector Routing
Figure 8.1: Distance Vector Routing Table Exchange (Page 77)

The Count-to-Infinity Problem & Remedies

Occurs when a link fails. Because routers update based on second-hand information, a routing loop is created where distance to unreachable node increments slowly to infinity (\(\infty = 16\) in RIP).

⚠️ The Count-to-Infinity Problem & Poison Reverse

A classic instability in Distance Vector routing occurs when a link breaks. Two neighboring routers falsely inform each other of an alternate route, incrementing their distance metrics indefinitely until reaching infinity (16 in RIP):

  • Split Horizon: A router never advertises a route back out the same interface through which it learned that route.
  • Split Horizon with Poison Reverse: A router does advertise the route back out the same interface, but explicitly sets the metric to \(\infty\) (16), saying "You told me how to get there; do not try to reach it through me!" This immediately eliminates two-node routing loops.

2. Link State Routing (Dijkstra's Algorithm & OSPF)

Each router discovers its direct neighbors, packages their states into a Link State Advertisement (LSA), and floods it to every router in the entire network. Every router builds an identical Link State Database (LSDB) representing the complete network topology graph, and runs Dijkstra's Shortest Path Algorithm locally.

OSPF Link State Routing
Figure 8.2: Link State Routing & OSPF Area Hierarchy (Page 85)
Comparison ParameterDistance Vector (RIP)Link State (OSPF)
Knowledge of TopologyTells its neighbors about the entire world. Has only local view.Tells the entire world about its local neighbors. Has full global map!
Algorithm UsedDistributed Bellman-Ford algorithm.Dijkstra's shortest path algorithm.
Convergence SpeedSlow convergence; vulnerable to count-to-infinity.Fast convergence; no routing loops.
Scalability & HierarchyLimited to max 15 hops.Supports two-level hierarchical Areas (Backbone Area 0).

3. Path Vector Routing & Border Gateway Protocol (BGP)

Inter-domain routing protocol used between Autonomous Systems (AS). Instead of just cost, BGP advertises the entire sequence of Autonomous Systems (the AS-PATH attribute) required to reach a destination prefix.

πŸ›οΈ OSPF Hierarchical Architecture: Areas, ABR & ASBR
🌐 External BGP (eBGP) vs. Internal BGP (iBGP)
PART 09 EXAMINATION ESSAY β€’ 5M / 9M

Multicast Routing Protocols: DVMRP, MOSPF & PIM

PDF Pages: 89 – 105
πŸ’‘ What is Multicasting?

One-to-many communication where a sender transmits a single packet, and network routers replicate that packet only at branching points to reach all subscribed members of a Multicast Group (Class D IP: 224.0.0.0 to 239.255.255.255).

1. Unicast vs Multicast: Foundational Concepts

Network communication can be categorized based on the number and specificity of recipients:

ParadigmSourceDestinationBandwidth EfficiencyKey Protocols
UnicastOne hostOne specific hostN separate streams for N receivers (wasteful for group video)HTTP, SSH, FTP, TCP/UDP
MulticastOne hostA specific group of subscribed hostsOne stream replicated by routers only at branch points (optimal)IGMP, DVMRP, MOSPF, PIM
BroadcastOne hostAll hosts on the subnetSent to all nodes regardless of interest (causes broadcast storms)ARP request, DHCP discover
AnycastOne hostNearest of multiple identical serversRoutes to topologically closest server instanceDNS Root servers, CDNs

2. Multicast Routing Trees: Source-Based vs. Group-Shared

FeatureSource-Based Tree (Shortest Path Tree)Group-Shared Tree (Core-Based Tree)
Tree ConstructionA separate unique tree is constructed for every individual source in the multicast group (\(m\) sources \(\rightarrow m\) trees).A single shared tree is constructed centered at a designated Rendezvous Point (RP) / Core Router.
Router Memory OverheadHigh (\(O(S \times G)\) state in routers).Low (\(O(G)\) state in routers).
Path OptimalityOptimal shortest path from each source to every receiver.Sub-optimal (packets first route to core, causing "tromboning" delay).
ProtocolsDVMRP, MOSPF, PIM-DM.PIM-SM, CBT.
PIM-SM Rendezvous Point
Figure 9.1: Group-Shared Tree with Rendezvous Point (RP) in PIM-SM (Page 102)

3. Key Multicast Routing Protocols

PART 10 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Next-Generation IP (IPv6) & Transition Strategies

PDF Pages: 106 – 112
πŸ’‘ Why IPv6?

IPv4 has run out of addresses (\(2^{32} \approx 4.3 \text{ billion}\)). IPv6 uses 128-bit addresses (\(2^{128} \approx 3.4 \times 10^{38}\) addressesβ€”enough to assign billions of addresses to every atom on Earth!), simplifies header processing, and adds native security and real-time streaming support.

1. IPv6 Address Representation

Written as eight groups of 4 hexadecimal digits separated by colons (e.g., 2001:0db8:85a3:0000:0000:8a2e:0370:7334).

IPv6 Header Format
Figure 10.1: IPv6 40-Byte Fixed Base Header Format (Page 107)

2. IPv6 Fixed Base Header (40 Bytes Fixed)

Field NameBit WidthTechnical Purpose
Version4 bitsValue = 6 (binary 0110).
Traffic Class8 bitsReplaces IPv4 ToS/DS; defines priority and congestion notification.
Flow Label20 bitsIdentifies packets belonging to the same real-time flow to enable fast hardware switching without deep packet inspection.
Payload Length16 bitsLength of data and extension headers following the 40-byte base header.
Next Header8 bitsSpecifies the type of header immediately following (an extension header or transport protocol like TCP = 6, UDP = 17).
Hop Limit8 bitsReplaces IPv4 TTL; decremented by 1 at each router.
Source Address128 bits (16 bytes)IPv6 address of the sending host.
Destination Address128 bits (16 bytes)IPv6 address of the receiving host.
⭐ Major Improvements in IPv6 Header over IPv4
  • Fixed Header Size: Fixed at 40 bytes; eliminates the HLEN field and speeds up hardware router processing.
  • No Header Checksum: Checksum removed; relying on link-layer CRC and transport-layer checksums eliminates router recalculation overhead!
  • No Mid-Path Router Fragmentation: Intermediate routers NEVER fragment IPv6 packets! If a packet exceeds link MTU, router drops it and sends ICMPv6 "Packet Too Big" so sender can use Path MTU Discovery.
πŸ“¦ IPv6 Extension Headers Architecture

To keep the base header lean (40 bytes fixed), optional fields are chained together as Extension Headers linked via the Next Header field:

Extension HeaderNext Header CodePurpose & Functionality
Hop-by-Hop Options0Processed by every router along the path (e.g. jumbo payloads, router alert).
Routing Header43Specifies an explicit source-routing list of intermediate routers to visit.
Fragment Header44Contains fragmentation offset and ID when sender fragments a packet larger than path MTU.
Encapsulating Security Payload (ESP)50Provides data confidentiality, encryption, and authentication in IPSec.
Authentication Header (AH)51Provides data integrity, message authentication, and replay protection in IPSec.
Destination Options60Additional packet options inspected only by the final destination host.

3. Comprehensive Comparison: IPv4 vs. IPv6 (IPv4 vs IPv6)

FeatureIPv4IPv6
Address Length32 bits (4.3 billion addresses)128 bits (\(3.4 \times 10^{38}\) addresses)
Base Header SizeVariable (20 to 60 bytes)Fixed 40 bytes
Header Length (HLEN)Present (4 bits)No HLEN field (fixed 40 bytes)
Checksum16-bit Header Checksum present (recalculated at every hop)No checksum field (relies on L2/L4 checksums for speed)
FragmentationPerformed by sending host AND intermediate routersPerformed exclusively by sender (Path MTU Discovery)
Packet LifetimeTime to Live (TTL, in hops)Hop Limit (in hops)
Protocol Field8-bit Protocol fieldReplaced by Next Header field
Security (IPSec)Optional add-onMandatory native architectural support

4. Transition Strategies from IPv4 to IPv6 (Transition from IPv4 to IPv6)

Transition StrategyWorking Principle & Where Used
1. Dual Stack Routers and hosts run both IPv4 and IPv6 protocol stacks simultaneously on the same machine. Can process both datagram types natively.
2. Tunneling When two IPv6 networks must communicate across an intermediate IPv4-only network, the entire IPv6 datagram is encapsulated as payload inside an IPv4 packet!
3. Header Translation Used when an IPv6-only host must communicate directly with an IPv4-only host. A NAT-PT gateway translates the IPv6 header into an IPv4 header and vice versa.
PART 11 VERY HIGH PRIORITY β€’ 5M / 9M ESSAY

Quality of Service (QoS) & Traffic Management

PDF Pages: 113 – 119
πŸ’‘ What is Quality of Service (QoS)?

Traditional IP networks provide "best-effort" service. Real-time applications (VoIP, video conferencing, telemedicine) require performance guarantees regarding four key QoS metrics: Throughput (Bandwidth), Delay, Jitter (Delay Variation), and Packet Loss.

1. Traffic Shaping: Leaky Bucket vs. Token Bucket

FeatureLeaky Bucket AlgorithmToken Bucket Algorithm
Working PrinciplePackets enter a bucket of capacity \(C\) with a hole at the bottom. Water leaks out at a strictly constant uniform rate.Tokens are generated at rate \(R\) and accumulate in a bucket of capacity \(B\). To transmit a packet, a token must be removed.
Bursty Output?Never. Bursts are eliminated; output is completely smoothed to fixed rate.Allows bounded bursts! If tokens are accumulated, a burst up to bucket capacity \(B\) can transmit at full wire speed.
Packet Dropping?Drops packets if incoming burst overflows buffer capacity.Drops only excess tokens; packets wait in queue if no tokens remain.
Leaky and Token Bucket Algorithms
Figure 11.1: Traffic Shaping: Smoothing Bursty Flows with Buckets (Page 114)

2. Packet Scheduling Disciplines

3. QoS Architectures: IntServ vs. DiffServ

FeatureIntegrated Services (IntServ)Differentiated Services (DiffServ)
GranularityPer-flow QoS guarantees.Per-class QoS aggregation.
Signaling ProtocolRSVP (Resource Reservation Protocol): reserves bandwidth along the entire end-to-end path.No end-to-end signaling. Edge routers classify packets and mark the 6-bit DS field.
Router StateStateful: core routers must maintain per-flow state.Stateless core: core routers only implement Per-Hop Behaviors (PHB).
ScalabilityPoor scalability in the Internet core (millions of flows).High scalability; dominant Internet QoS architecture.
🏷️ DiffServ Architecture & DSCP (Differentiated Services Code Point)

In Differentiated Services (DiffServ), packets are classified and marked at the network boundary using the 8-bit Differentiated Services (DS) field (former Type-of-Service / Traffic Class byte):

PART 12 EXAM MASTERCLASS β€’ NUMERICALS & QUESTION BANK

KTU Examination Masterclass & Solved Problems

πŸ“ Master Numerical: Subnetting a Company Network

Problem: An organization is granted a block of addresses with the beginning address 190.100.0.0/16. The administrator wants to create 512 subnets. Find:

  1. The subnet mask.
  2. The number of addresses in each subnet.
  3. The first and last address in Subnet 1.

Solution:

  • To create \(512 = 2^9\) subnets, we must borrow 9 bits from the host portion.
  • New prefix length \(n' = 16 + 9 = \mathbf{25}\). Subnet mask: 255.255.255.128.
  • Number of addresses per subnet = \(2^{32 - 25} = 2^7 = \mathbf{128 \text{ addresses}}\) (126 usable hosts).
  • First subnet (Subnet 0): 190.100.0.0/25 to 190.100.0.127/25.
  • Subnet 1: 190.100.0.128/25 to 190.100.0.255/25.

KTU Module 2 Comprehensive Question Bank

Answer:

  • (i) File Transfer: TCP β€” Requires 100% reliable, error-free transmission. A single dropped bit corrupts a file.
  • (ii) Live Video Call: UDP β€” Requires low latency and real-time playback. TCP retransmission delays cause unacceptable freezing.
  • (iii) DNS Query: UDP β€” Requires fast, single-packet query-response with zero connection setup overhead.

Answer Blueprint:

  1. Introduction (1 Mark): Define congestion and state that TCP controls congestion dynamically via the Congestion Window (\(cwnd\)).
  2. Neat Graph Diagram (2 Marks): Draw \(cwnd\) versus Transmission Round (RTT), showing exponential growth up to \(ssthresh\), linear AIMD growth, timeout drop to 1, and 3-duplicate ACK Fast Recovery drop.
  3. Slow Start (2 Marks): Starts at 1 MSS; doubles every RTT. Switches to Congestion Avoidance when \(cwnd \ge ssthresh\).
  4. Congestion Avoidance (2 Marks): Additive increase by 1 MSS per RTT.
  5. Congestion Detection & Fast Recovery (2 Marks):
    • Timeout: \(ssthresh = cwnd/2\), \(cwnd = 1\), restart Slow Start.
    • 3-Duplicate ACKs (TCP Reno): Fast Retransmit missing segment, set \(ssthresh = cwnd/2\), \(cwnd = ssthresh + 3\), enter Fast Recovery.
⚑ Module 2 Last-Minute Memory Mnemonics
  • TCP Control Flags: Unskilled Attackers Pester Real Security Fools → URG, ACK, PSH, RST, SYN, FIN.
  • IPv4 Header Minimum Size: 20 Bytes (\(HLEN = 5\)).
  • IPv6 Header Fixed Size: 40 Bytes.
  • UDP Header Size: 8 Bytes fixed.
  • Private IP Blocks: Class A: 10.0.0.0/8, Class B: 172.16.0.0/12, Class C: 192.168.0.0/16.
  • Multicast Address Range: Class D (224.0.0.0/4).