IP Addressing, Subnetting, and Routing Algorithms

Part 1: IP Addressing and Subnetting

At the heart of the Network Layer is the Internet Protocol (IP), and its addressing scheme is what gives every device on the internet a unique identity. An IPv4 address is a 32-bit number, commonly written in dotted-decimal notation (e.g., 192.168.1.1). This address has two parts: a Network ID that identifies the network the device belongs to, and a Host ID that identifies the specific device on that network.

The subnet mask is the tool we use to separate these two parts. In modern networking, we use Classless Inter-Domain Routing (CIDR), where the subnet mask is represented by a slash followed by a number (e.g., /24). This number indicates how many of the 32 bits are part of the Network ID.

Why Subnet?
Imagine an organization is given a large block of addresses, like 150.100.0.0/16. This single network can support $2^{16}-2$ hosts—over 65,000 devices! Placing them all in one broadcast domain would be a performance and security nightmare. Subnetting allows us to "borrow" some of the host bits to create multiple smaller, logical subnetworks. This improves organization, enhances security by isolating networks, and reduces broadcast traffic.

To succeed in GATE questions on this topic, you must be able to perform these key calculations for any given subnet:

1. Network ID: The first address of the subnet.
2. Broadcast ID: The last address of the subnet.
3. Valid Host Range: The range of usable IP addresses between the Network ID and Broadcast ID.
4. Subnet Mask: The mask corresponding to the CIDR notation.

The following video provides a comprehensive, step-by-step tutorial on how to perform these calculations.

Tying it Together: A GATE-Style Example

Let's consolidate the process with a typical problem.

Problem: An organization is assigned the network block 202.41.32.0/24. It needs to create 8 subnets. For the 5th subnet, find:
a) The subnet mask.
b) The Network ID.
c) The range of valid host IPs.
d) The Broadcast ID.

Solution:

1. Find the new subnet mask:

   • The original block is /24, meaning 24 bits are for the network part.
   • To create 8 subnets, we need to borrow bits from the host part. The number of bits to borrow, $n$, must satisfy $2^n\ge 8$. Here, $n=3$ bits are required ($2^3=8$).
   • The new subnet mask will be the original 24 bits plus the 3 borrowed bits: $24+3=27$. So, the new mask is /27.
   • In dotted-decimal, a /27 mask is 255.255.255.224 (since 27 ones are 11111111.11111111.11111111.11100000).

2. Analyze the subnets:

   • With a /27 mask, there are $32-27=5$ bits left for hosts.
   • The number of hosts per subnet is $2^5-2=30$. The block size (total addresses per subnet) is $2^5=32$.
   • The subnets will start at multiples of 32 in the last octet:
     • Subnet 0: 202.41.32.0
     • Subnet 1: 202.41.32.32
     • Subnet 2: 202.41.32.64
     • Subnet 3: 202.41.32.96
     • Subnet 4 (the 5th subnet): 202.41.32.128

3. Determine the addresses for the 5th subnet (Subnet 4):

   • Network ID: This is the starting address: 202.41.32.128.
   • Broadcast ID: This is the last address before the next subnet starts. The next subnet is at .160, so the broadcast ID is 202.41.32.159. (Alternatively, Network ID + Block Size - 1 = 128 + 32 - 1 = 159).
   • Valid Host Range: The addresses between the Network ID and Broadcast ID.
     • First Host IP: 202.41.32.129 (Network ID + 1)
     • Last Host IP: 202.41.32.158 (Broadcast ID - 1)
     • Range: 202.41.32.129 to 202.41.32.158.

This methodical approach is key to solving any subnetting question accurately.

Part 2: Routing Algorithms

Once we have our addresses, how do packets find their way from a source IP to a destination IP, possibly traversing dozens of networks? This is the job of routing algorithms, which run on routers to build and maintain routing tables. These tables tell the router which outgoing interface to use for any given destination network. We'll focus on the two main classes of dynamic routing algorithms: Distance Vector and Link State.

The video below explains both approaches with clear examples and concludes with a crucial comparison.

Distilling the Concepts: Distance Vector vs. Link State

Let's summarize the key distinctions you've just seen, which are essential for GATE.

Distance Vector (DV) Routing

• Analogy: "Routing by rumor" or knowing the way from a signpost.
• Knowledge: Each router has local knowledge. It knows the cost (distance) to its immediate neighbors, but relies on those neighbors' routing tables for information about the rest of the network. It doesn't have a view of the entire network topology.
• Mechanism: Routers periodically exchange their entire routing tables with their directly connected neighbors. Upon receiving a table, a router updates its own table if a neighbor has found a shorter path to a destination.
• Underlying Algorithm: Bellman-Ford algorithm. This is why it can handle negative edge weights (though not negative cycles) but is susceptible to the count-to-infinity problem, where bad news (like a link failure) propagates very slowly through the network.
• Example Protocol: RIP (Routing Information Protocol).

Link State (LS) Routing

• Analogy: "Everyone has the full map."
• Knowledge: Each router has global knowledge. Through a process called flooding, every router receives information about every other router and every link in the network. This allows each router to construct an identical, complete map of the network topology.
• Mechanism:
  1. Routers discover their neighbors and the cost to reach them.
  2. This information is packaged into a Link State Packet (LSP).
  3. The LSP is "flooded" (broadcast) to all other routers in the network.
  4. Each router independently runs Dijkstra's algorithm on its complete map to calculate the shortest path to every other destination.
• Underlying Algorithm: Dijkstra's algorithm. This is computationally more intensive but provides faster convergence and is more robust than DV.
• Example Protocol: OSPF (Open Shortest Path First).

Conclusion

Today, we journeyed into the core of the internet's architecture—the Network Layer. You learned the indispensable skill of subnetting, which is fundamental for network design and a frequent source of marks in GATE. You also dissected the two primary strategies routers use to navigate the internet's vast web of connections.

Here are your key takeaways:

• Subnetting: A CIDR address (e.g., /27) tells you the size of the network portion. You can borrow host bits to create subnets. For any subnet, you must be able to calculate its Network ID, Broadcast ID, and the valid host range. The block size ($2^{\text{host bits}}$) is your key to moving between subnets.
• Distance Vector (DV): Routers share their entire tables with neighbors. It's simple but converges slowly. Think "routing by rumor" and Bellman-Ford.
• Link State (LS): Routers share small updates about their local links with everyone. Each router builds a full map and runs Dijkstra's. It's complex but converges quickly. Think "everyone has the map."

In our previous lesson, we covered Layer 2. Today, we covered Layer 3. In our next lesson, we will continue up the stack to Layer 4 (Transport Layer), exploring how TCP and UDP provide end-to-end communication services. We will also look at essential helper protocols like ARP and ICMP that support the network layer, and deep-dive into the famous TCP 3-way handshake.