Routing Protocols (OSPF, BGP)

Routing protocols enable routers to exchange routing information and build routing tables. OSPF (Open Shortest Path First) is an interior gateway protocol, while BGP (Border Gateway Protocol) is an exterior gateway protocol for internet routing.

---

What are Routing Protocols?

Routing protocols allow routers to:

• Exchange routing information: Share network topology
• Build routing tables: Determine best paths
• Adapt to changes: Update when network changes
• Avoid loops: Prevent routing loops

Types:

• Interior Gateway Protocol (IGP): Within autonomous system (OSPF, RIP)
• Exterior Gateway Protocol (EGP): Between autonomous systems (BGP)

---

OSPF (Open Shortest Path First)

Type: Link-state routing protocol (IGP) Algorithm: Dijkstra's shortest path Use: Within autonomous system (AS)

How OSPF Works

1. Discover Neighbors

Router sends Hello packets
Neighbors respond
Establish adjacency

2. Exchange Link-State Advertisements (LSAs)

Each router describes its links
Flood LSAs to all routers
All routers have same topology database

3. Build Shortest Path Tree

Each router runs Dijkstra's algorithm
Calculates shortest path to all destinations
Builds routing table

OSPF Areas

Hierarchical design:

Area 0 (Backbone)
  ├─ Area 1
  ├─ Area 2
  └─ Area 3

Benefits:

• Reduced LSA flooding: LSAs only within area
• Scalability: Large networks divided into areas
• Stability: Changes isolated to area

OSPF Metrics

Cost based on bandwidth:

Cost = Reference Bandwidth / Interface Bandwidth

Fast link: Low cost
Slow link: High cost

---

BGP (Border Gateway Protocol)

Type: Path-vector routing protocol (EGP) Algorithm: Best path selection Use: Between autonomous systems (internet routing)

How BGP Works

1. Establish BGP Sessions

Routers establish TCP connections
Exchange BGP messages

2. Exchange Routes

Routers advertise routes with attributes
  - AS Path (list of ASes)
  - Next Hop
  - Origin
  - Local Preference

3. Best Path Selection

BGP selects best path based on attributes:
  1. Local Preference (highest)
  2. AS Path (shortest)
  3. Origin
  4. MED (Multi-Exit Discriminator)

BGP Attributes

AS Path:

Route: 192.168.1.0/24
AS Path: [AS100, AS200, AS300]

Shows path through autonomous systems

Local Preference:

Higher value = preferred
Used within AS

MED:

Lower value = preferred
Used between ASes

---

OSPF vs BGP

Feature	OSPF	BGP
Type	Link-state (IGP)	Path-vector (EGP)
Scope	Within AS	Between ASes
Algorithm	Dijkstra	Best path selection
Convergence	Fast	Slower
Scalability	Limited (areas)	Very scalable
Use case	Enterprise networks	Internet routing

---

Examples

OSPF Configuration

# Router configuration
router ospf 1
  network 192.168.1.0 0.0.0.255 area 0
  network 10.0.0.0 0.0.0.255 area 1
  
interface GigabitEthernet0/0
  ip ospf cost 10
  ip ospf priority 100

BGP Configuration

# Router configuration
router bgp 100
  neighbor 192.168.1.1 remote-as 200
  neighbor 192.168.1.1 update-source Loopback0
  
  network 10.0.0.0 mask 255.0.0.0
  redistribute ospf 1

OSPF Dijkstra Algorithm

class OSPFRouter:
    def __init__(self, router_id):
        self.router_id = router_id
        self.lsdb = {}  # Link State Database
        self.routing_table = {}
    
    def run_dijkstra(self):
        """Run Dijkstra's algorithm to calculate shortest paths"""
        distances = {self.router_id: 0}
        previous = {}
        unvisited = set(self.lsdb.keys())
        unvisited.add(self.router_id)
        
        while unvisited:
            # Find unvisited node with smallest distance
            current = min(unvisited, key=lambda x: distances.get(x, float('inf')))
            unvisited.remove(current)
            
            # Update distances to neighbors
            for neighbor, cost in self.lsdb[current].items():
                if neighbor in unvisited:
                    new_distance = distances[current] + cost
                    if new_distance < distances.get(neighbor, float('inf')):
                        distances[neighbor] = new_distance
                        previous[neighbor] = current
        
        # Build routing table
        self.build_routing_table(distances, previous)

BGP Best Path Selection

class BGPRouter:
    def select_best_path(self, routes):
        """Select best BGP path"""
        if not routes:
            return None
        
        # Sort by BGP attributes
        routes.sort(key=lambda r: (
            -r.local_preference,  # Higher is better
            len(r.as_path),      # Shorter is better
            r.origin,            # IGP < EGP < Incomplete
            -r.med               # Lower is better (if from same AS)
        ))
        
        return routes[0]

---

Common Pitfalls

• OSPF area design: Poor area design causes issues. Fix: Design areas carefully, use area 0 as backbone
• BGP route filtering: Not filtering routes causes problems. Fix: Filter routes, use route maps
• Convergence time: Slow convergence. Fix: Tune timers, optimize network design
• Route loops: Incorrect configuration causes loops. Fix: Verify configuration, use loop prevention

---

Interview Questions

Beginner

Q: What is the difference between OSPF and BGP? When would you use each?

A:

OSPF (Open Shortest Path First):

• Type: Link-state routing protocol (IGP)
• Scope: Within autonomous system (AS)
• Algorithm: Dijkstra's shortest path
• Use: Enterprise networks, data centers

BGP (Border Gateway Protocol):

• Type: Path-vector routing protocol (EGP)
• Scope: Between autonomous systems
• Algorithm: Best path selection
• Use: Internet routing, ISPs

Key Differences:

Feature	OSPF	BGP
Scope	Within AS	Between ASes
Convergence	Fast	Slower
Scalability	Limited	Very scalable
Complexity	Moderate	High

When to use:

• OSPF: Enterprise networks, data centers, within organization
• BGP: Internet routing, ISPs, between organizations

---

Intermediate

Q: Explain how OSPF builds routing tables using link-state advertisements.

A:

OSPF Process:

1. Discover Neighbors

   Router sends Hello packets
   Neighbors respond
   Establish adjacency
   

2. Exchange Link-State Advertisements (LSAs)

   Each router describes its links:
     - Connected networks
     - Link costs
     - Neighbor routers
   
   Flood LSAs to all routers in area
   All routers have same topology database
   

3. Build Shortest Path Tree

   Each router runs Dijkstra's algorithm:
     - Start from itself
     - Calculate shortest path to all destinations
     - Build routing table
   

Example:

Topology:
  Router A --10-- Router B --5-- Router C
       \                    /
        \                  /
         \--20-- Router D--/

Router A's LSDB:
  A: [(B, 10), (D, 20)]
  B: [(A, 10), (C, 5)]
  C: [(B, 5), (D, 15)]
  D: [(A, 20), (C, 15)]

Dijkstra from A:
  A → B: 10
  A → C: 15 (via B)
  A → D: 20

Routing Table:
  C: Next hop B, Cost 15
  D: Next hop D, Cost 20

Benefits:

• Fast convergence
• Loop-free
• Scalable with areas

---

Senior

Q: Design a routing system for a large ISP that uses both OSPF internally and BGP for internet routing. How do you handle route selection, load balancing, and failover?

A:

class ISPRoutingSystem {
  private ospf: OSPFRouter;
  private bgp: BGPRouter;
  private routeManager: RouteManager;
  
  constructor() {
    this.ospf = new OSPFRouter();
    this.bgp = new BGPRouter();
    this.routeManager = new RouteManager();
  }
  
  // 1. OSPF for Internal Routing
  class OSPFRouter {
    async buildTopology(): Promise<void> {
      // Discover neighbors
      await this.discoverNeighbors();
      
      // Exchange LSAs
      await this.exchangeLSAs();
      
      // Run Dijkstra
      await this.runDijkstra();
      
      // Build routing table
      await this.buildRoutingTable();
    }
    
    async runDijkstra(): Promise<void> {
      // Calculate shortest paths
      const distances = this.calculateShortestPaths();
      this.routingTable = this.buildRoutes(distances);
    }
  }
  
  // 2. BGP for External Routing
  class BGPRouter {
    async establishSessions(): Promise<void> {
      // Establish BGP sessions with neighbors
      for (const neighbor of this.neighbors) {
        await this.establishSession(neighbor);
      }
    }
    
    async exchangeRoutes(): Promise<void> {
      // Exchange routes with neighbors
      for (const neighbor of this.neighbors) {
        await this.exchangeRoutes(neighbor);
      }
    }
    
    async selectBestPath(destination: string): Promise<BGPRoute> {
      const routes = this.getRoutes(destination);
      
      // BGP best path selection
      return routes.sort((a, b) => {
        // 1. Local Preference
        if (a.localPreference !== b.localPreference) {
          return b.localPreference - a.localPreference;
        }
        
        // 2. AS Path length
        if (a.asPath.length !== b.asPath.length) {
          return a.asPath.length - b.asPath.length;
        }
        
        // 3. Origin
        const originOrder = { 'IGP': 0, 'EGP': 1, 'Incomplete': 2 };
        if (a.origin !== b.origin) {
          return originOrder[a.origin] - originOrder[b.origin];
        }
        
        // 4. MED
        return a.med - b.med;
      })[0];
    }
  }
  
  // 3. Route Selection (OSPF vs BGP)
  class RouteManager {
    async selectRoute(destination: string): Promise<Route> {
      // Check OSPF routes (internal)
      const ospfRoute = await this.ospf.getRoute(destination);
      
      // Check BGP routes (external)
      const bgpRoute = await this.bgp.getRoute(destination);
      
      // Prefer OSPF for internal routes
      if (ospfRoute && this.isInternal(destination)) {
        return ospfRoute;
      }
      
      // Use BGP for external routes
      if (bgpRoute) {
        return bgpRoute;
      }
      
      return null;
    }
  }
  
  // 4. Load Balancing
  class LoadBalancer {
    async balanceTraffic(destination: string): Promise<Route[]> {
      // Get multiple paths
      const routes = await this.getMultiplePaths(destination);
      
      // ECMP (Equal Cost Multi-Path)
      const equalCostRoutes = routes.filter(r => r.cost === routes[0].cost);
      
      // Distribute traffic
      return this.distributeTraffic(equalCostRoutes);
    }
  }
  
  // 5. Failover
  class FailoverManager {
    async handleFailure(failedRoute: Route): Promise<void> {
      // Detect failure
      if (await this.isRouteDown(failedRoute)) {
        // Find alternative route
        const alternative = await this.findAlternative(failedRoute.destination);
        
        // Update routing table
        await this.updateRoutingTable(failedRoute.destination, alternative);
        
        // Notify neighbors (BGP)
        await this.bgp.withdrawRoute(failedRoute);
      }
    }
  }
}

Features:

1. OSPF: Internal routing, fast convergence
2. BGP: External routing, internet connectivity
3. Route selection: Prefer OSPF for internal, BGP for external
4. Load balancing: ECMP for multiple paths
5. Failover: Automatic route updates on failure

---

Key Takeaways

• OSPF: Link-state IGP, uses Dijkstra, fast convergence, within AS
• BGP: Path-vector EGP, best path selection, internet routing, between ASes
• OSPF areas: Hierarchical design for scalability
• BGP attributes: AS Path, Local Preference, MED for path selection
• Route selection: OSPF for internal, BGP for external
• Convergence: OSPF fast, BGP slower but more stable
• Best practices: Design OSPF areas carefully, filter BGP routes, monitor routing tables