Routing Protocols: Algorithms, Protocols & VLSM

TAKEAWAYS:

• Routing protocols dynamically exchange route information between routers to forward packets efficiently, classified into interior (IGP) and exterior (EGP) based on network scope.
• Distance-vector (e.g., RIP) and link-state (e.g., OSPF) algorithms differ in how they calculate shortest paths and share updates, with trade-offs in convergence speed and overhead.
• Variable Length Subnet Masking (VLSM) optimizes IP address allocation by assigning smaller subnets to networks with fewer hosts, reducing waste (e.g., NTC’s branch offices).
• The count-to-infinity problem in distance-vector protocols causes routing loops, solved by techniques like split horizon, poison reverse, or triggered updates.
• Hierarchical routing (e.g., BGP for ISPs like Ncell) scales large networks by dividing them into autonomous systems (AS) and using policy-based routing.
• Real-world systems (e.g., WhatsApp’s CDN routing, Khalti’s payment gateway load balancing) rely on routing protocols to ensure low-latency, reliable communication.

1. Introduction to Routing Protocols

Routing protocols are the rules and algorithms that routers use to exchange route information and determine the best path for forwarding packets across networks. They operate at the Network Layer (Layer 3) of the OSI model and are essential for internetworking.

Why Routing Protocols?

Without routing protocols, routers would rely on static routes (manually configured), which are:

• Inflexible: Require manual updates if the network topology changes.
• Scalable: Impractical for large networks (e.g., Ncell’s backbone).
• Error-prone: Human mistakes can cause outages.

Routing protocols automatically adapt to network changes (e.g., link failures) and optimize path selection based on metrics like:

• Hop count (number of routers traversed).
• Bandwidth (link speed).
• Delay (propagation + processing time).
• Cost (administrative or monetary).

2. Classification of Routing Protocols

Routing protocols are categorized based on:

1. Scope:

   • Interior Gateway Protocols (IGP): Used within an autonomous system (AS) (e.g., a company’s network like Nepal Telecom’s backbone). Examples: RIP, OSPF, EIGRP.
   • Exterior Gateway Protocols (EGP): Used between autonomous systems (e.g., Ncell ↔ NTC ↔ Internet). Example: Border Gateway Protocol (BGP).

2. Algorithm Type:

   • Distance-Vector (DV): Routers share distance (cost) to destinations with neighbors (e.g., RIP).
   • Link-State (LS): Routers share complete topology and compute shortest paths independently (e.g., OSPF).
   • Path-Vector (PV): Used in BGP to track AS path and prevent loops.

3. Distance-Vector Routing Protocols

How It Works

• Each router maintains a routing table with:
  • Destination network.
  • Next hop (router to forward to).
  • Metric (e.g., hop count).
• Routers periodically exchange their entire routing table with direct neighbors.
• Bellman-Ford algorithm is used to compute shortest paths.

Example: RIP (Routing Information Protocol)

• Metric: Hop count (max 15 hops; 16 = unreachable).
• Update interval: Every 30 seconds.
• Convergence time: Slow (takes time to propagate updates).

Worked Example: RIP Routing Table Update Assume a simple network:

Router A -- Router B -- Router C

• Initial state: All routers know directly connected networks.
• After 1st update:
  • A learns C/24 via B (distance = 2).
  • B learns A/24 and C/24 (distance = 1).
  • C learns B/24 and A/24 via B (distance = 2).

Mermaid Diagram: RIP Update Process

sequenceDiagram
    participant A as Router A
    participant B as Router B
    participant C as Router C
    A->>B: Sends routing table (A/24, distance=0)
    B->>C: Sends routing table (B/24, A/24 via A, distance=1)
    C->>B: Sends routing table (C/24, B/24, A/24 via B, distance=1)
    B->>A: Sends updated table (A/24, B/24, C/24 via C, distance=2)

Problems with Distance-Vector

1. Count-to-Infinity Problem:

   • If a link fails, routers keep incrementing the hop count until it reaches 16 (infinite).
   • Example: If A-B link fails, A thinks B is 16 hops away and stops sending updates to B. But B still thinks A is 2 hops away (via C), causing a routing loop.

   Mermaid Diagram: Count-to-Infinity Loop

   flowchart TD
     A["Router A"] -->|"B/24 via B"| B["Router B"]
     B -->|"A/24 via A"| A
     C["Router C"] -->|"A/24 via B"| B
     B -->|"C/24 via C"| C

2. Slow Convergence:

   • Updates are periodic, so failures take time to propagate.

Solutions to Count-to-Infinity

4. Link-State Routing Protocols

How It Works

• Each router floods the entire network with Link-State Advertisements (LSAs) containing:
  • Neighbor routers.
  • Link costs (e.g., bandwidth).
• Every router builds a complete topology map and runs Dijkstra’s algorithm to compute shortest paths.

Example: OSPF (Open Shortest Path First)

• Metric: Cost (based on bandwidth; lower cost = faster link).
  • Formula: Cost = Reference Bandwidth / Interface Bandwidth.
  • Default reference bandwidth = 100 Mbps.
  • Example: A 100 Mbps link has cost 100/100 = 1; a 10 Mbps link has cost 100/10 = 10.
• Areas: Divides large networks into hierarchical regions to reduce overhead.
• Convergence: Faster than RIP (seconds vs. minutes).

Worked Example: OSPF Cost Calculation Assume:

• Link A-B: 100 Mbps → Cost = 100/100 = 1.
• Link B-C: 10 Mbps → Cost = 100/10 = 10.
• Link A-C: 10 Mbps → Cost = 10.

Shortest path from A to C:

• A → B → C: Cost = 1 + 10 = 11.
• A → C: Cost = 10. → A chooses A → C (lower cost).

Mermaid Diagram: OSPF Topology Flooding

sequenceDiagram
    participant A as Router A
    participant B as Router B
    participant C as Router C
    A->>B: Floods LSA (A-B cost=1)
    B->>C: Floods LSA (B-C cost=10, A-B cost=1)
    C->>A: Floods LSA (A-C cost=10, B-C cost=10)
    A->>A: Runs Dijkstra: A→C (cost=10) is best

Advantages of Link-State

• Faster convergence (no periodic updates; changes propagate immediately).
• No count-to-infinity (complete topology known).
• Scalable (hierarchical areas reduce flooding).

Disadvantages

• High memory usage (stores full topology).
• High CPU usage (runs Dijkstra’s algorithm).
• Complex configuration (areas, authentication).

5. Variable Length Subnet Masking (VLSM)

What is VLSM?

• Traditional subnetting assigns equal-sized subnets, wasting IP addresses.
• VLSM assigns different subnet mask lengths based on host requirements:
  • Networks with few hosts get smaller subnets (e.g., /28 for 14 hosts).
  • Networks with many hosts get larger subnets (e.g., /24 for 254 hosts).

Why Use VLSM?

• Conserves IP addresses (critical for IPv4 exhaustion).
• Reduces routing table size (smaller subnets aggregate better).

Worked Example: VLSM Subnetting

Given: 192.168.0.0/24 (CIDR 24). Requirements:

1. LAN 1: 30 hosts → Needs 6 bits for hosts (2^6 - 2 = 62 hosts). → Subnet mask: /26 (32 - 6 = 26).
2. LAN 2: 10 hosts → Needs 4 bits for hosts (2^4 - 2 = 14 hosts). → Subnet mask: /28 (32 - 4 = 28).
3. LAN 3: 5 hosts → Needs 3 bits for hosts (2^3 - 2 = 6 hosts). → Subnet mask: /29 (32 - 3 = 29).

Step-by-Step Subnetting:

1. Start with 192.168.0.0/24 (subnet 0, usable range 192.168.0.1–254).
2. Allocate LAN 1 (/26):
   • Subnet 0: 192.168.0.0/26 (wasted; avoid using 0).
   • Next available: 192.168.0.64/26 (LAN 1).
     • Usable hosts: 192.168.0.65–94.
3. Allocate LAN 2 (/28):
   • Next subnet: 192.168.0.96/28.
     • Usable hosts: 192.168.0.97–110.
4. Allocate LAN 3 (/29):
   • Next subnet: 192.168.0.112/29.
     • Usable hosts: 192.168.0.113–118.

Mermaid Diagram: VLSM Subnet Allocation

5+3 VLSM Rule

• 5 bits for subnets, 3 bits for hosts → /27 (default for VLSM).
• Used when no specific host requirements are given.
• Example: 192.168.0.0/27 gives:
  • Subnet bits: 5 → 2^5 = 32 subnets.
  • Host bits: 3 → 2^3 - 2 = 6 hosts per subnet.

Why Use 5+3?

• Balances subnet count and host capacity.
• Ensures no wasted subnets for small networks.

6. Exterior Gateway Protocol: BGP (Border Gateway Protocol)

What is BGP?

• The de facto standard for inter-domain routing (between ISPs like Ncell ↔ NTC ↔ Internet).
• Operates between autonomous systems (AS) (e.g., AS1234 for Ncell, AS5678 for NTC).
• Uses path-vector algorithm (extends distance-vector with AS path tracking).

How BGP Works

1. Peering: Routers in different ASes establish BGP sessions (e.g., Ncell’s router ↔ NTC’s router).
2. Route Advertisement:
   • Routers exchange network prefixes (e.g., 103.0.0.0/8 for Ncell).
   • Each update includes the AS path (e.g., AS1234 → AS5678).
3. Policy-Based Routing:
   • ISPs use BGP attributes (e.g., AS_PATH, NEXT_HOP, LOCAL_PREF) to enforce policies like:
     • Prefer local routes (e.g., Ncell prefers its own routes over competitors).
     • Avoid loops (if a route’s AS path contains its own AS, discard it).

Example: BGP Route Selection

Assume:

• AS1 (Ncell) advertises 192.168.1.0/24 to AS2 (NTC).
• AS2 receives two paths to 192.168.1.0/24:
  1. Via AS1 (AS path: AS1).
  2. Via AS3 → AS1 (AS path: AS3 AS1).

BGP selects the path with the shortest AS path → AS1 (shorter path).

Mermaid Diagram: BGP AS Path

sequenceDiagram
    participant Ncell as AS1234 (Ncell)
    participant NTC as AS5678 (NTC)
    participant Internet as AS7890 (Internet)
    Ncell->>NTC: Advertises 192.168.1.0/24 (AS_PATH: AS1234)
    NTC->>Internet: Advertises 192.168.1.0/24 (AS_PATH: AS5678 AS1234)
    note "NTC prefers the path with fewer AS hops."

BGP Attributes

BGP vs. IGP

7. Real-World Applications

1. Ncell’s Backbone Network

• Uses OSPF for interior routing (within Ncell’s AS) to efficiently route calls/data between towers.
• Uses BGP for exterior routing to exchange routes with other ISPs (e.g., NTC, Smart).
• VLSM optimizes IP allocation for different-sized cell sites.

2. eSewa’s Payment Gateway

• Load balancing: Uses OSPF or BGP to distribute traffic across multiple servers to prevent overload.
• Redundancy: If one payment server fails, OSPF quickly reroutes traffic to another.

3. WhatsApp’s CDN Routing

• Anycast DNS: Uses BGP to route users to the nearest WhatsApp server (e.g., Kathmandu user → Ncell’s nearest CDN node).
• VLSM: Efficiently allocates IPs to CDN nodes worldwide.

4. Daraz’s Order Fulfillment

• Hierarchical routing: Daraz’s warehouse network uses OSPF areas to separate regional hubs (e.g., Kathmandu, Pokhara) from the central database.
• RIP for small branches: Remote pickup points use RIP due to low traffic.

5. NTC’s Fiber Optic Backbone

• Uses MPLS (Multi-Protocol Label Switching) on top of OSPF for fast traffic engineering.
• VLSM ensures minimal IP waste across thousands of exchange points.

8. Exam Tips

1. Memorize Key Protocols and Their Features:

   • RIP: Distance-vector, hop count ≤ 15, slow convergence.
   • OSPF: Link-state, cost-based, hierarchical areas.
   • BGP: Path-vector, AS path, policy-based.

2. Practice VLSM Subnetting:

   • Always draw the subnet table (network, broadcast, usable hosts).
   • Use the 5+3 rule when no host count is given.

3. Understand Count-to-Infinity:

   • Explain why it happens (no poison reverse) and how to fix it (split horizon, triggered updates).

4. Compare IGP vs. EGP:

   • IGP = within AS (OSPF, RIP).
   • EGP = between ASes (BGP).

5. Real-World Scenarios:

   • Relate VLSM to NTC’s branches (small subnets for remote offices).
   • Relate BGP to Ncell ↔ NTC peering (AS path selection).

6. Diagrams Are Key:

   • Always draw:
     • Routing table updates (RIP).
     • Topology flooding (OSPF).
     • AS path diagrams (BGP).
   • Label metrics, costs, and next hops.

7. Common Pitfalls:

   • Forgetting broadcast addresses in subnetting.
   • Misapplying split horizon (e.g., sending updates back to the source).
   • Confusing OSPF cost with RIP hop count.

9. Summary Table: Routing Protocols

10. Practice Questions

1. Subnetting:

   • Subnet 172.16.0.0/16 using VLSM for:
     • LAN 1: 20 hosts.
     • LAN 2: 50 hosts.
     • LAN 3: 100 hosts.
   • Show the subnet allocation table.

2. Routing Loops:

   • Explain how split horizon and poison reverse prevent count-to-infinity in RIP.

3. OSPF Cost:

   • Calculate the cost of a 10 Mbps and 1 Gbps link (reference bandwidth = 100 Mbps).

4. BGP Policy:

   • Why might Ncell prefer routes from NTC over Smart even if Smart’s path is shorter?

5. VLSM vs. Traditional:

   • Given 10.0.0.0/8, allocate subnets for:
     • 3 networks with 50 hosts each.
     • 1 network with 5 hosts.
   • Compare IP usage in VLSM vs. traditional subnetting.