- 2076 Asoj · 6 marks
Link-state routing as adaptive routing
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.
Use examples to show that the link-state routing protocol is an adaptive routing algorithm.
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
- Discover neighbours (HELLO packets).
- Measure the cost (delay/load) of each link, e.g. by ECHO packets.
- Build an LSP (router ID, sequence number, age, neighbours and costs).
- Flood the LSP to all routers.
- 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)
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.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Adaptive and non-adaptive routing algorithms · Telecommunications, chapter 8 · asked 3×
- Link-state and distance vector routing · Telecommunications, chapter 8
- Short note: Routing algorithm in data communication · Telecommunications, chapter 8 · asked 2×
- Routing and need of routing protocol · Computer Networks and Security, chapter 4 · asked 2×
- Routing Information Protocol (RIP) · Computer Networks and Security, chapter 4
- Routed vs routing protocol · Computer Networks and Security, chapter 4
- Distance vector vs link state routing · Computer Networks and Security, chapter 4 · asked 5×