- Authors
- Name
- Youngju Kim
- @fjvbn20031
Internet Routing: OSPF and BGP
The real Internet is a massive network consisting of billions of devices. Computing routes for the entire Internet with a single routing algorithm is impossible from both scalability and management perspectives.
In this post, we examine how the Internet performs hierarchical routing at the Autonomous System (AS) level, intra-AS routing protocols RIP and OSPF, and the inter-AS routing protocol BGP.
1. Need for Hierarchical Routing
1.1 Scalability Problem
If all routers stored and computed the topology of the entire Internet:
- Storage: Forwarding tables for billions of destinations
- Computation: Running routing algorithms on the full topology
- Message Overhead: Link state updates propagating worldwide
1.2 Administrative Autonomy
Each organization (ISP, enterprise, university) wants to independently manage its internal network routing. They should be free to choose their own routing algorithms, policies, and equipment.
Hierarchical Routing Structure
================================
[AS 1: ISP-A] [AS 2: ISP-B] [AS 3: Google]
+-----------+ +-----------+ +-----------+
| R1---R2 | | R5---R6 | | R8---R9 |
| | | |<-------->| | | |<-------->| | | |
| R3---R4 | | R7 | | R10--R11 |
+-----------+ +-----------+ +-----------+
Intra-AS: OSPF, RIP, etc. (intra-AS routing)
Inter-AS: BGP (inter-AS routing)
2. Autonomous System (AS)
2.1 Definition of AS
An Autonomous System (AS) is a group of routers managed under the same routing policy. Each AS has a unique AS Number (ASN).
AS Types
=========
1. Stub AS: Connected to only one other AS (enterprises, universities)
[External] <---> [Stub AS]
2. Multihomed AS: Connected to multiple ASes but no transit traffic
[AS A] <---> [Multihomed AS] <---> [AS B]
3. Transit AS: AS that allows traffic to pass through (ISPs)
[AS A] <---> [Transit AS] <---> [AS B]
Transit allowed
2.2 Gateway Router
A Gateway Router is a router directly connected to a router belonging to another AS. It performs both intra-AS routing and inter-AS routing.
3. RIP (Routing Information Protocol)
3.1 Basic Characteristics
RIP is an intra-AS routing protocol based on the Distance-Vector algorithm.
RIP Characteristics
=====================
- Algorithm: Distance-Vector (Bellman-Ford)
- Metric: Hop count, maximum 15 hops
- Update interval: Sends distance vector to neighbors every 30 seconds
- Timeout: Route invalidated if no update for 180 seconds
- Transport: UDP port 520
- Suitable scope: Small networks (15 hop limit)
3.2 Limitations of RIP
- Maximum of 15 hops makes it unsuitable for large networks
- Slow convergence (count-to-infinity possible)
- Uses only hop count as metric, cannot reflect bandwidth differences
4. OSPF (Open Shortest Path First)
4.1 Basic Characteristics
OSPF is an intra-AS routing protocol based on the Link-State algorithm. It was designed to overcome the limitations of RIP.
OSPF Characteristics
======================
- Algorithm: Link-State (Dijkstra)
- Metric: Bandwidth, delay, etc. configurable by administrator
- Updates: Immediately on change (or 30-minute periodic)
- Transport: IP directly (protocol number 89)
- Authentication: MD5 authentication supported
- Suitable scope: Large networks
4.2 Key Advantages of OSPF
Security: OSPF messages can be authenticated, ensuring only trusted routers participate in routing.
Equal-Cost Multipath: When multiple paths with the same cost exist, traffic can be distributed.
Hierarchical Structure: A single AS can be divided into multiple areas.
OSPF Hierarchical Structure
==============================
[Backbone Area (Area 0)]
/ | \
[Area 1] [Area 2] [Area 3]
+------+ +------+ +------+
|R1 R2| |R4 R5| |R7 R8|
| R3 | | R6 | | R9 |
+------+ +------+ +------+
- Backbone Area (Area 0): Central area connecting all areas
- Area Border Router (ABR): Router spanning two areas
- AS Boundary Router (ASBR): Router connected to another AS
4.3 OSPF Inter-Area Routing
OSPF Inter-Area Routing
=========================
Sending packet from R1 in Area 1 to R9 in Area 3:
R1 (Area 1)
|
| Area 1 internal OSPF routing
v
ABR1 (Area 1 / Backbone boundary)
|
| Backbone (Area 0) OSPF routing
v
ABR3 (Backbone / Area 3 boundary)
|
| Area 3 internal OSPF routing
v
R9 (Area 3)
Within each area: Detailed topology information exchanged
Between areas: Only summarized distance information exchanged
5. BGP (Border Gateway Protocol)
5.1 Role of BGP
BGP is the only protocol responsible for inter-AS routing on the Internet. It serves as the "glue of the Internet," connecting all ASes together.
Two Forms of BGP
==================
1. eBGP (External BGP): Between routers of different ASes
AS1 gateway <---eBGP---> AS2 gateway
2. iBGP (Internal BGP): Between routers within the same AS
AS1 gateway <---iBGP---> AS1 internal router
eBGP: Exchanges route information between ASes
iBGP: Propagates learned route information within the AS
5.2 BGP Routes and Attributes
In BGP, a route is a combination of a destination prefix and path attributes.
BGP Route Advertisement Example
==================================
AS2 advertises to AS1:
Prefix: 138.16.64.0/24
AS-PATH: AS3 AS2
NEXT-HOP: 201.44.13.1
Key Path Attributes:
- AS-PATH: List of ASes the route traverses
Example: AS3 AS2 --> reaches AS3 via AS2
- NEXT-HOP: IP address of gateway router toward next AS
- LOCAL-PREF: Route preference within AS (higher is preferred)
- MED: Value indicating preferred route to other ASes (lower is preferred)
5.3 BGP Route Selection Algorithm
When multiple routes exist, BGP selects the best route in the following order:
BGP Route Selection Priority
==============================
1. Highest LOCAL-PREF (policy-based)
2. Shortest AS-PATH
3. Closest NEXT-HOP (Hot-Potato routing)
4. Smallest BGP identifier
Example:
Route A: LOCAL-PREF=200, AS-PATH=[AS2, AS5], NEXT-HOP=R1
Route B: LOCAL-PREF=100, AS-PATH=[AS3], NEXT-HOP=R2
--> Route A selected (higher LOCAL-PREF)
5.4 Hot-Potato Routing
Hot-Potato routing is a strategy of sending packets out of your own AS as quickly as possible. It selects the nearest gateway considering only intra-AS costs.
Hot-Potato Routing
====================
Inside AS1:
iBGP iBGP
[R1] <-------> [R2] <-------> [R3]
| | |
| Internal | Internal | Internal
| cost 2 | cost 5 | cost 3
| | |
[GW1] [GW2] [GW3]
|eBGP |eBGP |eBGP
v v v
[AS2] [AS3] [AS2]
For R2 to reach a prefix in AS2:
- Via GW1: internal cost 2 (R2->R1->GW1)
- Via GW3: internal cost 3 (R2->R3->GW3)
--> GW1 selected (Hot-Potato: nearest exit)
6. BGP Routing Policies
6.1 Customer-Provider-Peer Relationships
Inter-AS Relationships
========================
[Tier-1 ISP A] <--Peering--> [Tier-1 ISP B]
/ \ / \
Provider Provider Provider Provider
/ \ / \
[Customer AS1] [Customer AS2] [Customer AS3] [Customer AS4]
- Customers pay providers for traffic delivery
- Peers exchange customer traffic for free
- Providers advertise customer routes elsewhere
6.2 Routing Policy Rules
BGP Policy Rules
==================
From the perspective of AS X:
1. Routes received from customers: Advertise to everyone (revenue generating)
2. Routes from peers: Advertise only to customers (not to peers or providers)
3. Routes from providers: Advertise only to customers (not to peers or other providers)
Principle: Traffic passing through incurs costs,
so only actively relay customer traffic that generates revenue
7. Interaction Between OSPF and BGP
In practice, OSPF and BGP work together on routers.
OSPF and BGP Interaction
===========================
Intra-AS:
- OSPF computes shortest paths between routers within the AS
- Each router knows routes to all destinations within the AS
Inter-AS:
- eBGP learns prefix information from external ASes
- iBGP propagates learned information within the AS
- Route to NEXT-HOP is provided by OSPF
Forwarding Table Composition:
Destination Prefix | Next Hop | Source
-------------------+--------------+-------
10.1.0.0/16 | 192.168.1.2 | OSPF
172.16.0.0/12 | 192.168.1.5 | OSPF
8.8.8.0/24 | 10.0.0.1 | BGP
0.0.0.0/0 | 10.0.0.1 | BGP
8. Summary
| Concept | Key Points |
|---|---|
| Hierarchical Routing | Separates internal/external routing at AS level |
| RIP | DV-based, hop count metric, max 15 hops, small scale |
| OSPF | LS-based, flexible metrics, area hierarchy, large scale |
| eBGP | Exchanges route information between ASes |
| iBGP | Propagates external route info within the AS |
| AS-PATH | List of ASes a BGP route traverses |
| Hot-Potato | Strategy of sending traffic to nearest exit |
| LOCAL-PREF | Top priority criterion in BGP route selection (policy) |
In the next post, we will look one layer down the network stack at the link layer's error detection and multiple access protocols.
References
- James F. Kurose, Keith W. Ross, "Computer Networking: A Top-Down Approach", 6th Edition, Chapter 4
- RFC 2328 - OSPF Version 2
- RFC 4271 - A Border Gateway Protocol 4 (BGP-4)
- RFC 2453 - RIP Version 2