Intra-AS Routing in the Internet: OSPF · Computer Networking Interactive

The Internet is too large to route as one graph, so it is divided into autonomous systems. Inside one of them the usual protocol is OSPF (Open Shortest Path First) : link-state routing with Dijkstra, flooded to every router in the system.

Words you will meet

Autonomous system — written AS (Autonomous System) : a group of routers under the same administrative control.
ASN (Autonomous System Number) — the globally unique number that identifies one autonomous system.
Intra-AS routing protocol — the routing protocol run inside one autonomous system.
OSPF — Open Shortest Path First: the link-state intra-AS protocol this section is about.
Area — a piece of one autonomous system that does its own routing.
Backbone area — the one area every other area routes through.
Area border router — a router that belongs to an area and to the backbone.
Traffic engineering — choosing link weights to get the traffic pattern you want.

Why this matters

Sections 5.2.1 and 5.2.2 treated the network as one graph of interchangeable routers, all running the same algorithm over all of it. That model is simple and it does not survive contact with the real Internet.

Two things break it. The Internet is far too large, and it is owned by thousands of separate organisations who do not want to share the inside of their networks.

This section fixes both with one idea: divide the routers into autonomous systems. Then it shows the protocol that runs inside one, OSPF. At its centre is Dijkstra’s algorithm from section 5.2.1. Around that sit authentication, a flooding mechanism and a hierarchy of its own.

Why one flat network does not work

The book gives exactly two reasons, and they are different in kind.

Scale. As the number of routers grows, the work of communicating, computing and storing routing information becomes prohibitive. Today’s Internet holds hundreds of millions of routers. Storing a row for every possible destination in each of them would need enormous amounts of memory. The overhead of broadcasting connectivity and link-cost updates among all of them would be huge. And a DV (Distance-Vector) algorithm iterating among that many routers would never converge.

Administrative autonomy. The Internet is a network of ISP (Internet Service Provider) s, and each one is its own network of routers. An ISP generally wants to operate its network as it pleases. It wants to run whatever routing algorithm it chooses inside it. It also wants to hide how that network is organised from the outside. An organisation should be able to administer its own network freely and still connect to everyone else.

The first is a limit of arithmetic. The second is a matter of ownership. Notice that no amount of faster hardware fixes the second one.

Section 5.2.1 already gave the two costs of running a link-state algorithm over a graph, and a third follows from the table itself:

\text{messages} = O(|N| \cdot |E|) \qquad \text{computation} = O(|N|^2) \qquad \text{memory} = |N| \cdot b

where $|N|$ is how many routers there are, $|E|$ how many links, and $b$ the bytes one forwarding-table row takes. Read aloud: every router learns every link, sorts out the whole graph by itself, and keeps one row per destination. Put the Internet’s own numbers in and see what that comes to.

What one flat Internet-sized routing computation would cost

What each symbol means

|N| — how many routers there are — the size of the set of nodes (routers)
|E| — how many links there are — the size of the set of edges (links)
bytes per entry — memory for one forwarding-table row (bytes)

Read aloud: Every router would have to learn every link, store a row for every destination, and then sort the whole graph out by itself.

Routers in the networkroutersLinks per router, on averagelinksMemory for one table entrybytes

Forwarding table in one router3.20 GB

one entry per destination, in every router
memory = destinations x bytes per entry
       = 2.00e+8 x 16 bytes
       = 3.20 GB — in EVERY router, before any other state
and this is only the table. A router must also hold the whole graph to run Dijkstra on it.

Messages to flood the link state once6.00e+16

|N| = 2.00e+8 routers, each with about 3 links
|E| = |N| x links per router / 2 = 3.00e+8 links
link-state broadcast costs O(|N| . |E|) messages   [section 5.2.1]
       = 2.00e+8 x 3.00e+8 = 6.00e+16 messages
Dijkstra then costs O(|N|^2) = 4.00e+16 operations, in every router
for comparison, a large autonomous system holds a few thousand routers

Change any number above and the arithmetic re-runs, carrying the units through.

The complexities are section 5.2.1’s, unchanged. The default router count is the book’s own "hundreds of millions". The default of 16 bytes per entry is generous — a prefix, a next hop and an interface. Now compare: a large autonomous system holds a few thousand routers, so drag the count down to 5,000 and read the same three lines again.

In plain words

The numbers above are not the reason the Internet is divided. They are the shape of the reason.

A router can hold a table with a few thousand rows and run Dijkstra over a few thousand nodes without difficulty. Neither statement survives being multiplied by a hundred million. The second reason, ownership, would still stand even if the first one did not.

Autonomous systems

Both problems are solved by organising routers into autonomous systems. An autonomous system is a group of routers under the same administrative control.

Often the routers of one ISP, and the links between them, make up a single AS. Some ISPs split their network into several. Some tier-1 ISPs use one gigantic AS for their whole network; others break themselves into tens of interconnected ones.

Each autonomous system is identified by a globally unique autonomous system number, written ASN (Autonomous System Number) , defined in RFC (Request For Comments) 1930. AS numbers are assigned by ICANN (Internet Corporation for Assigned Names and Numbers) regional registries, just as IP (Internet Protocol) addresses are.

All the routers inside one AS run the same routing algorithm and hold information about each other. That algorithm is called an intra-autonomous system routing protocol .

One flat network, or a network of autonomous systems

	One flat networkevery router runs one algorithm over everything	Divided into autonomous systemswhat the Internet actually does
Scale
Administrative autonomy
Memory in one router
Convergence
Who chooses the routing algorithm

Cells marked ⓘ have a reason behind them — click to read it.

The book gives exactly two reasons for the division, and they are the first two rows. Click any cell for the reason.

Everyday picture

A national postal service does not keep one list of every house on Earth. It keeps a list of countries, and each country keeps its own list of streets.

To send a letter abroad you do not need the destination street to be in your country’s list. You need your country to know which country the letter is for, and that country to know the rest.

Where the picture stops. Countries are fixed by geography and an autonomous system is not. Two routers in the same building can belong to different autonomous systems, and one AS can span continents. The boundary is drawn by ownership, not by distance.

Open Shortest Path First

OSPF and its closely related cousin IS-IS (Intermediate System to Intermediate System) are both widely used for intra-AS routing in the Internet.

The Open in the name means the specification is publicly available. The book contrasts it with Cisco’s EIGRP (Enhanced Interior Gateway Routing Protocol) , which stayed proprietary for roughly twenty years and became open only recently. The current version, OSPF version 2, is defined in the public RFC 2328.

OSPF is a link-state protocol. It floods link-state information and it runs Dijkstra’s least-cost path algorithm. Every router builds a complete topological map — a graph — of the entire autonomous system. Each router then runs Dijkstra locally, producing a shortest-path tree to all subnets with itself as the root.

That is section 5.2.1, unchanged. What this section adds is everything around it.

Who hears what

What OSPF routers actually say to each other

HELLO goes to attached neighbours only. It is the one OSPF message that does not travel far.

message 4 of 4

Click any arrow to see what that message says and why it is sent.

Three things OSPF sends, drawn on the same four routers. HELLO reaches one neighbour; a link-state advertisement reaches everybody.

Read this diagram as text

R1 sends HELLO to R2. OSPF checks that links are operational with a HELLO message sent to an attached neighbour. R2 is attached to R1, so it receives one.
R2 sends HELLO to R1. The reply confirms the link works in both directions.
R1 sends HELLO to R3. R3 is also attached to R1, so it is also checked.
R3 sends HELLO to R1. R4 receives no HELLO from R1, because R4 is not attached to R1.

Lifelines, left to right: R1 (router), R2 (router), R3 (router), R4 (router).

Three separate things are happening there, and the book states each one plainly.

A router broadcasts routing information to all other routers in the autonomous system, not just to its neighbouring routers. This is the sentence that makes OSPF link-state rather than distance-vector. Compare section 5.2.2, where a node only ever spoke to the routers at the far end of its own links.

It broadcasts whenever a link’s state changes — a change in cost, or a change between up and down.

It also broadcasts at least once every 30 minutes even when nothing changed. RFC 2328’s own explanation is that “this periodic updating of link state advertisements adds robustness to the link state algorithm”. A router that missed an advertisement is repaired by the next one.

Separately, OSPF checks that links are still working with a HELLO message sent to an attached neighbour. It also lets a router fetch a neighbouring router’s whole database of network-wide link state.

OSPF rides directly on IP

OSPF is carried directly by IP

The usual arrangementstep 1 of 3

A web request rides in a TCP segment, which rides in an IP datagram, which rides in a frame. TCP supplies reliable transfer, so HTTP does not have to.

Almost everything in this book sits on TCP or UDP. OSPF does not. The IP header’s protocol field says 89, and the payload is the OSPF message.

Read all steps as text

The usual arrangement — A web request rides in a TCP segment, which rides in an IP datagram, which rides in a frame. TCP supplies reliable transfer, so HTTP does not have to.
OSPF skips the transport layer — The IP header carries upper-layer protocol number 89, and the next thing in the datagram is the OSPF message. There is no TCP header and no UDP header.
And that has a price — IP is best-effort: it may lose, duplicate or reorder a datagram. Nothing below OSPF repairs that, so the OSPF protocol must implement reliable message transfer, link-state broadcast and authentication by itself.

OSPF advertisements travel in OSPF messages that are carried directly by IP, with an upper-layer protocol number of 89. There is no TCP (Transmission Control Protocol) header and no UDP (User Datagram Protocol) header in between.

In plain words

IP promises nothing. It is best-effort : a datagram may be lost, duplicated or delivered out of order.

Every application in chapter 2 could ignore that, because TCP sat underneath and repaired it. OSPF has nothing underneath. So the OSPF protocol has to implement reliable message transfer itself, and its link-state broadcast itself, and its authentication itself.

That is why OSPF is a large protocol for something that computes a shortest path. Most of it is the machinery TCP would otherwise have provided.

Setting the link weights

OSPF does not say what a link should cost. The network administrator configures the individual link costs, and OSPF only supplies the mechanism for finding least-cost paths given whatever costs it is handed.

The book names two policies an administrator might pick.

Set every link cost to 1, which gives minimum-hop routing.
Set the weight inversely proportional to the link rate, which discourages traffic from using low-rate links.

Setting the link weights, and then setting them backwards

All weights 1 — minimum-hop routingstep 1 of 3

The administrator may set every link cost to 1. Then the cheapest path is the one with the fewest links. Here both paths have two links, so both cost 2, and Dijkstra has no way to prefer the fast one. Capacity is not in the graph at all.

The two weight policies are the book’s own examples. The traffic numbers are constructed, because the sidebar gives none — they are here so the utilization is a number rather than a word.

Read all steps as text

All weights 1 — minimum-hop routing — The administrator may set every link cost to 1. Then the cheapest path is the one with the fewest links. Here both paths have two links, so both cost 2, and Dijkstra has no way to prefer the fast one. Capacity is not in the graph at all.
Weights inversely proportional to capacity — The administrator may instead make a link’s weight small when its rate is high. A 1 Gbps link gets 10 and a 10 Gbps link gets 1. Now the top path costs 20, the bottom costs 2, and traffic avoids the slow links. Here the weight describes the link.
And now the sidebar’s point: run it backwards — An operator often knows the routing they want — for example, one that minimises the highest utilization of any link — and their only control over OSPF is the weights. So the weights stop being a description of the links and become the unknown in a search. The desired routing comes first; the weights that produce it must be found.

Principles in practice: cause and effect, reversed

Everything above assumes the weights come first. They are given, Dijkstra runs, and traffic flows along the paths that result. In that view a weight describes a link, and the algorithm minimises total cost.

In practice the relationship is often the other way round.

Suppose an operator has an estimate of the traffic entering the network at each entry point and leaving at each exit point. The operator may want a specific routing of those flows — for example, one that minimises the maximum utilization over all of the network’s links.

But with a protocol like OSPF, the operator’s only control over how flows are routed is the link weights. So the operator has to find the set of weights that produces the routing they already want. The desired routing is known, and the weights are the unknown. This is traffic engineering .

What else OSPF brings

The four advances the book lists in OSPF

Advance	What it gives you

By default OSPF packets are not authenticated and could be forged. Authentication is something you switch on.



Inter-area routing takes three legs: to an area border router, through the backbone, then to the destination.

Cells marked ⓘ have an explanation — click to read it.

Click a cell marked ⓘ for the detail. The last row is the one this page spends most time on.

The last of those four is a second use of this section’s own idea, one level further down, and it deserves its own picture.

Areas, and the backbone

An OSPF autonomous system can be configured hierarchically into areas . The book describes the arrangement in four sentences and draws no figure, so here is one.

Areas, the backbone, and how a packet crosses between two areas

Each area runs its own link-state algorithmstep 1 of 7

A router in Area 1 broadcasts its link state to the other routers in Area 1, and to nobody else. It builds a complete map of Area 1 and knows nothing of Area 2. That is the whole saving: the graph each router holds is one area, not one autonomous system.

The book describes this arrangement in words and draws no figure. Areas 1 and 2 are drawn touching the backbone, because an area border router genuinely belongs to two areas at once.

Read all steps as text

Each area runs its own link-state algorithm — A router in Area 1 broadcasts its link state to the other routers in Area 1, and to nobody else. It builds a complete map of Area 1 and knows nothing of Area 2. That is the whole saving: the graph each router holds is one area, not one autonomous system.
Area border routers belong to two areas — Within each area, one or more area border routers are responsible for routing packets outside the area. Every area border router in the autonomous system is also in the backbone. That is why they are drawn on the boundary.
The backbone is an area too, and there is exactly one — Its primary role is to route traffic between the other areas. It always contains all the area border routers in the AS, and may contain non-border routers as well — Rb here is one of those.
Leg 1 — intra-area routing to an area border router — R1 has a packet for R5, which is in another area. R1 cannot compute a path to R5, because R5 is not on its map. It routes to the area border router instead, using ordinary intra-area routing.
Leg 2 — across the backbone — ABR-1 hands the packet into the backbone, which carries it to the area border router that sits in the destination area. Here it passes through Rb, a backbone router in no other area.
Leg 3 — intra-area routing to the destination — ABR-2 is inside Area 2 and holds Area 2’s map, so from here it is ordinary intra-area routing again. Three legs: to a border router, through the backbone, then to the destination.
What R1 never had to know — R1 never held Area 2’s map, never ran Dijkstra over it, and never received one link-state advertisement from it. Add a third area and R1’s work does not grow at all.

The rules, in the book’s own order:

Each area runs its own OSPF link-state routing algorithm. Each router in an area broadcasts its link state to all other routers in that area.
Within each area, one or more area border routers are responsible for routing packets outside the area.
Exactly one OSPF area in the AS is configured to be the backbone area . Its primary role is to route traffic between the other areas.
The backbone always contains all area border routers in the AS, and may contain non-border routers as well.
Inter-area routing takes three legs. The packet is first routed to an area border router, which is ordinary intra-area routing. Then it is routed through the backbone to the area border router in the destination area. Then it is routed to the final destination.

In plain words

This is the same move made twice.

The Internet was too large for one graph, so it was cut into autonomous systems. Then one autonomous system turned out to be large too, so it can be cut into areas.

Both cuts do the same thing: they make the graph a router holds smaller, and they add a boundary where a special router has to know both sides.

Two hierarchies, two vocabularies

The words are similar and the levels are not. Keep them apart.

Between autonomous systems, the protocol is BGP (Border Gateway Protocol) , covered in section 5.4, and the boundary is a matter of ownership.

Between areas inside one autonomous system, the protocol is still OSPF, and the boundary is a matter of configuration. One organisation decides where its own areas begin and end.

An area border router is not a border between organisations. It is a border inside one.

The book closes by saying its own coverage has been brief, and points at RFC 2328 for the rest. OSPF is a large protocol.

Check yourself

0 of 7 answered

1.The book gives two reasons for dividing the Internet into autonomous systems. Suppose routers suddenly had unlimited memory and unlimited processing power. Would one flat routing computation then be acceptable?
2.An OSPF router's link state changes. Who receives the advertisement?
3.OSPF messages are carried directly by IP, with upper-layer protocol number 89. What does that force OSPF to do?
4.predictIn the weights diagram, the top path is two 1 Gbps links and the bottom path is two 10 Gbps links. The administrator sets every link weight to 1. What has Dijkstra been told about capacity?
5.What makes traffic engineering a reversal of cause and effect?
6.A packet in Area 1 is addressed to a host in Area 2 of the same autonomous system. What path does it take?
7.By default, are OSPF packets between routers authenticated?

What to remember

The flat model fails for two separate reasons: the Internet is too large, and it is owned by too many people. Faster hardware fixes only the first.
OSPF is Dijkstra from section 5.2.1, plus flooding, authentication and hierarchy. Each router builds a full map of the AS and computes its own shortest-path tree.
The administrator sets the weights, not OSPF. All ones gives minimum-hop routing; weights inverse to link rate steer traffic away from slow links. Traffic engineering runs that backwards: the wanted routing is known first, and the weights that produce it must be found.