GATE CS
Distance vector and link state
Routing decides the path a packet should take; forwarding moves it one hop along that path. Distance-vector routers exchange their cost tables with neighbours and apply the Bellman-Ford update, while link-state routers flood the whole topology and run Dijkstra locally. Typical questions ask you to fill tables round by round, trace count-to-infinity, run Dijkstra and read off the next hop and cost.
3 previous-year questions · 3 solved · 5 practice questions
Forwarding is the per-packet action at a router: look up the destination in the forwarding table and send the packet out of the chosen interface. Routing is the process that builds that table, using a routing algorithm and information exchanged between routers.
A routing table entry, for the purposes of GATE, holds a destination, the cost of the best known path, and the next hop (the neighbour to hand the packet to). The cost is a metric: hop count, delay or any link weight the question gives. All link costs are positive unless the question says otherwise.
Property | Distance vector | Link state |
|---|---|---|
Each router knows | Its own link costs and each neighbour's advertised cost to each destination | The full map: every router and every link cost |
Tells whom | Its neighbours only | Every router in the network (or area), by flooding |
Tells what | Its whole table (a vector of costs) | Only the costs of its own links |
Computation | Bellman-Ford update, repeated | Dijkstra, run once per change |
EXAM TIP
Both algorithms aim at the same answer, the least-cost path. Questions differ in how fast and how safely each gets there, so read whether the question asks for the final table or the table after a fixed number of exchanges.
Each router starts knowing only the cost of its directly attached links (cost to itself is 0, unknown destinations are ). Periodically, and when its table changes, it sends its distance vector to its neighbours. On receiving a vector, a router recomputes each entry using the Bellman-Ford equation.
BELLMAN-FORD (DISTANCE-VECTOR) UPDATE
For y not equal to x (D_x(x) = 0). x is the router, N(x) its neighbours, c(x,v) the (positive) link cost to neighbour v, D_v(y) the cost to destination y that v advertised. The neighbour v giving the minimum is the next hop.
Initialise: cost 0 to self, link cost to each neighbour, elsewhere.
Receive the vectors of all neighbours (in a synchronous round, the vectors from the end of the previous round).
For each destination, add the link cost to the neighbour's advertised cost and take the minimum over neighbours.
If any entry changed, advertise the new vector; if none changed, the router has nothing new to send. The network has converged when no router's table changes in a round.
EXAM TIP
In synchronous rounds starting from the initial state (cold start, no link failures), information travels one hop per round: after exchanges, a router's cost to equals the least cost over paths to with at most links (the first link is known at the start). So it already has the correct cost to every destination that has a least-cost path of at most links. An entry that stays the same in one round can still change in a later round when news arrives from further away: in the next example, A's cost to D stays 5 in round 1 and drops to 4 in round 2.
WORKED EXAMPLE
Routers A, B, C, D have links A-B cost 1, B-C cost 2, C-D cost 1, A-D cost 5. Run synchronous distance-vector routing and give each router's cost to D after every round. Round 0 is the initial state, and in each round a router uses the neighbours' vectors from the end of the previous round.
Round 0 (own links only): A to D = 5 (direct), B to D = (B is not adjacent to D), C to D = 1.
Round 1: A = min(5 + 0, 1 + ) = 5. B = min(1 + 5 via A, 2 + 1 via C) = min(6, 3) = 3 via C. C = min(1 + 0, 2 + ) = 1.
Round 2: A = min(5 + 0 via D, 1 + 3 via B) = 4 via B. B = min(1 + 5, 2 + 1) = 3. C = min(1 + 0, 2 + 3) = 1.
Round 3: A = min(5, 1 + 3) = 4. B = min(1 + 4, 2 + 1) = 3 and C = 1 do not change. No entry changed (the entries to the other destinations are also unchanged), so the tables are stable.
Answer: Cost to D: A = 4 (next hop B), B = 3 (next hop C), C = 1 (next hop D). A switches from the direct link (5) to the path through B at round 2.
EXAM TIP
Do not use a neighbour's value from the same round you are computing in a synchronous question. A common error is to let A use B's round-1 value of 3 already in round 1, giving 4 one round too early.
Distance vector spreads good news fast but bad news slowly. If a link fails, a router may accept a route from a neighbour whose own route depended on the failed link (often a route through the router itself). Routers that point at each other then keep raising their costs, each time by the cost of the link between them, until the value passes the cost of a real alternative path (if one exists) or reaches the protocol's finite 'infinity' (for example 16 in RIP, where hop count is the metric). This is count-to-infinity, and during it packets loop.
WORKED EXAMPLE
A, B, C are in a line: A-B cost 1, B-C cost 1. Before failure A's cost to C is 2 and B's is 1. The B-C link fails. Assume no remedies (no split horizon or poison reverse), infinity = 16, and that B recomputes first using A's last advertised value, then A and B alternately recompute using the other's latest value. Trace the costs to C.
B has lost its direct route; A advertises 2, so B = 1 + 2 = 3.
A hears B = 3, so A = 1 + 3 = 4.
B = 1 + 4 = 5, A = 6, B = 7, A = 8, and so on: B takes the odd values, A the even values.
A reaches 16 (infinity) after B = 15. B then computes 1 + 16 = 17, capped at 16.
Answer: Costs climb 3, 4, 5, 6, ... A reaches 16 at the 14th recomputation and B at the 15th; only then is C known to be unreachable.
Remedy | What the router does | Limit |
|---|---|---|
Finite infinity | Treats a cost of 16 (or the protocol's limit) as unreachable | Caps the loop but also caps the network diameter |
Split horizon | Does not advertise a route out of the interface it learned it from | Stops loops between two neighbouring routers; does not stop loops through three or more routers |
Poison reverse | Advertises the route back out of that interface with cost | Same limit as split horizon, but the neighbour learns at once that it must not use you |
Hold-down | After a route becomes unreachable, ignores new routes to that destination for a fixed time | Slows recovery when a real alternative path exists |
Triggered updates | Sends an update immediately on a change instead of waiting for the timer | Speeds up convergence; does not remove the problem |
EXAM TIP
Split horizon (or poison reverse) solves the two-router case above: A's route to C goes through B, so A advertises C to B with cost (or not at all), and B, seeing no alternative, marks C unreachable at once. It is not a guarantee for every topology. Never write that it prevents count-to-infinity in general.
Each router discovers its neighbours and the cost of each link, builds a link-state packet (LSP) listing them (with a sequence number so stale copies are discarded), and floods it to all routers: a router that receives a new LSP forwards a copy on every interface except the one it arrived on. Every router ends up with the same link-state database, i.e. the same map, and runs Dijkstra's shortest-path algorithm on it with itself as the source.
DIJKSTRA RELAXATION
Applied to every neighbour v of the node u just made permanent (only tentative neighbours can improve). Requires all link costs to be non-negative.
Set and for all other nodes; all nodes are tentative.
Pick the tentative node with the smallest and make it permanent.
Relax every neighbour of using the formula above, and remember the predecessor whenever improves.
Repeat until all nodes are permanent. The next hop to a destination is the first node after the source on its shortest path.
DIJKSTRA RUNNING TIME
n routers, e links; a straightforward implementation scans for the minimum, a heap makes extraction logarithmic.
WORKED EXAMPLE
Links with costs: U-V 7, U-W 9, U-Z 14, V-W 10, V-X 15, W-X 11, W-Z 2, X-Y 6, Y-Z 9. Run Dijkstra from U and give U's forwarding table.
Start: U = 0. Relax U: V = 7, W = 9, Z = 14.
Smallest tentative is V (7), permanent. Relax V: X = 7 + 15 = 22; W via V = 17, not better than 9.
Next W (9), permanent. Relax W: X = min(22, 9 + 11) = 20 via W; Z = min(14, 9 + 2) = 11 via W.
Next Z (11), permanent. Relax Z: Y = 11 + 9 = 20.
Next X (20) (tie with Y), permanent. Y via X = 26, not better. Then Y (20), permanent.
Answer: Costs from U: V 7, W 9, Z 11, X 20, Y 20. Next hops at U: V via V, and W, Z, X, Y all via W.
EXAM TIP
When two tentative nodes tie, either may be chosen; the final costs are the same. Dijkstra can give wrong results with negative link costs, but routing metrics are non-negative.
Aspect | Distance vector | Link state |
|---|---|---|
Information sent | Whole vector, to neighbours only | Own link costs, to all routers by flooding |
Router's view | Costs only; the path is hidden | Complete topology |
Convergence | Slower; bad news can count to infinity | Usually faster; once flooding completes every router computes from the same map (short loops are possible while maps differ) |
Robustness | A wrong advertised cost is used by neighbours and passed on in their vectors, so the error can spread network-wide | A faulty router can misstate only its own links' costs; each router computes its own table |
Per-router computation | Light, repeated | Heavier (Dijkstra), memory for the whole map |
Examples | RIP | OSPF |
On a large network a flat scheme does not scale: tables grow and updates multiply. Hierarchical routing divides the network into autonomous systems (domains). Inside a domain an intra-domain protocol (distance vector or link state, for example RIP or OSPF) is used; between domains an inter-domain protocol (BGP, a path-vector protocol) is used, where policy decides which routes are accepted and advertised, not just least cost. Link-state domains are often split further into areas so that flooding stays within an area.
Protocol | Type | Scope | Carried over |
|---|---|---|---|
RIP | Distance vector (hop count, infinity = 16) | Intra-domain | UDP, port 520 |
OSPF | Link state | Intra-domain | Directly over IP (protocol number 89) |
BGP | Path vector | Inter-domain | TCP, port 179 |
EXAM TIP
To choose the next hop in a question, compute the full cost through each neighbour and take the smallest. In a distance-vector table the cost is link cost plus the neighbour's advertised cost, not the neighbour's advertised cost alone.
PREVIOUS-YEAR QUESTIONS
Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.
See these papers in full: GATE CSE 2025 Set 2 · GATE CSE 2023 · GATE CSE 2022
Consider the routing protocols given in List I and the names given in List II:
For matching of items in List I with those in List II, which ONE of the following options is CORRECT?
(i) – (a) and (ii) – (b)
(i) – (a) and (ii) – (a)
(i) – (b) and (ii) – (a)
(i) – (b) and (ii) – (b)
Which of the following statements is/are INCORRECT about the OSPF (Open Shortest Path First) routing protocol used in the Internet?
OSPF implements Bellman-Ford algorithm to find shortest paths.
OSPF uses Dijkstra's shortest path algorithm to implement least-cost path routing.
OSPF is used as an inter-domain routing protocol.
OSPF implements hierarchical routing.
Consider a network with three routers P, Q, R shown in the figure below. All the links have cost of unity. The routers exchange distance vector routing information and have converged on the routing tables, after which the link Q-R fails. Assume that P and Q send out routing updates at random times, each at the same average rate. The probability of a routing loop formation (rounded off to one decimal place) between P and Q, leading to count-to-infinity problem, is ______.
Tap to open full sizeThree boxes in a row labelled P, Q, R. P is joined to Q by a straight line, and Q is joined to R by a straight line. Every link has cost 1.
PRACTICE
Routers S, A, B, C, D have links with costs S-A 2, S-B 5, A-B 1, A-C 7, B-C 2, B-D 6, C-D 1. Link-state routing is used and S runs Dijkstra. What is the sum of S's least costs to A, B, C and D?
Answer:
A = 2 (direct).
B = min(5, 2 + 1) = 3 via A.
C = min(2 + 7 = 9, 3 + 2 = 5) = 5 via B.
D = min(3 + 6 = 9, 5 + 1 = 6) = 6.
Sum = 2 + 3 + 5 + 6 = 16.
Which of the following statements about distance-vector routing are correct?
With split horizon, a router does not advertise a route out of the interface from which it learned that route.
With poison reverse, a router advertises a route back out of the interface from which it learned that route, with cost infinity.
Split horizon guarantees that count-to-infinity cannot occur in any topology.
Count-to-infinity can occur after a link failure because a router may accept a route from a neighbour whose own route passes through the first router.
Answer: (A), (B), (D)
A and B are the definitions of split horizon and poison reverse.
C is false: loops involving three or more routers can still form.
D is correct: the two routers then raise each other's cost step by step until the finite infinity (or a real alternative's cost) is reached.
Five routers R1, R2, R3, R4, R5 form a chain with links R1-R2, R2-R3, R3-R4, R4-R5, each of cost 1. Distance-vector routing is run in synchronous rounds. Initially each router knows only its directly attached links (round 0). In each round every router recomputes using its neighbours' vectors from the previous round. After how many rounds does R1 first have the correct cost to R5?
Answer:
R1 knows R2 at round 0.
Round 1: R1 learns R3 (via R2's initial knowledge of R3), cost 2.
Round 2: R1 learns R4, cost 3, from R2's round-1 value for R4.
Round 3: R1 learns R5, cost 4, from R2's round-2 value for R5.
So 3 rounds (the path R1 to R5 has 4 links, and after k rounds paths of up to k + 1 links are known).
Router X has three neighbours: P (link cost 3), Q (link cost 2) and R (link cost 6). For destination Z, P advertises cost 5, Q advertises 7 and R advertises 1. Using the distance-vector update, X's cost to Z and next hop are:
7 via R
8 via P
9 via Q
1 via R
Answer: (A)
Via P: 3 + 5 = 8.
Via Q: 2 + 7 = 9.
Via R: 6 + 1 = 7.
The minimum is 7, through R. Option D forgets to add the link cost.
A, B, C are in a line with link costs A-B 1 and B-C 1. The B-C link fails. Distance-vector routing is used with no split horizon or poison reverse, with infinity = 16. Immediately after failure, B recomputes first from A's last advertised cost to C (which was 2); thereafter A and B alternately recompute from the other's latest value. At the moment A's cost to C first becomes 16, B's cost to C is:
15
16
17
14
Answer: (A)
B = 1 + 2 = 3, A = 1 + 3 = 4, B = 5, A = 6, and so on.
B takes the odd values 3, 5, ..., 15 and A the even values 4, 6, ..., 16.
A reaches 16 right after B = 15, so B's cost at that moment is 15.
OFFICIAL GATE 2027 SYLLABUS WORDING
Copied from the GATE 2027 syllabus; see all 2027 syllabi.
GATE CS
Distance vector and link state routing
Preparing in Kolkata? IAE Academy's course for GATE CSE.
