Computer Networking › Section E · The network layer: control plane › Topic E.2
Intra-AS routing: OSPF
No router could run Dijkstra over the whole internet, and no ISP wants strangers deciding how traffic crosses its network. The internet therefore splits routing into pieces, and inside each piece the most common choice is OSPF, link-state routing put into practice.
Why routing is split up
The algorithms in Routing algorithms: link state and distance vector treat all routers as one flat graph. The real internet breaks that model in two ways. Scale: with hundreds of millions of routers, flooding every link cost everywhere and storing every destination would be impossible. Administrative autonomy: each ISP or company wants to run its own network its own way, choose its own costs and hide its internal design. The answer is to group routers into autonomous systems (ASes), each under one administration and identified by an AS number. Routing inside an AS is intra-AS routing; routing between ASes, covered in the next topic, is inter-AS routing.
Intra-AS routing
All routers within one AS run the same intra-AS routing protocol, chosen by the AS's operator, and that protocol computes paths to every destination inside the AS. Different ASes may choose different protocols, since the choice affects no one else. The main options are OSPF (Open Shortest Path First) and its close cousin IS-IS, both link state, which dominate in ISPs and large enterprises. RIP, the distance-vector protocol, survives in small networks. Some enterprise networks have used EIGRP, originally a Cisco protocol. An AS can be a whole national ISP, or an ISP may divide its network into several ASes.
How OSPF works
OSPF is a link-state protocol. Each router discovers its neighbours by sending periodic Hello messages, then describes its own links, with their costs, in link-state advertisements (LSAs). These are flooded to every router in the area, so all of them hold the same link-state database, a complete map. Each router runs Dijkstra on that map with itself as the source, giving a shortest-path tree to every subnet, and turns the result into forwarding-table entries. A router floods an LSA whenever a link's state or cost changes, and also refreshes each of its LSAs periodically, at least every 30 minutes, so stale information eventually disappears.
Link weights are the operator's choice
OSPF does not decide what a link should cost; the network administrator does. Setting every cost to 1 gives minimum-hop routing. A common default divides a reference bandwidth by the link's bandwidth, so faster links look cheaper. Operators then adjust weights to steer traffic, a practice called traffic engineering: raising one link's weight pushes flows onto other paths. Because the protocol only computes least-cost paths for whatever weights it is given, choosing the weights is where the real routing policy of the AS lives.
Worked example: bandwidth-based costs
An ISP sets a reference bandwidth of 100 Gbps, so cost = 100 Gbps ÷ link bandwidth. 1. A 100 Gbps link costs 1, a 10 Gbps link costs 10, and a 1 Gbps link costs 100. 2. From R1 to R9 there are two paths: two hops over 10 Gbps links, costing \(10 + 10 = 20\), or four hops over 100 Gbps links, costing \(1 + 1 + 1 + 1 = 4\). 3. OSPF chooses the four-hop path, cost 4, despite its extra hops. 4. If the operator wants less traffic on that path, raising one of its links to cost 20 makes it total 23, so traffic moves to the 20-cost path. Check: the decision always follows summed weights, not hop counts.
Features beyond plain Dijkstra
OSPF adds several practical features. Messages run directly over IP, with protocol number 89, rather than over TCP or UDP. They can be authenticated, so that only trusted routers can inject LSAs; without this, an intruder could advertise false costs. When several paths to a destination share the same least cost, OSPF can install all of them and spread traffic across them, equal-cost multipath (ECMP). A multicast extension, MOSPF, was once defined but is now obsolete. OSPFv2, defined in RFC 2328, handles IPv4; OSPFv3 carries IPv6. OSPF also scales through hierarchy, as the next card shows.
Areas and the backbone
A large OSPF network can be divided into areas. Each area floods LSAs only among its own routers and runs its own copy of Dijkstra, so a link flapping in one area does not make every router in the AS recompute. One special area, the backbone, area 0, connects all the others, and every other area must attach to it. Area border routers belong to both an area and the backbone; they summarise their area's subnets and advertise them into the backbone. Traffic between two areas therefore travels from its area to an area border router, across the backbone and down into the destination area.
Worked example: a link fails
Inside one OSPF area, the link between routers R4 and R7 is cut, and the hardware does not report it. Routers here send Hellos every 10 seconds and declare a neighbour dead after 40 seconds of silence. 1. R4 and R7 stop hearing each other's Hellos. 2. After 40 seconds each declares the other dead. 3. Each floods a new LSA that no longer lists the R4–R7 link. 4. Every router in the area updates its link-state database and reruns Dijkstra. 5. Routes that used the link switch to the next-cheapest path, and forwarding tables are rewritten. Check: detection took up to 40 seconds, but recomputation itself is fast, which is why operators often add faster failure-detection mechanisms.
Common mistakes to avoid
First, assuming OSPF minimises hops; it minimises the sum of operator-chosen weights. Second, thinking OSPF runs over TCP or UDP; its messages ride directly on IP as protocol 89. Third, believing every OSPF router floods to the whole AS; in a multi-area design, flooding stays within each area. Fourth, forgetting that all areas must connect to the backbone, area 0. Fifth, confusing intra-AS and inter-AS routing: OSPF never chooses paths between different organisations. Sixth, treating ECMP as a tie that OSPF breaks at random; it can use all equal-cost paths at once.
Key takeaways
Scale and administrative autonomy divide the internet into autonomous systems, each running one intra-AS protocol of its operator's choice. OSPF is a link-state protocol: routers discover neighbours with Hellos, flood LSAs on changes and at least every 30 minutes, and run Dijkstra on the shared map. Administrators set the link weights, which embody routing policy and allow traffic engineering. OSPF runs directly over IP (protocol 89), supports authentication and equal-cost multipath, and scales with areas joined by the backbone, area 0, through area border routers. OSPFv2 is for IPv4 and OSPFv3 for IPv6.
Flashcards
Flashcard
A group of routers under one administration, with an AS number
Test your understanding
Question 1 of 5
With a reference bandwidth of 100 Gbps, path P uses three 10 Gbps links and path Q uses one 1 Gbps link. Which does OSPF choose?
Question 2 of 5
What are the two main reasons the internet groups routers into autonomous systems?
Question 3 of 5
How are OSPF messages carried between routers?
Question 4 of 5
In a multi-area OSPF network, what happens when a link flaps inside area 3?
Question 5 of 5
Two paths to a subnet both have OSPF cost 12. What can OSPF do?
