Kurose and Ross, Computer Networking: A Top-Down Approach, section 5.3, cross-checked against RFC 2328 (OSPF Version 2), RFC 1930 (Guidelines for creation, selection, and registration of an Autonomous System) and RFC 6793 (BGP Support for Four-Octet Autonomous System (AS) Number Space). Every cost and path below was computed in code.
Learn the two reasons for autonomous systems first: scale and autonomy. Then treat OSPF as the Dijkstra guide plus a few practical details. Finish by drawing the area picture from memory and labeling every router type.
Many slides say “boundary router” for the router that connects an OSPF network to other autonomous systems. The standard name, in RFC 2328, is AS boundary router (ASBR). Both mean the same router. This is the textbook’s gateway router, seen from inside OSPF.
The picture: city buses and flights#
Picture travel between cities. Inside your own city, the bus company knows every street. It plans routes however it likes, and no other city cares how.
Between cities, you do not need to know the streets of the city you are flying to. You only need to know which airport connects to it.
The Internet works the same way. Each organization’s network is a city with its own bus plan: that is intra-AS routing, and OSPF is one of the most widely used plans. The links between networks are the flights: that is inter-AS routing, done by BGP, the next guide’s topic.
Vocabulary, before anything uses it#
| Term | What it means |
|---|---|
| Autonomous system (AS) | A group of routers run by one organization under one routing policy. “Autonomous” means self-governing. |
| ASN | Autonomous system number: the unique number that names an AS. |
| Gateway router | A router at the edge of an AS with a link to a router in another AS. |
| Intra-AS routing | Routing among the routers inside one AS. |
| Inter-AS routing | Routing between different ASes. On the Internet this is always BGP. |
| OSPF | Open Shortest Path First: a link-state intra-AS protocol. “Open” means its specification is public. |
| LSA | Link-state advertisement: a message in which a router lists its own links and their costs. |
| Flooding | Sending a message to every router in a region, each router passing it on to its neighbors. |
| Link cost | A number on each link, also called its weight. OSPF finds the path with the lowest total cost. |
| Area | A section of an OSPF network. LSAs flood only inside their own area. |
| Backbone | The special area, area 0, that connects all the other areas. |
| Area border router (ABR) | A router in both its own area and the backbone, passing summaries between them. |
Why one flat routing scheme cannot work#
The last two guides pretended every router is equal and knows about every other one. That fails on the real Internet for two reasons.
Scale. There are far too many destinations. Suppose every router kept one entry for every possible /24 network in IPv4 (a /24 is a block of 256 addresses). That is 224 = 16,777,216 entries, and every change anywhere would have to reach every router. Flooding would swamp the links, and distance vector would never converge, meaning settle on stable answers.
Administrative autonomy. The Internet is a network of networks, each with an owner. A company or an ISP (Internet service provider) wants to run its network its own way, and may want to hide how it is built.
The fix is to group routers into autonomous systems. An AS is usually one organization, though a large ISP may split its network into several. ASNs began as 16-bit numbers, allowing 216 = 65,536 of them. They can now be 32 bits, allowing 232 = 4,294,967,296. Inside an AS, all routers run the same intra-AS protocol, chosen by the owner. Between ASes, everyone runs the same inter-AS protocol, so they can understand each other.
Intra-AS vs inter-AS routing#
| Intra-AS routing | Inter-AS routing | |
|---|---|---|
| Between which routers | Routers in the same AS | Gateway routers in different ASes |
| Who chooses the protocol | The AS’s owner, freely | Nobody alone: the whole Internet uses BGP |
| Main goal | Performance: low-cost paths | Policy first: who may carry whose traffic |
| Examples | OSPF, IS-IS (another link-state protocol), RIP | BGP |
The two inter-AS jobs
Take an AS with two gateway routers, one linked to AS X and one to AS Y. For traffic leaving the AS, it must:
- Learn which destinations are reachable through AS X and which through AS Y.
- Spread that knowledge to every router inside the AS, so each can head for the right gateway.
If an AS has only one gateway, there is nothing to choose. Its routers can use a default route: “anything I do not recognize, send toward the gateway”.
One more name: RIP (Routing Information Protocol) is an older distance-vector intra-AS protocol. Every link costs 1, and 16 means “unreachable”, so paths are capped at 15 hops. It suits only small networks.
OSPF: link-state routing, run for real#
Each OSPF router does four things:
- Describe its links in an LSA: each link and its cost.
- Flood the LSA to every router in the AS (or area). It does this whenever a link changes, and at least once every 30 minutes anyway.
- Build the map. From all the LSAs, every router builds the same complete map, the link-state database.
- Run Dijkstra from itself to every subnet, and fill in its forwarding table from the result.
OSPF messages ride directly inside IP datagrams, with upper-layer protocol number 89. There is no TCP or UDP underneath, so OSPF acknowledges its own messages.
Who sets the link costs?
The network administrator. OSPF finds lowest-cost paths but does not say how to choose the costs. Setting every cost to 1 gives minimum-hop routing. A common habit makes fast links cheap:
cost = reference bandwidth ÷ link bandwidth, never below 1
Take a reference bandwidth (the speed that counts as cost 1) of 1,000 Mbps. A 10 Mbps link costs 1,000 ÷ 10 = 100, a 100 Mbps link costs 10, and a 1 Gbps link costs 1.
Five routers, R1 to R5, are joined by six links. The 1 Gbps links, each cost 1, are R1–R3, R2–R4 and R3–R5. The 100 Mbps links, each cost 10, are R1–R2 and R3–R4. The one 10 Mbps link, cost 100, is R4–R5.
Dijkstra at R1 adds R3 (cost 1), then R5 (2, via R3), then R2 (10), then R4 (11). R4 has two paths of cost 11: R1→R2→R4 (10 + 1) and R1→R3→R4 (1 + 10).
| Destination | Cost from R1 | Path(s) | R1 sends toward |
|---|---|---|---|
| R2 | 10 | R1→R2 | R2 |
| R3 | 1 | R1→R3 | R3 |
| R4 | 11 | R1→R2→R4 and R1→R3→R4 | R2 and R3 (OSPF may split traffic) |
| R5 | 2 | R1→R3→R5 | R3 |
Costs are a steering wheel. Upgrade R1–R2 to 1 Gbps and its cost drops to 1. R4 then costs 2 via R2 alone, and the tie is gone.
The cost formula is not part of the OSPF standard. One widely used vendor default takes a reference bandwidth of 100 Mbps. Then a 100 Mbps link and a 1 Gbps link both cost 1, because nothing goes below 1, and OSPF cannot tell them apart. So administrators raise the reference on modern networks.
The “advanced” features
- Security. Messages can be authenticated: a router checks a shared password or cryptographic hash before trusting them. An outsider then cannot inject fake LSAs to pull traffic through their own machine.
- Multiple same-cost paths. When paths tie, as R1→R4 did, OSPF may use both at once.
- Integrated unicast and multicast. An extension, MOSPF, reused the same map for multicast (one sender to a group). It is rarely used today.
- Hierarchy inside one AS, using areas.
Hierarchical OSPF: areas and the backbone#
A big AS has the scale problem in miniature: every change floods everywhere, and every router runs Dijkstra on the whole map. So the administrator can cut the AS into areas. LSAs flood only inside their area, and each router knows only its own area’s map. Exactly one area is the backbone (area 0). Every other area connects to it, and traffic between two areas always crosses it.
| Router type | Where it sits | What it does |
|---|---|---|
| Internal router | All its links in one area (a router entirely inside area 0 is both an internal router and a backbone router) | Routes within its area only. |
| Area border router (ABR) | In its own area and the backbone | Summarizes how far away its area’s networks are, and advertises that to the backbone, and passes the backbone’s summaries into its area. |
| Backbone router | Inside the backbone | Routes traffic between areas. Every ABR is also one. |
| AS boundary router (ASBR) | At the edge of the AS | Exchanges routes with other ASes (on the Internet, using BGP), and brings them into OSPF. |
A host in area 1 sends to a host in area 3 of the same AS. The datagram goes through area 1’s internal routers to area 1’s ABR, across the backbone to area 3’s ABR, then through area 3’s internal routers. It never enters area 2.
Say a 200-router AS is split into four areas of 50. When a link inside area 2 fails, the detailed LSA floods to about 50 routers, not 200. The other areas see only a new summary from area 2’s ABR.
The Internet is split into autonomous systems because of scale and administrative autonomy; inside each AS a protocol such as OSPF floods link-state advertisements, runs Dijkstra in every router over administrator-set costs, and can split a large AS into areas joined by a backbone, while BGP routes between ASes.
Practice#
Where a question mentions R1 to R5, use the five-router network from the OSPF section. Run Dijkstra on paper first.
- Give the two reasons the Internet is not run as one flat routing system, with one sentence each.
- With a reference bandwidth of 1,000 Mbps, what OSPF cost does each link get? (a) 10 Mbps, (b) 100 Mbps, (c) 1 Gbps, (d) 10 Gbps.
- The R3–R4 link fails. What is R1’s new lowest-cost path to R4, and its cost?
- In the original network, the administrator raises the cost of R3–R5 from 1 to 200. What is R1’s lowest-cost path (or paths) to R5 now, and the cost?
- A small company network has exactly one link to its ISP. Do its internal routers need the outside world’s routes?
- An OSPF network has four areas plus the backbone. A link inside area 4 changes cost. Which routers receive the detailed LSA?
- A datagram goes from a host in area 2 to a host in area 1 of the same AS. List, in order, the kinds of router it passes through.
Solutions#
Find the first line where your working split from the solution, and redo the problem from that line. Do not just read the answer and nod.
- Scale and administrative autonomy. Scale: too many destinations for every router to store and update, and the routing messages would swamp the links. Autonomy: each organization wants to run, and perhaps hide, its own network.
- (a) 100, (b) 10, (c) 1, (d) 1. 1,000 ÷ 10 = 100 and 1,000 ÷ 100 = 10. 1,000 ÷ 1,000 = 1. For 10 Gbps, 1,000 ÷ 10,000 = 0.1, but costs cannot go below 1, so it is also 1.
- R1→R2→R4, cost 11. The other cost-11 path used R3–R4, which is gone. The only other route, R1→R3→R5→R4, costs 1 + 1 + 100 = 102.
- Two paths tie at cost 111: R1→R2→R4→R5 and R1→R3→R4→R5. 10 + 1 + 100 = 111 and 1 + 10 + 100 = 111. The old path R1→R3→R5 now costs 1 + 200 = 201. OSPF may split traffic over the two cost-111 paths.
- No. A default route is enough. With one gateway there is no choice to make, so anything not recognized goes toward the gateway.
- Only the routers in area 4, including its ABR. Floods stay inside their area. The other areas see only the updated summary the ABR passes to the backbone.
- Area 2 internal routers, area 2’s ABR, backbone routers, area 1’s ABR, area 1 internal routers. Traffic between two areas always crosses the backbone.
Test-readiness checklist#
- ☐ I can give the two reasons for autonomous systems: scale and administrative autonomy.
- ☐ I can define an AS, an ASN and a gateway router, and say when a default route is enough.
- ☐ I can compare intra-AS and inter-AS routing and name the protocols for each.
- ☐ I can list the four steps of an OSPF router, and say that OSPF runs over IP as protocol 89.
- ☐ I can turn bandwidths into OSPF costs, and say why the formula varies between vendors.
- ☐ I can run Dijkstra on a small OSPF network and spot equal-cost paths.
- ☐ I can draw hierarchical OSPF and label internal routers, ABRs, the backbone and the ASBR.
For any routing question, first ask: inside one AS, or between ASes? Inside means OSPF, IS-IS or RIP, aiming for low cost. Between means BGP, aiming for policy.
Frequently asked questions#
What is an autonomous system?
An autonomous system is a group of routers under one administrative control with one routing policy, usually one organization such as an ISP or a company. Each AS has a unique number, and the Internet is a network of many thousands of them.
What is the difference between intra-AS and inter-AS routing?
Intra-AS routing finds paths inside one autonomous system, using a protocol its owner chooses, such as OSPF. Inter-AS routing finds paths between autonomous systems, and the whole Internet uses one protocol for it: BGP.
How does OSPF work?
Each OSPF router floods link-state advertisements listing its links and their costs to every router in its area. Every router builds the same map from them, runs Dijkstra's algorithm to find the lowest-cost path to every subnet, and fills in its forwarding table. The administrator sets the link costs.
What is an OSPF area?
An area is a section of an OSPF network. Link-state advertisements flood only within their area, and area border routers pass summaries to the backbone area, area 0, which connects all the areas. This keeps flooding and Dijkstra small in a large network.
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written.
Test yourself on this topic
The free networking practice app has 10 questions on this guide and 500 across the whole course, each with an explanation for every answer. Offline, no ads, no account.
Practise this topic →