--- title: "Link-state and distance vector routing" subject: "Telecommunications" chapter: 8 key: "semester_8/telecommunications:link-state-distance-vector" source: https://www.bctengineer.com/q/semester_8/telecommunications/link-state-distance-vector site: BCT Engineering --- # Link-state and distance vector routing Telecommunications ยท Chapter 8: Data Communication - Asked in: 2080 Baisakh, 6 marks - Video: [CN 20 : Distance Vector VS Link State Routing | Examples](https://www.youtube.com/watch?v=0Q3SEa9qyAI) โ€” CS & IT Tutorials by Vrushali ๐Ÿ‘ฉโ€๐ŸŽ“ - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_8/telecommunications/link-state-distance-vector - Whole chapter: https://www.bctengineer.com/md/semester_8/telecommunications/chapter-8 ## Question Describe the working mechanism of link-state routing and distance vector routing with the help of Dijkstra's algorithm and Bellman-Ford algorithm. ## Short answer Link-state routing floods LSPs so all routers know the topology and run Dijkstra; in the example, A's shortest paths are B via B, C via B, D via B, E via B. Distance-vector exchanges neighbour tables and uses the Bellman-Ford equation D_x(y)=min_v{c(x,v)+D_v(y)}; it converges to the same routes but slowly, with count-to-infinity. ## Answer Both are **dynamic (adaptive) routing** methods. In **link-state** routing every router learns the whole map and runs **Dijkstra's algorithm**; in **distance-vector** routing every router only exchanges distance tables with its neighbours and uses the **Bellman-Ford** equation. Example network used below (link costs shown): ```text A 2 / \ 6 / \ B --3-- C | / | 7| 2/ |4 | / | D --1-- E ``` #### Link-state routing (Dijkstra) 1. Each router finds its neighbours (HELLO packets) and measures the cost of each link. 2. It builds a **link state packet (LSP)**: its ID, sequence number, age and the list of neighbours with costs. 3. LSPs are **flooded** to all routers; each router stores them in a link-state database, so all routers have the same topology. 4. Each router runs **Dijkstra** with itself as root: - Put the source in the permanent set with $D=0$; set other $D$ = link cost or $\infty$. - Repeatedly make permanent the tentative node with the least $D$, then for each neighbour $v$ update $D(v) = \min(D(v),\ D(u) + c(u,v))$. Dijkstra from A: | Step | Permanent set | B | C | D | E | |---|---|---|---|---|---| | 1 | A | 2, A | 6, A | โˆž | โˆž | | 2 | A, B | **2, A** | 5, B | 9, B | โˆž | | 3 | A, B, C | | **5, B** | 7, C | 9, C | | 4 | A, B, C, D | | | **7, C** | 8, D | | 5 | A, B, C, D, E | | | | **8, D** | Routing table of A: to B via B (2), C via B (5), D via B (7), E via B (8). Used in OSPF and IS-IS. #### Distance-vector routing (Bellman-Ford) 1. Each router keeps a vector of its best known distance and next hop to every destination; at start it knows only its direct links. 2. Periodically (e.g. every 30 s in RIP) it sends its vector to its neighbours only. 3. On receiving vectors, router $x$ updates each destination $y$ using $$ D_x(y) = \min_{v \in \text{neighbours}} \{\, c(x,v) + D_v(y) \,\} $$ 4. Repeating this, the tables converge to the shortest paths. For A, neighbours are B (cost 2) and C (cost 6), with converged vectors $D_B = (A2, C3, D5, E6)$ and $D_C = (A5, B3, D2, E3)$: $$ \begin{aligned} D_A(C) &= \min(2+3,\ 6+0) = 5 \ \text{(via B)} \\ D_A(D) &= \min(2+5,\ 6+2) = 7 \ \text{(via B)} \\ D_A(E) &= \min(2+6,\ 6+3) = 8 \ \text{(via B)} \end{aligned} $$ This is the same result as Dijkstra, reached in 3 exchange rounds (A's vector after rounds: E = 10, 9, 8). #### Comparison | Link state | Distance vector | |---|---| | Knows full topology | Knows only neighbours' vectors | | Floods small LSPs to all | Sends full table to neighbours | | Fast convergence, loop-free | Slow, count-to-infinity problem | | More memory and CPU | Simple, less memory | ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does a link-state router flood to all routers? A. Its Dijkstra tree B. Only HELLO packets C. Its full routing table to neighbours D. A link state packet with its ID, sequence number, age and neighbour costs Answer: D. LSPs give every router the same topology database. (Key point: LSP flooding) 2. In Dijkstra, which node is made permanent next? A. A random neighbour B. The tentative node with the least D C. The destination D. The one with the largest D Answer: B. Then neighbours are updated with D(v) = min(D(v), D(u) + c(u,v)). (Key point: Dijkstra step) 3. A has neighbours B (cost 2) and C (cost 6), D_B(E)=6 and D_C(E)=3. What is D_A(E) and the next hop? A. 3 via B B. 6 via C C. 8 via B D. 9 via C Answer: C. min(2+6, 6+3) = min(8, 9) = 8, via B. (Key point: DV computation) 4. What does a distance-vector router send, and to whom? A. Its full vector, to neighbours only B. Nothing until a failure C. Link costs, to all routers D. A map to the ISP Answer: A. Periodically (e.g. 30 s in RIP) to neighbours only, unlike link-state flooding. (Key point: Information exchanged) ## Related in Telecommunications - [Link-state routing as adaptive routing](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Alink-state-adaptive-example) โ€” 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ร— - [Strowger switching mechanism](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Astrowger-switching-principle) โ€” Telecommunications, chapter 1 ## Related in other subjects - [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ร— - [Dijkstra's shortest path algorithm](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Adijkstra-algorithm-example) โ€” Data Structure and Algorithm, chapter 10, asked 2ร— - [Algorithm and flowchart help; Armstrong flowchart](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgorithm-flowchart-armstrong) โ€” Computer Programming, chapter 2 - [OSPF working with routing tables](https://www.bctengineer.com/question.md?key=semester_8%2Finternet_and_intranet%3Aospf-working-routing-tables) โ€” Internet and Intranet, chapter 2