CAP7001 · Unit 4: Network layer
Link state routing and OSPF
10 practice questions · in the ETE syllabus
Key points
- Routers flood LSAs and run Dijkstra on the same database
- OSPF cost = reference bandwidth / link bandwidth, minimum 1
- Areas limit flooding and connect through area 0
- DR and BDR cut adjacencies to 2n - 3 on a LAN
- A higher LSA sequence number means a newer LSA
In link state routing every router floods link state advertisements (LSAs) describing its own links. All routers in the area then hold the same database, and each runs Dijkstra's shortest path first algorithm to build a shortest path tree with itself as the root. This differs from distance vector, where routers share only their tables with neighbours.
OSPF is the standard link state protocol. Its cost is reference bandwidth divided by interface bandwidth, with the common default reference of 100 Mbps and a minimum cost of 1: a 10 Mbps link costs 10, a 100 Mbps link costs 1 and a 1 Gbps link also costs 1.
Key features:
- Areas limit flooding and keep databases small; all areas connect through area 0, the backbone.
- Hello packets discover and maintain neighbours.
- DR and BDR on a broadcast LAN reduce adjacencies. With n routers, a full mesh needs n(n-1)/2 adjacencies, while a DR and BDR give 2n - 3, so 7 instead of 10 for five routers.
- A higher LSA sequence number marks a newer LSA, and older copies are discarded.
Worked example: with costs A-B 4, A-C 2, B-C 1, B-D 5 and C-D 8, Dijkstra from A finds A-C-B-D at 2 + 1 + 5 = 8.
Exam trap: with a 100 Mbps reference, two 1 Gbps hops cost 2 and lose to one direct 100 Mbps hop of cost 1.
Try two questions
How does link state routing differ from distance vector routing?
- Routers send only their table and trust their neighbours' computed costs
- Routers keep a next hop and learn nothing of the topology
- Every router holds the full topology and computes its own shortest paths
- Routers exchange updates with a single central controller
Show the answer
C. In link state routing every router runs the same computation on the same database.
Why not A: That describes distance vector routing.
Why not B: That also describes distance vector routing.
Why not D: Link state routing is distributed, not controller based.
Five OSPF routers share one broadcast LAN and a DR and a BDR are elected. How many full adjacencies form?
- 7
- 10
- 5
- 4
Show the answer
A. Each of the three other routers pairs with both DR and BDR, plus the DR-BDR pair: 2 x 3 + 1 = 7.
Why not B: That is the number of pairs in a full mesh of five routers.
Why not C: That counts only one adjacency per router.
Why not D: That counts only the adjacencies of the DR.