Back to Computer Networks
Network Layer
Routing algorithms, IP addressing, and packet forwarding
Key Concepts
Shortest path algorithms, IP subnetting, routing protocols
Applications
Internet routing, network design, address management
Exam Focus
Dijkstra algorithm, IP calculations, routing table analysis
Network Layer Topics
Routing Algorithm Concepts
Distance Vector Algorithm
Each router maintains a table of distances to all destinations
Algorithm Formula:
D_x(y) = min_v{c(x,v) + D_v(y)}Properties:
- • Distributed and iterative
- • Uses Bellman-Ford equation
- • Count-to-infinity problem
- • Poisoned reverse solution
Protocols:
RIP (Routing Information Protocol)
Link State Algorithm
Each router has complete network topology information
Algorithm Formula:
Dijkstra's algorithm with network topologyProperties:
- • Global information required
- • Faster convergence
- • No count-to-infinity problem
- • Higher memory requirements
Protocols:
OSPF (Open Shortest Path First)
IS-IS
Path Vector Algorithm
Each router maintains the actual path to destinations
Algorithm Formula:
Path advertisement with loop detectionProperties:
- • Loop prevention by path inspection
- • Policy-based routing support
- • Slower convergence
- • Used in inter-domain routing
Protocols:
BGP (Border Gateway Protocol)
IP Addressing Concepts
Classful Addressing
| Class | IP Range | Default Mask | Max Hosts |
|---|---|---|---|
| A | 0.0.0.0 - 127.255.255.255 | /8 | 16,777,214 |
| B | 128.0.0.0 - 191.255.255.255 | /16 | 65,534 |
| C | 192.0.0.0 - 223.255.255.255 | /24 | 254 |
| D | 224.0.0.0 - 239.255.255.255 | Multicast | N/A |
| E | 240.0.0.0 - 255.255.255.255 | Reserved | N/A |
CIDR (Classless Inter-Domain Routing)
Network address/prefix length (e.g., 192.168.1.0/24)
Benefits:
- • Reduces routing table size
- • Eliminates class boundaries
- • Allows route aggregation
- • More efficient address allocation
CIDR Examples:
192.168.1.0/24: 254 hosts
10.0.0.0/8: 16,777,214 hosts
172.16.0.0/12: 1,048,574 hosts
192.168.1.128/25: 126 hosts
Sample Problems & Solutions
Dijkstra Algorithm Problem
Problem: Find shortest path from vertex 0 to all vertices in given graph.
Given: Graph with 5 vertices, edge weights: (0→1:4), (0→2:2), (1→2:1), (1→3:5), (2→3:8), (2→4:10), (3→4:2)
Solution: Apply Dijkstra's algorithm step by step
Step 1: Initialize distances: [0, ∞, ∞, ∞, ∞]
Step 2: Visit 0, update neighbors: [0, 4, 2, ∞, ∞]
Step 3: Visit 2, update neighbors: [0, 3, 2, 10, 12]
Step 4: Visit 1, update neighbors: [0, 3, 2, 8, 12]
Step 5: Visit 3, update neighbors: [0, 3, 2, 8, 10]
Final distances: [0, 3, 2, 8, 10]
IP Subnetting Problem
Problem: Subnet 192.168.1.0/24 into 4 equal subnets.
Solution:
Original: 192.168.1.0/24 (256 addresses)
Required: 4 subnets = 2² subnets
New mask: /24 + 2 = /26
Subnet 1: 192.168.1.0/26 (0-63)
Subnet 2: 192.168.1.64/26 (64-127)
Subnet 3: 192.168.1.128/26 (128-191)
Subnet 4: 192.168.1.192/26 (192-255)
Each subnet: 62 usable host addresses