Routing is the process of choosing the path that packets take from source to destination across a network. In distance vector routing, each router keeps a table of the best known distance (cost) to every destination and shares it periodically with its neighbours only.
Routing. Done by routers at the network layer. A routing algorithm builds the routing table; forwarding then uses the table to send each packet out on the right interface. Algorithms are static (fixed by the administrator) or dynamic/adaptive (adjust to topology and traffic changes).
Distance vector routing (DVR)
- Each router knows the cost of links to its direct neighbours.
- Each router keeps a vector: for every destination, the least cost and the next hop.
- Periodically, each router sends its whole vector to its neighbours.
- On receiving a neighbour's vector it applies the Bellman–Ford equation:
\[D_x(y) = \min_{v}\{\,c(x,v) + D_v(y)\,\}\]
where \(v\) ranges over the neighbours of \(x\).
Example. Three routers: A–B cost 2, B–C cost 3, A–C cost 7.
Initial table at A (only direct links known): to A = 0, to B = 2 (via B), to C = 7 (via C).
B sends its vector (A: 2, B: 0, C: 3) to A. A checks the route to C through B:
\[c(A,B) + D_B(C) = 2 + 3 = 5 < 7\]
So A updates: to C = 5, next hop B. Final table at A:
| Destination | Cost | Next hop |
|---|---|---|
| A | 0 | – |
| B | 2 | B |
| C | 5 | B |
Similarly, C learns it can reach A at cost 5 via B. After a few exchanges all tables converge.
Problem: count-to-infinity. Good news spreads fast, but when a link fails, routers may keep raising each other's costs slowly (bad news spreads slowly). Remedies: a maximum hop count (16 = infinity in RIP), split horizon, and poison reverse.
Example protocol: RIP (Routing Information Protocol) uses distance vector routing with hop count as the metric.