Routing formulas

Routing: distance vector and link state. 3 formulas for GATE CS Computer Networks, each with when to use it. Each is explained in the topic notes.

All 3 Routing formulas

BELLMAN-FORD (DISTANCE-VECTOR) UPDATE

D_{x} (y) = v \in N (x) min {c (x, v) + D_{v} (y)}

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.

DIJKSTRA RELAXATION

d (v) = min {d (v), d (u) + c (u, v)}

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.

DIJKSTRA RUNNING TIME

T = O (n^{2}) (array), T = O ((n + e) lo g n) (binary heap)

n routers, e links; a straightforward implementation scans for the minimum, a heap makes extraction logarithmic.

Where this was asked: 2022 (1), 2023 (1), 2025 (1). See the 3 previous-year questions on Routing. This shows what was asked, not what will be asked.

KEEP GOING

Routing: the notes and 3 solved previous-year questions