Routing Algorithms Explained: RIP, OSPF, and BGP

Section 01

The Routing Problem — Why Packets Need a Map

📖 Real World Analogy

GPS vs. Old-School Driving Directions

Imagine you need to drive from London to Edinburgh. You could ask one person who knows the entire UK road network (link state), ask your neighbour who only knows the next city (distance vector), or follow a pre-negotiated international highway agreement that ignores local traffic completely (path vector).

Each strategy is a routing algorithm. None is universally "best" — they trade off how much each router knows against how much they need to communicate. The entire Internet runs on all three, layered on top of each other.

Every time you load a webpage, your data travels across dozens of routers — physical devices that forward packets hop-by-hop toward the destination. Each router must answer one question: where do I send this packet next? Routing algorithms decide that answer.

🌍

The Three Algorithms That Run the Internet

RIP (Distance Vector) — lightweight, each router only knows costs to neighbours.
OSPF (Link State) — each router knows the entire network map and computes shortest paths.
BGP (Path Vector) — glues autonomous systems together using policy-based routing.

📶 Key Terminology Before We Begin

Router

A network device that forwards packets. Runs one or more routing protocols.

Route

A path from source to destination, with an associated cost or metric.

Autonomous System — a network under a single administrative domain (e.g., Google, BT, Vodafone).

IGP

Interior Gateway Protocol — routing within an AS (RIP, OSPF).

EGP

Exterior Gateway Protocol — routing between autonomous systems (BGP).

Metric

A number representing the "cost" of a route. Lower is better in most protocols.

Section 02

Distance Vector Routing — RIP

Distance Vector is the oldest and simplest approach to routing. Each router maintains a routing table containing the best-known distance to every destination, and which neighbour to use to get there. Routers share their entire table with direct neighbours only — they never see the whole network.

📖 Analogy

The Postal Worker Who Only Asks Their Neighbours

You are a postal worker in a town. You don't have a map of the whole country. Every morning you ask the workers next door: "How far are you from Paris?" If they say "3 hops," you know Paris is 4 hops from you (via them).

Next morning you update your table and share it again. Slowly, correct information spreads across the network — but only as fast as the morning gossip rounds. And if a road closes, you might keep recommending it for a long time before the bad news reaches you. This is called count-to-infinity.

The Bellman-Ford Equation

Distance Vector is based on the Bellman-Ford algorithm. The core update rule every router uses:

Bellman-Ford Update

D(x,y) = min_v { c(x,v) + D(v,y) }

The cost from x to y = the minimum over all neighbours v of (cost to v) + (v's cost to y).

RIP Metric

metric = hop count (1–15)

RIP uses hop count as its only metric. 16 hops = infinity (unreachable). Limits RIP to small networks.

🏭 Animated: How Distance Vectors Converge

▶ RIP Convergence Animation — 4-Router Network

Step 0 of 4

💡 Click "Next Step" to watch distance vectors exchange and routing tables converge.

RIP — The Protocol in Practice

📈

RIP v1

RFC 1058 — 1988

Classful routing only. Broadcasts updates every 30 seconds to 255.255.255.255. No authentication. No VLSM support. Still found in some legacy embedded devices.

📉

RIP v2

RFC 2453 — 1998

Classless routing with subnet masks. Uses multicast 224.0.0.9. Supports MD5 authentication. Still widely used in small enterprise and branch networks.

🌐

RIPng

RFC 2080 — IPv6

RIP for IPv6. Uses multicast FF02::9. Authentication handled by IPsec. Still limited to 15 hops. Used in small IPv6-only networks.

⚠️

The Count-to-Infinity Problem

If a link fails, a router stops advertising it. But its neighbour might still be advertising a route through that router. The failing router picks up that stale route and adds 1. The count bounces back and forth until it hits 16 (infinity). This is slow convergence by design — a fundamental weakness of Distance Vector. Fixes include split horizon, poison reverse, and triggered updates.

🛠 RIP Loop-Prevention Mechanisms

Split Horizon

Do not advertise a route back on the interface it was learned from.

Poison Reverse

Advertise failed routes with metric 16 (∞) back to their source, making the failure explicit.

Hold-down Timer

After a route is lost, wait 180 s before accepting an alternative. Prevents premature re-installation.

Triggered Update

Send an immediate update when a route changes, rather than waiting 30 s. Speeds convergence.

Real-World RIP: Router Configuration Snapshot

! Cisco IOS — Enabling RIPv2 on a small branch router
Router(config)# router rip
Router(config-router)# version 2
Router(config-router)# network 192.168.10.0
Router(config-router)# network 10.0.0.0
Router(config-router)# no auto-summary          ! Required for VLSM/CIDR
Router(config-router)# passive-interface GigabitEthernet0/1   ! Don't send RIP on LAN

! Verify: show routing table
Router# show ip route rip

! Output:
! R  10.0.1.0/24  [120/1] via 192.168.10.2, 00:00:07, GigabitEthernet0/0
! R  10.0.2.0/24  [120/2] via 192.168.10.2, 00:00:07, GigabitEthernet0/0
!   [AD=120, metric=hop count]

RIP TABLE FIELDS

R = RIP learned route [120/1] = [Administrative Distance / Hop Count] via X = Next-hop router address 00:00:07 = Time since last update received

Section 03

Link State Routing — OSPF

Link State routing gives every router a complete map of the network. Instead of sharing routing tables, routers share Link State Advertisements (LSAs) — small packets that describe each router's direct connections and their costs. Every router floods LSAs across the network, builds an identical topology database, and then runs Dijkstra's Shortest Path First algorithm locally.

📖 Analogy

The GPS Navigator with a Full Road Map

Unlike the postal worker, imagine you have a complete Google Maps of every road, with live traffic data. You can calculate the exact fastest route yourself — no need to ask neighbours. But downloading that full map takes bandwidth, and keeping it updated as roads change requires constant communication. This is OSPF.

The trade-off: OSPF converges much faster than RIP and supports complex topologies — but it's significantly more complex to configure and more demanding on CPU and memory.

OSPF Key Concepts

📋

LSA — Link State Advertisement

The building block

A packet describing a router's interfaces and costs. Each router floods its LSA to all OSPF routers. Types include Router LSA, Network LSA, Summary LSA, and External LSA.

📌

LSDB — Link State Database

The full network map

Each router stores all received LSAs. All routers in an OSPF area have identical LSDBs. Dijkstra runs on this database to produce the routing table.

🏛

Area — OSPF Hierarchy

Scalability mechanism

Large networks are split into areas. Area 0 (backbone) connects all others. LSA flooding is contained within areas, reducing overhead dramatically.

🏭 Animated: Dijkstra's Algorithm on an OSPF Network

▶ SPF (Dijkstra) Animation — Computing Shortest Paths from Router A

Step 0

💡 Dijkstra visits the lowest-cost unvisited node at each step. Green = settled, amber = in queue.

OSPF Areas — The Scalability Answer

🏛 OSPF Area Architecture

ABR = Area Border Router. It sits in two areas and summarises routes between them, shrinking the LSDB within each area.

OSPF Metric — Cost = 10⁸ / Bandwidth

OSPF Cost Formula

Cost = 10⁸ / link_bandwidth_bps

A 100 Mbps link: cost = 10⁸/10⁸ = 1. A 10 Mbps link: cost = 10. Faster links have lower costs — OSPF automatically prefers them.

Common Interface Costs

100M=1 | 10M=10 | T1=64

For gigabit and faster links, you must adjust the reference bandwidth: auto-cost reference-bandwidth 10000 for a 10G reference.

OSPF — Cisco IOS Configuration

! OSPF multi-area configuration — Cisco IOS
Router(config)# router ospf 1
Router(config-router)# router-id 1.1.1.1              ! Unique 32-bit ID
Router(config-router)# auto-cost reference-bandwidth 10000  ! 10Gbps ref for modern nets
Router(config-router)# network 192.168.1.0 0.0.0.255 area 0
Router(config-router)# network 10.10.0.0 0.0.255.255 area 1
Router(config-router)# passive-interface GigabitEthernet0/2

! Verify OSPF neighbours and database
Router# show ip ospf neighbor
Router# show ip ospf database
Router# show ip route ospf

OSPF NEIGHBOR TABLE (SAMPLE)

Neighbor ID Pri State Dead Time Address Interface 2.2.2.2 1 FULL/DR 00:00:34 10.10.1.2 GigEth0/0 3.3.3.3 1 FULL/BDR 00:00:38 10.10.1.3 GigEth0/0 State FULL = adjacency established, LSDBs are synchronised DR = Designated Router (elected on broadcast segments) BDR = Backup Designated Router

💡

DR/BDR Election — Why OSPF Elects a Leader on LANs

On a broadcast segment (e.g., Ethernet switch), N routers would form N(N-1)/2 adjacencies — an O(N²) problem. OSPF elects a Designated Router (DR) and Backup DR (BDR). All others form adjacencies only with DR/BDR, reducing the problem to O(N). The DR floods LSAs on behalf of the segment. DR is elected by highest OSPF priority (default 1), then highest Router-ID.

Section 04

Path Vector Routing — BGP

BGP (Border Gateway Protocol) is the routing protocol of the Internet. It connects Autonomous Systems (AS) — the ~75,000+ independent networks operated by ISPs, cloud providers, enterprises, and governments. BGP is fundamentally different from RIP and OSPF: it does not try to find the shortest path. It finds the best policy-compliant path.

📖 Analogy

International Trade Routes, Not Just Highways

Imagine the world's shipping routes. A cargo ship from Tokyo to Rotterdam might not take the absolute shortest sea distance — it avoids war zones, uses preferred ports, respects trade agreements, and chooses partners it has commercial relationships with.

BGP works the same way. An ISP in the US might prefer to route traffic through its own network rather than a competitor's, even if the competitor's path is physically shorter. BGP encodes business relationships and policy, not just geography.

BGP: Path Vector vs. Distance Vector

📈 Distance Vector (RIP)

Destination	Cost	Next Hop
10.0.1.0/24	3	192.168.1.1
10.0.2.0/24	5	192.168.1.1

Only knows cost and next hop. Can't detect loops — the path is opaque.

📌 Path Vector (BGP)

Prefix	AS Path	Next Hop
10.0.1.0/24	AS64500 AS64501	203.0.113.1
10.0.2.0/24	AS64500 AS64502 AS64503	203.0.113.1

Knows the full AS path. Loop detection is trivial: if your own AS number appears in the path, discard it.

BGP Message Types

👋

OPEN

TCP:179 — Session setup

Sent after TCP session established. Contains AS number, Hold Time, BGP Identifier (Router-ID), and optional capabilities (e.g., 4-byte ASN support).

📤

UPDATE

Route advertisement & withdrawal

Contains new reachable prefixes (NLRI) and withdrawn routes. Carries Path Attributes including AS_PATH, NEXT_HOP, LOCAL_PREF, MED, and COMMUNITY.

💔

KEEPALIVE / NOTIFICATION

Health check / Error reporting

KEEPALIVE sent every 60s (default) to maintain the session. NOTIFICATION immediately terminates the session and reports the error code and sub-code.

🏭 Animated: AS-Path in Action

▶ BGP AS-Path Advertisement — Tracing a Route Across the Internet

Step 0

💡 Watch an UPDATE message travel from AS64500 (origin) to AS64503, accumulating AS numbers in the path attribute at each hop.

BGP Path Selection — The Decision Process

When BGP receives multiple paths to the same prefix, it applies a decision process in order. The first attribute that differs determines the winner:

Highest Weight (Cisco proprietary)

Local to the router only. Set with route-maps. Default 0; locally-originated routes get 32768.

Highest LOCAL_PREF

Shared within the AS. Controls egress (outbound) traffic. Default 100. Set by inbound policy from eBGP peers.

Locally Originated (network/aggregate)

Prefer routes originated by this router over routes learned from iBGP peers.

Shortest AS_PATH

Fewer AS hops = preferred. Can be manipulated with AS_PATH prepending to make a path look less attractive.

Lowest ORIGIN code

IGP (i) < EGP (e) < Incomplete (?). Usually IGP from network statement wins.

Lowest MED → Lowest Router-ID

MED (Multi-Exit Discriminator) is a hint to neighbouring AS about preferred entry point. Tie-breaking finally falls to lowest BGP Router-ID.

iBGP vs eBGP

eBGP — External BGP

Property	Value
Between	Different AS routers
TTL	1 (directly connected peers)
NEXT_HOP	Changed to own address
LOCAL_PREF	Set on ingress from eBGP

iBGP — Internal BGP

Property	Value
Between	Same AS routers
TTL	255 (can span multiple hops)
NEXT_HOP	Preserved from eBGP peer
Full Mesh	Required (or use Route Reflectors)

⚠️

iBGP Full-Mesh Requirement & Route Reflectors

iBGP does not re-advertise routes learned from one iBGP peer to another — it prevents loops within the AS. This means all iBGP routers must be in a full mesh: N(N-1)/2 sessions. With 100 routers that's 4,950 sessions. Route Reflectors (RFC 4456) solve this: a designated RR re-advertises routes to its clients, breaking the full-mesh requirement.

BGP Configuration — Cisco IOS

! BGP peering setup — Router in AS 64500
Router(config)# router bgp 64500
Router(config-router)# bgp router-id 1.1.1.1
Router(config-router)# bgp log-neighbor-changes

! eBGP peer in AS 64501
Router(config-router)# neighbor 203.0.113.2 remote-as 64501
Router(config-router)# neighbor 203.0.113.2 description eBGP-to-AS64501

! iBGP peer in same AS (loopback-based, TTL update needed)
Router(config-router)# neighbor 10.0.0.2 remote-as 64500
Router(config-router)# neighbor 10.0.0.2 update-source Loopback0

! Originate our prefix into BGP
Router(config-router)# network 198.51.100.0 mask 255.255.255.0

! Verify
Router# show bgp ipv4 unicast summary
Router# show bgp ipv4 unicast 198.51.100.0/24

Section 05

RIP vs OSPF vs BGP — Side-by-Side

Property	RIP	OSPF	BGP
Algorithm Type	Distance Vector	Link State	Path Vector
Algorithm	Bellman-Ford	Dijkstra (SPF)	Policy-based selection
Scope	IGP (within AS)	IGP (within AS)	EGP (between AS)
Metric	Hop count (max 15)	Cost (bandwidth-based)	AS_PATH + policy attributes
Network scale	Small (<15 hops)	Medium–large (1,000s of routers)	Entire Internet (~900,000 prefixes)
Convergence speed	Slow (minutes)	Fast (seconds)	Very slow (minutes to hours)
Loop prevention	Split horizon / Poison reverse	SPF (topology is fully known)	AS_PATH loop detection
Transport	UDP port 520	IP Protocol 89	TCP port 179
Config complexity	Very simple	Moderate–complex	Complex (policy-heavy)
Supports VLSM/CIDR	v2 only	Yes	Yes
Authentication	MD5 (v2)	MD5 / SHA	MD5 / TCP-AO
Typical use today	Legacy / embedded	Enterprise LAN / WAN core	ISP peering / data centres

Section 06

When Routing Goes Wrong — Real Incidents

🌐

2010 — China Telecom BGP Hijack

China Telecom briefly advertised ~50,000 IP prefixes belonging to US military, government, and commercial sites. Traffic was rerouted through Chinese networks for approximately 18 minutes. Cause: an incorrect BGP origin attribute — no malicious intent proven, but the incident exposed how easily BGP can be weaponised without cryptographic validation. Motivated work on RPKI (Resource Public Key Infrastructure).

Protocol: BGP | Root Cause: No route origin validation

🔥

2021 — Facebook 6-Hour Outage

A configuration change removed all of Facebook's BGP routes from the global Internet routing table — effectively making their AS invisible. Their internal DNS servers could not reach the outside world. Even internal tools used to fix the problem required network access. Engineers needed physical access to data centres to restore BGP peering. The outage cost an estimated $60 million in revenue and affected 3.5 billion users across Facebook, Instagram, and WhatsApp.

Protocol: BGP | Root Cause: Misconfigured route withdrawal

⚡

2019 — Cloudflare Route Leak via Verizon

A small Pennsylvania ISP (AS396531) leaked over 20,000 routes to Verizon (AS701), which accepted and propagated them globally. Traffic meant for Amazon, Cloudflare, and others was routed through a tiny ISP completely unequipped to handle it. Cloudflare, AWS, and Linode went down for hours globally. BGP has no built-in verification that a peer is authorised to advertise a prefix — RPKI and IRR filtering could have prevented this.

Protocol: BGP | Root Cause: Missing prefix filters + RPKI

🔑

RPKI — The Fix for BGP's Trust Problem

Resource Public Key Infrastructure (RPKI) is a cryptographic framework that lets IP address holders digitally sign which AS is authorised to originate their prefixes. Routers receiving a BGP route can validate it against the RPKI. As of 2024, about 50% of the global routing table is covered by RPKI ROAs (Route Origin Authorizations). Major ISPs including AT&T, Comcast, Deutsche Telekom, and NTT now enforce RPKI route origin validation.

Section 07

Where Each Protocol Lives — The Protocol Ecosystem

🏛 Internet Architecture — Protocol Placement

IGPs (OSPF/RIP) run inside each AS for internal reachability. BGP runs between ASes, exchanging reachability information about the prefixes each AS can reach.

Section 08

Golden Rules & Practitioner Checklist

📌 Routing Protocol Selection & Design Rules

Never use RIP on a network with more than 7–8 hops end-to-end. The 15-hop limit is not just theoretical — slow convergence at scale causes real outages. Migrate to OSPF or EIGRP.

Always assign explicit OSPF Router-IDs. Relying on the highest active IP address causes unpredictable behaviour when interfaces go up/down. Use a Loopback interface IP — it never flaps.

On OSPF broadcast segments, manually set the DR. Default DR election by priority can result in a low-power router becoming DR. Set ip ospf priority 0 on routers that should never be DR, and ip ospf priority 255 on your dedicated DR.

In BGP, never accept a default route from a peer unless you are a stub AS. Accepting a default route means your router will forward traffic it cannot reach — potentially causing you to become a transit path for others' traffic.

Always use prefix lists + RPKI validation on eBGP sessions. The 2019 Cloudflare outage happened because Verizon had no inbound prefix filtering. Filter what prefixes you accept from each peer, and validate against RPKI.

Administrative Distance (AD) determines which protocol wins when routes overlap. OSPF (AD=110) beats RIP (AD=120). BGP eBGP (AD=20) beats everything except connected (AD=0) and static (AD=1).

Never redistribute between routing protocols without careful filtering. Mutual redistribution (OSPF ↔ RIP) can cause routing loops and suboptimal paths. Always use route-maps with explicit permit/deny logic when redistributing.

🎓

Summary — Which Protocol for Which Job?

RIP: Small branch networks, embedded routers, legacy environments. Simple config, poor scalability, slow convergence — use only when OSPF is too complex to justify.

OSPF: The go-to IGP for enterprise and ISP internal networks. Fast convergence, hierarchical with areas, bandwidth-aware metrics. More complex to configure but far more robust.

BGP: The protocol of the Internet. Required whenever you have multiple upstream ISPs, run a data centre, or operate a CDN. Policy-rich but demands careful design — a misconfiguration can impact millions of users worldwide.