--- title: "Link-state routing as adaptive routing" subject: "Telecommunications" chapter: 8 key: "semester_8/telecommunications:link-state-adaptive-example" source: https://www.bctengineer.com/q/semester_8/telecommunications/link-state-adaptive-example site: BCT Engineering --- # Link-state routing as adaptive routing Telecommunications · Chapter 8: Data Communication - Asked in: 2076 Asoj, 6 marks - Video: [Link state routing | computer networks](https://www.youtube.com/watch?v=HKYQveom2Ew) — INFOSTREAM ENGINEERING - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_8/telecommunications/link-state-adaptive-example - Whole chapter: https://www.bctengineer.com/md/semester_8/telecommunications/chapter-8 ## Question Use examples to show that the link-state routing protocol is an adaptive routing algorithm. ## Short answer Link-state routing is adaptive because routers measure link costs, flood LSPs on changes, and rerun Dijkstra. In the example, when B-C cost rises from 3 to 10, A's route to E changes from A-B-C-D-E to A-C-D-E; when C-D fails, it becomes A-B-C-E. ## Answer An **adaptive routing algorithm** changes its routes automatically when the topology or traffic changes. Link-state routing is adaptive because every router keeps measuring its link costs, floods a new **link state packet (LSP)** whenever a cost changes or a link fails, and every router then re-runs **Dijkstra's algorithm** on the updated map. #### Steps of link-state routing 1. Discover neighbours (HELLO packets). 2. Measure the cost (delay/load) of each link, e.g. by ECHO packets. 3. Build an LSP (router ID, sequence number, age, neighbours and costs). 4. Flood the LSP to all routers. 5. Each router computes shortest paths with Dijkstra. Steps 2–5 repeat periodically and on any change, which is what makes it adaptive. #### Example network (normal state) ```text A 2 / \ 6 / \ B --3-- C | / | 7| 2/ |4 | / | D --1-- E ``` Dijkstra at A (cost, previous node): | Step | Made permanent | B | C | D | E | |---|---|---|---|---|---| | 1 | A | 2, A | 6, A | ∞ | ∞ | | 2 | B | – | 5, B | 9, B | ∞ | | 3 | C | – | – | 7, C | 9, C | | 4 | D | – | – | – | 8, D | | 5 | E | – | – | – | – | Routes from A: C via A–B–C (5), D via A–B–C–D (7), E via A–B–C–D–E (8). All traffic leaves A on link A–B. #### Change 1: link B–C becomes congested (cost 3 → 10) B and C measure the higher delay and flood new LSPs. A re-runs Dijkstra: | Step | Made permanent | B | C | D | E | |---|---|---|---|---|---| | 1 | A | 2, A | 6, A | ∞ | ∞ | | 2 | B | – | 6, A | 9, B | ∞ | | 3 | C | – | – | 8, C | 10, C | | 4 | D | – | – | – | 9, D | New routes: C via A–C (6), D via A–C–D (8), E via A–C–D–E (9). Traffic to C, D and E now leaves on link A–C and avoids the congested link. #### Change 2: link C–D fails (B–C back to cost 3.) C and D stop getting HELLO replies and flood LSPs without that link. A re-runs Dijkstra and gets: C via A–B–C (5), D via A–B–D (2 + 7 = 9) and E via A–B–C–E (5 + 4 = 9). | Situation | Route A→E | Cost | |---|---|---| | Normal | A-B-C-D-E | 8 | | B–C congested | A-C-D-E | 9 | | C–D failed (B–C normal) | A-B-C-E | 9 | The routing tables follow the state of the network without any manual change, so link-state routing (e.g. OSPF) is an adaptive routing algorithm. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What makes link-state routing an adaptive algorithm? A. Routes are fixed by the administrator at start-up B. Routers re-measure link costs, flood new LSPs on a change and re-run Dijkstra C. Each router only uses the queue length of its own links D. Packets choose a random next hop at every router Answer: B. Adaptive means routes follow topology and traffic changes; link-state does this by flooding updated LSPs and recomputing shortest paths. (Key point: Why link-state is adaptive) 2. Which set correctly describes what a link state packet carries? A. Full routing table of the sender B. Router ID, sequence number, age, neighbours and their costs C. Only the destination address and hop count D. The Dijkstra tree of the sender Answer: B. An LSP holds the sender's ID, sequence number, age and the list of neighbours with link costs. (Key point: Contents of an LSP) 3. In the example, B-C cost rises from 3 to 10. How does A reach C afterwards? A. A-B-C with cost 12 B. A-B-C with cost 5 C. Directly on A-C with cost 6 D. C becomes unreachable Answer: C. Via B the cost is now 2+10 = 12, so direct A-C (6) is cheaper and traffic avoids the congested link. (Key point: Effect of congestion on B-C) 4. With C-D failed and B-C back to 3, what is the route and cost from A to E? A. A-B-C-E, cost 9 B. A-B-C-D-E, cost 8 C. A-C-E, cost 10 D. A-B-D-E, cost 10 Answer: A. Without C-D, the best path is A-B-C-E = 2+3+4 = 9. (Key point: Effect of link failure C-D) ## Related in Telecommunications - [Adaptive and non-adaptive routing algorithms](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Aadaptive-nonadaptive-routing) — Telecommunications, chapter 8, asked 3× - [Link-state and distance vector routing](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Alink-state-distance-vector) — Telecommunications, chapter 8 - [Short note: Routing algorithm in data communication](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Arouting-algorithm-data-comm) — Telecommunications, chapter 8, asked 2× ## Related in other subjects - [Routing and need of routing protocol](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Arouting-protocol-necessity) — Computer Networks and Security, chapter 4, asked 2× - [Routing Information Protocol (RIP)](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Arip-protocol) — Computer Networks and Security, chapter 4 - [Routed vs routing protocol](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Arouted-vs-routing-protocol) — Computer Networks and Security, chapter 4 - [Distance vector vs link state routing](https://www.bctengineer.com/question.md?key=semester_7%2Fcomputer_networks_and_security%3Adv-vs-link-state) — Computer Networks and Security, chapter 4, asked 5×