Routing Protocols: RIP, OSPF, BGP & Routing Algorithms
---
1. Routing Algorithm Types
Distance-Vector Routing
- Each router knows only the distance (hop count or metric) to each destination and the direction (vector/next hop) to reach it
- Bellman-Ford algorithm: Iteratively update shortest path estimates based on neighbours' information
- Distributed computation: Each router shares its routing table with direct neighbours only
- Convergence: Slow — changes propagate hop-by-hop ("count to infinity" problem)
Link-State Routing
- Each router knows the complete network topology (all links and their costs)
- Dijkstra's algorithm: Each router independently computes the shortest path tree
- Flooding: Each router floods Link State Advertisements (LSAs) to all other routers
- Convergence: Fast — all routers have consistent topology view after flooding
Path-Vector Routing
- Extension of distance-vector for inter-domain routing (between Autonomous Systems)
- Each route advertisement includes the complete AS path to the destination
- Prevents routing loops and allows policy-based routing decisions
| Algorithm | Protocol | Convergence | Scale | Loop Risk |
|---|---|---|---|---|
| Distance-Vector | RIP | Slow | Small | Yes (count to infinity) |
| Link-State | OSPF, IS-IS | Fast | Large | No (each router has full map) |
| Path-Vector | BGP | Slow | Internet-scale | No (AS path prevents loops) |
---
2. RIP (Routing Information Protocol)
RIP is a classic distance-vector protocol using hop count as its metric.
RIP Characteristics
| Feature | RIPv1 | RIPv2 |
|---|---|---|
| Metric | Hop count (max 15) | Hop count (max 15) |
| Classful/Classless | Classful only | Classless (CIDR support) |
| Updates | Broadcast (255.255.255.255) | Multicast (224.0.0.9) |
| Authentication | None | MD5 or plain text |
| VLSM support | No | Yes |
RIP Limitations
- Maximum 15 hops — any destination with metric ≥ 16 is considered unreachable. Cannot be used in large networks.
- Count-to-infinity problem: When a link fails, routers may iteratively increment metric in a loop until it reaches 16. Solutions: split horizon, route poisoning, holddown timers.
- Convergence: Very slow — uses periodic updates every 30 seconds.
Split Horizon Rule: A router does not advertise a route back out the interface through which it was learned — prevents some routing loops.
---
3. OSPF (Open Shortest Path First)
OSPF is a link-state protocol using bandwidth-based cost as its metric.
OSPF Concepts
| Concept | Description |
|---|---|
| Router ID | 32-bit identifier for each OSPF router (highest IP or configured) |
| LSA (Link State Advertisement) | Each router floods LSAs describing its directly connected links |
| LSDB (Link State Database) | All received LSAs — complete topology map |
| SPF Algorithm | Dijkstra runs on LSDB to compute shortest path tree |
| Designated Router (DR) | Elected on multi-access networks to reduce LSA flooding |
| Area | OSPF divides large networks into areas to limit LSA flooding scope |
OSPF Hierarchy
- Area 0 (Backbone): The central OSPF area — all other areas must connect to it
- Internal routers: All interfaces in same area
- ABR (Area Border Router): Connects two or more areas; summarises routes
- ASBR (Autonomous System Boundary Router): Connects OSPF domain to external routing domains
OSPF Metric (Cost)
Cost = 10^8 / Bandwidth (bps)
- 100 Mbps Ethernet: cost = 10^8 / 10^8 = 1
- 10 Mbps Ethernet: cost = 10^8 / 10^7 = 10
- T1 (1.544 Mbps): cost = 10^8 / 1,544,000 ≈ 64
Exam Tip: OSPF uses Dijkstra's algorithm; RIP uses Bellman-Ford. OSPF metric = 10^8 / bandwidth. OSPF is open standard; EIGRP is Cisco proprietary. OSPF area 0 is the backbone — required.
---
4. BGP (Border Gateway Protocol)
BGP is the path-vector protocol that runs the global internet — the only protocol connecting different Autonomous Systems (ASes).
BGP Key Concepts
| Concept | Description |
|---|---|
| AS (Autonomous System) | Set of networks under single administrative control |
| ASN (AS Number) | Unique identifier for each AS (e.g., AS 15169 = Google) |
| eBGP | BGP between routers in different ASes |
| iBGP | BGP between routers in the same AS |
| AS Path | List of AS numbers a route has passed through — loop prevention |
| Next Hop | IP address of the next-hop router to reach the prefix |
BGP Path Selection (simplified priority order)
- Highest Local Preference (iBGP — prefer certain exit points)
- Shortest AS Path length
- Lowest Origin type (IGP < EGP < Incomplete)
- Lowest MED (Multi-Exit Discriminator — hint to neighbours)
- eBGP over iBGP
- Lowest IGP cost to Next Hop
- Lowest Router ID as tiebreaker
---
5. Static vs Dynamic Routing
| Feature | Static Routing | Dynamic Routing (RIP/OSPF/BGP) |
|---|---|---|
| Configuration | Manual | Automatic (protocol learns routes) |
| Maintenance | Manual update needed on change | Auto-converges after topology change |
| Scalability | Poor (impractical for large nets) | Good |
| Security | Higher (no routing protocol exploits) | Lower (routing protocol attacks possible) |
| Overhead | None (no protocol bandwidth) | Some (update/LSA messages) |
| Best for | Small networks, stub routes, default routes | Medium to large networks |
---
6. Routing Protocol Comparison Table
| Feature | RIP | OSPF | EIGRP | BGP |
|---|---|---|---|---|
| Type | Distance-Vector | Link-State | Advanced D-V | Path-Vector |
| Algorithm | Bellman-Ford | Dijkstra | DUAL | Path-Vector |
| Metric | Hop count | Cost (bandwidth) | Composite | AS Path + attrs |
| Convergence | Slow (minutes) | Fast (seconds) | Very fast | Slow (minutes) |
| Max hops | 15 | Unlimited | Unlimited | Unlimited |
| Scale | Small | Large | Large | Internet-scale |
| Standard | Open | Open | Cisco proprietary | Open |
| AD (Cisco) | 120 | 110 | 90 | 20 (eBGP) |
Exam Tip: Administrative Distance (AD) on Cisco routers: directly connected = 0, static = 1, EIGRP = 90, OSPF = 110, RIP = 120. Lower AD = more trusted. When multiple protocols know a route, the lowest AD wins.
---
Study Deep: How Internet Routing Works
- BGP is the glue of the internet: ~70,000 ASes worldwide exchange reachability information via BGP. When you access a website, BGP determines which path your packets take across international networks.
- Route flapping: Unstable BGP routes (repeatedly appearing/disappearing) cause massive convergence events. Route dampening suppresses unstable routes temporarily.
- OSPF in enterprise: Most corporate networks use OSPF internally with multiple areas to partition the network and limit LSA flooding scope.
- Software-defined routing: Modern data centres increasingly use BGP even for internal routing (BGP in the data centre), replacing traditional OSPF.